將重疊的三角形合併爲一個多邊形

我從投影到二維平面的3D模型中獲得了一堆重疊的三角形。我需要將觸摸三角形的每個島合併爲一個封閉的非凸多邊形。將重疊的三角形合併爲一個多邊形

結果多邊形不應該有任何洞（因爲源數據沒有）。

許多源三角形與源數據中的其他三角形共享（浮點相同）邊。

這樣做最簡單的方法是什麼？性能不是特別重要，因爲這將在設計時完成。

2010-05-12 nornagon

參見「複雜的多邊形的聯盟」：http://stackoverflow.com/questions/2667748/union-of-complex-polygons – unutbu 2010-05-12 19:50:30

嘗試gpc，或一般多邊形帆船庫。

2010-05-12 12:18:00 lhf

不幸的是，這將在商業遊戲中使用;不確定U曼徹斯特會如何看待這一點。 – nornagon 2010-05-12 22:35:56

gpc也有商業許可。此外，gpc在http://www.cs.man.ac.uk/~toby/alan/software/#Links上列出了其他類似的庫。也許其中一個擁有更適合的許可證。 – lhf 2010-05-12 23:05:29

想象投影到一個平面上的模型的「視圖」（即投影的方向是視線，並且所述突出部你看到的）。在這種情況下，要計算的多邊形的邊界對應於模型的輪廓。

輪廓反過來是模型中的一組邊。對於輪廓中的每個邊緣，相鄰的面都將具有法線，該法線指向遠離平面或朝向平面。您可以檢查這是將面法線的點積與平面法線相乘 - 查找相鄰面法線具有與投影方向相反符號的點積的邊。

一旦你找到了所有的輪廓邊，你可以將它們連接在一起進入所需多邊形的邊界。

一般情況下，你可以通過google搜索術語如mesh silouette finding detection找到更多關於輪廓檢測和提取。也許一個好的開始是here。

2010-05-12 12:49:29 brainjam

這並不完全適用 - 例如，我有幾個模型零件的投影重疊。 – nornagon 2010-05-12 23:56:38

@nomagon，好點。另外，你的模型是否關閉？即他們是否有像球體或圓環一樣的內部和外部？或者他們只是一個普通的多邊形湯？ – brainjam 2010-05-13 02:58:44

我也發現這個[1]方法，我將在下一步嘗試。

2010-05-12 22:39:08 nornagon

回答