Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 426

B.2.10 Computing bounding shapes
Bounding volumes are useful as approximate extents of more complex objects. Often, simpler tests can
be used to determine the general position of an object by using bounding volumes, thus saving com-
putation. In computer animation, the most obvious example occurs in testing for object collisions. If the
bounding volumes of objects are not overlapping, then the objects themselves must not be penetrating
each other. Planar polyhedra are considered here because the bounding volumes can be determined by
inspecting the vertices of the polyhedra. Nonplanar objects require more sophisticated techniques.
Axis-aligned bounding boxes and bounding spheres are relatively easy to calculate but can be poor
approximations of the object's shape. Slabs and oriented bounding boxes (OBBs) can provide a much
better fit. OBBs are rectangular bounding boxes at an arbitrary orientation [ 7 ] . For collision detection,
bounding shapes are often hierarchically organized into tighter and tighter approximations of the
object's space. A convex hull , the smallest convex shape bounding the object, provides an even tighter
approximation but requires more computation.

Bounding boxes
Bounding box typically refers to a boundary cuboid (or rectangular solid) whose sides are aligned with the
principal axes. A bounding box for a collection of points is easily computed by searching for minimum
and maximum values for the x -, y -, and z -coordinates. A point is inside the bounding box if its coordinates
are between min/max values for each of the three coordinate pairs. While the bounding box may be a good
fit for some objects, it may not be a good fit for others ( Figure B.19 ). Howwell the bounding box approx-
imates the shape of the object is rotationally variant, as shown in Figures B.19b and B . 19c.

Bounding slabs
Bounding slabs are a generalization of bounding boxes. A pair of arbitrarily oriented planes are used to
bound the object. The orientation of the pair of planes is specified by a user-supplied normal vector.
The normal defines a family of planes that vary according to perpendicular distance to the origin.
The planar equation axþ byþ cz¼ d ,( a , b , c ) represents a vector normal to the plane. If this vector
has unit length, then d is the perpendicular distance to the plane. If the length of ( a , b , c ) is not one, then
d is the perpendicular distance scaled by the vector's length. Notice that d is equal to the dot product of
the vector ( a , b , c ) and a point on the plane.
Given a user-supplied normal vector, the user computes the dot product of that vector and each
vertex of the object and records the minimum and maximum values ( Eq. B.32 ). The normal vector

A B C

FIGURE B.19
Sample objects and their bounding boxes (in two-dimensional).