Overview

Most popular Game Physics Engines (Havok, Box2D, Bullet, PhysX) work in a rather similar way. A world, consisting of rigid bodies, is simulated in an endless loop, advancing time by some interval (often 1/60s = 16.7ms) in every iteration. In each iteration, forces act on bodies, thereby determining their acceleration and changing the velocity, leading to collisions; these are then resolved by adding constraint impules (velocity changes), and finally, the new body positions and orientations are computed. The calling code can then use the new positions to redraw the world. Each time step starts at a known configuration for each body - consisting of position, orientation, linear and angular velocity. A time step consists of the following calculations:

  1. Collision Detection: detect what bodies penetrate and how. This consists of two or more phases, at least
    • a fast broad phase identifying potentially colliding pairs (axis-aligned bounding boxes - AABBs - are a popular choice)
    • a narrow phase that determines collision pairs and the involved vertices and surfaces.
  2. For each body, infer its acceleration from Newton's formula, \mathbf{a}=\mathbf{M}^{-1}\mathbf{f}. The most common force is due to gravity, but spring and friction forces are also used. Note acceleration includes linear and angular acceleration; the force vector includes both the force and the implied torque; more about this in the next section. These accelerations are integrated to obtain a velocity prediction \mathbf{v} for each body - \mathbf{v} := \mathbf{v} + \Delta t \mathbf{a}.
  3. Velocity-based constraint equations - more on this soon - are set up. Constraints usually include
    • collision constraints (both resting and colliding contacts are treated identically), one or more for each pair of colliding bodies and other constraints. E.g., a box (in 2D) falling onto another box may lead to two contact points, resulting in 2 constraint equations.
    • distance constraints (joints as for doors, or ropes)
    • motors, friction etc.
  4. in a loop (about 4 iterations), the engine iterates over all constraint equations sequentially, for each computing impulses \mathbf{P} necessary to satisfy the constraint, and applies them to arrive at a new tentative velocity (\mathbf{v} := \mathbf{v} + \mathbf{M}^{-1}\mathbf{P})
  5. finally, new positions are computed based on the corrected velocities (\mathbf{x} := \mathbf{x} + \Delta t \mathbf{v})