Current stable version: 0.1.1
Home › Metropolis Light Transport

Metropolis Light Transport

Fri, 09/04/2010 - 12:40 — apatriarca

Personal information

Name: Antonio Patriarca
E-mail address: antoniopatriarca@gmail.com
IRC/forum: apatriarca

Idea to implement

Synopsis and Goals

The aim of this project is to implement a new integrator based on the Metropolis Light Transport (MLT) algorithm ([1]) in Yafaray. It is an unbiased rendering method based on the Metropolis-Hastings sampling procedure. In this algorithm a sequence of Light Transport paths are generated recursively mutating a single starting path. Each mutation is then accepted or rejected with a carefully chosen probability, to ensure that paths are sampled according to their contribution to the image. It can efficiently handle arbitrary geometry and lighting conditions using little storage. It is particularly effective with scenes which are usually considered difficult because it explore the path space locally, but it is also competitive with simple scenes.

Detailed description

Path Tracing ([2]) is the older unbiased surface integrator ever described and it is a simple application of the general Monte Carlo integration method to the Light Transport equation. Indeed, if we define a path x as a finite sequence of points xi such that every segment xixi+1does not intersect the scene in its interior, then the Light Transport Equation can be written as an integral over the paths starting from the camera. The Path tracing algorithm generates a set of paths starting from the camera and at each step it decides a random direction to follows. This method is unbiased, but it is not very efficient. In particular, a large number of paths is often necessary to find the more important paths and the computational cost of finding paths is not shared between nearby pixels. Scenes with caustics, glossy materials or with hard to reach lights are often problematic for this integrator.

The Bidirectional Path Tracing algorithm, independently invented by Veach and Guibas in [3] and by Lafortune and Willems in [4], mitigates the first problem. This algorithm generates two paths, one beginning from the camera and one from the light. Then several paths are generated joining them. This method is more efficient than Path Tracing in most scenes because some parts of the path space are best sampled generating paths starting from the light. This is an improvement over the original algorithm, but it does not solve the second problem. Indeed, paths are not shared between nearby pixels even if it is well known that the integrands of nearby pixels are highly correlated.

This problem was solved by the Metropolis Light Transport algorithm invented by Veach and Guibas in [1]. It use a completely different approach than the previous unbiased algorithms. It is in fact based on the Metropolis-Hastings sampling method which generates samples according to a particular function. This method alone is not able to integrate a particular function, but it can be used to reduce the variance. Indeed, the variance of a Monte Carlo integrator is minimum if the samples are sampled with a density function proportional to the integrands. Let suppose we already have an histogram proportional to the function we want to sample from and suppose we have a transition function T mapping this histogram to itself. In other words, T moves samples of the histogram but the number of samples leaving a single bin is the same as the number of samples which enter. If we consider a single sample and recursively apply the transition function recording all the bins the sample visit, we can hope to reconstruct the histogram as limit. This is possible if the transition function assures every state is equally probable. In practice, the transition function randomly mutates the sample and then accept the new sample with probability 1 - a(x -> y), where

The Metropolis Light Transport algorithm is a straightforward application of these ideas to the Light Transport problem. In this case, we consider a function f which assign to each path the contribution made to the image by the light flowing along the path. The image is then simply the integral of this function on the paths starting from the camera. We use therefore the Metropolis-Hasting sampler procedure to sample Light Transport paths according to f and then integrate using a Monte Carlo method. The starting sample is taken like in a (Bidirectional) Path Tracer. A detailed description of the method and of the theory involved can be found in [1] and [5].

The most critical part of a MLT integrator is the definition of the mutation strategies. Several mutations has been proposed in [1], but a lot of work has been done to define new and better mutation strategies. The mutations described in [6] and [7] are particularly important. In [6] the basic algorithm is extended to render scenes with participating media, whereas in [7] a new theoretical framework for mutation is defined.

An important issue of this algorithm is the start-up bias. The first path is in fact sampled according to a density function p which is different from the target one. This can introduce bias. To compensate for this problem a weight W = f(x0)/p(x0) is associated to each path generated from that path. Moreover, starting the MLT algorithm using a single path does not work well since there is an high probability W = 0. Therefore, several paths are generally generated using the Bidirectional Path Tracer algorithm and several chains will run in parallel. The Bidirectional Path Tracer paths are also used to compute an average value of f to scale the values computed using MLT.

There are several techniques available to improve the performance of MLT. Some of them are listed in [5]. All those refinement of the basic algorithm are unbiased. The most important are:

  • Use a standard method to compute direct lighting. Under some direct lighting conditions MLT is not very effective and using a more standard approach improve its performance.
  • Accumulate both accepted and rejected samples scaled by their probability. This optimization replace the random variable by its expected value. This is useful because more samples are accumulated in the image.
  • Break the algorithm in two stage to assures every pixel have roughly the same number of samples. In the first pass an approximation I of the intensity of every pixel is computed and in the second pass the paths are sampled based on f/I.
  • Use importance sampling for mutation probabilities. It is often possible to compute some of the factors of the acceptance probability before casting any rays. We can in this way weight the probabilities of each mutation to increase the chance to choose a good mutation.

In [12] two biased noise filters are introduced. These filters can probably be implemented with MLT as well. The last modification of MLT worth considering is the coherent version described in [13].

MLT is completely different from the others integrator and even if it is a surface integrator (if I will not implement the idea presented in [6]), the surface integrator interface does not have sense in this case. In fact, it does not integrate each pixel separately, but it sample paths on the entire image. It will probably have to inherit from the surfaceIntegrator_t class anyway, but some changes in the program logic will be probably required. Several different mutation strategies are possible and I have not yet decided if I will implement the strategies of [7] or the strategies from [1]. I will also implement a Bidirectional Path Tracer sampler based on [3]. It should not be difficult and I will get some inspiration from the current Bidirectional Path Tracing integrator of Yafaray.

I plan to implement some of the modifications of MLT. I plan in particular to implement a user controlled direct lighting pass, the expected value method and the importance sampling method. The two pass algorithm will be controlled by the user with the number of AA passes. Of the filters described in [12] I plan to implement the consecutive sample filtering even if the expected value method should probably already reduce this problem.

One last issue of MLT is multi-threading. Several markov chains can be evaluated in parallel, but they all have to write on the image at random positions. The usual method used in Yafaray to parallelize a surface integrator cannot be used in this case and a new solution have to be found. My idea to solve this problem is to have a single worker thread which writes the samples on the image and several other worked thread which computes MLT's markov chains.

Workflow and Usability

Most of the usual parameters of the surface integrators are not applicable to MLT. I have yet to decide if this plug-in will use AA_SAMPLE and AA_THRESHOLD to compute the number of mutation per pixel or if it will be an explicit parameter. A new parameter will determine the number of samples (secondary rays) to use for direct lighting pass. If this number is zero, MLT will be used to compute direct lighting. This is useful when there is mostly indirect light.

Tentative schedule

  • Present - April 11. Study Yafaray source code and reference materials of MLT.
  • April 12 - April 22. Write a Design documents describing the basic structure of the code and a detailed road-map of the implementation.
  • April 22 - May 4. Implement a Bidirectional Path Tracing sampler based on Veach and Guibas' paper.
  • May 5 - May 17. Vacation in Japan. Improve the design document based on the experience in the previous period.
  • May 18 - June 18. Implementation of the basic MLT algorithm in a plug-in. In this period I will also try to find a solution to the API problem.
  • June 19 - July 15. Implementation of the modifications to the basic algorithm (doing several tests to compare the performances).
  • July 16. Midterm evaluation.
  • July 16 - July 25. Solution to the problems encountered in the implementation.
  • July 26 - August 6. Tune and test the code.
  • August 7 - August 15. Writing documentation.
  • August 16. Final evaluation.

In June and July, I will have to study for some exams. This isn't a big problem because I have already studied for the majority of them and I will probably only spend a couple of days for exam. Moreover, if I will be accepted at the google summer of code, I plan to give precedence to this project over my studies. By the way, I have already studied and passed some exams when working full time (8 hours a day for 5 days) so I think I can manage it. The only vacancy I plan to do in the following few months is the vacation in Japan already listed in the schedule. I plan to work 6-8 hours each day and work 5 days each week on average.

Biography

My name is Antonio Patriarca and I am a 25 years old Italian student. I am studying a Master degree in Mathematics at Università degli Studi di Torino and I have a Bachelor degree in Cinema and Media Engineering at Politecnico di Torino. I am currently working on my master's thesis on discrete exterior calculus ([8]) in collaboration with a professor at Politecnico di Torino and I plan to graduate in October or December. 
I learned to program when I was at high school (approx. 10 years ago) and I have a very good knowledge of C and C++. Indeed, I have been a moderator of the C/C++ section on the ioprogrammo forum for some years (using celeborn85 as username). I also have a working knowledge of C#, Java and Haskell and a very basic knowledge of other languages like PHP, SQL, Python... In the past, I wanted to be a game developer and attended several real-time graphics related online courses at GameInstitute ([9]). I am not anymore interested in working in the game industry, but I am still very interested in computer graphics. I regularly read some graphics related journal like "ACM Transactions on Graphics" and I am an ACM student member since 2005. In 2006, I attended the Siggraph Conference in Boston and really enjoyed it. I also attended several computer graphics related courses at University. In two of them I learned to use Blender and learned about Yafaray.
I have not a lot of practical experience of ray-tracers or off-line renderers in general, but I have a good theoretic understanding. I learned the basics following the Computer Graphics course OCW ([10]) and reading the pbrt book ([11]). I wanted to develop an unbiased renderer since I learned about these algorithms, but I never found the time or motivation to work on such a big project. Therefore, I have only made simple (Whitted or Distributed) ray tracers. I first learned about MLT a couple of years ago looking for unbiased algorithms. I have also joined the Indigo forum where there was several discussion about this algorithm. 

References