Constraint Solver

The solver's first task is to mathematically define the constraints that must be satisfied. These are typically expressed as equality or inequality equations.

• Equality Constraints: Enforce exact relationships, like a ball-and-socket joint where two points on different bodies must coincide.
• Inequality Constraints: Enforce one-sided limits, such as contact non-penetration (the distance between bodies must be >= 0) or joint angle limits.
• The Jacobian matrix is constructed to linearize these constraints, relating small changes in system state to changes in constraint violation.

Constraint problems are often formulated as a Linear Complementarity Problem (LCP) or a system of equations that is solved iteratively.

• Solvers like the Projected Gauss-Seidel (PGS) or Sequential Impulse method apply small corrective impulses over multiple iterations to gradually reduce constraint error.
• Warm starting uses the solution from the previous time step as an initial guess, dramatically improving convergence speed for contacts that persist across frames.
• The process runs for a fixed number of iterations or until the total constraint error falls below a specified tolerance, balancing accuracy with computational cost.

A primary function is resolving collisions, which involves two coupled sub-problems.

• Normal Force Resolution: Calculates impulses along the contact normal to prevent penetration and model restitution (bounciness).
• Friction Force Resolution: Models Coulomb friction tangentially to the contact surface. The solver finds forces within the friction cone to simulate sticking and sliding.
• These are solved simultaneously to ensure physically plausible behavior, such as a box tipping over instead of sliding unrealistically.

Numerical integration errors can cause constraint drift, where bodies slowly penetrate or joints separate. Solvers employ stabilization methods to counter this.

• Baumgarte Stabilization: Adds a corrective term proportional to both the position error and velocity error of the constraint, acting like a virtual spring-damper to pull the system back to a valid state.
• Position-Based Dynamics (PBD) methods directly correct particle positions to satisfy constraints, inherently avoiding drift but differing from force-based physics.
• These techniques are crucial for long-duration simulation stability, especially in complex articulated systems.

Real-world systems like humanoid robots or complex machinery often have over-constrained or singular configurations.

• Redundant Constraints: Occur when multiple constraints try to enforce the same or conflicting motion (e.g., two arms pushing on the same object). The solver must distribute forces intelligently, often using a weighted scheme.
• Kinematic Singularities: In articulated chains, these are configurations where the Jacobian loses rank, leading to unrealistic force spikes. Robust solvers detect and handle these cases, often by damping or constraint prioritization.
• This ensures the simulation remains stable even in edge-case poses.

For use in training and real-time applications, solvers must be fast and predictable.

• Determinism: Identical inputs must produce identical outputs. This is non-negotiable for reproducible robotic training in simulation. Solver iteration count and order of constraint processing are carefully controlled.
• Parallelization: Modern solvers exploit SIMD instructions and parallel processing for independent constraint groups to achieve the high step rates (often 1kHz+) required for stable robotic control.
• The choice between a single large solve and smaller, decoupled solves is a key architectural decision impacting performance and stability.

A Linear Complementarity Problem is the primary mathematical framework for modeling contact and friction in many physics engines. It formulates constraints such that forces are non-penetrating (normal force ≥ 0) and non-adhesive (force * penetration = 0). The constraint solver's core task is to solve this LCP each time step.

• Key Condition: 0 ≤ force ⟂ penetration ≥ 0 (complementarity).
• Solver Role: Finds the set of contact forces that satisfy all complementarity conditions simultaneously.
• Example: Determines if a box is sliding (friction force active) or sticking (static friction) on an inclined plane.

Baumgarte Stabilization is a numerical technique used to reduce constraint drift, the accumulation of small errors that cause simulated joints to separate or bodies to unnaturally penetrate over time. It adds a corrective term to the constraint equation.

• Mechanism: Adds -(β * positional error + γ * velocity error) to the constraint force calculation.
• Purpose: Acts like a virtual spring-damper, gently pulling the system back to a valid state.
• Trade-off: High stabilization factors can make the simulation appear "springy" or overly stiff.

Warm starting is an optimization where the impulse or force solution from the previous physics time step is reused as the initial guess for the iterative solver in the current step. This dramatically improves convergence speed.

• Analogy: Like using yesterday's weather to predict today's—it's often close.
• Benefit: Reduces the number of solver iterations needed, crucial for real-time performance.
• Use Case: Essential for stable stacking of objects, where contact points change little between frames.

The penalty method is an alternative to exact constraint solvers. Instead of solving for exact non-penetration, it allows bodies to intersect slightly and applies a spring-like penalty force proportional to the penetration depth and velocity.

• How it works: Force = - (stiffness * penetration) - (damping * penetration_velocity).
• Pros: Simpler to implement, can be more stable for certain scenarios.
• Cons: Can cause "jitter" with high stiffness or lead to unrealistic energy changes. Often used in soft-body or cloth simulation.

Impulse-based dynamics is a simulation paradigm where collisions and contacts are resolved by applying instantaneous changes in velocity (impulses) rather than computing continuous forces over a time step. Many real-time game physics engines use this method.

• Core Principle: Applies an impulse J to change velocity: Δv = J / mass.
• Constraint Solver's Role: Iteratively calculates the magnitude of these impulses to satisfy non-penetration and friction constraints.
• Characteristic: Often results in a velocity-level solver, as opposed to a force-level solver.

The Featherstone Algorithm (Articulated Body Algorithm) is an O(n) method for computing forward dynamics of complex articulated chains, like robot arms. It efficiently calculates joint accelerations given applied forces.

• Relation to Constraint Solvers: For systems with closed loops (e.g., a robot grabbing an object, creating a loop), the constraint solver must work in concert with algorithms like Featherstone's to handle the loop constraints.
• Performance: Enables simulation of robots with hundreds of joints in real-time by avoiding inversion of the large system mass matrix.