CS 6620 Project 3: BVH Ray Tracer

Jan 27, 2002

Add bounding volume hierarchy to my ray tracer. AAboxes are used to bound spheres. When creating the bounding volume hierarchy tree, STL's sort is used to sort the list of objects. When creating a node in level i, the objects are first sorted according to the i%3 component of its center.

To test the efficiency of bounding volume hierarchy, the raytracer is run on random spheres scene. The result is listed below. All the images are of 500X500 pixels. Click it to get the normal size. Here is the detailed output of unix time command.

g++ compiler On SGI workstation IRIX 6.5, 270MHz CPU, 256M main memory + 32K DataCache + 32K InsCache

10 spheres	100 spheres	1000 spheres	10,000 spheres	100,000 spheres	1,000,000 spheres
2.109 seconds	4.705 seconds	10.827 seconds	26.586 seconds	72.451 seconds	409s (dynamic array and STL's sort)... 379s (static array and qsort).

From the above experiments, it turns out that BVH is a quite efficient strategy for these random and approxiately uniform size spheres.

The efficiency is due to the fact that the generated BVH tree effectively approximates a binary subdivision of the 3-D scene space. This can be best demonstrated by rendering only those spheres in left subtree of level 3, of level 6(i.e. 2*3), of level 9(3*3), and so on.

As can be seen from the following images, these subtrees approximate the lower-left-front parts of a recursive binary space subdivision with a quite satisfatory result.

All the images are sub-scenes of 100,000 spheres, with 500X500 pixels. Click it to get the normal size.

And again here is the detailed output of unix time command. (shadow effect for the whole scene, instead of only the rendered subspace)

leftest subtree: level 3	leftest subtree: level 6	leftest subtree: level 9	leftest subtree: level 12	leftest subtree: level 15