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