Walkin’ Robin: Walk on Stars with Robin Boundary Conditions

Numerous scientific and engineering applications require solving boundary value problems (BVPs) like the Laplace and Poisson equations on geometrically intricate domains. We describe a unified Monte Carlo approach to solving elliptic BVPs with Dirichlet, Neumann and Robin boundary conditions using the walk on stars algorithm, which unlike conventional numerical methods, does not require any cumbersome finite element mesh generation or global solves. Similar to Monte Carlo rendering, we simulate independent random walks in domains with partially absorbing and reflecting boundaries using a mix of ray intersection and distance queries---our key contribution is the development of a pointwise estimator with bounded walk throughput, which can have orders of magnitude less error in its solution estimate than previous grid-free techniques for BVPs like the walk on boundary method. We also develop bidirectional and boundary value caching strategies to further reduce the variance of our estimator. Our approach is trivial to parallelize, scales favorably with increasing geometric detail, and allows for progressive and view-dependent evaluation.

Authors

Bailey Miller (Carnegie Mellon University)
Rohan Sawhney (NVIDIA)
Keenan Crane (Carnegie Mellon University)
Ioannis Gkioulekas (Carnegie Mellon University)

Publication Date

Research Area

Award

SIGGRAPH 2024 Best Paper Award