Graphics Reference
In-Depth Information
5.5.7
Intersecting Moving Sphere Against AABB
Let a sphere
S
be specified by a center
C
and a radius
r
, and let
d
be the direction vector
for
S
, such that the sphere center movement is given by
C
(
t
)
=
C
+
t
d
over the interval
of motion 0
1. Let
B
be an AABB. Intersecting the moving sphere
S
against the
box
B
is equivalent to intersecting the segment
L
(
t
)
≤
t
≤
1, against the
volume
V
that results after sweeping
B
with
S
(that is, against the Minkowski sum
of
B
and
S
,
V
=
C
+
t
d
,0
≤
t
≤
S
), as illustrated in Figure 5.37. The latter test can be efficiently
performed without forming
V
, as demonstrated next.
Let
E
be the AABB given by expanding the faces of
B
outward by a distance equiv-
alent to the sphere radius
r
. This is the tightest AABB bounding
V
, differing from
V
only in the lack of spherically beveled edges. Now, intersect
L
against
E
.If
L
does not
intersect
E
, then clearly
S
does not intersect
B
. Otherwise, let
P
=
B
⊕
=
L
(
t
) denote the
point where
L
intersects
E
at time
t
.
If
P
lies in a face Voronoi region of
B
, then nothing more is needed:
S
intersects
B
at time
t
when the sphere center is at point
P
. However, if
P
lies in an edge or vertex
Voronoi region, further tests are required to determine whether
L
passes through the
beveled region of
V
not present in
E
, thus missing
V
, or whether
L
intersects
V
on one
of its beveled edges or vertices at some later time
t
,
t
t
≤
1.
When
P
lies in an edge Voronoi region of
B
,
L
must additionally be intersected
against the capsule of radius
r
determined by the edge. If and only if
L
intersects the
capsule does
S
intersect
B
. The intersection of
L
and the capsule corresponds to the
actual intersection of
S
and
B
.
<
d
P
V
=
S
B
r
C
B
E
Figure 5.37
A 2D illustration of how the test of a moving sphere against an AABB is trans-
formed into a test of a line segment against the volume resulting after sweeping the AABB
with the sphere (forming the Minkowski sum of the sphere and the AABB).
