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

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

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.