Game Development Reference

In-Depth Information

4.7.4 SAT versus GJK

A major advantage of SAT over GJK is that SAT works great for penetrating

shapes. In fact, SAT works better in the penetrating case than in the separated

shape case because there's no need to check vertex-vertex feature pairs if shapes

penetrate (see, for example,
Figure 4.21(a)
)
.

A major disadvantage of SAT is its inherently slower asymptotic convergence

rate. The GJK formulation is convex and implicit, so there is one and only one

local minimum, which is a global minimum, too. And GJK needs only support

mapping, it doesn't need features (edges, faces, connectivity), so implicit surfaces

work just as well, and it's possible to stop when the solution is “close enough”

(when the Minkowski sum support is within a small range of the simplex). SAT,

on the other hand, solves potentially every concave problem with a lot of local

optima. The Minkowski sum in Figure 4.21(b) has at least six local maxima, for

example.

4.7.5 SAT versus EPA

EPA obtains the global minimum and is probably the best-known and widely used

algorithm for finding a true MTD. It can also be warm-started with GJK. SAT

doesn't require a priority queue data structure, so it may be more suitable for

hardware with limited/slow conditional branching (like a GPU). It is also arguably

much simpler to implement, especially without the optimizations, so it may run

faster on very simple shapes (cube, octahedron).

4.7.6 SAT versus Xenocollide or Dual-CD

Both the Xenocollide [Snethen 08] and Dual-CD [Choi et al. 05] algorithms ulti-

mately cast a ray from inside the Minkowski sum, find where the ray intersects the

boundary, and thus detect the penetration distance in the given direction. It's pos-

sible to iterate the direction, but both algorithms perform a local search, whereas

SAT finds the global minimal translation distance. Sometimes we may prefer one

or the other, but when we prefer the MTD, SAT may be better.

4.8 Acknowledgments

I would like to extend a special thanks to my wife, Anna Bibikova, for her support

and tremendous help with illustrations.

An algorithm similar to the one described here was used in the awesome

PlayStation
R

3 title
Uncharted: Drake's Fortune
that sold one million copies in