Spatial acceleration structures

// status: seedling

Any non-trivial 3D problem — ray tracing, collision, nearest-neighbour queries, broadphase physics — benefits from a structure that rejects large irrelevant regions quickly. These are four important families and when to reach for each.

Bounding Volume Hierarchy (BVH)

A binary tree of axis-aligned bounding boxes. Each node's box contains the boxes of its children. Leaves hold primitives.

• Query (ray or point): start at root, if box isn't hit, prune. Otherwise recurse. Classic depth-first traversal with a small stack.
• Build: recursive top-down split with the Surface Area Heuristic (SAH) — the cost of a split is P_L · N_L + P_R · N_R where P is the ratio of child-box surface area to parent. Minimise it.
• Refit: when primitives move, walk leaves up and expand the parent boxes. Much cheaper than rebuild, mesh quality degrades over time.
• Update: fully dynamic scenes use LBVH (linear/Morton-sorted) or "twin BVH" rebuild-vs-refit strategies.

BVH is the default for ray tracing. Hardware-RT APIs such as Vulkan ray tracing and DXR expose bottom- and top-level acceleration structures; the driver builds an opaque implementation from geometry and instances. BVH and SAH concepts remain useful even when the representation is hidden.

Strengths: excellent for ray queries with varying densities. Builds in O(N log N) with decent quality. Refits handle animation.

Weaknesses: overlapping boxes mean "traverse both children" is common. Pointer-chasing on CPU; worth flattening to a linear array with skip-indices.

k-d tree

A binary tree that alternates splitting dimensions (x, y, z, x, y, z…). Each split is a plane.

• Great for static point clouds and nearest-neighbour queries.
• Better ray-tracing performance than BVH in the 2000s — since overtaken for dynamic scenes by BVH, but still competitive on fully static high-quality builds.
• Builds are expensive if you want SAH-quality; median splits are fast but much worse.
• Useless for dynamic scenes — splits aren't easily refittable.

Where I see them today: pro offline renderers, exact-nearest-neighbour in ML preprocessing, FLANN, and photon maps.

Octree / Quadtree

Regular 8-way (3D) or 4-way (2D) subdivision of a cube. Subdivide only non-empty cells.

• Natural fit for voxel data (see Sparse Voxel Octrees).
• Cheap to build, cheap to update, cache-friendly layout (Morton-ordered).
• Less adaptive to primitive distribution than BVH — cells are fixed; long thin objects span many cells.
• Great for broadphase collision, particle binning, view-frustum culling of grid-aligned data.

Quadtrees do the same job in 2D (terrain LOD, 2D physics, tile culling).

Uniform grid / spatial hash

Partition space into cubes of equal size; primitives hash into cells.

• Fastest possible build: O(N).
• Best insertion/update in the world: O(1) per primitive.
• Terrible when density varies wildly — empty regions waste memory; dense regions degenerate.
• Spatial hashing (map 3D index to a hash table) gives you a grid without allocating for empty cells.
• DDA traversal (Amanatides & Woo) walks rays through the grid one cell at a time.

Perfect for broadphase collision of same-scale objects, SPH/position-based dynamics, particle-particle queries, small voxel worlds.

Picking one

Two-level BVH

The standard pattern for animated scenes:

• BLAS (Bottom-Level) — per mesh, built once, stays in the mesh's local space.
• TLAS (Top-Level) — contains instances, each referencing a BLAS with a transform. Rebuilt or refit per frame.

RTX/DXR use this model directly. Very cheap per-frame update compared to rebuilding a full-scene BVH.

The Surface Area Heuristic

The SAH cost of a split puts numbers on intuition. For a parent box with surface area A_P and a candidate split into left/right with areas A_L, A_R and primitive counts N_L, N_R:

\text{cost} = C_{\text{traverse}} + \frac{A_L}{A_P} N_L C_{\text{isect}} + \frac{A_R}{A_P} N_R C_{\text{isect}}

Why it works: the probability that a random ray entering the parent also enters a child is proportional to the child's surface area. Weighted by primitive count, that's expected intersection cost. Minimise it.

Fast builders approximate SAH with binned SAH: quantise primitive centroids into K bins per axis, evaluate cost at bin boundaries only. Near-optimal quality, O(N) per split.

Things that tripped me up

• Flat arrays help locality — a linear node layout avoids per-node allocations and can traverse more predictably than a linked-pointer tree. The gain depends on node layout, workload, and CPU.
• Short-stack / stackless — stack depth and divergent traversal can hurt GPU software BVHs. Sibling links, parent links, or bounded short stacks are useful design options; hardware traversal details are implementation-specific.
• Bounding box precision — single-precision float boxes for meshes at large world coordinates lose precision. Either keep a per-object local space or use double-precision in the builder.
• Tree quality vs build time — SAH is slow. For real-time rebuilds, use LBVH (sort by Morton code, build from bits). For static scenes, spend the build time.
• Refit vs rebuild — refit many frames, full rebuild every N. Measure trace time and trigger rebuild when it degrades.

References

• Physically Based Rendering (Pharr, Jakob, Humphreys) — the definitive chapter on accel structures, free online.
• Wald, I. — On fast construction of SAH-based Bounding Volume Hierarchies.
• Karras, T. — Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees (NVIDIA).
• Amanatides, J., & Woo, A. — A Fast Voxel Traversal Algorithm for Ray Tracing.

Back to Notes · see also Sparse Voxel Octrees · GPU-Driven Visibility for Large Worlds · Ray marching and SDFs