Graphics Reference
In-Depth Information
5.5.2
Separating-axis Test for Moving Convex Objects
For nonrotating convex polygonal or polyhedral objects moving with constant veloc-
ity, a modification of the separating-axis test (as described in Section 5.2.1) can be
used to determine the time of intersection of the objects, if any. First note that for
two moving objects,
A
and
B
, the velocity of
A
can be subtracted off from
B
, thus
effectively treating the problem as that of intersecting the stationary object
A
against
the moving object
B
.
Now, if the objects are initially intersecting, the first time of contact is at time
t
0.
Otherwise, the objects are disjoint. If disjoint, consider the intervals of projection of
A
and
B
onto some arbitrary line
L
. Clearly, collision may occur only if the projection
interval of
B
moves toward the interval of
A
and eventually overlaps it.
Note that just immediately before a first time of contact between the
A
and
B
projection intervals
A
and
B
must be separated along some axis. Then, too, just
immediately after a last time of contact they must again be separated along some
axis. Thus, the first and last time of contact can be determined by projection onto the
same separating axes as used for a stationary separating-axis test.
Consequently, to determine whether
B
intersects
A
it is sufficient to compute for
each potential separating axis the times at which the projected intervals start and end
intersection. The start and end times are computed using simple linear operations
and correspond to the initial and final contact, respectively, of the objects. Because
the objects can only overlap if they overlap simultaneously on all separating axes, the
nonemptiness of the intersection of the time intervals determined by the first and
last times of contact determines the collision result between the objects. Let
t
first
track
the largest of all times corresponding to the first time of contact on a separating axis.
Let
t
last
track the smallest of all times corresponding to the last time of contact on
a separating axis. After all axes have been tested, the objects intersect if and only if
t
first
=
t
last
, no intersection is possible and a
result of “no intersection”can be immediately returned.
The technique of using the separating-axis test with moving objects was indepen-
dently described by [Gomez99] for AABBs, and in more detail by [Levine00] for the
general case. A concrete example of the described method is given in Section 5.5.8
for the intersection of moving AABBs.
≤
t
last
. If sometime during the test
t
first
>
5.5.3
Intersecting Moving Sphere Against Plane
Let a plane
d
, where
n
is a unit vector. Let a sphere
S
be
specified by a center
C
and a radius
r
, and let
v
be the direction vector for
S
such that
the sphere center movement is given by
C
(
t
)
π
be specified by
n
·
X
=
=
C
+
t
v
over the interval of motion
0
≤
t
≤
1. The signed distance from the plane of a point
R
is (
n
·
R
)
−
d
. Therefore,
the sphere initially overlaps the plane if
(
n
d
≤
r
.
The sphere's movement relative to the plane can be categorized by considering
the sign of
n
·
C
)
−
·
·
>
v
and what side of the plane the sphere starts on. If (
n
v
)
0, the
