Projected Gauss-Seidel (PGS) Solver

PGS operates by sequentially processing constraints one at a time. Unlike batch methods that solve all constraints simultaneously, it updates the solution for a single constraint and immediately uses that result for the next. This local propagation often converges faster for contact-dominated problems. The core update for a constraint i is:

• delta_lambda = (b_i - sum(a_ij * lambda_j)) / a_ii
• lambda_i_new = clamp(lambda_i_old + delta_lambda, lower_bound, upper_bound) where lambda is the constraint impulse (e.g., contact force) and clamping enforces bounds like non-penetration.

The "Projected" in PGS refers to the operation that enforces physical bounds on the solution. After each local Gauss-Seidel update, the computed value is projected (clamped) onto a feasible interval. For contact constraints, this typically means:

• Normal forces are projected onto [0, +inf) to prevent adhesive forces (no pulling).
• Friction forces are projected onto a Coulomb friction cone [-mu * lambda_normal, +mu * lambda_normal]. This projection is what guarantees a physically plausible solution, ensuring objects push apart but do not stick together.

PGS is specifically designed to solve Linear Complementarity Problems (LCPs), the mathematical formulation of rigid body contact with friction. An LCP states that for contact i:

• lambda_i >= 0 (force must be non-negative)
• v_i >= 0 (relative velocity at contact must be non-penetrating)
• lambda_i * v_i = 0 (complementarity: either force is zero or velocity is zero) PGS finds an approximate solution to this hard problem through iterative projection, making it more robust and faster than direct LCP solvers for real-time applications.

A key performance optimization in PGS is warm starting. The solver reuses the impulse (lambda) values from the previous simulation time step as the initial guess for the current step. Since object positions and contacts change relatively slowly between frames (typically 60Hz or 120Hz), the previous solution is often very close to the new one. This drastically reduces the number of iterations required for convergence, which is critical for maintaining real-time performance in games and interactive simulations.

PGS is favored in real-time engines for its speed and stability, but trades off some accuracy.

• Vs. Direct Methods (e.g., Pivoting LCP Solvers): Direct methods are more accurate but have unpredictable O(n³) worst-case time, unsuitable for real-time. PGS offers predictable O(n) per iteration.
• Vs. Jacobi Methods: A Jacobi solver updates all constraints in parallel using values from the previous iteration. It's more parallelizable but converges slower per iteration than Gauss-Seidel's sequential updates.
• Vs. Newton Methods: Newton-based solvers (like Sequential Impulse, which is similar to PGS with a full Jacobian) can have faster convergence but may require more complex matrix setups.

PGS is versatile and used to solve various physics constraints:

• Contact Constraints: Preventing inter-penetration and modeling friction.
• Joint Constraints: Restricting degrees of freedom between bodies (e.g., hinges, sliders, ball joints).
• Ragdoll Constraints: Keeping bones within anatomical limits.
• Soft Constraints: Such as springs or motors, where bounds may be elastic limits or torque limits. The same iterative, bounded solving loop applies, with the Jacobian matrix J defining how each constraint affects body velocities and the effective mass matrix JM⁻¹Jᵀ forming the a_ii term in the update rule.

PGS is the foundational solver in many real-time game physics engines, such as NVIDIA PhysX and Bullet Physics. Its sequential, iterative nature provides predictable performance and robust handling of stacked objects and persistent contacts, which are common in gameplay scenarios. Key advantages include:

• Stability with large time steps: Tolerates the variable frame rates common in games.
• Warm starting: Uses solutions from previous frames to converge faster.
• Handling of inequality constraints: Efficiently manages non-penetration and friction without solving a full global system matrix.

In sim-to-real transfer learning, physics engines like Isaac Sim and MuJoCo utilize PGS and its variants to simulate contact-rich environments for training robotic policies. It is critical for modeling:

• Grasping and manipulation: Solving contact forces between grippers and objects.
• Legged locomotion: Resolving foot-ground interactions for walking and running robots.
• Articulated systems with joints: PGS efficiently handles the mixed constraints of joint limits and contact forces simultaneously, which is essential for simulating complex robotic mechanisms before real-world deployment.

For applications requiring direct user interaction with simulated objects—such as virtual prototyping, digital twins, and interactive design tools—PGS provides the necessary stability. Its projection step ensures constraints like non-penetration are strictly enforced, preventing objects from sinking into each other even under persistent user-applied forces. This makes it ideal for simulating:

• Particle systems and granular materials (when combined with constraint-based formulations).
• Complex assemblies of rigid parts connected by joints.
• Puzzle-like interactions where stability is more critical than absolute physical accuracy.

While Position-Based Dynamics (PBD) is often used for real-time deformables, PGS is employed in constraint-based approaches to simulate cloth, ropes, and soft bodies. In this context, distance constraints (to maintain edge lengths) and bending constraints are solved iteratively. The projection in PGS directly corrects vertex positions to satisfy these constraints, making it effective for:

• Real-time garment simulation on characters.
• Flag and cable dynamics.
• Interactive soft object manipulation where two-way coupling with rigid bodies is required.

PGS is a specific iterative method for solving the Linear Complementarity Problem (LCP) formulation of contact physics. It addresses problems of the form Ax + b = w, where x ≥ 0, w ≥ 0, and x⋅w = 0 (the complementarity condition). This mathematically captures the "non-penetration and non-adhesion" nature of contact. PGS solves this by:

• Sequentially processing each constraint (contact point).
• Projecting the solution for that constraint onto its feasible set (e.g., force must be non-negative).
• Updating the system's velocity/force estimates, which influences subsequent constraint solves in the same iteration.

PGS is chosen over other numerical solvers based on the requirements of the application:

• vs. Direct Solvers (e.g., Pivoting Methods): PGS is iterative and approximate but offers O(n) complexity per iteration and better stability for ill-conditioned systems (e.g., large mass ratios). Direct solvers are exact but can be O(n³) and fail on indefinite systems.
• vs. Gradient-Based Methods: PGS is a specialized successive over-relaxation (SOR) method for LCPs, often more robust for contact problems than generic gradient descent.
• vs. Its Variants: Sequential Impulse (SI) is a nearly identical method often used synonymously. Extended PGS (XPGS) and PGS with Shock Propagation are enhancements that improve convergence for challenging stacks and loops of constraints.

A constraint solver is the algorithmic core of a physics engine responsible for calculating forces and impulses to satisfy physical constraints. These constraints define relationships between bodies, such as:

• Contact constraints preventing interpenetration.
• Joint constraints like hinges or sliders that limit relative motion.
• Stability constraints for numerical integration. The solver's objective is to find a set of forces that satisfy all constraints simultaneously, often formulated as a large system of equations or inequalities. PGS is one specific iterative method used to solve this problem efficiently.

A Linear Complementarity Problem (LCP) is the formal mathematical framework underlying many rigid body contact and friction models. It is expressed as finding vectors w and z such that: w = Mz + q, w ≥ 0, z ≥ 0, and wᵀz = 0.

• M is a matrix capturing system inertia and constraint geometry.
• q is a vector of relative velocities and biases.
• The complementarity condition wᵀz = 0 enforces that forces (z) are only applied when there is no separation (w). PGS is a robust, iterative algorithm for approximating solutions to the LCP, especially suited for large systems with many contact points where direct solvers are too slow.

Sequential Impulse is a closely related iterative solver technique popularized by Erin Catto for real-time physics. It operates by:

• Processing constraints one at a time.
• Calculating an impulse that partially satisfies the current constraint.
• Immediately applying that impulse to the involved bodies' velocities.
• Cycling through all constraints repeatedly until convergence. PGS can be viewed as a specific implementation of the sequential impulse idea with a formal projection step that ensures solutions stay within feasible bounds (e.g., non-negative normal forces). This method is prized for its simplicity, stability, and ease of warm-starting from a previous frame's solution.

The contact model defines the physical laws governing collisions. A PGS solver typically implements a velocity-level model with Signorini's condition and Coulomb friction. Key components are:

• Non-penetration: Relative normal velocity must be non-negative (objects separate or rest).
• Newton's restitution: A coefficient models energy loss during collision.
• Coulomb friction: Tangential force magnitude is bounded by the normal force times a friction coefficient. PGS solves for normal and frictional impulses concurrently, projecting solutions onto a friction cone approximation (often a pyramidal or linearized cone) to satisfy these coupled constraints.

In the context of constraint solving, the Jacobian matrix is a fundamental mathematical object. For each constraint, the Jacobian J is a matrix that:

• Maps the applied constraint force (a scalar or small vector) into the force/torque space of each affected body.
• Relates body velocities to the constraint's relative velocity: v_rel = J * v. Within the PGS formulation, the system matrix M in the LCP is built from the mass-inertia matrices of the bodies and the Jacobians of all active constraints. Constructing and using these Jacobians efficiently is critical for solver performance.

PGS is an iterative solver, contrasting with direct solvers like those based on matrix factorization (e.g., LDLT). Their trade-offs are significant for simulation:

Iterative (PGS):

• Pros: Lower per-iteration cost, memory efficient, naturally handles indefinite systems, easy to warm-start.
• Cons: Provides an approximate solution; convergence can be slow for ill-conditioned systems.

Direct Solvers:

• Pros: Provide an exact (to numerical precision) solution in a fixed number of steps.
• Cons: Higher computational and memory cost (O(n³), O(n²)), struggle with changing constraint topology.

PGS is favored in real-time applications (games, robotics sim) where speed and robustness are prioritized over absolute precision.