Time Integration

The primary dichotomy in time integration is between explicit and implicit methods. Explicit methods (e.g., Forward Euler) calculate the new state using only known information from the current and past states. They are simple and fast per step but can become unstable with large time steps or stiff systems (e.g., stiff springs). Implicit methods (e.g., Backward Euler) solve for the new state using equations that depend on the future state itself, requiring the solution of a (often linear) system. They are unconditionally stable for linear problems, allowing much larger time steps, but are computationally more expensive per step. The trade-off is between the cost-per-step of implicit methods and the potentially tiny steps required for explicit stability.

The order of accuracy describes how the local truncation error of an integrator scales with the time step size. An O(Δtⁿ) method means the error per step is proportional to Δtⁿ. Higher-order methods (e.g., 4th-order Runge-Kutta) provide more accurate results for a given step size but involve more function evaluations (stages) per step. Lower-order methods (e.g., Forward Euler, O(Δt)) are less accurate but simpler. The choice depends on the required fidelity: high-accuracy scientific simulation demands high-order methods, while real-time interactive applications often prioritize speed with lower-order, stable integrators.

Numerical stability determines whether small errors (e.g., from rounding) decay or grow uncontrollably over many time steps. An integrator's region of stability defines the time step limits for a stable simulation. Stiff systems have components that evolve on vastly different time scales (e.g., a robot arm with very stiff joint limits). Explicit integrators require impractically small time steps to remain stable for stiff systems. Implicit integrators and semi-implicit methods are essential for handling stiffness, as their stability regions are much larger, enabling feasible simulation of complex robotic systems with contacts and constraints.

For simulating conservative mechanical systems (e.g., orbital dynamics, idealized pendulums), preserving geometric properties is crucial. A symplectic integrator (e.g., Verlet, Leapfrog, Symplectic Euler) conserves a modified Hamiltonian, leading to near-perfect long-term energy conservation and stable orbital trajectories, unlike non-symplectic methods where energy can drift. While not all physics engines prioritize symplecticity, it is a key characteristic for high-fidelity, long-duration simulations of closed physical systems where numerical energy dissipation is undesirable.

Robotics simulations employ a range of integrators based on needs:

• Semi-Implicit Euler (Symplectic Euler): Popular in real-time engines; combines explicit velocity update with implicit position update for improved stability.
• Runge-Kutta 4 (RK4): The workhorse for high-accuracy, non-stiff dynamics; provides 4th-order accuracy with four derivative evaluations per step.
• Implicit Euler: Used for highly stiff problems or systems with hard constraints and contacts; provides robust, damping stability.
• Variable Step Methods: Algorithms like RKF45 adapt the time step size dynamically to control error, useful for simulating systems with varying dynamics.

In practice, time integration is not performed in isolation. It is tightly coupled with the constraint solver (e.g., for contacts, joints). The most common approach is the velocity-level formulation, where the integrator updates positions and velocities, and a solver (like PGS) applies impulses to satisfy constraints at the velocity level. More advanced methods like Baumgarte stabilization or post-stabilization correct constraint drift introduced by the integrator. The choice of integrator affects the formulation and performance of this coupled solve, making the integration-solver pair a core design decision for any physics engine.

An Ordinary Differential Equation (ODE) is a mathematical equation that relates a function to its derivatives. In physics simulation, the equations of motion (Newton's second law, Euler's equations) are ODEs that describe how position, velocity, and acceleration evolve over time. The primary goal of a time integrator is to numerically solve these ODEs.

• General Form: dy/dt = f(t, y), where y is the state vector (positions, velocities).
• Example: For a simple mass-spring system, the ODE is derived from F = ma, resulting in a second-order ODE for the mass's position.

Explicit integration methods calculate the future state of a system using only known information from the current and past states. These methods are straightforward to implement and computationally cheap per step but can become unstable if the time step is too large.

• Common Algorithms: Forward Euler, Runge-Kutta methods (RK4).
• How it works: The new state y_{n+1} is computed directly from the current state y_n and its derivative f(t_n, y_n).
• Trade-off: Susceptible to instability for stiff systems (e.g., systems with very stiff springs or high-frequency constraints), requiring very small time steps.

Implicit integration methods calculate the future state of a system by solving an equation that involves the unknown future state itself. This requires solving a system of equations (often via matrix inversion) but provides superior stability, allowing for much larger time steps.

• Common Algorithm: Backward Euler.
• How it works: The equation y_{n+1} = y_n + Δt * f(t_{n+1}, y_{n+1}) must be solved for the unknown y_{n+1}.
• Primary Benefit: Unconditional stability for linear problems, making it ideal for simulating stiff materials like ragdolls or cloth without explosive behavior.
• Drawback: Significantly more computationally expensive per time step than explicit methods.

The Semi-Implicit Euler method, also known as Symplectic Euler, is a popular integrator in game physics and real-time simulation. It updates velocity and position in an interleaved manner, offering a good balance of simplicity, performance, and improved stability over pure explicit Euler.

• Algorithm:
  • Update velocity using acceleration at the current time: v_{n+1} = v_n + Δt * a(t_n, x_n)
  • Update position using the new velocity: x_{n+1} = x_n + Δt * v_{n+1}
• Key Property: It is a symplectic integrator for separable Hamiltonian systems, meaning it better conserves energy over long simulations, preventing artificial damping or energy blow-up.
• Use Case: The default integrator in many real-time engines like NVIDIA PhysX and Bullet for rigid body dynamics.

Verlet integration is a family of numerical methods that calculate new positions based on previous positions, bypassing the explicit storage of velocities. It is highly stable and time-reversible, making it a cornerstone for molecular dynamics and particle-based simulations.

• Basic Verlet: x_{n+1} = 2x_n - x_{n-1} + a_n * Δt^2
• Velocity Verlet: A more common variant that explicitly tracks velocities:
  • x_{n+1} = x_n + v_n*Δt + 0.5*a_n*Δt^2
  • v_{n+1} = v_n + 0.5*(a_n + a_{n+1})*Δt
• Advantages: Excellent long-term stability and energy conservation properties.
• Applications: Ubiquitous in Smoothed-Particle Hydrodynamics (SPH) and Position-Based Dynamics (PBD) for simulating fluids, cloth, and soft bodies.

Runge-Kutta methods are a class of explicit, multi-stage integration algorithms that achieve higher accuracy by evaluating the derivative (the "slope") at several intermediate points within a single time step. The fourth-order method (RK4) is the most widely used for high-accuracy simulations.

• How RK4 Works: It computes four derivative estimates (k1, k2, k3, k4) within the interval [t_n, t_n+Δt] and takes a weighted average to compute the final update.
• Accuracy: RK4 has a local truncation error of O(Δt⁵), making it a fourth-order method. It is significantly more accurate than Euler methods for a given step size.
• Trade-off: Requires four derivative evaluations per step, making it four times more expensive than Forward Euler.
• Use Case: Preferred in offline, high-fidelity simulations where accuracy is paramount over real-time performance, such as in aerospace or robotics trajectory planning.