Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1999-01-29
2001-02-06
Powell, Mark R. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S440000, C345S428000
Reexamination Certificate
active
06184894
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to 3D graphics systems, and more particularly to transitioning between level-of-detail (LOD) texture maps.
BACKGROUND OF THE INVENTION
Three-dimensional (3D) graphics systems are becoming more common on low-cost and portable personal computer (PCs). The surfaces of 3D objects are approximated as triangles that are transformed and displayed from the user's perspective. Often a repeating pattern or texture is applied to these surfaces for added realism.
The texture is stored in texture maps of varying levels of detail (LOD). Object surfaces closer to the user are shown in more detail by using a texture map with a high LOD, while far-away surfaces are shown with little texture detail by using a texture map with a coarser LOD. The texture pixels (texels) in the texture map are used to modify or modulate the pixels being displayed for the triangle to add the texture to the triangle.
FIG. 1
shows texture maps with three different levels-of detail. The LOD=3 map is an 8×8 texture map with 8 rows of 8 texels; a total of 64 texels. This level of detail may be used for surfaces at some distance to the viewer. The LOD=2 map has only 4×4 or 16 texels. Each texel in the 4×4 map may be generated by averaging together four pixels in the 8×8 map.
The coarsest level map is a 1×1 LOD
0
map with only one texel. The LOD
0
map is generated from the LOD=1 map by ‘averaging’ together groups of pixels in the 2×2 map for each texel in the 1×1 map. The LOD=0 map is used for more distant object surfaces that show little surface-texture detail.
When the triangle is parallel to the viewer so that all pixels are nearly the same distance (depth) from the viewer, the texels on a single LOD map can be applied directly to the pixels from a single LOD map. However, as triangles rotate with respect to the viewer, some pixels on the triangle are at a greater distance from the viewer than others. Perspective correction is required when using linear interpolation rasterization.
The u,v coordinate values calculated may not be exact integer values. The pixel may fall between texels on the texture map. Then the texture value for the pixel may be calculated by a distance-weighted average of the four closest texels to the exact u,v coordinate. This is known as bi-linear interpolation since interpolation is performed linearly in each of the two dimensions of a single LOD texture map.
The LOD map selected depends on the rate of change or derivative of the u,v values with respect to the x and y pixel coordinates. Triangles at high or glancing angles to the viewer have many u,v points per screen pixel (x and y values) and thus have at least one high derivative of u,v with respect to x,y. The largest of the four derivatives (du/dx, dv/dx, du/dy, dv/dy) may be used to determine the LOD map to select for a pixel, although more correct methods may be used.
LOD Map Selection—
FIG. 2
FIG. 2
is a graph showing selection of LOD maps using derivatives. LOD map
10
is the finest-detail map, having 2
10
×2
10
texels, or 1024×1024. The coarsest map, LOD
0
, has only one texel (2
0
×2
0
or 1×1). The largest of the four derivatives of texture-space coordinates u,v with respect to screen coordinates x,y is used to select which LOD map to use. For example, when the largest derivative is 2
9
or more, the coarsest map, LOD
0
, is selected. When the largest derivative is less than 2
0
or 1, then the finest-detail map is used, LOD
10
.
The LOD-transition function shown by steps
10
is a step function. As the largest derivative doubles, the next-coarser LOD map is selected. For example, derivatives of 2
4
to 2
5
−1 use LOD
5
, a 2
5
×2
5
(32×32) map. Once the derivative reaches
25
, the next-coarser LOD map is chosen. The abrupt transition from one LOD map to the next can sometimes be seen as a sudden change from a sharp image to a less sharp image. In real-time, this appears as a wave—several may be visible at different ranges—moving across the data base as the viewer moves across the data base.
Bi-linear interpolation is inadequate since abrupt, noticeable changes in image sharpness can occur as the next LOD map is selected. To eliminate these artifacts, tri-linear interpolation is often used. Tri-linear interpolation performs bi-linear interpolation for 2 adjacent LOD maps. Four texels on one LOD map are averaged to produce a first bi-linear result for one LOD map, and then four texels on an adjacent LOD map are averaged to produce a second bi-linear result. The first and second bi-linear results are then linearly interpolated. The interpolation factor is the complement of the fraction of the largest derivative value.
FIG. 3
is a graph showing LOD ‘smoothing’ using tri-linear interpolation. The texel results from two adjacent LOD maps are linearly interpolated for tri-linear interpolation.
For bi-linear interpolation, the LOD-transition function is shown by steps
10
is a step function. With tri-linear interpolation, a weighted average of the two adjacent LOD maps is used to produce texel values. For example, when the largest derivative is 6, the texture map for LOD
7
is used for bi-linear interpolation. Tri-linear interpolation also selects the next-coarser LOD map, LOD
6
. The bi-linear average of the four adjacent texels on LOD
6
is then averaged with the LOD
7
average to produce the tri-linear result. This result falls on the tri-linear line
12
.
Tri-linear line
12
thus smoothes out the abrupt steps
10
of bi-linear interpolation. Texels from two LOD maps are averaged. This improves image quality by eliminating the noticeable changes in level-of-detail. However, tri-linear interpolation produces some blurring of the image, and also increases the complexity of the calculations required by the graphics engine.
Kamen et al., U.S. Pat. No. 5,812,141, discloses an adaptive texture-mapping controller. Different interpolation methods are used based on the hierarchical level (primitive, span, pixel) and control signals. Economy et al., U.S. Pat. No. 5,367,615, describes a smoothing scheme for providing finer detail based on the polygon density. Yang, U.S. Pat. No. 5,719,599, describes a method for providing more effective scanning of textured surfaces. While useful, a better scheme for smoothing LOD transitions and reducing complexity is desired.
What is desired is a 3D graphics system that adapts the interpolation method. It is desired to reduce computational complexity when using tri-linear interpolation. It is desired to dynamically use either bi-linear or tri-linear interpolation. It is desired to smooth the abrupt bi-linear transitions from one LOD to another LOD. It is further desired to use tri-linear interpolation only near LOD transitions, while using bi-linear interpolation when the LOD is not near a transition.
SUMMARY OF THE INVENTION
An intermittent tri-linear interpolator for a graphics engine has a texel memory that stores texels indicating texture attributes of pixels for display on a display screen. The texels are arranged into a plurality of level-of-detail LOD maps. The LOD maps are for applying different levels of detail of texture onto pixels.
A bi-linear interpolator is coupled to receive four texels from a current LOD map in the texel memory. The four texels are the four closest approximations to a pixel. The bi-linear interpolator generates a first average texel from the four texels. The first average texel is a closer approximation for the pixel than any of the four texels.
An LOD-map selector is coupled to the texel memory. It selects the current LOD map for the pixel from the plurality of LOD maps.
A second bi-linear interpolator is coupled to receive another four texels from a next LOD map in the texel memory. The another four texels are the four closest approximations to the pixel. The second bi-linear interpolator generates a second average texel from the another four texels. The second average texel is a closer approximation
Pimpalkhare Mangesh S.
Rosman Andrew
Auvinen Stuart T.
NeoMagic Corp.
Powell Mark R.
Yang Ryan
LandOfFree
Adaptive tri-linear interpolation for use when switching to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive tri-linear interpolation for use when switching to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive tri-linear interpolation for use when switching to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2594930