Game Development Reference
In-Depth Information
the hit spot. Algorithm 2 describes the GJK-based continuous collision test in
pseudocode.
As mentioned, we can only progress if v
·
p >t v
·
r . Note that the sequence
{
generated by GJK can have a wild behavior, especially in the first few itera-
tions, so it is not guaranteed that this condition is immediately met. However, the
condition must become valid in a finite number of iterations. This can be shown
as follows. First of all, for regular GJK iterations,
v k }
v k
2
·
v k
w k approaches
v k
2
> 0, we see that v k
·
zero. Since
w k must become positive in a finite
number of iterations. It follows from
v
·
w = v
·
( p
s )
= v
·
( p
t r )
= v
·
p
t v
·
r
that, within a finite number of iterations, our condition must be valid. So, as long
as s is not contained in A
B , it takes a finite number of GJK iterations to either
get closer to the hit spot or find a condition for rejecting the complete ray. Note
that progress along the ray is a necessary yet not sufficient condition for global
convergence. The interested reader is referred to [van den Bergen 04] for a proof
that Algorithm2 is indeed guaranteed to terminate at the hit spot, should one exist.
The returned normal at the hit spot is the normal of the last supporting plane
that clipped the ray. If the objects A and B are intersecting at time t =0,then
of course the ray is never clipped, and the algorithm terminates returning a zero
hit spot and normal. This all makes perfect sense since if the objects are already
intersecting then the normal at the first time of impact is not defined.
Note that in contrast to the GJK distance algorithm, the CSO may change
position during iterations. The CSO is given by A
B
s and changes position
each time s is updated. These updates result in a behavior that deviates from the
normal behavior of GJK. First of all,
is no longer monotonically decreasing
in k . Secondly, the same support point may be returned over multiple iterations.
With the original GJK, generating the same support point twice is theoretically
impossible. Since it is a clear sign of numerical problems in a finite-precision
implementation of GJK, this property can be exploited to exit gracefully should
a support point ever reappear [van den Bergen 99]. For the GJK ray cast, we can
still rely on this property for signaling numerical problems; however, we need to
take care that the support-point history is flushed along with the simplex whenever
s is updated.
An issue that needs some attention is the choice of error tolerance ε in the
termination condition. The relative error in the computed value for v can be
quite large. We have found that the error in the squared length of v is roughly
v k