Harmonic caching for walk on spheres

In ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia), 2025

We simulate heat conduction by solving a Laplace equation with Robin boundary conditions on a triangle mesh of a turkey leg containing one million primitives. The Robin conditions prescribe a radiant flux, precomputed via ray tracing on a texture to capture oven radiation (left). Our harmonic caching algorithm achieves robust temperature estimation with lower error and fewer correlation artifacts than alternative Monte Carlo solvers for PDEs.

Abstract

We present a variance reduction technique for Walk on Spheres (WoS) that solves elliptic partial differential equations (PDEs) by combining overlapping harmonic expansions of the solution, each estimated using unbiased Monte Carlo random walks. Our method supports Laplace and screened Poisson equations with Dirichlet, Neumann, and Robin boundary conditions in both 2D and 3D. By adaptively covering the domain with local expansion regions and reconstructing the solution inside each region using an infinite Fourier series of the harmonic function, our method achieves over an order of magnitude lower error than traditional pointwise WoS in equal time. While low-order truncations of the series typically introduce limited bias, we also introduce a stochastic truncation scheme that eliminates this bias in the reconstructed solution. Compared to recently developed caching algorithms for WoS, such as Boundary and Mean Value Caching, our approach yields solutions with lower error and fewer correlation artifacts.

Downloads

• Publication

  • Paper, PDF (46MB)
  • Paper (compressed), PDF (23MB)
  • Supplemental document, PDF (5MB)
  • Publisher's official version (may require a subscription)
  • SIGGRAPH Asia 2025 poster, PPTX (48MB) or PNG (35MB)

• Slides

  • Presentation slides, PDF (53MB)
  • Presentation slides, PowerPoint (91MB)

• Video

  • Video (full-quality), MOV (38MB)
  • Video (web-quality), MP4 (4MB)

• Data

  • Supplemental archive, ZIP (145MB) - offline version of the interactive comparisons below, also with EXR renderings.

• Code

  • GitHub project - Official reference implementation (soon to be merged into the mainline Zombie repo)

Videos

Visual overview

In this paper we introduce a new method that accelerates Walk on Spheres (WoS) and Walk on Stars (WoSt) by orders of magnitude.

WoS is a Monte Carlo approach for solving partial differential equations (PDEs) such as the Laplace equation (Δu=0). It works by expanding the largest sphere that fits within the domain and jumping to a random point on that sphere. This continues recursively until we reach the (Dirichlet) boundary, where we terminate the walk by returning the boundary value.

With only one walk per evaluation point ("pixel"), the result can be very noisy. Similar to ray tracing, we can reduce this noise by running multiple walks and averaging the results — but this quickly becomes computationally expensive.

WoS exploits the so-called "mean-value property" by (randomly) averaging the solution along the boundary of a sphere to obtain an estimate of the solution at the sphere's center. Unfortnately, this property only tells us the solution at one point – the center of the sphere/disc.

We show that with the same samples on the boundary, we can directly reconstruct a smooth, noise-free function throughout the entire disc via a harmonic series expansion.

Whenever you run N walks starting from an evaluation point, you can use those same walks to splat out a smooth, noise-free solution across all pixels in the largest disc/ball around it.

To reconstruct the solution over the entire domain, we introduce an efficient harmonic caching algorithm that achieves 100× to 100,000× lower error than WoS with equal-time.

Our algorithm naturally handles Robin boundary conditions using the Walk on Stars (WoSt) estimator. Here, the Robin boundary condition (top middle) prescribes a radiant flux precomputed via ray tracing on a texture (left) to model oven radiation. Solving the Laplace equation simulates heat conduction on the turkey leg (bottom middle), and our method effectively reduces noise and artifacts compared to prior methods (right).

Previous Next

Interactive result comparisons

Below you can view interactive comparisons comparing our method to various previous approaches.

Figure 8 Bunny
(LDR version)

Figure 9 Engine
(LDR version)

Figure 9 Gear
(LDR version)

Figure 9 Teapot
(LDR version)

Figure 9 Teapot (screening)
(LDR version)

Figure 12 Fish
(LDR version)

Figure 13 Fan
(LDR version)

Figure 14 Oven
(LDR version)

Figure 15 Gear (Neumann)
(LDR version)

Acknowledgements

The grilled turkey leg mesh in Fig. 1 is courtesy of Quixel Megascans under a standard license, and the oven scene is courtesy of Oven Crystal Black Dct Cr 982 by Franke from Blender Market. The “Engine” model in Fig. 9a is from Zombie [Sawhney and Miller 2023] under the MIT license. The model in Fig. 5 is from Qi et al. [2022], also under the MIT license. All other 2D models are based on images from Adobe Stock under the Education license. The fixed Stanford bunny mesh in Fig. 8 is courtesy of VertexDon from Sketchfab under CC BY-NC-SA 4.0, and the gear mesh in Fig. 15 is courtesy of Ali107_YT from Sketchfab under CC BY 4.0.

We thank the reviewers for their valuable feedback and suggestions. We are grateful to Aaron Lefohn and Ken Museth for supporting this research, and for fruitful discussions with Thomas Booth and Yang Qi. We also thank the Dartmouth Research Computing team for support on the Discovery cluster. Zihong thanks members of the Dartmouth Visual Computing Lab for their support during the project. ChatGPT was used solely to improve grammar and readability, and did not contribute to the technical content or ideas in this paper or supplemental document. This work was partially supported by the National Science Foundation under award numbers 1844538, 2403122, and 2440472.

Cite

@article{zhou25harmonic,
    author  = {Zhou, Zihong and d'Eon, Eugene and Sawhney, Rohan and Jarosz, Wojciech},
    title   = {Harmonic Caching for Walk on Spheres},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia)},
    year    = {2025},
    month   = dec,
    volume  = {44},
    number  = {6},
    doi     = {10.1145/3763322}
}

Related Projects

• 2025 Paper: State of the art in grid-free Monte Carlo methods for partial differential equations
• 2022 Paper: Grid-free Monte Carlo for PDEs with spatially varying coefficients
• 2022 Paper: A bidirectional formulation for Walk on Spheres
• 2012 Paper: Practical Hessian-based error control for irradiance caching

Copyright Disclaimer