System and method for creating bounding volume hierarchies utilizing model simplification

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.

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.

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.