# Monte Carlo Methods for Computer Graphics

Reference S.P. Mudur and S.N. Pattanik, "Monte Carlo Methods for Computer Graphics", State of the Art Reports, Eurographics'93, Barcelona, Sept. 6-10, 1993.:

The Monte Carlo method is a numerical method for solving mathematical problems using stochastic sampling. Look at a simple Monte Carlo technique known as the "hit or miss" method.

Assume we have a function f(x) and we want to find the integral of f(x) from x = 0.0 to x = 1.0. We can draw a unit square, choose N random points within the square. For each point we determine if it lies below the f(x) curve, if it does then we increment a counter Hit. Then the area under the curve is given by Hit/N. N = Hit + Miss.

Note two features of this method. First, an algorithm is written to perfom one random test and then repeated N times. Second, the statistical measure of error is proportional to (D/N)^1/2 where D depends on the particular Monte Carlo technique used.

Another method for finding an integral is called Monte Carlo quadrature. This consists of the following steps:

1. Let G = òg(x) dx be the integral to be evaluated. 2. Rewrite g(x) as f(x)g'(x) where f(x) is a probability distribtion function and g'(x) = g(x)/f(x). Note that for a uniform random distribution in the interval [a,b] the pdf = 1/(b-a). 3. Sample f (x) for a xi, i.e. obtain some xi from f(x). 4. For each such sample xi evaluate g'(x). 5. Perform steps 3 and 4 N times. Then the average = 1/N SNi=1 g'(x). The estimate has an associated error, i.e. = G + error where error is approximately equal to (variance(g')/N)^1/2.

One value of the variance that is frequently used is the sample variance S2 where: S2 = 1/(N-1)SNi=1 (g'(x) - )2.

So we can improve the accuracy by increasing the number of samples N or by decreasing the variance. We can decrease the variance by eliminating potential samples with unusually high or low values.

Last changed April 01, 1998, G. Scott Owen, owen@siggraph.org