Game Development Reference
Algorithm 3 The hybrid approach to computing contact data using GJK. Objects A and
B are dilated by respective radii ρ A and ρ B . Here, the contact data are a normal
pair of points p A and p B on the dilated boundaries of the respective objects. Any distances
less than tolerance ε tol are assumed to be zero, which means that contact data need to be
obtained from a penetration-depth query.
arbitrary point in A
s A−B (
− v · w >ε 2 do
w > 0 and ( v · w ) 2
2 > ( ρ A + ρ B ) 2 then
The dilated objects do not intersect.
point closest to the origin of conv( Y );
smallest X ⊆ Y such that v ∈ conv( X );
w ← s A−B ( − v );
2 >ε 2 then
Only the skins overlap.
Compute the closest points p A and p B of the bones.
Move the witness points to the skin boundaries.
← v v
p A ←
p A −
ρ A n ;
p B ←
p B + ρ B n
The distance between the bones is (close to) zero.
Compute contact data from penetration depth. ;
roughly one centimeter. Under these conditions, a combined radius of one or two
centimeters will do.
For computing the closest points p A and p B , additional data concerning the
individual objects A and B need to be maintained along with the current sim-
plex. Recall that each vertex of the simplex is obtained from the support mapping
s A−B , which is given by
s A−B ( v )= s A ( v )
s B (