CAREER: Algorithms and Data Structures for Robust 3D Geometry Processing via Intrinsic Triangulations

该项目开发的方法，使用户的几何软件，以利用一个更大的部分可用的三维几何数据。 我们目前正在见证几何数据可用性的爆炸式增长，这是由越来越实惠和可访问的3D采集和数字制造技术驱动的。然而，这些数据在科学，工程和医学领域仍然没有得到充分利用，因为几何软件的开发仍然需要对困难的低级技术概念（网格生成，有限元方法等）的复杂理解。 相反，这项研究提供了一个可靠的“黑盒子”接口的几何数据，使非专家用户将精力集中在更高层次的应用目标。 该项目中开发的算法将适用于从结构工程到自主车辆导航，到虚拟3D环境开发，再到医疗数据分析的广泛任务。 该项目将开发免费和开源软件，使这些算法立即和广泛访问。 该项目还将与行业和当地“制造商”社区合作，评估新技术的有效性，并促进向各种实际用户的转让。该项目开发的材料将有助于阐明离散计算算法和微分几何之间的联系，为教学和培训多样化的STEM劳动力提供丰富的机会。基本的技术方法是用所谓的内在三角测量取代表面或体积网格的标准概念。 这样的三角剖分可以通过边连接多面体表面的任何两个顶点，无论它们是否通过空间中的直线连接。 基于内在三角剖分的算法不太容易失败，因为它们可以自由地调整三角剖分以适应给定算法的要求。 数值线性代数的一个很好的类比是使用矩阵重排来提高线性求解器的数值稳定性。 同样地，内禀三角剖分提高了几何算法的数值稳定性。 从系统级的角度来看，内在三角剖分在大量现有算法和具有挑战性的几何数据之间提供了有价值的“桥梁”，使得例如1）最初不是被设计为在数值上鲁棒的算法能够在极低质量的网格上成功运行; 2）最初仅针对平面制定的算法能够应用于曲面;以及3）为均匀、各向同性问题设计的算法，以应用于更一般的非均匀、各向异性设置。固有方法还回避了几何计算中一些基本的、传统上不可避免的挑战，例如需要兼顾几何近似的质量和单个网格元素的质量。 该项目将专门为表面和体积网格开发新的数据结构，以及几何上采样/下采样，重新三角化，计算测地线路径，求解各向异性偏微分方程，处理切向量场和处理体积数据的算法。 该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project develops methods that make it possible for users of geometric software to take advantage of a much larger fraction of available three-dimensional geometric data. We are currently witnessing an explosion in the availability of geometric data, driven by increasingly affordable and accessible technologies for 3D acquisition and digital manufacturing. Yet this data remains under-utilized across science, engineering, and medicine, since development of geometric software still demands sophisticated understanding of difficult low-level technical concepts (mesh generation, finite element methods, etc.). This research instead provides a reliable "black box" interface to geometric data, enabling non-expert users to focus their energy on higher-level application goals. The algorithms developed in this project will be applicable to a broad range of tasks ranging from structural engineering, to autonomous vehicle navigation, to development of virtual 3D environments, to analysis of medical data. The project will develop free and open source software that makes these algorithms immediately and broadly accessible. The project will also engage with both industry and the local "maker" community to evaluate the effectiveness of the new technology and to facilitate transfer to a diverse set of real-world users. Materials developed in this project will help to illuminate connections between discrete computational algorithms and differential geometry, offering rich opportunities for pedagogy and training of a diverse STEM workforce.The basic technical approach is to replace the standard notion of a surface or volume mesh with a so-called intrinsic triangulation. Such a triangulation can connect any two vertices of a polyhedral surface by an edge, whether or not they are connected via a straight line through space. Algorithms based on intrinsic triangulations are far less prone to failure, since they can freely adjust the triangulation to accommodate the demands of a given algorithm. A good analogy from numerical linear algebra is the use of matrix reordering to improve the numerical stability of linear solvers. In the same way, intrinsic triangulations improve the numerical stability of geometric algorithms. From a system-level point of view, intrinsic triangulations provide a valuable "bridge" between a large class of existing algorithms and challenging geometric data, enabling for instance 1) algorithms that were not originally designed to be numerically robust to be successfully run on extremely low-quality meshes; 2) algorithms that were originally formulated only for the flat plane to be applied to curved surfaces; and 3) algorithms designed for homogeneous, isotropic problems to be applied in more general inhomogeneous, anisotropic settings. The intrinsic approach also side-steps some fundamental, traditionally unavoidable challenges in geometric computing, such as the need to juggle the quality of geometric approximation with the quality of individual mesh elements. The project will specifically develop new data structures for both surface and volume meshes, and algorithms for geometric upsampling/downsampling, retriangulation, computing geodesic paths, solving anisotropic partial differential equations, processing tangent vector fields, and processing volumetric data. Methods developed in the project will be evaluated via large-scale data sets arising from industrial applications.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.