Resolving Rigid Body Stacking Loops in Game Physics

Simulating stacked rigid bodies in game development frequently leads to circular physical dependency loops, where constraints between contacting bodies cyclically depend on one another. This article examines the computational techniques used to resolve these loops and stabilize stacks, including iterative constraint solvers, shock propagation, contact graph hierarchies, Position-Based Dynamics, and Linear Complementarity Problem (LCP) formulations.

Iterative Solvers and Sequential Impulses

Most modern real-time physics engines (such as PhysX, Havok, and Jolt) resolve cyclic contact loops using iterative solvers based on the Projected Gauss-Seidel (PGS) method or Sequential Impulses. Instead of calculating the global force distribution simultaneously, the engine processes each contact constraint independently across multiple iterations per time step.

In a circular dependency—such as an arch or a ring of resting blocks—each iteration propagates momentum incrementally through the loop. By clamping impulses to prevent negative (attractive) normal forces and applying successive over-relaxation (SOR), the solver converges toward a stable resting state without needing to invert a global system matrix.

Shock Propagation

Iterative velocity solvers can suffer from noticeable jitter or "sponginess" when resolving deep or cyclical stacks. Shock propagation breaks loops by imposing an artificial directional hierarchy onto the contact network:

  1. The solver identifies ground-supported bodies and treats them as having infinite mass during a dedicated stabilization pass.
  2. Forces are propagated strictly upward through the contact graph, treating lower bodies as static foundations for the bodies directly above them.
  3. Once the upward pass completes, the temporary mass modifications are removed, effectively damping cyclic feedback and eliminating settling artifacts.

Contact Graph Partitioning and Tree-Decomposition

Physics engines build contact graphs where rigid bodies represent nodes and contacts represent edges. Circular dependencies appear as cycles or strongly connected components within this graph.

Engines isolate these cycles by partitioning the graph into distinct "islands." If a cycle creates instability, the engine can temporarily break cycles by computing a minimum spanning tree of the contact graph, resolving primary compressive forces along the tree edges, and applying friction and secondary constraints as weak correction terms.

Position-Based Dynamics (PBD) and XPBD

Position-Based Dynamics avoids the momentum accumulation typical of velocity-force-based solvers by manipulating positions directly. In Extended Position-Based Dynamics (XPBD):

  • Penetration and resting conditions are framed as non-linear geometric constraints.
  • The solver projects body positions and orientations directly onto valid non-penetrating states iteratively.
  • Because XPBD couples constraint stiffness directly to time steps independently of solver iterations, circular loops dissipate kinetic energy rapidly rather than amplifying it into explosive instabilities.

Direct Linear Complementarity Problem (LCP) Solvers

For scenarios requiring absolute mathematical precision without iterative drift, engines can model the contact loop as a mixed Linear Complementarity Problem (MLCP).

Direct pivoting algorithms (such as Lemke's algorithm) or block-based interior point solvers solve the entire constraint matrix simultaneously. While computationally expensive (\(O(n^3)\) worst-case complexity), direct solvers eliminate the feedback loops inherent in circular dependencies by finding a globally optimal set of non-interpenetrating contact impulses in a single solve. Many game engines reserve this method for small, isolated sub-assemblies.

Velocity Clamping and Sleep Thresholds

In production environments, algorithmic solutions are paired with heuristic stabilization:

  • Contact Caching (Warm Starting): Impulses calculated in the previous frame seed the next frame's solver, allowing cyclic networks to remain stable across frames.
  • Aggressive Velocity Clamping: Micro-velocities resulting from solver oscillations are zeroed out before they propagate into the next time step.
  • Island Sleeping: When the aggregate kinetic energy of a closed contact island falls below a defined threshold, all participating rigid bodies are deactivated simultaneously to prevent perpetual jitter within the loop.