Game Development Reference
t = 1
A − B
t = 0
Figure 5.5. A new lower bound t clip is found by clipping the ray r using the supporting
plane at p = s A−B ( − v ) .
however, in our case, we perform the advancement inside GJK. We do regular
GJK iterations and use the supporting planes that are generated in each iteration
as clipping planes. Each time we find a new lower bound t clip , time is advanced
to this value. In terms of configuration space, we say that the origin is “shifted”
to t clip r . Of course, conceptually the origin does not move along the ray. Instead,
the CSO moves in the opposite direction.
Let s = t r be the current lower bound for the hit spot. Then the current CSO
is A−B− s . In search of the point of the CSO closest to the origin, GJK generates
a supporting plane with normal
− v and support point p = s A−B ( − v ). We can
identify the intersection point of the plane and the ray as
t clip = v
and find the following:
1. If v · r > 0,then t clip is a lower bound for t hit ,andif v · p >t v · r ,then
t clip >t , which means that we found a better lower bound. See Figure 5.5
for an illustration of this case.
2. If v
r < 0,then t clip is an upper bound for t hit ,andif v
p >t v
t clip <t , which means we have evidence that the ray misses.
p > 0, then the ray
misses as well, since it is completely contained in the positive half-space of
the supporting plane.
3. If v
r =0, then the ray is not clipped at all, and if v
Again, we see that for all three cases, if v
r , then the ray can either be
clipped or rejected. As long as this condition is not valid, we continue performing
regular GJK iterations. Note that we need to search for the closest point of the
p >t v