Collision Detection

Often, in games, you want to know if an object is touching another object, if a laser is bouncing off a mirror, if the player character is standing on something, or the player is clicking on a specific part of the UI. These are all problems that involve writing functions to check for collisions between different sorts of geometric objects.

In addition to simply checking for intersections, it will also often be useful for a collision routine to report:

• collision location (perhaps in the local coordinate system of both colliders)
• collision normal (direction of most rapid separation)
• the closest pair of points between the objects (if not colliding)

So also keep these use cases in mind in the following discussion.

There is no single best algorithm for all collision detection scenarios, but there are some big ideas that can be useful in designing collision handling systems. In this lesson we will discuss a few of these big ideas in three topic areas:

• Early Out: speeding up collision detection by skipping checks that aren't needed.
• Mathematical Ideas: structures that can help you think about the collision detection process.
• Valid Spaces: avoiding complex collision checks by using world representations that guarantee validity.

Early Out

The fastest collision check is the one that is never performed. "Early Out" code attempts to bail out of collision checks as quickly as possible -- generally, by having a fast check that can prove items are not colliding.

Simple Checks First

The type of early out you will almost always see in collision code is to perform a low-computational-cost test on a pair of potential colliders before performing a high-cost test. For example, you might do a sphere vs sphere test (costs a few subtracts, multiplies, and a comparison) before doing a convex-vs-convex or mesh-vs-mesh test.

This can even be done in the normal course of an intersection check -- if your code needs to check three different things, it should probably be checking the quickest-to-check one first.

The Broad Phase

Even with very fast object-vs-object tests, your code will still need to perform \( \frac{n(n-1)}{2} \) checks given \( n \) objects unless it has some fast way of excluding pairs of objects that can't possibly overlap. This is the job of a broad phase -- code that comes up with a list of pairs of objects to collision check, generally in faster than \( O(n^2) \) time.

Consider a 2D game world containing objects in three boxes, A, B, and C:

Can objects in box A and box C possibly overlap? Why or why not?

Broad phase checks can be built on a wide range of spatial data structures, but all boil down to the same basic reasoning: if \(A\) is contained in \(X\), and \(B\) is contained in \(Y\), then if \(X\) doesn't intersect \(Y\), \(A\) cannot intersect \(B\). Or, slightly more generally, and written in math:

And, indeed, we can make a similar statement about distances: if \(A\) is contained in \(X\) and \(B\) is contained in \(Y\), then the distance between the closest points in \(A\) and \(B\) is at least the distance between the closest points in \(X\) and \(Y\).

A Shout-Out to Grids

You can use a wide range of spatial data structures in games (binary space partition trees, in particular, turn out to be really beautiful to write code for, and have a long history with games). But when you want structures that are darn easy to write code for and will work decently, the choice is clear: use uniform grids.

So let's go on a quick tour of some of the flavors of uniform grid you might use.

First, here's the vanilla grid. This is the simple, lazy thing that I use whenever checking all pairs of colliders isn't quite fast enough:

#include <glm/gtx/hash.hpp> //(0)
struct Collider {
	//...
	//axis-aligned bounding box:
	glm::vec2 aabb_min;
	glm::vec2 aabb_max;
};
void broad_phase( std::vector< Collider > &colliders, std::function< void(Collider &, Collider &) > const &report_pair ) {
	glm::vec2 constexpr GridSize = glm::vec2(1.0f, 1.0f); //(1)
	std::unordered_multimap< glm::ivec2, Object * > grid;
	grid.reserve(colliders.size()); //(2)
	for (auto &collider : colliders) {
		glm::ivec2 min = glm::ivec2( //(3a)
			std::floor(collider.aabb_min.x / GridSize.x),
			std::floor(collider.aabb_min.y / GridSize.y)
		);
		glm::ivec2 max = glm::ivec2( //(3b)
			std::floor(collider.aabb_max.x / GridSize.x),
			std::floor(collider.aabb_max.y / GridSize.y)
		);
		for (glm::ivec2 cell = min; cell.y <= max.y; ++cell.y) {
			for (cell.x = min.x; cell.x <= max.x; ++cell.x) {
				auto others = grid.equal_range(cell); //(4)
				for (auto other = others.first; other != others.second; ++other) {
					report_pair(*other, collider); //(5)
				}
				grid.emplace_hint(equal_range.first, &collider);
			}
		}
	}
}

While this sort of vanilla, hash-based uniform grid works really well as-is on moderately-sized worlds, they can begin to break down in large worlds. You can improve performance with a few simple-to-code tricks.

• There's no reason to fully recompute the grid each frame. You could, instead, remove and add objects as they move. This can be a huge savings if you have a bunch of static objects.
• If you know the bounds on the world, you can use a std::vector to hold the grid instead of a std::unordered_multimap. This will save hash computations at the expense of (potentially) a bit more memory use.
• You can also build a two-level grid, where the top-level grid stores pointers to sub-grids. This can improve memory locality and (depending on how you represent the top-level and sub-grids) save hash computations. Taking this method to its logical conclusion would give you a quadtree-like structure; but, often, two levels is enough.
• In 3D-but-generally-flat games, you can use a 2D grid and ignore the vertical dimension, saving a bit of memory but costing a few more fine-scale collision checks.

Temporal Broad Phase

Spatial data structures aren't the only way to avoid doing collision checks.

Consider a 2D game world containing three circular objects A, B, and C at the following positions:

If the maximum velocity that any object can travel in the game is 1 unit / second, can A and B can possibly intersect in the next 3 seconds of gameplay? Why or why not?

How might you use this idea in a game to avoid performing collision checks between every pair of objects every frame? (Describe at a high level, do not write code.)

Mathematical Ideas

When devising collision checks, it is important to think about collisions in the right way. What is the right way? Well, it depends on the situation.

In this section, I will equip you with some different mathematical ideas which can be useful in building collision checks.

Convexity

You have probably run into the notion of a convex object (or set) before. A set of points \( C \) is convex if every line between two points in the set is itself contained in the set:

It turns out that convexity is exactly the property you want objects to have to make them easy to perform collision and distance checks between. We'll see a bit of why this is below.

Convex objects are so nice to work with that you'll often find yourself splitting more complex objects (e.g., complicated polygons) into simple convex objects (e.g., triangles) in order to perform collision or distance checks. This process is known as convex decomposition, and it is worth looking into (especially) approximate convex decomposition before writing your own algorithms. (It's also generally worth asking your artist if they would be willing to hand-build such a decomposition, since they will do a better job and it's generally pretty easy to do.)

Minkowski Sum

The Minkowski Sum of two sets \(A\) and \(B\) is the set of sums of elements of the sets:

I'll also use \( A - B \) to denote the set of differences of elements.

This is much easier to think about if we draw a picture:

The above three observations form the basis for the GJK algorithm, a general-purpose closest-point / collision algorithm which is powerful and worth knowing about, but is also typically considered very difficult to implement properly.

It is also worth noting that explicitly computing the Minkowski sum or difference of simple objects is entirely feasible, and a good way to write simple collision checks which are straightforward to visualize and debug.

Separating Axis

Perhaps paradoxically, the easiest way to demonstrate that two objects collide is to check all of the ways they might not collide and -- if they don't not collide in any of these ways -- conclude that they must collide.

Your key tool in any collision check between two convex objects is the separating axis theorem, which states that two convex sets do not overlap if and only if there exists a direction along which their projections do not overlap. This direction is called the "separating axis", and there may be one than one.

A key observation which you should take a moment to reason about using intuitions from the Minkowski Sum discussion above is that for two non-overlapping convex polytopes, there always exists a separating axis perpendicular to a face of one of the polytopes.

Thus, if you want to write a check for collisions between two convex polygons your code can check all the edges of each polygon to see if its perpendicular works as a separating direction. If it finds a separating direction among the perpendiculars to the edges, then it can report that the polygon's don't intersect; otherwise, it can report that they must intersect. (Though, unfortunately, it won't have computed an intersection point.)

Admittedly, it would generally be just as quick to explicitly compute the intersection by repeated half-plane clipping steps, and the resulting overlap polygon would also allow your code to readily compute a collision location and normal. This is worth thinking about for a moment. (And, really, writing up convex/convex polygon intersection is worth doing. I'd have you write it right here if this weren't already a bit long as a lesson. It's surprisingly enjoyable code to put together.)

A totally incidental claim for which I currently don't recall a satisfying proof is that any arrangement of non-intersecting convex objects may be transformed into any other arrangement of the same objects by a sequence of moves, where each move involves translating a single object along a straight, intersection-free path.

Continuous Collision Detection

When objects are travelling very quickly, you may wish to check for collisions at all points along their trajectory.

While this may at first seem complex, notice that an object \( A \) traveling along linear path \( v_a \) and object \( B \) traveling along linear path \( v_b \) will intersect at time \( t \) such that the Minkowski sum \[ (A + tv_a) - (B + tv_b) = (A - B) + t(v_a - v_b) \] contains zero. In other words, computing the continuous collision time between two objects moving along linear paths can be computed by tracing an appropriate ray into their Minkowski difference.

Note that this approach generally must handle rotations separately, either by using rotationally-symmetric collision geometry for the object of interest or by resolving rotations using instant-to-instant checking and doing continuous checks for translation only.

Voronoi Regions

A Voronoi diagram divides space into a set of Voronoi cells (regions), each of which is closest to some specific feature of an object.

The Voronoi diagram is interesting to think about when computing closest-point queries because if you can figure out what Voronoi cell a point is, you know what feature it must be closest to.

Signed Distance Fields

While all the above machinery can be really useful for doing collision or distance checks, sometimes the right answer really is to just compute a look-up table. A signed distance field is just that: a look-up table of how far inside (or outside) of an object every point in some volume of space around that object is.

Say you want to check if a point is inside the object. With a signed distance field this operation takes a single memory access and comparison -- distanceField.at(pt) < 0. For things where low-res collisions are enough -- e.g. GPU particle systems or ray-marched soft shadows -- signed distance fields are a brilliant tool to keep in your back pocket.

Valid Spaces

We generally discuss collision as being about keeping players out of level geometry; that is, testing and rejecting invalid configurations. But, in some cases, it actually makes sense to instead think about keeping players inside the level interior; that is, constraining the world to the space of valid configurations. (An idea akin to generalized coordinates, coordinates that represent a physical system in terms of its degrees of freedom.)

Imagine, for example, that you are building a 3D exploration game where a player walks around a complex world. Because the player can only walk (and not, say, jump), the player can only ever access a limited subset of the space.

If your asset pipeline could pre-compute (or, indeed, you could hand-author) this manifold of positions -- say, as a triangle mesh -- your runtime code could then prevent the player from intersecting the world by keeping the player's position on the valid position mesh. This turns a complex 3D problem (is the player intersecting any object in the world?) into a simple 2D problem (is the player's position still in the same triangle? If not, what neighboring triangle should it be in?).

This is a Walk Mesh approach to collision avoidance (not detection because collisions with level geometry are never checked). It's very convenient for games where you want players to walk (or run) around largely static scenes and you don't want to deal with fancier collision detection schemes.