“Hierarchical russian roulette for vertex connections” by Tokuyoshi and Harada

  • ©Yusuke Tokuyoshi and Takahiro Harada




    Hierarchical russian roulette for vertex connections

Session/Category Title:   Light Science



    While bidirectional path tracing is a well-established light transport algorithm, many samples are required to obtain high-quality results for specular-diffuse-glossy or glossy-diffuse-glossy reflections especially when they are highly glossy. To improve the efficiency for such light path configurations, we propose a hierarchical Russian roulette technique for vertex connections. Our technique accelerates a huge number of Russian roulette operations according to an approximate scattering lobe at an eye-subpath vertex for many cached light-subpath vertices. Our method dramatically reduces the number of random number generations needed for Russian roulette by introducing a hierarchical rejection algorithm which assigns random numbers in a top-down fashion. To efficiently reject light vertices in each hierarchy, we also introduce an efficient approximation of anisotropic scattering lobes used for the probability of Russian roulette. Our technique is easy to integrate into some existing bidirectional path tracing-based algorithms which cache light-subpath vertices (e.g., probabilistic connections, and vertex connection and merging). In addition, unlike existing many-light methods, our method does not restrict multiple importance sampling strategies thanks to the simplicity of Russian roulette. Although the proposed technique does not support perfectly specular surfaces, it significantly improves the efficiency for caustics reflected on extremely glossy surfaces in an unbiased fashion.


    1. J. Arvo and D. Kirk. 1990. Particle Transport and Image Synthesis. SIGGRAPH Comput. Graph. 24, 4 (1990), 63–66. Google ScholarDigital Library
    2. R. L. Cook and K. E. Torrance. 1982. A Reflectance Model for Computer Graphics. ACM Trans. Graph. 1, 1 (1982), 7–24. Google ScholarDigital Library
    3. C. Dachsbacher, J. Křivánek, M. Hašan, A. Arbree, B. Walter, and J. Novák. 2014. Scalable Realistic Rendering with Many-Light Methods. Comput. Graph. Forum 33, 1 (2014), 88–104. Google ScholarDigital Library
    4. C. Dachsbacher and M. Stamminger. 2006. Splatting Indirect Illumination. In I3D ’06. 93–100. Google ScholarDigital Library
    5. T. Davidovič, J. Křivánek, M. Hašan, and P. Slusallek. 2014. Progressive Light Transport Simulation on the GPU: Survey and Improvements. ACM Trans. Graph. 33, 3 (2014), 29:1–29:19. Google ScholarDigital Library
    6. A. C. Estevez and C. Kulla. 2018. Importance Sampling of Many Lights with Adaptive Tree Splitting. Proc. ACM Comput. Graph. Interact. Tech. 1, 2 (2018), 25:1–25:17. Google ScholarDigital Library
    7. A. C. Estevez and P. Lecocq. 2018. Fast Product Importance Sampling of Environment Maps. In SIGGRAPH ’18 Talks. 69:1–69:2. Google ScholarDigital Library
    8. I. Georgiev. 2013. Combining Photon Mapping and Bidirectional Path Tracing. In SIGGRAPH Asia ’13 Course: State of the Art in Photon Density Estimation. 15:475–15:515.Google Scholar
    9. I. Georgiev, J. Křivánek, T. Davidovič, and P. Slusallek. 2012a. Light Transport Simulation with Vertex Connection and Merging. ACM Trans. Graph. 31, 6 (2012), 192:1–192:10. Google ScholarDigital Library
    10. I. Georgiev, J. Křivánek, S. Popov, and P. Slusallek. 2012b. Importance Caching for Complex Illumination. Comput. Graph. Forum 31, 2pt3 (2012), 701–710. Google ScholarDigital Library
    11. T. Hachisuka, S. Ogaki, and H. W. Jensen. 2008. Progressive Photon Mapping. ACM Trans. Graph. 27, 5 (2008), 130:1–130:8. Google ScholarDigital Library
    12. T. Hachisuka, J. Pantaleoni, and H. W. Jensen. 2012. A Path Space Extension for Robust Light Transport Simulation. ACM Trans. Graph. 31, 6 (2012), 191:1–191:10. Google ScholarDigital Library
    13. S. Herholz, O. Elek, J. Schindel, J. Křivánek, and H. P. A. Lensch. 2018. A Unified Manifold Framework for Efficient BRDF Sampling Based on Parametric Mixture Models. In EGSR ’18 EI&I. 41–52. Google ScholarDigital Library
    14. S. Herholz, O. Elek, J. Vorba, H. Lensch, and J. Křivánek. 2016. Product Importance Sampling for Light Transport Path Guiding. Comput. Graph. Forum 35, 4 (2016), 67–77. Google ScholarDigital Library
    15. H. Igehy. 1999. Tracing Ray Differentials. In SIGGRAPH ’99. 179–186. Google ScholarDigital Library
    16. J. Jendersie. 2019. Variance Reduction via Footprint Estimation in the Presence of Path Reuse. In Ray Tracing Gems: High-Quality and Real-Time Rendering with DXR and Other APIs. Apress, 557–569.Google Scholar
    17. A. Keller. 1997. Instant Radiosity. In SIGGRAPH ’97. 49–56. Google ScholarDigital Library
    18. C. Knaus and M. Zwicker. 2011. Progressive Photon Mapping: A Probabilistic Approach. ACM Trans. Graph. 30, 3 (2011), 25:1–25:13. Google ScholarDigital Library
    19. T. Kollig and A. Keller. 2006. Illumination in the Presence of Weak Singularities. In MCQMC ’04. 245–257.Google Scholar
    20. E. P. Lafortune and Y. D. Willems. 1993. Bi-Directional Path Tracing. In Compugraphics ’93. 145–153.Google Scholar
    21. O. Olsson, M. Billeter, and E. Persson. 2014. Efficient Real-Time Shading with Many Lights. In SIGGRAPH Asia ’14 Courses. 11:1–11:310. Google ScholarDigital Library
    22. B. T. Phong. 1975. Illumination for Computer Generated Pictures. Commun. ACM 18, 6 (1975), 311–317. Google ScholarDigital Library
    23. S. Popov, R. Ramamoorthi, F. Durand, and G. Drettakis. 2015. Probabilistic Connections for Bidirectional Path Tracing. Comput. Graph. Forum 34, 4 (2015), 75–86. Google ScholarDigital Library
    24. J. Stewart. 2015. Compute-Based Tiled Culling. In GPU Pro 6: Advanced Rendering Techniques. A K Peters/CRC Press, 435–458.Google Scholar
    25. Y. Tokuyoshi and T. Harada. 2016. Stochastic Light Culling. J. Comput. Graph. Tech. 5, 1 (2016), 35–60.Google Scholar
    26. Y. Tokuyoshi and T. Harada. 2017. Stochastic Light Culling for VPLs on GGX Microsurfaces. Comput. Graph. Forum 36, 4 (2017), 55–63. Google ScholarDigital Library
    27. Y. Tokuyoshi and T. Harada. 2018. Bidirectional Path Tracing Using Backward Stochastic Light Culling. In SIGGRAPH ’18 Talks. 70:1–70:2. Google ScholarDigital Library
    28. T. S. Trowbridge and K. P. Reitz. 1975. Average Irregularity Representation of a Rough Surface for Ray Reflection. J. Opt. Soc. Am. 65, 5 (1975), 531–536.Google ScholarCross Ref
    29. E. Veach. 1998. Robust Monte Carlo Methods for Light Transport Simulation. Ph.D. Dissertation. Google ScholarDigital Library
    30. E. Veach and L. Guibas. 1994. Bidirectional Estimators for Light Transport. In EGWR ’94. 147–162.Google Scholar
    31. E. Veach and L. J. Guibas. 1995. Optimally Combining Sampling Techniques for Monte Carlo Rendering. In SIGGRAPH ’95. 419–428. Google ScholarDigital Library
    32. J. Vorba, O. Karlik, M. Šik, T. Ritschel, and J. Křivánek. 2014. On-line Learning of Parametric Mixture Models for Light Transport Simulation. ACM Trans. Graph. 33, 4 (2014), 101:1–101:11. Google ScholarDigital Library
    33. B. Walter, A. Arbree, K. Bala, and D. P. Greenberg. 2006. Multidimensional Lightcuts. ACM Trans. Graph. 25, 3 (2006), 1081–1088. Google ScholarDigital Library
    34. B. Walter, S. Fernandez, A. Arbree, K. Bala, M. Donikian, and D. P. Greenberg. 2005. Lightcuts: A Scalable Approach to Illumination. ACM Trans. Graph. 24, 3 (2005), 1098–1107. Google ScholarDigital Library
    35. B. Walter, P. Khungurn, and K. Bala. 2012. Bidirectional Lightcuts. ACM Trans. Graph. 31, 4 (2012), 59:1–59:11. Google ScholarDigital Library
    36. B. Walter, S. R. Marschner, H. Li, and K. E. Torrance. 2007. Microfacet Models for Refraction Through Rough Surfaces. In EGSR ’07. 195–206. Google ScholarDigital Library
    37. J. Wang, P. Ren, M. Gong, J. Snyder, and B. Guo. 2009. All-Frequency Rendering of Dynamic, Spatially-Varying Reflectance. ACM Trans. Graph. 28, 5 (2009), 133:1–133:10. Google ScholarDigital Library
    38. K. Xu, W.-L. Sun, Z. Dong, D.-Y. Zhao, R.-D. Wu, and S.-M. Hu. 2013. Anisotropic Spherical Gaussians. ACM Trans. Graph. 32, 6 (2013), 209:1–209:11. Google ScholarDigital Library
    39. T. Zirr, J. Hanika, and C. Dachsbacher. 2018. Reweighting Firefly Samples for Improved Finite-Sample Monte Carlo Estimates. Comput. Graph. Forum 37, 6 (2018), 410–421.Google ScholarCross Ref

ACM Digital Library Publication:

Overview Page: