Game Development Reference

In-Depth Information

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

v
k

·

w
k

.

v
k

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

v

·
w
k
is positive. The added termination condition now becomes

·
w
k
)
2

(
v
k

>
(
ρ
A
+
ρ
B
)
2
.

v
k

·

w
k
>
0 and

v
k

2

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

contacts.

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

1

2
Games usually have a gravitational acceleration that is greater than 9.8 m/s
2
.