Collision detection

Computational methods for determining when two or more shapes are intersecting either statically (right now) or predictively (in the future). In technical terms, a posterior and a priori respectively. Detecting and reacting to collisions is extremely important in videos games and physical simulations, and takes quite a lot of brains and computational muscle to do effectively in real-time, especially in large-scale systems.

Building your own collision detection code is a fun and educational exercise, but is so complex and difficult to achieve in practice that it is generally a good idea to use an establisihed physics library or VFX/modelling application for performance. See the Physics engine and Tools sections for options.

Relevant topics:

• Broad phase - class of algorithms that detect pairs of potentially colliding shapes using fast but approximate methods, such as:
  • Axis-aligned bounding box (AABB)
  • Sort and sweep (a.k.a. sweep and prune)
  • Bounding volume hierarchy (BVH)
• Narrow phase - class of algorithms that determine if two shapes are definately intersecting or not, and by how much.
  • Separating axis theorem (SAT)
  • Gilbert-Johnson-Keerthi (GJK) algorithm
  • Expanding Polytope Algorithm (EPA)

Articles:

• Collision detection on Wikipedia
• Video Game Physics Tutorial - Part II: Collision Detection for Solid Objects by Nilson Souto
• Let's talk about broad phase by Stanislav Pidhorskyi

Books:

• Real-Time Collision Detection by Christer Ericson