网格曲面上质心Power图的快速计算及应用

Nowadays virtual reality develops rapidly. Digital geometry processing, as the key to construct the technological system of virtual reality, is playing an increasingly important role. In this proposal, the applicant focuses on the hard-core subject, i.e., seeking for an as-uniform-as-possible point distribution with area constraints on curved surfaces. It requires (1) all the sites form a decomposition of the whole domain and each site coincides with the centroid of its dominated cell, and (2) each cell meets the given area constraint. So such a geometric tool is able to easily support area requirements and guarantee the uniformity of point distribution. de Geos et al. found that this problem can be formulated by optimal mass transport (OMT) and they further gave an algorithm with one-order convergence. In the recent SIGGRAPH ASIA 2016, the applicant and his co-authors named this problem as centroidal power diagram and proposed a super-linearly convergent algorithm. However, these existing algorithms are only applicable to the 2D Euclidean space. This proposal focuses on how to compute the centroidal power diagram on polygonal meshes. Furthermore, the applicant will explore its applications in digital geometry processing based on the area-controllable property.

目前，虚拟现实进入了一个高速发展的时期，而数字几何处理作为实现虚拟现实技术体系的关键内容，发挥着越来越重要的作用。本项目重点研究数字几何处理中的核心课题，即曲面上带严格面积约束且分布尽可能均匀的采样。它满足：(1)整个区域被划分成若干块，每个种子点统治一块子区域且与其质心重合，(2)每个种子点统治的子区域满足给定的面积约束。可见，这样的采样分布不仅面积可控，还能保证分布上的相对均匀性。de Geos等人[2012]发现带面积约束的分布问题可通过最优传输理论进行诠释，并给出了一阶收敛的优化算法。在SIGGRAPH ASIA 2016大会上，申请人及其合作者把该问题命名为质心Power图问题，并提出了超线性收敛的优化算法。然而，已有算法仅适用于二维的欧氏空间。本项目拟研究如何在网格曲面上快速计算质心Power图, 并基于测地质心Power图在面积控制上的优点，探讨它在数字几何处理中的重要应用。

本项目关注数字几何处理中的核心课题，即曲面上带严格面积约束且分布尽可能均匀的采样，重点研究如何在网格曲面上快速计算质心Power图和Voronoi图, 并基于这种剖分结构的优点，探讨它在数字几何处理、计算机辅助设计中的重要应用。项目团队在过去四年中攻克了以下几个方面的问题。.第一，面向多模态三维数据的剖分和网格化。考虑到三维数据有各种各样的形态，例如点云、网格曲面、隐式曲面、参数曲面等等，针对多模态三维数据的几何处理异常重要。我们发现投影操作是多模态三维数据与几何处理任务之间的桥梁。我们在CSIAM 2021年会等多个重要场合报告了我们的工作。.第二，薄板曲面上的剖分。GVD (Geodesic Voronoi Diagram) 是流形上的Voronoi剖分，它作为一种重要的几何结构，被广泛应用在各种领域。然而精确GVD的计算代价十分高昂，通过RVD (Restricted Voronoi Diagram) 近似计算是目前常用的方法。“薄板曲面上的Restricted Voronoi剖分”，通过无主区域的检测和重分割策略，解决复杂情况下内蕴与外蕴剖分之间的冲突，得到几何和拓扑上更加合理的、更加近似于GVD的剖分结果。.第三，高效率、拓展性更强的测地变分理论。测地度量能够衡量曲面上两点之间的远近，是几何处理效果和效率的重要驱动因素。与过去关注效率和精度不同，本项目更加关注测地度量的泛化性和可用性。因此，我们针对测地度量的光滑性和泛化性做了一系列的工作，发表了一系列的学术论文，形成了系统性较强的测地变分理论。.第四，直接面向高质量三角化、流形网格的曲面重构。过去的方法主要分为显式重构和隐式重构，前者不容易保流形，后者不容易保证三角化的质量。我们将曲面上的剖分理论引入曲面重构问题，同时克服了这两个困难。.第五，面向工业CAD的算法攻坚。我们以CAD软件中的两个典型问题为突破口，将本项目中提出的剖分理论用于解决CAD软件中的核心问题，获得了突破性进展。它们是：（1）sweep surface上的测地线问题，（2）曲面偏置问题。目前正与中望联合攻克，将算法并行化、实用化。.未来，项目团队还会再接再励，在已有的基础上，将研究成果向以下三个方向推向前进：（1）剖分的速度和精度有待于进一步提高，（2）用于解决CAD软件中的瓶颈问题,（3）应用的深度和广度有待于进一步挖掘。