“Generalized resampled importance sampling: foundations of ReSTIR” by Lin, Kettunen, Bitterli, Pantaleoni, Yuksel, et al. …

  • ©Daqi Lin, Markus Kettunen, Benedikt Bitterli, Jacopo Pantaleoni, Cem Yuksel, and Chris Wyman




    Generalized resampled importance sampling: foundations of ReSTIR



    As scenes become ever more complex and real-time applications embrace ray tracing, path sampling algorithms that maximize quality at low sample counts become vital. Recent resampling algorithms building on Talbot et al.’s [2005] resampled importance sampling (RIS) reuse paths spatiotemporally to render surprisingly complex light transport with a few samples per pixel. These reservoir-based spatiotemporal importance resamplers (ReSTIR) and their underlying RIS theory make various assumptions, including sample independence. But sample reuse introduces correlation, so ReSTIR-style iterative reuse loses most convergence guarantees that RIS theoretically provides.We introduce generalized resampled importance sampling (GRIS) to extend the theory, allowing RIS on correlated samples, with unknown PDFs and taken from varied domains. This solidifies the theoretical foundation, allowing us to derive variance bounds and convergence conditions in ReSTIR-based samplers. It also guides practical algorithm design and enables advanced path reuse between pixels via complex shift mappings.We show a path-traced resampler (ReSTIR PT) running interactively on complex scenes, capturing many-bounce diffuse and specular lighting while shading just one path per pixel. With our new theoretical foundation, we can also modify the algorithm to guarantee convergence for offline renderers.


    1. Pablo Bauszat, Victor Petitjean, and Elmar Eisemann. 2017. Gradient-Domain Path Reusing. ACM Trans. Graph. 36, 6, Article 229 (nov 2017), 9 pages. Google ScholarDigital Library
    2. Philippe Bekaert, Mateu Sbert, and John H Halton. 2002. Accelerating Path Tracing by Re-Using Paths.. In Rendering Techniques. 125–134.Google Scholar
    3. Nikolaus Binder, Sascha Fricke, and Alexander Keller. 2019. Massively parallel path space filtering. arXiv preprint arXiv:1902.05942 (2019).Google Scholar
    4. Benedikt Bitterli. 2021. Correlations and reuse for fast and accurate physically based light transport. Ph.D. Dissertation. Dartmouth College. http://benedikt-bitterli.me/Data/dissertation.pdfGoogle Scholar
    5. Benedikt Bitterli, Wenzel Jakob, Jan Novák, and Wojciech Jarosz. 2017. Reversible jump Metropolis light transport using inverse mappings. ACM Transactions on Graphics (TOG) 37, 1 (2017), 1–12.Google ScholarDigital Library
    6. Benedikt Bitterli, Chris Wyman, Matt Pharr, Peter Shirley, Aaron Lefohn, and Wojciech Jarosz. 2020. Spatiotemporal reservoir resampling for real-time ray tracing with dynamic direct lighting. ACM Transactions on Graphics (TOG) 39, 4 (2020), 148–1.Google ScholarDigital Library
    7. Guillaume Boissé. 2021. World-Space Spatiotemporal Reservoir Reuse for Ray-Traced Global Illumination. In SIGGRAPH Asia 2021 Technical Communications (Tokyo, Japan) (SA ’21 Technical Communications). Association for Computing Machinery, New York, NY, USA, Article 22, 4 pages. Google ScholarDigital Library
    8. Jakub Boksansky, Paula Jukarainen, and Chris Wyman. 2021. Rendering Many Lights with Grid-Based Reservoirs. In Ray Tracing Gems II. Springer, 351–365.Google Scholar
    9. Olivier Cappé, Arnaud Guillin, Jean-Michel Marin, and Christian P Robert. 2004. Population monte carlo. Journal of Computational and Graphical Statistics 13, 4 (2004), 907–929.Google ScholarCross Ref
    10. Chakravarty R. Alla Chaitanya, Laurent Belcour, Toshiya Hachisuka, Simon Premoze, Jacopo Pantaleoni, and Derek Nowrouzezahrai. 2018. Matrix Bidirectional Path Tracing. In Proceedings of the Eurographics Symposium on Rendering: Experimental Ideas & Implementations (Karlsruhe, Germany) (SR ’18). Eurographics Association, Goslar, DEU, 23–32. Google ScholarDigital Library
    11. Chakravarty R. Alla Chaitanya, Anton S. Kaplanyan, Christoph Schied, Marco Salvi, Aaron Lefohn, Derek Nowrouzezahrai, and Timo Aila. 2017. Interactive Reconstruction of Monte Carlo Image Sequences Using a Recurrent Denoising Autoencoder. ACM Trans. Graph. 36, 4, Article 98 (jul 2017), 12 pages. Google ScholarDigital Library
    12. Min-Te Chao. 1982. A general purpose unequal probability sampling plan. Biometrika 69, 3 (1982), 653–656. Google ScholarCross Ref
    13. Michael Donikian, Bruce Walter, Kavita Bala, Sebastian Fernandez, and Donald P. Greenberg. 2006. Accurate Direct Illumination Using Iterative Adaptive Sampling. IEEE Transactions on Visualization and Computer Graphics 12, 3 (may 2006), 353–364. Google ScholarDigital Library
    14. Michaël Gharbi, Tzu-Mao Li, Miika Aittala, Jaakko Lehtinen, and Frédo Durand. 2019. Sample-Based Monte Carlo Denoising Using a Kernel-Splatting Network. ACM Trans. Graph. 38, 4, Article 125 (jul 2019), 12 pages. Google ScholarDigital Library
    15. Abhijeet Ghosh, Arnaud Doucet, and Wolfgang Heidrich. 2006. Sequential Sampling for Dynamic Environment Map Illumination. In Symposium on Rendering, Tomas Akenine-Moeller and Wolfgang Heidrich (Eds.). The Eurographics Association. Google ScholarCross Ref
    16. Adrien Gruson, Binh-Son Hua, Nicolas Vibert, Derek Nowrouzezahrai, and Toshiya Hachisuka. 2018. Gradient-domain volumetric photon density estimation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.Google ScholarDigital Library
    17. Adam Guetz. 2012. Monte Carlo Methods for Structured Data. Stanford University.Google Scholar
    18. Henrik Halen, Andreas Brinck, Kyle Hayward, and Xiangshun Bei. 2021. Global Illumination Based on Surfels. In SIGGRAPH Courses; Advances in Real-Time Rendering.Google Scholar
    19. Jon Hasselgren, Jacob Munkberg, Marco Salvi, Anjul Patney, and Aaron Lefohn. 2020. Neural Temporal Adaptive Sampling and Denoising. Computer Graphics Forum (2020). Google ScholarCross Ref
    20. Paul S Heckbert. 1990. Adaptive radiosity textures for bidirectional ray tracing. In Proceedings of the 17th annual conference on Computer graphics and interactive techniques. 145–154.Google ScholarDigital Library
    21. E. Heitz and L. Belcour. 2019. Distributing Monte Carlo Errors as a Blue Noise in Screen Space by Permuting Pixel Seeds Between Frames. Computer Graphics Forum 38, 4 (2019), 149–158. Google ScholarCross Ref
    22. Eric Heitz, Stephen Hill, and Morgan McGuire. 2018. Combining Analytic Direct Illumination and Stochastic Shadows. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. Association for Computing Machinery, New York, NY, USA, Article 2, 11 pages. Google ScholarDigital Library
    23. Binh-Son Hua, Adrien Gruson, Derek Nowrouzezahrai, and Toshiya Hachisuka. 2017. Gradient-domain photon density estimation. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 31–38.Google Scholar
    24. Binh-Son Hua, Adrien Gruson, Victor Petitjean, Matthias Zwicker, Derek Nowrouzezahrai, Elmar Eisemann, and Toshiya Hachisuka. 2019. A Survey on Gradient-Domain Rendering. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 455–472.Google Scholar
    25. Wenzel Jakob and Steve Marschner. 2012. Manifold exploration: A markov chain monte carlo technique for rendering scenes with difficult specular transport. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–13.Google ScholarDigital Library
    26. Henrik Wann Jensen. 2001. Realistic Image Synthesis Using Photon Mapping. A. K. Peters, Ltd., USA.Google ScholarDigital Library
    27. Simon Kallweit, Petrik Clarberg, Craig Kolb, Kai-Hwa Yao, Theresa Foley, Yong He, Lifan Wu, Lucy Chen, Tomas Akenine-Moller, Chris Wyman, Cyril Crassin, and Nir Benty. 2021. The Falcor Rendering Framework. https://github.com/NVIDIAGameWorks/Falcor https://github.com/NVIDIAGameWorks/Falcor.Google Scholar
    28. Csaba Kelemen, László Szirmay-Kalos, György Antal, and Ferenc Csonka. 2002. A Simple and Robust Mutation Strategy for the Metropolis Light Transport Algorithm. Computer Graphics Forum 21, 3 (2002), 531–540. Google ScholarCross Ref
    29. Markus Kettunen. 2020. Gradient-Domain Methods for Realistic Image Synthesis. Ph.D. Dissertation. Aalto University.Google Scholar
    30. Markus Kettunen, Marco Manzi, Miika Aittala, Jaakko Lehtinen, Frédo Durand, and Matthias Zwicker. 2015. Gradient-domain path tracing. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–13.Google ScholarDigital Library
    31. Emmett Kilgariff, Henry Moreton, Nick Stam, and Brandon Bell. 2018. NVIDIA Turing Architecture In-Depth. https://developer.nvidia.com/blog/nvidia-turing-architecture-in-depth/. [Online; accessed 9-December-2021].Google Scholar
    32. Eric P. Lafortune and Yves D. Willems. 1993. Bi-Directional Path Tracing. In Proc. the International Conference on Computational Graphics and Visualization Techniques, Vol. 93. 145–153.Google Scholar
    33. Yu-Chi Lai, Shao Hua Fan, Stephen Chenney, and Charcle Dyer. 2007. Photorealistic image rendering with population monte carlo energy redistribution. In Proceedings of the 18th Eurographics conference on Rendering Techniques. 287–295.Google ScholarDigital Library
    34. Jaakko Lehtinen, Tero Karras, Samuli Laine, Miika Aittala, Frédo Durand, and Timo Aila. 2013. Gradient-domain metropolis light transport. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–12.Google ScholarDigital Library
    35. Faming Liang and Sooyoung Cheon. 2009. Monte Carlo dynamically weighted importance sampling for spatial models with intractable normalizing constants. 197 (dec 2009), 012004. Google ScholarCross Ref
    36. Daqi Lin, Chris Wyman, and Cem Yuksel. 2021. Fast Volume Rendering with Spatiotemporal Reservoir Resampling. ACM Transactions on Graphics (TOG) 40, 6 (2021), to appear.Google ScholarDigital Library
    37. Jun S Liu and Jun S Liu. 2001. Monte Carlo strategies in scientific computing. Vol. 10. Springer, 36–37.Google ScholarDigital Library
    38. Marco Manzi, Markus Kettunen, Miika Aittala, Jaakko Lehtinen, Frédo Durand, and Matthias Zwicker. 2015. Gradient-domain bidirectional path tracing. (2015).Google Scholar
    39. Marco Manzi, Markus Kettunen, Frédo Durand, Matthias Zwicker, and Jaakko Lehtinen. 2016. Temporal gradient-domain path tracing. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–9.Google ScholarDigital Library
    40. Marco Manzi, Fabrice Rousselle, Markus Kettunen, Jaakko Lehtinen, and Matthias Zwicker. 2014. Improved sampling for gradient-domain metropolis light transport. ACM Transactions on Graphics (TOG) 33, 6 (2014), 1–12.Google ScholarDigital Library
    41. Pierre Moreau, Matt Pharr, and Petrik Clarberg. 2019. Dynamic Many-Light Sampling for Real-Time Ray Tracing. In High-Performance Graphics – Short Papers, Markus Steinberger and T. Foley (Eds.). The Eurographics Association. Google ScholarDigital Library
    42. Thomas Müller, Brian Mcwilliams, Fabrice Rousselle, Markus Gross, and Jan Novák. 2019. Neural Importance Sampling. ACM Trans. Graph. 38, 5, Article 145 (oct 2019), 19 pages. Google ScholarDigital Library
    43. Thomas Müller, Markus Gross, and Jan Novák. 2017. Practical Path Guiding for Efficient Light-Transport Simulation. Computer Graphics Forum 36, 4 (2017), 91–100. Google ScholarDigital Library
    44. Kosuke Nabata, Kei Iwasaki, and Yoshinori Dobashi. 2020. Resampling-Aware Weighting Functions for Bidirectional Path Tracing Using Multiple Light Sub-Paths. ACM Trans. Graph. 39, 2, Article 15 (mar 2020), 11 pages. Google ScholarDigital Library
    45. Yaobin Ouyang, Shiqiu Liu, Markus Kettunen, Matt Pharr, and Jacopo Pantaleoni. 2021. ReSTIR GI: Path Resampling for Real-Time Path Tracing. Computer Graphics Forum 40, 8 (2021), 17–29. Google ScholarCross Ref
    46. Jacopo Pantaleoni. 2020. Online Path Sampling Control with Progressive Spatiotemporal Filtering. SN Computer Science 279 (aug 2020).Google Scholar
    47. Christoph Peters. 2021. BRDF Importance Sampling for Polygonal Lights. ACM Trans. Graph. 40, 4, Article 140 (jul 2021), 14 pages. Google ScholarDigital Library
    48. Victor Petitjean, Pablo Bauszat, and Elmar Eisemann. 2018. Spectral Gradient Sampling for Path Tracing. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 45–53.Google Scholar
    49. Stefan Popov, Ravi Ramamoorthi, Fredo Durand, and George Drettakis. 2015. Probabilistic Connections for Bidirectional Path Tracing. Comput. Graph. Forum 34, 4 (jul 2015), 75–86.Google Scholar
    50. DB Rubin. 1987. A Noniterative Sampling/Importance resampling alternative to data augmentation for creating a few imputations when fractions of missing information are modest: The SIR algorithm. J. Amer. Statist. Assoc. 82 (1987), 544–546.Google ScholarCross Ref
    51. Christoph Schied, Christoph Peters, and Carsten Dachsbacher. 2018. Gradient Estimation for Real-Time Adaptive Temporal Filtering. Proc. ACM Comput. Graph. Interact. Tech. 1, 2, Article 24 (2018). Google ScholarDigital Library
    52. Peter Shirley, Changyaw Wang, and Kurt Zimmerman. 1996. Monte Carlo Techniques for Direct Lighting Calculations. ACM Trans. Graph. 15, 1 (jan 1996), 1–36. Google ScholarDigital Library
    53. Tomasz Stachowiak. 2015. Stochastic Screen-Space Reflections. In Advances in Real Time Rendering, (ACM SIGGRAPH Courses). Google ScholarDigital Library
    54. Weilun Sun, Xin Sun, Nathan A Carr, Derek Nowrouzezahrai, and Ravi Ramamoorthi. 2017. Gradient-Domain Vertex Connection and Merging.. In EGSR (EI&I). 83–92.Google Scholar
    55. László Szésci, László Szirmay-Kalos, and Csaba Kelemen. 2003. Variance reduction for Russian-roulette. (2003).Google Scholar
    56. Justin Talbot, David Cline, and Parris Egbert. 2005. Importance Resampling for Global Illumination. In Eurographics Symposium on Rendering (2005), Kavita Bala and Philip Dutre (Eds.). The Eurographics Association. Google ScholarCross Ref
    57. Justin F Talbot. 2005. Importance resampling for global illumination. Brigham Young University.Google Scholar
    58. Lorenzo Tessari, Johannes Hanika, and Carsten Dachsbacher. 2017. Local quasi-monte carlo exploration. In Proceedings of the Eurographics Symposium on Rendering: Experimental Ideas & Implementations. 71–81.Google ScholarDigital Library
    59. Yusuke Tokuyoshi and Takahiro Harada. 2019. Hierarchical Russian Roulette for Vertex Connections. ACM Trans. Graph. 38, 4, Article 36 (jul 2019), 12 pages. Google ScholarDigital Library
    60. Joran Van de Woestijne, Roald Frederickx, Niels Billen, and Philip Dutré. 2017. Temporal coherence for metropolis light transport. In Eurographics Symposium on Rendering-Experimental Ideas & Implementations. Eurographics Association, 55–63.Google Scholar
    61. Eric Veach. 1998. Robust Monte Carlo methods for light transport simulation. Stanford University.Google ScholarDigital Library
    62. Eric Veach and Leonidas J. Guibas. 1997. Metropolis Light Transport. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. USA, 65–76. Google ScholarDigital Library
    63. Petr Vévoda, Ivo Kondapaneni, and Jaroslav Křivánek. 2018. Bayesian Online Regression for Adaptive Direct Illumination Sampling. ACM Trans. Graph. 37, 4, Article 125 (jul 2018), 12 pages. Google ScholarDigital Library
    64. Jiří Vorba, Johannes Hanika, Sebastian Herholz, Thomas Müller, Jaroslav Křivánek, and Alexander Keller. 2019. Path Guiding in Production. In ACM SIGGRAPH 2019 Courses (Los Angeles, California) (SIGGRAPH ’19). ACM, New York, NY, USA, Article 18, 77 pages. Google ScholarDigital Library
    65. Jiří Vorba, Ondřej Karlík, Martin Šik, Tobias Ritschel, and Jaroslav Křivánek. 2014. On-line learning of parametric mixture models for light transport simulation. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–11.Google ScholarDigital Library
    66. Bruce Walter, Sebastian Fernandez, Adam Arbree, Kavita Bala, Michael Donikian, and Donald P. Greenberg. 2005. Lightcuts: A Scalable Approach to Illumination. 24, 3 (jul 2005), 1098–1107. Google ScholarDigital Library
    67. Bruce Walter, Stephen R Marschner, Hongsong Li, and Kenneth E Torrance. 2007. Microfacet Models for Refraction through Rough Surfaces. Rendering techniques 2007 (2007), 18th.Google Scholar
    68. Rex West, Iliyan Georgiev, Adrien Gruson, and Toshiya Hachisuka. 2020. Continuous multiple importance sampling. ACM Transactions on Graphics (TOG) 39, 4 (2020), 136–1.Google ScholarDigital Library
    69. Chris Wyman and Alexey Panteleev. 2021. Rearchitecting Spatiotemporal Resampling for Production. In ACM/EG Symposium on High Perfrormance Graphics. 23–41. Google ScholarDigital Library
    70. Junqiu Zhu, Yaoyi Bai, Zilin Xu, Steve Bako, Edgar Velázquez-Armendáriz, Lu Wang, Pradeep Sen, Miloš Hašan, and Ling-Qi Yan. 2021. Neural Complex Luminaires: Representation and Rendering. ACM Trans. Graph. 40, 4, Article 57 (jul 2021), 12 pages. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: