Keenan Crane
Walk on Stars:
A Grid-Free Monte Carlo Method for
PDEs with Neumann Boundary Conditions
ACM Transactions on Graphics (SIGGRAPH 2023)
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. This paper introduces the walk on stars (WoSt) method, 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 by locating the closest visible point on the geometric silhouette. Overall, WoSt retains many attractive features of other grid-free Monte Carlo methods, such as progressive and view-dependent evaluation, trivial parallelization, and sublinear scaling to increasing geometric detail.
Implementation Guide
Though our method takes some work to derive, it is extremely simple to implement. This guide steps through a full 2D implementation, in about 150 lines of illustrated code.
The authors thank Gautam Iyer for suggesting Tikhonov regularization, and Dario Seyb and Rasmus Tamstorf for fruitful conversations. This work was generously supported by nTopology and Disney Research, NSF awards 1943123, 2212290 and 2008123, Alfred P. Sloan Research Fellowship FG202013153, a Packard Fellowship, NSF Graduate Research Fellowship DGE2140739, and an NVIDIA Graduate Fellowship.
Monte Carlo Geometry Processing—good starting point for learning about the walk on spheres method, and its connection to visual computing.
Boundary Value Caching—method for speeding up Walk on Stars.
@article{Sawhney:2023:WoSt, author = {Sawhney, Rohan and Seyb, Dario and Jarosz, Wojciech and Crane, Keenan}, title = {Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions}, year = {2023}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, journal = {ACM Trans. Graph.}, keywords = {Monte Carlo methods, walk on spheres} }
C++ tutorialsimple 2D version used in implementation guide.