CS6620 Advanced Graphics 2 University of Utah
Prof: Peter Shirley Ray Tracing Sem: Spring 2002

Assignment 03 - Million Primitive Test

On top of the framework I built for Assignment 02 - Basic Ray Tracer 2, I've added a bounding volume hierarchy.

The bounding volume hierarchy is a tree of bounding boxes. It is built by bounding the list of surfaces in the scene, then halving the list and recursively bounding each half. Before the list is halved, it is sorted along each of the major axes in turn.

Timings (MM:SS.S) are for 500x500 pixel images on a PentiumIII 733Mhz with 384MB SDRAM
(unless otherwise noted).

sphereflake-1 sphereflake-2
sphereflake-3 sphereflake-4
(click on each image for a larger view).

Four images of a sphereflake at four different stages of "bloom".

spheres w/o BVH with BVH BVH create
10 0.9 1.9 0.0
91 5.6 6.9 0.0
820 51.5 18.3 0.0
7381 15:12.8 34.4 0.1
bar chart

dolphins-1 dolphins-2
dolphins-3 dolphins-4
(click on each image for a larger view).

A scene with dolphins from four different views (1692 triangles, 2 lights).

triangles w/o BVH with BVH BVH create
845 52.4 3.7 0.0
830 1:12.8 8.5 0.0
946 1:16.4 11.1 0.0
891 1:04.9 6.0 0.0
bar chart

al soccerball
rose+vase teapot
(click on each image for a larger view).

A few different scenes.

scene triangles lights with BVH
al 4105 2 8.7
soccerball 1755 2 15.2
rose+vase 1562 4 5.4
teapot 3136 2 11.9

5x5x5 25x25x25
50x50x50 100x100x100
(click on each image for a larger view).

My color cube scene.

spheres with BVH BVH create total time
5.9 0.0 5.9
45.6 0.4 50.0
1:31.6 16.9 1:48.5
5:07.1 15:03.3 20:10.4

The 100x100x100 scene took by far the longest to create the bounding volume hierarchy (15 minutes!). Perhaps this generates the degenerate case (sorted backward) for qsort, because of the regularity of the spheres? Or, perhaps each bounding volume can contain the maximum amount of spheres, again, because of the regularity? It is interesting to compare this result with that below of the million random spheres (which is more than 20 times faster).

random-1000 random-10000
random-100000 random-1000000
(click on each image for a larger view).

Four different random sphere scenes.

spheres with BVH BVH create total time
1,000 3.8 0.0 3.8
10,000 11.5 0.1 11.6
100,000 23.0 2.1 25.1
1,000,000 1:09.2 38.7 1:47.9

Something interesting to note about these images is that you can see some patterns emerging (especially in the upper right corner of the images with many spheres). I believe that this shows the distribution properties of the random function used to generate the spheres. In these images, the rand() function from the C library that comes with Microsoft Visual C++ was used. It looks like it has a pretty poor distribution.

All of the images above can be regenerated by specifying the appropriate scene file on the command line of the rayn program rayn-03.zip (976 Kb). The source code is included in the zip file. Here is a description of the command line parameters for rayn.
rayn [@response] [options]

    -scene      <scene_file>       file containing scene description (string).
    -output     <output_file>      output image filename (string).
    -size       <width,height>     size of output image (int,int).
    -noshadows                     don't generate shadow rays.
    -nobvh                         don't generate a bounding volume hierarchy.

    Specifies a file from which options are to be read,
    one option per line.  Options which are specified on
    the command line override those in the response file.

Questions/comments to nate@pobox.com.

January 2002
© Nate Robins