G6: Spatial Acceleration Flashcards
Why is naïve ray casting expensive?
Because it loops over all aspects of the scene for each ray.
What can we do to accelerate the ray casting algorithm?
Call fewer intersection tests
Make intersection tests more efficient
What are the two key ideas for acceleration?
Hierarchical partitioning
Bounding complex objects with simpler primitives
What is the goal of spatial acceleration structures?
To reduce computation using hierarchical and/or bounding strategies.
Name some types of spatial acceleration structures.
Uniform grids
Bounding volumes
Bounding Volume Hierarchies (BVH)
k-d trees (quadtree, octree)
Binary Space Partitioning (BSP)
What’s the difference between object partitioning and space partitioning?
Object partitioning: Divides objects into groups
Space partitioning: Divides the space the objects occupy (adaptive or uniform)
How does a uniform grid help with ray tracing?
It lets the ray step through grid cells and only check objects in the cells it traverses.
What is a bounding volume?
A simple shape enclosing a complex object, used to cheaply test for potential intersection.
When is bounding volume testing worthwhile?
The shape is simple
The object inside is complex
The bounding shape is a good fit (“tightness vs complexity”)
Compare types of bounding volumes.
Sphere: Easy to intersect, but usually not tight
AABB: Axis-aligned, tighter and easy to intersect
OBB: Oriented box, tighter for arbitrary shapes but requires transforming
How does the AABB ray intersection test work?
Parameterize ray by distance t
Compute t intervals for each axis
Check if the intersection of all intervals is non-empty
What is a Bounding Volume Hierarchy (BVH)?
A tree where each node contains a bounding volume for a subset of objects in the scene.
How do you construct a BVH?
Recursively split object sets
Create bounding boxes for subsets
Stop when few primitives remain in a box
What are BVH partitioning strategies?
Center partition: Split at center along an axis
Median partition: Split based on median object count
Surface Area Heuristic (SAH): Minimize expected ray traversal cost
What theorem does SAH rely on?
Probability a ray intersects box B inside A = SA(B)/SA(A)
How does k-d tree construction differ from BVH?
k-d tree partitions space, not objects
It’s adaptive (irregular) vs. BVH’s object-based bounding
Describe k-d tree ray tracing traversal.
Traverse ray through the split space
Visit the closest intersected cell first
Stop on first intersection
Trade-offs: Object partitioning vs Spatial partitioning
Object (BVH): Easier updates, simpler tree
Space (k-d tree): Better hit accuracy, but may test same object multiple times
Trade-offs: Adaptive vs Non-Adaptive structures
Adaptive: Better for complex distributions, costly to build
Non-Adaptive: Fast to build, works best for uniform scenes
What are other uses of spatial acceleration beyond ray tracing?
Collision detection
View Frustum Culling for rasterization
Path and motion planning
