Game Development Reference

In-Depth Information

Figure 4.4.
Separating directions
s
, support features
F
, and support planes
P
: (a) contin-

uum of separating planes and (b) support planes.

4.4 SAT Basics

SAT states that two convex shapes
A
and
B
are disjoint if and only if there is a

plane that separates them:

⎧

⎨

s

·

x

−

d
S
=0
,

||

s

||

=1

Separating plane (SP),

s

·

x
A
−

d
S
≥

0
,
x
A
∈

AA
in front of SP,

⎩

BB
behind SP
.

Let's call
s
the separating direction.
2
Note that for strictly disjoint shapes, there is

a continuum of separating planes: there are many possible values for both
s
and

Let's call the plane
s

s

·

x
B
−

d
S
≤

0
,
x
B
∈

·

x

−

d
A
=0touching
A
the
support plane
of
A
in

direction
s
,or

P
A
(
s
):

s

·

x
A
−

d
A
≥

0
,

∀

x
A
∈

AA
in front of

P
A
(
s
),

(4.1)

∃

x
A
:
s

·

x
A
−

d
A
=0

P
A
(
s
) must touch
A
.

P
B
(

−

And let's consider

s
) to be

s

·

x
B
−

(

−

d
B
)

≤

0
,

∀

x
B
∈

BB
in front of

P
B
(

−

s
),

(4.2)

∃

x
B
:
s

·

x
B
−

(

−

d
B
)=0

P
B
(

−

s
) must touch
B
.

Denote the minimal translation distance (MTD) and direction as

2

(
d
min
,
s
min
)=su
d
{

(
d,
s
):
s

∈
S

}

.

(4.3)

2
Without loss of generality, we assume that
||
s
||
=1
.