I'm learning about collision detection in 3D game programming. At first, I imagined representing the world with a 2D or 3D array where each coordinate stores whether that space is occupied. Then I learned that games often use simpler collision shapes—such as boxes, spheres, or capsules—and check only nearby objects instead of maintaining a huge occupancy grid.
That makes sense for basic objects, but how does collision detection work with irregular environments such as caves, hills, valleys, and other detailed terrain? Would the game represent the shape using thousands or millions of small cubes or grid cells? Or is the environment usually stored as a polygon mesh and tested using some other method? I'm especially curious how the game determines whether the player is inside a cave, hitting a wall, or about to move through an uneven surface without checking every polygon in the entire level.
4 Answers
Collision detection is usually split into broad, mid, and narrow phases. The broad phase uses cheap shapes like bounding boxes or spheres to find pairs of objects that might be touching. The mid phase can use a structure such as a bounding volume hierarchy to narrow a complex mesh down to only the relevant parts. The narrow phase then performs the accurate test, often against individual triangles. The exact math depends on the shapes involved—for example, sphere-to-sphere tests use distances, while box and triangle tests can use the separating axis theorem.
An occupancy array is useful for voxel-style worlds, but it is usually wasteful for general 3D terrain. A mesh stores surfaces rather than every empty volume, and spatial acceleration structures make queries efficient. Static geometry can be preprocessed, so the game does not rebuild the structure every frame. Dynamic objects use their own simple colliders and are checked against nearby static and dynamic objects only.
The collision mesh is often simpler than the visible graphics. A cave might be rendered with a highly detailed model, while physics uses a lower-resolution mesh made of triangles, boxes, capsules, or other approximations. This gives the player believable collisions without requiring the physics system to process every visual detail. For movement, the engine also sweeps the player's collision shape along the intended path rather than checking only a few points, which helps prevent fast objects from passing through thin surfaces.
A useful way to picture this is dividing the level into spatial regions. Suppose a terrain has a million triangles split among a thousand grid cells. The game first checks which cells overlap the player's collision volume, then tests only the triangles inside those cells. A binary tree, octree, k-d tree, or bounding volume hierarchy does the same job with different tradeoffs. Static terrain can have this structure built ahead of time, while moving objects are handled separately.
That doesn't necessarily mean the terrain is made from little cubes like a voxel game. The cells or bounding boxes are mainly an index for finding geometry; the actual surface can still be a detailed triangle mesh.
So the triangles are still the actual detailed geometry, but the hierarchy prevents the game from testing every triangle in the entire cave?