Bounding Volumes - Real-Time Collision Detection - page 98

int imin, imax;
ExtremePointsAlongDirection(e, pt, numPts, &imin, &imax);
Point minpt = pt[imin];
Point maxpt = pt[imax];
float dist = Sqrt(Dot(maxpt - minpt, maxpt - minpt));
eigSphere.r = dist * 0.5f;
eigSphere.c = (minpt + maxpt) * 0.5f;
}
The modified full code for computing the approximate bounding sphere becomes:
void RitterEigenSphere(Sphere &s, Point pt[], int numPts)
{
// Start with sphere from maximum spread
EigenSphere(s, pt, numPts);
// Grow sphere to include all points
for(inti=0;i<numPts; i++)
SphereOfSphereAndPt(s, pt[i]);
}
The type of covariance analysis performed here is commonly used for dimension
reduction and statistical analysis of data, and is known as principal component analysis
(PCA). Further information on PCA can be found in [Jolliffe02]. The eigenvectors
of the covariance matrix can also be used to orient an oriented bounding box, as
described in Section 4.4.3.
4.3.4 Bounding Sphere Through Iterative Refinement
The primary idea behind the algorithm described in Section 4.3.2 is to start with a
quite good, slightly underestimated, approximation to the actual smallest sphere and
then grow it until it encompasses all points. Given a better initial sphere, the final
sphere can be expected to be better as well. Consequently, it is hardly surprising that
the output of the algorithm can very effectively be used to feed itself in an iterative
manner. The resulting sphere of one iteration is simply shrunk by a small amount to
make it an underestimate for the next iterative call.
void RitterIterative(Sphere &s, Point pt[], int numPts)
{
const int NUM_ITER = 8;