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