CS184 Section 10
Ray Tracing Acceleration

Brandon Wang
April 3, 2012
Material adapted from Fu-Chung Huang and Carlo Sequin.

Logistics

Today

Acceleration Structures

Acceleration Structures

Which is best? I have no idea. (Depends on the scene.)

Octrees

Octree Demo

Spatial Hierarchies

I feel the most straightforward to implement is a type of spatial hierarchy, the AABB (axis-aligned bounding box) tree. It is very similar to the k-d (k-dimensional) 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.)

Bounding Boxes

Idea: Build an axis-aligned box around each primitive (triangle). (Or here, butterfly.)

Axis-aligned?

How many points are needed to represent the box?

Transformations

Box Intersection

Box Hierarchy

It is straightforward to find the bounding box of two bounding boxes

(Can you see where this is going?)

Binary Tree of Boxes

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)

Binary Tree of Boxes

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).

So far, k-D trees

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

A Little Simplified: AABB Trees

Is there one line that splits these two triangles?

(No, they overlap).

AABB Trees

Just divide up the box into two overlapping bounding boxes.

(This is the big difference between this and a k-D tree. Can you see why k-D trees are preferred?)

How much faster does this go?

Some results when I tried it... (This has reflection/shadows)

AABB - Thousand Spheres (1rpp, 4mrd)

Acceleration Time Ratio
No Acceleration14s1x
Max Depth 025s0.56x
Max Depth 113s1.07x
Max Depth 27s2x
Max Depth 44s3.5x
Max Depth 8*1s14x
Max Depth 16*1s14x

AABB - Thousand Spheres (32rpp, 4mrd)

Acceleration Time Ratio
No Acceleration361s1x
Max Depth 0636s0.57x
Max Depth 1348s1.04x
Max Depth 2188s1.92x
Max Depth 4113s3.19x
Max Depth 8*39s9.26x
Max Depth 16*39s9.26x

References

A good reference is James O'Brien's Fall 2009 slides

Midterm Q4

Consider a uniform quadratic B-Spline curve with control points at (-2,0), (0,2), (2,0) in that order.

a) What are the end-points of the curve?

b) What is the mid-point?

c) What are the control points for a Bezier curve that generates the same curve as the B-Spline above (this follows directly from the above)? Verify that the mid-point of the resulting Bezier curve matches the midpoint for the B-Spline 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 B-spline control points for the left and right halves of the uniform B-spline curve? (i.e., what B-spline control points would match left and right halves from (d))?

HW5 EC

Natural extensions of ray tracing. (I feel easier than HW3 shader stuff.) Some good ideas:

HW6

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):