From CGAFaq
Monte Carlo Integration in Computer Graphics
Complicated integrals show up often in computer graphics, especially in
rendering. At first glance these integrals may seem too impossibly complex to
compute, and indeed it is often impossible to compute them exactly (see for
example the rendering equation). However, in many cases there is an
intuitive way to think about what these integrals mean, and this interpretation
leads to a natural way of evaluating them.
Example
Let's look at a simple example:
 = \int_{\cal H} L(\mathbf{x},\omega) d\sigma_{\mathbf{x}}^{\perp}(\omega) )
This equation tells us how much light is hitting a point 
on the
surface of some object. More exactly, it gives us the irradiance, 
,
at in terms of the incoming radiance, 
, in every
direction on the hemisphere 
around . The last
term, )
is the projected solid angle measure
- it tells us how significant the contribution
of light in a direction 
is relative to other directions.
For example, light hitting the surface at a shallow angle
will contribute to the total irradiance less than light hitting the
surface straight on. (We'll look at exactly how to compute this in a moment.)
Looking at this collection of symbols, it may not be clear how to best compute
. However, if we think about what the equation means, it becomes more
obvious.
Imagine a tiny insect sitting at our point on the surface. The
bug can look at a point in the sky and judge how bright it is on a scale from
one to ten. If he writes down this score for a bunch of different points and
then takes their average, he'll have a pretty good estimate of the sky's
overall brightness.
Discussion
The insect analogy demonstrates how Monte Carlo integration can
be applied to our irradiance integral. We pick a set of random directions
, measure the incoming radiance )
in that direction, and
then find the average of these values. At this point the simplicity and
elegance of Monte Carlo integration may be apparent: we can approximate
the integral of a complicated function while knowing essentially nothing about its
overall shape.
Of course, we have to be careful about a few things. First, as noted before,
the same amoung of light coming in at different directions will contribute
different amounts to the overall brightness, so we need to weight our sample
values accordingly. Specifically, we weight the values by the cosine
between the normal direction at and the direction of the
incoming radiance (see the rendering equation for an explanation of this
weight). In general, we have some measure associated with our
integral which tells us how much samples from a region of the domain
should contribute to the total.
Second, we have to make sure that we didn't sample one part of the hemisphere
more than others. If we did, then our guess is biased, and won't
accurately represent the irradiance at . The issue of bias comes
up not only with this irradiance integral, but when estimating any integral
using point sampling: we must make sure to sample all regions of the domain
equally. The simplest way to do this is by using uniform sampling, where
each point is just as likely to be picked as any other.
Monte Carlo Integration in General
Any Monte Carlo estimate which uses uniform sampling has the form
 )
where 
is the function being integrated, 
is the number of samples used
in the estimate, and 
is the (randomly generated) location of the 
th
sample. Some corresponding pseudocode might look like
integrateMC( f, N )
{
estimate = 0
for i = 1 .. N
{
estimate += (1/N) * f( uniformRand(f) )
}
return( estimate )
}
where uniformRand() produces a (uniformly) random location in f's
domain. In the case of our irradiance integral, f represents . The
function f may simply look up into an environment map of radiance values,
or may require yet another Monte Carlo integration (this recursive
structure is apparent in the rendering equation).
More generally, an estimate can use any distribution of samples
(not just a uniform distribution), and will remain unbiased as long as it takes
this distribution into account. A more general estimate has the form
}{p(X_i)} )
where )
is the probability density of samples . The topic of
importance sampling further explores the use of different sampling
densities, but the idea is to get a more efficient estimate of the integral by
being intelligent about where samples are placed. For instance, dark parts of
the sky won't contribute significantly to our irradiance estimate, so we may
not need to take many samples there.
It is worth noting that while Monte Carlo integration is a fantastic
general-purpose algorithm, it is also a brute-force approach. For simple
integrals (especially smooth, low-dimensional ones), faster, more precise
methods often exist. On the other hand, Monte Carlo is currently the only way
to evaluate some complex, high-dimensional integrals like the rendering
equation with complete accuracy.
