A Bidirectional Formulation for Walk on Spheres

Simple item page
dc.contributor.authorQi, Yangen_US
dc.contributor.authorSeyb, Darioen_US
dc.contributor.authorBitterli, Benedikten_US
dc.contributor.authorJarosz, Wojciechen_US
dc.contributor.editorGhosh, Abhijeeten_US
dc.contributor.editorWei, Li-Yien_US
dc.date.accessioned2022-07-01T15:36:41Z
dc.date.available2022-07-01T15:36:41Z
dc.date.issued2022
dc.description.abstractNumerically 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.en_US
dc.description.number4
dc.description.sectionheadersSampling
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume41
dc.identifier.doi10.1111/cgf.14586
dc.identifier.issn1467-8659
dc.identifier.pages51-62
dc.identifier.pages12 pages
dc.identifier.urihttps://doi.org/10.1111/cgf.14586
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14586
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectCCS Concepts: Computing methodologies --> Ray tracing; Modeling and simulation; Mathematics of computing --> Stochastic processes
dc.subjectComputing methodologies
dc.subjectRay tracing
dc.subjectModeling and simulation
dc.subjectMathematics of computing
dc.subjectStochastic processes
dc.titleA Bidirectional Formulation for Walk on Spheresen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v41i4pp051-062.pdf
Size:
29.57 MB
Format:
Adobe Portable Document Format
Download
Collections
41-Issue 4