demofoxDec 29, 2022
If you've heard of monte carlo geometry processing and wondered what it's all about, give this a read!
In short, it's a way of interpolating data using random walks. An implementation looks quite a bit like ray marching an SDF, including needing to know the distance to the closest feature, from within a loop!
https://blog.demofox.org/2020/07/11/interpolating-data-over-arbitrary-shapes-with-laplaces-equation-and-walk-on-spheres/
Interpolating Data Over Arbitrary Shapes With Laplace’s Equation and Walk on Spheres

A very cool paper was accepted to SIGGRAPH 2020 called “Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains” The paper is here: You can find…

The blog at the bottom of the sea
Show threadj_bertolottiDec 29, 2022
@demofox Naïve question: is this faster and/or more efficient than solving the Laplace equation? I somehow had in my mind that there were pretty good Laplace solvers out there (notice that I might be badly wrong about it).
Show threadNikita LisitsaDec 29, 2022
@j_bertolotti @demofox IIRC the trick here is that it gives you the value of a solution at a specific point without requiring to solve for the whole domain.
Show threadj_bertolottiDec 29, 2022
@lisyarus @demofox What this is exploiting is that the solution of the Laplace equation is also the steady state of the diffusion equation. So while it is true you don't need to solve for parts of the domain far away from the boundaries (i.e. the data you want to interpolate/extrapolate), you still need to "diffuse" from all those points.
If you tell me that solving the Laplace equation is a lot more onerous than doing a random walk I am ready to believe you, but it doesn't feel obvious to me.
Show threadNikita LisitsaDec 29, 2022

@j_bertolotti @demofox There are other benefits, like the usual solution methods require a triangle/tetrahedral mesh and often real-world data is really bad for meshing, while this random walk method is way less demanding, etc.

There's a nice presentation on this with a lot of rationale in it: https://www.youtube.com/watch?v=bZbuKOxH71o&ab_channel=KeenanCrane

Monte Carlo Geometry Processing

YouTube
Show threaddemofoxDec 29, 2022
@lisyarus @j_bertolotti oh and it can also solve poisson equations (using greens functions, which is just a tiny bit more calculation per step) which is neat, not just laplace.
Show threadtroy_s Aug 3, 2023

@demofox I was going to ask this in the other comment.

Any chance you could demo? Would be very interesting to see it applied to a 2D buffer image.

Show threaddemofoxAug 3, 2023
@troy_s yeah you bet. 8 have some shadertoys linked here
https://blog.demofox.org/2020/07/11/interpolating-data-over-arbitrary-shapes-with-laplaces-equation-and-walk-on-spheres/
Interpolating Data Over Arbitrary Shapes With Laplace’s Equation and Walk on Spheres

A very cool paper was accepted to SIGGRAPH 2020 called “Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains” The paper is here: You can find…

The blog at the bottom of the sea
Show threadtroy_s Aug 3, 2023
@demofox Are any of the complete Poisson? I see the Laplacian and other fancy bits.
Show threaddemofoxAug 3, 2023
@troy_s no, sorry. I don't know green's functions well enough to do that!
Show threadtroy_s Aug 3, 2023
@demofox
Show threaddemofoxAug 3, 2023
@troy_s I wish someone had a simple example of them too though. :sigh:
Show threadtroy_s 
@demofox Would it not be effectively like random walking across an already populated array, and taking the existing sample into the calculation at the position?
Aug 3, 2023 at 2:43pmWeb
Show threaddemofoxAug 3, 2023
@troy_s I'm not sure but I think it might be that you evaluate a function at each step? Hard to remember
Show threadWojciech Jarosz has movedAug 4, 2023
@demofox @troy_s that’s right. You have a source function that you look up and add to your answer at each step. Fora rendering person, Laplace is roughly like a scattering medium lit by an envmap (the boundary), whereas with Poisson the medium is additionally emissive in some parts.
Show threadtroy_s Aug 4, 2023
@wjarosz @demofox Is there a Monte Carlo Poisson out there already? My specific context would be to apply it to some 2D array of values like a picture or a render 2D data etc. Many seem to be for mathematical geometry.
Show threadWojciech Jarosz has movedAug 5, 2023
@troy_s @demofox all the walk on sphere papers that I’m aware of show examples with both laplace and the more general poisson equation. However, if your problem is already discretized over a pixel domain, and you need to solve over the whole domain, then I suspect that deterministic methods like finite differences will work better.
Show threadtroy_s Aug 5, 2023

@wjarosz For sure it is a direct line to a solution.

The sampling based Monte Carlo versions would allow someone to set a sample threshold, which is great for interfaces that allow for the audience to set values to lower “preview” solutions where necessary.

I just have not seen any demonstration solutions that perform the full PI, only L.