Numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral. This the backbone of physics simulations because it allows calculation of velocity and position from forces (and therefore acceleration) applied to a rigid body.
In realtime simulations, the most important integrator criteria are performance, stability, and accuracy. Performance refers to how long it takes to perform the integration for a given timestep. Stability refers to how well the integrator copes with stiff constraints such as high spring constants before errors becomes unacceptably large. Accuracy refers to how well the integrator matches the expected result, and includes whether or not the integrator damps out (loses energy) over time.
The Euler method is a first order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic kind of explicit method for numerical integration for ordinary differential equations. The performance is excellent, but both stability and accuracy are poor. Because it is so simple, it unfortunately gets used very often. Vamos uses Euler integration.
a = acceleration(state, t+dt) x += v*dt v += a*dt
Newton-Stormer-Verlet (NSV) / Symplectic Euler / Euler–Cromer algorithm
the Euler–Cromer algorithm or symplectic Euler method or Newton-Stormer-Verlet (NSV) method is a modification of the Euler method for solving Hamilton's equations, a system of ordinary differential equations that arises in classical mechanics. It is a symplectic integrator, which is a class of geometric integrators that is especially good at simulations of dynamics and hence it yields much better results than the standard Euler method. The performance is excellent, and stability and accuracy are both reasonably good.
a = acceleration(state, t+dt) v += a*dt x += v*dt
Verlet integration is a numerical integration method originally designed for calculating the trajectories of particles in molecular dynamics simulations. The velocity verlet variant directly calculates velocity. The performance is good, and both stability and accuracy are excellent. Unfortunately, calculating the velocity depends on knowing the acceleration for the current iteration, which poses a problem when the acceleration depends on the velocity. Using the velocity from the last iteration to calculate the acceleration degrades its accuracy.
if (not oldaccel) oldaccel = acceleration(state, t+dt) x += v*dt + 0.5*oldaccel*dt*dt a = acceleration(state, t+dt) v += 0.5*(a + oldaccel)*dt oldaccel = a;
Runge Kutta 4
The Runge–Kutta methods are an important family of implicit and explicit iterative methods for the approximation of solutions of ordinary differential equations. The Runge Kutta 4 (or RK4) is a well-known 4th-order explicit Runge Kutta algorithm. The code snippet shown below is high level, and the actual implementation is a bit more complicated. Performance is poor, since the acceleration must be evaluated for all objects 4 times per iteration, stability is excellent, and accuracy is merely good.
Derivative a = evaluate(state, t) Derivative b = evaluate(state, t, dt*0.5f, a) Derivative c = evaluate(state, t, dt*0.5f, b) Derivative d = evaluate(state, t, dt, c) const float dxdt = 1.0f/6.0f * (a.dx + 2.0f*(b.dx + c.dx) + d.dx) const float dvdt = 1.0f/6.0f * (a.dv + 2.0f*(b.dv + c.dv) + d.dv) state.x = state.x + dxdt*dt state.v = state.v + dvdt*dt