Graphics Reference
In-Depth Information
during hill climbing. A drawback is that both presented methods only provide inter-
ference detection. However, interval halving can be effectively used to obtain the time
of collision. Using an interval-halving approach, the simplices from the previous iter-
ation are ideal candidates for starting the next iteration. Alternatively, the time of
collision can be obtained iteratively using a root finder such as Brent's method, as
described in [Vlack01].
A recent method that also returns the time of collision is presented in [Bergen04].
Described is an iterative GJK-based algorithm for performing a ray cast against
a general convex object. This algorithm can trivially be used for detecting colli-
sion between two moving convex objects by forming the Minkowski sum of the
objects and casting a ray against their sum, where the ray corresponds to the relative
movement of one object with respect to the other. The time of collision is directly deter-
mined from the point along the ray at which intersection with the Minkowski sum
occurs.
9.6
The Chung-Wang Separating-vector Algorithm
The last convexity-based algorithm explored here is an algorithm given by Chung
and Wang [Chung96]. It is an original algorithm for intersection testing between
polyhedra
P
and
Q
, which is fast and simple to implement. In fact, the Chung-
Wang (CW) algorithm consists of two algorithms. The main algorithm starts from a
candidate separating vector and, in the case of nonintersection of
P
and
Q
, iteratively
updates the vector to one closer and closer to an actual separating vector. A supporting
subalgorithm detects the case in which
P
and
Q
are in collision, for which the main
algorithm would loop indefinitely.
Like the GJK algorithm, the CW algorithm operates on the vertices of the poly-
hedra. At each iteration
i
, the main algorithm computes the two vertices
p
i
and
q
i
(
p
i
∈
Q
) most extreme with respect to the current candidate separating-vector
s
i
. If this pair of vertices indicates object separation along
s
i
, the algorithm exits with
no intersection. Otherwise, the algorithm computes a new candidate separating-
vector by reflecting
s
i
about the perpendicular to the line through to
p
i
and
q
i
. More
specifically, the main algorithm of the CW algorithm is given in the following five
steps (the notation used here follows that in [Chung96]).
P
,
q
i
∈
1. Start with some candidate separating vector
s
0
and let
i
=
0.
2. Find extreme vertices
p
i
of
P
and
q
i
of
Q
such that
p
i
·
s
i
and
q
i
·−
s
i
are maximized.
3. If
p
i
s
i
, then
s
i
is a separating axis. Exit reporting no intersection.
4. Otherwise, compute a new separating vector as
s
i
+
1
·
s
i
<
q
i
·−
=
s
i
−
2(
r
i
·
s
i
)
r
i
, where
p
i
)
q
i
p
i
.
r
i
=
(
q
i
−
−
=
+
5. Let
i
i
1 and go to 2.
