Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure
First Claim
1. A method for processing an arbitrary collection of objects, represented by computer generated images thereof, 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, comprising the steps of:
- a) creating bounding volumes for said objects;
b) processing selected bounding volumes through a predetermined combining algorithm to determine whether or not, based upon a geometric relationship between said bounding volumes and the root volume, the selected bounding volumes can be combined into a new volume representative of said selected bounding volumes, and with respect to those bounding volumes which can be combined;
c) creating a new bounding volume with said combined bounding volumes comprising sub-volumes thereof,d) recursively applying steps b) and c) to said new bounding volume and treating the new bounding volume as the root volume and its combined volumes as the selected volumes,e) utilizing said new bounding volume as an approximation of the image of said sub-volumes in a computer generated display.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
43 Claims
-
1. A method for processing an arbitrary collection of objects, represented by computer generated images thereof, 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, comprising the steps of:
-
a) creating bounding volumes for said objects; b) processing selected bounding volumes through a predetermined combining algorithm to determine whether or not, based upon a geometric relationship between said bounding volumes and the root volume, the selected bounding volumes can be combined into a new volume representative of said selected bounding volumes, and with respect to those bounding volumes which can be combined; c) creating a new bounding volume with said combined bounding volumes comprising sub-volumes thereof, d) recursively applying steps b) and c) to said new bounding volume and treating the new bounding volume as the root volume and its combined volumes as the selected volumes, e) utilizing said new bounding volume as an approximation of the image of said sub-volumes in a computer generated display. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A method for creating a tight, spatially balanced hierarchy of bounding volumes from an arbitrary distribution of parts for use as successive approximations to the original parts and part assemblies, comprising the steps of:
-
a) selecting a first part; b) computing a first bounding volume for said first part; c) making said first bounding volume a root volume; d) selecting a second part; e) computing a second bounding volume for said second part; f) creating a new root volume to contain said second bounding volume with said old root volume and second bounding volume as sub-volumes thereof; g) selecting a third part; h) computing a third bounding volume for said third part; i) expanding said root volume to contain said third bounding volume and adding said third bounding volume as a sub-volume thereof; j) selecting a first pair of said sub-volumes; k) processing said selected sub-volumes through a predetermined combining algorithm which determines, based upon a geometric relationship between said sub-volumes and said root volume, whether or not said selected sub-volumes can be combined into a new bounding volume and; i) if they cannot be combined, selecting a new pair of sub-volumes and processing said selected pair of sub-volumes through step k), ii) if they can be combined; 1) creating a new bounding volume with said selected sub-volumes as sub-volumes thereof, 2) selecting a new pair of sub-volumes and processing said selected pair of sub-volumes through step k), whereby sub-volumes of said root volume are tested to determine if they can combine into new bounding volumes to thereby create said hierarchy of bounding volumes; and utilizing said new bounding volumes as an approximation of the image of said sub-volumes in a computer generated display. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28)
-
-
29. A method for creating a tight, spatially balanced hierarchy of bounding volumes from an arbitrary distribution of parts for use as successive approximations to the original parts and part assemblies, comprising the steps of:
-
a) selecting a first part; b) computing a bounding volume for said first part; c) determining if a root volume exists and; i) if it does not; 1) making the current volume the root volume, and 2) selecting a new object and proceeding with step b), ii) if it does, proceeding with step d); d) determining if the root volume has sub-volumes; i) if it does not; 1) creating a new root volume with the old root volume and new selected volume as sub-volumes; 2) selecting a new object and proceeding with step b); ii) if it does, proceeding with step e); e) expanding the root volume to contain the new selected volume and adding the new selected volume as a sub-volume thereof; f) selecting a first pair of sub-volumes; g) processing said selected sub-volumes through a predetermined combining algorithm which determines whether or not said selected sub-volumes can be combined into a new bounding volume which is representative of said sub-volumes, and; i) if they cannot be combined, selecting a new pair of sub-volumes and proceeding to step g), ii) if they can be combined, proceeding to step h); h) determining if the first of the selected sub-volumes has sub-volumes and; i) if it does; 1) expanding the first selected sub-volume to contain the second selected sub-volume, and 2) if it does not, proceeding to step f); ii) if it does not, proceeding to step i); i) determining if the second of the selected sub-volumes has sub-volumes and; i) if it does; 1) expanding the second selected sub-volume to contain the first selected sub-volume, and 2) proceeding to step f), ii) if it does not, proceeding to step j); and j) creating a new volume with the first and second selected sub-volumes as sub-volumes thereof and selecting a new pair of sub-volumes and proceeding to step g), whereby sub-volumes of said root volume are tested to determine if they can combine into new bounding volumes to thereby create said hierarchy of bounding volumes; and k) utilizing the new bounding volume as an approximation of the image of said sub-volumes in a computer generated display. - View Dependent Claims (30, 31, 32, 33, 34, 35)
-
-
36. A method for processing an arbitrary collection of geometric objects 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 representation therefore comprising the steps of:
-
a) creating bounding volumes for said objects; b) processing selected bounding volumes through a predetermined combining algorithm to determine whether or not, based upon a geometric relationship between said bounding volumes and the root volume, the selected bounding volumes can be combined into a new volume representative of said selected bounding volumes, and with respect to those bounding volumes which can be combined; c) creating a new bounding volume with said combined bounding volumes comprising sub-volumes thereof, whereby the new bounding volume approximates the spatial relationship of said sub-volumes, d) recursively applying steps b) and c) to said new bounding volume treating the new bounding volume as the root volume; and e) utilizing said new bounding volume as an approximation of the spatial relationship of said sub-volumes in a computer generated representation therefore. - View Dependent Claims (37, 38, 39, 40, 41, 42)
-
-
43. A method for creating a tight, spatially balanced hierarchy of bounding volumes from an arbitrary distribution of parts for use as successive approximations to be the original parts and part assemblies, in a computer generated representation thereof comprising the steps of:
-
a) selecting a first part; b) computing a bounding volume for said first part; c) determining if a root volume exists and; i) if it does not; 1) making the current volume the root volume, and 2) selecting a new object and proceeding with step b), ii) if it does, proceeding with step d); d) determining if the root volume has sub-volumes; i) if it does not; 1) creating a new root volume with the old root volume and new selected volume as sub-volumes thereof; 2) selecting a new part and proceeding with step b), ii) if it does, proceeding with step e); e) expanding the root volume to contain a new selected volume, N, and adding the new selected volume as a sub-volume thereof; f) selecting a first, previously existing, sub-volume, M; g) computing the combined volume of selected sub-volume M and newly inserted sub-volume, N; h) determining if said combined volume is smaller than a predetermined percentage of the parent volume and; i) if it is not, selecting a next, previously existing sub-volume, M, and proceeding to step g) unless all previously existing sub-volumes have been previously selected, in which case proceed to step l); ii) if it is, proceeding to step i); i) determining whether sub-volume M has sub-volumes, and; i) if it does, a) expanding volume M to contain volume N and proceeding to step l), ii) if it does not, proceeding to step j); j) determining whether sub-volume N has sub-volumes, and; i) if it does, a) expanding volume N to contain volume M, b) selecting the next, previously existing sub-volume, M, and proceeding to step g) unless all previously existing sub-volumes have been previously selected, in which case proceeding to step l); ii) if it does not, proceeding to step k); k) creating a new volume with N and M as sub-volumes and proceeding to step l); l) determining whether N was merged with a previously existing sub-volume and; i) if it was not, selecting a new object and proceeding with step b), ii) if it was, proceeding with step m); m) determining if the parent volume of N increased by the inclusion of N, and; i) if it did not, selecting a new object and proceeding with step b), ii) if it did, proceeding with step n); n) determining if the smallest sub-volume within the parent volume is smaller than a predetermined percentage of the parent volume, and; i) if it is not, selecting a new object and proceeding with step b), ii) if it is, proceeding with step o); o) selecting a first pair of sub-volumes A, B; p) computing the combined volume of selected volumes A and B; q) determining if said combined volume is less than a predetermined percentage of the parent volume, and i) if it is not, selecting a new pair of sub-volumes A, B and proceeding to step p); ii) if it is, proceeding to step r); r) determining if the first sub-volume A has sub-volumes and; i) if it does; 1) expanding the first selected sub-volume A to contain the second selected sub-volume B, and 2) proceeding to step f), ii) if it does not, proceeding to step s) s) determining if the second selected sub-volume B has sub-volumes and; i) if it does; 1) expanding the second selected sub-volume to contain the first selected sub-volume A, and 2) proceeding to step f), ii) if it does not, proceeding to step t); and t) creating a new volume with the selected sub-volumes A, B as sub-volumes thereof and selecting a new pair of sub-volumes A, B, and proceeding to step b), whereby sub-volumes are tested to determine if they can combine into new bounding volumes to thereby create said hierarchy of bounding volumes and u) utilizing said new bounding volumes as an approximation of said sub-volumes as an approximation of said sub-volumes in a computer generated representation thereof.
-
Specification