Encoding and progressive transmission of progressive meshes

• US 5,963,209 A
• Filed: 01/11/1996
• Issued: 10/05/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/586,953
• Time in Patent Office: 1,363 Days
• Field of Search: 395/119, 395/120, 395/121, 395/122, 395/123, 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. A method of representing a three-dimensional geometric object with polygonal meshes at varying levels of detail for computer graphics, comprising the steps of:

specifying a base polygonal mesh having a plurality of vertices and a plurality of faces that approximates the three-dimensional geometric object at a coarse level of detail; and

specifying a sequence of sets of mesh refinement transformations which, when applied successively to the base polygonal mesh, produce a succession of polygonal meshes that approximate the three-dimensional geometric object at progressively finer levels of detail, the sets of mesh refinement transformations being complete.

2. The method of claim 1 wherein at least one of the sets of mesh refinement transformations is a vertex split transformation which, when applied to a preceding polygonal mesh in the succession, splits an ancestor vertex of the preceding polygonal mesh into two descendent vertices to produce a next polygonal mesh in the succession such that the next polygonal mesh has one more vertex and from one to two more faces than the preceding polygonal mesh.

3. The method of claim 2 wherein the step of specifying the base polygonal mesh comprises the steps of:

specifying a set of vertices; and

specifying a set of faces, where the vertices and the faces define the base polygonal mesh.

4. The method of claim 3 wherein the step of specifying the base polygonal mesh further comprises the step of:

specifying attributes on at least some of the vertices, the faces, edges defined by pairs of the vertices, and corners defined by pairs of one of the vertices with one of the faces.

5. The method of claim 2 wherein the step of specifying the base polygonal mesh comprises the steps of encoding data into a base polygonal mesh record representing a simplicial complex, a set of vertex positions, and a set of attributes;

and

the step of specifying the mesh refinement transformations comprises, for each vertex split transformation, the step of encoding data into a vertex split record specifying an ancestor vertex, a first side vertex, and a second side vertex of a preceding polygonal mesh in the sequence, and geometric positions of the ancestor vertex and a descendent vertex in a next polygonal mesh in the succession.

6. The method of claim 5 wherein the step of encoding data into the vertex split record comprises the step of:

encoding differences of the geometric positions of the ancestor vertex and the descendent vertex in the next polygonal mesh from the geometric position of the ancestor vertex in the preceding polygonal mesh into the vertex split record to thereby specify the geometric positions of the ancestor vertex and the descendent vertex in the next polygonal mesh.

7. The method of claim 5 wherein the step of encoding data into the vertex split record comprises the steps of:

assigning vertex indices uniquely to the vertices of the base polygonal mesh and the vertices introduced by the sets of mesh refinement transformations;

encoding the vertex index assigned to the ancestor vertex into the vertex split record to thereby specify the ancestor vertex;

assigning adjoining vertex indices uniquely to a set of vertices adjoining the ancestor vertex; and

encoding the adjoining vertex indices assigned to the first and second side vertices in the vertex split record to thereby specify the first and second side vertices.

8. The method of claim 5 wherein the step of encoding data into the vertex split record comprises the steps of:

encoding a control bit sequence to indicate a discrete attribute of a face introduced by the vertex split transformation, the control bit sequence having a first value if the discrete attribute is the same as a neighboring face of the preceding mesh and having a second value if the discrete attribute is different.

9. The method of claim 5 wherein the step of encoding data into the vertex split record comprises the steps of:

encoding a control bit sequence to indicate a scalar attribute of a corner introduced by the vertex split transformation, the control bit sequence having a first value if the scalar attribute is the same as a neighboring corner of the preceding mesh and having a second value if the scalar attribute is different.

10. The method of claim 1 wherein the step of specifying the sequence of sets of mesh refinement transformations comprises, for each vertex split transformation in the sequence, the steps of:

specifying an ancestor vertex and first and second side vertices out of the vertices of a preceding polygonal mesh in the succession; and

specifying geometries of two descendent vertices for a next polygonal mesh in the succession, where the ancestor vertex, the first and second side vertices and the geometries of the two descendent vertices define a vertex split transformation that, when applied to the preceding polygonal mesh, splits the ancestor vertex into the two descendent vertices and adds two new faces defined by the combination of the descendent vertices with each of the side vertices, respectively, to produce the next polygonal mesh.

11. The method of claim 10 wherein the step of specifying the sequence of mesh refinement transformations further comprises, for each vertex split transformation in the sequence, the steps of:

specifying attributes on at least some of the first and second side vertices, the new faces, edges defined by pairs out of the descendent vertices and the first and second side vertices, and corners defined by pairs of one out of the descendent vertices and the first and second side vertices with one of the new faces.

12. The method of claim 1 further comprising:

applying a subset of the sequence of sets of mesh refinement transformations to the base mesh to form a mesh having a desired level-of-detail.

13. The method of claim 1 further comprising:

applying a first subset of the sequence of set of mesh refinement transformations to the base mesh to form a coarser mesh having a first desired level-of-detail;

applying a second subset greater than the first subset of the sequence of set of mesh refinement transformations to the base mesh to form a finer mesh having a second desired level-of-detail greater than the first desired level-of-detail; and

forming a geomorph between the coarser mesh and the finer mesh.

14. The method of claim 2 further comprising:

selecting a subset of the sequence of sets of mesh refinement transformations within at least one localized area of the base mesh;

applying the subset to the base mesh to form a selectively refined mesh.

15. The method of claim 14 wherein the step of selecting the subset comprises selecting sets of the mesh refinement transformations within a view frustum.

16. The method of claim 14 wherein the step of selecting the subset comprises selecting sets of the mesh refinement transformations that are within a view frustum, and are near silhouette edges or near a viewer.

17. The method of claim 1 further comprising the steps of:

transmitting information from a first computer at a first site to a second computer at a remote site, the information specifying, in order, the base mesh and the sequence of sets of mesh refinement transformations;

receiving the information by the second computer;

displaying a view of a mesh based on the information; and

progressively refining the mesh and updating the view as the information of the sequence of sets of mesh refinement transformations is received.

18. The method of claim 17 wherein the step of progressively refining the mesh and updating the view comprises the steps of

forming a coarser mesh based on the information of the base mesh and a first subset of the sequence of sets of mesh refinement transformations received at the second computer;

displaying a view of the coarser mesh;

receiving information of a further subset of the sequence of sets of mesh refinement transformations at the second computer;

applying the further subset to the coarser mesh to form a finer mesh;

forming at least one geomorph between the coarser and the finer meshes; and

displaying a view of the at least one geomorph.

19. The method of claim 18 further comprising the steps of:

selecting a subset of the sequence of sets of mesh refinement transformations that lie within a frustum of the view being displayed at the second computer for transmission by the first computer.

20. The method of claim 1 further comprising the steps of:

modeling the three dimensional object as an original mesh;

selecting a plurality of edge collapse transformations that simplify the original mesh to a simplified mesh having a desired level-of-detail; and

selecting the simplified mesh and a sequence of vertex split transformations which is the inverse of the edge collapse transformations as the base mesh and the sequence of sets of mesh refinement transformations.

21. The method of claim 20 wherein the step of selecting the edge collapse transformations comprises selecting the edge collapse transformations according to an appearance metric for preserving a geometry of the original mesh.

22. The method of claim 21 wherein the appearance metric further preserves scalar attributes associated with the original mesh.

23. The method of claim 22 wherein the appearance metric further preserves discontinuity curves of the original mesh.

24. A computer readable data storage medium having encoded thereon a progressive meshes representation of a multi-dimensional object for computer graphics, the progressive meshes representation comprising:

a base mesh record for specifying a base mesh representative of the object at a lowest level of detail; and

a plurality of vertex split records for specifying a plurality of vertex split transformations which, when applied successively to the base mesh, yield a succession of meshes representative of the object and having progressively higher levels of detail.

25. The computer readable data storage medium of claim 24 wherein each of the vertex split records comprises:

vertex identifiers for specifying a split vertex and two side vertices of the vertex split transformation; and

vertex position identifiers for specifying position coordinates of two resultant vertices of the vertex split transformation.

26. The computer readable data storage medium of claim 25 wherein the vertex identifiers are encoded according to a predictive encoding scheme.

27. The computer readable data storage medium of claim 25 wherein the vertex position identifiers are encoded according to a variable-length delta encoding scheme.

28. The computer readable data storage medium of claim 24 wherein each of the vertex split records comprises:

attribute values for specifying attributes associated with faces and corners introduced by the vertex split transformation.

29. The computer readable data storage medium of claim 28 wherein the attribute values are encoded according to a predictive encoding scheme.

30. A method of losslessly encoding an arbitrary initial mesh at progressive levels of detail for rendering computer graphics views of a multi-dimensional geometric object, comprising:

encoding a base mesh record specifying a set of position coordinates and a connectivity of vertices of a base mesh, the position coordinates and connectivity of the vertices defining a plurality of faces having edges between adjacent vertices and corners at the vertices; and

encoding a plurality of vertex split records specifying a split vertex identifier, two side vertex identifiers, and two resulting vertex position coordinates for each of a sequence of vertex split transformations that yield a succession of meshes at progressively increasing levels of detail and exactly reproduce the arbitrary initial mesh when applied in sequence to the succession beginning with the base mesh, each vertex split transformation introducing a new vertex and at least one new face having edges between adjacent vertices and corners at the vertices to a current mesh in the succession to yield a next mesh in the succession.

31. The method of claim 30 comprising for each of the vertex split records:

encoding the two resulting vertex positions in the vertex split record as differences between the two resulting vertex positions and a vertex position of a split vertex specified by the split vertex identifier.

32. The method of claim 31 comprising:

encoding the differences according to a variable length encoding scheme.

33. The method of claim 30 comprising:

encoding the two resulting vertex positions in the vertex split record as a choice of a starting position of a split vertex specified by the split vertex identifier and differences in position between the two resulting vertex positions and the starting position, where the choice of the starting position is from a group consisting of a first of the two resulting vertex positions, a second of the two resulting vertex positions, and a mid-point between the two resulting vertex positions.

34. The method of claim 33 comprising:

encoding the differences according to at least one variable length encoding scheme.

35. The method of claim 30 comprising:

encoding the two resulting vertex positions in the vertex split record as a choice of a split vertex position and a single position difference, where the choice of the split vertex position is from a group consisting of a first of the two resulting vertex positions, a second of the two resulting vertex positions, and a mid-point between the two resulting vertex positions, and where the single position difference is a difference between the split vertex position and one of the two resulting vertex positions other than the split vertex position.

36. The method of claim 35 comprising:

encoding the single position difference according to a variable length encoding scheme.

37. The method of claim 30 comprising:

encoding the two side vertex identifiers as adjacent vertex indices specifying two side vertices out of a plurality of vertices adjacent to a split vertex specified by the split vertex identifier.

38. The method of claim 30 comprising:

encoding discrete attribute values into the base mesh record specifying discrete attributes associated with the faces; and

encoding a discrete attribute value into each vertex split record specifying a discrete attribute associated with the at least one new face introduced by the vertex split transformation of the vertex split record according to a predictive encoding scheme in which a first value specifies the discrete attribute being equal to that of an adjacent face and a second value specifies the discrete attribute being different from any adjacent face.

39. The method of claim 30 comprising:

encoding scalar attribute values into the base mesh record specifying scalar attributes associated with the corners; and

encoding a scalar attribute value into each vertex split record specifying a scalar attribute associated with a corner of the at least one new face introduced by the vertex split transformation of the vertex split record according to a predictive encoding scheme in which a first value specifies the scalar attribute being equal to that of an adjacent corner and a second value specifies the scalar attribute being different from any adjacent corner.

40. The method of claim 39 comprising:

encoding the scalar attribute value according to the predictive encoding scheme in which a difference value accompanying the second value specifies a difference in the scalar attribute between the corner of the at least one new face and the adjacent corner.

41. The method of claim 40 comprising:

encoding the difference in the scalar attribute according to a variable length encoding scheme.

42. A method of progressively transmitting a level-of-detail representation of an object from a remote site for displaying computer graphics views of the object at a computer, comprising:

transmitting a base mesh record from the remote site defining a base mesh representing the object at a low level of detail;

transmitting a stream of mesh refinement records from the remote site defining a sequence of mesh transformations for refining the base mesh into an arbitrary mesh representing the object at a high level of detail, the mesh transformations being complete;

receiving the base mesh record at a computer;

constructing a progressive resolution mesh at the computer from the base mesh record;

rendering and displaying at the computer a first computer graphics view of the object having a lower level of detail based on the progressive resolution mesh;

receiving an increment of the stream of mesh refinement records at the computer;

refining the progressive resolution mesh to a higher level of detail at the computer by applying the mesh transformations defined by the mesh refinement records of the increment; and

rendering and displaying at the computer a second computer graphics view of the object having the higher level of detail based on the progressive resolution mesh.

43. The method of claim 42 comprising:

constructing a geomorph for interpolating between the progressive resolution mesh at the lower level of detail and the progressive resolution mesh at the higher level of detail as a function of a blend parameter;

evaluating the geomorph at a sequence of intermediate values of the blend parameter that create a transition of the geomorph from the progressive resolution mesh at the lower level of detail to the progressive resolution mesh at the higher level of detail; and

rendering and displaying at the computer a sequence of computer graphics views of the object based on the geomorph evaluated at the sequence of intermediate values.

44. The method of claim 42 comprising:

storing the mesh refinement records of the stream into an input buffer at the computer as the mesh refinement records are received;

for each of a plurality of successive increments of the stream of mesh transformation records, performing the steps of;

retrieving mesh transformation records for a next increment of the stream from the input buffer for refining the progressive resolution mesh to a next higher level of detail; and

when the step of retrieving the mesh transformations temporarily empties the input buffer, updating the progressive resolution mesh and the computer graphics view being displayed based on the progressive resolution mesh with that next increment of the stream.

45. The method of claim 42 comprising:

performing the steps, for each of a plurality of further successive increments of the stream of mesh transformation records that produce respective further computer graphics views of the object at exponentially increasing levels of detail, of;

receiving the further increment of the stream of mesh refinement records at the computer;

refining the progressive resolution mesh to a next higher exponentially increasing level of detail at the computer by applying the mesh transformations defined by the mesh refinement records of the further increment; and

rendering and displaying at the computer the respective further computer graphics view of the object having the next higher exponentially increasing level of detail based on the progressive resolution mesh as refined by applying the further increment.

46. The method of claim 42 wherein the mesh refinement transformations are vertex split transformations.

47. The method of claim 46 comprising:

displaying a computer graphics view of a different portion of the object; and

selecting a subset of the mesh refinement records of the progressive resolution meshes representation for transmitting in the stream where each mesh refinement record in the subset has not already been transmitted in the stream and defines a mesh refinement transformation relating to refinement of the progressive resolution mesh in the different portion of the object.

48. The method of claim 42 comprising:

storing a progressive resolution meshes representation of the object at the remote site, the progressive resolution meshes representation comprising the base mesh record and a sequence of mesh refinement records;

displaying a computer graphics view of a portion of the object based on the progressive resolution mesh; and

selecting a subset of the mesh refinement records of the progressive resolution meshes representation for transmitting in the stream where each mesh refinement record in the subset defines a mesh refinement transformation relating to refinement of the progressive resolution mesh in the portion of the object.

49. A system for progressively transmitting a level-of detail representation of an object from a remote site for displaying computer graphics views of the object at a computer, comprising:

a memory at the remote site for storing a progressive resolution meshes representation of the object comprising a base mesh record and a sequence of vertex split records, the base mesh record defining a base mesh representative of the object at a low level of detail, the sequence of vertex split records defining vertex split transformations that applied successively to the base mesh refine the base mesh into an arbitrary mesh representative of the object at a high level of detail;

a data transmitter at the remote site for transmitting the base mesh record and a stream of the vertex split records to the computer.

50. The system of claim 49 comprising:

a selective refinement transmission processor at the remote site for selecting a subset of the vertex split records of the progressive resolution meshes representation for transmitting in the stream where each vertex split record in the subset defines a vertex split transformation relating to refinement within a portion of the object.

51. The system of claim 50 wherein the portion of the object is dependent on the computer graphics view being displayed at the computer.

52. The system of claim 51 comprising:

the selective refinement transmission processor being responsive to the computer graphics view changing to a different portion of the object for selecting a further subset of the vertex split records of the progressive resolution meshes for transmitting in the stream where each vertex split record in the further subset has not already been transmitted in the stream and defines a vertex split transformation relating to refinement of the progressive resolution mesh in the different portion of the object.

53. The system of claim 49 further comprising:

the computer for displaying the computer graphics views of the object;

a data receiver in the computer and in communication with the data transmitter of the remote site for receiving the base mesh records and the stream of vertex split records;

a progressive resolution mesh processor in the computer for constructing a progressive resolution mesh from the base mesh record and for refining the progressive resolution mesh at progressive levels of detail by applying vertex split transformations defined by successive increments of the stream of vertex split records;

a graphics rendering engine in the computer for rendering computer graphics views of the object from the progressive resolution mesh at the progressive levels of detail; and

a display driver in the computer for causing the computer to display the computer graphics views of the object.

54. The system of claim 53 comprising:

a geomorph processor in the computer for constructing a geomorph that interpolates between the progressive resolution mesh at a successive two of the progressive levels of detail as a function of a blend parameter, and for evaluating the geomorph at a sequence of intermediate values of the blend parameter that create a transition of the geomorph from the progressive resolution mesh at a lower and at a higher of the successive two of the progressive levels of detail; and

the graphics rendering engine rendering a sequence of computer graphics views of the object based on the geomorph evaluated at the sequence of intermediate values.

55. The system of claim 53 comprising:

an input buffer in the computer for storing the mesh refinement records of the stream as the vertex split records are received at the computer;

the progressive resolution mesh processor retrieving a plurality of vertex split records for each of the successive increments of the stream from the input buffer;

the computer shifting from refining the progressive resolution mesh by the progressive resolution mesh processor and rendering the computer graphics views by the graphics engine when the input buffer is emptied from retrieving the vertex split records for a current one of the successive increments of the stream whereby processing is balanced between refining the progressive resolution mesh and rendering the computer graphics views.