New occlusion testing optimization

I just checked in a new optimization for light source testing that seems to speed renderings up by about a factor of 2, depending on the number and arrangement of light sources in the scene. There is no command-line option associated with the algorithm, as it is strictly a time vs. memory trade-off, and a pretty good one at that. Using the default cache resolution of 20x20, the memory cost is a little over 4 Kbytes per light source, so a scene with 100 sources will take an additional 400 Kbytes of memory during rendering. This seems like a small price for a doubling in rendering speed, so I decided not to make it a runtime option. (You can add a -DSHADCACHE=0 compile option if you really want to switch it off, or use -DSHADCACHE=40 if you want to use 4 times as much memory for even faster renderings.)

The way it works is simple: with each light source, we associate an array of SHADCACHExSHADCACHE OBJECT indices listing occluders in each direction as seen from the source. Each time we're about to test for shadows, we first check against the cached occluder. Since it doesn't matter where in the path a surface occludes the source, we don't really have to trace a ray to find the first blocker -- any blocker will do. If the cached occluder does not block the point being tested, but another blocker is found for this point, then the new blocker replaces the previous one in the cache. This tends to save the largest occluders over time, since they'll have better cache longevity.

This is actually a very old and widely used technique for reducing shadow tests, but the way it is implemented in most ray tracers is to store just one blocker per source -- the most recent. This of course doesn't work if your test points are randomly distributed in your scene, as they are during most Radiance renderings by the indirect (ambient) calculation. My earlier test of this simpler approach many years ago showed no improvements in rendering time. So, the innovation here use an array of recent occluders per source, which works for any sample ordering provided the shadows in the scene are not caused entirely by teeny obstructions. (Shadows cast by the leaves of a tree will not be sped up much by this technique.)

The way I implemented it in Radiance, it tends to improve the accuracy of the -dt and -dc settings, even when it does not substantially reduce the rendering time. Also, it allows you to specify -dt 0 without incurring nearly as great a cost as it used to for those who need the utmost in accuracy. Since the occlusion cache does not introduce any errors (at least none that I've seen), you can get 100% reliable source tests at a fraction of the expected cost.

I'm hoping that some of you will download tomorrow's HEAD release and give it a try. I have only experimented with it extensively on one (rather complicated) scene, so I'm curious what effect it has on others.

Happy New Year everyone!

P.S. Rob's latest post makes it sound like he's taking after me -- forgetting what he's said as well as what he knows!