US6009435A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Progressive compression of clustered multi-resolution polygonal models
Assignee: Google LLC
•
Filing: 1997-11-21
•
Granted: 1999-12-28
•
Expires: 2017-11-21
Abstract
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.
Inventors
- 👤 Gabriel Taubin
- 👤 William Pettit Horn
- 👤 Paul Borrel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:11
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/001; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
339 words
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.
Claim 2
Independent Claim
339 words
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.
Claim 3
Dependent Claim
67 words
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.
Claim 4
Dependent Claim
14 words
A system, as in claim 2, where the sequence of connect bits is compressed.
Claim 5
Dependent Claim
15 words
A system, as in claim 3, where the sequence of connect bits is entropy encoded.
Claim 6
Dependent Claim
15 words
A system, as in claim 3, where the sequence of connect bits is run-length encoded.
Claim 7
Dependent Claim
46 words
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.
Claim 8
Dependent Claim
83 words
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.
Claim 9
Dependent Claim
12 words
A system, as in claim 5, where the geometric information is compressed.
Claim 10
Dependent Claim
94 words
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.
Claim 11
Dependent Claim
109 words
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.
Claim 12
Dependent Claim
53 words
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.
Claim 13
Independent Claim
278 words
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.
Claim 14
Independent Claim
278 words
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.
Claim 15
Dependent Claim
57 words
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.
Claim 16
Dependent Claim
56 words
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.
Claim 17
Dependent Claim
12 words
A system, as in claim 5, where the connectivity information is compressed.
Claim 18
Dependent Claim
54 words
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.
Claim 19
Dependent Claim
12 words
A system, as in claim 5, where the clustering information is compressed.
References Cited (Backward Citations)
US5448686A
Cited
US5363107A
Cited
US5748865A
Cited
US5506947A
Cited
EP0757333A2
Cited
US5872572A
Cited
US5825369A
Cited
US5886702A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-27 | 2003-06-28 | 2003-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-27 | 2007-06-28 | 2007-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-27 | 2011-06-28 | 2011-12-28 | $7700.00 | Window Closed / Lapsed |