CCF: AF: Small: Volumetric Mesh Mapping

随着体积采集和计算技术在许多应用中的快速发展，如工业检测和医学成像，对处理这些数据集的工具的需求越来越大，以分析拓扑和几何，包括到规范结构的体积映射、体积配准、体积特征提取、几何数据库索引、体积参数化等。在这个项目中，PI和他的团队将开发用于计算一般网格体的拓扑和几何的严格算法，这是一个不平凡且从根本上比曲面更具挑战性的问题。要捕捉体积的隧道、句柄和空洞，需要计算同调和上同调群；要描述句柄、隧道和空洞之间的缠绕、扭曲和链接模式，还需要计算基本群。由于验证两个基本群是否同构是NP难的，传统的代数拓扑法是不够的，需要考虑Ricci流等几何结构。因此，该项目的一个主要焦点是开发RICI流的计算算法。另一方面，为了支持数据库索引和卷注册，将一个或多个卷映射到规范域是非常理想的，然而使用计算方法来获得卷的规范几何结构是一个开放的问题。PI们相信，Ricci资金流也是解决这个问题的关键。项目成果将包括基于三维流形拓扑和几何结构处理体积数据的严格计算算法，将按如下一系列相关步骤开发：设计和实现计算拓扑不变量的算法，包括同调、上同调群和基本群；设计和实现基于曲率流和微分形式的离散三维流形的具有恒截面曲率的正则几何结构的算法；设计和实现将正则几何结构合并到拓扑不变量的算法，例如寻找作为同伦类代表的闭测地线和极小曲面；设计和实现体积映射到规范结构、体积配准、体积特征提取和体积参数化的算法；设计和实现上述算法的并行版本，并使用GPU集群进行加速；调查上述算法的复杂性、稳定性和收敛速度。广泛影响：PI将构建和分发一套具体的软件工具，用于计算和可视化网格体的拓扑和几何结构，包括体积参数化、体积配准、体积到规范结构的体积映射、基本组计算以及拓扑和几何特征提取。不同的学科，如工程、科学、医学、计算机图形学、视觉、科学计算和数学，以及许多工业应用程序，将直接受益于这些工具，这些工具可用于体积纹理贴图、样条线体积构造、体积变形等。

With the rapid development of volumetric acquisition and computational technologies in numerous applications, such as industrial inspection and medical imaging, there is a growing need for tools for processing such datasets to analyze the topology and geometry, including volumetric mapping to canonical structures, volumetric registration, volumetric feature extraction, geometric database indexing, volumetric parameterization, etc. In this project the PI and his team will develop rigorous algorithms for computing the topology and geometry for general mesh volumes, a nontrivial and fundamentally more challenging problem than for surfaces. To capture the tunnels, handles, and voids of a volume, homology and cohomology groups need to be computed; to describe the tangling, twisting, and linking patterns among the handles, tunnels, and voids, fundamental groups need to be computed as well. Because it is NP-hard to verify whether two fundamental groups are isomorphic, conventional algebraic topological methods are inadequate and geometric structures such as Ricci flows need to be incorporated. Thus, a major focus of this project is development of computational algorithms for Ricci flows. On the other hand, it is highly desirable to map one or more volumes to a canonical domain, in order to support database indexing and volume registration, yet it is an open problem to obtain canonical geometric structures for volumes using computational methodologies. The PIs are confident that Ricci flows are the key to solving this problem, too. Project outcomes will include rigorous computational algorithms for processing volumetric data based on 3-manifold topology and geometric structures, which will be developed in a sequence of interrelated steps as follows: design and implementation of algorithms to compute topological invariants, including homology, cohomology groups, and fundamental groups; design and implementation of algorithms to compute canonical geometric structures, Riemannian metrics with constant section curvatures for discrete 3-manifolds, based on curvature flow and differential forms; design and implementation of algorithms to incorporate canonical geometric structures to the topological invariants, such as finding the closed geodesics and minimal surfaces as homotopy class representatives; design and implementation of algorithms for volumetric mapping to canonical structures, volumetric registration, volumetric feature extraction, and volumetric parameterization; design and implementation of parallel version of the above algorithms, and use of a GPU cluster for speed up; and investigation of the complexity, the stability, and the convergence rate of the above algorithms.Broader Impacts: The PIs will build and disseminate a concrete set of software tools for computing and visualizing the topology and geometric structures for mesh volumes, including volumetric parameterization, volumetric registration, volumetric mapping to canonical structures, fundamental groups computation, and topological and geometric feature extraction. Diverse disciplines such as engineering, science, medicine, computer graphics, vision, scientific computing, and mathematics, as well as a host of industrial applications, will directly benefit from these tools, which can be used for volumetric texture mapping, spline volume construction, volumetric deformation, etc.