Numerical Integration

From VDrift
Revision as of 20:07, 19 May 2008 by Venzon (talk | contribs)
Jump to: navigation, search

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 its error becomes unacceptably large. Accuracy refers to how well the integrator matches the expected result.

Euler Integration

 a = acceleration(state, t+dt)
 x += v*dt
 v += a*dt

Newton-Stormer-Verlet (NSV) / Symplectic Euler / Euler–Cromer algorithm

 a = acceleration(state, t+dt)
 v += a*dt
 x += v*dt

Velocity Verlet

 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

 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