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

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)

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

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
• 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

Next Homework

• Improve Performance of a Rigidbody Simulation
  • Implement Spatial Data Structure of your choice to detect collisions
• Starting Source Code later this week