“Metropolis light transport” by Veach and Guibas

We present a new Monte Carlo method for solving the light transport problem, inspired by the Metropolis sampling method in computational physics. To render an image, we generate a sequence of light transport paths by randomly mutating a single current path (e.g. adding a new vertex to the path). Each mutation is accepted or rejected with a carefully chosen probability, to ensure that paths are sampled according to the contribution they make to the ideal image. We then estimate this image by sampling many paths, and recording their locations on the image plane. Our algorithm is unbiased, handles general geometric and scattering models, uses little storage, and can be orders of magnitude more efficient than previous unbiased approaches. It performs especially well on problems that are usually considered difficult, e.g. those involving bright indirect light, small geometric holes, or glossy surfaces. Furthermore, it is competitive with previous unbiased algorithms even for relatively simple scenes. The key advantage of the Metropolis approach is that the path space is explored locally, by favoring mutations that make small changes to the current path. This has several consequences. First, the average cost per sample is small (typically only one or two rays). Second, once an important path is found, the nearby paths are explored as well, thus amortizing the expense of finding such paths over many samples. Third, the mutation set is easily extended. By constructing mutations that preserve certain properties of the path (e.g. which light source is used) while changing others, we can exploit various kinds of coherence in the scene. It is often possible to handle difficult lighting problems efficiently by designing a specialized mutation in this way.

1. ARVO, J., AND KIRK, D. Particle transport and image synthesis. Computer Graphics (SIGGRAPH 90 Proceedings) 24{, 4 (aug. 1990), 63-66.
2. BEYER, M., AND LANGE, B. Rayvolution: An evolutionary ray tracing algorithm. In Eurographics Rendering Workshop 1994 Proceedings (June 1994), pp. 137-146. Also in Photorealistic Rendering Techniques, Springer-Verlag, New York, 1995.
3. COLLINS, S. Reconstruction of indirect illumination from area luminaires. In Rendering Techniques ’95 (1995), pp. 274-283. Also in Eurographics Rendering Workshop 1996 Proceedings (June 1996).
4. COOK, R. L., PORTER, T., AND CARPENTER, L. Distributed ray tracing. Computer Graphics (SIGGRAPH 84 Proceedings) 18, 3 (July 1984), 137-145.
5. DUTRE, P., AND WILLEMS, Y. D. PotentiM-driven Monte Carlo particle tracing for diffuse environments with adaptive probability density functions. In Rendering Techniques ’95 (1995), pp. 306-315. Also in Eurographics Rendering Workshop 1996 Proceedings (June 1996).
6. GOLDBERG, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Massachusetts, 1989.
7. HALMOS, P. R. Measure Theory. Van Nostrand, New York, 1950.
8. HECKBERT, P. S. Adaptive radiosity textures for bidirectional ray tracing. In Computer Graphics (SIGGRAPH 90 Proceedings) (Aug. 1990), vol. 24, pp. 145-154.
9. JENSEN, H. W. Importance driven path tracing using the photon map. In Eurographics Rendering Workshop 1995 (June 1995), Eurographics.
10. KAJIYA, J. T. The rendering equation. In Computer Graphics (SIGGRAPH 86 Proceedings) (Aug. 1986), vol. 20, pp. 143-150.
11. KALOS, M. H., AND WHITLOCK, P. A. Monte Carlo Methods, Volume I: Basics. John Wiley & Sons, New York, 1986.
12. LA~ORTUNE, E. P., AND WILLEMS, Y. D. Bi-directional path tracing. In CompuGraphics Proceedings (Alvor, Portugal, Dec. 1993), pp. 145-153.
13. LAFORTUNE, E. P., AND WILLEMS, Y. D. A theoretical framework for physically based rendering. Computer Graphics Forum 13, 2 (June 1994), 97-107.
14. LA~ORTUNE, E. P., AND WILLEMS, Y. D. A 5D tree to reduce the variance of Monte Carlo ray tracing. In Rendering Techniques ’95 (1995), pp. 11-20. Also in Eurographics Rendering Workshop 1996 Proceedings (June 1996).
15. METROPOLIS, N., ROSENBLUTH, A. W., ROSENBLUTH, M. N., TELLER, A. H., AND TELLER, E. Equations of state calculations by fast computing machines. Journal of Chemical Physics 21 (1953), 1087-1091.
16. MITCHELL, D. P., AND HANRAHAN, P. Illumination from curved reflectors. In Computer Graphics (SIGGRAPH 92 Proceedings) (July 1992), vol. 26, pp. 283-291.
17. PATTANAIK, S. N., AND MUDUR, S. P. Adjoint equations and random walks for illumination computation. A CM Transactions on Graphics 14 (Jan. 1995), 77-102.
18. PESKUN, P. H. Optimum monte-carlo sampling using markov chains. Biometrika 60, 3 (1973), 607-612.
19. REIF, J. H., TVCAR, J. D., AND YOSHIDA, A. Computability and complexity of ray tracing. Discrete and Computational Geometry 11 (1994), 265-287.
20. SHIRLEY, P., WADE, B., HUBBARD, P. M., ZARESKI, D., WALTER, B., AND GREENBERC, D. P. Global illumination via density-estimation. In Eurographics Rendering Workshop 1995 Proceedings (June 1995), pp. 219-230. Also in Rendering Techniques ’95, Springer-Verlag, New York, 1995.
21. SHIRLEY, P., WANe, C., AND ZIMMERMAN, K. Monte Carlo methods for direct lighting calculations. A CM Transactions on Graphics 15, 1 (Jan. 1996), 1-36.
22. SPANIER, J., AND GELBARD, F~. M. Monte Carlo Principles and Neutron Transport Problems. Addison-Wesley, Reading, Massachusetts, 1969.
23. VEACH, E. Non-symmetric scattering in light transport algorithms. In Eurographics Rendering Workshop 1996 Proceedings (June 1996). Also in Rendering Techniques ’96, Springer-Verlag, New York, 1996.
24. VEACH, E., AND GUIBAS, L. Bidirectional estimators for light transport. In Eurographics Rendering Workshop 1994 Proceedings (June 1994), pp. 147-162. Also in Photorealistic Rendering Techniques, Springer-Verlag, New York, 1995.
25. VEACH, E., AND GUIBAS, L. J. Optimally combining sampling techniques for Monte Carlo rendering. In SIGGRAPH 95 Proceedings (Aug. 1995), Addison-Wesley, pp. 419-428.
26. WHITTED, T. An improved illumination model for shaded display. Communications of the A CM 32, 6 (June 1980), 343-349.