Method for creating spatially balanced bounding volume hierarchi

Details Method for creating spatially balanced bounding volume hierarchi Method for creating spatially balanced bounding volume hierarchi

1994-10-26

1997-03-18

Nguyen, Phu K.

G06T 500

Patent

active

056130490

ABSTRACT:
Disclosed is a method for processing an arbitrary collection of objects, forming a complex structure, into a hierarchy of bounding volumes, from a root volume bounding all objects, to sub-volumes bounding individual objects or assemblies thereof, for use as successive approximations to said objects in a computer generated display. The method includes the first step of creating a bounding volume for each of the objects. Selected bounding volumes are then processed through a combining algorithm determining whether or not, based upon a geometric relationship between the bounding volumes and the higher level, root volume, the selected bounding volumes can be combined. If it is determined that the bounding volumes can be combined, a new bounding volume is created with the combined volumes comprising sub-volumes thereof. This process systematically repeats and attempts to combine all sub-volumes. The combining algorithm preferably allows a combination if the volumes of the combination of the sub-volume is smaller than a fixed percentage of the parent volume. When a pair can combine, it is replaced by a box bounding volume that contains the pair as sub-volumes, and the process continues. In this way, a bounding volume hierarchy for all objects and assemblies within a complex structure is created.

REFERENCES:
patent: 4631690 (1986-12-01), Corthout et al.
patent: 4862392 (1989-08-01), Steiner
patent: 4901252 (1990-02-01), Fitzgerald et al.
patent: 4912659 (1990-03-01), Liang
patent: 4922430 (1990-05-01), Wavish
patent: 4967375 (1990-10-01), Pelham et al.
patent: 4982180 (1991-01-01), Seki et al.
patent: 5048095 (1991-09-01), Bhann et al.
patent: 5088054 (1992-02-01), Paris, II
patent: 5144685 (1992-09-01), Nasar et al.
patent: 5363475 (1994-11-01), Baker et al.
patent: 5434617 (1995-07-01), Bianchi
patent: 5442733 (1995-08-01), Kaufman et al.
patent: 5448686 (1995-09-01), Borrel et al.
Kay et al.; Ray Tracing Complex Scence; 1986; pp. 269-278.
Goldsmith et al.; Automatic Creation of Object Hierarchies for Ray Tracing; 1987; pp. 14-20.
Teller et al.; Global Visibility Algorithms for Illumination Computations; 1993; pp. 239-246.
Funkhouser et al.; Adaptive Display Algorithms for Interactive Frame Rates During Visualization of Complex Virtual Environments; 1993; pp. 247-254.
Heckbert et al.; Multiresolution Modeling for Fast Rendering; 1994; pp. 43-50.

Affiliated with

Also associated with

Rating

Method for creating spatially balanced bounding volume hierarchi does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for creating spatially balanced bounding volume hierarchi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for creating spatially balanced bounding volume hierarchi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1712279