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.

Go back to First Math screen
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed April 01, 1998, G. Scott Owen,