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

Search Nedrilad ::

Custom Search