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
(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.
Timings (MM:SS.S) are for 500x500 pixel images on a PentiumIII 733Mhz with 384MB SDRAM
(unless otherwise noted).