siggraph2019 2 Navigating Intrinsic Triangulations.pdf

### 导航内在三角剖分：一种用于处理低质量表面网格的数据结构 #### 摘要与背景 本文介绍了一种新的数据结构，该结构使我们能够在极端低质量的表面网格上运行计算几何和科学计算中的大量算法。传统上，为了解决网格质量问题，人们通常会改变网格的几何形状（例如通过重新网格化）。然而，在这项工作中，研究者考虑了一种不同的方法——内在三角剖分，这种方法利用输入网格的确切几何形状来连接顶点。具体来说，这种三角剖分是通过沿着输入网格表面上的直线路径来连接顶点。 #### 内在三角剖分的关键概念 内在三角剖分的核心在于其编码方式：它存储了从一个顶点到其相邻顶点的方向和距离。这种方法使得可以隐式地表示内在三角剖分，进而使得在不显式构建覆盖网格的情况下进行几何和拓扑查询成为可能。此外，这种方法只使用常量内存，因此在处理大规模数据集时非常高效。 #### 数据结构的实现 该文提出的数据结构被命名为“路标”（signpost）数据结构。它支持一系列基本操作，如顶点插入、边分割等，这些操作类似于普通三角网格的操作。这使得现有的算法可以很容易地转换到内在设置中。通过这种数据结构，用户可以在需要时按需追踪路径，从而在表面上执行各种操作。值得注意的是，除非特别请求，否则无需显式构建覆盖网格。 #### 应用案例 为了验证这一数据结构的有效性，研究团队实施了一系列基础几何算法，包括： 1. **内在Delaunay细化**：这是一种用于改善网格质量的技术。传统的Delaunay细化算法依赖于显式的网格重构，而内在版本则能够处理更加退化的输入。 2. **最优Delaunay三角剖分**：这是另一个重要的优化技术，它可以生成具有最优质量的三角形。 3. **Steiner树逼近**：Steiner树问题是在图中寻找包含所有终端节点且总长度最小的连通子图的问题。内在Steiner树逼近可以用来优化网络或路径规划问题。 4. **适应性网格细化**：对于偏微分方程的数值求解而言，适应性网格细化是一种关键的方法，它可以根据解的局部特征动态调整网格的精细度。 5. **泊松方程求解**：泊松方程是偏微分方程的一种形式，广泛应用于物理模拟中。内在方法可以提高解的质量并减少计算资源的需求。 6. **测地线距离计算**：测地线距离是指两点间沿曲面最短路径的距离。内在方法可以更准确地计算这种距离。 7. **无翻转切向量场**：在图形学中，切向量场对于纹理映射和形状分析非常重要。无翻转切向量场确保了纹理映射的一致性和高质量。 #### 性能评估 研究团队使用Thingi10k数据集对这一数据结构进行了性能评估。Thingi10k数据集包含了大量的人工制造物体模型，这些模型在网格质量方面差异很大，既有高质量网格也有极低质量的网格。通过这一评估，研究人员展示了他们的数据结构不仅能够在处理这些低质量网格时表现出色，而且还可以有效地运行多种几何算法。 #### 结论 “导航内在三角剖分”提供了一种新颖而有效的方式来处理低质量网格数据，这对于图形学、科学计算以及计算机辅助设计等领域都有着重要意义。通过引入隐式编码和“路标”数据结构，研究者们不仅解决了传统网格化方法中的局限性，而且还开发出了一种灵活、高效的工具，能够在实际应用中发挥重要作用。