Walk on Decomposed Subdomains
Blog post by Clément Jambon.
Disclaimer. The goal of this blog post is to walk you through the main<br>intuitions and ideas behind our work. To this end, it takes a completely different approach from the exposition<br>in the paper. It also takes a few technical and non-rigorous shortcuts. If you want a more formal treatment,<br>please refer directly to the paper. Note<br>also that the code behind this blogpost shouldn't be treated as a reference implementation: the<br>visualizations are for illustrative purposes onlySome things are “faked” to keep the webpage<br>lightweight!
1Elliptic PDEs and Boundary Value Problems
Many real-world phenomena are governed by elliptic partial differential equations (PDEs): heat conduction,<br>electrostatics, path planning, steady-state potential flow, and more.<br>These are often cast as boundary value<br>problems (BVPs), where values are prescribed on the boundary of a domain and we seek the solution to the PDE in<br>the interior.
Consider for example the Laplace equation with Dirichlet boundary conditions:
$$ \begin{cases} \Delta u = 0 & \text{in } \Omega \\ u = g & \text{on } \partial\Omega_D \end{cases} $$
Feel free to play with the interactive figure below to get an intuition for what this does:
Brush value +1.00
−1 (cold)+1 (hot)
Reset boundary<br>Presets
Click and paint inside the<br>outer boundary band to paint Dirichlet values $g$. The interior satisfies $\Delta u=0$.
Dirichlet problem. Solving the Laplace equation with Dirichlet boundary<br>conditions on a square.
We can make things more interesting by considering more complex geometries and boundary conditions. For example,<br>people are often interested in solving mixed boundary value problems with Neumann boundary conditionsNote that<br>we will restrict ourselves to zero-Neumann conditions.:
$$ \begin{cases} \Delta u = 0 & \text{in } \Omega \\ u = g & \text{on } \partial\Omega_D \\ \frac{\partial<br>u}{\partial n} = 0 & \text{on } \partial\Omega_N \end{cases} $$
The interactive figure below illustrates this. Notice how the isolines bend to meet the zero-Neumann obstacle at<br>right angles to satisfy $\frac{\partial u}{\partial n} = 0$.
Brush value +1.00
−1 (cold)+1 (hot)
Reset boundary<br>Hide isolines
Scene
Boundary presets
Click and paint the<br>Dirichlet band as before. The interior obstacle (dashed, grey) enforces $\partial u/\partial n = 0$ —<br>isolines bend to meet it at right angles.
Mixed problem. Laplace equation with Dirichlet values painted on the outer<br>boundary and zero-Neumann geometry inside.
If you look closely, you'll see that the solution is actually "pixelated". This is because it is computed with<br>finite<br>differences on a grid. Finite differences are very easy to<br>understand and to implement but they don't deal very well with complex geometries, often requiring extreme grid<br>refinement. Another common alternative is to use finite elements. The<br>problem is that finite elements require<br>careful mesh generation, which can be particularly challenging and time-consuming for complex geometries<br>Imagine designing a car and having to regenerate the mesh every time you tweak the design. That would be a<br>nightmare — and it is!<br>, such as<br>the city shown below.
Wind around a city. This scene contains hundreds of buildings with intricate<br>geometry.<br>Our method characterizes their influence on wind patterns, visualized here as steady-state potential<br>streamlines.
2Grid-Free Monte Carlo Methods
Luckily, the computer graphics community has recently revived an old idea: grid-free Monte Carlo methods. The<br>canonical algorithm underpinning<br>this approach is the Walk on Spheres (WoS) algorithm.
The intuition, from stochastic calculus, is that if<br>you were to simulate a Brownian motion (a continuous<br>random walk) starting from an interior point $x$, it would<br>eventually hit the boundary at some random location $Z_\tau$. The expected value $\mathbb{E}[g(Z_\tau)]$ of the<br>boundary condition at that<br>random<br>location is exactly the solution to the Dirichlet problem given by .
▶ Drop particle<br>✕ Clear
Brownian motion and Laplace equation. A particle starts at the interior<br>point $x$ and diffuses until it is absorbed at a random boundary location $Z_\tau$. The boundary is colored<br>by $g$; averaging $g(Z_\tau)$ over many such walks recovers $u(x)$.
Doing this independently at every interior point gives us the whole solution. With only a few walks per<br>point the estimate is noisy, but as we average more and more, variance progressively vanishes and the smooth<br>harmonic solution emerges as shown in the figure below.
Refresh rate: 1 walks/frame
slowfast
⏸ Pause<br>↻ Restart
low $u$<br>high $u$
Every interior pixel runs<br>independent Walk-on-Spheres estimates of $u(x)=\mathbb{E}[g(Z_\tau)]$. Averaging more walks per pixel<br>denoises the field into the harmonic solution. It runs continuously; the slider sets how fast.
Number of samples: 1
Progressive Monte Carlo estimate. The same square Dirichlet problem, now<br>solved at every pixel by...