CS184 Section 10
Ray Tracing Acceleration
Brandon Wang
April 3, 2012
Material adapted from FuChung Huang and Carlo Sequin.
Brandon Wang
April 3, 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
Consider a uniform quadratic BSpline curve with control points at (2,0), (0,2), (2,0) in that order.
a) What are the endpoints of the curve?
b) What is the midpoint?
c) What are the control points for a Bezier curve that generates the same curve as the BSpline above (this follows directly from the above)? Verify that the midpoint of the resulting Bezier curve matches the midpoint for the BSpline curve in (b).
d) What are the control points for the left and right halves of the Bezier curve (per the deCasteljau subdivision scheme)?
e) What are the corresponding Bspline control points for the left and right halves of the uniform Bspline curve? (i.e., what Bspline control points would match left and right halves from (d))?
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):