Bounding Volumes - Real-Time Collision Detection - page 77

BETTER BOUND, BETTER CULLING

FASTER TEST, LESS MEMORY

SPHERE AABB OBB 8-DOP CONVEX HULL

Figure 4.2 Types of bounding volumes: sphere, axis-aligned bounding box (AABB), oriented
bounding box (OBB), eight-direction discrete orientation polytope (8-DOP), and convex hull.

point inclusion, ray intersection with the volume, and intersection with planes and
polygons.
Bounding volumes are typically computed in a preprocessing step rather than at
runtime. Even so, it is important that their construction does not negatively affect
resource build times. Some bounding volumes, however, must be realigned at runtime
when their contained objects move. For these, if the bounding volume is expensive
to compute realigning the bounding volume is preferable (cheaper) to recomputing
it from scratch.
Because bounding volumes are stored in addition to the geometry, they should
ideally add little extra memory to the geometry. Simpler geometric shapes require less
memory space. As many of the desired properties are largely mutually exclusive, no
specific bounding volume is the best choice for all situations. Instead, the best option
is to test a few different bounding volumes to determine the one most appropriate
for a given application. Figure 4.2 illustrates some of the trade-offs among five of
the most common bounding volume types. The given ordering with respect to better
bounds, better culling, faster tests, and less memory should be seen as a rough, rather
than an absolute, guide. The first of the bounding volumes covered in this chapter is
the axis-aligned bounding box, described in the next section.

4.2 Axis-aligned Bounding Boxes (AABBs)

The axis-aligned bounding box (AABB) is one of the most common bounding volumes.
It is a rectangular six-sided box (in 3D, four-sided in 2D) categorized by having its
faces oriented in such a way that its face normals are at all times parallel with the
axes of the given coordinate system. The best feature of the AABB is its fast overlap
check, which simply involves direct comparison of individual coordinate values.