1

我需要一种算法来修复 3D 三角形网格。期望的条件是 2n 个三角形（大多数时候是 2 个三角形）共享一条边。相比之下，输入网格包含在边 2n+1 个三角形 (1,3,..) 的情况。我已经实施了一些启发式方法：

  • 关闭的顶点（由于舍入错误）合并为一个。

  • 如果之后新顶点可以与其他合理的顶点合并，则边界边会被分割。

  • 孔被三角测量到某个区域阈值。

这对于许多输入都非常有效（我在稍后阶段关心自相交），但是有些网格在这些启发式方法中失败了。主要问题是修复边不是仅具有局部后果的决定：每个创建的三角形都会减少可用于后续修复步骤的边集。因此，只有一个错误的决定可能会导致一系列连续的错误。

这个问题似乎接近于曲面重建问题，但我已经拥有了大部分曲面，因此需要一种尊重现有三角形的部分重建算法。有任何想法吗？

4

1 回答 1

1

您可以进行有限的组合探索，动态编程风格，而不是使三角形创建不可逆。您可以为每个操作（也可能为结果）分配成本，以评估在任何给定阶段哪些组合最有希望。

大概大多数情况都是本地化的，并且不需要动态编程的全部功能（和费用）。但是，可以并行探索需要多个依赖操作的案例，并从实现闭合的案例中选择最佳的半本地解决方案。

于 2012-10-02T18:16:12.307 回答