Octree

Since I will probably need to create or adapt an existing acceleration structure for ray tracing, I thought it was a good idea to implement a new acceleration structure to familiarize myself with the avaible methods and interfaces.

PBRT already comes with a Bounding Volume Hierarchy, Uniform Grid and kD-acceleration structure, so I decided to add an Octree to the list.

An octree subdivides the scene into eight equal sized voxels and each non-empty voxel is again recursively subdivided into eight voxels. Speedups are gained when a ray misses a voxel, since all of the children of that voxel no longer need to be checked.

Furthermore, an octree does not suffer from the "teapot in the stadium" problem, since it adapts to irregular placed geometry by only subdividing non-empty voxels.

The false-colour image below shows the number of intersection tests (including voxel intersections) for the stanford bunny scéne.

Stanford Bunny Scéne
(displaying the correctness of the octree implementation)

False color image when using the Octree. 
The maximum number of intersections is 2324 (red).
The total number of intersections is 102,265,467 

Next we compare the rendering times against the other acceleration structures:

	BVH with SAH	Uniform Grid	kD-tree with SAH	Octree
Stanford Bunny	2.9s	5.3s	3.1s	5.3s
Utah Teapot	27.7s	34.2s	31.6s	36.2s
Killeroo Scene	160.1s	415.7s	233.7s	669.5s

These results show that my implementation of the octree accelerates ray tracing, but still needs some tuning. I guess "make it work, make it right, make it fast" is the key here. The implementation already works and the "aggegratetest" tests assures that it is also right. Now I still need to make it fast.