Game Development Reference
SAT in Narrow Phase and
for objects colliding rather than sinking into each other. This chapter discusses
approaches to generation and optimization of contacts between polygonal meshes.
Collision detection often occurs in two phases. A first broad phase determines
whether two objects may potentially collide, then a subsequent narrow phase
determines exact separation or penetration and generates a contact manifold. The
solver stage follows and updates the simulated object states. The narrow phase
may consume a considerable share of processing time, and the stability of the
simulation and the speed of the subsequent solver stage depend directly on the
quality of the generated manifold. However, the narrow phase is well suited to
parallel computation, which can greatly improve execution time.
We present both approximate and exact algorithms for finding full contact
manifolds. Furthermore, we present a linear-time heuristic approach to finding a
dynamically stable subset of contact points. Next we present a linear complexity
SIMD algorithm for finding an approximate contact manifold using a direction
perturbation method, as well as a heuristic to reduce contacts (see Section 4.6).
Please refer to Tables 4.1, 4.4, and 4.5 for some notation used throughout this
4.2 Contact Manifold
When two rigid bodies are in contact, the force (or impact) direction is along
the surfaces' normals, or within the cone coaxial with the normal—the Coulomb
friction cone. Other friction models exist, but we don't consider them in this
chapter. The point of contact is where the forces or impulses are applied and