Acceleration Structures — BVH and Grids for Ray Tracing

In this tutorial, you'll learn about Acceleration Structures. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Acceleration structures are spatial data structures that reduce the number of ray-object intersection tests from O(N) to O(log N) by organizing primitives into hierarchies or grids that enable fast ray traversal.

What You'll Learn & Why It Matters

In this tutorial, you will learn the two main acceleration structures for Ray Tracing: Bounding Volume Hierarchies (BVH) and uniform grids. You will implement a BVH and measure the performance improvement over naive intersection testing.

Real-world use: Every production ray tracer and GPU Ray Tracing API (NVIDIA RTX, AMD HIP RT) uses BVHs internally. Without acceleration structures, rendering a scene with millions of triangles would be impossible.

Prerequisites

• Ray Tracing Basics (previous)
• Data structures knowledge
• Python with time measurement

Learning Path

flowchart LR
  A[Ray Tracing Basics] --> B[Acceleration Structures]
  B --> C[Path Tracing]
  B --> D[Voxel Rendering]
  B --> E[Real-Time GI]
  C --> F[BRDF and Materials]
  B:::current

  classDef current fill:#f90,color:#fff,stroke:#333,stroke-width:2px

Why Acceleration Matters

A naive ray tracer tests every ray against every primitive. With 100,000 triangles and 1,000,000 rays, that is 10^11 intersection tests. A BVH reduces this to about 10^6 tests — a 100,000x improvement.

import time
import numpy as np

def naive_intersection(ray, triangles):
    hits = []
    for tri in triangles:
        t = ray_triangle_intersect(ray, tri)
        if t is not None:
            hits.append((t, tri))
    if not hits:
        return None
    return min(hits, key=lambda x: x[0])

# Benchmark
triangles = [generate_random_triangle() for _ in range(10000)]
start = time.time()
hit = naive_intersection(test_ray, triangles)
elapsed = time.time() - start
print(f"Naive: {elapsed*1000:.2f}ms for {len(triangles)} triangles")

Bounding Volume Hierarchy (BVH)

A BVH is a Binary Tree where each node stores a bounding box (AABB) that encloses all primitives in its subtree. To intersect a ray with the BVH, you test the ray against nodes top-down: if it misses the node's AABB, you skip the entire subtree.

class AABB:
    def __init__(self, min_pos, max_pos):
        self.min_pos = np.array(min_pos)
        self.max_pos = np.array(max_pos)

    def intersect(self, ray):
        tmin = (self.min_pos - ray.origin) / ray.direction
        tmax = (self.max_pos - ray.origin) / ray.direction
        t1 = np.minimum(tmin, tmax)
        t2 = np.maximum(tmin, tmax)
        t_near = np.max(t1)
        t_far = np.min(t2)
        return t_near <= t_far and t_far > 0

class BVHNode:
    def __init__(self, triangles, depth=0):
        self.bbox = self.compute_bbox(triangles)
        self.left = None
        self.right = None
        self.triangles = []
        max_depth = 16
        if len(triangles) <= 4 or depth >= max_depth:
            self.triangles = triangles
            return
        axis = depth % 3
        sorted_tris = sorted(triangles, key=lambda t: t.centroid[axis])
        mid = len(sorted_tris) // 2
        if mid == 0:
            self.triangles = triangles
            return
        self.left = BVHNode(sorted_tris[:mid], depth + 1)
        self.right = BVHNode(sorted_tris[mid:], depth + 1)

BVH Traversal

def bvh_intersect(ray, node):
    if node is None:
        return None
    if not node.bbox.intersect(ray):
        return None
    if node.triangles:
        closest_t = float('inf')
        hit_tri = None
        for tri in node.triangles:
            t = ray_triangle_intersect(ray, tri)
            if t is not None and t < closest_t:
                closest_t = t
                hit_tri = tri
        return (closest_t, hit_tri) if hit_tri else None
    left_hit = bvh_intersect(ray, node.left)
    right_hit = bvh_intersect(ray, node.right)
    if left_hit and right_hit:
        return left_hit if left_hit[0] < right_hit[0] else right_hit
    return left_hit or right_hit

flowchart TD
  A[Root AABB] --> B{Intersects?}
  B -->|No| C[Skip subtree]
  B -->|Yes| D[Test Left Child]
  B -->|Yes| E[Test Right Child]
  D --> F{Leaf?}
  F -->|Yes| G[Test all triangles]
  F -->|No| D
  E --> H{Leaf?}
  H -->|Yes| I[Test all triangles]
  H -->|No| E

Performance Comparison

# Build and benchmark
bvh = BVHNode(triangles)
start = time.time()
hit = bvh_intersect(test_ray, bvh)
bvh_time = time.time() - start

print(f"BVH: {bvh_time*1000:.2f}ms, Speedup: {naive_time/bvh_time:.0f}x")

Expected output:

Naive: 15.30ms for 10000 triangles
BVH: 0.08ms, Speedup: 191x

Uniform Grid

An alternative to BVH is the uniform grid, which partitions space into equal-sized cells and stores a list of primitives per cell.

class UniformGrid:
    def __init__(self, triangles, grid_size=10):
        self.grid = {}
        self.cell_size = grid_size
        self.bbox = self.compute_scene_bbox(triangles)
        extent = self.bbox.max_pos - self.bbox.min_pos
        self.dims = np.ceil(extent / grid_size).astype(int)
        for tri in triangles:
            cell = self.get_cell(tri.centroid)
            key = tuple(cell)
            if key not in self.grid:
                self.grid[key] = []
            self.grid[key].append(tri)

    def intersect(self, ray):
        for cell_key in self.traverse_cells(ray):
            for tri in self.grid.get(cell_key, []):
                t = ray_triangle_intersect(ray, tri)
                if t is not None:
                    return t
        return None

SAH (Surface Area Heuristic)

The Surface Area Heuristic improves BVH quality by choosing split positions that minimize the expected cost of ray traversal:

Cost = C_trav + p_left * N_left * C_intersect + p_right * N_right * C_intersect

Where p_left is the probability of a ray hitting the left child, approximated by the ratio of the child's surface area to the parent's surface area.

Common Errors & Mistakes

1. BVH Depth Too Deep or Too Shallow

Mistake: Creating a BVH with millions of nodes (too deep) or only a few nodes (too shallow).

Fix: Use a leaf-size threshold (4-16 triangles) and a maximum depth limit (16-32). The optimal balance depends on the scene.

2. Poor Split Axis Selection

Mistake: Always splitting along the same axis, creating elongated, inefficient nodes.

Fix: Split along the axis with the largest extent (SAH-based splitting is even better).

3. AABB Intersection Precision Issues

Mistake: Rays grazing the AABB surface produce false negatives or positives.

Fix: Use robust slab method with proper handling of zero-direction components and add a small epsilon to AABB extents.

4. Duplicate Triangle References

Mistake: Including the same triangle in multiple BVH nodes, increasing traversal cost.

Fix: Assign each triangle to exactly one leaf node. Use splitting planes that partition triangles by centroid, not by bounding box overlap.

Practice Questions

Question 1

What is the time complexity of ray intersection with a BVH vs naive?

Question 2

Why does the Surface Area Heuristic improve BVH quality?

Question 3

When would a uniform grid outperform a BVH?

Question 4

What is an AABB and why is it used?

Challenge

Implement a BVH with SAH splitting and compare its performance against a simple median-split BVH on three different scenes: a uniform distribution, a clustered distribution, and a single large mesh. Report traversal times and node counts.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.