Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-04-02
2001-05-01
Powell, Mark R. (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S440000, C345S419000
Reexamination Certificate
active
06226012
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field Of The Invention
This invention relates to computer systems, and more particularly, to methods and apparatus for accelerating the rendering of images to be reproduced on a computer output display.
2. History Of The Prior Art
In three dimensional graphics, surfaces are typically rendered by assembling a plurality of polygons into a desired shape. The polygons are conventionally triangles having vertices which are defined by three dimensional coordinates in world space, by color values, and by texture coordinates. The color values define the brightness of each of red/green/blue (r, g, b) colors at each vertex and thus the color at each vertex. The texture coordinates (u, v) define the positions of each vertex on a texture map stored in memory. The texture map is a matrix of values which describe colors at intersections of the texture coordinates. The placement of the color values in the matrix describes a pattern which when applied to the surface of the triangle varies the colors in accordance with the pattern. Other characteristics such as fog, transparency, spectral colors, and additional textures may also define each vertex in a particular system to provide more sophisticated rendering.
The surfaces represented by an assembly of polygons are, as a generality, being viewed in perspective. In order to display a surface, the vertices of each triangle must be positioned in two dimensional screen space and the pixels which describe the entire triangle determined. Then the characteristics (attributes) for each of the pixels may be determined for each pixel.
The positions of the vertices of each triangle may be furnished in screen space or world space. If furnished in world space, the three dimensional world space coordinates are transformed into screen coordinates in which horizontal and vertical values (x, y) define screen position and a depth value z determines how near a particular vertex is to the screen and thus how and whether that vertex is viewed with respect to other points at the same screen coordinates. This may be accomplished by a perspective transformation algorithm well known to those skilled in the art. The other attributes are almost always furnished by an application program in world space.
It is a simple matter to determine the x and y coordinates of each pixel defining a triangle if the screen space coordinates of the vertices are known because the pixel positions are distributed linearly from vertex to vertex in screen space. However, all of the other attributes are distributed linearly across the triangle in world rather than screen space. Consequently, attributes accurately defining each pixel in two dimensional screen space may be determined from the linear distribution of those attributes at positions across the surface of the triangle in world space and the perspective transformation of values at those positions to the pixel positions in screen space.
Thus, the depth of the vertices of a triangle vary linearly in world space from one to the other vertex within the triangle. This allows the depth value for any position in the triangle to be determined in world space. The depth of each pixel which defines the triangle projected onto the screen may then be determined by perspective transformation of the world depth values using algorithms well known to those skilled in the art. Similarly, the color values and the texture coordinates for each pixel defining the triangle vary linearly from vertex to vertex in world space and so may be used to find the color values and texture coordinates for each pixel.
Once the values of all of the attributes for each pixel have been determined in screen space, the texture coordinates are utilized to determine texture values from the texture map for each pixel. Determining the texture values of each pixel in a triangle accurately is a lengthy process. The texture coordinates u and v of each pixel provide an index into a map of texture values typically stored in memory which describe colors at the individual coordinates and thereby define a particular texture pattern that is to be applied in world space to the surface of the triangle. The texture value is then used with the other attribute values to generate a color value for that pixel of the triangle.
Since each individual screen pixel describing the triangle covers some portion of the texture map as it is projected onto the screen, each screen pixel will cover some one or more texture values (texels) on the projected triangle. Texture coordinates obtained by processes combining linear interpolation and perspective transformation are not typically integer values. On the other hand, indexing into a texture map is accomplished using integral coordinates. There are a number of methods used in the prior art to derive texture values from the u and v values. A simple method of obtaining texture values uses the closest integral u and v values for each pixel obtained by either rounding or truncating to select the texture value at that intersection. A more accurate method of representing the texture pattern called bilinear interpolation utilizes the integer portion of the u and v coordinates for each pixel to determine four additional sets of integral texture coordinates surrounding the position of the original set of coordinates, uses those four sets to index into the texture map to obtain four texture values, and then utilizes the fractional portion of the original texture coordinates to weight the four texture values derived. These weighted values are combined and blended into a more accurate representation for modifying each pixel color value to reproduce the texture pattern.
However, those skilled in the art have recognized that where a pixel covers a very large number of texels on a texture map, only a small portion of those values will be represented in the final texture value selected to modify the color of that pixel using the bilinear interpolation method. Consequently, a more accurate method of texture mapping has been devised. The method provides a plurality of texture maps for each texture at different scales so that by selecting a map of the correct scale the pixels defining the individual triangles may be made to cover relatively constant numbers of texels. This allows most of the texels to used in reaching a final texture value for any pixel and provides a more accurate color representation. The process of selecting a texture value for a pixel then includes an initial step for each particular triangle being rendered in which a texture map is selected having a scale adapted to accurately represent texture values for the pixels of that triangle. One process for choosing a texture map of a correct scale is described in a paper entitled “Pyramidal Parametrics,” presented at Siggraph Proceedings, 1984.
In order to make the scale selection process even more accurate, an additional process by which texture maps of the two scales closest to a desired size are selected and the texture values provided by those two different texture maps are interpolated to provide values closer to the desired scale.
Although these methods render pixels progressively more accurately on the screen if the triangle lies in a plane parallel to the screen surface, each of these methods is based on the assumption that the projection of a pixel onto the texture map is square or rectangular in shape. This assumption is incorrect in the greater number of cases when three dimensional shapes are being rendered. If the vertices of the triangle being mapped are at significantly different depths, the pixels describing a scan line are warped and of different sizes when projected onto the triangle. None of these methods is capable of describing with sufficient accuracy the texture values which should be attributed to the pixels when three dimensional shapes are rendered in any significant perspective on a flat screen surface.
Consequently, a new process has been developed which evaluates and combines texture values at a plurality of positions within each pixel. The positions
Kirk David
Priem Curtis
Boyce Justin F.
Hamrick Claude A. S.
Harrison Chante
Nvidia Corporation
Oppenheimer Wolff & Donnelly LLP
LandOfFree
Method and apparatus for accelerating the rendering of... 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 accelerating the rendering of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for accelerating the rendering of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549635