The UpdateBodyEuler method integrates the equations of motion for each particle. Since we’re dealing with particles, the only equation of motion we need concern ourselves with is that for translation; rotation does not matter for particles (at least not for us here). The following code sample shows UpdateBodyEuler.

void  Particle::UpdateBodyEuler(double dt)
{
    Vector a;
    Vector dv;
    Vector ds;

    // Integrate equation of motion:
    a = vForces / fMass;

    dv = a * dt;
    vVelocity += dv;

    ds = vVelocity * dt;
    vPosition += ds;

    // Misc. calculations:
    fSpeed = vVelocity.Magnitude();
}

As the name of this method implies, we’ve implemented Euler’s method of integration as described in Chapter 7. Using this method, we simply need to divide the aggregate forces acting on a particle by the mass of the particle to get the particle’s acceleration. The line of code a = vForces / fMass does just this. Notice here that a is a Vector, as is vForces. fMass is a scalar, and the / operator defined in the Vector class takes care of dividing each component of the vForces vector by fMass and setting the corresponding components in a. The change in velocity, dv, is equal to acceleration times the change in time, dt. The particle’s new velocity is then computed by the line vVelocity += dv. Here again, vVelocity and dv are Vectors and the += operator takes care of the vector arithmetic. This is the first actual integration.

The second integration takes place in the next few lines, where we determine the particle’s displacement and new position by integrating its velocity. The line ds = vVelocity * dt determines the displacement, or change in the particle’s position, and the line vPosition += ds computes the new position by adding the displacement to the particle’s old position.

The last line in UpdateBodyEuler computes the particle’s speed by taking the magnitude of its velocity vector.

For demonstration purposes, using Euler’s method is just fine. In an actual game, the more robust method described in Chapter 7 is advised.

In this example, rendering the particles is rather trivial. All we do is draw little circles using Windows API calls wrapped in our own functions to hide some of the Windows-specific code. The following code snippet is all we need to render the particles.

void  Particle::Draw(void)
{
  RECT   r;
  float  drawRadius = max(2, fRadius);

  SetRect(&r, vPosition.x − drawRadius,
          _WINHEIGHT − (vPosition.y − drawRadius),
          vPosition.x + drawRadius,
      _WINHEIGHT − (vPosition.y + drawRadius));
  DrawEllipse(&r, 2, RGB(0,0,0));
}

You can use your own rendering code here, of course, and all you really need to pay close attention to is converting from world coordinates to window coordinates. Remember, we’ve assumed our world coordinate system origin is in the lower-left corner of the window, whereas the window drawing coordinate system has its origin in the upper-left corner of the window. To transform coordinates in this example, all you need to do is subtract the particle’s y-position from the height of the window.

Essentially what we’re aiming to achieve with particle-to-ground collision detection is to prevent the particles from passing through a ground plane specified at some y coordinate. Imagine a horizontal impenetrable surface that the particles cannot pass through. There are several things we must do in order to detect whether a particle is indeed colliding with the ground plane. If so, then we need to handle the collision, making the particles respond in a suitable manner.

The left side of Figure 8-5 illustrates a collision scenario. It’s easy to determine whether or not a collision has taken place. Over a given simulation time step, a particle may have moved from some previous position (its position at the previous time step) to its current position. If this current position puts the centroid coordinate of the particle within one particle radius of the ground plane, then a collision might be occurring. We say might because the other criteria we need to check in order to determine whether or not a collision is happening is whether or not the particle is moving toward the ground plane. If the particle is moving toward the ground plane and it’s within one radius of the ground plane, then a collision is occurring. It may also be the case that the particle has passed completely through the ground plane, in which case we assume a collision has occurred.

Figure 8-5. Particle-to-ground collision

To prevent such penetration of the ground plane, we need to do two things. First, we must reposition the particle so that it is just touching the ground plane, as shown on the right side of Figure 8-5. Second, we must apply some impact force resulting from the collision in order to force the particle to either stop moving down into the ground plane or to move away from the ground plane. All these steps make up collision detection and response.

There are several changes and additions that we must make to the example code in order to implement particle-to-ground collision detection and response. Let’s begin with the Particle class.

We’ve added three new properties to Particle, as follows:

class Particle {
  .
  .
  .
  Vector  vPreviousPosition;
  Vector  vImpactForces;
  bool    bCollision;
  .
  .
  .
};

vPreviousPosition is used to store the particle’s position at the previous time step—that is, at time t-dt. vImpactForces is used to aggregate all of the impact forces acting on a particle. You’ll see later that it is possible for a particle to collide with more than one object at the same time. bCollision is simply a flag that is used to indicate whether or not a collision has been detected with the particle at the current time step. This is important because when a collision occurs, at that instant in time, we assume that the only forces acting on the particle are the impact forces; all of the other forces—gravity, drag, and wind—are ignored for that time instant. We use bCollision in the updated CalcLoads method:

void  Particle::CalcLoads(void)
{
  // Reset forces:
  vForces.x = 0.0f;
  vForces.y = 0.0f;

  // Aggregate forces:
  if(bCollision) {
    // Add Impact forces (if any)
    vForces += vImpactForces;
  } else {
    // Gravity
    vForces += vGravity;

    // Still air drag
    Vector  vDrag;
    float  fDrag;

    vDrag -= vVelocity;
    vDrag.Normalize();
    fDrag = 0.5 * _AIRDENSITY * fSpeed * fSpeed *
           (3.14159 * fRadius * fRadius) * _DRAGCOEFFICIENT;
    vDrag *= fDrag;
    vForces += vDrag;

    // Wind
    Vector  vWind;
    vWind.x = 0.5 * _AIRDENSITY * _WINDSPEED * _WINDSPEED *
             (3.14159 * fRadius * fRadius) * _DRAGCOEFFICIENT;
    vForces += vWind;
  }
}

The only difference between this version of CalcLoads and the previous one is that we added the conditional if(bCollision) { ... } else { ... }. If bCollision is true, then we have a collision to deal with and the only forces that get aggregated are the impact forces. If there is no collision, if bCollision is false, then the non-impact forces are aggregated in the usual manner.

You may have caught that we are aggregating impact forces in this example. This is an alternate approach to the one shown in Chapter 5. There we showed you how to calculate an impulse and change an object’s velocity in response to a collision, using conservation of momentum. Well, we’re still calculating impulses just like in Chapter 5; however, in this example, we’re going to compute the impact force based on that impulse and apply that force to the colliding objects. We’ll let the numerical integrator integrate that force to derive the colliding particle’s new velocities. Either method works, and we’ll show you an example of the former method later. We’re showing the latter method here just to illustrate some alternatives. The advantage of this latter method is that it is easy to compute impact forces due to multiple impacts and let the integrator take care of them all at once.

Now, with these changes made to Particle, we need to add a line of code to UpdateSimulation, as shown here:

void  UpdateSimulation(void)
{
  .
  .
  .

  // update computer controlled units:
  for(i=0; i<_MAX_NUM_UNITS; i++)
  {
    Units[i].bCollision = CheckForCollisions(&(Units[i]));
    Units[i].CalcLoads();
    Units[i].UpdateBodyEuler(dt);
    .
    .
    .
  } // end i-loop

  .
  .
  .
}

The new line is Units[i].bCollision = CheckForCollisions(&(Units[i]));. CheckForCollisions is a new function that takes the given unit, whose pointer is passed as an argument, and checks to see if it’s colliding with anything—in this case, the ground. If a collision is detected, CheckForCollisions also computes the impact force and returns true to let us know a collision has occurred. CheckForCollisions is as follows:

bool  CheckForCollisions(Particle* p)
{
  Vector  n;
  Vector  vr;
  float   vrn;
  float   J;
  Vector  Fi;
  bool    hasCollision = false;


    // Reset aggregate impact force
    p->vImpactForces.x = 0;
    p->vImpactForces.y = 0;

    // check for collisions with ground plane
    if(p->vPosition.y <= (_GROUND_PLANE+p->fRadius)) {
      n.x = 0;
      n.y = 1;
      vr = p->vVelocity;
      vrn = vr * n;
      // check to see if the particle is moving toward the ground
      if(vrn < 0.0) {
        J = -(vr*n) * (_RESTITUTION + 1) * p->fMass;
        Fi = n;
        Fi *= J/_TIMESTEP;
        p->vImpactForces += Fi;

        p->vPosition.y = _GROUND_PLANE + p->fRadius;
        p->vPosition.x = ((_GROUND_PLANE + p->fRadius −
                         p->vPreviousPosition.y) /
                        (p->vPosition.y - p->vPreviousPosition.y) *
                        (p->vPosition.x - p->vPreviousPosition.x)) +
                        p->vPreviousPosition.x;

        hasCollision = true;
      }
    }

  return hasCollision;
}

CheckForCollisions makes two checks: 1) it checks to see whether or not the particle is making contact or passing through the ground plane; and 2) it checks to make sure the particle is actually moving toward the ground plane. Keep in mind a particle could be in contact with the ground plane right after a collision has been handled with the particle moving away from the ground. In this case, we don’t want to register another collision.

Let’s consider the details of this function, starting with the local variables. n is a vector that represents the unit normal vector pointing from the ground plane to the particle colliding with it. For ground collisions, in this example, the unit normal vector is always straight up since the ground plane is flat. This means the unit normal vector will always have an x component of 0 and its y component will be 1.

The Vector vr is the relative velocity vector between the particle and the ground. Since the ground isn’t moving, the relative velocity is simply the velocity of the particle. vrn is a scalar that’s used to store the component of the relative velocity in the direction of the collision unit normal vector. We compute vrn by taking the dot product of the relative velocity with the unit normal vector. J is a scalar that stores the impulse resulting from the collision. Fi is a vector that stores the impact force as derived from the impulse J. Finally, hasCollision is a flag that’s set based on whether or not a collision has been detected.

Now we’ll look at the details within CheckForCollisions. The first task is to initialize the impact force vector, vImpactForces, to 0. Next, we make the first collision check by determining if the y-position of the particle is less than the ground plane height plus the particles radius. If it is, then we know a collision may have occurred. (_GROUND_PLANE represents the y coordinate of the ground plane, which we have set to 100.) If a collision may have occurred, then we make the next check—to determine if the particle is moving toward the ground plane.

To perform this second check, we compute the unit normal vector, relative velocity, and relative velocity component in the collision normal direct as described earlier. If the relative velocity in the normal direction is negative (i.e., if vrn < 0), then a collision has occurred. If either of these checks is false, then a collision has not occurred and the function exits, returning false.

The interesting stuff happens if the second check passes. This is where we have to determine the impact force that will cause the particle to bounce off the ground plane. Here’s the specific code that computes the impact force:

        J = -(vr*n) * (_RESTITUTION + 1) * p->fMass;
        Fi = n;
        Fi *= J/_TIMESTEP;
        p->vImpactForces += Fi;

        p->vPosition.y = _GROUND_PLANE + p->fRadius;
        p->vPosition.x = (_GROUND_PLANE + p->fRadius −
                         p->vPreviousPosition.y) /
                        (p->vPosition.y - p->vPreviousPosition.y) *
                        (p->vPosition.x - p->vPreviousPosition.x) +
                         p->vPreviousPosition.x;

        hasCollision = true;

We compute the impulse using the formulas presented in Chapter 5. J is a scalar equal to the negative of the relative velocity in the normal direction times the coefficient of restitution plus 1 times the particle mass. Recall that the coefficient of restitution, _RESTITUTION, governs how elastic or inelastic the collision is, or in other words, how much energy is transferred back to the particle during the impact. We have this value set to 0.6, but it is tunable depending on what effect you’re trying to achieve. A value of 1 makes the particles very bouncy, while a value of, say, 0.1 makes them sort of stick to the ground upon impact.

Now, to compute the impact force, Fi, that will act on the particle during the next time step, making it bounce off the ground, we set Fi equal to the collision normal vector. The magnitude of the impact force is equal to the impulse, J, divided by the time step in seconds. The line Fi *= J/_TIMESTEP; takes care of calculating the final impact force.

To keep the particle from penetrating the ground, we reposition it so that it’s just resting on the ground. The y-position is easy to compute as the ground plane elevation plus the radius of the particle. We compute the x-position by linearly interpolating between the particle’s previous position and its current position using the newly computed y-position. This effectively backs up the particle along the line of action of its velocity to the point where it is just touching the ground plane.

When you run the simulation now, you’ll see the particles fall, drifting a bit from left to right until they hit the ground plane. Once they hit, they’ll bounce on the ground, eventually coming to rest. Their specific behavior in this regard depends on what drag coefficient you use and what coefficient of restitution you use. If you have wind applied, when the particles do come to rest, vertically, they should still drift to the right as though they are sliding on the ground plane.

To make things really interesting, we’ll now add those circular obstacles you saw in Figure 8-1 through Figure 8-4. The particles will be able to hit them and bounce off or even settle down into crevasses made by overlapping obstacles. The obstacles are simply static particles. We’ll define them as particles and initialize them but then skip them when integrating the equations of motion of the dynamic particles. Here’s the declaration for the Obstacles array:

Particle      Obstacles[_NUM_OBSTACLES];

Initializing the obstacles is a matter of assigning them positions and a common radius and a mass. The few lines of code shown next were added to the main program’s Initialize function to randomly position obstacles in the lower, middle portion of the window above the ground plane. Figure 8-1 through Figure 8-4 illustrate how they are distributed.

bool  Initialize(void)
{
  .
  .
  .

  for(i=0; i<_NUM_OBSTACLES; i++)
  {
    Obstacles[i].vPosition.x = GetRandomNumber(_WINWIDTH/2 −
                               _OBSTACLE_RADIUS*10,
                               _WINWIDTH/2 +
                               _OBSTACLE_RADIUS*10, false);
    Obstacles[i].vPosition.y = GetRandomNumber(_GROUND_PLANE +
                               _OBSTACLE_RADIUS, _WINHEIGHT/2 −
                               _OBSTACLE_RADIUS*4, false);
    Obstacles[i].fRadius = _OBSTACLE_RADIUS;
    Obstacles[i].fMass = 100;
  }
  .
  .
  .
}

Drawing the obstacles is easy since they are Particle types with a Draw method that already draws circular shapes. We created DrawObstacles to iterate through the Obstacles array, calling the Draw method of each obstacle.

void DrawObstacles(void)
{
  int    i;

  for(i=0; i<_NUM_OBSTACLES; i++)
  {
    Obstacles[i].Draw();
  }

}

DrawObstacles is then called from UpdateSimulation:

void  UpdateSimulation(void)
{
  .
  .
  .

  // initialize the back buffer
  if(FrameCounter >= _RENDER_FRAME_COUNT)
  {
    ClearBackBuffer();
    // Draw ground plane
    DrawLine(0, _WINHEIGHT - _GROUND_PLANE,
             _WINWIDTH, _WINHEIGHT - _GROUND_PLANE,
             3, RGB(0,0,0));

    DrawObstacles();
  }
  .
  .
  .
}

The last bit of code we need to add to have fully functioning collisions with obstacles involves adding more collision detection and handling code to the CheckForCollisions function. Before we look at CheckForCollisions, let’s consider colliding circles in general to gain a better understanding of what the new code will do.

Figure 8-6 illustrates two circles colliding. We aim to detect whether or not these circles are colliding by checking the distance between their centers. If the distance between the two centers is greater than the sum of the radii of the circles, then the particles are not colliding. The topmost illustration in Figure 8-6 shows the distance, d, between centers and the distance, s, between the edges of the circles; s is the gap between the two. Another way to think about this is that if s is positive, then there’s no collision. Referring to the middle illustration in Figure 8-6, if s is equal to 0, then the circles are in contact. If s is a negative number, as shown in the bottommost illustration, then the circles are penetrating.

Figure 8-6. Collision states

We’ll apply these principles for detecting colliding circles to detecting collisions between our particles and obstacles since they are both circles. Figure 8-7 illustrates how our particle-to-obstacle collisions might look.

Figure 8-7. Particle-to-obstacle collision

We’ll calculate s for each particle against each obstacle to determine contact or penetration. If we find either, then we’ll perform the relative velocity check in the same manner we did for particle-to-ground collisions to see if the particle is moving toward the obstacle. If it is, then we have a collision and we’ll back up the particle along the collision normal vector line of action, which is simply the line connecting the centers of the particle and the obstacle. We’ll also compute the impact force like we did earlier and let the integrator take care of the rest.

OK, now let’s look at the new code in CheckForCollisions:

bool  CheckForCollisions(Particle* p)
{
  .
  .
  .

    // Check for collisions with obstacles
    float r;
    Vector d;
    float s;

    for(i=0; i<_NUM_OBSTACLES; i++)
    {
      r = p->fRadius + Obstacles[i].fRadius;
      d = p->vPosition - Obstacles[i].vPosition;
      s = d.Magnitude() - r;

      if(s <= 0.0)
      {
        d.Normalize();
        n = d;
        vr = p->vVelocity - Obstacles[i].vVelocity;
        vrn = vr*n;


        if(vrn < 0.0)
        {
          J = -(vr*n) * (_RESTITUTION + 1) /
             (1/p->fMass + 1/Obstacles[i].fMass);
          Fi = n;
          Fi *= J/_TIMESTEP;
          p->vImpactForces += Fi;

          p->vPosition -= n*s;
          hasCollision = true;
        }
      }
    }
  .
  .
  .
}

The new code is nearly the same as the code that checks for and handles particle-to-ground collisions. The only major differences are in how we compute the distance between the particle and the obstacle and how we adjust the colliding particle’s position to prevent it from penetrating an obstacle, since the unit normal vector may not be straight up as it was before. The rest of the code is the same, so let’s focus on the differences.

As explained earlier and illustrated in Figure 8-6, we need to compute the separation, s, between the particle and the obstacle. So to get s, we declare a variable r and equate it to the sum of radii of the particle and the obstacle against which we’re checking for a collision. We define d, a Vector, as the difference between the positions of the particle and obstacle. The magnitude of d minus r yields s.

If s is less than 0, then we make the relative velocity check. Now, in this case the collision normal vector is along the line connecting the centers of the two circles representing the particle and the obstacle. Well, that’s just the vector d we already calculated. To get the unit normal vector, we simply normalize d. The relative velocity vector is simply the difference in velocities of the particle and the obstacle. Since the obstacles are static, the relative velocity is just the particle’s velocity. But we calculated the relative velocity by taking the vector difference vr = p->vVelocity – Obstacles[i].vVelocity, because in a more advanced scenario, you might have moving obstacles.

Taking the dot product of the relative velocity vector, vr, with the unit normal vector yields the relative velocity in the collision normal direction. If that relative velocity is less than 0, then the particle and the object are colliding and the code goes on to calculate the impact force in a manner similar to that described earlier for the particle-to-ground collisions. The only difference here is that both the particle’s and object’s masses appear in the impulse formula. Earlier we assumed the ground was infinitely massive relative to the particle’s mass, so the 1/m term for the ground went to 0, essentially dropping out of the equation. Refer back to Chapter 5 to recall the impulse formulas.

Once the impact force is calculated, the code backs up the particle by a distance equal to s, the penetration, along the line of action of the collision normal vector, giving us what we desire (as shown in Figure 8-7).

Now, when you run this simulation you’ll see the particles falling down, bouncing off the obstacles or flowing around them depending on the value you’re using for coefficient of restitution, ultimately bouncing and coming to rest on the ground plane. If you have a wind speed greater than 0, then the particles will still drift along the ground plane from left to right.