The present invention relates to a method for computer image modeling of a complex structure and, in particular, to a method for creating a spatially balanced hierarchy of bounding volumes from an arbitrary distribution of parts for use as successive approximations thereof in a graphic display.
Interactive computer generated displays provide for the visualization of realistic looking, three-dimensional models. Such models, under user control, are useful for both design evaluation and training in virtual environments, as may be found, for example, in mechanical computerized design systems. Such computer visualization systems provide images of a three-dimensional, complex structure on the screen of a computer workstation as seen from a simulated observer's viewpoint under interactive control by the user. If the computer generated display can be rendered smoothly and quickly enough, the user is provided an illusion of real-time exploration of a virtual environment under simulated observer movement through the structure.
A particular application for an interactive, computer generated visualization system of a complex structure is found in the modeling of highly complex structure, such as aircraft. Here, a system which allows the user interactive movement throughout the structure can aid in numerous aspects related to the ultimate success of the product. For example, an interactive display of a complex aircraft structure can identify interference and fit problems, provide the ability to "see" areas of the product normally hidden in a physical mock-up, design routing of ducts and wiring through crowded areas, facilitate the work of integrated product teams by providing a "live" model and reduce cycle time and cost of the production of illustrations and training media. As computer graphic based systems have matured, so have the three-dimensional model data bases that its methods were meant to display. Because real world structure contains far more complexity than can reasonably be stored on computer storage media, the complexity of models developed has traditionally exceeded the capacity of the hardware required to display it. To deal with this problem, various methods have been developed to reduce the complexity of models while attempting to effect only minor changes on the perceived complexity to the eye. These methods may be divided into two categories: culling and detail elision.
Culling is the practice of not displaying objects that are invisible from the current viewing position. Such objects are considered "culled" from the scene. Objects may be culled either from being hidden by other objects or by being outside the current viewing frustum. While culling to the viewing frustum is often straightforward, culling occluded objects can be difficult, although numerous algorithms have been devised to solve this problem. The key to culling is having a fast method of determining the visibility of all objects in a scene.
Detail elision is the practice of displaying an object at a varying level of detail (LOD) depending on the object's importance to the perceived complexity of the scene. This perceived importance has traditionally been measured by the size of the object in screen picture elements (pixels). The key to using detail elision is to have several levels of detail available for all complex objects in the scene.
The use of bounding volume hierarchies is not new to computer graphics. The most common use is in the simplification of a variety of intersection problems, e.g., intersection with a viewing frustum for culling, intersection with other objects for collision detection, and intersection with rays for ray tracing.
A number of published methods are known in the art for generating a bounding volume hierarchy. One simple method is to have the bounding volume match the modeling hierarchy. Methods which do not depend on a known modeling hierarchy include a median-cut scheme which creates a binary tree based sorting by x, y, and z coordinates of objects, and an octree scheme which groups objects based on their clustering in octants.
None of the known methods in the an are capable of deriving a tight, well-balanced bounding volume hierarchy from an arbitrary ordering of objects. There is no useful modeling hierarchy known to the art because of the arbitrary ordering. Median-cut schemes work only with one dimension at a time, and therefore objects that are close in space may be distant from each other in the tree. An octree scheme holds promise, but does not provide a tight bounding volume for objects centered at octant boundaries, and leaves choosing which octants go together unspecified.