將3d網格分解爲2d網格

Question

假設您有一個三維對象，以某種常見文件格式表示爲三維網格。你將如何設計一個算法來將網格分解成一個或多個2D網格 - 也就是說，可以剪切並摺疊以創建原始3D對象的二維表示。

除其他事項外，算法將需要考慮：

• 多個可能的分解對於任何給定對象
• 處理網格裝配到固定大小的畫布（紙張）。
• 確認網絡中的兩個面板何時會重疊（因而無效）。
• 由於重疊或頁面大小限制，如果不能將網格表示爲單個網格，則會將網格劃分爲多個網格。
• 在適當的位置生成選項卡，用於附加相鄰的面。

明顯的退化情況是簡單地創建一個網面，每邊都有一個網點，邊上有一半標籤。顯然這並不理想：理想的情況是一個連續的網絡。複雜形狀的現實可能在中間的某個地方。

我意識到尋找最佳網（最少的網/最少的網頁）可能在計算上很昂貴，但尋找「足夠好」的網絡的一個很好的啓發就足夠了。

Answer 1

當我讀到你的問題時，「自動papercraft算法」這個詞來找我。所以我搜索了它，發現了由Massarwi等人發現的Papercraft Models using Generalized Cylinders（pdf）。

我們提出了通過基於 條形逼近的裝置產生的，從 三角網格 圓形玩具動物附圖 展開papercraft圖案的新方法。雖然在 原則三角模型可以通過 保留儘可能多 儘可能它連接的同時 檢查中 展開的平面相交的三角形，創建具有三角形數以萬計的模式 簡單地展開是 不現實的。我們的方法是通過一組 連續三角形條對 進行近似網格模型，而沒有 內部頂點。最初，我們 將我們的網格細分成與 模型的特徵相對應的部分 。我們將每個部分分爲區域 區域，分組的三角形爲 與 部分邊界相似的拓撲距離。我們通過簡化網格生成三角形 條，而 保留區域 區域的邊界和附加的切割線。 圖案然後簡單地通過 展開一組條。 我們的方法 的區別特徵是我們通過一組連續條來近似一個網格模型，而不是通過其他直紋表面，例如圓錐或圓柱體的部分 。因此，僅使用網格操作 和簡單展開算法生成的近似展開圖案可以是 。另外，一組條可以是僅通過彎曲紙 （沒有斷裂邊緣）而製作的 ，並且 可以代表 原始網格模型的平滑特徵。

Shatz等人也有一篇較早的相關論文Paper craft models from meshes（9MB pdf）。

本文介紹了 的算法分割的網格到顯影 近似值。算法可以是用於CAD 和計算機圖形學中的各種應用的 。這篇論文 側重於紙製造，並且 表明算法 生成的近似值是可展開的，容易剪切的，並且可以將 膠合在一起。它也表明 給定的模型和 之間的誤差很小。

來源：http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg

Answer 2

的算法eed3si9n連接會產生很好的合理papercraft從複雜的幾何形狀網格。如果你想展示網格完全按照它的模型，比如多面體模型，那麼這裏有一個相對簡單的技術來展開任何網格，因爲它站立起來

從你的源網格構建一個圖形，其中每個面是一個頂點在圖中，並且如果它們在網格中共享公共邊，則連接兩個頂點。其中一個圖表示一個可展開的網格，當且僅當它沒有循環時，即它是一棵樹。

一棵好樹代表了從起點到達最遠的人臉所需的最少的折線，因爲每個褶皺都代表將在成品模型中積累的誤差。 Dijkstra的算法在這裏很好，但最小生成樹不起作用。每條邊的權重都相等，所有的樹都是最小的生成樹，甚至可以將網格展開成一個大螺旋。當你把模型粘在一起時，錯誤就會積累起來，直到最後幾張臉完全不適合。

一旦你有了這棵樹，開始在原點繪製你的起始臉。然後通過計算新頂點作爲兩個圓的交點，並將半徑與原始網格中邊的長度相對應，然後漫步樹並添加新面。選項卡的位置對應於原始網格中的邊緣，但不在可扁平樹中。

用戶指定的剪切可以在樹步驟之前作爲邊緣刪除進行處理。

該技術的一些缺點是，它會愉快地創建在平坦圖案重疊的部分，並且它依賴於找到一個很好的起點的臉。我試圖用Floyd-Warshal找到一個最小直徑的臉，但是它的O（n^3）行爲會造成過長的咖啡時間。重疊的部分可以通過將樹的分支標記爲「不完整」來處理，跳過它，並且再次在所有不完整的面上重新運行算法。

Answer 3

我知道這不是一個答案，但它是相關的。前SGI圖形傢伙Paul Haeberli的Lamina程序是針對此問題的解決方案。