METHOD FOR CREATING SPATIALLY BALANCED BOUNDING VOLUME HIERARCHIES FOR USE IN A COMPUTER GENERATED DISPLAY OF A COMPLEX STRUCTURE

摘要

Disclosed is amethod for processingan arbitrary collection ofobjects, forming a complexstructure, into a hierarchyof bounding volumes,from a root volumebounding all objects, tosub-volumes boundingindividual objects orassemblies thereof,for use as successiveapproximations to saidobjects in a computergenerated display. Themethod includes the firststep of creating a boundingvolume for each of theobjects. Selected boundingvolumes are then processedthrough a combiningalgorithm determiningwhether or not, based upona geometric relationshipbetween the boundingvolumes and the higherlevel, root volume, the selected bounding volumes can be combined. If it isdetermined that the bounding volumes can be combined, anew bounding volume is created with the combined volumes comprising sub-volumes thereof. This process systematically repeats andattempts to combine all sub-volumes. The combining algorithm preferably allowsa combination if the volumes of the combination of thesub-volume is smaller than a fixed percentage of the parent volume. When apair can combine, it is replaced by a box bounding volumethat contains the pair as sub-volumes, and the process continues. In this way,a bounding volume hierarchy for all objects and assemblieswithin a complex structure is created.