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

跨越科学和工程的问题需要对自然界行为的准确预测，这通常是通过数值逼近所谓的偏微分方程组(PDE)的解来获得的。虽然这样的预测可以帮助我们理解各种现象，如复杂建筑模型的能效或地下水污染物通过岩土层的传输，但求解相关方程的算法很难管理自然界中发现的巨大复杂性，特别是随着新兴技术使获取更详细的几何描述成为可能。一个主要的挑战是，传统算法在求解方程之前必须将空间划分为小元素，对于详细的几何图形，这种离散化过程不仅需要比求解方程本身更多的时间，而且还会引入错误的误差，从而给人一种解的错误感觉。这项研究通过在偏微分方程和可伸缩的、可靠的蒙特卡罗方法之间建立桥梁来完全避开离散化，蒙特卡罗方法是为生成照片级真实感图像而开发的。主要目标是扩大可使用蒙特卡罗技术解决的偏微分方程的集合，并通过非专家容易使用的免费和开放源码软件提供对这些工具的访问。将通过与行业合作伙伴合作来评估该方法在实际应用中的有效性，以解决结构分析、工程设计和机器人路径规划方面的问题。该项目还将产生更广泛的影响，通过在线教程和开源课程材料，在学生和更广泛的公众中建立对STEM的兴奋。该项目的技术起点是穆勒球面行走(WOS)方法，该方法提供了具有Dirichlet边界条件的常系数拉普拉斯方程的解的无偏估计。虽然该方法已推广到其他扩散偏微分方程组，但仍远远落后于现代有限元和有限差分方法，而且WOS方法还不能应用于许多重要的工程和分析问题，如线弹性或Stokes流动。这个项目通过探索新的WOS方法来缩小差距，这些方法可以处理各向异性和空间变化的系数、更一般的Neumann和Robin边界条件、非线性偏微分方程组和基于偏微分方程组的优化问题。一个关键的见解是，复杂的蒙特卡罗技术是为计算机图形中的照片级真实感绘制(方差减少、密度估计等)开发的。可以通过将这两个问题都放在一个共同的数学框架中来适应偏微分方程。项目成果将包括关键的算法组件，例如对丰富的几何表示(隐式曲面、细分曲面等)的高性能最近点查询，以及使PDE规范能够自动转换为无偏WOS估计器的特定领域语言。由此产生的方法与蒙特卡罗渲染方法有许多共同之处：无网格、平凡的并行性，以及无需求解全局方程组即可在任何点评估解的能力。它们还允许对问题数据和领域几何进行动态更改，从而帮助提供即时、渐进的反馈，以收紧工程设计周期。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.