# ==Spatial acceleration structures== <p class="doc-sub">// status: seedling</p> Any non-trivial 3D problem — ray tracing, collision, nearest-neighbour queries, broadphase physics — needs a structure that lets you skip the 99% of space that's irrelevant to your query. These are the four families that matter 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 on modern GPUs (RTX, RDNA2+) traces through a BVH that you build via `VkAccelerationStructureKHR` / DXR equivalent; the API takes triangles and returns an opaque BVH handle. You still need to understand SAH because that's what you're working with conceptually. 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 | Need | Reach for | |------|-----------| | GPU ray tracing | BVH (the API builds one) | | CPU ray tracing, mostly static | BVH with SAH, or k-d tree | | Voxel grids, big sparse worlds | Octree / SVO | | Real-time physics broadphase | Uniform grid / spatial hash | | Nearest-neighbour on point clouds | k-d tree | | Heightfield terrain | Quadtree | | Mixed scene with animated characters + static BG | Two-level BVH — TLAS of per-object BLAS | # 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 beat pointers** — a linear array of BVH nodes with `firstChild + skipIndex` traverses 2–3× faster than a linked-pointer tree on modern CPUs. - **Short-stack / stackless** — stack depth hurts GPU BVH. Stackless traversal with sibling pointers or parent pointers is what RTX-class traversals actually do. - **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 [[Index|Notes]] · see also [[Sparse Voxel Octrees]] · [[Ray marching and SDFs]]