Game Development Reference
InDepth Information
Figure 4.9.
Parallelepiped.
planes, and assume the shapes are close enough or are penetrating, so that we have
to generate a contact manifold and can't ignore their collision.
Of course, basic SAT (Listing 4.2) is a very nonscalable algorithm. But in case
we have really simple shapes (for example, parallelepipeds (
Figure 4.9)
) with just
a dozen features, brute force is the fastest algorithm ever. A parallelepiped has
just three edge directions
a
,
b
,and
c
and three face directions
a
×
b
,
b
×
c
,and
c
a
to check. We need to normalize the directions and check both ends of each
direction. If we aren't interested in nonpenetrating shapes, we don't have to check
VV
,
VE
,and
EV
pairs. Even if we are interested in nonpenetrating shapes, we
can still skip checking vertexvertex pairs. We will not have the correct MTD, but
we'll have an approximation that's good enough for many purposes. As a side
note, the support function for a parallelepiped is very simple due to its specific
shape:
×
o
. If you have a general case polyhedron
with 812 vertices, it's still very fast to compute dot products with all vertices on
SIMD processors, four dot products at a time. In some cases, nothing beats brute
force, but for other cases, we discuss some optimizations in Section 4.7.

s
·
a

+

s
·
b

+

s
·
c

+
s
·
4.6.2 Step 2a: Supporting TwoDimensional Shapes—
LowPoly Case
There's no standard term for this, but it's a simple operation. We now found the
support plane (and, equivalently, separating axis or contact normal), and we need
to find the feature (point, line, or polygon) that lies in that plane.
When we have two shapes touching nontrivially, i.e., having an edge or a
polygon in close contact, we need to find several contact points representative of
that area of contact. For convex shapes, we can assume the same contact normal
across the whole contact area.
Lowpoly shapes are common in game physics, and they allow a specific lux
ury: they can rest on only one polygon and be stable (box versus highpoly curved
surface). In the simplest case of lowpoly shapes, e.g., stacked toy cubes, we just