A bidirectional formulation for Walk on Spheres

1Dartmouth College 2NVIDIA

In Computer Graphics Forum (Proceedings of EGSR), 2022

Teaser
Our formalism allows us to construct Walk on Sphere paths (top) starting at source points (left), “sensor” points (right), or from both directions (middle), corresponding conceptually to (bottom) forward path tracing, bidirectional path tracing, and light tracing (left to right respectively).
Abstract Downloads VideosMore Cite Related

Abstract

Numerically solving partial differential equations (PDEs) is central to many applications in computer graphics and scientific modeling. Conventional methods for solving PDEs often need to discretize the space first, making them less efficient for complex geometry. Unlike conventional methods, the walk on spheres (WoS) algorithm recently introduced to graphics is a grid-free Monte Carlo method that can provide numerical solutions of Poisson equations without discretizing space. We draw analogies between WoS and classical rendering algorithms, and find that the WoS algorithm is conceptually equivalent to forward path tracing. Inspired by similar approaches in light transport, we propose a novel WoS reformulation that operates in the reverse direction, starting at source points and estimating the Green's function at “sensor” points. Implementations of this algorithm show improvement over classical WoS in solving Poisson equation with sparse sources. Our approach opens exciting avenues for future algorithms for PDE estimation which, analogous to light transport, connect WoS walks starting from sensors and sources and combine different strategies for robust solution algorithms in all cases.

Downloads

Videos

Presentation slides video

Acknowledgements

This work was generously supported by NSF awards 1812796 and 1844538, and a Neukom Institute CompX faculty grant.

Cite

Yang Qi, Dario Seyb, Benedikt Bitterli, Wojciech Jarosz. A bidirectional formulation for Walk on Spheres. Computer Graphics Forum (Proceedings of EGSR), 41(4), July 2022. 
@article{qi22bidirectional,
    author   = {Qi, Yang and Seyb, Dario and Bitterli, Benedikt and Jarosz, Wojciech},
    title    = {A bidirectional formulation for {Walk} on {Spheres}},
    journal  = {Computer Graphics Forum (Proceedings of EGSR)},
    year     = {2022},
    month    = jul,
    volume   = {41},
    number   = {4},
    issn     = {1467-8659},
    doi      = {10/jgzr},
    keywords = {Brownian motion, partial differential equations, PDEs, Monte Carlo}
}
© The Author(s). This is the author's version of the work. It is posted here by permission of The Eurographics Association for your personal use. Not for redistribution. The definitive version is available at diglib.eg.org.