Graphics Reference
In-Depth Information
Welzl's algorithm can be applied to computing both bounding circles and higher
dimensional balls. It does not, however, directly extend to computing the minimum
sphere bounding a set of spheres. An algorithm for the latter problem is given in
[Fischer03]. Having covered spheres in detail, we now turn our attention to bounding
boxes of arbitrary orientation.
4.4
Oriented Bounding Boxes (OBBs)
An oriented bounding box (OBB) is a rectangular block, much like an AABB but with
an arbitrary orientation. There are many possible representations for an OBB: as a
collection of eight vertices, a collection of six planes, a collection of three slabs (a pair
of parallel planes), a corner vertex plus three mutually orthogonal edge vectors, or
a center point plus an orientation matrix and three halfedge lengths. The latter is
commonly the preferred representation for OBBs, as it allows for a much cheaper
OBB-OBB intersection test than do the other representations. This test is based on
the separating axis theorem, which is discussed in more detail in Chapter 5.
// Region R =
x|x=c+r*u[0]+s*u[1]+t*u[2]
, |r|<=e[0], |s|<=e[1], |t|<=e[2]
struct OBB {
Point c;
// OBB center point
Vector u[3];
// Local x-, y-, and z-axes
Vector e;
// Positive halfwidth extents of OBB along each axis
};
At 15 floats, or 60 bytes for IEEE single-precision floats, the OBB is quite an expen-
sive bounding volume in terms of memory usage. The memory requirements could be
lowered by storing the orientation not as a matrix but as Euler angles or as a quater-
nion, using three to four floating-point components instead of nine. Unfortunately,
for an OBB-OBB intersection test these representations must be converted back to
a matrix for use in the effective separating axis test, which is a very expensive oper-
ation. A good compromise therefore may be to store just two of the rotation matrix
axes and compute the third from a cross product of the other two at test time. This
relatively cheap CPU operation saves three floating-point components, resulting in
a 20% memory saving.
4.4.1
OBB-OBB Intersection
Unlike the previous bounding volume intersection tests, the test for overlap between
two oriented bounding boxes is surprisingly complicated. At first, it seems a test to see
if either box that is fully outside a face of the other would suffice. In its simplest form,
