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