Graphics Reference
In-Depth Information
analysis of the program used to generate the paths: How likely are we to have gen-
erated the two spliced-together subpaths? How likely are we to have spliced the
paths together along this particular edge? These probabilities depend on the sam-
pling approach. For instance, to generate a path, we might do one of the following.
• Repeatedly cast a ray in a uniform random direction (i.e., the probability
that the direction lies in some solid angle is proportional to the measure of
that solid angle) in the outgoing hemisphere from the current path point.
• Repeatedly cast a ray uniformly with respect to the
projected
solid angle.
• Repeatedly choose a point (toward which we'll cast a ray) at random with
respect to the area on the union of all surfaces in the scene.
Each of these will sample some paths more often than others; switching from one
to another is similar to changing variables in an ordinary integration problem:
An extra factor is introduced in the integrand. And while the geometry term for
the “choosing surface points” version has a
r
2
factor, which leads to very large
values when two chosen points are close to each other (see Figure 31.27), in the
“choosing directions” version this change of variables exactly cancels out the bad
factor in the geometry term,
except
for the factor associated with the edge joining
the light path to the eye path.
Figure 31.27: If this light path
is chosen by selecting points
uniformly on surfaces, it will con-
tribute a large value to the inte-
gral because of the short segment
in the corner and the
Veach describes how multiple importance sampling can be used to ameliorate
this problem.
In 1997, Veach and Guibas [VG97] described the
Metropolis light transport,
or
MLT, algorithm. This was yet another Markov chain Monte Carlo approach, but
the Markov chain no longer formed a random walk in the set
1
r
2
term in
the integrand.
of all surface
points in the scene, as it did in the path-tracing algorithms; instead, the algorithm
takes a random walk in the space of all
paths
in the scene. That is to say, the algo-
rithm may first examine a path of length 1, then a path of length 20, then a path
of length 3, etc. Explicitly describing this space of paths, and how to randomly
sample from it, is difficult. There's also the unfortunate fact that the Metropolis-
Hastings algorithm, on which MLT is based, only provides a result that's guar-
anteed to be
proportional
to the result you're seeking. Fortunately in MLT, we're
seeking a whole array of results (the output pixel values), and the constant of pro-
portionality is the same for all of them. In other words, we get an image that's
some constant multiple of the desired image. But once again, there's bad news:
The constant of proportionality may be zero, that is, we may get an all-black
image. Finally, while MLT's result is guaranteed to be unbiased, it may take a
great many paths to ensure that the variance is low (just as with other Monte Carlo
methods); the rapidity of variance reduction depends, in part, on how cleverly
one chooses a
mutation strategy,
which determines how new paths are gener-
ated from the current one. (This is closely analogous to what we saw in comput-
ing sums of matrix powers: Picking the transition probabilities
p
ij
dramatically
affected the rate of convergence.) Thus, once you develop an MLT renderer, you
can improve upon it by adding more and better mutation strategies; such mutation
strategies are ways to express your knowledge of the structure of light transport.
That is to say, you might argue that if lots of light is being carried along
this
path,
then if you
only
move the eye ray a tiny bit, which moves the first interior point
of the path, but you leave everything else the same, maybe the new path will also
M
