HCC: Medium: Grid-Free Monte Carlo Methods for Digital Geometry Processing

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Problems across science and engineering demand accurate predictions about the behavior of the natural world, which are often obtained by numerically approximating solutions to so-called partial differential equations (PDEs). While such predictions can help us understand diverse phenomena such as the energy efficiency of complex building models or the transport of groundwater pollutants through layers of rock and soil, the algorithms for solving the relevant equations have difficulty managing the immense complexity found in nature, especially as emerging technology makes it possible to acquire ever more detailed descriptions of geometry. A major challenge is that traditional algorithms must partition space into small elements prior to solving equations, and for detailed geometry this process of discretization can both take far more time than solving the equation itself and also introduce error that gives a false sense of the solution. This research side-steps discretization entirely by building a bridge between PDEs and scalable, reliable Monte Carlo methods developed for photorealistic image generation. The main goal is to expand the set of PDEs that can be solved using Monte Carlo techniques and to provide access to these tools via free and open source software that is easily usable by non-experts. The effectiveness of the approach for real-world applications will be evaluated through collaborations with industry partners to address problems in structural analysis, engineering design, and robotic path planning. The project will have additional broad impact by building excitement about STEM among students and the broader public, via online tutorials and open source course material. The technical starting point for the project is Muller's walk on spheres (WoS) method, which provides unbiased estimates of the solution to a constant-coefficient Laplace equation with Dirichlet boundary conditions. Although this method has been generalized somewhat to other diffusive PDEs, it still lags far behind the capability of modern finite element and finite difference methods, and WoS methods cannot yet be applied to many problems important for engineering and analysis, such as linear elasticity or Stokes flow. This project helps close the gap by exploring new WoS methods that handle anisotropic and spatially varying coefficients, more general Neumann and Robin boundary conditions, nonlinear PDEs, and PDE-based optimization problems. A key insight is that sophisticated Monte Carlo techniques developed for photorealistic rendering in computer graphics (variance reduction, density estimation, etc.) can be adapted to PDEs, by casting both problems in a common mathematical framework. Project outcomes will include critical algorithmic components, such as high-performance closest point queries for a rich class of geometric representations (implicit surfaces, subdivision surfaces, etc.), and a domain-specific language that enables PDE specifications to be automatically translated into unbiased WoS estimators. The resulting methods share many features with methods from Monte Carlo rendering: no meshing, trivial parallelism, and the ability to evaluate the solution at any point without solving a global system of equations. They also allow dynamic changes to problem data and domain geometry, thereby helping to provide immediate, progressive feedback that tightens the engineering design cycle. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.