Game Development Reference
In order to make this possible, we will need to dilate at least one of the objects
by a small radius. We will call the part of the object that is formed by dilation
the skin and the rest of the body the bone . If only the skins overlap, then we
can compute the contact data using the closest points of the bones. For deeper
penetrations, we can fall back to the penetration depth for our contact data.
We combine the collision test of the dilated objects and the computation of the
closest points of the bones into a single GJK query rather than perform a separate
test for each of the two operations. Of course, it suffices to simply compute the
distance between the bones, since the dilated objects intersect only if the distance
between the bones is not greater than the sum of the radii of the skins. However,
we can do a little better.
Often it is not necessary to compute an accurate distance, since once we have
evidence that the distance is greater than the sum of the radii, we can exit early.
GJK maintains a lower bound for the distance in the form of
If this value ever gets greater than ρ A + ρ B , the sum of the radii of objects A and
B , then we may exit. Again, we do not like to evaluate
since this involves a
square root, so we square out both ends of the inequality, but not before checking
whether v k
· w k is positive. The added termination condition now becomes
· w k ) 2
( v k
> ( ρ A + ρ B ) 2 .
w k > 0 and
Algorithm 3 describes the hybrid approach in pseudocode.
Falling back to a penetration-depth query should only happen in emergen-
cies. Under normal conditions, the objects should only intersect with their skins.
The question remains of how to pick a proper radius for the dilation. Under the
assumption that high-velocity impacts are resolved using the contact data from
the continuous collision detection algorithm discussed in Section 5.6, it is safe to
conclude that the hybrid approach only needs to compute contact data for resting
Depending on the physics engine's contact solver and the type of application,
the dilation radius may vary, but let us assume that the resting object is allowed
to drop into the other object by the distance it can move in a single frame due to
gravity. If we start with a relative velocity of zero, the traversed distance is
2 gt 2 ,
where g is the gravitational acceleration and t is the frame time. For an acceler-
ation 2 of 20 m/s 2 and a frame time of 0.033 seconds, this results in a distance of
2 Games usually have a gravitational acceleration that is greater than 9.8 m/s 2 .