Graphics Reference
In-Depth Information
D
A
B
C
Figure 4.1
The bounding volumes of
A
and
B
do not overlap, and thus
A
and
B
cannot
be intersecting. Intersection between
C
and
D
cannot be ruled out because their bounding
volumes overlap.
Many geometrical shapes have been suggested as bounding boxes. This chapter
concentrates on the shapes most commonly used; namely, spheres, boxes, and convex
hull-like volumes. Pointers to a few less common bounding volumes are provided in
Section 4.7.
4.1
Desirable BV Characteristics
Not all geometric objects serve as effective bounding volumes. Desirable properties
for bounding volumes include:
Inexpensive intersection tests
●
Tight fitting
●
Inexpensive to compute
●
Easy to rotate and transform
●
Use little memory
●
The key idea behind bounding volumes is to precede expensive geometric tests
with less expensive tests that allow the test to exit early, a so-called “early out.”To
support inexpensive overlap tests, the bounding volume must have a simple geomet-
ric shape. At the same time, to make the early-out test as effective as possible the
bounding volume should also be as tight fitting as possible, resulting in a trade-off
between tightness and intersection test cost. The intersection test does not necessarily
just cover comparison against volumes of the same type, but might also test against
other types of bounding volumes. Additionally, testing may include queries such as
