On top of the framework I built for Assignment 03a - Sorting vs. Splitting, I've added a regular grid subdivision (RGS) option, as another acceleration technique to compare with the bounding volume hierarchy (BVH).

In most cases, RGS is a faster algorithm, in both speed of generation and rendering speed. However, there are cases where it is slower. These cases usually involve scenes with a mix of very large primitives and very small primitives. I believe what happens is that the number of grid spaces created isn't sufficient to put few enough objects into. So, there are a few primitives that span many grid cells, but most grid cells have many primitives in them, which leads to the poor performance.

I found an interesting thing when rendering the random sphere scenes. The resulting images were different between the RGS and BVH algorigthms. I originally thought this was a bug in my RGS create routine, but I later discovered that it was simply caused by concentric spheres that were being re-ordered by the BVS routine, but not by the RGS routine. This caused a different sphere to be hit for each set of concentric spheres between the two algorithms. I did nothing to fix this, as which sphere to pick is arbitrary. However, it should be noted that the random sphere pictures are not identical, but under careful inspection, it can be seen that the positions of the spheres are identical, their color is not.

I've made some charts comparing the performance characteristics of the two algorithms:

(click on each image for a larger view).

I noticed something interesting after making these charts. The performance of the RGS seems to degrade much better than that of the BVH. Notice the geometric look of the BVH curves, compared to the almost linear (especially in the sphereflake case) look of the RGS curves.

These tests show best case performance, since the data is actually in a grid structure to begin with, so there is exactly a single primitive in each grid cell. Hence, an increase in speed by an average of almost 6 times!

(click on each image for a larger view).

The row in red shows a case in which the RGS is not as fast as the BVH. Notice the mixture of large polygons and small polygons in the model for this scene. This causes the grid size to be too large, hence too many primitives are in each grid cell, causing the poor performance.

(click on each image for a larger view).

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)
  -rgs       <true/false>    generate regular grid subdivision (true)
  -bvh       <true/false>    generate bounding volume hierarchy (false)
  -sort      <true/false>    sort (not split) the surface list (false)
  -cull      <true/false>    cull backfacing triangles (false)