Monte Carlo Integration
Motivation
Quadrature rules
To integrate the function
Pretend you don't know the equation for the following function and you want to know its area bounded by it. In high school, we were taught that the integral can be approximated with infinitesimal rectangles, a.k.a. the rectangle rules. So let's put together a bunch of rectangles and crunch some numbers!
As the number of rectangles grows, the closer it fills the target area. To which I can say with confidence the area is
There are more similar approaches to do integration and they are known as quatrature rules. The generalized form looks like this
Downside
These kind of numerical approximations suffers from two major problems.
High-frequency signals
Graphs like this can't be easily approximated with thick bars. To get closer to the real value, the bars must be really narrow which means more iterations to compute.
High-dimensional domains
where
Definition
As the name suggests, we can integrate functions with stochastic approaches through random sampling. With the Monte Carlo method, we can tap into the power of integrating arbitrary multi-dimensional functions!
where
It comes with the following benefits:
- It has a convergence rate of
in any number of dimensions, which quadrature rule methods cannot achieve. - Simplicity. All you need is two functions
sample()
andeval()
, and occationally finding a suitable pdf.
Sampling random variables
Generating uniform samples (e.g.
Inverse Transform Sampling
This is a method for generating random variables from a given probability distribution (pdf) by using its inverse cumulative distribution (cdf). Imagine the likelihood of picking a random variable
From the above example, we can see most samples are centered at the highest probability area while the tails on both sides will have lower sample count. Good thing with this method is that it can be easily extended to multi-dimensional cases, and stratifying samples in the domain helps improves exploring the entire domain.
Downside
The pdf must be known, also building the cdf takes time and memory. And if the cdf cannot be inverted analytically, numerically computing the inverse mapping value (e.g. binary search) on every drawn samples is quite costly.
Note: A more efficient sampling structure exists out there, and it's called the Alias Method, which samples can be drawn in constant
Rejection Sampling
When the pdf is difficult to sample, we can instead sample from a simpler density
The sampling space is defined as the tight bounding box of the shape, since drawing samples from a square is much simpler. We know the probability
- Sample
according to (draw a point inside the square) - Sample
uniformly on - If
, return the sample - Else, repeat 1
In the above case,
Importance Sampling
Approx
BSDF Sampling
Depending on the surface properties, there are certain directions (
Light Sampling
In case when BSDF failed to find a significant contribution, other words the outgoing ray direction missed the light source, light sampling then comes into play to provide as a backup strategy.
To importance sample the light instead of solid angle, the density
Transformation of Space / Conversion of Domain
Multiple Importance Sampling
Next event estimation can be seen as a multiple importance sampling1 approach of integrating the radiance since it combines two sampling strategies, BSDF sampling and light sampling, often called as direct and indirect lighting.
-
Veach, E. (1997). Robust Monte Carlo Methods for Light Transport Simulation. (Doctoral dissertation, Stanford University). ↩