The problem: collision is everywhere in games
Every game has to answer one question over and over: did this thing touch that thing?
Did the bullet hit the enemy? Did the player land on the platform? Did the sword swing pass through the goblin? Did the car crash into the wall? Did the cursor click the button?
That question has a name. Collision detection.
It sounds simple. It is not. A typical game runs collision checks thousands of times per frame, 60 times per second. If each check is slow, the whole game is slow. If each check is wrong, the player walks through walls or floats above the floor.
So game engines need a way to answer "did A touch B" that is both fast AND correct.
The naive way: check every triangle
Remember that 3D models are made of triangles. A character mesh might be 20,000 triangles. A wall might be 500 triangles.
The naive collision check is: for every triangle in the player, test if it overlaps any triangle in the wall. 20,000 × 500 = 10 million triangle vs triangle tests. Per pair of objects. Per frame.
If the scene has 100 objects, that's 100 × 100 × 10 million = 100 billion checks per frame. Your game runs at 0 fps. The CPU melts.
The fix: collision shapes
Game objects use a separate, simpler shape just for collision. The thing you see (the visual mesh) and the thing the engine uses for collision (the collision shape) are two different things.
The visual mesh of a character: 20,000 triangles, looks like a person.
The collision shape of the same character: maybe a single capsule (a cylinder with rounded ends). Or a box. Or a sphere. Or a small handful of simple shapes glued together.
Why? Because checking "did this capsule touch that box" is something you can do with a few math operations. Checking "did 20,000 triangles touch 500 triangles" is not.
So what shapes can we use?
Game engines have a small list of "primitive shapes" that are fast to test for collision:
Sphere. Two spheres collide if the distance between their centers is less than the sum of their radii. One math operation. Fastest collision check there is.
Box. Slightly more math but still cheap.
Capsule. Like a cylinder with rounded ends. Great for characters.
Cylinder. Sometimes.
Plane. For floors and walls.
Most things in games can be simplified using these shapes or a mix of them. A character can be a capsule. A barrel can be a cylinder. A crate can be a box. A coin can be a small box.
But what if your shape isn't any of these? What if it's a weird custom shape, like a rock with bumps, or a sword, or a piece of architecture with multiple jutting parts?
That's where convex hulls come in.
What "convex" actually means
Before we talk about convex hulls, let's talk about what the word "convex" means. This is the word that tripped me up when I was learning this stuff.
A shape is convex if you can draw a straight line between any two points inside the shape, and the entire line stays inside the shape.
That's it. That's the whole definition. Pick any two points in the shape, connect them with a straight line, never leave the shape.
A circle is convex. Pick any two points inside it, draw a line, the line never leaves the circle.
A square is convex. Same test, same result.
A triangle is convex. A box is convex. A capsule is convex. Any shape made by stretching a balloon outward is convex.
A shape is concave (the opposite of convex) if you can find at least two points inside it where the line between them goes OUTSIDE the shape at some point.
A donut is concave. Pick a point on one side of the hole and a point on the other side. The line between them passes through the hole, which is outside the donut. So a donut is not convex.
A star shape is concave. A letter "L" is concave. A capital "C" is concave. Any shape with a dent, hole, or curve that bends inward is concave.
Why convex shapes are a big deal for collision
Here's the magic. Collision detection between two convex shapes is fast. Like, really fast. There are clean math algorithms (one famous one is called GJK) that can test "did these two convex shapes collide" in just a few microseconds.
But collision between a concave shape and anything else is hard. The math doesn't have a clean shortcut. You usually end up breaking the concave shape into pieces somehow, which gets messy.
So engines work hard to avoid concave shapes. They want every collision shape in the scene to be convex.
The reason: with convex shapes, the engine knows that the shape has no "hidden" parts. No tunnels. No notches. No pockets. The outside is fully outside. That property is what lets the math be clean.
What a convex hull is
A convex hull is the smallest convex shape that fully wraps around a given set of points or a given mesh.
Imagine you have a complicated mesh, like a treasure chest with a curved lid, handles sticking out, and detail bumps on every surface. That mesh is concave (it has dents and gaps).
Now imagine wrapping a tight rubber band or a piece of plastic wrap around the whole thing. The wrapper touches the outermost points but skips over the dents and notches. The result is a simpler shape that:
That's a convex hull. The "shrink-wrapped" version of your mesh.
In 2D, picture nails hammered into a board in a random pattern. Stretch a rubber band around all the nails. The shape of the rubber band is the convex hull of those nails.
Convex hulls in 3D
Same idea. Take any 3D mesh, no matter how detailed. The convex hull is the smallest convex shape that fully wraps it.
A character mesh has thousands of triangles, with concave parts (the gap between legs, the curve of the armpit, the space between fingers). Its convex hull might be just 30 to 50 triangles, like a rough faceted balloon around the character.
Game engines compute the convex hull of a mesh once, save it, and use that for collision instead of the original mesh. You went from 20,000 triangles to 50 triangles, AND those 50 triangles form a convex shape that's fast to test against.
That's the trick. That's why convex hulls are such a big deal.
What you give up
Convex hulls aren't perfect. By definition they ignore dents and gaps in the original shape. So:
The space between a character's legs gets filled in. The hull treats it as a solid.
A donut's hole gets filled. The donut becomes a flattened disc.
An "L" shaped piece of architecture becomes a triangle that fills the inner corner.
For most things this is fine. A character with the leg gap filled in still collides correctly enough that the player can't tell. A donut prop in a game probably doesn't need bullets to fly through the hole.
But for some shapes you DO need the concave parts. A house with a doorway. A tunnel. A cup that things should be able to fall into. A maze.
How engines handle truly concave shapes
When you really need the concave parts, engines use one of these tricks:
Convex decomposition. Break the concave shape into a bunch of smaller convex pieces. A donut becomes maybe 12 wedge-shaped chunks arranged in a ring. Collision is then "did anything touch any of these 12 convex pieces." Slower than one convex check but still fast. Tools like V-HACD do this automatically.
Triangle mesh collision (only for static stuff). For things that never move (the ground, the level geometry, big buildings), engines do use the actual triangles, but with heavy spatial optimizations like a BVH (bounding volume hierarchy) so they only check the few triangles near the player. This works for static geometry but is too slow for moving objects.
Compound shapes. Manually glue several primitive shapes together. A character might be a sphere for the head, a capsule for the torso, capsules for each limb. Each piece is convex, the whole assembly approximates the character.
The pattern is always the same: keep collision shapes convex, and if you can't, break them into multiple convex pieces.
