### 2D Rigid Body Collision Resolution

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

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.

A word about math

While these articles will involve a fair bit of math, please don’t be discouraged

by that if you don’t consider yourself to be a “math person”.

I think this kind of thinking is harmful and actively prevents you from engaging

with topics that you might actually enjoy!

Many times, it’s the math *notation* that makes things look more complicated

than they actually are because it’s so information-dense and unfamiliar.

Most of the math in these articles will be fairly straight-forward arithmetic

but dressed up to look fancy!

This is something that’s really dear to my heart.

I think too many people have this instinctive reaction of

*“I’m not smart enough to understand this”* whenever they see any kind of math

notation.

While I can definitely empathize with this, I encourage you to fight this

reaction because at some point it becomes a self-fulfilling prophecy.

## 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.

Without collision resolution

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.

After collision resolution

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.

Collision Resolution

The goal of collision resolution is to find the values of

$Delta vec{v}_{a}$ and $Delta vec{v}_{b}$.

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.

That doesn’t look right

You might have noticed that the way the two boxes bounce off each other looks

a little strange.

This is because, in order to keep things simple for now, we’re not yet

making the boxes spin when they hit each other.

Don’t worry we’ll add that in a later post, but let’s try and keep the

complexity to a minimum for now.

### Towards a definition

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

- The bodies’ geometries have to be touching or overlapping
- 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}$.

The dot product can be defined either algebraically or geometrically.

Algebraically, the dot product is defined as the sum of the products of the

corresponding components of the two vectors.

For two-dimensional vectors such as the ones we’re dealing with, we can write

this as:

Note that the result of the dot product is a *scalar*, not another vector.

While this is fairly straight-forward to calculate, it’s not exactly obvious

what this scalar *represents*.

Luckily, there is also a geometric interpretation of the dot product that can be

visualized nicely.

Say we have two vectors **a** and **b** that

have some angle **θ** between them.

Next, starting from the tip of **a** let’s draw a line

perpendicular to **b** connecting the two vectors.

The length from the base of **b** to the point where the

perpendicular line intersects **b** is called the

**scalar projection** **s** of **a**

onto **b**.

Imagine a light that’s perfectly perpendicular to **b** shining

down on **a**.

The scalar projection is the length of the shadow that **a**

casts on **b**.

Since we now have a right triangle, trigonometry tells us that the length of

this **projection** is the product of the length of

**a** (the hypotenuse) and the cosine of the angle between the

two vectors.

To be precise, it’s the *absolute value* of the scalar projection that gives us

the length of the shadow, since we will see in a moment that the scalar

projection can also be negative.

This is equivalent to the dot product of **a** and the unit

vector **$hat{b}$** in the direction of

**b**.

Well hold on, that’s a bit of a bait and switch!

Why are we suddenly talking about the *unit vector in the direction of
b*?

That’s not what we wanted to find!

How do we get the dot product between

**a**and

**b**itself?

By definition, $hat{b}$ and $vec{b}$ are already

pointing in the same direction.

The only difference between them is their length.

Since unit vectors have a length of 1, all we have to do is multiply

$hat{b}$ by the length of $vec{b}$.

Therefore, multiplying both sides of by

$| vec{b} |$ gives us the full geometric definition of the dot

product.

In English, the dot product of two vectors is the length of the scalar

projection of one vector onto the other, multiplied by the length of the vector

we’re projecting onto.

Before moving on, take a second to think about the following questions.

You can click on them to reveal the answers.

I mentioned earlier that the scalar projection, and therefore the dot product,

can also be negative.

A lot of the time, we’re actually more interested in the *sign* of the dot

product rather than its actual value.

The demonstration below shows the **dot product** between

**two** **vectors** as well as the

**angle** between them.

You can control the **angle** between the vectors with the

**slider** below.

The angle is normalized to always be between 0° and 180°.

Pay attention to the **sign** of the **dot product** as you

change the **angle**.

Can you tell at what **angles** the

**dot product** is negative or positive?

How about when it’s zero?

Think about how looking at the sign of the **dot product**

can help us determine if two vectors are generally pointing in the same

direction or not.

If the angle between the vectors is **acute** (less than $90^{circ}$),

the dot product is **positive**.

A positive dot product indicates that the vectors are generally pointing in the

same direction.

If the angle is **obtuse** (greater than $90^{circ}$), the dot product

is **negative**.

A negative dot product indicates that the vectors are generally pointing in

opposite directions.

If the angle is **exactly $90^{circ}$**, the dot product is **zero**.

### Tying it all together

We started out by asking what it means for two bodies to be moving *towards*

the collision.

To answer this, we took a slight detour and looked at what it means to move away

from a *surface*.

Using the dot product, we can now answer the second question.

As long as the velocity vector of the body has some component in the normal

direction of the surface normal, i.e. the dot product between these vectors is

positive, the body is moving *away* from the surface.

Even so, it might not be immediately obvious how this helps us answer the

original question.

Let’s look at our two boxes again.

This situation differs from the previous example of the box and the floor in two

ways:

- We have
*two***velocity vectors**instead of one, one for

each box. Which one do we use? - There is no “surface”, is there? What is our surface normal?

To answer the first question, instead of using the individual velocities of the

boxes, we use their *relative velocity*.

As the name implies, the relative velocity tells us the velocities of the bodies

relative to each other.

The relative velocity is the vector difference between the individual velocities.

In this article, I will denote the relative velocity of bodies $a$

and $b$ as $vec{v}_{ab}$.

Geometrically, the relative velocity $vec{v}_{ab}$ is the vector

that points from the tip of the velocity vector $vec{v}_b$ to the

tip of the velocity vector $vec{v}_a$.

All other things being equal, two cars hitting each other head-on at

$50 frac{text{km}}{text{h}}$ each is the same as one car

hitting a stationary car at $100 frac{text{km}}{text{h}}$.

What about the second question?

What’s our surface and its corresponding normal?

What we’re looking for is called the *collision normal*.

Unfortunately, the way you calculate the collision normal depends on the shapes

(or geometries) of the colliding bodies, so I can’t just show you a single

formula.

What we’re dealing with is called a *vertex-edge collision*.

In this type of collision, a point (or vertex) on one body collides with a

side (or edge) of another body.

We’ll talk more about collision normals when we take a look at the forces that

act during the collision.

For now, you’ll have to take my word that in a vertex-edge collision, the

collision normal is perpendicular to the edge.

In our example, the **collision normal** looks like this:

If we label our bodies **a** and **b**, by convention, the collision normal

points toward body **a**.

It’s fairly arbitrary which body is called **a** or **b** as long as we’re

consistent throughout our calculations.

Based on what we learned about surface normals earlier, the

**collision normal** tells us the direction that points

directly away from the surface of the collision.

We can now calculate the dot product between the relative velocity of the bodies

$vec{v}_{ab}$ and the collision normal $hat{n}$ to

determine if the bodies are moving towards the collision or not.

We’ll call this value the *relative normal velocity*.

It is the component of the relative velocity in the direction of the collision

normal.

For now, we only care about the sign of the relative normal velocity, but we’ll

see later on that it plays an important part in calculating the forces that act

during the collision.

Using our understanding of the dot product, we can say that

- if the relative normal velocity is
**positive**, the bodies are already

separating - if the relative normal velocity is
**negative**, the bodies are still smashing

into each other

The demonstration below combines all concepts we’ve learned so far.

As before, you can change the **velocities** of the boxes by

dragging the arrowheads.

The top right corner shows the **collision normal** and

**relative velocity** of the bodies.

You can see that as soon as the angle between the

**relative velocity** and the

**collision normal** is less than or equal to

$90^{circ}$—and therefore the dot product is positive—the bodies are

no longer colliding.

So, finally, we can formally define what a collision is:

Definition

A collision occurs when a point on one body touches a point on another body

with a negative relative normal velocity.

Neat!

## Conclusion

If you made it to this point, pat yourself on the back!

We now have a formal definition of what a collision is, as well as the set of

equations we’re ultimate trying to solve when resolving collisions

(see ).

Not bad at all!

In the next post, we’ll dive into the actual physics behind collisions.

If you enjoyed this article, you’ll love the next part!

This is all I have for you today.

Thank you so much for reading and I hope I’ll see you again for the next post.

*If you want to discuss this article, feel free to either reach out to me on
Twitter or shoot me an email at
*

**me@kai-sassnowski.com**.