Game Development Reference
In-Depth Information
( s min ,d min ) ( o , −∞ )
for each face A F ( A ) do // check FV ⊃ FE∪ FF
checkDirection( n ( face A ) )
for each face B F ( B ) do
// check VF ⊃ EF ∪ FF
n ( face B ) )
for each edge A E ( A ) and edge B E ( B ) do // check cases EE
s e ( edge A ) × e ( edge B )
checkDirection( s ) // to choose one of ± s ,
checkDirection( s ) // ... see Equation 4.9
if d min 0 then // penetrating case
return ( s min ,d min ) // skip VV , VE , EV
for each v A V ( A ) and v B V ( B ) do
checkDirection(
// check cases VV
checkDirection( v A v B )
for each v A V ( A ) and edge B E ( B ) do // check cases VE
if proj ( v A ,edge B ) ∈ edge B then // optimization
checkDirection ( v A proj ( v A ,edge B ))
for each edge A E ( A ) and v B V ( B ) do // check cases EV
if proj ( v B ,edge A ) ∈ edge A then // optimization
checkDirection ( proj ( v B ,edge A ) v B )
return ( s min ,d min )
procedure checkDirection( s )
if || s || =0 then // ignore degenerate cases
s norm ||·|| ( s )
d ← support ( A, s )+ support ( B,− s )
if d>d min then
( s min ,d min ) ( s ,d )
function support( Shape , s )
return min{ s · v : v V ( Shape ) }
Listing 4.2. Basic SAT algorithm.
4.4.3 Negating Shape
B
Normals
We should never forget about asymmetry anytime we are dealing with shapes A
and B . By this chapter's convention, direction s is used to find
P A ,but
s is used
to find
P B . See Figure 4.4(b)—the support features
F A and
F B always oppose

Custom Search