Methods and apparatus for the efficient compression of non-manifold polygonal meshes

• US 6,452,596 B1
• Filed: 04/22/1999
• Issued: 09/17/2002
• Est. Priority Date: 10/06/1998
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Silva, Claudio, Gueziec, Andre P, Bossen, Frank J, Taubin, Gabriel
• Primary Examiner(s): Brier, Jeffery
• Assistant Examiner(s): YANG, RYAN R
• Application Number:
  US09/296,833
• Time in Patent Office: 1,244 Days
• Field of Search: 345/440, 345/441
• US Class Current: 345/440
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method for encoding a non-manifold polygonal mesh operates by converting an original (non-manifold) model to a manifold model, encoding the manifold model using a mesh compression technique, and clustering, or stitching together during a decompression process, vertices that were duplicated earlier to faithfully recover the original connectivity. By separating the connectivity from model geometry and properties, the method avoids encoding vertices (and properties bound to vertices) multiple times. This provides a reduction in the size of the bit-stream compared with encoding the model as a manifold.

Claims

1. A method for compressing a non-manifold mesh representing a geometric object, comprising the steps of:

converting the non-manifold mesh to at least one manifold mesh, the step of converting including a step of storing information on how to cluster vertices;

compressing the at least one manifold mesh; and

compressing the information on how to cluster vertices.

2. A method as in claim 1, and further comprising a step of storing the compressed at least one manifold mesh and the information on how to cluster the vertices.

3. A method as in claim 1, and further comprising a step of transmitting the compressed at least one manifold mesh and the information on how to cluster the vertices to a remote location.

4. A method as in claim 1, wherein the non-manifold mesh is represented in compressed form as a data structure comprised of a collection of data structures for a mesh connected component, each data structure for a mesh connected component comprising:

a data structure for representing mesh connectivity;

a data structure for representing stitches; and

a data structure for representing mesh geometry as vertex coordinates as well as mesh properties per vertex/face/corner.

5. A method as in claim 1, and further comprising a step of transmitting the compressed at least one manifold mesh and the compressed information on how to cluster the mesh vertices to a remote location using a bit-stream syntax comprised of, for each vertex of the manifold mesh, a stitching command having a type selected from a set consisting of NONE, PUSH, GET and POP.

6. A method as in claim 5, wherein the bit-stream syntax is further comprised of a stitch length;

a stack index;

a differential length;

a push bit; and

a reverse bit.

7. A method for encoding a non-manifold polygonal mesh representing a geometric object, comprising the steps of:

representing the non-manifold polygonal mesh as at least one manifold polygonal mesh and a vertex clustering array obtained by cutting through singular edges and vertices of the non-manifold polygonal mesh;

representing each connected component of the manifold polygonal mesh with a vertex graph, a triangle tree and a triangle data record;

representing the information contained in the vertex cluster array as stitching information comprised a set of stitching commands each of the type NONE, PUSH, GET or POP, each stitching command having associated data;

applying the stitching information to a vertex cluster look-up table that describes a relation between polygon boundary loop nodes and mesh vertices; and

encoding the stitching information in a bit-stream according to a predetermined bit-stream syntax.

8. A method as in claim 7, wherein the bit-stream syntax is comprised of, for each vertex of the manifold polygonal mesh, one of the stitching commands having the type NONE, PUSH, GET or POP;

a stitch length;

a stack index;

a differential length;

a push bit; and

a reverse bit.

9. A method as in claim 7, wherein in the step of representing the non-manifold polygonal mesh as a manifold polygonal mesh and a vertex clustering array has the faces of two polygonal meshes in one-to-one correspondence, and the vertex clustering array assigns each vertex of the manifold polygonal mesh to its corresponding vertex in the non-manifold polygonal mesh before the cutting process.

10. A method as in claim 9, wherein the vertex clustering array is represented as an array with as many elements as vertices in the manifold polygonal mesh.

11. A method as in claim 7, wherein in the step of representing each connected component of the manifold polygonal mesh with a vertex graph, a triangle tree, and a triangle data record, an order of connected components and an order of a traversal of vertex trees spanning vertex graphs determines a global order of traversal, represented as a vertex traversal array, and wherein parent-child relationships are represented as a vertex father array.

12. A method as in claim 11, wherein in the step of representing the information contained in the vertex cluster array as stitching information, the vertex traversal array represents a permutation of the vertices, which is used to convert encoder vertex indices to decoder vertex indices.

13. A method as in claim 7, wherein in the step of applying the stitching commands to a look-up table the obtained information is used later to keep track of visited vertices in the triangle data record.

14. A method as in claim 8, and further comprising a step of decoding the bit-stream syntax by the steps of:

decoding manifold connected components;

decoding the stitch information;

applying the decoded stitch information to the vertex cluster look-up table that describes the relationship between simple polygon boundary loop nodes and mesh vertices; and

decoding mesh geometry and mesh properties per vertex/face/corner.

15. A computer program embodied on a computer-readable medium for providing a program that is capable of executing a method for compressing a non-manifold mesh, comprising:

a code segment for converting the non-manifold mesh to at least one manifold mesh, including storing information on how to cluster vertices;

a code segment for compressing the at least one manifold mesh; and

a code segment for compressing the information on how to cluster vertices.

16. A bit-stream conveyed between at least two points through a data communications network, said bit-stream conveying an encoded non-manifold polygonal mesh that has been converted to at least one manifold polygonal mesh, said bit-stream having a syntax comprised of, for each vertex of the manifold polygonal mesh, a stitching command having a type selected from a set of types consisting of NONE, PUSH, GET or POP;

a stitch length;

a stack index;

a differential length;

a push bit; and

a reverse bit.

17. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encoding a non-manifold polygonal mesh, said method steps comprising:

representing the non-manifold polygonal mesh as at least one manifold polygonal mesh and a vertex clustering array obtained by cutting through singular edges and vertices of the non-manifold polygonal mesh;

representing each connected component of the at least one manifold polygonal mesh with a vertex graph, a triangle tree, and a triangle data record;

representing the information contained in the vertex cluster array as stitching information comprised a set of stitching commands each of the type NONE, PUSH, GET or POP, each stitching command having associated data;

applying the stitching information to a vertex cluster look-up table for describing a relation between polygon boundary loop nodes and mesh vertices; and

encoding the stitching information in a bit-stream according to a predetermined bit-stream syntax, the bit-stream syntax being comprised of, for each vertex of the manifold polygonal mesh, one of the stitching commands having the type NONE, PUSH, GET or POP;

a stitch length;

a stack index;

a differential length;

a push bit; and

a reverse bit.

18. A computer system for compressing a non-manifold mesh, comprising:

data storage for storing a representation of a non-manifold mesh;

a data processor coupled to the data storage and operating under the control of a program for converting the non-manifold mesh to at least one manifold polygonal mesh and storing information on how to cluster vertices;

said data processor further operating to compress the at least one manifold polygonal mesh and to also compress the information on how to cluster vertices; and

a communications network interface coupled between said data processor and a communications network, said data processor further being operable for generating a bit-stream for conveying the encoded non-manifold polygonal mesh that has been converted to at least one manifold polygonal mesh, said bit-stream having a syntax comprised of, for each vertex of the manifold polygonal mesh, a stitching command having a type selected from a set of types consisting of NONE, PUSH, GET or POP.

19. A computer system as in claim 18, wherein said bit-stream syntax is further comprised of a stitch length;

a stack index;

a differential length;

a push bit; and

a reverse bit.