Game Development Reference

In-Depth Information

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

Table 4.2.
)
We can just skip and ignore all special cases for the purposes of finding

(
s
min
,d
min
).

Case

Degeneracy Condition

General Cases

FF
,
FE
,
EF

always a special case

FV
,
VF

EE

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

VV

VV

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.