Progressive hulls

• US 6,587,104 B1
• Filed: 09/30/1999
• Issued: 07/01/2003
• Est. Priority Date: 09/30/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hoppe, Hugues H.
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US09/409,529
• Time in Patent Office: 1,370 Days
• Field of Search: 345/418, 345/419, 345/428, 345/420, 345/424, 345/441, 345/423, 382/125, 382/126
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A progressive hull sequence is provided that approximates the outer surface geometry of a three dimensional object to be rendered. The progressive hull sequence is an adaptation of the earlier progressive mesh representation developed for level-of-detail control and progressive transmission of geometry. The progressive hull representation of an object is a sequence of lower and lower resolution mesh geometries with the property that the volume within each successive lower resolution mesh contains the volume defined by the previous higher resolution mesh. This requirement is met by ensuring that, as each edge is collapsed, each new vertex generated by the collapse is placed in the convex volume defined by the intersection of the half spaces above the face planes touching the collapsed edge. In addition, to ensure that the hull representation is as accurate as possible as edges are collapsed, it is desirable to minimize the increase in volume from hull to hull in the sequence of progressive hulls. A volume minimization constraint identifies a single point from this convex volume.

Claims

1. A computer based method for generating a sequence of data structures that model the outer surface geometry of a three dimensional object to be rendered, comprising:

(a) generating a first mesh representation of the object, wherein the first mesh comprises a first number of vertices and encloses a first volume; and

(b) generating a second mesh representation of the object, wherein the second mesh comprises a second number of vertices, the second number being less than the first number, and encloses a second volume that contains the first volume.

2. A method according to claim 1, wherein the second mesh representation of the object is generated by performing an edge collapse transformation involving a reduction of two vertices into a single new vertex.

3. A method according to claim 2, wherein the edge collapse transformation comprises:

determining a set of permissible positions for the new vertex;

selecting one of the permissible positions based on a minimization constraint; and

collapsing the edge using the selected position for the new vertex.

4. A method according to claim 3, wherein the edge is touched by a plurality of face planes, and wherein the set of permissible positions for the new vertex is based on the constraint that, as the edge is collapsed, the new vertex generated by the collapse is placed in a volume defined by the intersection of the half spaces above the face planes touching the edge.

5. A method according to claim 3, wherein the minimization constraint comprises minimizing the increase in volume between the second volume and the first volume.

6. A method according to claim 1, further comprising performing a plurality of iterations of the steps (a) and (b) until the second mesh representation has a predetermined level-of-detail.

7. A method according to claim 1, further comprising:

choosing a level-of-detail; and

performing a plurality of iterations of the steps (a) and (b) until the second mesh representation has the chosen level-of-detail.

8. A computer based system for generating a sequence of data structures that model the outer surface geometry of a three-dimensional object to be rendered, the system comprising:

a data store for storing data representative of the outer surface geometry of the three-dimensional object; and

a processor for reading the data store, generating a first mesh representation of the object using the data representative of the outer surface geometry of the three dimensional object, wherein the first mesh comprises a first number of vertices and encloses a first volume, and generating a second mesh representation of the object, wherein the second mesh comprises a second number of vertices, the second number being less than the first number, and encloses a second volume that contains the first volume.

9. A system according to claim 8, wherein the processor generates the second mesh representation of the object by performing an edge collapse transformation involving a reduction of two vertices into a single new vertex.

10. A system according to claim 9, wherein the processor performs the edge collapse transformation by determining a set of permissible positions for the new vertex, selecting one of the permissible positions based on a minimization constraint, and collapsing the edge using the selected position for the new vertex.

11. A system according to claim 10, wherein the edge is touched by a plurality of face planes, and wherein the set of permissible positions for the new vertex is based on the constraint that, as the edge is collapsed, the new vertex generated by the collapse is placed in a volume defined by the intersection of the half spaces above the face planes touching the edge.

12. A system according to claim 10, wherein the processor minimizes the increase in volume between the second volume and the first volume as the minimization constraint.

13. A system according to claim 8, wherein the processor performs a plurality of iterations generating additional mesh representations of the object, each additional mesh representation having a volume enclosing the volume of the previous mesh representation, until one of the additional mesh representations has a predetermined level-of-detail.

14. A system according to claim 8, further comprising:

a user interface for choosing a level-of-detail,

wherein the processor performs a plurality of iterations generating additional mesh representations of the object, each additional mesh representation having a volume enclosing the volume of the previous mesh representation, until the current additional mesh representation has the chosen level-of-detail.

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

a base mesh record for specifying a base mesh representation of the object at a lowest level-of-detail and a highest volume; and

a plurality of mesh records for specifying an associated plurality of mesh representations of the object at progressively higher levels-of-detail and at progressively lower volumes;

wherein each mesh encompasses the meshes having a higher resolution than itself.

16. A computer readable data storage medium according to claim 15, further comprising edge collapse transformation data indicative of reductions of vertices between successive mesh representations.

17. A computer readable medium having stored thereon a data structure, comprising:

a first data field containing base mesh data for specifying a base mesh representation of a multi-dimensional object for computer graphics at a lowest level-of-detail and a highest volume; and

a plurality of data fields containing associated mesh data for specifying an associated plurality of mesh representations of the object at progressively higher levels of detail and at progressively lower volumes;

wherein each mesh encompasses the meshes having a higher resolution than itself.

18. A computer readable medium according to claim 17, further comprising a transformation data field containing edge collapse transformation data indicative of reductions of vertices between successive mesh representations.

19. A progressive hull data structure stored in a computer readable medium that approximates an outer surface geometry of a three-dimensional object to be rendered in a computer graphics system, wherein the progressive hull data structure comprises data defining a sequence of lower and lower resolution mesh geometries, each enclosing a volume, with the property that the volume within each successive lower resolution mesh contains the volume defined by the previous higher resolution mesh.

20. A progressive hull data structure as recited in claim 19, wherein each successive lower resolution mesh is distinguished from the previous higher resolution mesh by an edge collapse transformation and a new vertex generated by the edge collapse transformation, wherein-the new vertex is placed in a volume defined by an intersection of half spaces above face planes touching the collapsed edge.