Game Development Reference

In-Depth Information

area) to be aligned within a rather tight tolerance. But in the case of long time

steps, the supporting features may be significantly misaligned, and yet it may

be desirable to detect a large contact area, like the rectangular contact area in

Figure 4.13(a).

We may start with the separating axis direction
s
min
and take a wide cone

of directions around
s
min
within some tolerance angle
δ
Pe
.Thenwemayfind

all vertices supporting that cone of direction. See Figure 4.13(b): we may have

some vertices that do not support our cone. We often may ignore them and form

a simplified contact area (unless the tolerance angle is too high). Sometimes,

as in Figure 4.13(c), we have an “edge-on” contact, where stable stacking is not

possible. The tolerance angle lets us make a clear distinction between these cases.

It may be better to illustrate this method with the Gauss map of the convex

shape. To find the outline of the contact area, choose a
δ
Pe
(5
◦
-15
◦
works fine)

and cut out a cone with that angle around the contact-normal direction, like in

Figure 4.10.

This gives rise to a sampling algorithm. If it's too slow to find the full con-

tact area with all the vertices, we may only find a representative sample of those

vertices. A vertex is mapped to an area on

2
, so the cone will intersect a continu-

ous circle of vertices around the base of the polytope (see
Figure 4.10(a)
). Those

vertices will limit the area consisting of the faces with normals inside the toler-

ance angle from the contact normal (see
Figure 4.10(c)
)
. Sometimes there will

be no such faces, but only one vertex (see
Figure 4.11(a)
)
or several vertices with

corresponding edges (see
Figure 4.11(b)
and
(c)
)
. This definition is completely

independent from the linear scale of the shapes.

S

4.6.7 Contact Area Sampling

Of course, we could walk the circle on the Gauss map and find all vertices one

by one. It is not particularly hard, but unless you want a very precise contact

manifold, we can also just sample 8 (or 4,or12) discrete directions from the

cone. To decide how many samples we need, consider the two-dimensional Gauss

(right)). If we make
n
uniform samples,
360
n
each, we may only miss vertices on

the contact polygon with internal angle of 180
◦
−

360
n
. Eight samples worked

well for me. If we miss a vertex on the contact polygon, and it's important,

chances are the dynamic simulation will tilt the shape towards the missing ver-

tex, and we'll find it the next time. Another good property of eight samples is that

it's easily SIMD-izable: we can find support for all eight directions in parallel

easily.