Game Development Reference

In-Depth Information

A

A − B

B

t = 1

t = 1

B

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

t

[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
)

∈

A

−

B
.

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

moving sphere.

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