Progressive hulls
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
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. - View Dependent Claims (16)
-
-
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. - View Dependent Claims (18)
-
- 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.
Specification