Graphics Reference
In-Depth Information
if (dist2 > s.r * s.r) {
float dist = Sqrt(dist2);
float newRadius = (s.r + dist) * 0.5f;
float k = (newRadius - s.r) / dist;
s.r = newRadius;
s.c+=d*k;
}
}
The full code for computing the approximate bounding sphere becomes:
void RitterSphere(Sphere &s, Point pt[], int numPts)
{
// Get sphere encompassing two approximately most distant points
SphereFromDistantPoints(s, pt, numPts);
// Grow sphere to include all points
for(inti=0;i<numPts; i++)
SphereOfSphereAndPt(s, pt[i]);
}
By starting with a better approximation of the true bounding sphere, the resulting
sphere could be expected to be even tighter. Using a better starting approximation is
explored in the next section.
4.3.3
Bounding Sphere from Direction of Maximum Spread
Instead of finding a pair of distant points using an AABB, as in the previous section, a
suggested approach is to analyze the point cloud using statistical methods to find its
direction of maximum spread [Wu92]. Given this direction, the two points farthest
away from each other when projected onto this axis would be used to determine the
center and radius of the starting sphere. Figure 4.8 indicates the difference in spread
for two different axes for the same point cloud.
Just as the mean of a set of data values (that is, the sum of all values divided by
the number of values) is a measure of the central tendency of the values,
variance
is a measure of their dispersion, or spread. The mean
u
and the variance
2
σ
are
given by
n
1
n
u
=
x
i
,
i
=
1
