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

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