The method we use in
*Radiance*
for reducing the number of shadow rays is described in [26].
A prioritized list of potential source contributions is
created at each evaluation of Equation (1).
The largest potential contributors (contribution being a function of
source output, proximity and BRDF) are tested for shadows
first, and we stop testing when the remainder of the source list is below
some fraction of the unoccluded contributions.
The remaining source contributions are
then added based on statistical estimates of how likely
each of them is to be visible.

Figure 4 shows a simple example of how this works. The left column represents our sorted list of potential light source contributions for a specific sample point. We proceed down our list, checking the visibility of each source by tracing shadow rays, and summing together the unobstructed contributions. After each test, we check to see if the remainder of our potential contributions has fallen below some specified fraction of our accumulated total. If we set our accuracy goal to 10%, we can stop testing after four light sources because the remainder of the list is less than 10% of our known direct value. We could either add all of the remainder in or throw it away and our value would still be within 10% of the correct answer. But we can do better than that; we can make an educated guess at the visibility of the remaining sources using statistics. Taking the history of obstructed versus unobstructed shadow rays from previous tests of each light source, we multiply this probability of hitting an untested source by the ratio of successful shadow tests at this point over all successful shadow tests (2/(.9+.55+.65+.95) == 0.65 in this example), and arrive at a reasonable estimate of the remainder. (If any computed multiplier is greater than 1, 1 is used instead.) Our total estimate of the direct contribution at this point is then the sum of the tested light sources and our statistical estimate of the remainder, or 1616 in this example.

We have found this method to be very successful in reducing
the number of shadow test rays required, and it is possible
to place absolute bounds on the error of the approximation.
Most importantly, this type of adaptive shadow testing emphasizes
contrast as the primary decision criterion.
Contrast is defined as the difference between the luminance
at a point and the background luminance
divided by the background luminance.
If a shadow boundary is below the visible contrast threshold,
then an error in its calculation is undetectable by the viewer.
Thus, this method produces no
*visible*
artifacts in its tradeoff of speed for accuracy.
Accuracy is still lost in a controlled way, but the resulting image
is subjectively flawless,
due to the eye's relative insensitivity to absolute light levels.

Figure 5 shows a theater lighting simulation
generated by *Radiance* in 1989.
This image contains slightly over a hundred light sources,
and originally took about 4 days to render on a Sun-4/260.
(The equivalent of about 5 Vax-11/780's.)
Using our adaptive shadow testing algorithm reduced the rendering
time to 2 days for the same image.
The time savings for scenes with more light sources can be better than 70%,
especially if the light sources have narrow
output distributions, such as the spotlights popular in overlighted
retail applications.

A different problem associated with ray-per-source shadow testing is
*inadequate sampling*
of large or nearby sources, which threatens simulation accuracy.
For example, a single ray cannot adequately sample a
fluorescent desk lamp for a point directly beneath it.
The simplest approach for sources that are large relative to their
distance is to send multiple sample rays.
Unfortunately, breaking a source into pieces and sending
many rays to it is inefficient for distant points in the room.
Again, an adaptive sampling technique is the most practical
solution.

In our adaptive technique, we send multiple rays to a light source if its extent is large relative to its distance. We recursively divide such sources into smaller pieces until each piece satisfies some size/distance criterion. Figure 6a shows a long, skinny light source that has been broken into halves repeatedly until each source is small enough to keep penumbra and solid angle errors in check. Figure 6b shows a similar subdivision of a large rectangular source. A point far away from either source will not result in subdivision, sending only a single ray to some (randomly) chosen location on the source to determine visibility.