網狀結構的網格簡化

Question

我正在研究3D建築應用。該建築是在3D網格上完成的（如魔方），並且網格的每個單元格都是實心立方體或45度斜坡。爲了說明這一點，這裏有一個倒角立方體我脫下谷歌圖像的畫面：

忽略圖像的權利，重點是左邊的一個。目前，在建築階段，我將每個單元的每個面分別繪製。但是，出口它時，我想簡化它。所以在上面的立方體中，我希望上下左右後部正面由每個單個四邊形（兩個三角形）組成，並且邊緣將從兩個四邊形減少爲單個四邊形。

我一直在試圖最近做的是以下幾點：

迭代通過層形狀層，從各個方向，併爲每個層拿捏好簡化（刪除重疊的邊緣以創建單個多邊形，然後拆分多邊形以避免出現孔，使用耳廓裁剪來進行三角測量）。

我是明確在複雜的事情（至少我希望我是）。如果我有一個頂點，法線和索引列表（目前有很多重複的頂點），是否有一些簡潔的方法來簡化？限制是指數之間不能共享（因爲我需要法向指向不同的方向），但否則我不介意它是不是最快或最理想的解決方案，我寧願它很容易實現並保持。

編輯：只是爲了進一步澄清，我已經執行隱藏的臉部刪除，這不是一個問題。其次，最重要的是質量沒有降低，只有簡化臉部本身（我需要保留鋒利的邊緣）。

Answer 1

感謝羅傑羅蘭的偉大提示！如果有人對此提出疑問，下面簡要總結我的工作：

首先要解決的問題：確保您試圖簡化的網格是一個多面體網格！這是遍歷半邊數據結構的要求。一個我遇到問題的例子是四邊形和三角形的重疊;我最初決定只留下四邊形，而不是將它們分割成三角形，因爲它更容易，但是這會導致打破半邊網格的邊緣。

一旦網格是流形，從頂點和麪創建一個半邊網格。

完成後，抽取網格。我通過邊緣塌陷來確定哪些邊緣會通過正常偏差（在我的情況下，如果塌陷產生的面的法線與原始值不等於原始值，則不會執行塌陷）崩潰。

我是通過我自己的實現開始的，但是我開始遇到令人沮喪的錯誤，因此選擇使用OpenMesh（它很容易開始使用）。

還有一個問題我還沒有解決：如果對角線上有兩個立方體相互碰觸，結果是一個有四個面相連的邊：一個複雜的邊！我懷疑，通過遍歷邊來檢查連接的面的數量，然後通過複製適當的頂點來解決是微不足道的。但有了這些說法，我不打算花時間來解決問題，除非它在以後成爲關鍵問題。

Answer 2

Google「網格簡化」。你會發現這個問題是一個巨大的問題，並且經過深入研究。看看這些介紹性資源：link（第11頁開始好東西）和link。 CGAL也有很好的討論：link。

一旦熟悉了這些問題，您將會對將簡化應用於您的問題做出一些決定。簡化應該多快？準確性有多重要？ （迭代頂點聚類是一種快速和骯髒的方法，但其結果可能是任意醜陋的。）您可以依賴第三方庫嗎？ （即CGAL？GTS不再有效，但還有其他）。