Game Development Reference
In-Depth Information
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
and a
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.
n
arbitrary point in A
B ;
v
W
←∅
;
s A−B (
w
v );
while
v
2
v · w 2 do
begin
if v
w > 0 and ( v · w ) 2
v
2 > ( ρ A + ρ B ) 2 then
·
{{
The dilated objects do not intersect.
}}
return false
Y
W
∪{
}
w
;
point closest to the origin of conv( Y );
W ←
v
smallest X ⊆ Y such that v conv( X );
w ← s A−B ( v );
end ;
if
2 2 then
v
{{
Only the skins overlap.
}}
begin
Compute the closest points p A and p B of the bones.
{{
Move the witness points to the skin boundaries.
}}
v v
n
;
p A
p A
ρ A n ;
p B
p B + ρ B n
end
else
{{
The distance between the bones is (close to) zero.
}}
Compute contact data from penetration depth. ;
return true
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 (
v ).