System and method for creating bounding volume hierarchies utilizing model simplification

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.