CS184 Section 11
Ray Tracing Acceleration
Brandon Wang
November 7, 2012
Material adapted from FuChung Huang and Carlo Sequin.
Brandon Wang
November 7, 2012
Material adapted from FuChung Huang and Carlo Sequin.
I feel the most straightforward to implement is a type of spatial hierarchy, the AABB (axisaligned bounding box) tree. It is very similar to the kd (kdimensional) tree, but with less constraints.
This is what I'll go over and recommend that you do in your homework.
(Disclaimer: For HW you can actually do anything you want, but you need some sort of acceleration structure.)
Idea: Build an axisaligned box around each primitive (triangle). (Or here, butterfly.)
How many points are needed to represent the box?
It is straightforward to find the bounding box of two bounding boxes
(Can you see where this is going?)
Idea: Make one BIG bounding box for your entire scene, and then keep splitting each box in half to be more precise.
(Or, the other direction, make a bounding box for each primitive, and then make one bounding box for each close pair, then keep making one box for each pair of each level)
O(logn) depth of tree!
First intersect with the largest bounding box, then find which of the subdivisions you intersect with, and recurse into that bounding box only, until you hit your primitives (triangles).
Recursively split your primitives in half by your axis at each division
(Easy way: sort by axis, then split array/vector in half)
Alternate between axis for each level
Is there one line that splits these two triangles?
(No, they overlap).
Just divide up the box into two overlapping bounding boxes.
(This is the big difference between this and a kD tree. Can you see why kD trees are preferred?)
Some results when I tried it... (This has reflection/shadows)
AABB  Thousand Spheres (1rpp, 4mrd)

AABB  Thousand Spheres (32rpp, 4mrd)

A good reference is James O'Brien's Fall 2009 slides
Natural extensions of ray tracing. (I feel easier than HW3 shader stuff.) Some good ideas:
Start thinking about final project. Many people usually do a OpenGL interactive scene, or extend the ray tracer project
Fancier extensions of HW5 include (and are definitely not limited to):