Collision Detection in 2D

An explanation of the Separating Axis Theorem

November 6, 2022

If you have ever played any video game in your life, you used algorithms that solve the hard problem of collision detection, without even knowing about it. The solutions are often ingenious and answer the question of "what do we need all this math for" beautifully. This post is a deep dive into one of those solutions. The SAT algorithm.

This post is going to answer that question, by explaining one particular algorithm based on the SAT theorem.

In all the demos of this article, you can drag around the polygons (and their points), as well as rotate polygons around their centers by pressing the A or D keys.

What you see in the demo above is based on the SAT (Separating Axis Theorem) Algorithm. We'll derive this idea and how it can be used for collision detections, with mathematics and in code, step by step.

The main idea behind it is rather simple.

If you can draw a line between two shapes, without touching either of them, then the two shapes do not collide.

If you can find such a line, you know for sure, that the two shapes are separated from each other by (at least) that line. And that's why this line can be called a "separating axis", and that's exactly where the name of the theorem comes from.

But how does the computer search for the lines that separate two shapes? It's using shadows.

Shadows?

If you shine a light onto an object from very, very far away and track where the shadow falls on a wall, you get what is mathematically known as a "projection". Projections are a useful concept in linear algebra and we need them for the SAT algorithm.

For the next section you should be comfortable with some basic concepts of vectors, if you aren't here's a summary of the concepts necessary.

Projections

There is a mathematical expression for how to calculate where that projection (shadow) of a point (object) would fall on a line (wall).

Given the Points $a$ , $b$ , and $c$ , where $c$ is the point we want to project and $a$ and $b$ are the two points defining the line $\overline{ab}$ , we can find the projection of $c$ onto the line $\overline{ab}$ like so:

p = c - a

q = b - a

proj_c \, q = \frac{a + p \, \cdotp q}{\lVert q \rVert^2}* q

The same formula can be expressed in code:

function projectOnLine(a: Vec2, b: Vec2, c: Vec2) {
    const p = c.sub(a);
    const q = b.sub(a);
    return a.add(q.multScalar(p.dot(q) / q.mag2()));
}

Drawing this out onto the canvas yields a line going through $a$ and $b$ and an arrow $p$ , going from $a$ to $c$ , which casts a shadow on the line from $b$ to $a$ .

The above can be done for any 2 vectors. For a line, we needed 2 points to get the direction of the line and to shift the result onto the line by adding on the vector/point a. The whole idea for only two vectors can be expressed more shortly and is also a useful operation to have in general.

proj_b \, a = \frac{a \, \cdotp b}{\lVert b \rVert^2} * b

The same idea in Typescript:

function project(a: Vec2, b: Vec2) {
  return b.multScalar(a.dot(b) / b.mag2());
}

There is also the idea of using a scalar projection. A scalar is just a number, and the result of scalar projections are just numbers. A scalar projection calculates the length of the projection of the vector and in the direction of vector b. And it can be computed like so:

s = \lVert a \rVert * cos(\theta) = a \, \cdotp \hat{b}

Notice the little hat on the b, that means that this is a unit vector.

Projecting a Whole Polygon

In the SAT Algorithm the projections of the polygons determine whether or not a single ray of light could shine through in between them. If there is such a ray of light, the two can't collide. Otherwise, how could the light get through?

The ray of light is the separating axis.

So the goal is easier now: For the two polygons we only need to find two shadows (projections) that don't overlap to determine that they don't collide.

However, to get there, we first need to be able to project a whole polygon onto a line. Casting the shadow for a whole object, not just for a single point...

Luckily, a polygon is just a set of points. Usually, the points of a polygon are called vertices in computer graphics. If we were to project all the vertices of a polygon we would still have to figure out which points are the "left" and "right" edge of the shadow.

There are multiple approaches to do this, but one I find particularly fascinating and which is the one used down below in the demos is that of using a support function.

Essentially a support function finds a point among a set of points (here the vertices of the polygon we want to project), that is furthest along in a particular direction.

export function getSupportPoint(vertices: Vec2[], direction: Vec2) {
  let highest = -Infinity;
  let support = new Vec2(0, 0);
  
  for (let vertex of vertices) {
    const dot = vertex.dot(direction);
	
    if (dot > highest) {
      highest = dot;
      support = vertex;
    }
  }
  
  return support;
}

If we run the support function in the two directions of the line we want to project on, we get out only two points.

We can then use these two support points to project them onto the line. Which gives us the "left" and "right" edge of the shadow.

export function drawProjection(
  ctx: CanvasRenderingContext2D,
  polys: Polygon | [Polygon, Polygon],
  p1: Vec2,
  p2: Vec2
) {
 

  // get directions for "up" and "down" the line
  const d2 = p2.sub(p1);
  const d1 = p1.sub(p2);

  // create translation matrix
  const origin = new Vec2(parseFloat(ctx.canvas.style.width) / 2, parseFloat(ctx.canvas.style.height) / 2);
  const toOrigin = getTranslationMatrix(origin.x, origin.y);
 
  // use translation matrix + scaling to create far-apart line points
  // which goes through the origin in the middle of the canvas 
  const len = Math.max(parseFloat(ctx.canvas.style.width), parseFloat(ctx.canvas.style.height));
  const l1 = d2.unit().multScalar(len).transform(toOrigin);
  const l2 = d2.unit().multScalar(-len).transform(toOrigin);

  ctx.strokeStyle = "rgba(100, 100, 100, 0.5)";
  line(ctx, l2, l1);
  
  const s1 = getSupportPoint(poly.vertices, d1);
  const s2 = getSupportPoint(poly.vertices, d2);
  
  // get a projection for each support point
  const projectedS1 = projectOnLine(l1, l2, s1);
  const projectedS2 = projectOnLine(l1, l2, s2);
  
  // draw shadow based on projections
  line(ctx, projectedS1, projectedS2);

  // also draw a dashed line between the projected and support points
  ctx.save();
  ctx.setLineDash([5, 15]);
  ctx.strokeStyle = "rgb(150, 150, 150)";
  line(ctx, s1, projectedS1);
  line(ctx, s2, projectedS2);
  ctx.restore();
}

Projection for 2 Polygons

All of this also works for 2 Polygons at once of course! The question we would like to answer given the two shadows is whether or not they overlap. Since the shadows are two line segments, that we know to be collinear we can use a simple test like the one below to check whether or not they overlap.

function onSegment(p: Vec2, q: Vec2, r: Vec2) {
  if (
    q.x <= Math.max(p.x, r.x) &&
    q.x >= Math.min(p.x, r.x) &&
    q.y <= Math.max(p.y, r.y) &&
    q.y >= Math.min(p.y, r.y)
  )
    return true;

  return false;
}

function doIntersect(a1: Vec2, a2: Vec2, b1: Vec2, b2: Vec2) {
  if (onSegment(a1, b1, a2)) return true;
  if (onSegment(a1, b2, a2)) return true;
  if (onSegment(b1, a1, b2)) return true;
  if (onSegment(b1, a2, b2)) return true;

  return false;
}

There are also versions of this test, which use the dot product to determine how far along the line the points are and by comparing the minimum and maximum against each other determine whether or not they overlap. Which algorithm we use doesn't matter so much in the end, the important thing is that we can test for the two shadows "overlapping" or not. In the example below, if the shadows overlap we change the color to red.

The Last Idea

How should we pick the lines that we project onto? Isn't there an infinity of possible lines we could choose from?

Luckily for us, there is a last insight for the SAT algorithm to work, namely that we only have to check a single axis for every edge of the polygons we want to check for collisions. Namely, need to check each of the normals of the edges, and see if the shadows projected onto that normal overlap. You can see that in the example below, where we are slowly cycling through the different normals, one by one!

The only thing we are interested in from the normal is the direction, so we displace it towards the origin and draw a line passing in the same general direction that the normal was pointing in. Usually, normals would be directly on the edge of the polygon.

The edge to which the normal belongs is colored yellow in the example and you can see how the line drawn through the origin is always perpendicular to the yellow edge (because the direction is taken from the normal that has to be the case)!

In the above example, if you make the shapes overlap, what do you notice about their shadows?

Complete SAT

In the demo above, we stop for a second at each step just for visualization purposes. We could just check all of the normals "at once". If all shadows overlap (and show up in red), then the shapes also have to overlap. They are colliding. That's the whole meaning behind the separating axis theorem.

To sum up the algorithm:

Cast shadows onto the normals of two polygons

Check if the shadows overlap

If all shadows overlap, there is a collision.

If you find a single pair of shadows that doesn't overlap, there can't be a collision, because you have found a separating axis.

Now you might say, wait for a second... we don't yet prevent the shapes from intersecting with each other, do we?

And you would be right.

This is an important distinction in collision detection algorithms, between calculating if two shapes collide, and then what to do to deal with that collision.

This second problem is usually known as calculating a collision response. So, how could we appropriately respond to the collision?

Adding a Collision Response

Luckily for us, SAT is easy to adapt to get out a collision response – namely, if you find that all shadows (and therefore the shapes) overlap, you can find the pair of shadows that overlaps the least, and push the two shapes apart in that direction until the shadows don't touch anymore.

This idea of the "overlap" between the two shadows is related to an idea known as the MTV – the Minimum Translation Vector. In a way, the smallest overlap of the shadows of the two polygons projected onto their normals is a vector that tells us exactly how far and in which direction the two shapes have to move so that at least one pair of shadows stops overlapping. It represents the minimum amount of work necessary to push the shapes apart. So we just apply half of the vector as a translation transformation to one shape and the opposite of that to the other shape.

Let's see how we could implement that idea in code:

function getShadowOverlap(
  axis: Vec2,
  pointsA: Vec2[],
  pointsB: Vec2[]
) {
  const rangeA = flattenPointsOn(pointsA, axis);
  const rangeB = flattenPointsOn(pointsB, axis);

  let overlap = 0;
  if (rangeA.min < rangeB.min) {
    if (rangeA.max < rangeB.max) {
      overlap = rangeA.max - rangeB.min;
    } else {
      const option1 = rangeA.max - rangeB.min;
      const option2 = rangeB.max - rangeA.min;
      overlap = option1 < option2 ? option1 : -option2;
    }
  } else {
    if (rangeA.max > rangeB.max) {
      overlap = rangeA.min - rangeB.max;
    } else {
      const option1 = rangeA.max - rangeB.min;
      const option2 = rangeB.max - rangeA.min;
      overlap = option1 < option2 ? option1 : -option2;
    }
  }

  return overlap;
}

export function getResponseForCollision(poly1: Polygon, poly2: Polygon) {
  let smallestOverlap = Infinity;
  let axis = new Vec2(0, 0);
  // loop over all the polygon normals
  for (let normal of [...poly1.edgeNormals(), ...poly2.edgeNormals()]) {
    // get the overlap between the shadows
    const overlap = getShadowOverlap(normal, poly1.vertices, poly2.vertices);
    const absOverlap = Math.abs(overlap);
    // check if the overlap is the smallest so far
    if (absOverlap < Math.abs(smallestOverlap)) {
      smallestOverlap = overlap;
      axis = normal.copy();
      if (overlap < 0) {
        axis.multScalar(-1);
      }
    }
  }

  return axis.transform(getScalingMatrix(smallestOverlap, smallestOverlap));
}

Then we can use that getResponseForCollision function like so:

// get MTV
const responseVector = getResponseForCollision(poly1, poly2);
// scale MTV by 0.51 or -0.51 respectively.
const half = responseVector.multScalar(0.51);
const oppositeHalf = responseVector.multScalar(-0.51);
if (response) {
  // if a response should happen, translate polygons by MTVs
  poly1.translate(oppositeHalf);
  poly2.translate(half);
} else {
  // if a response should not happen – draw the MTV arrows
  drawArrow(ctx, poly1.centroid(), poly1.centroid().add(oppositeHalf));
  drawArrow(ctx, poly2.centroid(), poly2.centroid().add(half));
}

And here is the demo:

The Problem of Concavity

Cool, so we are done now, right? Well, check this out:

Well... that didn't go too well huh? The problem is that what you just saw were so-called "concave" shapes... All the polygons you've seen so far up to this point were "convex" and therefore just worked.

Convex and concave express whether something bulges in- or outwards. I remember them with the word "cave" as in concave. A cave goes inward, and so does a concave object. In other words, concave shapes are shapes that have some kind of indentation in them. A star would be a concave shape, or something looking like a V or U.

To handle collisions with concave shapes is very tricky... so instead, we don't bother and just chop their concave shapes up into simple, convex shapes and then run collision detection algorithms on them.

To do that, we are going to use a process called triangulation. Chopping an arbitrary shape up into triangles, is not a trivial problem and has more than one solution! We'll look at one of them known as the "Ear Clipping Algorithm".

The Ear Clipping Algorithm or how to triangulate Polygons

Triangulating Polygons is a tough problem because there are so many weird edge cases to deal with. There have been whole papers written about how to efficiently do it (see resources below) and I won't go into too much detail here, and neither will I attempt to fix all the possible edge cases.

The algorithm we are going to use for triangulating concave shapes into a bunch of convex triangles is known as "Ear Clipping".

Ear Clipping?

The basic idea is to find "ears" – triangular pieces of the polygon that "stick out", like an ear, and then "clip" them out of the polygon, reducing the problem to a smaller polygon – for which we can then find another ear to clip, and so on until only a last triangle is left.

If you turn off the visualization, you can drag around the polygon vertices to try out different shapes!

Let's define what an "ear" is more formally. An ear is a set of three consecutive vertices, $a$ , $b$ and $c$ if two conditions are met:

The interior angle between edge $\overline{ab}$ , and $\overline{bc}$ has to be smaller than 180°
The triangle formed by the three vertices can not contain any other vertices of the polygon.

When an ear is found, we put it into our list of triangles for the triangulation, remove the vertices from the list of vertices to check, and keep looping over the rest of the vertices left and check for another ear. We can keep doing this until just 3 vertices are left – those will form the last ear. In code this would look something like this:

type Triangle = [Vec2, Vec2, Vec2]
function triangulate(p: Vec2[]): Triangle[] {
  const n = vertices.length - 1;
  if (n < 3) return [];

  // assemble the list of vertices to check
  let indexList: number[] = vertices.map((_, i) => i)
  
  let triangles = [];
  let triangleIndexCount = 0;

  let i = 0;
  while (indexList.length > 3) {
    // this is a hack –> in case the internal angle is exactly 180° – the loop would run forever
    if (i++ > 1000) {
      break;
    }
    for (let i = 0; i < indexList.length; i++) {
      const a = indexList[i];
      const b = getItem(indexList, i - 1);
      const c = getItem(indexList, i + 1);

      const va = vertices[a];
      const vb = vertices[b];
      const vc = vertices[c];

      // calculate edges
      let va_to_vb = vb.sub(va);
      let va_to_vc = vc.sub(va);

      // check the inner angle between the two edges
      // this uses the "perpendicular dot product" – the 2D analog of the cross product.
      // if this is 0 or smaller than 0 the angle is greater than 180° 
      if (va_to_vb.perpDot(va_to_vc) < 0) {
        continue;
      }

      let isEar = true;
      for (let j = 0; j < vertices.length; j++) {
        // skip if the vertex is part of the ear
        if (j === a || j === b || j === c) {
          continue;
        }

        // check if the vertex is in the triangle
        if (isPointInTriangle({ p: vertices[j], triangle: [va, vb, vc] })) {
          isEar = false;
          break;
        }
      }

      // add ear vertex indices to triangulation
      if (isEar) {
        triangles.push([vb, va, vc]);
        indexList.splice(i, 1);
        break;
      }
    }
  }

  // loop is done, one triangle remaining, add it to the list as well.
  const va = vertices[indexList[0]];    
  const vb = vertices[indexList[1]];
  const vc = vertices[indexList[2]];
  triangles.push([vb, va, vc]);

  return triangles;
}

// helper function to determine whether or not a point is within a triangle
function isPointInTriangle({p, triangle: [ a, b, c ]}: { p: Vec2; triangle: Triangle }) {
  const v0 = c.sub(a);
  const v1 = b.sub(a);
  const v2 = p.sub(a);
  
  const dot00 = v0.dot(v0);
  const dot01 = v0.dot(v1);
  const dot02 = v0.dot(v2);
  const dot11 = v1.dot(v1);
  const dot12 = v1.dot(v2);

  const denom = dot00 * dot11 - dot01 * dot01;
  // u and v here are just placeholder names.
  const u = (dot11 * dot02 - dot01 * dot12) / denom;
  const v = (dot00 * dot12 - dot01 * dot02) / denom;

  return u >= 0 && v >= 0 && u + v < 1;
}

function getItem<T>(arr: T[], i: number) {
  if (i >= arr.length) {
    return arr[i % arr.length];
  } else if (i < 0) {
    return arr[(i % arr.length) + arr.length];
  }
  return arr[i];
}

For now, this is it. We can have collision detection and responses for both convex and concave shapes.

However... Collision detection is a tricky business and there are still edge cases where the above breaks down.

Limitations

The first that comes to mind: Curved shapes. Anything that doesn't have vertices doesn't work with the above algorithms and we would need to convert it first. Also, the triangulation implemented doesn't handle holes and breaks if the interior angle between two edges of a polygon is exactly equal to 180° or the polygon intersects with itself. Most of these problems could be tackled simply by using a better triangulation algorithm, in case you are curious there is a list of resources down below.

Another problem could be objects or shapes that move very quickly. If they move quickly enough and the step size is bigger than the thing they should collide with, they could simply pass through (or "over") the other object. In games, usually bullets and thin walls would show this kind of behavior and problem. It's like the shape were "tunneling" through the other shape because it moved so fast that there never was a position update where the two were overlapping...

Yet another problem is that of performance when there are lots of things that could potentially collide with each other. I mean, all of the above code is written for clarity rather than performance so there are improvements to be gained in "simply" rewriting the collision code we have, but the problem of checking collisions for many shapes at once remains $O(n^2)$ . Which is bad...

What if n is more than 2? If it is 10, 100, or 1000? Collision detection algorithms of any kind are expensive and if we have to check every single polygon against every single other polygon the amount of computations we have to do grows exponentially. Which will eventually slow down to a halt.

This means we have to use some clever data structure or algorithm to reduce the number of collisions to check.

Spatial Subdivision

One way to do so would be to divide up the "space" into separate regions or "buckets". Because two shapes that are very very far apart can not intersect (unless one of them is big) we could cut down on the number of collision detections we have to do by a lot, because only things from the same bucket could potentially collide with one another.

The general algorithm that could be used for that is called a Quadtree (in 2D) or an Octree (in 3d). Here's an image of the idea in 3D:

But coding these is reserved for another time.

If you came all this way – congratulations! I hope you learned something. You can inspect most of the code for the demos of this website at the repo for this page over here.

Resources

If you want to read more, I have assembled a list of resources for this project that I used while building. Here you go:

SAT

Triangulation

Subscribe to Live and Learn

Twice a month. Quotes, photos, booknotes and interesting links. Bundled together in one heck of a Newsletter. No spam. No noise.

Check out what you missed so far.

Keep reading:

Fractal Garden Learnings – Part 2

This is part 2 of a series of posts on building the fractal.garden, my first 1-month project. It will dive into the technical learnings and decisions that went into making the fractal.garden website.

The beauty of being alive.

I am sitting alone in my room. It is dark outside and my speakers play some soft and mellow music. FKJ, beautiful piano, some techno mixed into it...

Site Demo

This is a site demo! It is only a quick showcase of what this blog can do, to test when refactoring that all the bits and pieces still work and also to show how flexible markdown setups with MDX are! Maybe, I'll write a writeup on how this blog works...