Game Development Reference
In-Depth Information
P
r
Q
Q
r
G
Figure 8.2. The initial bounding sphere determined by the extents of the set of points in
the direction of the principal axis is expanded to include any points in the set that lie out-
side of the sphere.
Whenever a point is encountered that lies outside the sphere, we expand the
sphere by adjusting the center Q and radius r to enclose the previous sphere and
the exterior point, as shown in Figure 8.2. A point P lies outside the sphere if
2
2
PQ
−>
r
.
(8.17)
i
We expand the sphere by placing the new center
Q on the line connecting the
previous center Q and the exterior point P . The new sphere is then tangent to the
previous sphere at a point G given by
PQ
PQ ,
i
(8.18)
G
=−
Q
r
i
which also lies on the line containing Q and P . The new center
Q is placed
halfway between the points G and P , and the new radius r
is the distance from
the new center to either of these points:
GP
+
=
i
Q
2
r
=−
PQ .
(8.19)
i
8.1.4 Bounding Ellipsoid Construction
An ellipsoidal bounding volume may be appropriate for a triangle mesh having
an elongated shape. To determine a good bounding ellipsoid for a set of vertices
12
PP
,
,
, we need to calculate the lengths of the three semiaxes of the ellip-
,
N