[Radiance-general] New occlusion testing optimization

[Greg Ward]

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!
-Greg

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!