由邊緣環

Question

分割3D模型我有一個3D模型，代表的是這樣的：

class Vertex 
{ 
    double x, y, z; 
} 

class Edge 
{ 
    Vertex *v1, *v2; // no particular order 
    Face *f1, *f2; // no particular order. f2 may be null. 
} 

class Face 
{ 
    List<Vertex*> vertices; // clockwise order 
    List<Edge*> edges; // clockwise order 
} 

class Model 
{ 
    List<Face*> faces; 
    List<Vertex*> vertices; 
    List<Edge*> edges; 
} 

當然，這可以轉化成任何表示是最方便的。

我想將這個模型分成幾個不連貫的部分，沿着多個連接邊的循環，並創建新的面來蓋住兩端。實施例與一個循環：

新的面孔應在相同的位置，並從它們與其他面的連接分開相同的，但是在這個例子中我已經移動分開它們。我怎麼能這樣做？

如果頂點在其他不連接的部分之間共享，則無關緊要。

由於每條邊都恰好連接兩個面，我試着將每條邊分別分成兩份（每張面一張）。這根據需要將模型分開，但是我看不到正確添加新面部的方法。

這個問題被標記爲圖算法，因爲這個問題看起來好像與圖論有某種關係。

Answer 1

• 修復您的模型。 class Edge應該保持指向Face和Vertex而不是值。
• 您想在class Model內使用某種set而不是List。這有助於查找和刪除東西，並確保沒有重複。

• 想出你的函數原型。我建議

pair<Model*, Model*> split_model(const Model* mx, const List<Edge*>& loop); 

• 創建兩個新的，空的車型，說ma和mb。將loop的邊添加到每個邊上。
• 從loop挑選一條邊。讓我們稱之爲fa和fb。
• 將fa加到模型ma。從fa開始，按照附加到fa的所有邊以及附加到這些邊的所有面，執行完整的圖搜索，依此類推。必須遵循所有遇到的面和邊，並將其添加到型號ma。如果您遇到已經是ma的一部分的面或邊，則不需要遵循它們。特別是當你遇到屬於loop的邊緣時，會發生什麼情況，所以你永遠不會越過邊界。通過這種方式，您可以在一側對所有邊和麪進行完整搜索，最終得到一個完整的模型ma。最後你添加一張代表剪輯的面孔。這裏可以忽略頂點，但最後你可能想要添加屬於你添加的面的所有頂點。
• 重複此步驟從面fb開始創建代表另一部分的模型mb。