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
d S (see Figure 4.4(a) ) .
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 .