Bounding Volumes - Real-Time Collision Detection - page 89

Although the sphere test has a few more arithmetic operations than the AABB
test, it also has fewer branches and requires fewer data to be fetched. In modern
architectures, the sphere test is probably barely faster than the AABB test. However,
the speed of these simple tests should not be a guiding factor in choosing between
the two. Tightness to the actual data is a far more important consideration.
4.3.2 Computing a Bounding Sphere
A simple approximative bounding sphere can be obtained by first computing the
AABB of all points. The midpoint of the AABB is then selected as the sphere center,
and the sphere radius is set to be the distance to the point farthest away from this
center point. Note that using the geometric center (the mean) of all points instead of
the midpoint of the AABB can give extremely bad bounding spheres for nonuniformly
distributed points (up to twice the needed radius). Although this is a fast method, its
fit is generally not very good compared to the optimal method.
An alternative approach to computing a simple approximative bounding sphere
is described in [Ritter90]. This algorithm tries to find a good initial almost-bounding
sphere and then in a few steps improve it until it does bound all points. The algorithm
progresses in two passes. In the first pass, six (not necessarily unique) extremal points
along the coordinate system axes are found. Out of these six points, the pair of points
farthest apart is selected. (Note that these two points do not necessarily correspond
to the points defining the longest edge of the AABB of the point set.) The sphere
center is now selected as the midpoint between these two points, and the radius is
set to be half the distance between them. The code for this first pass is given in the
functions MostSeparatedPointsOnAABB() and SphereFromDistantPoints() of the
following:
// Compute indices to the two most separated points of the (up to) six points
// defining the AABB encompassing the point set. Return these as min and max.
void MostSeparatedPointsOnAABB(int &min, int &max, Point pt[], int numPts)
{
// First find most extreme points along principal axes
intminx=0,maxx=0,miny=0,maxy=0,minz=0,maxz=0;
for(inti=1;i<numPts; i++) {
if (pt[i].x < pt[minx].x) minx = i;
if (pt[i].x > pt[maxx].x) maxx = i;
if (pt[i].y < pt[miny].y) miny = i;
if (pt[i].y > pt[maxy].y) maxy = i;
if (pt[i].z < pt[minz].z) minz = i;
if (pt[i].z > pt[maxz].z) maxz = i;
}