Geomorphs and variable resolution control of progressive meshes

• US 5,966,133 A
• Filed: 02/07/1997
• Issued: 10/12/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, Hughes H.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US08/797,501
• Time in Patent Office: 977 Days
• Field of Search: 395/119, 395/120, 395/121, 395/122, 395/123, 345/419, 345/420, 345/421, 345/422, 345/427, 345/425, 345/428, 345/429, 345/430
• US Class Current: 345/420
• 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. A method of creating a smooth visual transition between any two meshes of a progressive resolution succession of meshes representing a multi-dimensional geometric object for computer graphics, comprising:

selecting a coarser mesh and a finer mesh from the progressive resolution succession of meshes specified by a base mesh and a sequence of vertex split transformations which yield the progressive resolution succession of meshes when applied in sequence beginning with the base mesh, each mesh in the progressive resolution succession being defined by a set of position coordinates and a connectivity of a plurality of vertices, the vertex split transformations each modifying a position coordinate of a split vertex in a current mesh in the progressive resolution succession to yield a new position coordinate of the split vertex and introduce a position coordinate of a new vertex in a next mesh in the progressive resolution succession such that each vertex of the finer mesh has a vertex position derived from a vertex position of an ancestor vertex in the coarser mesh; and

defining a geomorph having a set of vertices with a connectivity of the finer mesh and a set of vertex positions, at least some of the vertex positions varying between position coordinates of vertices in the finer mesh and position coordinates of their ancestor vertices in the coarser mesh according to a blend parameter;

evaluating the geomorph at a plurality of values of the blend parameter; and

displaying views of the geometric object based on the geomorph evaluated at the values of the blend parameter.

2. The method of claim 1 comprising:

recursively backtracking through a subset of the sequence of vertex split transformations which are applied to a portion of the progressive resolution succession of meshes from the coarser mesh to the finer mesh to locate an ancestor vertex in the coarser mesh for a vertex of the finer mesh.

3. The method of claim 1 comprising:

tracking the ancestor vertex of each new vertex introduced by a subset of the sequence of vertex split transformations as the subset is applied to a portion of the progressive resolution succession of meshes from the coarser mesh to the finer mesh.

4. The method of claim 1 wherein the step of evaluating the geomorph at a plurality of values of the blend parameter comprises:

varying a value of the blend parameter within a predetermined range; and

interpolating the vertex positions between the position coordinates of the vertices in the finer mesh and the position coordinates of their ancestor vertices in the coarser mesh based on the value of the blend parameter.

5. The method of claim 4 comprising:

interpolating the vertex positions according to a non-linear function of the blend parameter.

6. The method of claim 4 comprising:

interpolating the vertex positions according to a glow-in, slow-out interpolating function of the blend parameter.

7. The method of claim 1 wherein the connectivity of the vertices of the geomorph defines a plurality of faces, the connectivity of the vertices of the finer mesh defines a plurality of faces having discrete attributes associated therewith, the method further comprising:

associating the discrete attributes of the faces of the finer mesh with the faces of the geomorph.

8. The method of claim 1 wherein the connectivity of the vertices of the coarser mesh defines a plurality of faces and corners, each of the vertex split transformations applied in a portion of the sequence to the progressive resolution succession from the coarser mesh to the finer mesh introducing at least one new face and corners such that the finer mesh has a first group of corners also present in the coarser mesh and a second group of corners introduced by the portion of the sequence of vertex split transformations, the corners of the coarser mesh being associated with coarse scalar attribute values, the corners of the finer mesh being associated with fine scalar attribute values, the geomorph having a same first and second set of corners as the finer mesh being defined by the connectivity of the finer mesh, and the method further comprising:

defining first scalar attributes for associating with the first group of corners of the geomorph, the first scalar attributes varying according to the blend parameter between the coarse scalar attribute values associated with that group of corners in the coarser mesh and the fine scalar attribute values associated with that group of corners in the finer mesh;

defining second scalar attributes for associating with a subset of the second group of corners of the geomorph that are introduced by the vertex split transformations with a same scalar attribute value as an adjacent corner, the second scalar attributes varying according to the blend parameter between the coarse scalar attribute value of the adjacent corner in the coarser mesh and the fine scalar attribute value of the subset in the finer mesh; and

defining third scalar attributes for associating with a remainder of the second group of corners of the geomorph not in the subset and having constant values equal to the fine scalar attribute values of the remainder of the second group of corners in the fine mesh.

9. A computer readable data storage medium having encoded thereon a geomorph data structure for performing a smooth visual transition with computer graphics between a coarser mesh and a finer mesh selected from a progressive resolution succession of meshes representing a multi-dimensional object, the progressive resolution succession being defined by a base mesh and a sequence of vertex split transformations where the vertex split transformations refine a set of position coordinates and a connectivity of vertices in the finer mesh from a set of position coordinates and a connectivity of ancestor vertices in the coarser mesh, the geomorph data structure comprising:

a vertex positions table for specifying positions of a plurality of vertices of the geomorph as varying from the set of position coordinates of the ancestor vertices in the coarser mesh to the set of position coordinates of the vertices in the finer mesh according to an interpolating function of a blend parameter; and

a simplicial complex table for specifying a connectivity of the vertices of the geomorph as equal to the connectivity of the vertices in the finer mesh.

10. The computer readable data storage medium of claim 9 wherein the connectivity of the vertices in the finer mesh define a plurality of faces, the faces being associated with discrete attribute values, the geomorph data structure further comprises:

a discrete attributes table for specifying discrete attributes of faces of the geomorph as equal to the discrete attribute values of faces of the finer mesh.

11. The computer readable data storage medium of claim 9 wherein the connectivity of the vertices of the coarser mesh defines a plurality of faces and corners, each of the vertex split transformations introducing at least one new face and corners such that the finer mesh has a first group of corners also present in the coarser mesh and a second group of corners introduced by the vertex split transformations, the corners of the coarser mesh being associated with coarse scalar attribute values, the corners of the finer mesh being associated with fine scalar attribute values, the geomorph having a same first and second set of corners as the finer mesh being defined by the connectivity of the finer mesh, and the geomorph data structure further comprising:

a scalar attributes table for specifying first scalar attributes of the first group of corners of the geomorph as varying according to the blend parameter between the coarse scalar attribute values associated with that group of corners in the coarser mesh and the fine scalar attribute values associated with that group of corners in the finer mesh, and for specifying second scalar attributes of a subset of the second group of corners of the geomorph which subset is introduced by the vertex split transformations with a same scalar attribute value as an adjacent corner as varying according to the blend parameter between the coarse scalar attribute value of the adjacent corner in the coarser mesh and the fine scalar attribute value of the subset in the finer mesh, and for specifying third scalar attributes of a remainder of the second group of corners of the geomorph not in the subset as having constant values equal to the fine scalar attribute values of the remainder of the second group of corners in the fine mesh.

12. A system for controlling display of computer graphics views of a multi-dimensional geometric object at a variable level of detail, comprising:

a computer readable data storage medium for storing a progressive resolution meshes representation of the multi-dimensional geometric object as a base mesh and a sequence of mesh refinement transformations, the mesh refinement transformations being complete, the progressive resolution meshes representation defining a succession of meshes at progressive levels of detail;

a detail user interface control for varying a value of a level-of-detail variable responsive to user input;

a level of detail approximator for extracting from the progressive resolution meshes a representation of the multi-dimensional geometric object at a level of detail related to the value of the level-of-detail variable; and

an image rendering and display means for producing and displaying a computer graphics view from the representation of the multi-dimensional geometric object at the level of detail.

13. The system of claim 12 wherein the mesh refinement transformations consist of vertex split transformations.

14. The system of claim 13 comprising:

a geomorphs table for storing a set of geomorphs G⁰, . . . ,G^g where each geomorph G^j is defined between a pair of meshes selected from the progressive resolution meshes representation at successive complexities T_j and T_j+1 in a set of complexities T₀, . . . , T_g+1 related to a set of complexity variables;

an interpolator for mapping the value of the level-of-detail variable to a selected one of the set of geomorphs and a selected value of a blend parameter; and

the level of detail approximator being operative to evaluate the selected geomorph at the selected value of the blend parameter to produce the representation of the multi-dimensional object at the level of detail.

15. The system of claim 14 comprising:

a complexity user interface control for varying values of the set of complexity variables responsive to user input.

16. The system of claim 15 wherein the values of the complexity variables specify a set of meshes selected from the succession of meshes according to a sequential numbering of the meshes in the succession.

17. The system of claim 15 wherein the values of the complexity variables specify a set of meshes selected from the succession of meshes according to a number of faces of the meshes in the set.

18. The system of claim 15 wherein the values of the complexity variables specify a set of meshes selected from the succession of meshes according to a number of vertices of the meshes in the set.

19. The system of claim 14 comprising:

a complexity user interface control having a sliding logarithmic scale for logarithmically varying values of the set of complexity variables responsive to user input.

20. A method of controlling display of computer graphics views of a multi-dimensional geometric object at a variable level of detail, comprising:

storing a progressive resolution meshes representation of the multi-dimensional geometric object in a computer memory as a base mesh and a sequence of mesh refinement transformations, the mesh refinement transformations being complete, the progressive resolution meshes representation defining a succession of meshes at progressive levels of detail;

setting a value of a level-of-detail variable responsive to user input;

extracting from the progressive resolution meshes a representation of the multi-dimensional geometric object at a level of detail related to the value of the level-of-detail variable;

rendering a computer graphics view of the representation of the multi-dimensional geometric object at the level of detail; and

visually displaying the computer graphics view.

21. The method of claim 20 further comprising:

iteratively repeating the steps of setting, extracting, rendering and visually displaying for different values of the level-of-detail variable.

22. The method of claim 20 further comprising:

constructing a set of geomorphs G⁰, . . . , G^g where each geomorph G^j is defined between a pair of meshes selected from the progressive resolution meshes representation at successive complexities T_j and T_j+1 in a set of complexities T₀, . . . , T_g+1 related to a set of complexity variables;

mapping the level-of-detail variable to the set of geomorphs and a blend parameter such that mapping the value of the level-of-detail variable yields a selected one of the set of geomorphs and a selected value of a blend parameter; and

evaluating the selected geomorph at the selected value of the blend parameter to produce the representation of the multi-dimensional object at the level of detail.

23. The method of claim 22 further comprising:

setting values of the set of complexity variables responsive to user input.

24. The method of claim 23 further comprising:

specifying with the values of the set of complexity variables a set of meshes selected from the succession of meshes according to a sequential numbering of the meshes in the succession.

25. The system of claim 23 further comprising:

specifying with the values of the complexity variables a set of meshes selected from the succession of meshes according to a number of faces of the meshes in the set.

26. The system of claim 23 further comprising:

specifying with the values of the complexity variables a set of meshes selected from the succession of meshes according to a number of vertices of the meshes in the set.

27. The system of claim 23 wherein the mesh refinement transformations consist of vertex split transformations.