Game Development Reference

In-Depth Information

-4-

SAT in Narrow Phase and

Contact-Manifold Generation

Sergiy Migdalskiy

4.1

Introduction

Collision detection is a large part of physics simulations
(
Figure 4.2
)
, responsible

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

chapter.

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