BVH Acceleration

Naive ray-mesh: test each triangle. O(N). For 1M triangles + 1M rays = trillion tests. Hours per frame.

BVH (Bounding Volume Hierarchy): tree of bounding boxes.

                  [Box around all geometry]
                  /                          \
        [Box around half]            [Box around other half]
        /          \                 /          \
    [...]        [...]            [...]        [...]
                                                  \
                                              [single triangle]

Ray vs box: cheap (slab method). Ray vs triangle: more expensive.

Algorithm:

1. Test ray vs root box.
2. If miss: no intersections.
3. If hit: recurse into both children.
4. At leaves: test ray vs triangles.

Complexity: O(log N) average. For 1M triangles, ~20 box tests + a few triangle tests per ray.

Construction:

Better split: SAH (Surface Area Heuristic):

• For each candidate split, estimate cost.
• Cost = SA(left) * count(left) + SA(right) * count(right).
• Pick split with min cost.
• Slower to build but faster queries.

BVH traversal:

Optimization: traverse closer child first; if hit found, can prune farther child if its bbox is beyond.

Modern BVH:

• Embree (Intel): production CPU ray tracing. SIMD optimized.
• OptiX / DXR / Vulkan ray tracing: hardware-accelerated on GPU.
• RTX cards have BVH traversal in hardware.

Other accelerators:

• KD-tree: spatial subdivision. Slower to build, better cache performance.
• Grid: regular cells. Easy. Bad for non-uniform geometry.
• Voxel octree: 3D BSP. Good for very dense scenes.

BVH dominates modern path tracing.