Selective refinement of progressive meshes

• US 6,046,744 A
• Filed: 02/07/1997
• Issued: 04/04/2000
• 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): Nguyen, Phu K.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US08/797,781
• Time in Patent Office: 1,152 Days
• Field of Search: 395/119, 395/125, 395/127, 395/128, 395/129, 395/130
• 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. A method of displaying selectively refined computer graphics views of a multi-dimensional object represented in a progressive resolution data structure having a base mesh record and a stream of mesh refinement records, the base mesh record defining a base mesh representative of the object at a low level of detail, the mesh refinement records defining a sequence of mesh refinement transformations for refining the base mesh into an arbitrary mesh representative of the object at a high level of detail, the mesh refinement transformations being complete, the method comprising:

forming a selectively refined mesh at an initial coarse level of detail from the base mesh record;

for each of a plurality of the mesh refinement records in the stream, performing the steps of;

(a) checking whether the mesh refinement transformation defined by the mesh refinement record meets a selection criteria for limiting refinement to a desired portion of the object; and

(b) if the mesh refinement transformation defined by the mesh refinement record meets the selection criteria, applying such mesh refinement transformation to the selectively refined mesh and thereby increasing the level of detail of the selectively refined mesh in the desired portion of the object; and

rendering and displaying a computer graphics view of the object based on the selectively refined mesh.

2. The method of claim 1 wherein the mesh refinement transformations are vertex split transformations, each of which modify a split vertex having two side vertices to introduce a new vertex and at least one new face.

3. The method of claim 2 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises:

checking whether the split vertex and the two side vertices are present in the selectively refined mesh; and

checking whether the split vertex is within the desired portion of the object.

4. The method of claim 2 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises:

checking whether closest living ancestors of the two side vertices are adjacent to the split vertex in the selectively refined mesh; and

checking whether the split vertex is within the desired portion of the object.

5. The method of claim 2 wherein the computer graphics view is a view of a portion of the object within a view frustrum, and the selection criteria limits refinement to the portion of the object within the view frustrum.

6. The method of claim 5 comprising:

determining that a mesh refinement transformation meets the selection criteria if both the split vertex and the two side vertices are all present in the selectively refined mesh, and the split vertex is within the view frustrum.

7. The method of claim 5 comprising:

determining that a mesh refinement transformation meets the selection criteria if both the split vertex is adjacent to closest living ancestor vertices of the two side vertices in the selectively refined mesh, and the split vertex is within the view frustrum.

8. The method of claim 5 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises:

checking whether any of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex are within the view frustrum.

9. The method of claim 5 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises:

calculating a signed projected screen area of each of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex, the signed projected screen area of each face having a sign and a magnitude; and

checking whether the faces all have signed projected screen areas with equal signs.

10. The method of claim 5 wherein the step of checking whether the mesh refinement transformation meets the selection criteria comprises:

calculating a signed projected screen area of each of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex, the signed projected screen area of each face having a sign and a magnitude; and

checking whether a sum of the signed projected screen areas of the faces is greater than a predetermined screen area threshold.

11. The method of claim 5 comprising:

determining that a mesh refinement transformation does not meet the selection criteria if the mesh refinement transformation modifies a portion of the selectively refined mesh within the view frustrum, but not visible in the computer graphics view.

12. The method of claim 5 comprising:

constructing a geomorph for interpolating between two levels of detail of the selectively refined mesh according to a blend parameter;

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

rendering and displaying computer graphics views of the object based on the geomorph evaluated at the values whereby the computer graphics views form a smooth visual transition between the two levels of detail.

13. A computer graphics system for displaying selectively refined views of a multi-dimensional object, comprising:

a data storage memory for storing a progressive resolution data structure having a base mesh record and a stream of mesh refinement records, the base mesh record defining a base mesh representative of the object at a low level of detail, the mesh refinement records defining a sequence of mesh refinement transformations for refining the base mesh into an arbitrary mesh representative of the object at a high level of detail, the mesh refinement transformations being complete;

a selective refinement processor for forming a selectively refined mesh at an initial coarse level of detail from the base mesh record, for checking whether the mesh refinement transformation defined by each of a plurality of the mesh refinement records in the stream meets a selection criteria for limiting refinement to a desired portion of the object, and applying those of the mesh refinement transformations that meet the selection criteria to the selectively refined mesh thereby increasing the level of detail of the selectively refined mesh in the desired portion of the object;

a graphics engine for rendering a computer graphics view of the object based on the selectively refined mesh; and

a display device for displaying the computer graphics view.

14. The computer graphics system of claim 13 wherein the mesh refinement transformations are vertex split transformations, each of which modify a split vertex having two side vertices to introduce a new vertex and at least one new face.

15. The computer graphics system of claim 14 wherein the selection criteria comprises the condition that the split vertex and the two side vertices are present in the selectively refined mesh.

16. The computer graphics system of claim 14 wherein the selection criteria comprises the condition that the split vertex is within the desired portion of the object.

17. The computer graphics system of claim 14 wherein the selection criteria comprises the condition that closest living ancestors of the two side vertices are adjacent to the split vertex in the selectively refined mesh.

18. The computer graphics system of claim 14 wherein the computer graphics view is a view of a portion of the object within a view frustrum, and the selection criteria limits refinement to the portion of the object within the view frustrum.

19. The computer graphics system of claim 18 wherein the selection criteria comprises the condition that the split vertex is within the view frustrum.

20. The computer graphics system of claim 18 wherein the selection criteria comprises the condition that any of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex are within the view frustrum.

21. The computer graphics system of claim 18 wherein the selection criteria comprises the condition that a signed projected screen area of each of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex all have equal signs.

22. The computer graphics system of claim 18 wherein the selection criteria comprises the condition that a sum of signed projected screen areas of a plurality of faces of the selectively refined mesh that are adjacent to the split vertex is greater than a predetermined screen area threshold.

23. The computer graphics system of claim 18 wherein the selection criteria comprises the condition that the mesh refinement transformation modifies a portion of the selectively refined mesh that is visible in the computer graphics view.

24. The computer graphics system of claim 13 comprising:

a geomorph processor for constructing a geomorph which interpolates between two levels of detail of the selectively refined mesh according to a blend parameter, and for evaluating the geomorph at a plurality of values of the blend parameter; and

the graphics engine rendering computer graphics views of the object based on the geomorph evaluated at the values for a smooth visual transition between the two levels of detail.