demofox
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
Dec 29, 2022 at 1:53pmWeb
Show threadJeb CollinsDec 29, 2022
@demofox I saw the YouTube video of this and was really impressed. Made me wish I was still a grad student so I could start in a new research field.
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 threadj_bertolottiDec 29, 2022
@demofox @lisyarus Which brings me to the next (also very naïve) question: as the Green functions of the Poisson eq on many surfaces is well known, why not find the diffusion steady state as a sum of those instead of doing the whole Brownian random walk?
Show threaddemofoxDec 29, 2022
@j_bertolotti @lisyarus hey @keenancrane this is above my head a bit, can you explain? :)
Show threadRahul NarainDec 29, 2022
@j_bertolotti @demofox @lisyarus Green functions don't play too well with arbitrarily shaped domains, do they? As far as I recall they're primarily useful for free space computations, if you want to do any nontrivial boundaries you'd need to add lots of virtual sources.
Show threadWojciech Jarosz has movedDec 29, 2022
@j_bertolotti @demofox @lisyarus Walk on Spheres in fact uses the known Greens functions and Poisson kernels of simple shapes (by default the "Sphere" in Walk on Spheres, but you can also do Walk on Rectangles, etc). The benefit is that you can apply WoS to arbitrary domains where these functions are not known in closed form. As previously mentioned, you can perform point-evaluation, and you don't need to mesh/discretize the domain or boundaries.
Show threaddemofoxDec 29, 2022
@wjarosz @j_bertolotti @lisyarus that's so neat it supports other shapes. It makes sense from a "different norm" perspective but it sounds like you mean it more general than that
Show threadtroy_s Aug 3, 2023
@wjarosz Would love to see it solve the Poisson.
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 Aug 3, 2023
@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?
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.

Show threaddemofoxDec 29, 2022
@j_bertolotti @lisyarus one benefit is that you can do localized solves instead of solving it all globally. From a graphics pov, this means each pixel can solve for the data it needs on demand. You can zoom into part of the data and see that part, to the detail being viewed (even progressively) without having to calculate the whole solution in advance to full detail.
Show threadNikita LisitsaDec 29, 2022
@demofox Cool! I've made a shadertoy on this once as well: https://www.shadertoy.com/view/7lVcz3
Show threadCachefloweDec 29, 2022
@demofox I really appreciate your articles. I recently implementeed JFA and had read a couple of your posts several times long the way :)
Show threaddemofoxDec 29, 2022
@cacheflowe that's awesome :)
It's neat that JFA can make a voronoi which is an acceleration structure for this algorithm (!!). I have it on my todo list to implement the parallel banding algorithm, which is supposed to be faster and more accurate than JFA.
I wish I knew of an algorithm to do delaunay teiangulation as easy as JFA was (to know the N points that encompass a specific point)!
Show threadCachefloweDec 29, 2022
@demofox Very cool! JFA seems to have a *lot* of uses. Hopefully I’ll understand more of them someday 😅
Show threadPatricio Gonzalez VivoDec 30, 2022
@demofox nice article and technique! I have been working on something tangentially similar to convert meshes into SDF textures I can save as PNGs https://merveilles.town/@patricio/109563073013686829 I will try to implement your random walk. Any tip on ways to improve performance?
Patricio Gonzalez Vivo (@[email protected])

Attached: 1 video Dramatically improve the SDF generation from mesh, by: doing incremental LOD passes, multi-threading the distance sampling and image scaling and mixing. Also added support for colors.

Merveilles
Show threaddemofoxDec 30, 2022
@patricio good question! I haven't done what you are doing so profiling might indicate different problems, but in 2d, I've found using the jump flood algorithm to make Voronoi cells to know the closest distance in O(1) helped a lot. That is sort of what you are aiming for in the end though so unsure if it helps.
Show threaddemofoxDec 30, 2022
@patricio in randomized algorithms I also usually try / suggest using low discrepancy sequences instead of uniform white noise random numbers, but for random walks that just makes the walk never leave the origin hehe.
Show threadTony VladusichAug 3, 2023
@demofox cc @troy_s
Show threadTony VladusichAug 3, 2023
@demofox @troy_s the boundary between computer graphics and vision is getting blurry
Show threadtroy_s Aug 3, 2023
@TonyVladusich @demofox Yep. It’s deadly close!