Progressive multi-level transmission and display of triangular meshes

• US 6,031,548 A
• Filed: 02/13/1998
• Issued: 02/29/2000
• Est. Priority Date: 06/13/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lazarus, Francis, Taubin, Gabriel, Gueziec, Andre Pierre
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/023,757
• Time in Patent Office: 746 Days
• Field of Search: 345/440, 345/423, 345/441, 345/443, 345/118, 345/121
• US Class Current: 345/440
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

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.

Claims

1. 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).

2. 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.

3. A method as in claim 1, wherein the step of specifying includes a step of assigning Levels of Detail to vertices and triangles.

4. 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.

5. A computer data structure as in claim 4, wherein each batch also stores vertex and triangle properties.

6. A computer data structure as in claim 4, wherein the vertex representative indices are provided as required by triangle vertex indices.

7. 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.

8. 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.

9. A computer data structure as in claim 4, wherein the vertex representative indices are provided together, in conjunction with a first batch of triangles.

10. A computer data structure as in claim 4, wherein the vertex representatives are stored in direct form in a path compressed representative array.

11. 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.

12. 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).

13. 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.

14. 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).

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. A method as in claim 20, wherein the defined partial ordering is stored using a Directed Acyclic Graph.

22. 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.

23. 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).

24. 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.

25. 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.