部分曲面重建

Question

我需要一个算法来修复3D三角网格。期望的条件是2n个三角形（大部分时间是2个三角形）共享边缘。与之相反，输入网格在边缘包含2n + 1个三角形（1,3，...）的情况。我 已经实施了一些启发：

• 关闭顶点（由于舍入误差）被合并成一个。

• 如果以后可以将新顶点与合理的另一个合并，则可以拆分边缘。

• 孔被三角化到某个面积阈值。

这工作得很好了许多输入（I关心selfintersections在 后一阶段），但也有网格，其中这些启发式失败。主要问题是修复边缘并不是一个只有局部后果的决定：每个创建的三角形都会减少可供后续修复步骤使用的边缘集。因此，只有一个不好的决定可能会导致一系列连续的故障。

这个问题似乎接近表面重构问题，但我已经有大部分表面，所以需要一个尊重现有三角形的部分重建算法。有任何想法吗？

Answer 1

与其让三角形创造不可逆转，你可以做有限的组合探索，动态编程风格。您可以为每个操作（也可能是结果）分配一个成本，以评估哪个组合在任何特定阶段最有前途。

大概大多数情况下会被本地化，并且不需要动态编程的全部功能（和费用）。但是，需要多个相关操作的案例可以同时进行探索，并从那些实现关闭的案例中选出最好的半局部解决方案。