CS6620 - Assigment 03

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).



(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



(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



(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



(click on each image for a larger view).

My color cube scene.

spheres	with BVH	BVH create	total time
5x5x5 (125)	5.9	0.0	5.9
25x25x25 (15,625)	45.6	0.4	50.0
50x50x50 (125,000)	1:31.6	16.9	1:48.5
100x100x100 (1,000,000)	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).



(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]

  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.

  @reponse:
    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.