Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains

摘要

This paper explores how core problems in PDE-based geometry processingcan be efficiently and reliably solved via grid-free Monte Carlo methods.Modern geometric algorithms often need to solve Poisson-like equations ongeometrically intricate domains. Conventional methods most often meshthe domain, which is both challenging and expensive for geometry withfine details or imperfections (holes, self-intersections, etc.). In contrast, gridfreeMonte Carlo methods avoid mesh generation entirely, and instead justevaluate 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 manybenefits with Monte Carlo methods from photorealistic rendering: excellentscaling, trivial parallel implementation, view-dependent evaluation, and theability to work with any kind of geometry (including implicit or proceduraldescriptions). We develop a complete “black box†solver that encompassesintegration, variance reduction, and visualization, and explore how it can beused for various geometry processing tasks. In particular, we consider severalfundamental linear elliptic PDEs with constant coefficients on solid regionsof Rğ‘›. Overall we find that Monte Carlo methods significantly broaden thehorizons of geometry processing, since they easily handle problems of sizeand complexity that are essentially hopeless for conventional methods.