Game Development Reference
A − B
t = 1
t = 1
t = 0
t = 0
Figure 5.2. Computing a contact point (open dot) and a contact normal (arrow) of a box
and a moving sphere (left) by performing a ray test on the CSO of the objects (right).
Computing the time of impact between objects moving under translation boils
down to performing a ray cast on the CSO. The relative translation in space-time
can be visualized as a point that starts at the origin and moves towards the differ-
ence of the target translations of the objects. More formally, let the configuration
of objects A and B overatimeintervalbegivenby A + t c A and B + t c B ,where
[0 , 1]. Here, c A and c B are the target translations of A and B , respectively.
The earliest time the objects come into contact is given by the smallest t for which
t ( c B −
c A )
As can be seen, this expression defines the first intersection of a ray that is cast
from the origin towards c B −
c A .
Besides the time of impact, we can also compute the point of contact and a
contact normal from the ray cast. The contact point corresponds to the point where
the ray enters the CSO, and the contact normal is the normal to the boundary of
the CSO at this point. Figure 5.2 shows an example of the ray test for a box and a
For many pairs of shape types, the CSO's shape cannot be represented explic-
itly in a simple way. Fortunately, we do not need an explicit representation of
the CSO for performing any of these proximity queries. Instead, we require an
implicit representation of the used shapes in terms of their support mappings.
5.3 Support Mappings
The versatility of GJK lies in the fact that it uses support mappings for reading
the geometry of convex objects. A support mapping for an object C is a function