# 2 Monte Carlo Integration

Rendering is full of integration problems. In addition to the light transport equation (1.1), in the following chapters we will see that integral equations also describe a variety of additional quantities related to light, including the sensor response in a camera, the attenuation and scattering of light in participating media, and scattering from materials like skin. These integral equations generally do not have analytic solutions, so we must turn to numerical methods. Although standard numerical integration techniques like trapezoidal integration or Gaussian quadrature are effective at solving low-dimensional smooth integrals, their rate of convergence is poor for the higher dimensional and discontinuous integrals that are common in rendering. Monte Carlo integration techniques provide one solution to this problem. They use random sampling to evaluate integrals with a convergence rate that is independent of the dimensionality of the integrand.

Monte Carlo integration
has the useful property that it
only requires the ability to evaluate an integrand at arbitrary
points in the domain in order to estimate the value of its integral . This property not only makes Monte Carlo easy to implement but
also makes the technique applicable to a broad variety of integrands. It
has a natural extension to multidimensional functions; in
Chapter 13, we will see that the light
transport algorithm implemented in the `RandomWalkIntegrator` can be
shown to be estimating the value of an infinite-dimensional integral.

Judicious use of randomness has revolutionized the field of algorithm
design. Randomized algorithms fall broadly into two classes: *Las
Vegas* and *Monte Carlo*. Las Vegas algorithms are those that use
randomness but always give the same result in the end (e.g., choosing a
random array entry as the pivot element in Quicksort). Monte Carlo
algorithms, on the other hand, give different results depending on the
particular random numbers used along the way but give the right answer
*on average*. So, by averaging the results of several runs of a Monte
Carlo algorithm (on the same input), it is possible to find a result that
is statistically very likely to be close to the true answer.

The following sections discuss the basic principles of Monte Carlo
integration, focusing on those that are widely used in `pbrt`. See also
Appendix A, which has the implementations of
additional Monte Carlo sampling functions that are more rarely used in the
system.