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
map of the support shape (see Figure 4.14 ) . If we sample every 45 , we will
never miss the contact area vertex with a 135 internal angle (see Figure 4.14
(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.