Compression of polygonal models with low latency decompression

• US 6,445,389 B1
• Filed: 10/01/1999
• Issued: 09/03/2002
• Est. Priority Date: 10/06/1998
• Status: Expired due to Term

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Bossen, Frank J., Gueziec, Andre P., Silva, Claudio T., Taubin, Gabriel
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/411,448
• Time in Patent Office: 1,068 Days
• Field of Search: 345/418, 345/419, 345/420, 345/421, 345/422
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A data structure for representing a general n-dimensional polygonal mesh. The data structure includes a structure record and a data record for each three dimensional shape. The structural record contains polygonal model connectivity information and further includes a stitching record that defines corresponding polygonal (triangular) mesh edge pairs and a polygonal (triangular) tree record representing a polygon (triangle) tree. The stitching record includes a vertex tree and a set of jump edges. The data record includes at least three polygonal records, each corresponding to a polygon. Each polygonal record is associated with a face of said polygonal model and classifies its corresponding polygon as either a leaf polygon, a running polygon or a branching polygon. Polygonal shapes are encoded into the data structure by first building a spanning tree for the polygonal mesh. A set of cut edges are derived for the polygonal mesh. The stitching record is constructed for the set of cut edges. Then traversing the polygon tree, the data records are encoded. The encoded data is transmitted, the structure record being transmitted first, followed by the data record. The stitching tree and polygon tree are decoded as they are received and, after at least three polygons are received, received polygons may be displayed.

Claims

1. A data structure stored in a memory of a computer system for representing a general n-dimensional polygonal mesh, the data structure comprising:

a structure record containing polygonal model connectivity information, said structure record further including a stitching record defining corresponding polygonal mesh edge pairs and a polygonal tree record representing a polygon tree; and

a data record including three or more polygonal records, a corresponding polygon for each said polygonal record being associated with a face of said polygonal model, wherein each of said polygonal records classifies said corresponding polygon as either a leaf polygon, a running polygon or a branching polygon.

2. A data structure as in claim 1, wherein said stitching record includes a vertex tree and a set of jump edges.

3. A data structure as in claim 2, wherein each of said polygonal records are ordered according to traversal order of said polygon tree.

4. A data structure as in claim 3, wherein each of said polygonal records corresponding to a running polygon includes a marching field.

5. A data structure as in claim 3, wherein each of said polygonal records includes a properties field representing properties of said corresponding polygon.

6. A data structure as in claim 5, wherein each of said polygonal properties include color, normals and texture coordinates.

7. A data structure as in claim 3, wherein each of said polygonal records includes a geometry field.

8. A data structure as in claim 3, wherein one or more of said corresponding polygons are triangles.

9. A data structure as in claim 8, wherein each of said corresponding polygons is a triangle.

10. A data structure as in claim 8, each of said polygonal records includes a polygonal field indicating non-triangular polygons.

11. A data structure as in claim 3, wherein said polygonal tree is a rooted triangle tree defines a traversal order starting from a root triangle.

12. A data structure as in claim 3, wherein the structure record is compressed by any one of the following techniques:

run-length coding, Huffman coding, Arithmetic coding, Shannon-Fano-Elias coding, or Lempel-Ziv coding.

13. A data structure as in claim 3, wherein the data record are compressed by any one of the following techniques:

run-length coding, Huffman coding, Arithmetic coding, Shannon-Fano-Elias coding, or Lempel-Ziv coding.

14. A method of encoding three dimensional shapes comprising the steps of:

a) building a polygon spanning tree for a polygonal mesh representation of a three dimensional shape, said polygonal mesh being a plurality of connected polygons;

b) deriving a set of cut edges for edge of polygons of said polygon spanning tree;

c) constructing a stitching record for said set of cut edges; and

d) traversing said polygon spanning tree according to said stitching record and encoding a polygon record for each of said polygons.

15. A method of decoding shapes encoded as in claim 14, said method comprising the steps of:

e) decoding said stitching record and, responsive to said decoded stitching record, building a look-up table;

f) decoding said polygon spanning tree and, responsive to said decoded polygon spanning tree, computing subtree sizes; and

g) traversing said polygon spanning tree and decoding each encountered polygon record corresponding to a polygon in said polygon spanning tree.

16. A method of decoding shapes encoded as in claim 15 wherein for each decoded shape, polygons are displayed after decoding a third encountered polygon record.

17. A method of decoding shapes encoded as in claim 16, wherein a plurality of said connected polygons are triangles.

18. A method of decoding shapes encoded as in claim 15, further comprising compressing said polygon spanning tree, said set of cut etches and said stitching record by any one of the following techniques:

run-length coding, Huffman coding, Arithmetic coding, Shannon-Fano-Elias coding, or Lempel-Ziv coding.

19. A method of decoding shapes encoded as in claim 15, comprising compressing said encoded polygons by any one of the following techniques:

run-length coding, Huffman coding, Arithmetic coding, Shannon-Fano-Elias coding, or Lempel-Ziv coding.