Geometric Primitives - 3D Math Primer for Graphics and Game Development - page 307

An AABB class often defines two functions to help with this. The
first function “empties” the AABB. The other function adds a single point
into the AABB by expanding the AABB if necessary to contain the point.
Listing 9.2 shows such code.
Now, to create a bounding box from a set of points, we could use the
following code:

/ / Our l i s t o f p o i n t s

c o n s t i n t N;

V e c t o r 3 l i s t [N ] ;

/ / F i r s t , empty t h e box

AABB3 box ;
box . empty ( ) ;

/ / Add each p o i n t i n t o t h e box

f o r ( i n t i = 0 ; i < N ; ++ i ) {

box . add ( l i s t [ i ] ) ;

}

Listing 9.3
Computing the AABB for a set of points

9.4.3 AABBs versus Bounding Spheres
In many cases, we have a choice between using an AABB or a bounding
sphere. AABBs offer two main advantages over bounding spheres.
The first advantage of AABBs over bounding spheres is that computing
the optimal AABB for a set of points is easy to program and can be run
in linear time. Computing the optimal bounding sphere is a much more
di cult problem. (O'Rourke [52] and Lengyel [42] describe algorithms for
computing bounding spheres.)
Second, for many objects that arise in practice, an AABB provides a
tighter bounding volume, and thus better trivial rejection. Of course, for
some objects, the bounding sphere is better. (Imagine an object that is
itself a sphere!) In the worst case, an AABB will have a volume of just
under twice the volume of the sphere, but when a sphere is bad, it can be
really bad. Consider the bounding sphere and AABB of a telephone pole,
for example.
The basic problem with a sphere is that there is only one degree of
freedom to its shape—the radius of the sphere. An AABB has three degrees
of freedom—the length, width, and height. Thus, it can usually adapt to
differently shaped objects better. For most of the objects in Figure 9.10, the
AABB is smaller than the bounding sphere. The exception is the star in the
upper right-hand corner, where the bounding sphere is slightly smaller than
the AABB. Notice that the AABB is highly sensitive to the orientation of
the object, as shown by the AABBs for the two rifles on the bottom. In each