Keenan Crane

CARNEGIE MELLON UNIVERSITY

Monte Carlo Geometry Processing:

A Grid-Free Approach to PDE-Based Methods on Volumetric Domains

A Grid-Free Approach to PDE-Based Methods on Volumetric Domains

SIGGRAPH 2020 / ACM Transactions on Graphics 2020

This paper explores how core problems in PDE-based geometry processing can be efficiently and reliably solved via grid-free Monte Carlo methods. Modern geometric algorithms often need to solve Poisson-like equations on geometrically intricate domains. Conventional methods most often mesh the domain, which is both challenging and expensive for geometry with fine details or imperfections (holes, self-intersections, *etc.*). In contrast, grid-free Monte Carlo methods avoid mesh generation entirely, and instead just evaluate closest point queries. They hence do not discretize space, time, nor even function spaces, and provide the exact solution (in expectation) even on extremely challenging models. More broadly, they share many benefits with Monte Carlo methods from photorealistic rendering: excellent scaling, trivial parallel implementation, view-dependent evaluation, and the ability to work with any kind of geometry (including implicit or procedural descriptions). We develop a complete “black box” solver that encompasses integration, variance reduction, and visualization, and explore how it can be used for various geometry processing tasks. In particular, we consider several fundamental linear elliptic PDEs with constant coefficients on solid regions of *R*^{n}. Overall we find that Monte Carlo methods significantly broaden the horizons of geometry processing, since they easily handle problems of size and complexity that are essentially hopeless for conventional methods.

The authors thank Mark Gillespie, Ioannis Gkioulekas, and Rasmus Tamstorf for fruitful conversations, Ruihao Ye for support on closest point queries, and Timothy Sun for some early explorations of these ideas. The *hemisus guineensis* mesh is used courtesy of the Blackburn Lab, under a CreativeCommons BY 4.0 license. This work was supported by a Packard Fellowship, NSF awards 1717320 and 1943123, and gifts from Autodesk, Adobe, Disney, and Facebook. The second author was also supported by NSF award DMS-1439786 and Sloan award G-2019-11406 while in residence at ICERM.

@article{Sawhney:2020:MCG,
author = {Sawhney, Rohan and Crane, Keenan},
title = {Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains},
journal = {ACM Trans. Graph.},
volume = {39},
number = {4},
year = {2020},
publisher = {ACM},
address = {New York, NY, USA},
}

Tutorial

Web

WoSLaplace2D.cpp— | quick and dirty version of naïve estimator for 2D Laplace equation. Example output. |

WoSPoisson2D.cpp— | quick and dirty version of naïve estimator for 2D Poisson equation. Example output. |

Diffusion curves | —Shadertoy example of 2D diffusion curves, written by Inigo Quilez. (Twitter) |

Simple Laplace | —Shadertoy example of a simple 2D Laplace equation by Inigo Quilez. (Twitter) |

Implicit surface | —Shadertoy reproduction of smooth double torus in Figure 2 by Ricky Reusser. (Twitter) |

Figures