Walkin’ Robin: Walk on Stars with Robin Boundary Conditions
ACM Transactions on Graphics · 19.07.2024 · 43 (4) · 1-18
DOI: 10.1145/3658153 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 19.07.2024. Verfasst von Bailey Miller und 3 weiteren Autor:innen. Die Arbeit wurde bisher 31-mal zitiert (Crossref) und nennt 70 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF, Alfred P. Sloan Foundation, National Institute of Food and Agriculture.
Abstract (Originalsprache)
Numerous scientific and engineering applications require solutions to boundary value problems (BVPs) involving elliptic partial differential equations, such as the Laplace or Poisson equations, on geometrically intricate domains. We develop a Monte Carlo method for solving such BVPs with arbitrary first-order linear boundary conditions---Dirichlet, Neumann, and Robin. Our method directly generalizes the walk on stars (WoSt) algorithm, which previously tackled only the first two types of boundary conditions, with a few simple modifications. Unlike conventional numerical methods, WoSt does not need finite element meshing or global solves. Similar to Monte Carlo rendering, it instead computes pointwise solution estimates by simulating random walks along star-shaped regions inside the BVP domain, using efficient ray-intersection and distance queries. To ensure WoSt produces bounded-variance estimates in the presence of Robin boundary conditions, we show that it is sufficient to modify how WoSt selects the size of these star-shaped regions. Our generalized WoSt algorithm reduces estimation error by orders of magnitude relative to alternative grid-free methods such as the walk on boundary algorithm. We also develop bidirectional and boundary value caching strategies to further reduce estimation error. Our algorithm is trivial to parallelize, scales sublinearly with increasing geometric detail, and enables progressive and view-dependent evaluation.
Förderung
- NSF
- Alfred P. Sloan Foundation
- National Institute of Food and Agriculture
Zitieren
APA
Miller, B., Sawhney, R., Crane, K., & Gkioulekas, I. (2024). Walkin’ Robin: Walk on Stars with Robin Boundary Conditions. ACM Transactions on Graphics, 43(4), 1-18. https://doi.org/10.1145/3658153
Vancouver
Miller B, Sawhney R, Crane K, Gkioulekas I. Walkin’ Robin: Walk on Stars with Robin Boundary Conditions. ACM Transactions on Graphics. 2024;43(4):1-18. doi:10.1145/3658153
BibTeX
@article{Miller2024,
author = {Miller, Bailey and Sawhney, Rohan and Crane, Keenan and Gkioulekas, Ioannis},
title = {Walkin’ Robin: Walk on Stars with Robin Boundary Conditions},
journal = {ACM Transactions on Graphics},
year = {2024},
volume = {43},
number = {4},
pages = {1--18},
doi = {10.1145/3658153}
}
EUVIMED