Graphics Reference
In-Depth Information
y
the surface into small rectangles, also work. Press et al. [Pre95] describe these and
more sophisticated deterministic methods.
A probabilistic or Monte Carlo method for computing, or more precisely,
for estimating the integral of f over the interval [ a , b ] ,isthis:Let X 1 ,
...
, X n be
a ) n i = 1 f ( X i ) is
a random value whose average (over many different choices of X 1 ,
randomly chosen points in the interval [ a , b ] . Then Y =( b
...
, X n )isthe
integral [ a , b ] f . To implement this we use a random number generator to generate n
points x i in the interval [ a , b ] , evaluate f at each, average the results, and multiply
by b
x
20-sample estimate = 1.4598
Exact value
= 2 ¯
1.571
a . This gives an estimate of the integral, as shown in Figure 30.2. Of
course, each time we compute such an estimate we'll get a different value. The
variance in these values depends on the shape of the function f . If we generate the
random points x i nonuniformly, we must slightly alter the formula. But in using
a nonuniform distribution of points we gain an enormous advantage: By making
our nonuniform distribution favor points x i where f ( x ) is large, we can drastically
reduce the variance of our estimate. This nonuniform sampling approach is called
importance sampling. Figure 30.3 shows an example.
Figure
30.2:
Estimating
1
1 1 x 2 dx with 20 samples
approximates the correct result,
which is 2 1. 571 .
y
y
We can integrate a function f over a surface region R by an analogous method.
We choose points uniformly randomly on R , average the values of f at these points,
and multiply by the area of the region. Or we can generate points nonuniformly,
and compute a weighted average, again multiplied by the region's area, generaliz-
ing importance sampling. Our main application of numerical integration is when
R is either the sphere or the outward-facing hemisphere at some surface point P
where we're trying to compute the scattered light (i.e., trying to evaluate the inte-
gral in the reflectance equation). We'll return to this application at the end of the
chapter.
Randomized integration techniques form part of the working tools of anyone
studying rendering, and much of the rest of graphics. Press et al. [Pre95] is a solid
first reference for ideas beyond those discussed in this chapter.
x
x
20-sample estimate = 1.6121
Exact value
20-sample estimate = 1.6121
Exact value
2
2
=
=
¯
¯
1.571
1.571
Figure 30.3: Estimating the same
integral, again with 20 samples,
but preferentially selecting sam-
ples near x = 0 , and using appro-
priate weighting, gives a better
approximation.
30.3 Random Variables and Randomized
Algorithms
Because the major shift in rendering methods over the past several decades was
from deterministic to randomized, we'll be discussing randomized approaches to
solving the rendering equation. To do so means using random variables, expecta-
tion, and variance, all of which we assume you have encountered in some form
in the past. To establish notation, and prepare for the continuum and mixed-
probability cases, we review discrete probability here. The approach we take may
seem a little unusual. That's because our goal is not to analyze some probabilistic
phenomenon that already exists (e.g., the chance of rainfall in Boston tomorrow,
given that it's already been raining for two days), but rather to construct proba-
bilistic situations in which something computable, like expected value, turns out
to have the same value as some integral (like the reflectance integral) that we
care about. That leads to emphasis on some things that are largely downplayed in
introductory probability courses.
We often find that for our students, the connection between formal probabil-
ity theory and programs that implement probabilistic ideas is unclear, and so we
discuss this connection as well.
Those familiar with these concepts can skip forward to Section 30.3.8.
 
 
 
Search WWH ::




Custom Search