Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure
US5613049A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Oct 26, 1994 |
| Grant date | Mar 18, 1997 |
| Priority date | — |
| Expiry date | Oct 26, 2014 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T2219/2008
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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. …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.