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
).