System and method for creating bounding volume hierarchies utilizing model simplification

• US 6,747,651 B1
• Filed: 04/04/2001
• Issued: 06/08/2004
• Est. Priority Date: 07/18/1998
• Status: Expired due to Term

• Current Assignee: National University of Singapore
• Original Assignee: National University of Singapore
• Inventors: Chong, Ket Fah, Low, Kok Lim, Tan, Tiow Seng
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): NGUYEN, KIMBINH T
• Application Number:
  US09/743,921
• Time in Patent Office: 1,161 Days
• Field of Search: 345/420, 345/423, 345/426, 345/440
• US Class Current: 345/474
• CPC Class Codes: G06T 15/50 Lighting effects
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

This invention integrates model simplification and bounding volume hierarchy construction for collision detection in interactive 3D graphics. In particular, it provides general framework and a preferred method to construct bounding volume hierarchy using outputs of model simplification. Simplified models, besides their application to multi-resolution rendering, can provide clues to the shape of the input object. These clues help in the partitioning of the object'"'"'s model into components that may be more tightly bounded by simple bounding volumes. The framework and method naturally employ both the bottom-up and the top-down approaches of hierarchy building, and thus can have the advantages of both approaches. The framework and method includes the steps of simplified models generation, component derivation, component tree generation, and bounding volume hierarchy generation. The operation of the method includes the steps of interactively computing, displaying and recording simplified models and bounding volume hierarchy in response to user commands. Ray tracing and collision detection may be efficiently performed using the bounding volume hierarchy generated by the invention.

Claims

1. A computer implemented method for successively approximating a collection of objects with a hierarchy of bounding volumes, from a root volume bounding all objects, to sub-volumes bounding individual objects or assemblies thereof, comprising:

inputting an original model approximating the objects;

generating one or more simplified models from the original model with each simplified model having fewer faces and vertices than the original model;

deriving sub-components of the objects using clues from the simplified models;

connecting the sub-components into a component hierarchy;

assigning the component hierarchy as a top few levels of the bounding volume hierarchy;

subdividing parts of the objects in each sub-component that are leaves in the component hierarchy into remaining levels of the bounding volume hierarchy; and

configuring a memory device to embody the bounding volume hierarchy,

wherein said step of deriving sub-components from the simplified models includes the substep of;

forming a sub-component from each of the parts consisting of all triangles of the original model simplified to elements in that part, the step of forming sub-components being repeated to further divide the sub-components into smaller sub-components using simplified models that are more detailed than that used to obtain the sub-component.

2. The method as set forth in claim 1, said generating step iteratively generating simplified models.

3. The method as set forth in claim 1, said generating step including the substeps of:

analyzing a frequency distribution of measurements of the objects to generate a plurality of clustering cell widths; and

using the clustering cell widths to apply floating-cell clustering to generate the simplified models.

4. The method as set forth in claim 3, said analyzing substep analyzing the frequency distribution of edge lengths where each edge is counted only once.

5. The method as set forth in claim 3, said analyzing substep analyzing the frequency distribution of edge lengths where each edge is counted for each of the objects containing this edge.

6. The method as set forth in claim 1, said generating step including the substeps of:

generating error tolerant measures of the simplified models; and

applying a simplification algorithm using the error tolerant measures to generate the simplified models.

7. The method as set forth in claim 1, said deriving step deriving sub-components from the simplified model including the substep of:

partitioning a set of triangles, a set of edges, and a set of points of the simplified model into parts.

8. The method as set forth in claim 7, wherein S consists of the set of triangles S₃, the set of edges S₂, and the set of points S₁,

said partitioning step partitions S into parts including the substeps of:

forming parts from S₃ incorporating some S₂ and S₁;

forming parts from remaining S₂ incorporating some S₁;

then

forming parts from remaining S₁.

9. The method as set forth in claim 8, wherein said substep of forming parts from S₃ incorporating some S₂ and S₁ includes:

forming a new part with a triangle in S₃ that has not been assigned to any part,

putting individual triangles that have not been assigned to any part into the new part if the individual triangle shares an edge with any triangle in the part;

including into the part edges in S₂, which are also edges of triangles in the part;

including into the part isolated edges in S₂ having both endpoints incident to some triangles in the part;

including into the part a vertex incident to some triangles in the part and not any other triangles not in the part; and

repeating the forming, putting and including steps when there are still unassigned triangles in S₃.

10. The method as set forth in claim 8, wherein said substep of forming parts from remaining S₂ incorporating some S₁ includes:

forming a new part with an edge in S₂ that has not been assigned to any part;

including into the part each endpoint of the edge if the endpoint is not also an endpoint of any other edge or triangle in S; and

repeating the forming and including substeps when there are still unassigned edges in S₂.

11. The method as set forth in claim 8, wherein said step of forming parts from remaining S₁ forms a part for each remaining point in S₁.

12. The method as set forth in claim 11, further comprising:

not forming a new part with points that are incident by existing parts; and

distributing triangles of the original model simplified to the points to parts by utilizing a spatial partitioning scheme.

13. The method as set forth in claim 1, wherein said step of connecting sub-components into a component hierarchy includes top-down spatial partitioning of sub-components into a component hierarchy tree with a low degree.

14. The method as set forth in claim 1, wherein the step of connecting sub-components into a component hierarchy includes bottom-up merging of all sub-components of each sub-component into a component hierarchy tree with a low degree.

15. The method as set forth in claim 14 further including the step of using either a minimum area, a minimum volume, a number of triangles, a percentage of area or a percentage of volume, in deciding the merging of two sub-components into a bigger sub-component.

16. The method as set forth in claim 1, wherein the step of subdividing objects in each sub-component that are leaves in the component hierarchy includes top-down spatial partitioning of objects into a balanced bounding volume tree.

17. A machine having the memory device which embodies data representing the bounding volume hierarchy generated by the method of claim 1.

18. The method as set forth in claim 1, further comprising:

performing ray tracing by utilizing the bounding volume hierarchy.

19. The method as set forth in claim 1, further comprising:

performing collision detection between at least two of the objects by utilizing the bounding volume hierarchy.

20. An apparatus for successively approximating a collection of objects with a hierarchy of bounding volumes, from a root volume bounding all objects, to sub-volumes bounding individual objects or assemblies thereof, comprising:

means for inputting an original model approximating the objects;

means for generating one or more simplified models from the original model with each simplified model having fewer faces and vertices than the original model;

means for deriving sub-components of the objects using clues from the simplified models;

means for connecting the sub-components into a component hierarchy;

means for assigning the component hierarchy as a top few levels of the bounding volume hierarchy; and

means for subdividing parts of the objects in each sub-component that are leaves in the component hierarchy into remaining levels of the bounding volume hierarchy,

wherein said means for deriving sub-components from the simplified models includes;

means for forming a sub-component from each of the parts consisting of all triangles of the original model simplified to elements in that part, and means for further repeatedly dividing the sub-components into smaller sub-components using simplified models that are more detailed than that used to obtain the sub-component.

21. A computer implemented method for generating a bounding volume hierarchy data structure approximating a collection of objects, comprising:

inputting an original model approximating the objects;

generating one or more simplified models from the original model with each simplified model having fewer faces and vertices than the original model;

deriving sub-components of the objects using clues from the simplified models;

connecting the sub-components into a component hierarchy;

assigning the component hierarchy as a top few levels of the bounding volume hierarchy;

subdividing parts of the objects in each sub-component that are leaves in the component hierarchy into remaining levels of the bounding volume hierarchy; and

configuring a memory device to embody the bounding volume hierarchy data structure,

wherein said step of deriving sub-components from the simplified models includes the substep of;

forming a sub-component from each of the parts consisting of all triangles of the original model simplified to elements in that part, the step of forming sub-components being repeated to further divide the sub-components into smaller sub-components using simplified models that are more detailed than that used to obtain the sub-component.

22. An article of manufacture, comprising:

a computer-usable medium including computer-readable program code means, embodied therein, for causing a computer to generate a bounding volume hierarchy data structure approximating a collection of objects, the computer-readable program code means comprising;

computer-readable program code means for inputting an original model approximating the objects;

computer-readable program code means for generating one or more simplified models from the original model with each simplified model having fewer faces and vertices than the original model;

computer-readable program code means for deriving sub-components of the objects using clues from the simplified models;

computer-readable program code means for connecting the sub-components into a component hierarchy;

computer-readable program code means for assigning the component hierarchy as a top few levels of the bounding volume hierarchy; and

computer-readable program code means for subdividing parts of the objects in each sub-component that are leaves in the component hierarchy into remaining levels of the bounding volume hierarchy,

wherein said computer-readable program coed means of deriving sub-components from the simplified model includes;

means for forming a sub-component from each of the parts consisting of all triangles of the original model simplified to elements in that part and further repeatedly dividing the sub-components into smaller sub-components using simplified models that are more detailed than that used to obtain the sub-component.