Graphics Reference
In-Depth Information
2.3.5 Sampling Techniques
The final results of Monte Carlo simulations is highly dependent on how the sam-
ples are chosen. A good sampling scheme uses a small number of samples, pro-
duces little noise, and results in less error. Purely random sampling is unbiased,
but inefficient. Although there may not be an “ideal” sampling method, a number
of good sampling schemes have been proposed.
Random samples are rarely evenly distributed; they often end up close to each
other in a phenomenon known as
clustering
. The effect on Monte Carlo sampling
is that values near clustered points are overemphasized in the average. For exam-
ple, if it is probabilistically expected that only one ray on the hemisphere above a
surface point will hit the light source, but three rays end up hitting it, that surface
point will get too much light. Although clustering is not unavoidable, it can be
mitigated by dividing the domain into small regions and then sampling in these
regions separately. This is known as
stratified sampling
. Figure 2.7 illustrates
unstratified and stratified sampling, with three different ways of dividing up the
domain.
Clustering is made worse by another practical problem with Monte Carlo
sampling: truly random numbers are not easy to generate, especially at the rates
needed for rendering.
4
Implementations normally depend on
pseudorandom se-
quences
, which typically exhibit worse clustering than truly random numbers and
the lack of randomness can bias sampling in other ways. Alexander Keller be-
gan advocating the use of
quasi-Monte Carlo
(QMC) sampling for rendering in
the mid-1990s [Keller 96]. QMC sampling constructs sample points from a fixed
sequence, known as a
low discrepancy sequence
, rather than from a pseudoran-
dom sequence. A low discrepancy sequence avoids clustering by construction, as
the bottom row of Figure 2.7 illustrates. A variety of such sequences are known,
although some are difficult to compute.
As noted above, some light paths carry more power than others, but finding
those more “important” paths is not easy. General Monte Carlo integration can be
made more efficient by concentrating samples where the function being integrated
is largest, a technique known as
importance sampling
. Something similar can be
done with Monte Carlo ray tracing. Instead of firing rays distributed uniformly
on the hemisphere, they can be concentrated in areas of the hemisphere in which
the incoming radiance (times the BRDF value) is largest. The trick, of course, is
to determine what those areas are, and the only way to do that is to actually sample
4
Hardware random number generators are currently available that produce values based on theo-
retically unpredictable physical processes, but they only give a few hundred numbers per second. A
MCRT algorithm may need millions per second.
