2D Rigid Body Collision Resolution
Part 1: Defining the problem

From Mario bouncing off a Goomba to two cars bumping into each other in a racing game, dealing with collisions is such an integral part of most video games that we often take it for granted.

In this series of blog posts, I want to show you what actually goes on behind the scenes in a physics simulation like the one above. While we're going to look at this through the lens video games, this post is really about the actual math and physics of collisions. Video games are just a nice way to contextualize these concepts and help make things a little less abstract.

Before we start

Let's set our expectations and define a few terms.

Rigid bodies

The specific kind of physics simulation we are going to cover is called rigid body physics. A rigid body is a body that does not deform when subjected to forces. This is an idealized model because true rigid bodies do not exist in the real world; everything deforms on the molecular level even if this deformation is not visible to the naked eye.

For most physics simulations, trying to simulate this level of detail is not only extremely difficult (if not flat out impossible) and computationally expensive, it's also unnecessary. As long as our bodies behave realistically, we're allowed to simplify as much as we want. Rigid bodies are one such simplification.

This might sound a little abstract at the moment but will hopefully start to make sense as we work through our examples.

Collision detection vs. collision resolution

In a video game engine, dealing with collisions can be broken down into two distinct phases: collision detection and collision resolution.

Collision detection is about determining which bodies in our scene are colliding. This usually involves a bunch of geometry to check if two shapes are intersecting or overlapping. Depending on how many objects there are in our scene, this can be quite computationally expensive and is usually heavily optimized. The result of this step is then used in the collision resolution step.

Collision resolution is the process of figuring out what needs to happen to two colliding bodies based on things like their current movement directions, speeds, materials, and many other things.

In this series of blog posts, we're only looking at the collision resolution phase as this where all the interesting physics happens.

Ok, enough preamble. Let's get started!

What are we trying to do?

Let's start out by trying to define the problem we're trying to solve.

Most games run in a big loop. In order to make things move on the screen, the game engine needs to continually calculate the positions of the various objects in the scene. So on each iteration of the game loop, the position of each of object gets updated a tiny amount based on its current velocity.

Velocity is a vector quantity, meaning it has both a magnitude and a direction. We can represent an object's current velocity with an arrow where the length of the arrow represents the object's current speed and the direction the arrow is pointing its travel direction.

In the demonstration below, you can change the box's velocity by dragging the arrow around. If you ever get lost in space, you can always reset the simulation with the button.

Velocity describes the change in position of an object over a certain time interval $\Delta t$. In physics, this change in position is called displacement and is usually denoted $\vec{s}$.

Whenever you see a little arrow over a variable like this $\vec{s}$, this means that the variable is a vector. Therefore, we can see that displacement is also a vector quantity, meaning it has both magnitude and direction.

In order to find an object's new position, we first calculate the displacement based on the object's current velocity.

Where $\Delta t$ is the time that has passed since the last iteration of our game loop. So if our game loop runs 60 times per second, then $\Delta t$ would be $\frac{1}{60}$ of a second. We then add the displacement to the object's current position to get its new position for the current frame.

We do this for every object in our scene and lo' and behold. Things are moving!

What happens if the new positions of two objects would cause their geometries to overlap?

The scene below shows two objects and their current velocities on a certain frame in our game loop.

Let's think about what would happen if we didn't do anything special and simply continued with the next iteration of our game loop.

In this case, the physics engine would update each objects' positions as usual based on its current velocity. This would cause the objects to penetrate each other and eventually pass through each other.

You can see this happening in the demonstration below by dragging the slider to progress time.

This situation, where continuing to update the objects' positions would cause the objects to penetrate, is called a collision.

Part of a physics engine's job is to resolve collisions between objects.

Conceptually, this is actually quite simple. The goal of collision resolution is to change each object's velocity so that as the simulation progresses the objects will no longer penetrate each other.

We can define two equations for the respective post-collision velocities of our bodies.

Where $\vec{v}_{a, i}$ and $\vec{v}_{b,i}$ are the velocities of bodies $a$ and $b$ before the collision, $\vec{v}_{a,f}$ and $\vec{v}_{b,f}$ the velocities after the collision, and $\Delta \vec{v}_{a}$ and $\Delta \vec{v}_{b}$ the respective changes in velocity caused by the collision. The subscripts $_i$ and $_f$ stand for initial and final, respectively.

If we want our collision behavior to look realistic, we have to ensure that whatever values we pick for $\Delta \vec{v}_{a}$ and $\Delta \vec{v}_{b}$ satisfy the relevant laws of physics. What are these laws? Well, that's what the majority of this series of articles is going to be about!

To start, let's try defining what a collision is a little more rigorously.

What is a collision?

Take a look at the scene below. This scene shows two bodies on a specific frame of our game. We can see that the bodies are touching, but are they colliding?

In the last section we learned that two bodies are said to be colliding if continuing to move them along their current velocities would cause them to penetrate each other. So, with the information we've been given, can we actually determine if the scene above depicts a collision or not?

We can't! All we know is that the bodies are touching. We haven't been given any information about their velocities.

To see why this matters, take a look at the demonstration below.

You can change the velocities of the bodies by dragging the arrows around. The indicator tells you if the current configuration would lead to a collision or no collision. You can verify the result by playing the simulation.

We can see that depending on the velocities of the bodies, the same scene can either represent a collision or not.

Towards a definition

In order for two bodies to be colliding, two conditions have to be met:

1. The bodies' geometries have to be touching or overlapping
2. The bodies are still moving towards the collision

Let's assume that point 1 is true for now and focus on point 2, instead. What does it mean for two bodies to be moving "towards the collision"? This seems like a pretty circular definition.

Instead of asking what it means to move towards the collision, let's ask what it means to move away from the collision. In fact, let's ignore collisions entirely for a moment. What does it mean to move away from a surface?

The image below shows a box sitting on the floor. What direction would you have to move the box in order to move it away from the floor?

At first glance, this seems like a silly question. Obviously, we'd have to move the box up.

However, there are an infinite number of directions that we could move the box! As long as we are moving it generally upwards, we are increasing the distance between the box and the floor.

Notice that while the box was moved the exact same distance in each direction—that is, the length of the arrows is the same—some of the boxes are clearly further away from the floor than others.

So, are some of these directions more "up" than others? Is there a direction that is most "up"?

To explore this idea, let's play a little game.

Surface normals

You are given a box sitting on the floor. Your goal is to move the box so that its distance to the floor is as close as possible to the total distance the box was moved. It doesn't matter how far you move the box, just that these two distances are as close to each other as possible.

To make things a little more challenging, the angle of inclination of the floor is going to change every time you reset the game.

I know, I know, Game of the Year material right here. But hopefully you were able to figure out that the direction that maximizes the distance between the box and the floor is the direction that is perpendicular to the floor, which isn't necessarily straight up!

This direction is called the normal direction, often referred to as simply the normal of the surface. The normal direction of a surface is always perpendicular to the surface. It is the direction that points directly away from the surface.

Normal directions are represented with a normalized vector; that is, a vector with length $1$. A vector with length $1$ is also called a unit vector. To make it clear that a vector is normalized, we often add a little hat on top of the variable like this $\hat{n}$.

If our surface is perfectly straight, the normal direction is the same everywhere on the surface. However, if the surface is curved, the normal direction will be different for each point on the surface. The easiest way to demonstrate this is with a circle. If we stick with the idea that the normal direction points directly away from a surface, then the normal direction for any point on the circle's circumference is the direction from the center of the circle to that point.

More generally, the normal direction for a point on a surface is perpendicular to the tangent of the surface at that point.

We saw earlier that it isn't necessary to move the box directly in the normal direction in order to move it away from the floor.

What all these directions have in common, is that they all generally point in the same direction as the surface normal. We say that these directions have some component in the normal direction. Let's take a closer look at what this means, exactly.

The dot product

To calculate how much of one vector is pointing in the same direction as another vector, we can use the dot product of the two vectors. In our example, the two vectors are the direction we move the box and the surface normal. The dot product between two vectors $\vec{a}$ and $\vec{b}$ is written as $\vec{a} \cdot \vec{b}$