Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-04-16
2001-03-20
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S182000, C345S156000, C345S426000, C345S440000
Reexamination Certificate
active
06204857
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to real-time computer image generation systems and, more particularly, to means and method for selecting effectively an appropriate level of detail (LOD) of stored information for representing an object to be displayed.
BACKGROUND OF THE INVENTION
In certain real-time computer image generation systems, objects to be displayed are represented by convex polygons which may include texture information for rendering a more realistic image. The texture information is typically stored in a plurality of two-dimensional texture maps, with each texture map containing texture information at a predetermined level of detail (“LOD”) with each coarser LOD derived from a finer one by filtering as is known in the art. Further details regarding computer image generation and texturing, can be found in U.S. Pat. No. 4,727,365, U.S. Pat. No. 4,811,245 and U.S. Pat. No. 4,692,880 which are incorporated herein in their entirety by reference thereto.
Selection of the most appropriate LOD for obtaining texture for polygons representing an object requires consideration of the apparent distance of the object from a viewpoint and the angle between a vector from the viewpoint to a pixel on the polygon and the normal vector of the polygon. These two factors determine the size of the projected pixel footprint in the texture space. As the polygon moves further away from the viewpoint the footprint will decrease in size, or as it moves closer it will increase in size on the polygon. Also the angle between the view ray and the polygon normal will give a measure of how “edge on” the polygon is. As the polygon becomes more edge on in a direction the footprint will grow in size along that dimension. When moving from screen pixel to screen pixel the texture coordinate rate of change will continue to change. This non-linear relationship is why perspective mapping in necessary. The u and v texture coordinates are not linear in screen space as soon as the polygon is not perpendicular to the viewer.
Some prior art techniques had resolved to calculate an LOD value per polygon which only allowed one LOD of a map per polygon. Sometimes polygons are sub-divided (tesselated) to obtain more than one LOD per polygon. While this works well for pixels that project into polygons that are perpendicular to the viewer, texture mapping for perspective projections requires further incremental calculation techniques to generate accurate texture addresses on a per pixel basis. Such texture mapping techniques in perspective requires the calculation of texture address partial derivatives or delta values which are used to determine the appropriate LOD for texture mapping and described mathematically as:
∂
u
∂
x
,
∂
u
∂
y
,
∂
v
∂
x
,
∂
v
∂
y
These values represent the rate of change of the U and V texture addresses with respect to one pixel change in the X or Y pixel directions on a computer display screen. Intuitively, the magnitude of each term describes the distance covered in the finest LOD level of the texture map by the projection of a pixel onto the surface of a textured polygon in the specified direction. In other words, when progressing from one pixel to the next neighboring pixel in screen X space, dU/dX is measure of how much U changes in the texture map. Another way to think of these terms is that the larger the magnitude of the term the more compressed the texture is in the specified direction. If a high frequency signal, such as a compressed texture address, is point sampled at a lower frequency, such as the pixel centers on the screen, aliasing can result. This aliasing produces undesirable visual anomalies such as scintillation or “texture swimming”, where the texture pattern appears to float around on the top of a polygon when in motion. By pre-filtering the texture images into multiple LODs the unwanted visual artifacts can be avoided. The above terms are used to select the texture image which has the appropriate amount of filtering applied on a pixel-by-pixel basis. The term with the largest rate of change should dominate the LOD selection criteria, otherwise the sampled texture in that direction may scintillate. This approach generally minimizes visual artifacts at the expense of blurring the resulting image in other directions. A simple maximum of all four gradient terms however, is not sufficient because the magnitude of the terms can change as the polygon rotates and effectively select a different LOD for the same pixel, depending on the orientation of the polygon. One approach for reducing this problem has been proposed as set forth by Paul Heckbert's Master's Thesis, University of California, Berkeley, June 1989 which sets forth an LOD calculation in accordance with equation (1) as follows:
LOD
Heckbert
=
log
2
[
max
[
(
∂
u
∂
x
)
2
+
(
∂
v
∂
x
)
2
,
(
∂
u
∂
y
)
2
+
(
∂
v
∂
y
)
2
]
]
(
1
)
Techniques have been implemented to approximate such texture address partial derivatives, however, they have proven to be very computer resource intensive, requiring many floating point operations which are often difficult and impractical to implement in real-time, 3-D computer graphics applications.
Thus, it would be highly desirable to provide a method for generating instantaneous texture address values used to calculate an LOD on a per pixel basis, in real-time, that requires minimum operations and results in a visually effective texture mapped perspective object.
SUMMARY OF THE INVENTION
In accordance with the present invention, the rate of change of texture addresses when mapped to individual pixels of a polygon is used to obtain the correct level of detail (LOD) map from a set of pre-filtered maps. The method comprises a first determination of perspectively correct texture address values found at four corners of a predefined span or grid of pixels. Then, a linear interpolation technique is implemented to calculate a rate of change of texture addresses for pixels between the perspectively bound span corners. This linear interpolation technique is performed in both screen directions to thereby create a potentially unique level of detail value for each pixel. When mapping an individually determined LOD value per pixel, the effect of producing undesirable artifacts, such as “Shark teeth”, that may appear if a single LOD for an entire span is used, is virtually obviated.
Each pixel of a span is assigned an independently interpolated value from the horizontal and vertical direction of the screen. Since the u and v gradients are monotonic, linear interpolation of the rate of change of each gradient will allow a LOD change in the u or v gradient direction at any pixel, and once the gradient has moved on to a new LOD, it will continue on in that LOD until it gets to the next LOD. Although the LOD assignments to pixels other than those at the corners of the span may represent a non-perspective correct interpolation within a span due to linear interpolation of a non-linear function, the resulting image to be displayed is acceptable generally to the human eye for most practical applications.
The rate of change of a coordinate from a two dimensional texture map when applied to a rendered polygon (i.e. a polygon to be displayed) is approximated between regularly spaced perspectively correct address values (i.e. those obtained from pixels situated at the corners of a span) in order to determine the appropriate Level of Detail (LOD) for proper texture mapping. This allows a form of linear interpolation between small areas in screen space to be used without obtaining artifacts from linear interpolation and prevents the need of subdividing polygons to very small polygons, as an alternative, to avoid distortions to non-perspective correct mapping of textures and corresponding increased demand for computing resources. This method of the present invention reduces the hardware necessary to obtain an image that appears perspectively cor
Cook Val Gene
Mantor Michael
Piazza Thomas A.
Taylor Ralph Clayton
Nguyen Kimbinh T.
Real 3-D
Scully Scott Murphy & Presser
Zimmerman Mark
LandOfFree
Method and apparatus for effective level of detail selection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for effective level of detail selection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for effective level of detail selection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2507253