Assignment #3 - BVH

This assignment is also going to have multiple parts.  In the first part, we were supposed to get a sphere flake working in order to motivate an acceleration data structure.  In this second portion, we had to build a hierarchy of axis-aligned bounding boxes, and to traverse the tree, tracing the bounding boxes themselves.

So I thought the first part of this was creating a finite plane abstraction, I called it Rectangle.  Here is my first bounded rectangle:

Then I created a Box abstraction that just compiled 6 Rectangles, here it is:

Then I added code to build a hierarchy of axis aligned bounding boxes recursively.  When I get to the leaves of the recursion, either because I hit the requested recursion depth, or else because the boxes are getting smaller than a small fixed tolerance along the axis of division, I created an actual Box to fill the bounding box.  Actually, in order to see the boxes at all, I had to shrink the bounding boxes a little when making the visible boxes at the leaf level.

I also added code to traverse the tree, only attempting to hit actual GeometricObjects when I hit the leaves of tree, or otherwise didn't get any further hits from recursion.

Below is a screenshot with 1 level of recursion:


Number of tree nodes: 3, number of geometric objects: 2
Raytraced image in 322019 microseconds

2 levels of recursion:


Number of tree nodes: 7, number of geometric objects: 4
Raytraced image in 394739 microseconds

3 levels:


Number of tree nodes: 15, number of geometric objects: 8
Raytraced image in 465404 microseconds

4 levels:


Number of tree nodes: 31, number of geometric objects: 16
Raytraced image in 552563 microseconds

5 levels:


Number of tree nodes: 63, number of geometric objects: 32
Raytraced image in 677675 microseconds

Now we're up to 10 levels of recursion:


Number of tree nodes: 2047, number of geometric objects: 1024
Raytraced image in 2180543 microseconds

Up to 12 levels of recursion:


Number of tree nodes: 8191, number of geometric objects: 4096
Raytraced image in 3421047 microseconds

13 levels:


Number of tree nodes: 16383, number of geometric objects: 8192
Raytraced image in 5524829 microseconds

So this is already looking pretty good.  In my sphereflake blog post, I was only tracing 937 spheres in over 33 seconds without an acceleration data structure.  Boxes are much more work to hit than spheres because of their 6 bounded planes to check, and now I'm tracing over 8,000 Boxes in under 6 seconds!

To check out this assignment, just do an "svn update" if you've checked out my repository before.

This program is in the cs513/assignment03_spike_02/ directory, and to get different levels of recursion, run it like this:

./assignment03 -bvhLevel 7