Walkin' Robin: Walk on Stars with Robin Boundary Conditions

Bailey Miller*, Rohan Sawhney*, Keenan Crane†, Ioannis Gkioulekas†

ACM Transactions on Graphics (SIGGRAPH) 2024 best paper award

teaser
Thermal analysis of NASA's Curiosity Mars rover, mocked up on an artist-generated model not meant for simulation (top left). Keeping temperatures within specified thermal limits is critical to mission success—but thermal modeling is historically difficult to integrate into the design phase, due to intricate geometry not easily captured via finite element models. A grid-free Monte Carlo solver that supports Robin boundary conditions enables us to compute realistic temperature estimates quickly and progressively even for extremely complex geometry, without needing to volumetrically mesh the domain. Here a "deferred shading" approach provides output-sensitive evaluation, computing temperature values only at the points visible in screen space (top right). We can hence analyze temperature in local regions of interest, without computing a global solution (bottom row).

Abstract

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.

Resources

Paper: Our paper is available on the ACM Digital Library and locally.

Poster: Our poster is available here.

Presentation: Our presentation slides are available here.

Code: Our code is available on Github.

Citation

@article{Miller:Robin:2024,
	author = {Miller, Bailey and Sawhney, Rohan and Crane, Keenan and Gkioulekas, Ioannis},
	title = {Walkin’ Robin: Walk on Stars with Robin Boundary Conditions},
	year = {2024},
	issue_date = {July 2024},
	publisher = {Association for Computing Machinery},
	address = {New York, NY, USA},
	volume = {43},
	number = {4},
	issn = {0730-0301},
	url = {https://doi.org/10.1145/3658153},
	doi = {10.1145/3658153},
	journal = {ACM Trans. Graph.},
	month = {jul},
	articleno = {41},
	numpages = {18},
}

Acknowledgments

This work was supported by National Science Foundation (NSF) awards 2008123 and 2212290; National Institute of Food and Agriculture award 2023-67021-39073; a gift from Adobe Research; NSF Graduate Research Fellowship DGE2140739 and an NVIDIA graduate fellowship for Bailey Miller; a Packard Foundation Fellowship for Keenan Crane; and Alfred P. Sloan Research Fellowship FG202013153 for Ioannis Gkioulekas. Rohan Sawhney thanks Ken Museth for supporting this work. The Curiosity Mars rover model is courtesy of user 3d_molier International on TurboSquid.