Game Development Reference

In-Depth Information

when multiple subsimplices need to be checked in a single iteration. This would

be the case for triangles and tetrahedra, which are the common cases in GJK.

Finally, after you get a feel for it, the formulation is actually very simple

and offers a clean way to control precision. It is simple, since there is no case

distinction. The formula works the same for simplices of any dimension. Of

course, we can add case distinction based on the number of vertices, and if we

want to maximize reuse within an iteration, that actually would be a smart thing

to do. However, the structure of all computations remains the same: we start

by computing the Δ
i
values for edges first, then for triangles, and finally for a

tetrahedron, reusing the values from lower-dimensional simplices in the higher-

dimensional ones.

Simplicity is also nice for controlling precision. Basically, there are only two

places where precision is lost. Cancellation happens in the dot product and in the

summation of cofactor terms. We can reduce loss of precision due to cancellation

by making sure that the vector
y
k
−

y
j
that is used as an argument in the dot

product is as short as possible [van den Bergen 03]. We have some freedom in the

choice of
y
k
, so we choose the
y
k
∈

X
closest to
y
j
.

The division by Δ
X
can be skipped or at least postponed if we rely on differ-

ent termination criteria, since only the direction of
v
is required for computing the

support points [Muratori 06]. This is an interesting idea since it allows us to com-

pute the direction of
v
directly from the closest subsimplex without the need to go

through barycentric coordinates, potentially giving us better precision. However,

for selecting the closest subsimplex, we still need to do the Voronoi plane tests, so

the direct approach does not offer us a more reliable closest-subsimplex selection.

Furthermore, the need for the (squared) length of
v
rises if termination is guarded

by testing whether each iteration makes significant progress towards the closest

point. Divisions do not reduce precision and since only one is needed per itera-

tion, they take less than five percent of the total computation time, so performance

is not harmed too much by keeping the division.

5.6 Continuous Collision Detection

We are now ready to solve the problem of how to perform collision detection in

continuous space-time. As mentioned earlier, objects move only by translation

between time steps. For each instance of time
t

[0
,
1] between two time steps,

the configuration of objects
A
and
B
is given by
A
+
t
c
A
and
B
+
t
c
B
.Let

r
=
c
B
−

∈

c
A
be the relative target translation over the time interval. Then, the