Compression of three-dimensional graphics data including quantization, delta-encoding, and variable-length encoding
First Claim
1. A method for representing 3-D geometry data, wherein said 3-D geometry data includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex, said method comprising:
- determining a level of resolution for said first value, wherein said level of resolution specifies a number of bits to use in representing said first value;
encoding said level of resolution for said first value in a data stream;
quantizing said first value according to said number of bits specified by said level of resolution, thereby generating a quantized first value; and
encoding said quantized first value in said data stream.
0 Assignments
0 Petitions
Accused Products
Abstract
In a compression system, three-dimensional geometry is first represented as a generalized triangle mesh, a data structure that allows each instance of a vertex in a linear stream to specify an average of two triangles. Individual positions, colors, and normals are quantized, preferably quantizing normals using a novel translation to non-rectilinear representation. A variable length compression is applied to individual positions, colors, and normals. The quantized values are then delta-compression encoded between neighbors, followed by a modified Huffman compression for positions and colors. A table-based approach is used for normals. Decompression reverses this process. The decompressed stream of triangle data may then be passed to a traditional rendering pipeline, where it is processed in full floating point accuracy.
-
Citations
128 Claims
-
1. A method for representing 3-D geometry data, wherein said 3-D geometry data includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex, said method comprising:
-
determining a level of resolution for said first value, wherein said level of resolution specifies a number of bits to use in representing said first value; encoding said level of resolution for said first value in a data stream; quantizing said first value according to said number of bits specified by said level of resolution, thereby generating a quantized first value; and encoding said quantized first value in said data stream. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A method for representing 3-D geometry data, wherein said 3-D geometry data includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex, said method comprising:
-
encoding an initial value of said first parameter, wherein said initial value corresponds to a initial vertex; delta-encoding said first value of said first parameter with respect to said initial value. - View Dependent Claims (22, 23, 24, 25, 26, 27)
-
-
28. A method for representing 3-D geometry data, comprising:
-
receiving said 3-D geometry data, wherein said 3-D geometry data includes a plurality of vertex parameter values of varying lengths, wherein said plurality of vertex parameter values includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex; generating a variable-length encoding of said first value, wherein said variable-length encoding is usable to determine a length of said first value. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
-
-
46. A method for compressing 3-D geometry data, wherein said 3-D geometry data includes information which describes a plurality of vertices usable to form a plurality of triangle primitives, wherein said plurality of triangle primitives are usable to represent a three-dimensional graphical object, said method comprising:
-
converting said 3-D geometry data into a generalized triangle mesh format, wherein said generalized triangle mesh format includes commands which describe said plurality of vertices, wherein selected ones of said commands reference storage locations in a mesh buffer in order to form selected ones of said plurality of triangle primitives, and wherein said mesh buffer stores vertex parameters in a fixed maximum number of said storage locations, and wherein said fixed maximum number is substantially less than the number of said plurality of vertices; determining a first quantization threshold for a first value represented within said generalized triangle mesh format, wherein said first value corresponds to a first vertex parameter of a first vertex; quantizing said first value to a first number of bits specified by said first quantization threshold, wherein said quantizing produces a quantized first value; delta-encoding said quantized first value, thereby producing a delta-encoded first value; and performing a first variable-length encoding of a length of said delta-encoded first value, wherein said first variable-length encoding is usable to determine said length of said delta-encoded first value. - View Dependent Claims (47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76)
-
-
77. A method for compressing 3-D geometry data, wherein said 3-D geometry data includes information describing a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of triangle primitives in order to represent a three-dimensional graphical object, said method comprising:
-
receiving said 3-D geometry data; determining connectivity information for said plurality of triangle primitives formed from said 3-D geometry data; specifying a vertex traversal order of said plurality of triangle primitives based on said connectivity information, wherein said specifying includes identifying selected ones of said plurality of vertices to be pushed into a mesh buffer, and wherein said specifying further includes referencing said selected ones of said plurality of vertices from said mesh buffer in order to form selected ones of said plurality of triangle primitives; quantizing vertex parameter values included in said 3-D geometry data according to quantization thresholds specified for said vertex parameter values, thereby producing quantized vertex parameter values; delta-encoding selected ones of said quantized vertex parameter values, thereby producing delta-encoded vertex parameter values; generating a plurality of variable-length encodings for compressed data which includes said delta-encoded vertex parameter values and quantized vertex parameter values which are absolutely specified; outputting decompression table entries usable to decompress said compressed data; and traversing said plurality of vertices using said vertex traversal order, wherein said traversing includes outputting a data stream which includes said plurality of variable-length encodings and a plurality of data fields representing packets of said compressed data, wherein each of said plurality of variable-length encodings describes a length of a corresponding one of said packets of said compressed data. - View Dependent Claims (78, 79)
-
-
80. A method for compressing 3-D geometry data, wherein said compressed 3-D geometry data includes information describing a plurality of vertices, and wherein said plurality of vertices are usable to form a plurality of triangle primitives which represent a three-dimensional graphical object, said method comprising:
-
encoding a first vertex parameter value which corresponds to a first vertex of said plurality of vertices, wherein said first vertex parameter value includes a first plurality of components; delta-encoding a second vertex parameter value in relation to said first vertex parameter value, wherein said second vertex parameter value corresponds to a second vertex of said plurality of vertices, and wherein said second vertex parameter value includes a second plurality of components, and wherein said delta-encoding includes representing said second plurality of components in relation to said first plurality of components; generating a single variable-length encoding for said second vertex parameter value, wherein said single variable-length encoding is usable to represent lengths corresponding to each of said second plurality of components. - View Dependent Claims (81, 82, 83, 84, 85, 86, 87, 88, 89)
-
-
90. A method for compressing 3-D geometry data, wherein said 3-D geometry data includes a plurality of vertex parameter values corresponding to a plurality of vertices, comprising:
-
quantizing selected ones of said plurality of vertex parameter values to various levels of resolution, thereby producing quantized vertex parameter values; delta-encoding selected ones of said quantized vertex parameter values, thereby producing delta-encoded vertex parameter values. - View Dependent Claims (91, 92)
-
-
93. A method for compressing 3-D geometry data, wherein said 3-D geometry data includes a plurality of vertex parameter values corresponding to a plurality of vertices, comprising:
-
quantizing selected ones of said plurality of vertex parameter values to various levels of resolution, thereby producing quantized vertex parameter values; delta-encoding selected ones of said quantized vertex parameter values, thereby producing delta-encoded vertex parameter values; and performing a variable-length encoding of length values of said delta-encoded vertex parameter values. - View Dependent Claims (94)
-
-
95. A computer system for compressing 3-D geometry data, wherein said 3-D geometry data includes information which describes a plurality of vertices usable to form a plurality of triangle primitives, wherein said plurality of triangle primitives are usable to represent a three-dimensional graphical object, said computer system comprising:
-
a central processing unit (CPU); a memory coupled to said CPU; wherein said CPU is configured to execute a program stored in said memory which is operable to implement the steps of; converting said 3-D geometry data into a generalized triangle mesh format, wherein said generalized triangle mesh format includes commands which describe said plurality of vertices, wherein selected ones of said commands reference storage locations in a mesh buffer in order to form selected ones of said plurality of triangle primitives, and wherein said mesh buffer stores vertex parameter values in a fixed maximum number of said storage locations, and wherein said fixed maximum number is substantially less than the number of said plurality of vertices; determining a first quantization threshold for a first value represented within said generalized triangle mesh format, wherein said first value corresponds to a first vertex parameter of a first vertex; quantizing said first value to a first number of bits specified by said first quantization threshold, wherein said quantizing produces a quantized first value; delta-encoding said quantized first value, thereby producing a delta-encoded first value; and performing a first variable-length encoding of a length of said delta-encoded first value, wherein said first variable-length encoding is usable to determine said length of said delta-encoded first value. - View Dependent Claims (96, 97)
-
-
98. A computer system for compressing 3-D geometry data, wherein said compressed 3-D geometry data includes information which describes a plurality of vertices, said computer system comprising:
-
a central processing unit (CPU); a memory coupled to said CPU; wherein said CPU is configured to execute a program stored in said memory which is operable to implement the steps of; encoding a first vertex parameter value which corresponds to a first vertex of said plurality of vertices, wherein said first vertex parameter value includes a first plurality of components, delta-encoding a second vertex parameter value in relation to said first vertex parameter value, wherein said second vertex parameter value corresponds to a second vertex of said plurality of vertices, and wherein said second vertex parameter value includes a second plurality of components, and wherein said delta-encoding includes representing said second plurality of components in relation to said first plurality of components; generating a single variable-length encoding for said second vertex parameter value, wherein said single variable-length encoding is usable to represent lengths corresponding to each of said second plurality of components. - View Dependent Claims (99, 100)
-
-
101. A memory media which stores program instructions for compressing 3-D geometry data, wherein said 3-D geometry data includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex, wherein said program instructions are executable to implement the steps of:
-
determining a level of resolution for said first value, wherein said level of resolution specifies a number of bits to use in representing said first value; encoding said level of resolution for said first value in a data stream; quantizing said first value according to said number of bits specified by said level of resolution, thereby generating a quantized first value; and encoding said quantized first value in said data stream.
-
-
102. A memory media which stores program instructions for compressing 3-D geometry data, wherein said 3-D geometry data includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex, wherein said program instructions are executable to implement the steps of:
-
encoding an initial value of said first parameter, wherein said initial value corresponds to a initial vertex; delta-encoding a first value of said first parameter, wherein said first value corresponds to said first vertex, wherein said first value represents a delta between said first value and said initial value.
-
-
103. A memory media which stores program instructions for compressing 3-D geometry data, wherein said program instructions are executable to implement the steps of:
-
receiving said 3-D geometry data, wherein said 3-D geometry data includes a plurality of vertex parameter values of varying lengths, wherein said plurality of vertex parameter values includes a first value of a first parameter which corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex; generating a variable-length encoding of said first value, wherein said variable-length encoding is usable to determine a length of said first value. - View Dependent Claims (104)
-
- 105. A memory media for storing compressed 3-D geometry data, wherein said compressed 3-D geometry data includes a plurality of values corresponding to a plurality of vertices, wherein said plurality of values includes a first value of a first parameter, wherein said first value corresponds to a first vertex, wherein said first parameter is a surface characteristic of a three-dimensional graphical object which includes said first vertex, wherein said compressed 3-D geometry is represented in a generalized triangle mesh format, and wherein said generalized triangle mesh format includes references to a mesh buffer, wherein said mesh buffer stores vertex parameters in a fixed number of locations, and wherein said fixed number is substantially less than the number of said plurality of vertices.
-
111. A method for compressing 3-D geometry data which includes information describing vertices of a plurality of geometric primitives representing a surface of a three-dimensional graphical object, said method comprising:
-
determining a first quantization threshold for a first vertex parameter value, wherein said first vertex parameter value corresponds to a first vertex of said vertices of said plurality of geometric primitives; compressing said first vertex parameter value to a number of bits specified by said first quantization threshold, thereby producing a quantized first parameter value; associating a first tag value with said quantized first parameter value, wherein said first tag value is usable to determine a length of said quantized first parameter value during decompression; and encoding said first tag value and said quantized first parameter value in a compressed data stream. - View Dependent Claims (112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125)
-
-
126. A method for compressing 3-D geometry data which includes information describing vertices of a plurality of geometric primitives representing a surface of a three-dimensional graphical object, said method comprising:
-
delta-encoding a first vertex parameter value relative to a previously specified vertex parameter value, thereby producing a delta-encoded first parameter value, wherein said delta-encoded first vertex parameter value corresponds to a first vertex of said vertices of said plurality of geometric primitives; determining a first quantization threshold for said delta-encoded first vertex parameter value; compressing said delta-encoded first vertex parameter value to a number of bits specified by said first quantization threshold, thereby producing a quantized first parameter value; associating a first tag value with said quantized first parameter value, wherein said first tag value is usable to determine a length of said quantized first parameter value during decompression; and encoding said first tag value and said quantized first parameter value in a compressed data stream.
-
-
127. A system for compressing 3-D geometry data which includes information describing vertices of a plurality of geometric primitives representing a surface of a three-dimensional graphical object, said system comprising:
-
a central processing unit (CPU); a memory coupled to said CPU, wherein said memory includes said 3-D geometry data and a compression program executable for representing said 3-D geometry data in a compressed format; wherein said CPU is configured to execute said compression program in order to represent said 3-D geometry in said compressed format, wherein said compression program is executable to determine a first quantization threshold for a first vertex parameter value, wherein said first vertex parameter value corresponds to a first vertex of said vertices of said plurality of geometric primitives, and wherein said compression program is further executable to compress said first vertex parameter value to a number of bits specified by said first quantization threshold, thereby producing a quantized first parameter value, and wherein said compression is still further executable to associate a first tag value with said quantized first parameter value, wherein said first tag value is usable to determine a length of said quantized first parameter value during decompression, and wherein said compression program is additionally executable to encode said first tag value and said quantized first parameter value in a compressed data stream. - View Dependent Claims (128)
-
Specification