Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-10-31
2001-01-16
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06175369
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer graphics and to the rendering of three dimensional images. More particularly, it relates to compression and decompression 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. Surface normals are vectors and as such are defined by a length and a direction. They can be represented in Cartesian coordinates by the coordinates {x,y,z} of a parallel vector of the same length whose starting point is the coordinate system origin.
This procedure for storing surface normals as a set of three floating point numbers introduces several problems. First, floating-point number representations of Cartesian coordinates often provide more precision than needed for realistic visual representation resulting in inefficient use of the resources of memory and computation time. Second, storing a surface normal as an {x,y,z} Cartesian vector 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 scale the length of the surface normals to one, if they are not received as such. And third, 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 inefficient use of memory limits the maximum size and resolution of the image that can be rendered at any given time.
A common technique used to address the above problems is to represent and store surface normals as spherical 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, which results in a 3:2 data compression ratio for the unit length surface normal. Required memory could be reduced further, with reduced precision, by storing the latitude and longitude as two short integers, each of which requires 2 bytes of memory in common systems, for a total of 4 bytes, resulting in a 3:1 data compression ratio. However, the numeric precision is not uniform 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). Also, conversion from spherical coordinates to Cartesian coordinates for graphics processing is computationally expensive.
Another technique for storing the unit length surface 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 surface 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 decompress, 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 precision. 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 scaling the original surface normal coordinates for unit length, and thus is not a data compression technique in the purest sense.
Still another method uses an abstract single number as an index into a table of surface normals based on the tessellation of a unit sphere. Because of the symmetry of the unit sphere, the table size can be reduced by dividing the unit sphere into identical octants bounded by the x=0, y=0, and z=0 planes. This division results in a triangular shaped area which is further folded into identical sextants bounded by the x=y, y=z, and x=z planes. The resulting table size is reduced by a factor of 48.
In a further refinement of the previous method, the normal is encoded as two orthogonal angular addresses. This coding technique allows selection of the resolution of the surface normal by increasing or reducing the number of bits in each angular address. Further reduction of normal size is possible by encoding the normal index using a variable length delta-encoding where only the difference between adjacent normals is encoded. This technique can reduce the size of an encoded normal by half.
Such methods result in high compression, but are computationally expensive to compress and decompress. In addition, employing an index into a table consumes a large amount of memory in storing the table and incurs a performance penalty in accessing values from the table. Also, encoding the surface normal as two orthogonal angular addresses introduces data alignment issues which slow memory access and require special code to access and align the data for processing. And, using delta encoding makes rendering an arbitrary geometry from compressed data and error recovery very difficult.
Therefore, in order to better meet the dual requirements of reduced memory utilization which permits more geometry to be loaded into memory and of higher speed which increases rendering performance, a need exists for further improvements in compression methods used in storing surface normal data for use in rendering three dimensional images.
SUMMARY OF THE INVENTION
Representative embodiments of the present invention relate to methods for the high performance decompression of compressed representations of surface normals. In a representative embodiment of the methods for compression of a surface normal, if not already of unit length, the surface normal is first scaled to unit length in Cartesian coordinates. Scaling the surface normal to unit length is not required, however surface normal component values must be in the specified range of floating point values. Expressed in floating point number format, each of the three Cartesian vector components of the surface normal are biased by the subtraction of a constant. The subtractions are performed as if all values are binary numbers, referred to herein as fixed-point-format binary numbers. A specified number of bits is extracted from each result and stored as the compressed representation of that vector component. Decompression occurs in a similar, but reverse process.
The present patent document discloses methods for the high speed compression and decompression of limited range floating point numbers which are used to compress and decompress the vector components of surface normals. Compression of a floating point number con
Dyer Don W.
Sands Samuel C.
Hewlett--Packard Company
Nguyen Phu K.
Tobey Morley C.
LandOfFree
High performance surface normal decompression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High performance surface normal decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High performance surface normal decompression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2516585