I have implemented Metropolis light transport (MLT)  for this assignment, as I found it to be an particularly innovative approach to global illumination and to integration in general. In the process of implementing the MLT algorithm, I had to implement path tracing as well, and I present the results of path tracing as well below.
Path tracing, introduced by Kajiya in , can be seen as a straightforward extension of stochastic ray tracing, with the addition that secondary rays are shot not only from specular surfaces but from diffuse surfaces as well. This allows the technique to capture effects like diffuse-diffuse interactions and caustics. While it is complete in that it solves the full rendering equation, it can be slow to converge.
Metropolis light transport is based on a general sampling technique called Metropolis sampling  which can perform importance samping of an arbitrary distribution. It does this by setting up a Markovian process over the domain and carefully defining its transition probabilities so that its stationary distribution is equal to the desired one. The MLT algorithm applies this technique to importance sampling over the set of all light paths in the scene, thereby computing the global illumination. The basic advantage over other global illumination methods such as bidirectional path tracing is that Metropolis sampling can concentrate more effort on important light paths in the scene which other techniques are oblivious to.
While the conceptual basis for the MLT algorithm was quite clear from the original paper, I chose to implement a slightly different formulation for choosing the light paths as given in , which shows how to apply Metropolis sampling to an existing Monte Carlo method such as path tracing and bidirectional path tracing. This should retain the advantages of Metropolis sampling while being much simpler to implement than the original paper's novel path mutation strategy. Therefore, I implemented a path tracer and added Metropolis sampling to it through their approach.
Since Metropolis sampling is not guaranteed to be well-stratified in the image plane, it is suggested in  that direct lighting and specular interactions should be computed by standard Cook-style ray tracing, and MLT should be used only for the indirect lighting. I have used this approach and it works very well in practice.
Results and discussion
I modeled a Cornell box with coloured walls and two spheres and rendered it using the two algorithms. The results are shown below. Both images took the same computation time.
Metropolis light transport
The result of path tracing is very clean for diffuse lighting, but performs poorly at sampling the caustics in the scene. The scattered white dots are due to the light reflected from the second sphere.
Metropolis light transport works better on the caustics and the reflected light. Note the caustic on the left wall that is caused by light reflected from the second sphere focused through the first one. However, the rendering also suffers from noticeable noise and "patchiness". In hindsight I believe this is because Metropolis sampling depends on being able to sample neighbouring light paths close to the imporant ones, such as caustics. In such cases, it is more important to limit the mutation of the portion of the path near the light. However, since path tracing constructs the path starting from the camera, it is difficult to do so as small mutations in the path from the camera end can cause large changes in the path at the light end. I believe that a Metropolis sampler using bidirectional sampling or even backwards ray tracing should perform better.
Metropolis light transport
This example clearly demonstrates the superiority of Metropolis sampling over other algorithms which are oblivious to the important light transport paths in the scene. While regular path tracing is unable to sample the caustic cast by the cylinder to any degree of accuracy, Metropolis sampling is able to concentrate its efforts on exactly those paths which generate the caustic since they contribute a significant amount of indirect light to the scene. Bidirectional path tracing would have difficulty sampling the caustic as well, since it does not form a significant fraction of the light paths originating from the light source.
The source code for the implementation is in a Visual C++ project: globillum.zip (13.6 KB)
- Eric Veach and Leonidas J. Guibas. "Metropolis Light Transport".
- James T. Kajiya. "The Rendering Equation".
- Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, and Augusta H. Teller. "Equation of State Calculations by Fast Computing Machines".
- Csaba Kelemen, László Szirmay-Kalos and György Antal and Ferenc Csonka. "A Simple and Robust Mutation Strategy for the Metropolis Light Transport Algorithm".