nicatio/wost-simple

Simple didactic code + tutorial for the Walk on Stars (WoSt) algorithm

wost-simple

This repository provides basic example code and a step-by-step tutorial on how to implement the walk on stars (WoSt) algorithm, introduced in the paper

Sawhney, Miller, Gkioulekas, Crane
Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions
ACM Transactions on Graphics (2023)

WoSt is a grid-free Monte Carlo method for solving basic partial differential equations (PDEs) like the Laplace or Poisson equation, with both Dirichlet and Neumann boundary conditions. Unlike finite element, boundary element, or finite difference methods it does not require a volumetric grid or mesh, nor a high-quality boundary mesh. Instead, it uses random walks to solve the problem directly from the original boundary representation; moreover, it can provide accurate solution values at a single query point, rather than needing to solve the problem over the entire domain.

Though the derivation of algorithm takes some work, the final algorithm remains about as simple as the original walk on spheres (WoS) method of Muller (1956). For a Laplace equation with Dirichlet boundary conditions, WoS essentially says:

(Walk on Spheres) Repeatedly jump to a random point on a sphere around the current point until you reach the boundary. The average boundary value over many such walks yields the solution.

For a Laplace equation with Dirichlet and zero-Neumann boundary conditions, WoSt is nearly identical:

(Walk on Stars) Repeatedly jump to a random point on a star-shaped region around the current point until you reach the Dirichlet boundary. The average boundary value over many such walks yields the solution.

The main implementation effort is in enriching the closest point queries used by WoS with closest silhouette point queries, as well as standard "first hit" ray intersection queries. A complete 2D implementation with no external dependencies is provided here in about 150 lines of C++ code (ignoring I/O), in the file WoStLaplace2D.cpp. For simplicity, we omit nonzero Neumann conditions and acceleration of geometric queries—a full 3D implementation is discussed in Sawhney et al (2023).

To emphasize the core ideas of the WoSt algorithm, this tutorial focuses on a bare-bones 2D version of WoSt that solves the Laplace equation

$$ \begin{array}{rcll} \Delta u &=& 0 & \text{on}\ \Omega, \\ u &=& g & \text{on}\ \partial\Omega_D, \\ \tfrac{\partial u}{\partial n} &=& 0 & \text{on}\ \partial\Omega_N, \\ \end{array} $$

where $\Omega \subset \mathbb{R}^2$ is a closed polygon in the plane, $g$ is a real-valued function on the Dirichlet part of the boundary $\partial\Omega_D$, and $\partial\Omega_N$ is the complementary Neumann part of the boundary.

Acknowledgements

All diagrams in this document were made using Penrose. Special thanks to Wode Ni, Sam Estep, Yiliang Liang, and the rest of the Penrose team for development support during production of this document.

Citation

@software{WalkOnStarsIG,
author = {Sawhney, Rohan and Miller, Bailey and Gkioulekas, Ioannis and Crane, Keenan},
month = jun,
title = {{Walk on Stars (Implementation Guide)}},
version = {1.0},
year = {2023}
}

License

Walk on Stars (Implementation Guide) by Rohan Sawhney, Bailey Miller, Ioannis Gkioulekas, and Keenan Crane is licensed under CC BY 4.0.

Code is released under an MIT License.