Diskify：一种用于计算曲面上割网络的组合方法

《Computers & Graphics》：Diskify: A combinatorial approach to the computation of cut networks on surfaces

　　•我们提出了一种完全组合式的、稳健的算法，用于在任意曲面上计算割集网络。这些割集能够将曲面分解为拓扑上等价于圆盘的区域，或者将整个曲面展开为一个单一的拓扑圆盘。•我们的方法利用高效的Voronoi分解算法以及适当的数据结构来高效解决该问题，从而提供了一种具有可扩展性、稳健性，并且有坚实数学保障的解决方案。•我们的流程具有通用性，可高度定制，允许定义任意的度量标准以及特定应用所需的优化能量。引言在计算机图形学和几何处理中，三角网格已成为三维曲面的标准表示形式。它们的简洁性和表达能力使其适用于从动画和物理模拟到形状分析和纹理映射的广泛领域。其中，UV映射起着核心作用，它能够将纹理和颜色等表面属性从二维图像域传输到3D模型的表面上。这对于实时和交互式应用尤为重要，因为性能要求限制了顶点数量，而高质量标准则要求在亚顶点分辨率下使用这些属性。在计算机图形学[1]和制造设计[2]领域，人们已经付出了大量努力来直接在曲面上设计递归或重复的图案[3]、[4]、曲线[5]、[6]以及形状[7]。然而，大多数实际应用需要更复杂的设计和更高的效率，因此仍然依赖由艺术家手工制作的UV参数化，或者与曲面一起处理以生成程序化图案[8]、[9]、[10]，或者烘焙实心纹理[11]、[12]、[13]。尽管UV映射无处不在且非常重要，但构建可靠的UV贴图仍然是一个具有挑战性的问题。许多现有方法在面对复杂拓扑、不规则采样或数值不稳定时容易出错[14]，因此稳健性和可预测性是实际应用中的关键要求。本文扩展了[15]中的工作，我们在其中提出了一种利用三角网格结构特性进行UV映射的方法，该方法高效、实现简单且极为可靠。其核心思想是基于输入网格的稀疏点采样的Voronoi分解，并进一步细化这种分解，使其形成的区域在拓扑上必然等价于圆盘。我们的算法分为两个阶段。首先，迭代细分Voronoi单元，直到所有区域都具有类似圆盘的拓扑结构。其次，合并具有较大边界部分的相邻区域，以减少图表总数及其周长与面积比，同时保持圆盘等价性。这一拓扑保证使得每个区域的UV参数化变得简单，并显著减少了退化情况的发生。[15]的主要动机是尽量减少故障案例，而这在现有的UV映射流程中一直是个棘手的问题。通过这项工作，我们大幅扩展了之前的贡献，证明了分割算法和合并方法并不依赖于特定的度量标准，可以被视为一套可以轻松适应不同任务的通用流程。例如，在之前的工作中，我们仅考虑了标准的测地距离来生成周长与面积比最小的区域；而在本扩展工作中，我们提出了等光度量的离散版本[16]，它使我们能够在尖锐特征处定位区域边界。此外，我们还考虑了另一种情形，即分割并非合适的解决方案，而是需要将曲面展开为圆盘。将曲面切开并使其在拓扑上等价于圆盘是几何学和拓扑学中的一个经典问题[17]，它在曲面参数化[18]和制造[19]方面有着应用。然而，寻找最优切割点的问题属于NP难题[20]，即使是现有的近似方法也可能涉及代价高昂的优化过程[18]或解决复杂的几何问题[21]。通过利用分割过程中的邻接图，我们提供了一种完全组合式、数学上正确的算法，用于识别能够产生圆盘拓扑的曲面切割点，并且可以根据所需的度量标准进行调整（见图1）。虽然我们的方法无法提供最优性保证，但实验表明，其结果与其他基于优化过程的更为昂贵的解决方案相当，而且我们找到的切割点明显短于艺术家手工设计的切割点（见第5节的表2）。总之，通过这项工作，我们提供了一种通用、高效且可靠的流程，用于识别任意曲面上的割集网络。我们的方法是完全组合式的，生成的切割点既可以用于分割网格，也可以用于将其展开为拓扑圆盘。此外，我们的算法具有可证明的数学保障，并且可以通过多种度量标准进行调整，以实现不同的分割和参数化目标。本文的其余部分安排如下：第2节回顾了关于UV映射和网格分解的先前研究。第3节介绍了介绍我们方法所需的背景知识。第4节详细描述了所提出的算法。第5节报告了实验结果以及与现有方法的比较。另外，第6节分析了所提方法对不同网格密度的稳健性以及运行时间性能。最后，第7节讨论了局限性并指出了未来研究的方向。相关工作构建可靠UV贴图的重要性可追溯到计算机图形学的早期[22]，即使在近年来，它依然是几何处理领域中最活跃的研究方向之一[23]、[24]。因此，已经开发出了多种不同的方法来计算曲面的UV参数化[25]。生成UV参数化的标准流程包括先计算曲面的切割点，然后再分别对各个区域进行参数化。背景连续设定。在本工作中，我们将曲面视为嵌入在R3中的二维黎曼流形M，可能带有边界?M。给定曲面上的两点x,y∈M，我们用dM(x,y)表示它们在M上的测地距离。M的一个分割是一个由M的紧凑子流形组成的集合S(M)={S1,…,Sk}，满足?i=1kSi=M且 ?i≠j,Si∩Sj要么为空，要么是一维流形（即一条曲线）。关于曲面和黎曼流形的更多讨论，可参考[51]、[52]。所提出的方法我们用于对网格M=(V,E,T)进行UV参数化的方法可总结如下：1.根据给定的度量标准对曲面进行Voronoi分解（第4.1节）；2.细化分解结果，确保各区域具有圆盘拓扑结构（第4.2.1节），然后选择：(a)合并区域以在保持圆盘拓扑的同时优化目标函数（第4.2.2节）；(b)利用区域边界来识别能够将曲面展开为圆盘的切割点（第4.2.3节）；3.计算每个区域的UV贴图。结果我们使用C++实现了该方法，借助了Eigen [59]和libigl [60]库。源代码可在https://github.com/filthynobleman/comb-uv获取。基准测试对于UV参数化步骤，我们考虑了Eck等人[31]提出的谐波映射算法，后来Liu等人[33]对其进行了改进，加入了尽可能刚性的参数化方式，还有Lèvy等人[32]提出的共形映射技术。对于所有这些算法，我们都依赖于相应的实现版本。分析我们两种方法（即形状分割和曲面切割）的一个主要优势在于它们都是完全组合式的。由于我们的流程不涉及任何数值步骤，因此无论网格的几何结构和连通性如何，我们总能得到有效的曲面分解或有效的切割结果。再加上参数化算法只需以圆盘作为输入，这就保证了我们方法的高可靠性，这一点已通过显著的实验结果得到证实。结论我们扩展了最初在[15]中提出的方法，用于将曲面分割为拓扑圆盘，使分割算法能够根据任何局部定义的度量标准进行指导。我们进一步拓展了这一解决方案，利用圆盘分割来计算能够将曲面展开为拓扑圆盘的切割点。我们的方法是完全组合式的，这使得我们能够为具有任意拓扑结构和几何形状的曲面可靠地计算切割点和分割结果。CRediT作者贡献声明Filippo Maggioli：写作——审阅与编辑，写作——初稿撰写，可视化，验证，软件，方法论，研究，形式分析，概念构思。Simone Melzi：写作——审阅与编辑，写作——初稿撰写，监督，方法论，概念构思。利益冲突声明作者声明没有已知的财务利益或个人关系可能会影响本文所述的工作。Filippo Maggioli目前是Pegaso大学信息科学与技术系的终身助理教授。此前，他曾担任Pegaso大学的兼职教授、米兰-比可卡大学的博士后研究员，以及阿卜杜拉国王科技大学的科研实习生。Filippo于2019年在罗马萨皮恩扎大学获得计算机科学硕士学位，他还在那里完成了题为“可扩展几何处理”的博士论文。Filippo Maggioli|Simone Melzi