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


Assignment 03a - Sorting vs. Splitting

On top of the framework I built for Assignment 03 - Million Primitive Test, I've added a switch to enable either sorting of the surfaces array or splitting of the array (splitting means just grouping stuff on either side of a pivot value, but not caring whether the whole array is sorted).

Splitting is by far the faster of the two methods. Usually because the time cost to build the bounding volume hierarchy using the split instead of the sort is much faster (sometimes as much as 100x faster!). But, consistently, the split hierarchy is also rendered faster (on average, about 1.3x). Combining the built time and render time yields about a 1.6x improvement.

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


sort split
spheres create render total create render total times faster
1,000 0.0 2.9 2.9 0.0 2.6 2.6 1.1x
10,000 0.1 8.8 8.9 0.0 6.0 6.0 1.5x
100,000 2.2 18.6 20.8 0.6 15.1 15.7 1.3x
1,000,00039.1 55.4 94.5 9.7 35.8 45.5 2.1x

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

Sort images are on top, split images on bottom (they are identical - which is a good thing).



sort split
spheres create render total create render total times faster
5x5x5 = 125 0.0 4.5 4.5 0.0 4.1 4.1 1.1x
25x25x25 = 15,625 0.4 33.9 34.3 0.1 28.5 28.6 1.2x
50x50x50 = 125,000 17.1 1:10.5 1:27.6 0.7 58.5 59.2 1.5x
100x100x100 = 1,000,00014:58.9 4:30.9 19:29.8 8.4** 3:17.7 3:26.1 5.5x

** In the million sphere case, the create time for the split is 8.4 seconds compared to nearly 15 minutes in the sort case! This is a huge win - more than 100 times faster! Another good result can be seen in the 125,000 sphere case where it is almost 25 times faster.


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

Sort images are on top, split images on bottom (they are identical - which is a good thing).



sort split
triangles create render total create render total times faster
7124 0.1 7.9 8.0 0.0 5.6 5.6 1.4x
3516 0.0 12.2 12.2 0.0 11.1 11.1 1.1x
6320 0.1 7.4 7.5 0.0 5.3 5.3 1.4x
3360 0.0 6.7 6.7 0.0 4.1 4.1 1.6x

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

Sort images are on top, split images on bottom (they are identical - which is a good thing).



sort split
spheres create render total create render total times faster
10 0.0 1.5 1.5 0.0 1.5 1.5 1.0x
91 0.0 5.0 5.0 0.0 4.4 4.4 1.1x
820 0.0 13.1 13.1 0.0 8.9 8.9 1.5x
7381 0.1 24.4 24.5 0.0 15.9 15.9 1.5x

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

Sort images are on top, split images on bottom (they are identical - which is a good thing).



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

 required:

             <scene_file>    file containing scene description

 options:

  -o         <output_file>   output image filename (output.tga)
  -w         <width>         width of output image (256)
  -h         <height>        height of output image (256)
  -shadows   <true/false>    generate shadow rays (true)
  -bvh       <true/false>    generate bounding volume hierarchy (true)
  -cull      <true/false>    cull backfacing triangles (false)
  -sort      <true/false>    sort (not split) the surface list (false)

Questions/comments to nate@pobox.com.


February 2002
© Nate Robins