Patent ID: 6747651
Filing Date: 2004-06-08
Classification: G06T

Abstract:
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.