Graphics Reference
In-Depth Information
A
B
D
E
A
B
E
C
C
D
Figure 6.1
A bounding volume hierarchy of five simple objects. Here the bounding volumes
used are AABBs.
One approach to creating hierarchies is to have designers or artists manually create
them as part of their modeling hierarchies. However, creating trees manually is not
ideal. First, designers tend to think functionally rather than spatially. Consequently,
it is likely that, for instance, all nuts and bolts across a large mechanical design
are grouped under the same node. Such a grouping is not good from a collision
detection perspective. Second, the hierarchy is also likely to be either too shallow
or too deep in the wrong places. The designer's modeling hierarchy has been —
and arguably should be — constructed for easy editing and not to enable efficient
intersection queries. Although designers could theoretically adjust their hierarchies
to be more spatially oriented and better suited to collision queries, this is unlikely to
be an effective use of their time. A better solution is to automate, where possible, the
generation of hierarchies from the provided models. Such automation is not always
a trivial process and there are many issues to consider, as the next section will show.
6.1
Hierarchy Design Issues
There are many ways to construct a bounding volume hierarchy. The next section
outlines a number of desired characteristics for good hierarchies. A generic cost func-
tion to aid the cost comparison of queries for various hierarchical schemes is found in
Section 6.1.2. Finally, Section 6.1.3 discusses the question of what tree degree might
provide the best hierarchy.
6.1.1
Desired BVH Characteristics
Similar to bounding volumes, several desired properties for bounding volume
hierarchies have been suggested [Kaplan85] [Kay86] [Hubbard96]:
●
The nodes contained in any given subtree should be near each other.
Without explic-
itly defining nearness, the lower down the tree the nodes are the nearer they
should be to each other.
