Acceleration Structures and Grids
Interested of ways that have fewer number of rays per intersection
Acceleration structures:
- uniform spatial subdivision (grids)
- Bounding Volume Hierarchies (BVH)
- Binary Space Partitioning (BSP Trees)
- Axis-aligned often for ray tracing: kd-trees
- conceptually simple, implementation bit tricky
Acceleration and Regular Grids
- simplest acceleration for example 5x5x5 grid
- for each grid cell, store overlapping triangles
- March ray along grid, test each triangle in grid cell
- More sophisticated: kd-tree, oct-tree, bsp-tree
- Or use (hierarchical) bounding boxes
Bounding Volume Hierarchies
Bounding Box Test
- ray-intersection simple coordinate check
- hierarchical bounding boxes
Hierarchical Bounding Box Test
- if ray hits root box
- intersect left subtree
- intersect right subtree
- merge intersections (find closest one)
- standard hierarchical traversal
- at leaf nodes, must intersect objects
Binary Space Partitioning (BSP) Trees
- divide space rather than objects
- in BVH each object is in one of two sibling nodes
- in spatial subdivision, each space point in one node
- but object may lie in multiple spatial nodes
BSP trees
- axis aligned splits sometimes called kd-trees
- split space (binary space partition) along planes
- fast queries and back to front traversal
- construction is conceptually simple
- select a plane as root of a sub tree
- split into two children along this root
- random polygon for splitting plane
- continue splitting until leaf nodes
- visibility traversal in order
- child one
- root
- child two
- child one chose based on viewpoint
- BSP tree built once, used for all viewpoints