3D mesh compression and coding

• US 6,262,737 B1
• Filed: 07/31/1998
• Issued: 07/17/2001
• Est. Priority Date: 01/30/1998
• Status: Expired due to Fees

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Li, Jienkun, Kuo, Chung-Chieh Jay
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US09/127,053
• Time in Patent Office: 1,082 Days
• Field of Search: 345/419, 345/429, 345/420, 345/423, 345/427, 345/428
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/39 involving multiple description coding [MDC], i.e. with separate layers being structured as independently decodable descriptions of input picture data
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Single and progressive-resolution coding algorithms for the compression of 3-D polyhedral meshes are disclosed. In the single-resolution mode, the mesh topology (or connectivity) is encoded by a constructive traversing approach applied to the dual graph of the original mesh while the mesh geometry is encoded by successive quantization and the bit-plane coding (achieved by context arithmetic coding). In the progressive-resolution mode, the mesh is represented by a coarse approximation (i.e., the base mesh) and a sequence of refinements. Both the base mesh and the refinement operations are entropy coded so that a series of mesh models of continuously varying resolutions can be constructed from the coded bit stream. Topological and geometrical data of a 3-D mesh are encoded separately according to their importance and then integrated into a single bit stream. In decoding, the decoder finds from the bit stream the most important information and gradually adds finer detailed information to provide a more complete 3-D graphic model. The decoder can stop at any point while giving a reasonable reconstruction of the original model. The disclosed algorithm was applied to complicated 3-D meshes and achieved a compression ratio of 20:1 while maintaining a good graphic quality.

Claims

1. A method of encoding a three dimensional model represented by polyhedral meshes to provide a compressed data representation of the three dimensional model, said method comprising the steps of:

A. treating the mesh structure according to the following sequence;

1. select a starting node n_s and a principle link I associated with the starting node n_s;

2. traverse each link associated with the starting node in a counter clockwise direction starting with the principle link;

3. for each link traversed in Step 2, add the traversed link ending node n_ε

to a queue and set the link as the principle link, if the ending node is not already in the queue;

4. after each link associated with the starting node n_s has been traversed go to the next node in the queue and repeat Steps 3 and 4 until all nodes in the queue have been traversed, and then terminate;

B. recording each link associated with each node of the mesh traversed.

2. The method of claim 1 further comprising the step of identifying the ending node n_ε

of Step A-3 as a branch node if not in the queue and a merger node if in the queue.

3. The method of claim 2 further comprising the step of identifying each merger node according to a global indexing scheme.

4. The method of claim 2 further comprising the step of identifying each merger node according to a local indexing scheme.

5. The method of claim 4 wherein the local indexing scheme comprises a clockwise tracing or a counter clockwise tracing to the merger node from the starting node n_s, whichever is shorter.

6. The method of claim 1 further comprising the step of specifying the attributes of the node for each node traversed in step A.

7. The method of claim 6 wherein each of the attributes of the node are selected from the group consisting of position, normal, color and texture.

8. The method of claim 6 further comprising the step of coding the attributes of the node, comprising the steps of:

1. ordering the attributes to be coded;

2. producing a sequence of prediction residues for each coded attribute; and

3. quantizing and coding the prediction residues.

9. A method of encoding a three dimensional model represented by polyhedral meshes to provide a compressed data representation of the three dimensional model, said method comprising the steps:

coding the structure data of the polyhedral meshes representing the three dimensional model, wherein the step of coding the structure data comprises the steps of selecting a starting node n_s and a principle link associated with the starting node n_s, and traversing a selected link associated with the starting node n_s in a counter clockwise direction starting with the principle link;

coding the attribute data of the polyhedral meshes representing the three dimensional model; and

multiplexing the encoded structure data and the encoded attribute data into a single data stream.

10. The method of claim 9 wherein the step of coding the structure data comprises the step of:

adding the selected link ending node n_ε

to a queue and setting the link as the principle link if the ending node n_ε

is not already in the queue.

11. The method of claim 10 further comprising the step of traversing all nodes in the queue by repeating said traversing step and said adding step.

12. The method of claim 10 further comprising the step of identifying the ending node n_ε

as a branch node if the ending node n_ε

is not in the queue and as a merger node if the identifying node n_ε

is in the queue.

13. The method of claim 12 further comprising the step of identifying each merger node according to a global indexing scheme.

14. The method of claim 12 further comprising the step of identifying each merger node according to a local indexing scheme.

15. The method of claim 14 wherein the local indexing scheme comprises a clockwise tracing to the merger node from the starting node n_s.

16. The method of claim 14 wherein the local indexing scheme comprises a counter clockwise tracing to the merger node from the starting node n_s.

17. The method of claim 9 wherein the step of coding the attribute data comprises the step of specifying the attributes of each node in the polyhedral meshes.

18. The method of claim 17 wherein each of the attributes of each node in the polyhedral meshes are selected from the group consisting of position, normal, color and texture.

19. The method of claim 17 further comprising the step of coding the attributes of each node, comprising the steps of:

ordering the attributes to be coded;

producing a sequence of prediction residues for each coded attribute; and

quantizing and coding the prediction residues.

20. A method of encoding a tree dimensional model represented by polyhedral meshes to provide a compressed data representation of the three dimensional model, said method comprising the steps of:

A. treating the mesh structure according to the following sequence;

1. select a starting node n_s and a principle link I associated with the starting node n_s;

2. traverse each link associated with the starting node in a clockwise direction starting with the principle link;

3. for each link traversed in Step 2, add the traversed link ending node n_s to a queue and set the link as the principle link, if the ending node is not already in the queue;

4. after each link associated with the starting node n_s has been traversed go to the next node in the queue and repeat Steps 3 and 4 until all nodes in the queue have been traversed, and then terminate;

B. recording each link associated with each node of the mesh traversed.

21. The method of claim 20 further comprising the step of identifying the ending node n_ε

of Step A-3 as a branch node if not in the queue and a merger node if in the queue.

22. The method of claim 21 further comprising the step of identifying each merger node according to a global indexing scheme.

23. The method of claim 21 further comprising the step of identifying each merger node according to a local indexing scheme.

24. The method of claim 23 wherein the local indexing scheme comprises a counter clockwise tracing or a clockwise tracing to the merger node from the starting node n_s, whichever is shorter.

25. The method of claim 20 further comprising the step of specifying the attributes of the node for each node traversed in step A.

26. The method of claim 25 wherein each of the attributes of the node are selected from the group consisting of position, normal, color and texture.

27. The method of claim 25 further comprising the step of coding the attributes of the node, comprising the steps of:

1. ordering the attributes to be coded;

2. producing a sequence of prediction residues for each coded attribute; and

3. quantizing and coding the prediction residues.

28. A method of encoding a three dimensional model represented by polyhedral meshes to provide a compressed data representation of the three dimensional model, said method comprising the steps:

coding the structure data of the polyhedral meshes representing the three dimensional model, wherein the step of coding the structure data comprises the steps of selecting a starting node n_s and a principle link associated with the starting node n_s, and traversing a selected link associated with the starting node n_s in a clockwise direction starting with the principle link;

coding the attribute data of the polyhedral meshes representing the three dimensional model; and

multiplexing the encoded structure data and the encoded attribute data into a single data stream.

29. The method of claim 28 wherein the step of coding the structure data comprises the step of:

adding the selected link ending node n_ε

to a queue and setting the link as the principle link if the ending node n_s is not already in the queue.

30. The method of claim 29 further comprising the step of traversing all nodes in the queue by repeating said traversing step and said adding step.

31. The method of claim 29 further comprising the step of identifying the ending node n_s as a branch node if the ending node n_s is not in the queue and as a merger node if the identifying node n_s is in the queue.

32. The method of claim 31 further comprising the step of identifying each merger node according to a global indexing scheme.

33. The method of claim 31 further comprising the step of identifying each merger node according to a local indexing scheme.

34. The method of claim 33 wherein the local indexing scheme comprises a counter clockwise tracing to the merger node from the starting node n_s.

35. The method of claim 33 wherein the local indexing scheme comprises a clockwise tracing to the merger node from the starting node n_s.

36. The method of claim 28 wherein the step of coding the attribute data comprises the step of specifying the attributes of each node in the polyhedral meshes.

37. The method of claim 36 wherein each of the attributes of each node in the polyhedral meshes are selected from the group consisting of position, normal, color and texture.

38. The method of claim 36 further comprising the step of coding the attributes of each node, comprising the steps of:

ordering the attributes to be coded;

producing a sequence of prediction residues for each coded attribute; and

quantizing and coding the prediction residues.