部分曲面重建

Question

我需要一個算法來修復3D三角網格。期望的條件是2n個三角形（大部分時間是2個三角形）共享邊緣。與之相反，輸入網格在邊緣包含2n + 1個三角形（1,3，...）的情況。我 已經實施了一些啓發：

• 關閉頂點（由於舍入誤差）被合併成一個。

• 如果以後可以將新頂點與合理的另一個合併，則可以拆分邊緣。

• 孔被三角化到某個面積閾值。

這工作得很好了許多輸入（I關心selfintersections在 後一階段），但也有網格，其中這些啓發式失敗。主要問題是修復邊緣並不是一個只有局部後果的決定：每個創建的三角形都會減少可供後續修復步驟使用的邊緣集。因此，只有一個不好的決定可能會導致一系列連續的故障。

這個問題似乎接近表面重構問題，但我已經有大部分表面，所以需要一個尊重現有三角形的部分重建算法。有任何想法嗎？

Answer 1

與其讓三角形創造不可逆轉，你可以做有限的組合探索，動態編程風格。您可以爲每個操作（也可能是結果）分配一個成本，以評估哪個組合在任何特定階段最有前途。

大概大多數情況下會被本地化，並且不需要動態編程的全部功能（和費用）。但是，需要多個相關操作的案例可以同時進行探索，並從那些實現關閉的案例中選出最好的半局部解決方案。