Introduction

The reader should know the basics of vector maths, meaning addition, subtraction, multiplication with a scalar and the dot product. More than that is not required, however, for deeper understanding more knowledge of Euclidean geometry in two dimensions wouldn't hurt.

Verlet integration

There are different methods to do that - I guess, most of you know the Euler method:

If we merge these two equations into one, meaning we substitute the Velocity_New in the second equation by the right hand side of the first equation, we get:

There are different types of Verlet integration methods - Position Verlet, Velocity Verlet and Leapfrog. For this article, we will choose the position version, because it has some nice features that we're going to take advantage of.

The corresponding equation for position Verlet is actually not much different from the one shown above:

As we can see now, the term (Position_Current – Position_Old) in the Verlet equation replaces the velocity if we compare it with the Euler approach. Consequently, this means that this approach doesn't deal with velocities at all - one thing less to worry about. This integration method is not always quite accurate, since (Position_Current – Position_Old) is only an approximation of the actual velocity. However, it's fast and stable, which is why it is well suited for games. Also, using this approach the collision response gets really simple. Let us consider a point as shown in figure 1.

The starting conditions for Position_Old and Position_Current are chosen such that the point moves slowly to the right. After a certain amount of time steps, the point will intersect with the square on the right. Once the collision is detected, we only have to move the point out of the square and we are done with the collision response. Since the integration uses (Position_Current – Position_Old) as its velocity, the speed of the point will subsequently change if we change either CurrentPosition or OldPosition - which is what we did in the collision response (we moved the point out of the square). As we can see in figure 2, the point will automatically decelerate and eventually stop.

If we put the formula above in code, we get something like this (assuming you have a working vector-class, that is):

struct Point {
  Vec2 Position;
  Vec2 OldPosition;
  Vec2 Acceleration;
};

class Physics {
  int PointCount;
  Point* Points[ MAX_VERTICES ];

  float Timestep;

public:
  void  UpdateVerlet();

  //Constructors, getters/setters etc. omitted
};

void Physics::UpdateVerlet() {
  for( int I = 0; I < PointCount; I++ ) {
    Point& P = *Points[ I ];

    Vec2 Temp = P.Position;
    P.Position += P.Position - P.OldPosition + P.Acceleration*Timestep*Timestep;
    P.OldPosition = Temp;
  }
}

We could of course try and create thousands of particles and connect them in some way to approximate the behaviour of rigid bodies, which would work indeed. However, that would cause a huge amount of calculations to be done for e.g. a single cube, let alone a whole game filled with physics bodies, so this isn't really an optimal solution. Luckily, it shows to be sufficient only to model the vertices of a body. If we were to simulate a box, we would simply create the four vertices that make up the shape of a box, connect them somehow and we're done.

The problem left to compute is now only that of the connections. If we again imagine a box and the four vertices, it should become clear that the distance of a vertex to another should always remain constant. If the distance between two vertices changes, this always means that the shape of the body gets deformed, and we don't want that - who would like to have a crate in his game that collapses once you stand on it? Therefore, we have to find a way to keep the distance between two vertices at a constant value.

If we had the same problem in reality, the solution would be simple - just insert some kind of pole in-between and the vertices won't approach each other anymore. We will do the exact same thing in our program; create a new class that represents an 'imaginary pole'. It connects two vertices and keeps those vertices at a constant distance. The algorithm to update these 'poles' is called once the Verlet is calculated. The algorithm itself is actually quite simple. First of all, we have to calculate the vector between the two vertices that are connected by the pole. The current distance between the two vertices is simply the length of that vector. Once we have the current length, the difference of the original length of the pole should be calculated. We can now use the difference to push the vertices to a position where the distance constraint is satisfied.

struct Edge {
  Vertex* V1;
  Vertex* V2;

  float OriginalLength; //The length of the edge when it was created

  //Constructors etc. omitted
};

void Physics::UpdateEdges() {
  for( int I = 0; I < EdgeCount; I++ ) {
    Edge& E = *Edges[ I ];

    //Calculate the vector mentioned above
    Vec2 V1V2 = E.V2->Position - E.V1->Position; 

    //Calculate the current distance
    float V1V2Length = V1V2.Length(); 
    
    //Calculate the difference from the original length
    float Diff       = V1V2Length - E.OriginalLength; 
    
    V1V2.Normalize();

    //Push both vertices apart by half of the difference respectively 
    //so the distance between them equals the original length
    E.V1->Position += V1V2*Diff*0.5f; 
    E.V2->Position -= V1V2*Diff*0.5f;
  }
}

But why does that work? The code isn't much different from before, we only added a few lines to satisfy the distance constraint and suddenly we have rigid bodies. The reason behind this lies within our integration method. If we recall that the Verlet integration doesn't work with velocity but rather with the difference between the current position and the position before the last integration step, it should become clear that the speed of the point will change if we change its position. Therefore, since we change its position in the UpdateEdges method, its velocity will also change. The overall change in velocity looks exactly like we would expect it from a vertex of a rigid body; it is not totally correct, but good enough for games.

To be honest, I lied when I said before that the code would work just fine if we executed it like that. As the code is now, bodies would not be totally rigid. If a body collides with the floor, the distance between it's vertices is not totally constant, which means that the body is more or less deformed, depending on the it's speed before the collision. Why does that happen? The UpdateEdges method is totally correct, but still the distance between two vertices may vary. If we look at figure 3, this should become clear: If a vertex is connected to more than just one edge (which is normally the case), the length correction of one edge may disturb the length of another edge, which is why the bodies get deformed.

The only way to get rid of this problem is to execute the edge correction method more than just once per frame. The more this method is called, the more perfect the situation gets approximated, where all vertices have the right distance to each other. This gives game programmers a scalable physics algorithm - the more time is left at the end of the main loop, the more iterations can be used for the distance correction (and the collision response that will be introduced later). Vice-versa, if the main loop takes more time to execute, the iterations used for physics can be reduced so the game runs at a more or less constant frame rate.

Collision Detection