Integration: Our Best Friend (Part 2)

In the previous part of this post, we covered some mathematical foundations behind the concepts of position, velocity and acceleration. We explained that velocity is the derivative of position and that acceleration is the derivative of velocity. We also saw that derivatives represent rates of changes, and therefore, velocity is the rate of change in position and acceleration the rate of change in velocity. If velocity is constant (i.e. acceleration is 0), the rate of change in position is constant, and the position would change linearly. If on the other hand acceleration $>$ 0 (but constant), velocity would grow linearly and position would grow quadratically (i.e. forming a curve). Figure 1 shows different possibilities: stationary objects (no velocity), uniform motion (constant velocity) and motion with constants acceleration.

Figure 1 (source: http://cnx.org)

The problem that tries to solve an integrator is how to figure out (fast and efficiently) the velocity from the acceleration and the position from the velocity (i.e. doing the inverse of derivatives). And why? Because in most games, the acceleration on an object is the only information that we have.

Actually, this is not completely true. The information that we usually have is the force applied to an object (due to a collision or a hit, for example). However, as the Newton's second law states: 'The acceleration of a body is directly proportional to, and in the same direction as, the net force acting on the body, and inversely proportional to its mass'. Mathematically, this can be represented as follows:

$F = m \cdot a$     (1)

Therefore, knowing the direction and magnitude of an applied force, we can figure out the acceleration from (1):

$a = \frac{F}{m}$     (2)

At this point, we know the acceleration. We may find two different situations here, depending on whether we have constant acceleration or not. 

Constant acceleration

When we have constant acceleration, we can simply move our minds back to high school times and apply the famous equations that models how position changes when there is constant acceleration, that is:

                                              $p = p_{0} + v_{0} \cdot t + \frac{1}{2} \cdot a \cdot t^{2}$  (3)

Then, we could simply update velocity for the next iteration:

$v = v_{0} + a \cdot t$  (4)

Formulas (3) and (4) are also integration formulas, but they don't approximate: they provide the real position and velocity values. Here, in a couple of comments, they call this type of integration a ballistic or parabolic integrator, even though I haven't found any other references or entries for these names. 

In any case, the point is that if we know that acceleration is constant, we can and should use these formulas, because they provide accurate results. Euler's integrator, however, accumulates errors over the time and if the time step is big, this error grows faster. Euler's integration uses the following formulas:

$p = v \cdot t$ (5)

$v = a \cdot t$  (6)

Let's see how we could implement both integrators in C.  

  int dt = 1; //time step  
  int position = 0, velocity = 0, acceleration = 10;  
  printf("Using physics formulas\n");  
  for (i = 1; i <= limit; i++) {  
  printf("Time %d: ", i);  
  position += velocity * dt + acceleration*dt*dt/2;  
  velocity += acceleration*dt;  
  printf("Position %d, Velocity %d\n", position, velocity);  
  }  
  printf("--------------------------------\n");  
  velocity = 0, position = 0;  
  printf("Euler integration\n");  
  for (i = 1; i <= limit; i++) {  
  printf("Time %d: ", i);  
  position += velocity * dt;  
  velocity += acceleration * dt;  
  printf(" Position %d, Velocity %d\n", position, velocity);  
  }  

  

If we execute the previous code, and we change the number of iterations we can see that the higher the number of iterations, the higher the error is (that is, error is accumulating in Euler's integration). Also, if we reduce the time step (dt), we can see how the Euler's error decreases, whereas it would increase in case of a bigger time step. If you carefully see the formulas, all of this makes sense. Notice that the only difference between the 'accurate' integration and Euler integration is the position update. The former includes more information (basically an extra multiplication by 0.5 * dt^2). The smaller dt, the less significant is the difference with Euler's. Also note that velocity update is exactly the same in both methods.

As a conclusion, there is no problem with constant acceleration, as we can achieve exact results. This becomes a little trickier in non-constant acceleration situations.

Non-constant acceleration

Many physics engines have to deal with non-constant acceleration. For example, consider a force on an object that is proportional to the velocity of the object, that is:

$F = -v$    (7)

This could model the air friction, for example. In this case, and because we always assume constant mass, we deduce from (2) that if the velocity changes, the acceleration changes. In these cases, we find a differential equation:

$a = \frac{dv}{dt} = \frac{-v}{m}$      (8)

It's a ordinary differential equation (ODE) because the equation of the velocity has the derivative of the velocity in it. Analytically integrating (i.e. with paper and pen and with exact results) ODEs is tough, but integrating them numerically is pretty straightforward. We have already seen the formulas of Euler integration (5 and 6), but let's re-write them again, this time considering a time step called $h$ (instead of $t$), using the differential notation and considering explicitly the iterations with a subscript:

$p_{n+1} = p_{n} + h \cdot \frac{dp_{n}}{dx}$     (9)

$v_{n+1} = v_{n} + h \cdot \frac{dv_{n}}{dx}$  (10)

Most integration methods follow the same pattern. They evaluate the derivative (remember, the slope) of the variable we want to figure out, and they step forward in time by a fixed amount, h, on the tangent line with that slope. In the next step, they evaluate the derivative at the new position to get a new slope, taking another time step. Chris Hecker gives a very good, graphical explanation of this process here. 

Of course, Euler will have the same problems we discussed previously, but at least if we choose a sufficiently small time step (as we may find in 60 frames/second games, where the time step is approximately 0.017 seconds), results are not that bad. However,  in physics-intensive games, where you need high accuracy, or in order to avoid inaccuracy problems due to drops in frame rates, you'll need other better integration methods, and that's what I'll cover in the last post.

Concretely, I will explain Runge-Kuta order 4 and Verlet methods. I'll also explain how I dealt with all this for the game I'm working on and I'll provide a list of references that were useful to me while writing these posts. Some of them will give you more mathematical insight. 

See you!