US5793371A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for geometric compression of three-dimensional graphics data
Assignee: Oracle America Inc
•
Filing: 1995-08-04
•
Granted: 1998-08-11
•
Expires: 2015-08-04
Abstract
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.
Inventors
- 👤 Michael F. Deering
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:14
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/001
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
113 words
A method for compression in which a three-dimensional object whose surface defines surface characteristics including at least one characteristic selected from the group consisting of (i) position, (ii) normals, (iii) colors, (iv) texture map coordinates, (v) material surface properties of said object, said object being representable as three-dimensional triangular data defining a plurality of triangles having vertices, the method comprising: (a) converting said triangular data into linear strip format; (b) quantizing individual ones of said surface characteristics; (c) applying variable length compression to a difference between sequential ones said surface characteristics; and (d) providing a data stream representing said three-dimensional object as a collection of data generated in step (b) and step (c).
Claim 2
Independent Claim
113 words
A method for compression in which a three-dimensional object whose surface defines surface characteristics including at least one characteristic selected from the group consisting of (i) position, (ii) normals, (iii) colors, (iv) texture map coordinates, (v) material surface properties of said object, said object being representable as three-dimensional triangular data defining a plurality of triangles having vertices, the method comprising: (a) converting said triangular data into linear strip format; (b) quantizing individual ones of said surface characteristics; (c) applying variable length compression to a difference between sequential ones said surface characteristics; and (d) providing a data stream representing said three-dimensional object as a collection of data generated in step (b) and step (c).
Claim 3
Dependent Claim
54 words
The method of claim 1, wherein at step (a), said format has at least one format characteristic selected from the group consisting of (i) said format defines a generalized triangular data mesh, and (ii) said format causes each linear strip vertex on average to specify a number of triangles ranging from 1/3 to 2.
Claim 4
Dependent Claim
96 words
The method of claim 1, wherein said object has at least one characteristic selected from the group consisting of (i) characteristics of position of said object are represented as rectilinear x, y, z coordinate, (ii) characteristics of color of said object are represented as consisting of at least red, green, blue, and alpha components, said color being selected from the group consisting of at least (a) emissive color, (b) ambient color, (c) diffuse color, and (d) specular color, and (iii) characteristics of normals of said object are represented by rectilinear Nx, Ny, and Nz vector coefficients.
Claim 5
Dependent Claim
23 words
The method of claim 1, wherein each of said normals is represented by a single index into a table of predefined normalized normals.
Claim 6
Dependent Claim
27 words
The method of claim 4, wherein a chosen one, two or three bits of index representation comprise rectilinear representation sign bits of a normal to be represented.
Claim 7
Dependent Claim
56 words
The method of claim 4, wherein said index includes at least one bit specifying possible foldings of an absolute magnitude of a rectilinear representation of the normal to be represented by at least one folding plane x=y, x=z, y=z such that a folded normal is ensured to be on a known side of said folding plane.
Claim 8
Dependent Claim
19 words
The method of claim 4, wherein said index includes bits representing longitude information and latitude information of said normal.
Claim 9
Dependent Claim
34 words
The method of claim 4, wherein said index is defined to include three-bits of octant information, three-bits of sextant information, and two additional fields of information about longitude and latitude of the folded normal.
Claim 10
Dependent Claim
46 words
The method of claim 1, wherein step (c) is carried out at least in part using a procedure selected from the group consisting of (i) Huffman compression procedure, (ii) a variant of a Huffman compression procedure, (iii) arithmetic coding, and (iv) a variant of arithmetic coding.
Claim 11
Dependent Claim
76 words
The method of claim 4, wherein said index includes bits representing longitude information and latitude information of said normal, and further includes three-bits of octant information, three-bits of sextant information, and two additional fields of information about longitude and latitude of the folded normal, wherein at step (c), said difference between normals may be represented solely by differences between their longitude and latitude information of said normals if other components of said representation are otherwise identical.
Claim 12
Independent Claim
145 words
A system for compressing data representing a three-dimensional object whose surface defines surface characteristics including at least one characteristic selected from the group consisting of (i) position, (ii) normals, (iii) colors, (iv) texture map coordinates, (v) material surface properties of said object, said object being representable as three-dimensional triangular data defining a plurality of triangles having vertices, the system comprising: a computer system including a central processing unit (CPU) and memory coupled to said CPU; a first unit programmed to convert said triangular data into linear strip format; a quantizing unit that quantizes individual ones of said surface characteristics; a compression unit that applies variable length compression to a difference between sequential ones said surface characteristics; and a data stream generator that provides a data stream representing said three-dimensional object as a collection of data generated by said quantizing unit and by said compression unit.
Claim 13
Independent Claim
145 words
A system for compressing data representing a three-dimensional object whose surface defines surface characteristics including at least one characteristic selected from the group consisting of (i) position, (ii) normals, (iii) colors, (iv) texture map coordinates, (v) material surface properties of said object, said object being representable as three-dimensional triangular data defining a plurality of triangles having vertices, the system comprising: a computer system including a central processing unit (CPU) and memory coupled to said CPU; a first unit programmed to convert said triangular data into linear strip format; a quantizing unit that quantizes individual ones of said surface characteristics; a compression unit that applies variable length compression to a difference between sequential ones said surface characteristics; and a data stream generator that provides a data stream representing said three-dimensional object as a collection of data generated by said quantizing unit and by said compression unit.
Claim 14
Dependent Claim
51 words
The system of claim 11, wherein said format has at least one format characteristic selected from the group consisting of (i) said format defines a generalized triangular data mesh, and (ii) said format causes each linear strip vertex on average to specify a number of triangles ranging from 1/3 to 2.
Claim 15
Dependent Claim
98 words
The system of claim 11, wherein characteristics of said object have at least one characteristic selected from the group consisting of (i) characteristics of position of said object are represented as rectilinear x, y, z coordinates, (ii) characteristics of color of said object are represented as consisting of at least red, green, blue, and alpha components, said color being selected from the group consisting of at least (i) emissive color, (ii) ambient color, (iii) diffuse color, and (iv) specular color, and (iii) characteristics of normals of said object are represented by rectilinear Nx, Ny, and Nz vector coefficients.
Claim 16
Dependent Claim
23 words
The system of claim 11, wherein each of said normals is represented by a single index into a table of predefined normalized normals.
Claim 17
Dependent Claim
27 words
The system of claim 14, wherein a chosen one, two or three bits of index representation comprise rectilinear representation sign bits of a normal to be represented.
Claim 18
Dependent Claim
56 words
The system of claim 14, wherein said index includes at least one bit specifying possible foldings of an absolute magnitude of a rectilinear representation of the normal to be represented by at least one folding plane x=y, x=z, y=z such that a folded normal is ensured to be on a known side of said folding plane.
Claim 19
Dependent Claim
19 words
The system of claim 14, wherein said index includes bits representing longitude information and latitude information of said normal.
Claim 20
Dependent Claim
34 words
The system of claim 14, wherein said index is defined to include three-bits of octant information, three-bits of sextant information, and two additional fields of information about longitude and latitude of the folded normal.
Claim 21
Dependent Claim
44 words
The system of claim 14, wherein said compression unit uses, at least in part, a procedure selected from the group consisting of (i) Huffman compression procedure, (ii) a variant of a Huffman compression procedure, (iii) arithmetic coding, and (iv) a variant of arithmetic coding.
Claim 22
Dependent Claim
76 words
The system of claim 14, wherein said index includes bits representing longitude information and latitude information of said normal, and further includes three-bits of octant information, three-bits of sextant information, and two additional fields of information about longitude and latitude of the folded normal, wherein at step (c), said difference between normals may be represented solely by differences between their longitude and latitude information of said normals if other components of said representation are otherwise identical.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-10 | 2002-02-09 | 2002-08-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-10 | 2006-02-09 | 2006-08-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-10 | 2010-02-09 | 2010-08-11 | $7700.00 | Window Closed / Lapsed |