Image credit: 3D assets purchased from TurboSquid (Curiosity Mars Rover, Product ID: 1511835) created by 3d_molier International. We have permission to use these assets for academic/educational purposes as per the TurboSquid 3D Model License agreement. The final rendered image including simulation outputs were created by our group.
“Walkin’ Robin: Walk on Stars With Robin Boundary Conditions” represents a breakthrough in Monte Carlo methods for simulating partial differential equations (PDEs) in complex geometric domains. This innovative approach addresses the limitations of previous grid-free techniques by supporting more complex boundary interactions, including Robin boundary conditions, and offering enhanced reliability and performance. This research was presented as a Technical Paper at SIGGRAPH 2024. Here, we catch up with the contributors to take a deeper dive into this method.
SIGGRAPH: Share an overview of “Walkin’ Robin: Walk on Stars With Robin Boundary Conditions.” What inspired you to develop the walk on stars algorithm, and how does it address the limitations of previous grid-free techniques like the walk on boundary method?
The walk on stars (WoSt) method is part of a growing family of Monte Carlo algorithms that have recently caught the attention of the computer graphics community for simulating partial differential equations (PDEs) in complex geometric domains [1]. WoSt can model a variety of phenomena in nature and engineering, such as the transfer of heat in solids, the distribution of charges in a conductor, the flow of ions around biological cells, and the smooth interpolation of colors in vector graphics.
Compared to conventional simulation methods (e.g., finite elements), WoSt bypasses the major bottleneck of generating “simulation-ready” meshes, a task that can often take longer to complete than the simulation itself. WoSt also shares many numerical advantages with algorithms for photorealistic rendering such as Monte Carlo ray tracing — for example, WoSt works with a variety of geometry representations (meshes, splines, implicit surfaces), is embarrassingly parallelizable, and can analyze the solution in local regions of interest.
These advantages create new opportunities for speeding up scientific simulation and engineering design, analogous to the impact ray tracing has had on these types of applications. We recently presented a tutorial on Monte Carlo algorithms for PDE simulation that should better highlight these advantages. You can check it out here.
Our motivation behind “Walkin’ Robin” specifically was to extend the WoSt algorithm we had introduced in SIGGRAPH 2023 to support more complex boundary interactions, and thus provide greater physical realism in modeling thermal, electromagnetic, elastic, and fluidic materials. Prior algorithms only supported boundary materials that were either perfectly absorbing or perfectly reflecting, such as a black body or perfect insulator. Beyond this generalization, our method also offers significantly more reliable and faster performance compared to alternative Monte Carlo algorithms.
SIGGRAPH: Can you elaborate on the key challenges you faced in designing the pointwise estimator with bounded walk throughput, and how you overcame them?
A key aspect of solving PDEs is accurate treatment of boundary conditions, corresponding to application-dependent constraints on the temperature, voltage, force, velocity, etc., of a physical system. We have been working over several years, and through a series of SIGGRAPH publications, to generalize WoSt to support an arbitrary mix of Dirichlet, Neumann, and now Robin boundary conditions. Even though these types of boundary conditions are commonplace in simulation problems, there was relatively little prior work on tackling them specifically with Monte Carlo algorithms. Initially, it was unclear what technical direction we should pursue to generalize to these boundary conditions.
In the end, we drew inspiration from the mathematical literature on diffusion. An important insight we leveraged from diffusion was that the random walks we simulate with WoSt should be absorbed on a Dirichlet boundary and reflected off a Neumann boundary. Robin boundaries are partially absorbing and partially reflecting, interpolating between Dirichlet and Neumann boundaries. The WoSt algorithm we developed in “Walkin’ Robin” captures this behavior by terminating random walks with a non-zero probability on a Robin boundary. Moreover, it also automatically recovers the desired random walk behavior on Dirichlet and Neumann boundaries, thus unifying the treatment of all three boundary conditions within a single Monte Carlo algorithm.
SIGGRAPH: How do the bidirectional and boundary value caching strategies work in practice, and what impact do they have on reducing variance in the solution estimates?
It helps to consider for a moment how similar strategies in rendering, which inspired these strategies for WoSt, improve performance. Since Kajiya introduced Monte Carlo path tracing to computer graphics in 1986, we have seen the development of progressively more advanced rendering algorithms built upon this technique, such as bidirectional path tracing, Metropolis light transport, virtual point lights, and ReSTIR. Compared to path tracing that simulates light transport independently for each pixel, these advanced algorithms reduce noise by sharing information between light paths and pixels.
Like path tracing, WoSt also computes the solution independently at every point in the domain of interest, resulting in redundant computation when the solution needs to be evaluated at a set of nearby points. In “Walkin’ Robin”, we extend the recently developed bidirectional and boundary value caching techniques to also support WoSt for Robin boundary conditions. These strategies reuse random walks starting from the boundary of a domain to also estimate the solution inside the domain. This information sharing further suppresses the salt-and-pepper noise characteristic of independent Monte Carlo estimates.
We believe we have only scratched the surface when it comes to reducing noise in Monte Carlo algorithms for solving PDEs, and there is plenty of inspiration to be drawn from rendering.
SIGGRAPH: In what types of applications or scenarios do you see the most significant advantages of your Monte Carlo approach compared to traditional numerical methods? How does your method handle scalability and performance when applied to domains with extremely high geometric complexity?
In the teaser figure of “Walkin’ Robin”, we motivate our Monte Carlo method against conventional finite element methods by performing a thermal analysis of NASA’s Curiosity Mars rover. Keeping temperatures within specified thermal limits is critical to mission success, but thermal modeling is difficult to integrate into the design phase when working with intricate geometry not easily captured via finite element methods.
In contrast to finite elements, walk on stars enables us to compute accurate temperature estimates progressively and reliably even for extremely complex geometry, without waiting on bottlenecks like mesh generation. In this example, a “deferred shading” approach for output-sensitive evaluation offers another advantage for engineering design, as it enables us to analyze temperature in local regions of interest that need to be inspected, without having to compute a global solution.
Monte Carlo methods like WoSt are not, however, a silver bullet. On simple domains with smooth boundary conditions, finite element methods are very mature and hard to beat in terms of compute time. Yet for more complex problems, end-to-end performance depends on many factors beyond just the rate of convergence of the core simulation method, such as mesh generation, parallel scaling, and visualization. It is in such problems where we think Monte Carlo algorithms offer the most exciting opportunities. The computer graphics community has already made Monte Carlo algorithms the workhorse for scientific, engineering, and design applications requiring photorealistic rendering, and we envision the community having similarly transformative impact on the multitude of applications requiring PDE simulation.
There is more fascinating research ahead at SIGGRAPH 2025! Submit yours to programs still accepting submissions, and stay tuned for the reveal of the full program in a few short months.
Bailey Miller is a PhD student at CMU advised by Ioannis Gkioulekas. His research develops Monte Carlo algorithms for large-scale simulation and stochastic scene representations for inverse tasks like 3D reconstruction. His work has received recognition through the NSF Graduate Research Fellowship, the NVIDIA Graduate Research Fellowship, and best paper awards at both SIGGRAPH and CVPR. He has previously co-taught a course on Monte Carlo PDE solvers at the Symposium on Geometry Processing (2024), and has collaborated with industry through internships at Adobe, Apple’s XDG (Exploratory Design Group), and NVIDIA’s High Fidelity Physics team.
Rohan Sawhney is a Senior Research Scientist in Nvidia’s High Fidelity Physics group. He earned his PhD in Computer Science from CMU under Keenan Crane. His research focuses on developing efficient and reliable Monte Carlo algorithms inspired by photorealistic rendering for PDE-based geometric computing, eliminating the need for volumetric mesh generation. Rohan has received a CMU Dissertation Award and Best Paper Awards at SIGGRAPH for his work on Monte Carlo PDE solvers, as well as a Symposium on Geometry Processing Best Software Award for Boundary First Flattening, an application to quickly and robustly generate UV maps.
Keenan Crane is the Michael B. Donohue Associate Professor of Computer Science and Robotics at Carnegie Mellon University, where he leads the Geometry Collective and is a member of the Center for Nonlinear Analysis. His work uses insights from differential geometry to build fundamental representations and algorithms for processing, designing, and analyzing geometric data. Keenan received a BS from UIUC, was a Google PhD Fellow at Caltech, an NSF Mathematical Sciences Postdoctoral Fellow at Columbia University. He is a Packard Fellow, recipient of an NSF CAREER Award and Best Paper Awards at SIGGRAPH.
Ioannis Gkioulekas is an associate professor at CMU, where he works broadly in computer graphics, focusing on computational imaging, physically based rendering, and physical simulation. Recent topics of interest within these areas include: non-line-of-sight imaging, single-photon imaging, LIDAR, SONAR, interferometry, acousto-optics, differentiable rendering, Monte Carlo simulation, and stochastic geometry. He has previously taught courses and tutorials on these topics, both at CMU and at venues including CVPR 2021, CVPR 2023, and SIGGRAPH 2023. For his research, he has received the NSF CAREER Award, the Sloan Research Fellowship, and best paper awards at CVPR and SIGGRAPH.
