Tuesday, March 24, 2009

Assignment #5

Assignment #5: Acceleration Data Structures

This assignment adds the Octree primitive for improved performance. The ability to load OBJ files has also been added.

Get the code here

How to get and build the code:

wget http://cs.unm.edu/~jbowles/cs413/a5/jbowles-assign5.tar.bz2
tar jxf jbowles-assign5.tar.bz2
cd jbowles-assign5
./raytracer --width=512 --height=512 --reflections --shadows --maxdepth=20

For testing, I used a type of "Sphere Flake" built with approximately 2 million spheres. The octree dramatically sped up the rendering process.

Total number of spheres: 2,015,539
Without Octree With Octree Change
Time to build sphere flake (s) 1.5 1.5 0
Time to build Octree (s) N/A 34.5 N/A
Time to render (s) 76883 42 76841
Total time (s) 76885 78 76807 or 97.3%
Intersection Tests 629019024 588972081 4004693
Failed Intersection Tests 608663340 527464523 81198817
Percent successful intersection tests 3.2% 10.4% 7.2%

Using the octree results a 97.3% speed increase. Very nice. However, I'm surprised by the number of intersection tests that still have to be performed. This makes me wonder if I'm counting those correctly.

Here are the images generated with the two different methods. The octree looks slightly different - notice the darker patches and the small chunks missing on the outside of the sphere flake. This seems to indicate that some of the spheres didn't make it into the octree voxels.

Image of scene without octree:
Scene with octree:


  1. All of the spheres are making it into octree voxels. That is not why some are missing from the octree version. I'll have to keep looking.

  2. I'm using a smaller sphere flake to do my testing, and I've found that 'boxes' are missing. Is this a problem while intersecting the octree or while building the octree?

  3. I found one of my errors - an improper for loop that looped over each of the child nodes in the octree. I wasn't hitting one of the nodes.

    There's still problems, tho.