Method and system for adaptive refinement of progressive meshes

• US 6,137,492 A
• Filed: 04/03/1997
• Issued: 10/24/2000
• Est. Priority Date: 04/03/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hoppe, Hugues H.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US08/826,573
• Time in Patent Office: 1,300 Days
• Field of Search: 345/420, 345/423, 345/418, 345/419, 345/441, 345/433, 345/442, 364/578
• 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 2210/36 Level of detail

Abstract

A general method and system for adaptively refining an arbitrary progressive mesh representation for a graphical geometric model is presented. A real-time method for adaptively refining and coarsening the mesh according to a set of selective refinement criteria method is presented. The adaptive refinement method uses a constrained set of mesh transformations, and a set of selective refinement criteria to approximate a graphical object. The adaptive refinement method can be used to exploit view coherence, and can be used with non-view dependent parameters. For continuous changes in the parameters used in the set of selective refinement criteria, the adaptive refinement method can be amortized over consecutive frames, and smooth visual transitions (geomorphs) can be constructed between any two adaptively refined meshes used to represent a graphical object or image.

Claims

1. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

constructing a current mesh model of the object, the current mesh model defining a surface of interconnected polygons;

in a plurality of iterative traverses over a plurality of localities on the current mesh model, determining whether to apply a localized mesh refinement transformation or mesh coarsening transformation at individual such localities according to a set of selective refinement criteria and a set of transformation constraints, so as to thereby adaptively selectively refine the current mesh model; and

producing computer graphics images according to viewing parameters using the adaptively selectively refined current mesh model;

wherein the selective refinement criteria comprise a time-variant parameter that defines movement of a light source about the object.

3. The method of claim 1 wherein the localized mesh refinement transformation is a vertex split that replaces a vertex having a set of four neighboring polygonal faces with two resulting vertices and adds two polygonal faces between and adjacent to the four neighboring polygonal faces, and the transformation constraints on the localized mesh refinement transformation comprise that the vertex and the set of four neighboring polygonal faces are currently in the current mesh model.

4. The method of claim 1 wherein the localized mesh coarsening transformation is an edge collapse that replaces two vertices adjacent along an edge between two polygonal faces having a set of four neighboring polygonal faces, and the transformation constraints on the localized mesh coarsening transformation comprise that the two vertices, the two polygonal faces and the set of four neighboring polygonal faces are currently in the current mesh model.

5. The method of claim 1 wherein the viewing parameters comprise a viewing frustum, and wherein the selective refinement criteria further comprise that a region of the current mesh model affected by a mesh refinement transformation applied at a respective locality is within the viewing frustum.

6. The method of claim 1 wherein the viewing parameters comprise a view point relative to the current mesh model, and wherein the selective refinement criteria further comprise that the surface of the current mesh model at a respective locality is oriented away from the view point.

7. The method of claim 1 wherein the viewing parameters comprise a view screen projection, and wherein the selective refinement criteria further comprise that a screen space geometric error introduced by a mesh refinement transformation at a neighborhood of a respective locality is less than a tolerance.

8. The method of claim 1 wherein the viewing parameters comprise a view screen projection, and wherein the selective refinement criteria further comprise that a space on the view screen projection of a deviation of a neighborhood at a respective locality which is introduced by a mesh refinement transformation is less than a tolerance.

9. The method of claim 1 wherein the viewing parameters comprise a viewing frustum, a view point relative to the current mesh model, and a view screen projection;

and

wherein the selective refinement criteria further comprise that a region of the current mesh model affected by a mesh refinement transformation applied at a respective locality is within the viewing frustum, that the surface of the current mesh model at the respective locality is oriented away from the view point, and that a screen space geometric error introduced by a mesh refinement transformation at a respective locality is less than a tolerance.

10. A computer-readable data storage medium having computer-executable program code stored thereon operative to perform the method of claim 1 when executed on a computer.

11. A computer system programmed to perform the method of claim 1.

2. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

constructing a current mesh model of the object, the current mesh model defining a surface of interconnected polygons;

in a plurality of iterative traverses over a plurality of localities on the current mesh model, determining whether to apply a localized mesh refinement transformation or mesh coarsening transformation at individual such localities according to a set of selective refinement criteria and a set of transformation constraints, so as to thereby adaptively selectively refine the current mesh model; and

producing computer graphics images according to viewing parameters using the adaptively selectively refined current mesh model;

wherein the selective refinement criteria comprise a surface-focused parameter that defines a temperature variation over the surface.

12. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

generating a progressive mesh representation of a mesh data model of the object by selecting coarsening mesh transformations according to a geometry optimizing metric, the mesh data model defining a surface of interconnected polygons having arbitrary connectivity, the progressive mesh representation comprising a base mesh and a sequence of mesh refinement transformations, where the base mesh results from the coarsening mesh transformations and where the sequence of mesh refinement transformations exactly reconstruct the mesh data model when applied to the base mesh;

constructing a vertex hierarchy having a plurality of nodes in parent-child relationships from the progressive mesh representation in a top-down fashion from base mesh to the mesh data model, wherein a root node subset of the nodes represent the vertices of the base mesh of the progressive mesh representation, wherein the parent-child relationships between nodes are defined by the sequence of mesh refinement transformations, and wherein a leaf node subset of the nodes represent the vertices of the mesh data model;

constructing a current mesh from the base mesh and mesh refinement transformations selected from the sequence, such that the current mesh has a plurality of vertices defined by a vertex front across the vertex hierarchy;

in a plurality of iterative traverses of the vertices in the vertex front, determining whether to coarsen or refine the current mesh at individual such vertices by respectively applying the mesh refinement transformation that defines the relationship of such vertex to its children in the vertex hierarchy or a reverse of the mesh refinement transformation that defines the relationship of such vertex to its parent in the vertex hierarchy, and adjusting the vertex front in accordance with the applied transformations, so as to thereby adaptively selectively refine the current mesh; and

producing computer graphics images using the adaptively selectively refined current mesh.

13. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh comprises determining not to refine the current mesh at a vertex if a region of the current mesh affected by further refinement of such vertex overlaps a viewing frustum.

14. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh comprises determining not to refine the current mesh at a vertex if such vertex lies on a surface of the current mesh that is oriented away from a point of view of an image to be rendered of the object.

15. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh comprises determining not to refine the current mesh at a vertex if a screen space geometric error introduced by such refinement is less than a tolerance.

16. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh comprises determining not to refine the current mesh at a vertex if a screen space projection of a deviation of a neighborhood about such vertex that is introduced by such refinement is less than a tolerance.

17. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh comprises determining to refine the current mesh at a vertex if a region of the current mesh affected by further refinement of such vertex overlaps a viewing frustum, such vertex lies on a surface of the mesh that is not oriented away from a point of view, and a screen-space geometric error introduced by such refinement is greater than a tolerance.

18. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on a vertex split transformation that replaces the vertex having a set of four neighboring polygonal faces with two resulting vertices and adds two polygonal faces between and adjacent to the four neighboring polygonal faces, where the constraint is that the vertex and the set of four neighboring polygonal faces are currently in the current mesh.

19. The method of claim 12 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on an edge collapse transformation that replaces two vertices adjacent along an edge between two polygonal faces having a set of four neighboring polygonal faces, where the constraint is that the two vertices, the two polygonal faces and the set of four neighboring polygonal faces are currently in the current mesh.

20. A computer-readable data storage medium having computer-executable program code stored thereon operative to perform the method of claim 12 when executed on a computer.

21. A computer system programmed to perform the method of claim 12.

22. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

constructing a vertex hierarchy having a plurality of nodes in parent-child relationships, wherein a root node subset of the nodes represent the vertices of a base mesh, wherein the parent-child relationships between nodes are defined by a plurality of mesh refinement transformations, and wherein a leaf node subset of the nodes represent the vertices of a mesh data model of the object;

constructing a current mesh from the base mesh and selected of the mesh refinement transformations, such that the current mesh has a plurality of vertices defined by a vertex front across the vertex hierarchy;

in a plurality of iterative traverses of the vertices in the vertex front, determining whether to coarsen or refine the current mesh at individual such vertices by respectively applying the mesh refinement transformation that defines the relationship of such vertex to its children in the vertex hierarchy or a reverse of the mesh refinement transformation that defines the relationship of such vertex to its parent in the vertex hierarchy, and adjusting the vertex front in accordance with the applied transformations, so as to thereby adaptively selectively refine the current mesh;

wherein the step of determining whether to coarsen or refine the current mesh comprises determining not to refine the current mesh at a vertex if a region of the current mesh affected by further refinement of such vertex overlaps a viewing frustum; and

producing computer graphics images using the adaptively selectively refined current mesh.

23. The method of claim 22 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on a vertex split transformation that replaces the vertex having a set of four neighboring polygonal faces with two resulting vertices and adds two polygonal faces between and adjacent to the four neighboring polygonal faces, where the constraint is that the vertex and the set of four neighboring polygonal faces are currently in the current mesh.

24. The method of claim 22 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on an edge collapse transformation that replaces two vertices adjacent along an edge between two polygonal faces having a set of four neighboring polygonal faces, where the constraint is that the two vertices, the two polygonal faces and the set of four neighboring polygonal faces are currently in the current mesh.

25. A computer-readable data storage medium having computer-executable program code stored thereon operative to perform the method of claim 22 when executed on a computer.

26. A computer system programmed to perform the method of claim 22.

27. The method of claim 22 further comprising determining whether the vertex is within the view frustum according to the steps of:

determining a first bounding element that bounds a second set of vertices adjacent to a first set of vertices in the vertex hierarchy;

performing a traversal of the vertex hierarchy and determining a second bounding element that bounds the first bounding element;

determining a third bounding element centered at the vertex that bounds the second bounding element, the third bounding element having one or more bounding element components; and

determining whether selected ones of the bounding components of the third bounding element centered at the vertex lie outside the view frustum.

28. The method of claim 27 wherein the bounding element s are a set of one or more spheres S_v with radii R_v.

29. The method of claim 27 wherein the traversal of the vertex hierarchy is a postorder traversal.

30. The method of claim 27 wherein the view frustum is a four-sided pyramid, the method further comprising:

determining whether a sphere of a radius r_vi for the third bounding element centered at the vertex lies outside the view frustum, where the vertex is defined as V={v_x, v_y, v_z }, if;

space="preserve" listing-type="equation">a.sub.i v.sub.x +b.sub.i v.sub.y +c.sub.i v.sub.z +d.sub.i <

(-r.sub.vi) for i={1 . . . 4}

where the linear functions a_i v_x +b_i v_y +c_i v_z +d_i measure a signed Euclidean distance to a side of the view frustum from the vertex.

31. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

constructing a vertex hierarchy having a plurality of nodes in parent-child relationships, wherein a root node subset of the nodes represent the vertices of a base mesh, wherein the parent-child relationships between nodes are defined by a plurality of mesh refinement transformations, and wherein a leaf node subset of the nodes represent the vertices of a mesh data model of the object;

constructing a current mesh from the base mesh and selected of the mesh refinement transformations, such that the current mesh has a plurality of vertices defined by a vertex front across the vertex hierarchy;

in a plurality of iterative traverses of the vertices in the vertex front, determining whether to coarsen or refine the current mesh at individual such vertices by respectively applying the mesh refinement transformation that defines the relationship of such vertex to its children in the vertex hierarchy or a reverse of the mesh refinement transformation that defines the relationship of such vertex to its parent in the vertex hierarchy, and adjusting the vertex front in accordance with the applied transformations, so as to thereby adaptively selectively refine the current mesh;

wherein the step of determining whether to coarsen or refine the current mesh comprising determining not to refine the current mesh at a vertex if such vertex lies on a surface of the current mesh that is oriented away from a point of view of an image to be rendered of the object; and

producing computer graphics images using the adaptively selectively refined current mesh.

32. The method of claim 31 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on a vertex split transformation that replaces the vertex having a set of four neighboring polygonal faces with two resulting vertices and adds two polygonal faces between and adjacent to the four neighboring polygonal faces, where the constraint is that the vertex and the set of four neighboring polygonal faces are currently in the current mesh.

33. The method of claim 31 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on an edge collapse transformation that replaces two vertices adjacent along an edge between two polygonal faces having a set of four neighboring polygonal faces, where the constraint is that the two vertices, the two polygonal faces and the set of four neighboring polygonal faces are currently in the current mesh.

34. A computer-readable data storage medium having computer-executable program code stored thereon operative to perform the method of claim 31 when executed on a computer.

35. A computer system programmed to perform the method of claim 31.

36. The method of claim 31 further comprising determining whether said vertex lies on the surface of the current mesh that is oriented away from the point of view of the image to be rendered of the object according to the steps of:

determining a first bounding element that bounds an associated space of normals for a set of normals for faces associated with the vertex;

computing a semiangle of a cone about a normal vector for the vertex that bounds the intersection of the first bounding element and a unit sphere; and

determining with a backfacing test whether the point of view lies in a backfacing region of the vertex.

37. The method of claim 36 wherein the backfacing test includes:

(a) determining if (v-e)·

n_vi >

O, and if so;

(b) determining if ((v-e)·

n_v)² >

||v-e||² sin² α

_v, and if not, concluding that vertex does not lie in a backfacing region of the viewpoint, where v is the vertex, e is the point of view, and n_v is a normal vector to the vertex.

38. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

constructing a vertex hierarchy having a plurality of nodes in parent-child relationships, wherein a root node subset of the nodes represent the vertices of a base mesh, wherein the parent-child relationships between nodes are defined by a plurality of mesh refinement transformations, and wherein a leaf node subset of the nodes represent the vertices of a mesh data model of the object;

constructing a current mesh from the base mesh and selected of the mesh refinement transformations, such that the current mesh has a plurality of vertices defined by a vertex front across the vertex hierarchy;

in a plurality of iterative traverses of the vertices in the vertex front, determining whether to coarsen or refine the current mesh at individual such vertices by respectively applying the mesh refinement transformation that defines the relationship of such vertex to its children in the vertx hierarchy or a reverse of the mesh refinement transformation that defines the relationship of such vertex to its parent in the vertex hierarchy, and adjusting the vertex front in accordance with the applied transformations, so as to thereby adaptively selectively refine the current mesh;

wherein the step of determining whether to coarsen or refine the current mesh comprises determining not to define the current mesh at a vertex if a screen space geometric error introduced by such refinement is less than a tolerance; and

producing computer graphics images using the adaptively selectively refined current mesh.

39. The method of claim 38 wherein the screen space geometric error is determined to be less than the tolerance if a screen space projection of a deviation of a neighborhood about such vertex that is introduced by such refinement is less than the tolerance.

40. The method of claim 38 wherein the step of determining whether to coarsen or refine-the current mesh at a vertex comprises checking a constraint on a vertex split transformation that replaces the vertex having a set of four neighboring polygonal faces with two resulting vertices and adds two polygonal faces between and adjacent to the four neighboring polygonal faces, where the constraint is that the vertex and the set of four neighboring polygonal faces are currently in the current mesh.

41. The method of claim 38 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on an edge collapse transformation that replaces two vertices adjacent along an edge between two polygonal faces having a set of four neighboring polygonal faces, where the constraint is that the two vertices, the two polygonal faces and the set of four neighboring polygonal faces are currently in the current mesh.

42. A computer-readable data storage medium having computer-executable program code stored thereon operative to perform the method of claim 38 when executed on a computer.

43. A computer system programmed to perform the method of claim 38.

44. The method of claim 38 further comprising determining whether the screen space geometric error introduced by said refinement is less than the tolerance according to the steps of:

determining a deviation between a first set of normal vectors for a neighborhood of faces adjacent to the vertex in the current mesh, and a second set of normal vectors for a corresponding neighborhood of faces in the mesh data model by examining a set of residual error vectors from a set of points sampled on the corresponding neighborhood that locally projects onto the first set of normal vectors;

determining a smallest deviation space D_n (μ

_v,δ

_v) with the ratio δ

_v /μ

_v that bounds the set of residual error vectors; and

determining if the smallest deviation space D_n (μ

_v,δ

_v) exceeds the pre-determined screen space tolerance.

45. The method of claim 44 wherein the step of determining if the smallest deviation space D_n (μ

_v,δ

_v) exceeds a pre-determined screen space tolerance includes determining if;

space="preserve" listing-type="equation">μ

.sup.2.sub.v >

=k.sup.2 ||v-e||.sup.2 ;

and if not, determining if;

space="preserve" listing-type="equation">δ

.sup.2.sub.v (||v-e||.sup.2 -((v-e)·

N .sub.v).sup.2)>

=k.sup.2 ||v-e||.sup.4,

and if not, concluding that the smallest deviation space D_n (μ

_v δ

_v) does not exceed the pre-determined screen space tolerance, where v is a vertex, e is a viewpoint, N _v is a set of vectors for a neighborhood, and k² is a view angle factor.

46. A method of adaptively selectively refining a variable resolution representation of an object for producing computer graphics images of the object, the method comprising:

constructing a vertex hierarchy having a plurality of nodes in parent-child relationships, wherein a root node subset of the nodes represent the vertices of a base mesh, wherein the parent-child relationships between nodes are defined by a plurality of mesh refinement transformations, and wherein a leaf node subset of the nodes represent the vertices of a mesh data model of the object;

constructing a current mesh from the base mesh and selected of the mesh refinement transformations, such that the current mesh has a plurality of vertices defined by a vertex front across the vertex hierarchy;

in a plurality of iterative traverses of the vertices in the vertex front, determining whether to coarsen or refine the current mesh at individual such vertices by respectively applying the mesh refinement transformation that defines the relationship of such vertex to its children in the vertex hierarchy or a reverse of the mesh refinement transformation that defines the relationship of such vertex to its parent in the vertex hierarchy, and adjusting the vertex front in accordance with the applied transformations, so as to thereby adaptively selectively refine the current mesh;

wherein the step of determining whether to coarsen or refine the current mesh comprises determining to refine the current mesh at a vertex if a region of the current mesh affected by further refinement of such vertex overlaps a viewing frustum, such vertex lies on a surface of the mesh that is not oriented away from a point of view, and a screen-space geometric error introduced by such refinement is greater than a tolerance; and

producing computer graphics images using the adaptively selectively refined current mesh.

47. The method of claim 46 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on a vertex split transformation that replaces the vertex having a set of four neighboring polygonal faces with two resulting vertices and adds two polygonal faces between and adjacent to the four neighboring polygonal faces, where the constraint is that the vertex and the set of four neighboring polygonal faces are currently in the current mesh.

48. The method of claim 46 wherein the step of determining whether to coarsen or refine the current mesh at a vertex comprises checking a constraint on an edge collapse transformation that replaces two vertices adjacent along an edge between two polygonal faces having a set of four neighboring polygonal faces, where the constraint is that the two vertices, the two polygonal faces and the set of four neighboring polygonal faces are currently in the current mesh.

49. A computer-readable data storage medium having computer-executable program code stored thereon operative to perform the method of claim 46 when executed on a computer.

50. A computer system programmed to perform the method of claim 46.