“Adjoint-driven Russian roulette and splitting in light transport simulation”

  • ©Jiří Vorba and Jaroslav Křivánek




    Adjoint-driven Russian roulette and splitting in light transport simulation





    While Russian roulette (RR) and splitting are considered fundamental importance sampling techniques in neutron transport simulations, they have so far received relatively little attention in light transport. In computer graphics, RR and splitting are most often based solely on local reflectance properties. However, this strategy can be far from optimal in common scenes with non-uniform light distribution as it does not accurately predict the actual path contribution. In our approach, like in neutron transport, we estimate the expected contribution of a path as the product of the path weight and a pre-computed estimate of the adjoint transport solution. We use this estimate to generate so-called weight window which keeps the path contribution roughly constant through RR and splitting. As a result, paths in unimportant regions tend to be terminated early while in the more important regions they are spawned by splitting. This results in substantial variance reduction in both path tracing and photon tracing-based simulations. Furthermore, unlike the standard computer graphics RR, our approach does not interfere with importance-driven sampling of scattering directions, which results in superior convergence when such a technique is combined with our approach. We provide a justification of this behavior by relating our approach to the zero-variance random walk theory.


    1. Aldous, D., and Vazirani, U. 1994. “Go with the winners” algorithms. In Proc. 35th IEEE Symp. on Found. of Comp. Sci. Google ScholarDigital Library
    2. Arvo, J., and Kirk, D. 1990. Particle transport and image synthesis. In Proc. SIGGRAPH ’90, ACM, 63–66. Google ScholarDigital Library
    3. Bashford-Rogers, T., Debattista, K., and Chalmers, A. 2012. A significance cache for accelerating global illumination. Computer Graphics Forum 31, 6, 1837–51. Google ScholarDigital Library
    4. Bashford-Rogers, T., Debattista, K., and Chalmers, A. 2013. Importance driven environment map sampling. IEEE Trans. Vis. Comput. Graphics 19. Google ScholarDigital Library
    5. Bolin, M. R., and Meyer, G. W. 1997. An error metric for Monte Carlo ray tracing. In In Rendering Techniques ’97. Google ScholarDigital Library
    6. Booth, T., E., and Hendricks, J., S. 1984. Importance estimation in forward MC calculations. Nuc. Tech./Fusion 5, 1.Google Scholar
    7. Booth, T. E. 1985. Monte Carlo variance comparison for expected-value versus sampled splitting. Nucl. Sci. Eng. 89, 4.Google ScholarCross Ref
    8. Booth, T., E. 2006. Genesis of the weight window and the weight window generator in MCNP – a personal history. Tech. Rep. LA-UR-06-5807, July.Google Scholar
    9. Booth, T., E. 2012. Common misconceptions in Monte Carlo particle transport. Applied Radiation and Isotopes 70.Google Scholar
    10. Christensen, P. H. 2003. Adjoints and importance in rendering: An overview. IEEE Trans. Vis. Comput. Graphics 9, 3, 329–340. Google ScholarDigital Library
    11. Cook, R. L., Porter, T., and Carpenter, L. 1984. Distributed ray tracing. SIGGRAPH Comput. Graph. 18, 3 (Jan.). Google ScholarDigital Library
    12. Dutré, P., and Willems, Y. 1994. Importance-driven Monte Carlo light tracing. In Eurographics Workshop on Rendering.Google Scholar
    13. Dutré, P., Bala, K., and Bekaert, P. 2006. Advanced Global Illumination, 2nd ed. A. K. Peters. Google ScholarDigital Library
    14. Gassenbauer, V., Křivánek, J., and Bouatouch, K. 2009. Spatial directional radiance caching. Computer Graphics Forum (EGSR 2009) 28, 4, 1189–1198. Google ScholarDigital Library
    15. Georgiev, I., and Slusallek, P. 2010. Simple and Robust Iterative Importance Sampling of Virtual Point Lights. Proceedings of Eurographics (short papers).Google Scholar
    16. Georgiev, I., Křivánek, J., Davidovič, T., and Slusallek, P. 2012. Light transport simulation with vertex connection and merging. ACM Trans. Graph. (SIGGRAPH Asia ’12) 31, 6. Google ScholarDigital Library
    17. Grassberger, P. 2002. Go with the winners: a general Monte Carlo strategy. In Comp. Phys. Commun., vol. 147, 64–70.Google ScholarCross Ref
    18. Hachisuka, T., Ogaki, S., and Jensen, H. W. 2008. Progressive photon mapping. ACM Trans. Graph. (SIGGRAPH Asia ’08) 27, 5 (Dec.). Google ScholarDigital Library
    19. Hachisuka, T., Pantaleoni, J., and Jensen, H. W. 2012. A path space extension for robust light transport simulation. ACM Trans. Graph. (SIGGRAPH Asia ’12) 31, 6. Google ScholarDigital Library
    20. Hammersley, J., and Handscomb, D. 1964. Monte Carlo Methods. Chapman and Hall, New York.Google Scholar
    21. Hey, H., and Purgathofer, W. 2002. Importance sampling with hemispherical particle footprints. In SCCG. Google ScholarDigital Library
    22. Hoogenboom, Eduard, J., and Légrády, D. 2005. A critical review of the weight window generator in MCNP. Monte Carlo 2005 Topical Meeting (Apr.).Google Scholar
    23. Hoogenboom, Eduard, J. 2008. Zero-variance Monte Carlo schemes revisited. Nucl. Sci. Eng. 160, 1–22.Google ScholarCross Ref
    24. Jakob, W., 2010. Mitsuba renderer. http://mitsuba-renderer.org.Google Scholar
    25. Jensen, H. W. 1995. Importance driven path tracing using the photon map. In Eurographics Workshop Rendering, 326–335.Google ScholarCross Ref
    26. Jensen, H. W. 1996. Global illumination using photon maps. In Proceedings of the Eurographics Workshop on Rendering Techniques ’96, Springer-Verlag, London, UK, UK, 21–30. Google ScholarDigital Library
    27. Jensen, H. W. 2001. Realistic Image Synthesis Using Photon Mapping. A. K. Peters, Ltd., Natick, MA, USA. Google ScholarDigital Library
    28. Kahn, H., and Harris, T., E. 1951. Estimation of particle transmission by random sampling. In Nat. Bur. of Stand. Appl. Math. Ser., vol. 12, 27–30.Google Scholar
    29. Kahn, H. 1956. Use of different Monte Carlo sampling techniques. In Symp. on Monte Carlo Methods, New York: Wiley.Google Scholar
    30. Kajiya, J. T. 1986. The rendering equation. SIGGRAPH Comput. Graph. 20, 4 (Aug.), 143–150. Google ScholarDigital Library
    31. Kalos, M. H. 1963. Importance sampling in Monte Carlo shielding calculations: I. neutron penetration through thick hydrogen slabs. In Nuclear Science and Engineering, vol. 16, 227–234.Google ScholarCross Ref
    32. Keller, A., and Wald, I. 2000. Efficient importance sampling techniques for the photon map. In Proc. Fifth Fall Workshop Vision, Modeling, and Visualisation, 271–279.Google Scholar
    33. Křivánek, J., Gautron, P., Pattanaik, S., and Bouatouch, K. 2005. Radiance caching for efficient global illumination computation. IEEE Trans. Vis. Comp. Graph. 11, 5. Google ScholarDigital Library
    34. Křivánek, J., Georgiev, I., Hachisuka, T., Vévoda, P., Šik, M., Nowrouzezahrai, D., and Jarosz, W. 2014. Unifying points, beams, and paths in volumetric light transport simulation. ACM Trans. Graph. 33, 4 (Aug.), 1–13. Google ScholarDigital Library
    35. Křivánek, J., Keller, A., Georgiev, I., Kaplanyan, A., Fajardo, M., Meyer, M., Nahmias, J.-D., Karlík, O., and Canada, J. 2014. Recent advances in light transport simulation: Some theory and a lot of practice. In ACM SIGGRAPH 2014 Courses, ACM, New York, NY, USA, SIGGRAPH ’14. Google ScholarDigital Library
    36. Křivánek, J., and d’Eon, E. 2014. A zero-variance-based sampling scheme for Monte Carlo subsurface scattering. In ACM SIGGRAPH 2014 Talks, ACM, New York, NY, USA. Google ScholarDigital Library
    37. Lehtinen, J., Karras, T., Laine, S., Aittala, M., Durand, F., and Aila, T. 2013. Gradient-domain metropolis light transport. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    38. Lux, I., and Koblinger, L. 1991. Monte Carlo particle transport methods: neutron and photon calculations. CRC Press.Google Scholar
    39. Meinl, F., 2010. Crytek sponza. http://www.crytek.com/cryengine/cryengine3/downloads.Google Scholar
    40. Popov, S., Ramamoorthi, R., Durand, F., and Drettakis, G. 2015. Probabilistic connections for bidirectional path tracing. Computer Graphics Forum (Proc. of EGSR) 34, 4. Google ScholarDigital Library
    41. Seymour, M., 2014. Manuka: Weta digital’s new renderer. http://www.fxguide.com/featured/manuka-weta-digitals-new-renderer/.Google Scholar
    42. Spanier, J., and Gelbard, Ely, M. 1969. Monte Carlo principles and neutron transport problems. Addison-Wesley.Google Scholar
    43. Suykens, F., and Willems, Y. D. 2000. Density control for photon maps. In Proceedings of the Eurographics Workshop on Rendering Techniques 2000, Springer-Verlag, London, UK. Google ScholarDigital Library
    44. Szécsi, L., Szirmay-Kalos, L., and Kelemen, C. 2003. Variance reduction for russian roulette. Journal of WSCG.Google Scholar
    45. Szirmay-Kalos, L., and Antal, G. 2005. Go with the winners strategy in path tracing. In Journal of WSCG., vol. 13.Google Scholar
    46. Veach, E. 1997. Robust Monte Carlo methods for light transport simulation. PhD thesis, Stanford University. Google ScholarDigital Library
    47. Vorba, J., Karlík, O., Šik, M., Ritschel, T., and Křivá nek, J. 2014. On-line learning of parametric mixture models for light transport simulation. ACM Trans. Graph. (SIGGRAPH ’14) 33, 4 (July). Google ScholarDigital Library
    48. Wagner, J., C., and Haghighat, A. 1998. Automated variance reduction of Monte Carlo shielding calculations using the discrete ordinates adjoint function. In Nulc. Sci. Eng., vol. 128.Google Scholar
    49. Wagner, J., C. 1997. Acceleration of Monte Carlo shielding calculations with an automated variance reduction technique and parallel processing. PhD thesis, The Pennsylvania State Univ.Google Scholar
    50. X-5 Monte Carlo team. 2003. MCNP — A general Monte Carlo N-particle transport code, version 5. Tech. Rep. LA-UR-03-1987, Los Alamos National Laboratory, Apr.Google Scholar
    51. Xu, Q., Sun, J., Wei, Z., Shu, Y., Messelodi, S., and Cai, J. 2001. Zero variance importance sampling driven potential tracing algorithm for global illumination. In Journal of WSCG. 2001, vol. 9.Google Scholar

ACM Digital Library Publication:

Overview Page: