Mastodawn

demofox Dec 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

@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).

Nikita Lisitsa Dec 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.

j_bertolotti Dec 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.

Nikita Lisitsa Dec 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

demofox Dec 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.

j_bertolotti Dec 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?

demofox Dec 29, 2022

@j_bertolotti @lisyarus hey @keenancrane this is above my head a bit, can you explain? :)

Rahul Narain Dec 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.

Wojciech Jarosz has moved Dec 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.

demofox Dec 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

@wjarosz Would love to see it solve the Poisson.

@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.

demofox Aug 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

@demofox Are any of the complete Poisson? I see the Laplacian and other fancy bits.

demofox Aug 3, 2023

@troy_s no, sorry. I don't know green's functions well enough to do that!

demofox Aug 3, 2023

@troy_s I wish someone had a simple example of them too though. :sigh:

@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?

demofox Aug 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

Wojciech Jarosz has moved Aug 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.

@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.

Wojciech Jarosz has moved Aug 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.

@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.

demofox Dec 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.