Difference between revisions of "Numerical Integration"

From VDrift
Jump to: navigation, search
(New page: 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 calcu...)
 
Line 5: Line 5:
  
 
==Euler Integration==
 
==Euler Integration==
:<math> y_{n+1} = y_n + hf(t_n,y_n).  \qquad \qquad</math>
+
  a = acceleration(state, t+dt)
 +
  x += v*dt
 +
  v += a*dt
  
==Newton-Stormer-Verlet (NSV) Symplectic Euler==
+
==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==
 
==Runge Kutta 4==
 
+
  Derivative a = evaluate(state, t)
==Velocity Verlet==
+
  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

Revision as of 20:07, 19 May 2008

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.

Criteria

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