“Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions” by Sawhney, Miller, Gkioulekas and Crane
Conference:
Type(s):
Title:
- Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions
Session/Category Title: Pushing the Boundaries
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Grid-free Monte Carlo methods based on the walk on spheres (WoS) algorithm solve fundamental partial differential equations (PDEs) like the Poisson equation without discretizing the problem domain or approximating functions in a finite basis. Such methods hence avoid aliasing in the solution, and evade the many challenges of mesh generation. Yet for problems with complex geometry, practical grid-free methods have been largely limited to basic Dirichlet boundary conditions. We introduce the walk on stars (WoSt) algorithm, which solves linear elliptic PDEs with arbitrary mixed Neumann and Dirichlet boundary conditions. The key insight is that one can efficiently simulate reflecting Brownian motion (which models Neumann conditions) by replacing the balls used by WoS with star-shaped domains. We identify such domains via the closest point on the visibility silhouette, by simply augmenting a standard bounding volume hierarchy with normal information. Overall, WoSt is an easy modification of WoS, and retains the many attractive features of grid-free Monte Carlo methods such as progressive and view-dependent evaluation, trivial parallelization, and sublinear scaling to increasing geometric detail.
References:
1. Gavin Barill, Neil G. Dickson, Ryan Schmidt, David I. W. Levin, and Alec Jacobson. 2018. Fast Winding Numbers for Soups and Clouds. ACM Trans. Graph. 37, 4, Article 43 (2018), 12 pages.
2. Mégane Bati, Stéphane Blanco, Christophe Coustet, Vincent Eymet, Vincent Forest, Richard Fournier, Jacques Gautrais, Nicolas Mellado, Mathias Paulin, and Benjamin Piaud. 2023. Coupling Conduction, Convection and Radiative Transfer in a Single Path-Space: Application to Infrared Rendering. ACM Trans. Graph. 42, 4 (aug 2023).
3. Ilia Binder and Mark Braverman. 2012. The rate of convergence of the walk on spheres algorithm. Geometric and Functional Analysis 22, 3 (2012), 558–587.
4. 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 Trans. Graph. 39, 4, Article 148 (2020), 17 pages.
5. Andrei N Borodin and Paavo Salminen. 2015. Handbook of Brownian motion-facts and formulae. Springer Science & Business Media.
6. Barbara Busnello, Franco Flandoli, and Marco Romito. 2005. A probabilistic representation for the vorticity of a three-dimensional viscous fluid and for general systems of parabolic equations. Proc. Edinburgh Math. Soc. 48, 2 (2005), 295–336.
7. 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 (2017).
8. Tony F Chan and Tarek P Mathew. 1994. Domain decomposition algorithms. Acta numerica 3 (1994), 61–143.
9. Peter Yichen Chen, Jonathan David Blutinger, Yorán Meijers, Changxi Zheng, Eitan Grinspun, and Hod Lipson. 2019. Visual modeling of laser-induced dough browning. Journal of Food Engineering 243 (2019), 9–21.
10. Chris J Coleman, David L Tullock, and Nhan Phan-Thien. 1991. An effective boundary element method for inhomogeneous PDEs. J. App. Math. Phys. (ZAMP) 42, 5 (1991).
11. Robert L. Cook, Thomas Porter, and Loren Carpenter. 1984. Distributed Ray Tracing. In Proc. SIGGRAPH. 137–145.
12. Martin Costabel. 1987. Principles of boundary element methods. Computer Physics Reports 6, 1–6 (1987), 243–274.
13. Cristina Costantini, Barbara Pacchiarotti, and Flavio Sartoretto. 1998. Numerical Approximation for Functionals of Reflecting Diffusion Processes. SIAM J. Appl. Math. 58, 1 (1998), 73–102.
14. Carsten Dachsbacher, Jaroslav Křivánek, Miloš Hašan, Adam Arbree, Bruce Walter, and Jan Novák. 2014. Scalable realistic rendering with many-light methods. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 88–104.
15. Cuiyang Ding, Changhao Yan, Xuan Zeng, and Wei Cai. 2022. A Parallel Iterative Probabilistic Method for Mixed Problems of Laplace Equations with the Feynman-Kac Formula of Killed Brownian Motions. SIAM J. Sci. Comp. 44, 5 (2022).
16. Dean G Duffy. 2015. Green’s functions with applications. Chapman and Hall/CRC.
17. Sergey M Ermakov and Alexander S Sipin. 2009. The “walk in hemispheres” process and its applications to solving boundary value problems. Vestnik St. Petersburg University: Mathematics 42 (2009), 155–163. Issue 3.
18. Alejandro Conty Estevez and Christopher Kulla. 2018. Importance Sampling of Many Lights with Adaptive Tree Splitting. 1, 2 (Aug. 2018), 25:1–25:17.
19. Lawrence C Evans. 1998. Partial differential equations. Vol. 19. Rhode Island, USA.
20. Nicole Feng, Mark Gillespie, and Keenan Crane. 2023. Winding Numbers on Discrete Surfaces. ACM Trans. Graph. (2023).
21. George Fishman. 2006. Monte Carlo: concepts, algorithms, and applications. Springer Science & Business Media.
22. Pau Gargallo, Emmanuel Prados, and Peter Sturm. 2007. Minimizing the reprojection error in surface reconstruction from images. In IEEE Int. Conf. Comp. Vis. 1–8.
23. 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.
24. Michael B Giles. 2015. Multilevel monte carlo methods. Acta numerica 24 (2015), 259–328.
25. Denis S Grebenkov. 2006. Partially reflected Brownian motion: a stochastic approach to transport phenomena. arXiv preprint math/0610080 (2006).
26. Denis S Grebenkov. 2007. NMR survey of reflected Brownian motion. Reviews of Modern Physics 79, 3 (2007), 1077.
27. Karl Gustafson and Takehisa Abe. 1998. The third boundary condition—was it Robin’s? The Mathematical Intelligencer 20, 1 (1998), 63–71.
28. Toshiya Hachisuka and Henrik Wann Jensen. 2009. Stochastic Progressive Photon Mapping. ACM Trans. Graph. 28, 5 (dec 2009), 1–8.
29. Toshiya Hachisuka, Shinji Ogaki, and Henrik Wann Jensen. 2008. Progressive Photon Mapping. ACM Trans. Graph. 27, 5, Article 130 (2008), 8 pages.
30. Wolfgang Hackbusch. 2015. Hierarchical matrices: algorithms and analysis. Vol. 49. Springer.
31. David W Hahn and M Necati Özisik. 2012. Heat conduction. John Wiley & Sons.
32. Guillermo Hansen, Irmina Herburt, Horst Martini, and Maria Moszyńska. 2020. Star-shaped sets. Aequationes mathematicae 94, 6 (2020), 1001–1092.
33. John C Hart. 1996. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 10 (1996), 527–545.
34. Eric Heitz, Jonathan Dupuy, Cyril Crassin, and Carsten Dachsbacher. 2015. The SGGX Microflake Distribution. ACM Trans. Graph. 34, 4, Article 48 (2015), 11 pages.
35. Sebastian Herholz, Yangyang Zhao, Oskar Elek, Derek Nowrouzezahrai, Hendrik P A Lensch, and Jaroslav Křivánek. 2019. Volume Path Guiding Based on Zero-Variance Random Walk Theory. ACM Trans. Graph. 38, 3, Article 25 (2019), 19 pages.
36. Desmond J Higham. 2001. An algorithmic introduction to numerical simulation of stochastic differential equations. SIAM review 43, 3 (2001), 525–546.
37. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast Tetrahedral Meshing in the Wild. ACM Trans. Graph. 39, 4 (2020), 18 pages.
38. Peter Hunter and Andrew Pullan. 2001. Fem/bem notes. Department of Engineering Science, The University of Auckland, New Zeland (2001).
39. Derek B Ingham and Mark A Kelmanson. 2012. Boundary integral equation analyses of singular, potential, and biharmonic problems. Vol. 7. Springer Sci. Bus. Med.
40. Intel. 2013. Embree: High Performance Ray Tracing Kernels. http://embree.github.io/
41. Kurt Jacobs. 2010. Stochastic processes for physicists: understanding noisy systems. Cambridge University Press.
42. David E Johnson and Elaine Cohen. 2001. Spatialized normal come hierarchies. In Proceedings of the 2001 symposium on Interactive 3D graphics. 129–134.
43. Malvin H Kalos and Paula A Whitlock. 2009. Monte carlo methods. John Wiley & Sons.
44. 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. In Computer Graphics Forum, Vol. 21. Wiley Online Library, 531–540.
45. Alexander Keller. 1997. Instant radiosity. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 49–56.
46. Pawel Kozlowski and Tim Cheblokov. 2021. ReLAX: A Denoiser Tailored to Work with the ReSTIR Algorithm. GPU Technology Conference (2021).
47. Bastian Krayer and Stefan Müller. 2021. Hierarchical Point Distance Fields. In International Symposium on Visual Computing. Springer, 435–446.
48. Eric P Lafortune and Yves D Willems. 1993. Bi-directional path tracing. In Proc. Int. Conf. Comp. Graph. Vis. Tech. Alvor, Portugal.
49. Tzu-Mao Li, Miika Aittala, Frédo Durand, and Jaakko Lehtinen. 2018. Differentiable Monte Carlo Ray Tracing through Edge Sampling. ACM Trans. Graph. 37, 6 (2018).
50. Sylvain Maire and Etienne Tanré. 2013. Monte Carlo approximations of the Neumann problem. Monte Carlo Methods and Applications 19, 3 (2013), 201–236.
51. Michael Mascagni and Nikolai A Simonov. 2004. Monte Carlo Methods for Calculating Some Physical Properties of Large Molecules. SIAM J. Sci. Comp. 26, 1 (2004).
52. Bailey Miller, Rohan Sawhney, Keenan Crane, and Ioannis Gkioulekas. 2023. Boundary Value Caching for Walk on Spheres. ACM Trans. Graph. 42, 4 (2023).
53. Zackary Misso, Benedikt Bitterli, Iliyan Georgiev, and Wojciech Jarosz. 2022. Unbiased and Consistent Rendering Using Biased Estimators. ACM Trans. Graph. 41, 4 (2022).
54. Linus Mossberg. 2021. GPU-Accelerated Monte Carlo Geometry Processing for GradientDomain Methods. Ph. D. Dissertation. Linköping University, Linköping, Sweden.
55. Mervin E Muller. 1956. Some Continuous Monte Carlo Methods for the Dirichlet Problem. Annals of Mathematical Statistics 27, 3 (Sept. 1956), 569–589.
56. Thomas Müller, Markus Gross, and Jan Novák. 2017. Practical path guiding for efficient light-transport simulation. In Comp. Graph. Forum, Vol. 36. Wiley Online Library.
57. Thomas Müller, Brian Mcwilliams, Fabrice Rousselle, Markus Gross, and Jan Novák. 2019. Neural Importance Sampling. ACM Trans. Graph. 38, 5 (2019).
58. Thomas Müller, Fabrice Rousselle, Alexander Keller, and Jan Novák. 2020. Neural Control Variates. ACM Trans. Graph. 39, 6 (2020).
59. Nathan Myhrvold and Francisco J Migoya. 2017. Modernist bread. Cooking Lab.
60. Mohammad Sina Nabizadeh, Ravi Ramamoorthi, and Albert Chern. 2021. Kelvin Transformations for Simulations on Infinite Domains. ACM Trans. Graph. 40, 4, Article 97 (jul 2021), 15 pages.
61. Fabrice Neyret. 1998. Modeling, animating, and rendering complex scenes using volumetric textures. IEEE Trans. Vis. Comp. Graph. 4, 1 (1998).
62. NVIDIA. 2017. NVIDIA OptiX AI-Accelerated Denoiser. https://developer.nvidia.com/optix-denoiser.
63. NVIDIA. 2022. NVIDIA Real-time denoisers (NRD). https://developer.nvidia.com/rtx/ray-tracing/rt-denoisers.
64. Yaobin Ouyang, Shiqiu Liu, Markus Kettunen, Matt Pharr, and Jacopo Pantaleoni. 2021. ReSTIR GI: Path Resampling for Real-Time Path Tracing. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 17–29.
65. Paul William Partridge, Carlos Alberto Brebbia, et al. 2012. Dual reciprocity boundary element method.
66. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically based rendering: From theory to implementation. Morgan Kaufmann.
67. Helmut Pottmann, Johannes Wallner, Yong-Liang Yang, Yu-Kun Lai, and Shi-Min Hu. 2007. Principal curvatures from the integral invariant viewpoint. Computer Aided Geometric Design 24, 8–9 (2007), 428–442.
68. Yang Qi, Dario Seyb, Benedikt Bitterli, and Wojciech Jarosz. 2022. A bidirectional formulation for Walk on Spheres. Computer Graphics Forum 41, 4 (2022), 51–62. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14586
69. Damien Rioux-Lavoie, Ryusuke Sugimoto, Tümay Özdemir, Naoharu H. Shimada, Christopher Batty, Derek Nowrouzezahrai, and Toshiya Hachisuka. 2022. A Monte Carlo Method for Fluid Simulation. ACM Trans. Graph. 41, 6, Article 240 (nov 2022), 16 pages.
70. Karl K Sabelfeld and Nikolai A Simonov. 2013. Random walks on boundary for solving PDEs. De Gruyter.
71. Rohan Sawhney. 2021. FCPW: Fastest Closest Points In The West. https://github.com/rohan-sawhney/fcpw
72. Rohan Sawhney and Keenan Crane. 2020. Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains. ACM Trans. Graph. 39, 4, Article 123 (aug 2020), 18 pages.
73. Rohan Sawhney, Dario Seyb, Wojciech Jarosz, and Keenan Crane. 2022. Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients. ACM Trans. Graph. 41, 4, Article 53 (jul 2022), 17 pages.
74. Christoph Schied, Anton Kaplanyan, Chris Wyman, Anjul Patney, Chakravarty R Alla Chaitanya, John Burgess, Shiqiu Liu, Carsten Dachsbacher, Aaron Lefohn, and Marco Salvi. 2017. Spatiotemporal variance-guided filtering: real-time reconstruction for path-traced global illumination. In Proceedings of High Performance Graphics. 1–12.
75. Christoph Schied, Christoph Peters, and Carsten Dachsbacher. 2018. Gradient estimation for real-time adaptive temporal filtering. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 2 (2018), 1–16.
76. Thomas BA Senior. 1960. Impedance boundary conditions for imperfectly conducting surfaces. Applied Scientific Research, Section B 8, 1 (1960), 418–436.
77. Nicholas Sharp and Alec Jacobson. 2022. Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysis. ACM Trans. Graph. 41, 4, Article 107 (jul 2022), 16 pages.
78. Nikolai A Simonov. 2008. Walk-on-Spheres Algorithm for Solving Boundary-Value Problems with Continuity Flux Conditions. Springer Berlin Heidelberg, Berlin, Heidelberg. 633–643 pages.
79. Nikolai A Simonov. 2017. Walk-on-spheres algorithm for solving third boundary value problem. Applied Mathematics Letters 64 (2017), 156–161.
80. Ryusuke Sugimoto, Terry Chen, Yiti Jiang, Christopher Batty, and Toshiya Hachisuka. 2023. A Practical Walk-on-Boundary Method for Boundary Value Problems. ACM Trans. Graph. 42, 4 (aug 2023), 16 pages.
81. Eric Veach and Leonidas Guibas. 1995a. Bidirectional estimators for light transport. In Photorealistic Rendering Techniques. Springer, 145–167.
82. Eric Veach and Leonidas J Guibas. 1995b. Optimally combining sampling techniques for Monte Carlo rendering. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. 419–428.
83. Eric Veach and Leonidas J. Guibas. 1997. Metropolis Light Transport. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’97). ACM Press/Addison-Wesley Publishing Co., USA, 65–76.
84. Jiří Vorba and Jaroslav Křivánek. 2016. Adjoint-Driven Russian Roulette and Splitting in Light Transport Simulation. ACM Trans. Graph. 35, 4, Article 42 (jul 2016), 11 pages.
85. Carsten Wächter and Nikolaus Binder. 2019. A fast and robust method for avoiding self-intersection. Ray Tracing Gems: High-Quality and Real-Time Rendering with DXR and Other APIs (2019), 77–85.
86. Ingo Wald. 2007. On fast construction of SAH-based bounding volume hierarchies. In 2007 IEEE Symposium on Interactive Ray Tracing. IEEE, 33–40.
87. Ingo Wald, Will Usher, Nathan Morrical, Laura Lediaev, and Valerio Pascucci. 2019. RTX Beyond Ray Tracing: Exploring the Use of Hardware Ray Tracing Cores for Tet-Mesh Point Location.. In High Performance Graphics (Short Papers). 7–13.
88. Turner Whitted. 1980. An Improved Illumination Model for Shaded Display. Commun. ACM 23, 6 (jun 1980), 343–349.
89. Lifan Wu, Shuang Zhao, Ling-Qi Yan, and Ravi Ramamoorthi. 2019. Accurate Appearance Preserving Prefiltering for Rendering Displacement-Mapped Surfaces. ACM Trans. Graph. 38, 4, Article 137 (jul 2019), 14 pages.
90. Ekrem Fatih Yılmazer, Delio Vicini, and Wenzel Jakob. 2022. Solving Inverse PDE Problems using Grid-Free Monte Carlo Estimators. arXiv preprint arXiv:2208.02114 (2022).
91. Yijing Zhou, Wei Cai, and Elton Hsu. 2017. Computation of the local time of reflecting brownian motion and the probabilistic representation of the neumann problem. Communications in Mathematical Sciences 15, 1 (2017), 237–259.
92. Matthias Zwicker, Wojciech Jarosz, Jaakko Lehtinen, Bochang Moon, Ravi Ramamoorthi, Fabrice Rousselle, Pradeep Sen, Cyril Soler, and S-E Yoon. 2015. Recent advances in adaptive sampling and reconstruction for Monte Carlo rendering. In Computer graphics forum, Vol. 34. Wiley Online Library, 667–681.
