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)

• 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 (coming soon!)

Videos

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