Game Development Reference
4.4.2 SAT Algorithm
While s min defines support features, the opposite also happens to be true. For var-
ious reasons, a feature pair may only correspond to one possible ( s min ,d min ) (see
Table 4.3 ) if it is in fact the support-feature pair in MTD. The basic SAT algorithm
enumerates every feature pair and checks whether that feature pair realizes MTD
by finding the one with the highest d min . Many (most, actually) feature pairs
cannot possibly be the supporting-feature pairs in MTD. Finding and eliminating
these pairs is a major source of SAT optimizations.
There are just nine possible combinations of
F A ( s ) and
F B (
s ) to consider,
since a feature can only be a vertex ( V ), edge ( E ), or face ( F ). Three of them
are completely redundant: face-face ( FF ), edge-face ( EF ), and face-edge ( FE )
are special cases of the face-vertex ( FV ) and vertex-face ( VF ) variety and yield
the same ( s min ,d min ). Edge-edge ( EE ) is a degenerate case if the edges are
parallel. Degenerate EE is the special case of either the edge-vertex ( EV )or
vertex-edge ( VE ) variety, which in turn may be a vertex-vertex ( VV ) case. (See
( s min ,d min ).
FF , FE , EF
always a special case
FV , VF
parallel edges, e A e B
EV , VE , VV
VE , EV
VF , FV
vertex is inside the other shape's edge
VE , EV
vertex is on the edge line outside the edge
coinciding vertices, v A = v B
FV , VF , EE
Ta b l e 4 . 2 .
Special and degenerate case classes.
Each nondegenerate feature pair corresponds to just one possible support di-
rection s . This limits the set of potential MTD directions.
Ignoring special cases restricts all possible directions for s min to the classes
enumerated in Table 4.3. The basic SAT algorithm is to evaluate ( s ,d ) for every
feature pair and find the best (maximum) one. Basic optimizations aim at reduc-
ing the number of feature pairs and at reducing the cost of evaluating d , since it
involves computing support planes.
There are generally just three classes of support-feature pairs possible for
This means we only need to consider directions along face normals and edge-pair
cross products to find s min in the colliding case. This restricts Equation (4.3) to
4 Proof is out of the scope of this article.