Monte Carlo geometry processing
Authors:
Top Cited Papers
Open Access
- 12 August 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 39 (4)
Abstract
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.Keywords
This publication has 62 references indexed in Scilit:
- Polygon mesh repairingACM Computing Surveys, 2013
- Bounded biharmonic weights for real-time deformationACM Transactions on Graphics, 2011
- Interactive and anisotropic geometry processing using the screened Poisson equationACM Transactions on Graphics, 2011
- Efficient BRDF importance sampling using a factored representationACM Transactions on Graphics, 2004
- The meshless finite element methodInternational Journal for Numerical Methods in Engineering, 2003
- ϵ-Shell error analysis for “Walk On Spheres” algorithmsMathematics and Computers in Simulation, 2003
- Forward-backward stochastic differential equations and quasilinear parabolic PDEsProbability Theory and Related Fields, 1999
- A stochastic algorithm for high speed capacitance extraction in integrated circuitsSolid-State Electronics, 1992
- A ray tracing solution for diffuse interreflectionACM SIGGRAPH Computer Graphics, 1988
- Modeling the interaction of light between diffuse surfacesACM SIGGRAPH Computer Graphics, 1984