I'm learning about collision detection in 3D games and initially assumed worlds might use a large 2D or 3D grid where each cell records whether it is occupied. I've since learned that games often use simple colliders such as boxes, capsules, or spheres, then check only nearby objects instead of allocating a huge occupancy array.
That makes sense for simple objects, but how does collision detection work with irregular geometry, such as caves, hills, valleys, or detailed terrain? Surely the game does not test the player against thousands or millions of tiny boxes every frame. Does the terrain get represented as polygons or triangles, and if so, how does the engine efficiently determine which parts to test?
4 Answers
A useful way to picture it is to divide a million-polygon terrain into spatial regions. The engine first checks which regions overlap the player’s collision volume, then tests only the polygons inside those regions. A grid, tree, octree, or similar structure makes that lookup much cheaper than checking every polygon. Static terrain can have this acceleration structure built ahead of time, while moving objects are handled separately.
Collision detection is usually split into broad, mid, and narrow phases. The broad phase uses cheap bounding boxes or spheres to find pairs of objects that might overlap. The mid phase can use a structure such as a bounding-volume hierarchy to narrow a complex mesh down to a small group of possible triangles. The narrow phase then performs the accurate test, using the appropriate geometry algorithm for the pair—for example, center distance for spheres or the separating axis theorem for boxes and triangle meshes.
So the triangles are the detailed geometry, while the boxes and spheres are mostly used to quickly rule out areas that cannot possibly collide?
For static levels, the expensive organization work is usually done during development or when the level is built. The engine can divide the mesh into cells or build a hierarchy of bounding volumes. During gameplay it first tests the player against those simple volumes, then checks the actual triangles only in the handful of regions that could contain a collision. Dynamic objects need their own simpler colliders and updates, but the same broad-phase idea still applies.
The terrain generally is not stored as a giant one-or-zero occupancy array. It is usually represented by a mesh made of triangles, sometimes with additional simplified collision meshes rather than the exact visual model. The triangles describe the cave walls and terrain surface, and mathematical intersection tests determine whether the player’s collider touches them. Spatial partitioning keeps the number of triangle tests small.
For moving through the world, engines also use swept-volume or continuous collision tests when necessary, rather than checking only a few points ahead. That helps prevent a fast-moving player from passing through a thin surface between frames.
That helps. The geometry may still consist of many triangles, but the spatial structure prevents the engine from examining all of them every frame. It is more like finding the right chapter and page before reading the relevant sentence.