Game Development Reference
proportional to the maximum squared length of a vector in Y . So, a robust imple-
mentation would use as termination condition
2 : y ∈
ε tol max
where ε tol is an order of magnitude larger than the machine epsilon of the used
floating-point format. Choosing a tolerance ε tol that is too small may result in
infinite looping, since then the rounding noise in the computation of
become greater than ε tol times the maximum squared length of a vector y
The convergence speed depends on the used shape types. We have found
the worst convergence for quadric shapes such as spheres and cylinders. For a
quadric, the average number of iterations is roughly proportional to
log( ε tol ).
For instance, an ε tol of 10 − 6 results in eight iterations on average for random rays
with a high hit probability. Polytopes usually take fewer iterations.
For collision detection, the performance of GJK can be boosted by allowing
an early out as soon as v becomes a separating axis [van den Bergen 99]. Frame
coherence can be exploited by caching this axis and using it as the initial v in the
next frame. A similar scheme can be used for the GJK ray cast. In case of a miss,
v is a separating axis of the ray and the object CSO. If the configuration of objects
does not change a lot over time, then this separating axis is likely to be a sepa-
rating axis in the next frame as well. By initializing v with a previously returned
separating axis, the number of iterations per frame can be reduced considerably.
Note that since this v may no longer be contained in A
B , it is necessary to skip
the termination test for the first iteration. Overall, a continuous GJK collision test
that exploits earlier separating axes is only slightly more expensive than the static
A contact between two objects is defined by a contact point and an orientation
of the contact plane. The plane separates the two objects at the contact point.
In physics-based simulations, contact constraints should keep the objects from
further interpenetrating at the contact point. Usually, a force or impulse along the
contact normal is applied in order to take care of this. The objects are, of course,
free to move away from each other, so normal forces or impulses act in only one
direction. Furthermore, objects in contact usually experience friction. Friction
acts laterally, i.e., along the contact plane.
The collision handler should return a contact point and normal for each collid-
ing pair of convex objects. The continuous collision test described in Section 5.6
returns these contact data for the first time of contact. The problem is that if the