# 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}$)
• You might find the order above a bit weird - why not predict velocities and position first, then compute collisions, instead of the other way around. Different engines handle this in different manners - Box2D (see Erin Catto's GDC2009 presentation) and PhysX (see Richard Tonge's GDC2013 slides, slide 29]) use the above order, while Erwin Coumans' Bullet (GPU Rigid Body Simulation, slide 13) seems to predict both velocity and positions, then perform collision detection + constraint solving, followed by re-computing the positions)
• In the following, I am first going to give a very concise but complete introduction to unconstrained 2D rigid body motion (steps 2 and 5 of the above algorithm); this forms the basis for the next chapter how equality constraints (joints, pendulums, ...) are handled by sequential impulse solvers (steps 3 and 4). Then, inequality constraints - specifically, collisions - are dealt with, including a brief treatment of the theoretical connection to the Linear Complementarity Problem (LCP) (also 3 and 4). Finally, I'll very briefly describe the collision detection algorithm I use (step 1).
• This tutorial is heavily based on Erin Catto's awesome GDC2009 presentation and the accompanying Box2D Lite source code - by far the best and most intuitive I found on the subject of dealing with inequality constraints. Yet, I thought that there are some steps that could benefit from a more detailed explanation, in particular, a complete derivation of the formulas for collision constraints. I had to infer some details from the source code so I thought I'd write them down and show them in a Javascript demo. Also, being able to play with the parameters in a browser - no need for Matlab, or Visual Studio - might be instructive.