← Back
Home › Systems › Games

physics-engine

real-time physics engine

Box2D, Jolt, PhysX

Open the physics-engine pagephysics-engine Convex hull quickhullgeometry: Quickhull in 2D and 3D: robust convex hulls for collision shapes and geometryQuaternion rotationsgeometry: Unit quaternions as 3D rotations: 4 floats, cheap composition, no gimbal lock, plus the conversions, interpolation choices and numerical care needed in practice.›Ray primitive intersectiongeometry: Ray-triangle (Moller-Trumbore, watertight), ray-AABB slab and ray-sphere testsGraph coloringgraphs: Greedy/DSatur colouring for conflict-free assignment such as radio channelsUnion-findgraphs: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›SIMD programminghardware-os: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Semi-implicit Eulernumerics: Update velocity from forces first, then position with the new velocity: explicit Euler cost, but symplectic and stable; the default game-physics integrator.›Bounding volume hierarchyphysics: Binary tree of nested bounding boxes; prunes overlap and ray queries to O(log n) for any size distribution, and supports cheap insert/remove for moving objects.›Contact manifold generationphysics: Build persistent contact point sets from collision normals by clipping, with feature IDs for warm startsContinuous collision detectionphysics: Time-of-impact via conservative advancement or swept shapes to stop tunnelingGJK and EPAphysics: GJK decides whether (and how far apart) two convex shapes are from their support functions alone; EPA expands its simplex into penetration depth and normal.›Joint constraintsphysics: Hinge, ball, slider and motor constraints as Jacobian rows for impulse solversRigid-body dynamicsphysics: Advance one 3D rigid body per step from force and torque: semi-implicit Euler for position, an inertia tensor in the body frame, and quaternion orientation updated by the exponential map.›Separating axis theoremphysics: Convex shapes are disjoint iff some axis separates their projections; testing face normals and edge crosses gives overlap, depth and contact normal.›Sequential impulse solverphysics: Iterative contact solver applying impulses one constraint at a time with accumulated clamping and warm starting; the standard solver for stacking and friction in real-time physics engines.›Simulation islands sleepingphysics: Group touching bodies into islands, solve them independently and put resting islands to sleepSoft constraints substeppingphysics: Soft constraints with spring-damper parameters plus substepping (TGS, Box2D soft step) for stable stacksSpatial hashingphysics: Uniform grid stored in a hash table: bucket objects by cell, test only neighbouring cells; O(n) neighbour search for many similar-sized objects such as particles.›Sweep and prunephysics: Sort box endpoints along an axis and sweep: only intervals that overlap on that axis are tested; near-linear per frame thanks to temporal coherence.›Exact geometric predicatesgeometry: Robust orient and incircle tests with adaptive-precision floats (Shewchuk) or exact arithmeticFloating-point errornumerics: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.›d-ary heapdata-structures: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›BFS and DFSgraphs: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Fixed timestep loopgraphics: Fixed simulation dt with accumulator, render interpolation, spiral-of-death guardPolygon clippinggeometry: Polygon intersection/union/difference (Weiler-Atherton, Martinez) for spatial predicatesNewton root findingnumerics: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.›Rigid-body transforms (SE(3)poses)robotics: Represent, compose, invert, integrate and interpolate 3D poses as unit quaternion plus translation, with exp/log maps for small motions and uncertainty.›Fast hash functionsdata-structures: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Parallel prefix sumsearch-sort: Work-efficient scan (Blelloch, decoupled look-back) on CPU SIMD and GPUs; stream compactionSparse matrices (CSR)numerics: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›Point in polygongeometry: Ray-casting/winding tests and indexed polygon lookup for reverse geocodingLU and Cholesky factorizationnumerics: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›Homogeneous transformsgeometry: 4x4 affine and projective matrices, homogeneous coordinates, view and projection, normal matrices

How it is built

Architecture overview

A real-time physics engine advances a world of rigid bodies by a fixed time step, many times a second, and does it fast and stable enough for a game, a VR scene or a robot simulator to build on. Each step has the same shape: find which shapes touch (collision detection), turn the touches and the joints into constraints, solve the constraints for new velocities, integrate positions, and put resting bodies to sleep. The idea that makes it work is that nothing is solved exactly: contacts are solved one at a time and repeatedly (an iterative solver), last step's answers seed this step's (warm starting, persistent contact points), and independent groups of bodies (islands) are separated so that they can be solved in parallel or skipped when asleep. Box2D, Bullet, Jolt and Rapier all follow this skeleton; they differ in how they spend their time budget.

Parts:

 game loop ──dt──► ┌────────────────────────── one physics step ───────────────────────────┐
 (accumulator)     │ integrate velocities (forces, gravity)                                │
                   │        │                                                              │
                   │ broad phase ──pairs──► narrow phase ──manifolds──► contact cache      │
                   │  (BVH / SAP)           (SAT / GJK+EPA, clipping)   (warm-start data)  │
                   │                                                         │             │
                   │ constraints = contacts + joints ──► islands ──► colours ┤             │
                   │                                                         ▼             │
                   │                            solver: warm start → iterate / substep    │
                   │                                                         │             │
                   │ integrate positions ◄─────────── new velocities ◄───────┘             │
                   │ continuous collision (fast bodies) ──► sleep check ──► write poses    │
                   └───────────────────────────────────────────────────────────────────────┘
 queries (ray, shape cast, overlap) read the same broad phase between steps

The result is a library, not a program: the host app owns the loop, creates bodies and joints through an API, and reads poses back. That ownership split (who may touch bodies while a step runs) is the first contract to get right, see "Parallelism and ownership" below.

How the parts fit together

Time loop and integrator

Physics runs at a fixed step (the fixed-timestep-loop block, no page yet: accumulate frame time, run whole steps, interpolate the rendering) because the solver's stability depends on a constant dt. Rapier exposes dt as an integration parameter next to its solver and CCD settings (source: Rapier docs, integration parameters).

The integrator is Semi-implicit Euler: update velocity from forces first, then position from the new velocity. It costs the same as Explicit Euler but is symplectic, so energy does not drift upwards; a higher-order method such as RK4 would not help because the contact impulses are discontinuous and are applied once per step anyway. In 3D the state per body is a position, a quaternion (Quaternion rotations), linear and angular velocity and an inertia tensor (Rigid-body dynamics). Solver2D, a cut of Box2D v3, keeps a 2D rotation as a cosine/sine pair, a complex number (source: Catto, Solver2D post).

Broad phase

The broad phase turns "n bodies" into "a few candidate pairs" using only axis-aligned boxes. The choice is between a tree and a sorted list:

  • Bounding volume hierarchy: a dynamic tree of fat boxes. Box2D's documentation describes its dynamic tree as a BVH that can also serve game queries (source: Box2D docs), and Jolt's broad phase is a quad tree (BroadPhaseQuadTree, source: Jolt docs). Handles any size mix, supports ray and shape queries with the same structure, and inserting or removing a body is cheap.
  • Sweep and prune: sort box endpoints on an axis. Near-linear when most bodies are coherent from frame to frame, but it answers ray queries poorly and degrades when many objects line up on the sorted axis.
  • Spatial hashing: a uniform grid, best when all objects have similar size (particles, debris).

Why a tree is the default in the engines above: games mix a huge static level with small dynamic props, and a tree copes with both and doubles as the structure for queries. Contract with the narrow phase: a pair of body/shape ids, nothing more. A pair cache keyed by the two ids (hash: Fast hash functions) makes the step incremental: new pairs create contacts, vanished pairs destroy them.

Narrow phase and contact manifolds

For each candidate pair the narrow phase decides if the shapes overlap and, if so, produces a manifold: a contact normal plus up to a few contact points (2 in 2D; in 3D typically up to 4, order of). Two algorithm families:

  • Separating axis theorem: test face normals and edge-edge cross products; gives depth, normal and the features involved, which is what a manifold needs. Cheap for boxes and polygons.
  • GJK and EPA: works from a support function alone, so it handles spheres, capsules and convex hulls with one code path; EPA recovers penetration depth when GJK reports overlap.

The manifold itself comes from contact-manifold-generation (no page yet): clip the incident face against the reference face's side planes (polygon-clipping, no page yet), keep the points below the surface, and tag each point with a feature id. Convex hull shapes are built from vertex clouds with convex-hull-quickhull (no page yet), which needs the robust orientation tests of exact-geometric-predicates (no page yet) and care with Floating-point error.

The feature id is the contract with the solver: a point keeps its identity from step to step, so the solver can reuse its impulse (warm starting). Box2D describes this as contact recycling: bodies may move relative to each other without recomputing the manifold, which improves performance and stacking stability (source: Box2D docs). Jolt keeps a contact cache for the same reason (source: Jolt docs).

Continuous collision detection

A body moving farther than its own thickness in one step can pass through a thin wall. Box2D documents two remedies: interpolate the motion of two bodies to find the first time of impact, and speculative contacts that exist before bodies touch (source: Box2D docs). Jolt gives each body a motion quality: Discrete by default, LinearCast for fast small bodies, which sweeps the shape after the step and pulls it back to the first hit ("time stealing"); it states the weakness that fast rotation can still tunnel (source: Jolt docs). Rapier subdivides the step into CCD substeps, bounded by max_ccd_substeps and min_ccd_dt (source: Rapier docs). continuous-collision-detection (no page yet) combines shape casting from GJK and EPA, a root-finder for the time of impact (Newton root-finding, with a bracket for safety) and the broad phase for candidates. The price is a second pass over fast bodies only, so it is switched on per body, not globally.

Constraint solver

This is the heart, and the main place where engines differ. The default block is the Sequential impulse solver: visit each constraint, compute the impulse that fixes its relative velocity, clamp the accumulated impulse (not the increment), apply, move on; sweep a few times. Catto's Solver2D write-up lists the ingredients: warm starting, accumulated impulses and a small fixed iteration count (typically 4 to 8 for games, source: Catto, Solver2D post). Rapier's defaults are 4 solver iterations with 1 internal Gauss-Seidel iteration each (source: Rapier docs).

Why this and not the alternatives:

  • Complementarity (LCP/MLCP) contact solver (complementarity-contact-solver, no page yet): solves all contacts together, so it is exact for the model, but needs a global pivoting or large iterative solve with dense or sparse algebra (LU and Cholesky, Sparse matrices). Slower and less predictable per step, so it is the choice for engineering accuracy, not for a 16 ms budget.
  • Position-based dynamics (position-based-dynamics, no page yet): moves positions directly; very robust and easy to tune, but "stiffness" depends on iteration count and time step. Catto's Solver2D includes an XPBD solver among its eight (source: Catto, Solver2D post).
  • Soft constraints with substepping: the current Box2D approach. Contacts become spring-dampers described by a frequency in Hz and a damping ratio, solved with small sub-steps instead of many iterations; contact points are updated across sub-steps from local anchors without redoing collision. A relaxation pass without bias removes the energy the softness added (source: Catto, Solver2D post). The Box2D README names its solver "Soft Step". This is soft-constraints-substepping (no page yet), built on Semi-implicit Euler and the sequential-impulse core.

Joints (joint-constraints, no page yet) enter as extra rows with Jacobians that act on the same velocity vectors: Jolt lists fixed, distance, point, hinge, cone, slider, swing-twist, six-DOF, path and gear constraints (source: Jolt docs). Because joints and contacts share one solver, a ragdoll can stand on a box stack.

Rapier's block-solver feature solves the two normal constraints of a contact pair together as a 2x2 system (source: Rapier docs): a small direct solve inside an iterative loop, the cheapest taste of the complementarity alternative.

Islands and sleeping

Bodies that touch or share a joint form an island; static bodies do not connect islands. Islands are found by a graph traversal (Breadth-first and depth-first search) or incrementally with Union-find, as simulation-islands-sleeping (no page yet) describes. Jolt builds islands from active constraints every step, and puts the whole island to sleep when all bodies are at rest, controlled by mTimeBeforeSleep and mPointVelocitySleepThreshold; sleeping bodies still detect contacts with awake bodies and wake when touched (source: Jolt docs). Jolt deliberately does not wake neighbours when a body is removed or created, because accidental wake-ups hurt loading performance (source: Jolt README).

Parallelism and ownership

Within an island, Gauss-Seidel is sequential: each constraint reads the result of the previous one. Two ways out:

  • Across islands: free parallelism, one island per task.
  • Within one big island: graph-coloring (no page yet): assign each constraint a colour so that no two constraints of the same colour share a dynamic body. All constraints of one colour can then be solved at the same time, and in a SIMD register. Catto lists graph colouring, multithreading and SIMD among Box2D v3's features (source: Catto, Solver2D post). Rapier's solver processes 4 contact manifolds per instruction (8 with the simd8 feature) (source: Rapier docs); see SIMD programming. Colouring changes the solve order, so the result differs from a sequential sweep, and constraint order has to be fixed if the simulation must be deterministic.
  • Compacting active constraints into per-colour arrays is a scan problem (parallel-prefix-sum, no page yet) on wide hardware.

Ownership during a step is part of the API. Jolt's body interface comes in locking and non-locking variants, forbids reading or writing bodies while PhysicsSystem::Update runs, calls contact listeners from several threads and lets collision queries run in parallel with adding or removing bodies (source: Jolt docs and README). Rapier has a parallel feature (rayon) and an enhanced-determinism feature for cross-platform determinism (source: Rapier docs). Jolt documents conditions for determinism: same call order, same binary (source: Jolt docs).

Queries

Ray casts, shape casts and overlap tests read the broad phase tree and then the narrow phase shapes (Box2D lists them as separate collision routines usable without rigid-body simulation, source: Box2D docs). Ray-shape tests (ray-primitive-intersection, no page yet) are the same primitives as a renderer's.

Data and control flow

One step (dt = 1/60 s):

  1. Apply forces and gravity to velocities (semi-implicit Euler, first half). Reads: bodies; writes: velocities.
  2. Update the broad phase for moved bodies; collect new and removed pairs. Cost grows with moved bodies, not with all.
  3. Narrow phase on touched pairs: manifolds with feature ids; merge with last step's impulses by feature id.
  4. Build islands from contacts and joints; skip sleeping islands; colour constraints inside large islands.
  5. Warm start: apply last step's accumulated impulses. Then iterate (or substep): per constraint compute, clamp the accumulated impulse, apply. Most of the step time is here (order of: the largest single share in stacking scenes; profile your own scene).
  6. Integrate positions; CCD pass for fast bodies; position correction or relaxation.
  7. Store impulses in the contact cache; test islands for rest; publish poses.

One ray cast (between steps):

  1. Walk the broad-phase tree, visiting nodes whose box the ray hits, nearest first.
  2. For each leaf shape, run the ray-shape test; keep the closest hit.
  3. Return the shape, point and normal.

Time is dominated by the solver and, in open worlds with many static bodies, by broad-phase and narrow-phase work on moving bodies near terrain.

Scaling

In the order you would pull the levers:

  1. Fewer active bodies: sleeping, collision layers and filters so that pairs are never created, simpler shapes (a sphere or capsule instead of a mesh; Jolt orders shapes by computational complexity, source: Jolt docs).
  2. Cheaper solver settings: fewer iterations or substeps, soft contacts, fewer friction points per manifold.
  3. SIMD over constraints (colour them first): 4 to 8 lanes (source: Rapier docs for the lane counts).
  4. Threads: islands first, colours inside big islands, with the order of work fixed if you need determinism.
  5. Large worlds: stream sections in and out in batches on background threads (Jolt's stated design goal, source: Jolt README) rather than a bigger single world.
  6. Different physics for huge counts (particles, cloth, fluids): position-based or grid methods and Spatial hashing instead of the rigid-body pipeline.

Failure modes

FailureSymptomCauseFix
Tunnellingfast bullet or thin wall ignoredmovement larger than thickness in one stepCCD for that body, speculative contacts, thicker walls
Stack jitter or collapseboxes vibrate, tall stacks slumpno warm starting or per-iteration clamping, too few iterations or substepsaccumulated impulses, warm start by feature id, more substeps
Energy gain on overlapbodies pop apart explosivelyBaumgarte-style position fix feeds velocitysoft constraints, relaxation pass, cap the push-out speed
Large mass ratio instabilitylight body crushed by a heavy one, chains stretchGauss-Seidel converges slowly on stiff ratioskeep ratios modest, substep, joint softness, direct solver for the chain
Time-step dependencebehaviour changes with frame ratevariable dt fed into the solverfixed step with an accumulator, interpolate the render
Ghost collisionsbody hits an invisible bump on a flat floorcontact with the internal edge between two shapes or mesh trianglesedge-aware mesh shapes, contact filtering (Jolt docs: ghost collisions)
Non-determinismreplay or lockstep desyncsdifferent call order, thread order, compiler or CPUfixed call order, same binary, deterministic mode
Waking stormframe spike when loading contentbody creation or removal wakes neighboursdo not wake on add or remove (Jolt's default), wake explicitly
Degenerate geometryNaN, explosion or no contactzero-area faces, bad hull, rounding in predicatesvalidate shapes at build time, exact predicates, floating-point care

Real implementations

namewhat it isrepolicencenotes
Box2D2D engine; v3 uses soft constraints, substepping, graph colouring, islands, CCDerincatto/box2dMITSolver2D is the author's solver test bed
BulletC++ SDK for collision detection and multi-physics; PyBullet bindings for robotics and RLbulletphysics/bullet3zlib (LICENSE.txt, except Extras and third-party examples)the README recommends PyBullet
Jolt Physicsmulti-core 3D engine: quad-tree broad phase, islands, LinearCast CCD, deterministic modejrouwe/JoltPhysicsMITREADME names Horizon Forbidden West and Death Stranding 2 as users
RapierRust 2D/3D engine with SIMD solver, optional parallel and enhanced-determinism featuresdimforge/rapierApache-2.0docs list the feature flags used above

Sources

Similar systems

Share the most building blocks with this one.

robotics-sim 25 %realtime-cloth-fluid 17 %crash-sim 16 %