Collision Detection for 2D and 3D Games

Understand the Two-Phase Pipeline

The broadphase is the first filter. It answers the question: which pairs of objects might be colliding? It does this by testing AABBs, which are cheap to compute and cheap to compare. Two AABBs overlap if and only if they overlap on all axes simultaneously. For 3D, that means six comparisons (min and max on x, y, and z). This test is fast but imprecise, because a sphere's AABB includes the corners that the sphere does not fill. So the broadphase produces false positives, pairs whose bounding boxes overlap but whose actual shapes do not touch.

The narrowphase is the second filter. It takes the candidate pairs from the broadphase and tests exact geometric overlap using algorithms specific to each shape combination. Sphere vs sphere is a distance check. Box vs box can use the Separating Axis Theorem (SAT). Arbitrary convex shapes use the GJK algorithm. The narrowphase produces contact points: the exact location, normal direction, and penetration depth of each collision. These contacts feed into the constraint solver, which computes the forces needed to push the objects apart.

The reason for two phases is efficiency. The narrowphase algorithms are expensive, especially GJK and EPA for complex convex shapes. Running them on every possible pair would be prohibitive. The broadphase eliminates 95% or more of the pairs, so the narrowphase only processes the few dozen that are actually close to each other.

Choose a Broadphase Strategy

Different broadphase algorithms suit different scene layouts. The three most common are AABB trees (also called BVH, bounding volume hierarchies), sweep-and-prune (SAP), and spatial hash grids.

AABB trees organize objects in a tree structure where each node's bounding box encloses all objects in its subtree. Finding overlaps means traversing the tree and pruning branches whose bounding boxes do not overlap the query. This scales well to large scenes with objects at varying densities. Rapier uses a dynamic BVH that rebalances automatically as objects move, with SIMD-accelerated traversals for additional speed. AABB trees are the best general-purpose broadphase for scenes where objects are spread unevenly.

Sweep-and-prune sorts objects along one or more axes and walks the sorted list to find overlapping intervals. It is very fast when objects are mostly stationary or move slowly, because the sorted order barely changes between frames. Cannon-es offers SAPBroadphase as its recommended option. SAP works best when objects cluster along one axis, like a side-scrolling game where everything sits near the ground plane.

Spatial hash grids divide the world into uniform cells and assign each object to the cells it overlaps. Overlap tests only check objects in the same cell. This approach is simple and fast for 2D games where objects are roughly the same size. It struggles with objects of vastly different sizes, because a large object spans many cells and creates redundant pairs. Grid-based broadphase is common in 2D engines like Matter.js.

Implement Narrowphase Testing

For primitive shapes, narrowphase tests are straightforward formulas. Sphere vs sphere: compute the distance between centers and compare it to the sum of radii. If the distance is less, the spheres overlap, and the penetration depth is the difference. The contact normal points from one center to the other. This is the fastest possible collision test.

AABB vs AABB: check for overlap on all three axes. If overlap exists on all axes simultaneously, the boxes collide. The contact normal is typically along the axis of minimum penetration. This test is fast but only works for axis-aligned boxes. Rotated boxes require the Oriented Bounding Box (OBB) test, which is more expensive.

For arbitrary convex shapes, the GJK (Gilbert-Johnson-Keerthi) algorithm determines whether two convex shapes overlap by searching for a point in their Minkowski difference that is at the origin. If the origin is inside the Minkowski difference, the shapes overlap. GJK is iterative and converges quickly for most shape pairs. When GJK confirms overlap, the EPA (Expanding Polytope Algorithm) computes the penetration depth and contact normal by expanding a simplex from GJK until it reaches the boundary of the Minkowski difference.

The Separating Axis Theorem (SAT) is an alternative for convex polygons in 2D and convex polyhedra in 3D. It tests all potential separating axes (normals of each face and edges in 3D) and determines that the shapes are separated if any axis shows a gap. SAT is conceptually simpler than GJK and can be faster for low-polygon shapes, but its cost grows with the number of faces and edges.

For concave shapes (shapes with indentations or holes), no single algorithm works directly. The engine either decomposes the concave mesh into convex parts (convex decomposition) and tests each part separately, or it tests individual triangles of a triangle mesh against the other shape. Triangle mesh collision is expensive and should only be used for static scenery like terrain, walls, and level geometry.

Handle Fast Objects with CCD

Discrete collision detection checks for overlaps at each physics step. If an object moves far enough in one step to pass completely through a thin wall, the overlap is never detected. This is called tunneling, and it is a common problem with bullets, high-speed projectiles, and small fast-moving objects.

Continuous collision detection (CCD) prevents tunneling by sweeping the object's shape along its velocity vector and finding the first time of impact within the step. Instead of testing the shape at its current position, CCD tests the entire volume it passes through during the frame. This is more expensive than discrete detection, typically two to five times slower per body, so it should only be enabled on objects that actually need it.

In Rapier, enable CCD per body with bodyDesc.setCcdEnabled(true). Rapier uses swept-volume CCD that handles both linear and angular motion. In Cannon-es, there is no built-in CCD, but you can approximate it by raycasting along the body's velocity vector before each step and checking if the ray hits anything within the step distance. If it does, teleport the body to the hit point instead of letting it pass through. In Havok via Babylon.js, CCD is configured through the body's motion type and quality settings.

An alternative to CCD for very fast objects is to skip physics bodies entirely and use raycasting for bullets. Cast a ray from the gun barrel in the firing direction, check for the first hit, and apply damage immediately. This is called hitscan and is how most first-person shooters handle bullets. It avoids the tunneling problem entirely because rays test the full path in a single frame.

Set Up Collision Filtering

Collision filtering controls which objects can collide with which. Without filtering, every object tests against every other object, which wastes broadphase and narrowphase time on pairs that should never interact. More importantly, filtering prevents undesirable gameplay interactions like a player's own grenades hurting the player, or NPC allies blocking the player's movement.

Most engines use a bitmask system with two values per body: membership (which groups this body belongs to) and filter mask (which groups this body can collide with). A collision occurs only if body A's membership has at least one bit in common with body B's filter mask, and vice versa. For example, assign bit 1 to players, bit 2 to enemies, bit 4 to player projectiles, and bit 8 to enemy projectiles. Set player projectiles' filter mask to exclude bit 1 (players) so they pass through the player, and set enemy projectiles' mask to exclude bit 2 (enemies).

In Rapier, set collision groups with colliderDesc.setCollisionGroups(membership | (mask << 16)). The upper 16 bits are the mask and the lower 16 bits are the membership. In Cannon-es, set body.collisionFilterGroup and body.collisionFilterMask as separate integer values. In Havok/Babylon.js, set shape.filterMembership and shape.filterCollideMask.

Sensor bodies (triggers) deserve special mention. A sensor detects overlaps but does not produce collision response, meaning objects pass through it without bouncing. Sensors are used for pickup zones, damage fields, level boundaries, and event triggers. Configure them by setting the body or collider to sensor mode, then listen for overlap events.

Process Contact Points and Events

When two shapes collide, the narrowphase produces one or more contact points. Each contact has a position (where the shapes touch), a normal (the direction to push them apart), and a penetration depth (how far they overlap). The constraint solver uses these to compute impulses that separate the bodies and apply friction.

For gameplay, you care about collision events, not raw contact points. Most engines provide callbacks or events that fire when a collision starts, persists, or ends. Use collision-start events for impact damage, sound effects, and particle spawning. Use collision-end events for detecting when the player leaves a trigger zone. Use collision-persist events sparingly, since they fire every frame and can be expensive if your handler does significant work.

The impact velocity (or impulse magnitude) tells you how hard the collision was. Use it to scale damage, choose between soft and hard impact sound effects, and determine whether to break a destructible object. A gentle touch might produce a quiet tap, while a high-speed impact triggers a crash sound and spawns debris particles.

Contact normals are useful for wall sliding, slope detection, and surface alignment. If the contact normal points mostly upward, the player hit a floor and should be marked as grounded. If it points sideways, the player hit a wall and should slide along it. If the angle is between, the player is on a slope, and you can decide whether to let them walk up it or slide down based on the slope steepness.