Graphics Reference
In-Depth Information
4.3 Spheres
The sphere is another very common bounding volume, rivaling the axis-aligned
bounding box in popularity. Like AABBs, spheres have an inexpensive intersection
test. Spheres also have the benefit of being rotationally invariant, which means that
they are trivial to transform: they simply have to be translated to their new position.
Spheres are defined in terms of a center position and a radius:
(x, y, z) | (x-c.x) 2 + (y-c.y) 2 + (z-c.z) 2<=r 2
// Region R =
struct Sphere {
Point c;
// Sphere center
float r;
// Sphere radius
};
At just four components, the bounding sphere is the most memory-efficient
bounding volume. Often a preexisting object center or origin can be adjusted to
coincide with the sphere center, and only a single component, the radius, need be
stored. Computing an optimal bounding sphere is not as easy as computing an opti-
mal axis-aligned bounding box. Several methods of computing bounding spheres are
examined in the following sections, in order of increasing accuracy, concluding with
an algorithm for computing the minimum bounding sphere. The methods explored
for the nonoptimal approximation algorithms remain relevant in that they can be
applied to other bounding volumes.
4.3.1 Sphere-sphere Intersection
The overlap test between two spheres is very simple. The Euclidean distance between
the sphere centers is computed and compared against the sum of the sphere radii. To
avoid an often expensive square root operation, the squared distances are compared.
The test looks like this:
int TestSphereSphere(Sphere a, Sphere b)
{
// Calculate squared distance between centers
Vector d = a.c - b.c;
float dist2 = Dot(d, d);
// Spheres intersect if squared distance is less than squared sum of radii
float radiusSum = a.r + b.r;
return dist2 <= radiusSum * radiusSum;
}
 
Search WWH ::




Custom Search