Game Development Reference

In-Depth Information

Whatever feature vector

−

s
hits on the Gauss map, that is the support feature

in direction
s
:

2
,

−

s

∈G

(

F

(
s
))
,

∀

s

∈
S

where

G

(

F

(
s
)) is the Gauss map of feature

F

(
s
).

4.6 Computing Full Contact Manifolds

SAT is not particularly constructive. It doesn't tell us much about contact mani-

folds or explain how to compute collision response. We'll compute the collision

response in the solver using the contact-manifold vertices, a.k.a. contact points,

trying to reduce penetration distance, velocity, and/or acceleration in all of them

at the same time. But for now, our algorithm of finding the contact manifold

consists of the following three steps:

1.
Find the contact normal
s
.
It needs to be the MTD or something close

to it for the contact-manifold generation to work because we need support

polygons that actually intersect. SAT, the expanding polytope algorithm

(EPA) [van den Bergen 01], and Gilbert-Johnson-Keerthi algorithm (GJK)

[van den Bergen ] all generate MTD. Approximate direction, like the one

Xenocollide [Snethen 08] or Dual-CD [Choi et al. 05] produces, can be

used, too. To warm start many algorithms, we may cache
s
found on the

previous frame, exploiting coherence.

2.
Find the support shapes,
or the outlines of the shape surfaces “touching”

(close enough to) the plane of contact and potentially the other shape.

3.
Intersect the contact areas
to get the final contact manifold. We need to

choose a few representative points from the outline contour. It must be at

least three points, but if we choose just the corners, it may be unstable (see

Figure 4.3(b)
)
: whatever three corners we choose at the base of a cube, the

projection of the center of mass will not lie well inside their convex hull, a

condition necessary for stability. Four points are practically enough in most

cases (see below for a discussion on choosing the number of points).

4.6.1 Step 1: Find the Contact Normal

The
s
min
as described in Section 4.4, or the approximation thereof, will be our

contact normal. In convex shapes, the support features (along
s
min
)arealsothe

closest features. Denote a plane in the middle of the support planes and the contact