Mesh simplification and construction of progressive meshes

• US 5,929,860 A
• Filed: 02/07/1997
• Issued: 07/27/1999
• Est. Priority Date: 01/11/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hoppe, Hugues H.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US08/797,502
• Time in Patent Office: 900 Days
• Field of Search: 345/419, 345/425, 345/427, 345/428, 345/429, 345/430, 345/421, 345/422, 345/423
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

An efficient, lossless, continuous-resolution representation (the "PM representation") of highly detailed geometric models for computer graphics specifies a succession of progressively more detailed polygonal meshes (i.e., "progressive meshes") as a base polygonal mesh and a sequence of complete mesh refinement transformations (e.g., the vertex split transformation) that approximate the model at progressively finer levels of detail. Procedures for storing and transmitting geometric models using the PM representation address several practical problems in computer graphics: smooth geomorphing of level-of-detail approximations, progressive transmission, mesh compression, and selective refinement. An optimized mesh simplification procedure constructs the PM representation of a model from an arbitrary polygonal mesh, while preserving the geometry of the original mesh as well as its overall appearance as defined by its discrete and scalar appearance attributes such as material identifiers, color values, normals, and texture coordinates. In particular, the PM representation and these procedures preserve discontinuity curves such as creases and material boundaries of the geometric model.

Claims

1. In a computer, a method of simplifying an arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining edges between connected pairs of the vertices and faces defined by plural connected edges for representing multi-dimensional objects with computer graphics, comprising:

(a) choosing an edge of the mesh;

(b) performing an edge collapse transformation on the edge to produce a simpler mesh wherein the pair of vertices connected by the edge is replaced by the edge collapse transformation with a single vertex; and

(c) performing a plurality of iterations of the steps (a) and (b) to produce a base mesh having a desired level of detail.

2. The method of claim 1 further comprising:

(d) choosing the desired level of detail of the base mesh; and

(e) performing the iterations of the steps (a) and (b) until the simpler mesh has a level of detail at least as simple as the desired level of detail.

3. The method of claim 1 further comprising:

(d) choosing a number of faces of the base mesh at the desired level of detail; and

(e) performing the iterations of the steps (a) and (b) until the simpler mesh is within one face of the chosen number of faces.

4. The method of claim 1 further comprising:

(d) performing the iterations of the steps (a) and (b) until the simpler mesh has a level of detail equal to a simplest mesh of a same topological type as the initial mesh.

5. In a computer, a method of constructing a variable resolution representation of a multi-dimensional object from an arbitrary initial mesh representation of the object for displaying computer graphics views of the objects the arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining a plurality of edges between connected pairs of the vertices, the method comprising:

choosing a succession of mesh simplifying transformations that, when applied successively beginning with the arbitrary initial mesh, yield a succession of progressively simpler meshes, and a last in the succession of mesh simplifying transformations yielding a base mesh; and

recording the base mesh and a succession of mesh refining transformations which are an inverse of the mesh simplifying transformations and in a reverse order of the succession of mesh simplifying transformations, the mesh refining transformations exactly reproducing the arbitrary initial mesh when applied successively beginning with the base mesh.

6. The method of claim 5 wherein the mesh simplifying transformations are all edge collapse transformations and the mesh refinement transformations are all vertex split transformations.

7. The method of claim 6 further comprising, for each of the succession of progressively simpler meshes beginning with the arbitrary initial mesh:

choosing a current edge collapse transformation out of a plurality of candidate edge collapse transformations on a current mesh of the succession of progressively simpler meshes; and

applying the edge collapse transformation to the current mesh to yield a next mesh in the succession of progressively simpler meshes.

8. The method of claim 7 further comprising:

choosing the current edge collapse transformation at random out of the candidate edge collapse transformations.

9. The method of claim 7 wherein the step of choosing the current edge collapse transformation comprises:

prioritizing the candidate edge collapse transformations according to an appearance metric; and

choosing one of the plurality of edges having a highest priority as the current edge collapse transformation.

10. The method of claim 9 further comprising:

imposing a predetermined maximum dihedral angle restriction and a manifold preservation restriction on the candidate edge collapse transformations.

11. The method of claim 7 wherein the step of choosing the current edge collapse transformation comprises:

calculating an appearance metric for each of the candidate edge collapse transformations; and

choosing the current edge collapse transformation out of the candidate edge collapse transformations to optimize the appearance metric.

12. The method of claim 11 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises:

measuring a geometric deviation between the initial arbitrary mesh and a mesh resulting from applying the candidate edge collapse transformation to the current mesh.

13. The method of claim 11 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises:

sampling geometric attributes at a plurality of points on a surface of the initial arbitrary mesh;

measuring a geometric deviation between the geometric attributes of the initial arbitrary mesh at the points and a resultant mesh resulting from applying the candidate edge collapse transformation to the current mesh;

accumulating the geometric deviation with a spring term having an adaptive spring constant; and

setting the adaptive spring constant according to a ratio of a number of the points to a number of faces in a neighborhood of the edge collapse transformation.

14. The method of claim 11 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises:

measuring a scalar attribute deviation between the initial arbitrary mesh and a mesh resulting from applying the candidate edge collapse transformation to the current mesh.

15. The method of claim 11 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises:

measuring a deviation in scalar and geometric attributes between the initial arbitrary mesh and a mesh resulting from applying the candidate edge collapse transformation to the current mesh.

16. The method of claim 11 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises:

separately measuring a deviation in scalar attributes and a deviation in geometric attributes between the initial arbitrary mesh and a mesh resulting from applying the candidate edge collapse transformation to the current mesh; and

summing the deviation in scalar attributes with the deviation in geometric attributes.

17. The method of claim 11 wherein the step of calculating the appearance metric for each of the candidate edge collapse transformations comprises:

sampling geometric attributes at a plurality of points on sharp edges of the initial arbitrary mesh; and

measuring a geometric deviation between the geometric attributes at the points and sharp edges of a mesh resulting from applying the candidate edge collapse transformation to the current mesh.

18. The method of claim 7 wherein the step of choosing the current edge collapse transformation comprises:

checking whether a choice for the current edge collapse transformation modifies a discontinuity curve topology of the current mesh; and

disallowing the choice if the choice modifies the discontinuity curve topology.

19. The method of claim 7 wherein the step of choosing the current edge collapse transformation comprises:

checking whether a choice for the current edge collapse transformation modifies a discontinuity curve topology of the current mesh; and

penalizing the choice if the choice modifies the discontinuity curve topology.

20. A computer based system for constructing a variable resolution representation of a multi-dimensional object from an arbitrary initial mesh representation of the object for displaying computer graphics views of the object, the arbitrary initial mesh having a plurality of vertices and a connectivity of the vertices defining a plurality of edges between connected pairs of the vertices, the system comprising:

a mesh transformation processor for iteratively choosing a mesh simplifying transformation, and applying the chosen mesh simplifying transformation to a current mesh in a succession of progressively simpler meshes beginning with the initial arbitrary mesh to yield a next mesh in the succession, a last in the succession of mesh simplifying transformations yielding a base mesh; and

an encoder for recording the base mesh and a succession of mesh refining transformations which are an inverse of the mesh simplifying transformations and in a reverse order of the succession of mesh simplifying transformations;

the mesh refining transformations exactly reproducing the arbitrary initial mesh when applied successively beginning with the base mesh.

21. The computer based system of claim 20 comprising:

a user interface control for selecting a desired level of detail; and

the mesh transformation processor performing iterations of choosing and applying the mesh simplifying transformations until applying a last of the mesh simplifying transformation yields a next mesh having a level of detail at least as simple as the desired level of detail.