Current stable version: 0.1.1
Home › Energy Redistribution Path Tracing

Energy Redistribution Path Tracing

Fri, 02/04/2010 - 13:09 — apatriarca

Personal information

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

Idea to implement

Synopsis and Goals.

The main goal of this project is to implement a new surface integrator based on the Energy Redistribution Path Tracing (ERPT) algorithm ([1]). This method combines Bidirectional Path Tracing ([2], [3]) and Metropolis Light Transport (MLT) ([4]) to get the best of both approaches. It generates a certain number of paths for each pixels as a bidirectional path tracer, but it then recursively mutates each path as in MLT. In this way it solves the start-up bias problem of MLT without sacrificing its performances. Indeed, an image rendered using an ERPT integrator generally has a lower variance and a lower frequency noise than the same image rendered using a Bidirectional Path Tracer. The integrator will be implemented as a plug in. To simplify the future implementation of similar integrators, I will also independently implement a Bidirectional Path Tracer sampler based on Veach and Guibas description ([2]) and a simple API to simplify the implementation of new mutation strategies.

Detailed description.

Path Tracing ([5]) 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+1doesn't 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 isn't very efficient. In particular a large number of paths are often necessary to find the more important paths and the computational cost of finding paths isn't shared between nearby pixels. Scenes with caustics, glossy materials or with hard to reach lights are often problematic for this integrator.

The Bidirectional Path Tracer, independently invented by Veach and Guibas in [2] and by Lafortune and Willems in [3], 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 is best sampled generating paths starting from the light. This is an improvement over the original algorithm, but it doesn't solve the second problem. Indeed, paths aren't shared between nearby pixels even if it is well known that the integrands of nearby pixels are highly correlated.

Veach and Guibas solve this problem inventing the Metropolis Light Transport (MLT) algorithm in [4]. It is based on the Metropolis sampling used in computational physics and it uses a completely different approach than the methods above. In fact, the MLT algorithm doesn't integrate each pixel in isolation, but it samples paths according to a density function proportional to the contribution made to the image by the light flowing along these paths and it directly add these contributions to the image. A first bidirectional path is chosen and then it is recursively mutated. All new generated paths are randomly rejected based on an acceptance probability. There are two main problems related to this algorithm. The first problem is that the final result depends by the first chosen path. This is known as start-up bias. The second problem is the necessity to use very long chains and a large set of mutations to sample all the image plane.

The Energy Redistribution Path Tracing algorithm partially solves these problems. Using the Bidirectional Path Tracing algorithm an average energy (luminance) of the image is first computed. This average energy is then used to compute the contribution every accepted path will give to the image. Then, for each pixel in the image, a set of paths is created using a Bidirectional Path Tracing sampler. The contribution of each path is then redistributed to nearby pixels mutating this path in a way similar to MLT. It doesn't exhibit the start-up bias since it is based on Bidirectional Path Tracing and it requires shorter chains because it requires more local mutations. In ERPT is also possible to use additional variance reduction strategies used in the other Monte Carlo integrators. The original paper only describes two mutation strategies: lens perturbations and caustic perturbations. It also describes two biased filters to reduce noise in the image.

The ERPT integrator will be implemented as a plugin of Yafaray. MLT renderers usually assign one or more Markov chains to each thread. The Bidirectional Path Tracing integrator assign to each thread one or more tiles of the image. Since ERPT is more local than MLT and the chains are shorter, it doesn't make sense to use the MLT strategy and the ERPT integrator will work independently on each tile. Unfortunately, the current surface integrator API isn't very well suited to this algorithm. I will probably have to redefine the render function and change its logic.

The original paper of ERPT assumes a box filter is used. This problem is described in [10] but not solved. I plan to write an e-mail to David Cline to ask for suggestions or clarifications. I will also read in details how this problem is solved in MLT and try to adapt the results to ERPT. I probably also have the tools to solve this problem analytically, but it is not my mathematical specialization and it would probably take a lot of time. But this is an important issue in the implementation of the plug-in and I have to find a solution.

MLT renderers usually compute direct lightning separately because path mutations are not very efficient in this case. I have therefore to decide if it makes sense to do the same in this plug-in or if the basic ERPT algorithm is enough. This problem is not described in [10], so it is not probably very important. I will write tests the plug-in with and without the direct lightning pass and compares the performances. 

To implement this integrator I will also have to implement a Bidirectional Path Tracing sampler which generates new paths and a new API to manages paths and mutations. Since these functionalities can be useful in other integrators, I will implement them independently. The filters will be directly implemented in the integrator. While the consecutive sample filter is very easy to implement, I have some doubts regarding the proposed mutation filter. The main issue with this filter is the necessity to apply it on the entire image and to save the number of proposed mutations for each pixel. 

Workflow and Usability.

The ERPT integrator will support the same parameters of the Bidirectional Path Tracing integrator but some thoughts will be required to decide the meaning of the AA_SAMPLES in this case. Few additional parameters will be added:

  • Chain Length. The number of mutations for each pixel. A number between 100 and 1000 is suggested in the [1].
  • Noise Removal Filter. It can be one of NONE, PROPOSED_MUTATION, CONSECUTIVE_SAMPLE or BOTH. The filters are described in [1].
  • Kernel Size. If PROPOSED_MUTATION is used it defines the dimension of the convolution kernel.

Tentative schedule.

  • Present - April 11. Study Yafaray source code and reference materials of both MLT and ERPT. Write an email to David Cline to ask for clarifications and suggestions.
  • 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 13. Beginning implementation of the plug-in. In this period I will also try to find a solution to the problems described in this proposal.
  • June 14 - July 15. Implementation of the ERPT algorithm in the plug-in and of the mutation strategies. 
  • July 16. Midterm evaluation.
  • July 16 - July 25. Implementation of the noise filters or 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.

I wrote the email to David Cline to ask for suggestions. But I'm not very convinced ERPT doesn't work with image filters. If Cline will not reply, I will probably just ignore the problem until some tests will prove it is indeed an issue.

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 ([6]) 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 ([7]). 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 ([8]) and reading the pbrt book ([9]). 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 Energy Redistribution Path Tracing a couple of years ago looking for unbiased algorithms. It was the algorithm I decided to implement in my dreamed unbiased renderer. This is the reason I have decided to apply to this project and idea. I never implemented it, but I have a quite good understanding of the algorithm and I am very motivated to finally develop it.

References: