US6031548A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Progressive multi-level transmission and display of triangular meshes
Assignee: International Business Machines Corp
•
Filing: 1998-02-13
•
Granted: 2000-02-29
•
Expires: 2018-02-13
Abstract
Abstract Disclosed is a representation and file format for a multi-level progressive transmission or display of a triangular mesh, referred to as a Progressive Multi-Level Representation (PMR). Methods are disclosed for generating the PMR, for progressively building a triangular mesh from a PMR representation, and for extracting a particular level of detail of a triangular mesh from the PMR representation.
Inventors
- 👤 Andre Pierre Gueziec
- 👤 Francis Lazarus
- 👤 Gabriel Taubin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 20:38
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
183 words
A method for generating a multi-level progressive representation of a triangular mesh, comprising steps of: specifying a collection of vertex and triangle lists, with one pair (vertex list, triangle list) being provided for each Level of Detail in order of decreasing Level of Detail, wherein a pair (vertex list, triangle list) of a Level of Detail i is referred to as a batch of Level of Detail i; for each Level of Detail i of the triangular mesh, determining a total number of vertices (n vi ) of the Level of Detail i as the sum of vertices in batches i, i+1 . . . ,L max , where x represents a lowest Level of Detail; and for each triangle vertex index that is not between 0 and (n vi -1), specifying a vertex representative index, wherein if the vertex representative index is not between 0 and (n vi -1), specifying a vertex representative index for the triangle vertex index, with a succession of vertex representative indices being specified such that a last vertex representative index is between 0 and (n vi -1).
Claim 2
Independent Claim
183 words
A method for generating a multi-level progressive representation of a triangular mesh, comprising steps of: specifying a collection of vertex and triangle lists, with one pair (vertex list, triangle list) being provided for each Level of Detail in order of decreasing Level of Detail, wherein a pair (vertex list, triangle list) of a Level of Detail i is referred to as a batch of Level of Detail i; for each Level of Detail i of the triangular mesh, determining a total number of vertices (n vi ) of the Level of Detail i as the sum of vertices in batches i, i+1 . . . ,L max , where x represents a lowest Level of Detail; and for each triangle vertex index that is not between 0 and (n vi -1), specifying a vertex representative index, wherein if the vertex representative index is not between 0 and (n vi -1), specifying a vertex representative index for the triangle vertex index, with a succession of vertex representative indices being specified such that a last vertex representative index is between 0 and (n vi -1).
Claim 3
Dependent Claim
32 words
A method as in claim 1, wherein to fully specify the Level of detail i of the triangular mesh, all batches of Levels i, i+1. . . , L max are required.
Claim 4
Dependent Claim
23 words
A method as in claim 1, wherein the step of specifying includes a step of assigning Levels of Detail to vertices and triangles.
Claim 5
Dependent Claim
72 words
A computer data structure for representing a multi-level progressive representation of a triangular mesh, comprising: triangular mesh vertex coordinates and triangle vertex indices, stored in batches from a level of detail (L max ) associated with a lowest resolution, to a level of detail (1), associated with a highest resolution; and vertex representative indices for triangle vertex indices having a value outside of a range allowed in a current level of detail.
Claim 6
Dependent Claim
72 words
A computer data structure for representing a multi-level progressive representation of a triangular mesh, comprising: triangular mesh vertex coordinates and triangle vertex indices, stored in batches from a level of detail (L max ) associated with a lowest resolution, to a level of detail (1), associated with a highest resolution; and vertex representative indices for triangle vertex indices having a value outside of a range allowed in a current level of detail.
Claim 7
Dependent Claim
17 words
A computer data structure as in claim 4, wherein each batch also stores vertex and triangle properties.
Claim 8
Dependent Claim
21 words
A computer data structure as in claim 4, wherein the vertex representative indices are provided as required by triangle vertex indices.
Claim 9
Dependent Claim
65 words
A computer data structure as in claim 4, wherein a secondary vertex position is provided for each vertex of level between L max and 1 such that, for a vertex that is a representative of another vertex at a level of detail i, the secondary vertex position is used for the vertex when decreasing the resolution by transitioning from level i +1 to level i.
Claim 10
Dependent Claim
64 words
A computer data structure as in claim 4, wherein a secondary vertex property is provided for each vertex of level between L max and 1 such that, for a vertex that is a representative of another vertex at a level of detail i, the secondary vertex property is used for the vertex when decreasing the resolution by transitioning from level i+1 to level i.
Claim 11
Dependent Claim
24 words
A computer data structure as in claim 4, wherein the vertex representative indices are provided together, in conjunction with a first batch of triangles.
Claim 12
Dependent Claim
23 words
A computer data structure as in claim 4, wherein the vertex representatives are stored in direct form in a path compressed representative array.
Claim 13
Dependent Claim
57 words
A computer data structure as in claim 4, wherein the triangle vertex indices are maintained in a reference list and a current list, wherein a reference copy stored in the reference list can be read only, and wherein a current copy stored in the current list can be read, modified, and used for display and other computations.
Claim 14
Independent Claim
97 words
A method for extracting a particular level of detail i from a multi-level progressive representation of a triangular mesh, comprising steps of: determining vertices and triangles participating in the level of detail i, the step of determining including a step of determining a highest index n vi of a vertex participating in the level of detail; and for each triangle participating in the level of detail, and for each vertex index of the triangle, replacing each vertex index with a representative vertex index that is in a valid range of indices between 0 and (n vi -1).
Claim 15
Independent Claim
97 words
A method for extracting a particular level of detail i from a multi-level progressive representation of a triangular mesh, comprising steps of: determining vertices and triangles participating in the level of detail i, the step of determining including a step of determining a highest index n vi of a vertex participating in the level of detail; and for each triangle participating in the level of detail, and for each vertex index of the triangle, replacing each vertex index with a representative vertex index that is in a valid range of indices between 0 and (n vi -1).
Claim 16
Dependent Claim
57 words
A method as in claim 12, wherein the vertices and triangles that participate in the level of detail i are determined to be the vertices and triangles of a first batch of vertices and triangles, and then of a second batch of vertices and triangles, and so on until the number of vertices equals n vi .
Claim 17
Dependent Claim
55 words
A method as in claim 12, wherein for each triangle that participates in the level of detail, for each vertex index of the triangle, replacing each vertex index with a representative between 0 and (n vi -1) by following a representative hierarchy until the representative index has a value between 0 and (n vi -1).
Claim 18
Dependent Claim
56 words
A method as in claim 12, wherein for a given level of detail i, vertex representatives are ignored between n vi and (n v1 -1), and are used between n vLmax and (n v1 -1); and the vertex indices of triangles that participate in the level of detail i are replaced using the representative vertex indices.
Claim 19
Dependent Claim
135 words
A method as in claim 12, and including a step of providing a smooth transition between two adjacent levels of detail when detail is added to the triangular mesh by transitioning from a Level L +1 to a Level L, comprising steps of: adding the vertices of Level L to the triangular mesh, wherein the added vertices have a representative in a lower level of detail triangular mesh; determining new triangles having new vertices (vertices of Level L), where the coordinates of the vertex representatives are used first for producing a triangular mesh that is geometrically the same as the Level L +1 triangular mesh; and linearly interpolating the coordinates of the vertices from the produced triangular mesh to the coordinates of the new vertices using a parameter A that varies between 0 and 1.
Claim 20
Independent Claim
51 words
A method for use in a computer system for generating a multi-level progressive representation of a triangular mesh, comprising steps of: assigning levels of detail (LODs) to vertices and triangles; and determining vertex representatives, such that a representative of a vertex is a vertex of a higher LOD of decreased resolution.
Claim 21
Independent Claim
51 words
A method for use in a computer system for generating a multi-level progressive representation of a triangular mesh, comprising steps of: assigning levels of detail (LODs) to vertices and triangles; and determining vertex representatives, such that a representative of a vertex is a vertex of a higher LOD of decreased resolution.
Claim 22
Dependent Claim
52 words
A method as in claim 17, wherein the triangular mesh is provided as a multi-level clustered representation, and further comprising steps of: converting vertex levels of the multi-level clustered representation to vertex levels of a multi-level progressive representation; assigning levels to triangles; and ordering vertices and triangles in order of decreasing level.
Claim 23
Dependent Claim
77 words
A method as in claim 17, wherein a sequence of edge collapse specifications is specified as an ordered list of ordered pairs of vertex IDs of the triangular mesh, and further comprising steps of: assigning levels to vertices and triangles, and determining vertex representatives; determining L max as a level of least resolution, and assigning L max to all remaining vertices and triangles not having a representative; and ordering vertices and triangles in order of decreasing level.
Claim 24
Independent Claim
72 words
A method for defining a partial ordering of edge collapse specifications given a sequence of edge collapse specifications, comprising steps of: obtaining a final ordered list of edge collapses; redoing the collapses in their original order and computing vertex levels; and examining the current level of all vertices in a star of a collapsed edge, wherein each level greater than zero indicates that the corresponding vertex was the outcome of a collapse.
Claim 25
Independent Claim
72 words
A method for defining a partial ordering of edge collapse specifications given a sequence of edge collapse specifications, comprising steps of: obtaining a final ordered list of edge collapses; redoing the collapses in their original order and computing vertex levels; and examining the current level of all vertices in a star of a collapsed edge, wherein each level greater than zero indicates that the corresponding vertex was the outcome of a collapse.
Claim 26
Dependent Claim
18 words
A method as in claim 20, wherein the defined partial ordering is stored using a Directed Acyclic Graph.
Claim 27
Independent Claim
158 words
A method for lowering a Level of Detail (LOD) of a triangular mesh from a Level L +1 to a Level L, comprising steps of: providing a progressive multi-level representation of the triangular mesh; and providing a smooth transition between two adjacent LODs when detail is added to the triangular mesh by transitioning from Level L +1 to Level L, the step of providing comprising steps of, adding vertices of triangles of Level L to the triangular mesh, wherein the added vertices have a representative in a lower LOD triangular mesh; determining new triangles having new vertices (vertices of Level L), where the coordinates of the vertex representatives are used first for producing a triangular mesh that is geometrically the same as the Level L +1 triangular mesh; and linearly interpolating the coordinates of the vertices from the produced triangular mesh to the coordinates of the new vertices using a parameter A that varies between 0 and 1.
Claim 28
Independent Claim
158 words
A method for lowering a Level of Detail (LOD) of a triangular mesh from a Level L +1 to a Level L, comprising steps of: providing a progressive multi-level representation of the triangular mesh; and providing a smooth transition between two adjacent LODs when detail is added to the triangular mesh by transitioning from Level L +1 to Level L, the step of providing comprising steps of, adding vertices of triangles of Level L to the triangular mesh, wherein the added vertices have a representative in a lower LOD triangular mesh; determining new triangles having new vertices (vertices of Level L), where the coordinates of the vertex representatives are used first for producing a triangular mesh that is geometrically the same as the Level L +1 triangular mesh; and linearly interpolating the coordinates of the vertices from the produced triangular mesh to the coordinates of the new vertices using a parameter A that varies between 0 and 1.
Claim 29
Independent Claim
198 words
A system for generating a representation of a triangular mesh, comprising: a memory storing a data structure for representing a multi-level progressive representation of the triangular mesh, the data structure comprising (a) triangular mesh vertex coordinates and triangle vertex indices stored in batches from a level of detail (L max ) associated with a lowest resolution to a level of detail (1) associated with a highest resolution, and (b) vertex representative indices for triangle vertex indices having a value outside of a range allowed in a current level of detail; at least one data processing unit; and a program executed by the at least one data processing unit for extracting a particular level of detail i from the multi-level progressive representation, the program operating to determine those vertices and triangles participating in the level of detail i, including determining a highest index n vi of a vertex participating in the level of detail, and for each triangle participating in the level of detail, and for each vertex index of the triangle, the program operating to replace each vertex index with a representative vertex index that is in a valid range of indices between 0 and (n vi -1).
Claim 30
Independent Claim
198 words
A system for generating a representation of a triangular mesh, comprising: a memory storing a data structure for representing a multi-level progressive representation of the triangular mesh, the data structure comprising (a) triangular mesh vertex coordinates and triangle vertex indices stored in batches from a level of detail (L max ) associated with a lowest resolution to a level of detail (1) associated with a highest resolution, and (b) vertex representative indices for triangle vertex indices having a value outside of a range allowed in a current level of detail; at least one data processing unit; and a program executed by the at least one data processing unit for extracting a particular level of detail i from the multi-level progressive representation, the program operating to determine those vertices and triangles participating in the level of detail i, including determining a highest index n vi of a vertex participating in the level of detail, and for each triangle participating in the level of detail, and for each vertex index of the triangle, the program operating to replace each vertex index with a representative vertex index that is in a valid range of indices between 0 and (n vi -1).
Claim 31
Dependent Claim
32 words
A system as in claim 23, and further comprising a network interface coupled to a data communications network, wherein at least a representation of the triangular mesh is received from the network.
Claim 32
Dependent Claim
45 words
A system as in claim 23, and further comprising: a network interface coupled to a data communications network; and a download thread for progressively downloading from the network a total number of levels of detail, and triangle, vertex, and attribute data of the triangular mesh.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-28 | 2003-08-30 | 2004-02-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-28 | 2007-08-30 | 2008-02-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-28 | 2011-08-30 | 2012-02-29 | $7700.00 | Window Closed / Lapsed |