Spatial Partitioning

You can now test whether two objects collide — with the separating axis theorem — and turn a click into a pick ray. One problem remains, and it is a killer at scale: in a world of n objects, which pairs do you even bother testing? The naive answer — every pair — is a trap.

Spatial partitioning is the fix: organise objects by where they are so that each one is only ever tested against its near neighbours. It is the broad phase of collision detection — a cheap cull that throws out the overwhelming majority of pairs before the expensive exact test (the narrow phase) runs at all.

Why all-pairs is hopeless, and how partitioning saves it

Step 1 — count the pairs. Testing every distinct pair among n objects is

\binom{n}{2} = \frac{n(n-1)}{2} \;=\; O(n^2).

For n=100 that's 4{,}950 tests; for n=1000, 499{,}500; for n=10{,}000, nearly 50 million — every frame. Quadratic growth is death by a thousand tests: ten times the objects, a hundred times the work.

Step 2 — the key observation: distant objects can't collide. Two objects far apart in space will never touch, so testing them is wasted work. If we could ask only “is anything near me?” we'd skip almost every pair. Partitioning answers exactly that — it sorts objects into regions of space, and an object is compared only with others in its own region (and adjacent ones).

Step 3 — a uniform grid. Lay a grid of cells over the world and drop each object into the cell(s) it overlaps. To find collisions for an object, test only the objects sharing its cell and the eight (in 2-D) neighbouring cells. With objects spread roughly evenly across k cells, each cell holds about n/k objects, so the work drops from O(n^2) toward O(n) — when the density is uniform. Its weakness: clump everything into one cell and you're back to all-pairs.

Step 4 — a quadtree / octree adapts to the clumping. Where a grid uses one fixed cell size everywhere, a quadtree (2-D) recursively splits a square into four children only where it's crowded, and an octree does the same with eight in 3-D. Empty regions stay one big cell; dense regions subdivide deep. The depth of any object's leaf is O(\log n) for well-distributed data, so locating and querying neighbours costs about O(\log n) per object.

Step 5 — a bounding-volume hierarchy (BVH) for the objects themselves. A BVH wraps each object in a simple bounding volume (an AABB or sphere), then pairs them into nested parent volumes, all the way up to one root that encloses the scene. To test something, descend the tree: if it misses a node's volume, every object in that whole subtree is skipped. One cheap rejection prunes an exponential number of leaf tests.

Step 6 — collect the win. Each structure replaces the O(n^2) all-pairs sweep with a broad phase nearer O(n\log n): each object is located in the structure in about O(\log n) and compared only with a constant-ish handful of neighbours rather than all n-1 others. The same trees answer ray queries too — a ray descends a BVH or octree, skipping subtrees it can't reach — so picking and visibility get the identical speed-up.

For collision and spatial queries over n objects:

All-pairs is \binom{n}{2}=O(n^2) — quadratic, and infeasible for large scenes.
A uniform grid buckets objects into cells; test only same and adjacent cells — \approx O(n) when density is uniform.
A quadtree / octree recursively subdivides space where it is crowded, giving O(\log n) depth for well-distributed data.
A BVH nests bounding volumes into a tree; a missed node prunes its entire subtree.
Together these turn the broad phase from O(n^2) toward O(n\log n), and accelerate ray queries the same way.

A 4K frame has roughly eight million pixels, and a path tracer fires several rays per pixel, each bouncing a few times — tens of millions of rays per frame. A scene has millions of triangles. Testing every ray against every triangle is the O(n^2) nightmare squared, and it is simply impossible at 60 fps.

The BVH is the single data structure that makes it tractable. Each ray descends the hierarchy, rejecting whole branches whose bounding box it misses, and reaches only the handful of triangles it might actually hit — turning millions of triangle tests into a logarithmic walk. This is exactly why modern GPUs ship dedicated ray-tracing cores whose job is BVH traversal and box intersection in hardware: the maths of spatial partitioning, baked into silicon. The same hierarchy that lets a physics engine cull collision pairs in a big open world is what lets the GPU light it in real time.

A faster query is not automatically a faster frame. Every structure above also costs something to build and keep up to date: a quadtree or BVH has to be rebuilt (or repaired) whenever the objects inside it move, and for objects that shuffle every single frame that update cost can swamp whatever you saved on the query side.

So the right structure depends on how static vs dynamic the scene is, not on query speed alone. Mostly-still geometry (level walls, terrain) amortises a one-off BVH build over thousands of frames — nearly free per frame. A cloud of fast-moving particles or bullets rebuilt from scratch every tick can make the "smarter" tree slower in wall-clock time than a plain uniform grid, which is cheap to re-bucket every frame precisely because it has no hierarchy to repair. Pick the structure for the *churn* of the scene, not just its size.