Spatial Data Structures

Goals

Given objects in $k$-dimensional space, answer geometric questions

• $k$-nearest neighbors
• Find data points within a range
• Ray tracing

Goals

Given objects in $k$-dimensional space, answer geometric questions

• $k$-nearest neighbors
• Find data points within a range
• Ray tracing

Goals

Given objects in $k$-dimensional space, answer geometric questions

• $k$-nearest neighbors
• Find data points within a range
• Ray tracing

1D Case

• We can use binary search trees
• Every leaf in left sub-tree is smaller than every leaf in right sub-tree
• $O(\log N)$ time to find an element
• What are $k$-dimensional equivalents of BSTs?

Spatial Division vs. Object Hierarchy

Spatial Division vs. Object Hierarchy

Spatial Division vs. Object Hierarchy

Uniform Grid

• Keep a list of objects contained for each cell of a grid
• May use sparse storage to skip empty cells
• Popular for 2D problems
• Drawbacks:
  • Need to pick a grid size
  • Might need to visit many grid cells for large queries, even if empty

Uniform Grid: Operations

• Construction:
  for each object $O$:
  for each cell $(x, y, z)$ overlapping with $O$:
  append $O$ to $\mathrm{grid}(x, y, z)$
  

• Search:
  for each cell $(x, y, z)$ overlapping with query $Q$:
  for each object $O$ in $\mathrm{grid}(x, y, z)$:
  output $O$
  

• Can search nearest neighbors by visiting larger and larger disks
• Trace rays by walking along a line

Uniform Grids in Parallel

• Instead of explicitly allocating entries in each cell, sort objects by their cell indices
• Store the first index of each cell in an array

KD-Tree

• Idea: Use axis-aligned hyperplane to split entries
• Take the median of some axis as a splitting plane
• Cycle through the $k$ different axes of the coordinate system

KD-Tree Construction

$\mathrm{Build}$(objects, depth):
if objects contains only one object:
return a leaf node
else:
$i \gets \mathrm{depth} \mod k$
$m \gets$ the median of the $i$th coordinate
$a \gets \mathrm{Build}$(objects below the plane $\mathbf{x}_i = k$, depth $ + 1$)
$b \gets \mathrm{Build}$(objects above the plane $\mathbf{x}_i = k$, depth $ + 1$)
return $\mathrm{Node}(\mathbf{x}_i = k, a, b)$

KD-Tree Search

$\mathrm{Search}(n, Q)$:
if $n$ is a leaf in $Q$
output $n$
else:
if $Q$ contains part of the half-space $\mathbf{x}_i \le k$:
$\mathrm{Search}$(left child of $n$, $Q$)
if $Q$ contains part of the half-space $\mathbf{x}_i \ge k$:
$\mathrm{Search}$(right child of $n$, $Q$)

KD-Tree Nearest Neighbor

$r \gets \infty$
$\mathrm{Search}(n, \mathbf{q})$:
if $n$ is a leaf in $Q$
if $d(n, \mathbf{q}) \le r$
$r \gets d(n, \mathbf{q})$
else:
$\mathrm{Search}$(child of $n$ containing $\mathbf{q}$, $\mathbf{q}$)
if other child of $n$ intersects with sphere of radius $r$ centered at $\mathbf{q}$:
$\mathrm{Search}$(other child of $n$, $\mathbf{q}$)

Bounding Volume Hierarchy

• Instead of splitting space, group objects
• Typically uses Axis-Aligned Bounding Boxes (AABB) in proxy for objects
• Other options: bounding spheres, Oriented Bounding Boxes (OBB)
• Recent Survey: [Meister et al, 2021]

BVH Construction: Top-Down

• Given $n$ objects, we partition them into (at least) 2 groups
• There are $2^n$ possible partitions
• 2 Problems:
  1. How to tell a "good" partition from a "bad" one?
  2. How to find a suitable partition without spending too much time

BVH Quality: Heuristics

• Use an estimate
• How much time do we spend on a given node? \[E[t(k)] = t_{\mathrm{visit}} + \sum_{x \in \mathrm{child}(k)} P(\mathrm{hit}(x) | \mathrm{hit}(k))t_{\mathrm{query}}(x)\]
• Typical heuristic for ray tracing: Surface-Area Heuristic \[P(\mathrm{hit}(x) | \mathrm{hit}(k)) = \frac{\mathrm{surface}(x)}{\mathrm{surface}(k)}\]

BVH Construction: Top-Down

• Can’t afford to check every partition usually
• Typically:
  • sort objects along each of the $k$ axes, find minimum of the cost function for all $kn$ possible splits
  • Pick a finite number of bins (e.g. 16) of equal size and choose the best one
• Cost of children nodes approximated as cost of leave node (i.e. proportional to number of primitives)

BVH Construction: Bottom-Up

• Start with one node per object
• Combine two nodes that produce minimum-cost tree when merged
• Repeat until all nodes are merged
• Much more costly, but usually higher-quality tree

BVH Range Query

$\mathrm{Search}(x, Q)$:
if $x$ is a leaf in region $Q$:
output $x$
else:
for each child $k$ of $x$ intersecting $\mathrm{Q}$:
$\mathrm{Search}(k, Q)$

BVH Ray-Intersection

• Most popular acceleration structure for ray tracing
• Need to traverse both subtrees (in some cases)
• In order to speed up search: go front to back

$d \gets \infty$
$\mathrm{Search}(x, \mathrm{ray})$:
if $x$ is a leaf:
$t \gets$ distance from $\mathrm{ray}$ to $x$:
if $t \le d$:
$d \gets t$
else:
for each child $k$ of $x$ intersecting $\mathrm{ray}$:
if $d \ge$ distance to front of box:
$\mathrm{Search}(k, \mathrm{ray})$

BVH Update

• We don’t have to rebuild the entire tree
• Refitting: Adjust the bounding boxes of the object node and its parents [see e.g. Kopta et al, 2012]
• Over time: quality of the search tree decreases
• Full reconstruction can be amortized over multiple timesteps

$\mathrm{Refit}$(node, box):
while box not included in node:
bounding volume of node $\gets $ bounding volume of subchildren $\cup$ box
node $\gets$ parent of node

BVH Update

• After refitting, the tree structure may be inefficient
• Tree rotation: Locally rearrange the structure of the tree
• Also used to optimize static trees computed offline
• Can be applied in parallel to disjoint sub-trees

Parallel Construction with Linear BVH

• Parallel top-down construction has limited parallelism at the start of the tree
• Particularily ill-suited to GPU computations
• Linear BVH: Use a pre-determined order for all leave nodes [Karras, 2012; Jakob et al, 2021]
• Rely on this order to build all nodes in parallel

Morton Codes

Generating nodes in an LBVH

• There are $n$ leaves and $n - 1$ other nodes in a binary tree
• Each subtree corresponds to an interval
• The objects with a common prefix in their Morton code
• Node numbering: The node at index $i$ has a range that starts or ends at index $i$
• Binary search over Morton codes can be used to find the end-point of each interval
• Image from [Karras, 2012]

Generating nodes in an LBVH

if leaf $i-1$ shares a longer prefix with leaf $i$ than life $i+1$:
Range is from the last leaf where the highest-bit changed up to index $i$
else:
Range is from $i$ up to the next node where the highest-bit changed index
Find split index: Smallest index where one more bit changed (binary search)
Left child index: $\mathrm{split}$
Right child index: $\mathrm{split} + 1$

Hardware-accelerated BVH traversals

• Modern GPUs have instructions to help intersect rays with BVHs
• Different vendors or drivers generate trees of different quality and size (from zeux.io):
  • AMD Radeon 7900 GRE: 100 MB
  • AMD Radeon 9070: 84 MB
  • NVIDIA RTX 4090: 45 MB
  • NVIDIA RTX 5070: 33 MB

(Render of the bistro scene by NVIDIA)

Wide BVH

• Binary trees underutilize modern hardware resources
  • Modern CPUs can operate on 8 to 16 floating point number per instruction
• Wide BVHs store the bounding box of $k$ children (typically $k = 4$ or $k = 8$)
  • GPUs commonly have instructions for ray to BVH4 intersections
• Present new challenges:
  • Incomplete trees: some nodes won’t have 8 children
  • Construction: More degrees of freedom at each node
• Common construction pipeline: convert a binary BVH to a $k$-BVH by merging nodes

Quantized Precision

• 64-bit coordinates are extremely precise
• Unnecessary for most nodes of the tree
• Can simply use smaller number formats
  • Modern GPUs can directly use 8-bit floats or 8-bit integers
• Can also use the structure of floating point numbers to save space: \[x = \mathrm{sign} \times 2^{\mathrm{exp}} \times 0.1\mathrm{mantissa}_{b}\]
• Assume all coordinates will have the same exponent and only store the mantissa

Use of Oriented Bounding Boxes

• Store bounding boxes along with a rotation matrix
• More feasible thanks to hardware acceleration in recent GPUs
• $k$-DOP (Discrete Oriented Polytope) are also a popular way of creating tighter fits
  • A bounding box is a 3-DOP: Faces are parallel to the $\pm x$, $\pm y$, $\pm z$ planes
  • We can choose $k$ different directions to create pairs of planes