28x faster renders

I finally got a simple BVH implemented. To get a quick idea of what a BVH is, check out the Bounding Volume Hierarchy page on Wikipedia. My tree generation algorithm is pretty simple:

• if the number of remaining shapes is less than or equal to the target group size
• add the shapes to this node's list
• create a bounding box for the group
• otherwise
• find the bounding box that contains the remaining shapes
• figure out on which axis (x, y, or z) the bounding box is longest
• sort the shapes on the longest axis
• split the list at the median
• create a left node containing the first half of the list
• create a right node containing the second half of the list

It's nothing fancy, and I haven't tried to find an optimal group size yet, but it works. And, like the title of this post implies, for certain scenes the render times are almost 28 times as fast. Not too shabby.

Tree traversal is pretty simple, too....
I send a ray into the BVH and it figures out which bounding boxes it hits. If there's an intersection, it checks that node's children. It continues the process down the structure until it gets to the shape level. Once it gets down to the shapes, it performs full intersection tests on each shape in the group. One of the simple speedups I implemented was to not check the contents of a bounding box if a closer intersection with an actual shape was already found. Another one I plan on doing is to always pick the closer bounding box when given a choice between two.
Some quick tests reveal the following:

	No acceleration	BVH
BVH build time (seconds)	n/a	0.001
Render time (seconds)	18.237	16.715
Ray-box intersection tests	n/a	1,697,131
Ray-primitive intersection tests	3,013,940	948,342
Ray-primitive intersections	314,963	314,718

	No acceleration	BVH
BVH build time (seconds)	n/a	0.959
Render time (seconds)	4,385.083	157.843
Ray-box intersection tests	n/a	51,738,892
Ray-primitive intersection tests	1,031,241,456	5,256,829
Ray-primitive intersections	1,473,005	1,003,264

As you can see, there's a very little performance improvement on the smaller scene that only had three spheres, a plane, and two lights. It was hardly worth the effort. The real speedup begins shows itself with the more complicated scene. The render time went from 73 minutes down to 2.6 minutes. That's nearly 28 times as fast. That's pretty incredible considering I haven't even implemented all of my optimizations yet.

Now that the semester's over, I've turned this project in, and I've had a chance to think about all of it, I'm going to take a little break. Then I'll dive back in, fix a few things that have been bugging me, and jump into phase 1.5.

But first, one final render to show off. The model has over 5,100 triangles and rendered in something like 20 minutes.