Progressive compression of clustered multi-resolution polygonal models

• US 6,009,435 A
• Filed: 11/21/1997
• Issued: 12/28/1999
• Est. Priority Date: 11/21/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Horn, William Pettit, Borrel, Paul, Taubin, Gabriel
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/976,247
• Time in Patent Office: 767 Days
• Field of Search: 707/101, 345/440, 345/423, 345/443, 345/420, 345/425, 345/428
• US Class Current: 345/555
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer system progressively stores and transmits compressed clustered multi-resolution polygonal models. The computer uses a data structure that represents a clustered multi-resolution polygonal model in n-dimensional space. The data structure has a connectivity record which encodes the connectivity information of the highest level of detail. The data structure also has a clustering record which encodes how the vertices of each level of detal are clustered to obtain the vertices of the next lower level of detail. The clustering record is organized in decreasing order of level of detail. The data structure also has a data record with information describing the vertex positions of the levels of detail, and optionally the corresponding properties. The fields of the data record are organized in increasing order of level of detail. The system also includes ways for creating this data structure from a clustered multi-resolution polygonal model, transmitting this information between computers, and compressing and decompressing this transmitted information.

Claims

1. A system for compressing a clustered multi-resolution polygonal model comprising:

a memory containing a polygonal model with two or more levels of detail with progressively more resolution, each level of detail having a plurality of vertices forming a plurality of triangles, each level of detail having a geometric information about the position of the vertices in space and each level of detail having a connectivity information about the association between each triangle and the vertices that form the triangle, the memory further having a clustering information for each level of detail about how a plurality of sets of vertices in each level of detail are clustered and how each of the respective clusters correspond to a vertex in a level of detail with a next lower resolution;

a central processing unit (CPU);

a connectivity process, executed by the CPU, that identifies the connectivity information of a highest resolution level of detail;

a clustering process, executed by the CPU, that orders the clustering information for each level of detail, from the level of detail with the highest resolution to the level of detail with the lowest resolution, where the clustering information is compressed by a clustering compression process having the following steps;

first, determining a connectivity preserving partition of the vertices of the level of detail into one or more connected clusters, with two vertices joined by an edge of the level of detail belonging to the same connected cluster if the clustering information determines that the two vertices are clustered into the same set, and

second, determining an anti-connectivity partition of the connected clusters into one or more sets of connected clusters, with two connected clusters belonging to the same set of connected clusters if the clustering information determines that the vertices that belong to the two connected clusters are clustered into the same set; and

a geometry process, executed by the CPU, that orders the geometric information of each level of detail from the level of detail with lowest resolution to the level of detail with highest resolution.

2. A system, as in claim 1, where the connectivity preserving partition is represented in compressed form as a sequence of connect bits composed of one or more connect bits, each connect bit corresponding to one edge of the corresponding level of detail, and where the value of the connect bit describes whether the two vertices joined by the edge belong to the same connected cluster or not.

3. A system, as in claim 2, where the sequence of connect bits is compressed.

4. A system, as in claim 3, where the sequence of connect bits is entropy encoded.

5. A system, as in claim 3, where the sequence of connect bits is run-length encoded.

6. A system, as in claim 2, where the sequence of connect bits is represented by a parameterized bit pattern, the parameterized bit pattern composed of one or more bit parameters, the bit parameters determining the values of the connect bits in the sequence of connect bits.

7. A system, as in claim 1, where the anti-connectivity partition is represented in compressed form as one or more anti cluster lists, each anti cluster list corresponding to one set of connected cluster containing two or more connected clusters, and composed of one or more anti cluster list elements, each anti cluster list element corresponding to one connected cluster belonging to the set of connected clusters, and with no cluster list associated with sets of connected clusters composed of exactly one connected cluster.

8. A system, as in claim 5, where the geometric information is compressed.

9. A system, as in claim 8, where the geometric information of the levels of detail of higher resolution than the lowest level of detail are compressed using the correspondence between the vertices and triangles of each level of detail and the vertices and triangles of the next lower level of detail defined by the clustering information of the level of detail to represent the coordinates of each vertex of the level of detail as the sum of the coordinates of the corresponding vertex of the next lower level of detail plus a vertex displacement.

10. A system, as in claim 8, where the geometric information of the levels of detail of higher resolution than the lowest level of detail are compressed using the correspondence between the vertices and triangles of each level of detail and the vertices and triangles of the next lower level of detail defined by the clustering information of the level of detail to represent the coordinates of each vertex of the level of detail as the sum of the a predictor function plus a vertex correction, the predictor function being a function of zero or more predictor parameters and zero or more elements of the next lower level of detail.

11. A system, as in claim 10, where each vertex correction is further computed by evaluating an intra-level prediction function and then adding a second correction vector, the intra-level predictor function being a function of zero or more intra-level predictor parameters and zero or more elements of the current level of detail previously computed.

13. A system, as in claim 5, that further comprises a transmission process having the following steps:

first, transmitting the connectivity information of the highest resolution level of detail;

second, transmitting all of the clustering information in decreasing order of level of detail; and

third, transmitting all of the geometric information in increasing order of level of detail.

14. A system, as in claim 5, further comprising a storage process having the following steps:

first, storing the connectivity information of the highest resolution level of detail;

second, storing all of the clustering information in decreasing order of level of detail; and

third, storing all of the geometric information in increasing order of level of detail.

15. A system, as in claim 5, where the connectivity information is compressed.

16. A system, as in claim 15, where the connectivity information is compressed using any one or more of the following methods:

Rossignac and Taubin'"'"'s Compression of Simple Geometric Models Using Spanning Trees,

Rossignac and Taubin'"'"'s Compression of Geometric Models Using Spanning Trees,

Deering'"'"'s Generalized Triangle Meshes,

Hoppe'"'"'s Progressive Meshes, and

Popovic'"'"'s Progressive Simplicial Complexes.

17. A system, as in claim 5, where the clustering information is compressed.

12. A system for compressing a clustered multi-resolution polygonal model comprising:

a memory containing a polygonal model with two or more levels of detail with progressively more resolution, each level of detail having a plurality of vertices forming a plurality of triangles, each level of detail having a geometric information about the position of the vertices in space and each level of detail having a connectivity information about the association between each triangle and the vertices that form the triangle, the memory further having a clustering information for each level of detail about how a plurality of sets of vertices in each level of detail are clustered and how each of the respective clusters correspond to a vertex in a level of detail with a next lower resolution;

a central processing unit (CPU);

a connectivity process, executed by the CPU, that identifies the connectivity information of a highest resolution level of detail;

a clustering process, executed by the CPU, that orders the clustering information for each level of detail, from the level of detail with the highest resolution to the level of detail with the lowest resolution; and

a geometry process, executed by the CPU, that orders the geometric information of each level of detail from the level of detail with lowest resolution to the level of detail with highest resolution, where the geometric information of the lowest level of detail is compressed by representing each vertex of as the sum of a first prediction function and a first correction vector, the first predictor function being a function of zero or more first predictor parameters and zero or more vertices of the lowest resolution level of detail previously computed.