The Monte-Carlo Estimation Technique

Here about this Monte-Carlo buzz word. Ideally, an exact evaluation of the global illumination value at a given pixel in a given scene would require the evaluation of several integrals. But because the integrals that we find in a typical 3D scene are not analytically evaluatable, we have to resort to an approximate evaluation technique, which is called Monte-Carlo integration. 

Please sit on the chair...

The name Monte-Carlo comes from the fact that it is really driven by chance. Suppose you have two large dices one numbered from 1 to 360 gives you an azimuth value and the other numbered from 1 to 180 gives you an elevation value. You throw the two dices and then record the environment as seen through a pin-hole in the direction suggested by the dices.

If you repeated this often enough, you will eventually have a good idea of what the whole environment looks like. Obviously, repeating this process only a few times will not give you a good idea of the environment. Especially, if each time you repeated it, the pin-hole oriented toward the sky, then you could very well conclude wrongly that the whole environment is blue.

So it is best to test the scene at many many sample points in order to acquire a statistically plausible estimate of the integral. Obviously, the more samples you take, the higher probability you have that the estimate reflects the true value. Exactly the same idea applies to any Monte-Carlo based estimation technique including photon mapping. The more samples you take, the more exact the estimate.

How Monte-Carlo is used

The main difference between the Photon Mapping and the other Monte-Carlo GI rendering algorithms, since they are both Monte-Carlo based, is in the way they estimate the global illumination.

Traditional Monte-Carlo GI typically launches thousands of rays through each pixels. Each of those rays bounces around in the scene, accumulating the interactions between the rays and the surfaces as they go, until it reaches a light.

There is also another class of Monte-Carlo GI algorithm which does the exact opposite which is shooting photons from the lights, bouncing around in the scene until it reach the camera through each pixels a few thousand times. As can be expected, those algorithms takes just as long to render as one another. The main advantage here is that since the photons are shot from the lights, those algorithms can compute caustics while the previous class of algorithm can't.

Yet another class of Monte-Carlo GI algorithm is called multi-pass. They try to use the best from both the previous classes of GI algorithms. Photon Mapping is a two-pass algorithm, which takes this mixed approach, and adds two very clever twists.

The impact of Monte-Carlo on render time

Just for comparison, if you set Multi-Pass ON in A:M with only one pass, you get the time it takes to render the scene with only one sample per pixel and roughly 1 bounce per ray. This results in 300 thousand light-surface interaction computations for a 640x480 image. Shooting one thousand rays through each pixels would take one thousand time longer.

Now suppose that you turn soft shadows ON by setting the number of rays to 30 which is, BTW, also a Monte-Carlo estimation technique used to estimate soft shadows. You now have 30 samples in the environment per pixels and thus, you already have 9 million light surface interaction to compute which takes 30 times longer to render.

But wait! there's more. In a typical ray-tracing algorithm, rays are only reflected off reflective surfaces while in global illumination algorithms, rays are reflected off every surfaces. Not only those surface where some reflectivity is set. This is precisely what produces the global illumination effect. So you can easily imagine that a typical Monte-Carlo scene render can take several hours to several days to render even several weeks for some architectural simulations.

Assuming a 640x480 image with 1000 samples per pixels and an average of 20 bounces per samples, this results un 6 billion light-surface interaction computations. Roughly taking 20 thousand more time to render than our ray-traced image. At this rate, the same image which hypothetically took 1 minute to render with ray-tracing could take 13 days with a pure Monte-Carlo GI renderer

Although it is possible to reduce the number of samples per pixels, doing so in pure Monte-Carlo renderers only produces noisy renders. The lower the number of rays per pixels, the noisier the render. Fortunately, Photon Mapping is much more clever than that.