Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-09-30
2001-02-20
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06191791
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer graphics, and more particularly to the rendering of three dimensional images. More particularly still, the invention relates to a novel method of compression and expansion of surface normal data used in the rendering of three dimensional images.
BACKGROUND
For three dimensional images generated from abstract platonic primitives, such as lines and polygons, computer graphics applications and systems store primitive vertex information such as coordinates of surface points, associated surface normals, and other rendering information such as opacity, color, etc. The surface normals are usually specified as one coordinate point {X,Y,Z} for each vertex of the primitive. The starting point for each of these surface normal vectors is the coordinate system origin.
This procedure for storing surface normals as a set of three floating point numbers introduces several problems. First, in common use, {X,Y,Z} Cartesian coordinates often provide more accuracy than needed for realistic visual representation resulting in inefficient utilization of the resources of memory and computation time. Second, storing a surface normal as an {X,Y,Z} Cartesian coordinate does not guarantee that the surface normal is of unit length, i.e. the distance from the origin to the point {X,Y,Z} is one. Graphics libraries in common use expect to receive surface normal data in unit length and must unitize the surface normals if they are not received as such. Third, representing a surface normal as three floating point numbers, one for each axis, does not produce a uniform distribution of precision between the three values. This situation is especially noticeable when the normal is aligned or nearly aligned with one of the three major axes. And fourth, using common single precision floating point formats, the total space required to store a surface normal is three 32-bit full words, or 12 bytes. When several hundred-thousand surface normals need to be stored, along with other geometric and application data, upper bounds on system memory resources can be reached. This situation limits the maximum size of the image that can be rendered at any given time.
A technique used to address the above problems is to represent and store surface normals as spherical or polar coordinates instead of Cartesian coordinates. Using this technique two floating point values are specified, one for the longitude or polar angle and one for the latitude or azimuthal angle, and results in a 3:2 date compression ratio for the surface unit normal. Required memory could be reduced further, with reduced accuracy, by storing the latitude and longitude as two short integers, each of which requires 2 bytes of memory, for a total of 4 bytes, resulting in a 3:1 data compression ratio. However, the numeric precision is still unevenly distributed between the two coordinate values of longitude and latitude. If the normal position is near latitude &pgr;/2 or −&pgr;/2 (i.e., near the poles), the longitude value provides much greater precision than when the latitude is near 0 (i.e., near the equator).
Another technique for storing the surface unit normals is to use an abstract single number representation. This technique involves a tessellation of a sphere obtained by combining the vertices of two platonic solids, the icosahedron and the dodecahedron. Then, a 4-deep triangle subdivision of the resulting 60 equilateral triangles is performed giving a sphere covered with 7680 triangles. A normal is mapped into an abstract value by first determining which of the original 60 triangles contains the normal. Then 128 dot products with the normal to the 128 interior triangles are performed. The largest dot product indicates the best matching triangle for the incoming normal. The result of these computations is used as the compressed normal. To uncompress, the compressed normal is used to index a table of pre-computed values. Calculation of the numerous dot products required in this technique is computationally inefficient. Higher resolution, i.e., more and smaller triangles, results in even more involved computations. Much of the memory savings inherent in this technique is lost because of the size of the lookup table. Also, the range of compressed normals is limited by the size of the decompression table which puts an upper limit on their accuracy.
This technique is often used to map normals to pre-computed lighting values using a lookup table as above with the lighting values instead of normals. Used in this manner, when the lighting direction to the model is changed, the values in the look-up table must be recomputed, resulting in additional computation time. Because a lighting look-up table is used, this algorithm does not address the issue of converting back to the original surface normal coordinates, and thus is not a data compression technique in the purest sense.
A need, therefore, exists for further improvements in compression methods used for storing surface normal data to be used in rendering three dimensional images.
SUMMARY OF THE INVENTION
In a representative embodiment of the methods for compression of surface normals into quantized normals and the inverse expansion of quantized normals into surface unit normals, the surface of a unit sphere is divided into a large number of small, nearly-equal-sized areas or tiles. To generate these tiles, the surface of the unit sphere is divided into equal width latitudinal bands. Each band is then divided into equal length units which are approximately equal to the width of the latitude bands. The maximum number of tiles in a band occurs at the equator with the number of tiles in each band decreasing the closer the band is to one of the poles.
The tiles of the surface of the unit sphere are numbered from 0 to the total number of tiles minus one. The number of tiles may be, for example, the largest value that can be efficiently stored in a computing system, such as an unsigned integer. Depending upon the particular number space used an unsigned integer value may typically range from 0 up to 2 raised to the power of 16 minus 1 or 2 raised to the power of 32 minus 1. In general, the larger the number of tiles, the less the average error between the original surface normal and the resulting quantized normal. However, a larger number of tiles may result in a smaller compression ratio.
A quantized normal representation is the tile number on the surface of the unit sphere. The center of each numbered tile represents all normal vectors which pass through that tile. For a particular three dimensional abstract image, instead of storing surface unit normal values of {X,Y,Z} for each coordinate, the quantized surface normal value (i.e., the tile number) it stored.
Memory requirements for the storage of surface normals of three dimensional graphical images are substantially reduced in contrast to other techniques used in the art. A compression ration of 6:1 over that of using the surface normal Cartesian coordinates {X,Y,Z} is attained. A look-up table is not required in this technique. In addition, conversions from the surface normal coordinates of Cartesian, polar, spherical, or other coordinate systems to the quantized normal representation is computationally efficient.
Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. The details disclosed in the specification should not be read so as to limit the invention.
REFERENCES:
patent: 5440682 (1995-08-01), Deering
patent: 5736987 (1998-04-01), Drucker et al.
Excerpt from the World-Wide-Web Site: /home/martz
ormals/shpere.faq printed Apr. 7, 1997 and entitled: Topics On Sphere Distributions. Author Dave Rusin, 1995.
“Direct Volume Rendering With Shading Via Three-Dimensional Textures”, Allen Van Gelder and Kwansik Kim, 1996 IEEE Symposium On Volume Visualization.
Dyer Don W
Martz Paul E
Morrison Teresa M
Hewlett--Packard Company
Nguyen Phu K.
Tobey, Jr. Morely C.
LandOfFree
Methods for high precision, memory efficient surface normal... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for high precision, memory efficient surface normal..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for high precision, memory efficient surface normal... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2566157