兩個截面飛機的交集

我試圖找到一種算法來使用兩個（或更多）截面飛機來切割3D對象。只有在兩個截面正在切割的情況下才應該切割該物體。因此，請考慮以下兩個截面平面相交的abcd矩形：s0和s1; s1向右切，s0向上切。我想要的是產生ajikcd形狀。兩個截面飛機的交集

.  |s1 
. a______j_________b^
. |  |   | | 
. |- - - i - - - - |k- - s0 
. |  |   | 
. d----------------c 
.  |->

這是一個相當簡單的例子，但我希望它能夠說明我要完成的任務。另外，這應該在3D中完成。

有沒有人知道任何這樣做的庫，或者一個算法來做到這一點？這似乎是某人必須在我之前解決的一個不平凡的問題！ :)

我必須補充一點，我知道如何做基本知識（平面與面/平面/邊的交點）。我無法看到的是，是否有一種巧妙的方式來解決所有可能的情況（在這一個中，必須添加兩個面孔，但在其他一些面孔中可能只創建一個面孔等），或者如果你應該處理它們分別。

我應該補充的另一件事是我不關心渲染部分，我知道如何使用帶剪切平面的OpenGL進行渲染。我想要的是能夠計算對象的新拓撲。

來源

2012-10-09 seb

什麼樣的對象是你分開？你如何描述輸入和結果？對於多邊形來說，這很簡單，但是你的表述「這應該用3D來完成」表明你實際上對固體或類似物感興趣。一般來說，關鍵字[Constructive Solid Geometry]（http://en.wikipedia.org/wiki/Constructive_solid_geometry）會描述您的任務和相關任務，因此請查找CSG庫。 SO上還有一個[csg標籤]（http://stackoverflow.com/questions/tagged/csg）。 – MvG

感謝您使用CSG關鍵字！我正在切割3D固體物體，大部分是平行六面體。我的對象被描述爲他們臉部的添加，所以輸入是一個面陣列，而一個臉部基本上是一個3D點陣列。當我用一個單獨的平面切割時，我會分別處理每個面並遍歷每個分段，並相應地變換每個分段（有時向面部添加一個點）。這很好。我希望能夠爲幾架飛機做類似的事情...... – seb

我認爲這可以相當容易地解決方法是切片對象，刪除不需要的部分，然後通過合併面膠合剩下的部分。

假設你模擬你的對象作爲一個完全連接的圖形

頂點的列表，每個邊的列表
邊緣的列表，每兩個頂點和兩個面引用
面的名單，每邊

只要你是在維護和操作該圖細心的列表，它擁有快速剪切和濱海所需的所有信息ge你的對象。

您可以使用this answer中描述的算法來計算剪切後產生的新臉部。

因此：您對算法的輸入是切割平面列表和對象列表 - 最初只有一個。對於每個切割平面，將列表對象中的每個對象分成兩部分並將它們放回到列表中。添加的兩個面（每個新對象都有一個面）應該保留對產生它們的切割面的引用。對於由平面切成兩半的面，請記住，生成的兩個新面應該繼承此引用（如果存在）。新對象應該記錄它們所在平面的哪一側（只是布爾含義爲「保留」或「丟棄」） - 這些記錄還應該在對象進一步細分時保留。

所有切割完成後，您將獲得一個對象列表，其中每個對象都有一個記錄列表，詳細列出了他們所在切割平面的哪一側。查找所有這些記錄「丟棄」並丟棄的對象。我們現在不得不將物體粘在一起。

從簡單合併對象圖開始 - 只需將所有頂點，邊和列表組合到一個對象中即可。我們現在檢查由同一個切割平面創建的兩個面：

如果兩個面相同（即：它們共享同一組頂點），則可以移除兩個面和所有關聯的邊。
如果一個人臉的頂點集大於另一人的臉，則刪除較小的人臉和所有共享邊。

您現在應該有一個合併對象，但有一些無關的頂點。簡單地遍歷頂點並去除那些只有兩個相關邊的元素。

這裏的切割將如何工作的例子：

 : 
a---1-:---b 
|  : | 
2 X : 3 
|  : | 
|  : | 
c---4-:---d 
     : 
     :s

我們先從一個對象（？代表的一些邊緣或面未顯示）：

verts: 
    a:1,2,? 
    b:1,3,? 
    c:2,4,? 
    d:3,4,? 
edges: 
    1:a,b X,? 
    2:a,c X,? 
    3:b,d X,? 
    4:c,d X,? 
faces: 
    X:1,2,3,4 
    ?:...

當我們切斷與平面s，我們結束了兩個對象：

a--1--e-7-b 
|  | | 
2 X 5 Y 3 
|  6 | 
|  | | 
c--4--f-8-d 

verts:   verts:   
    a:1,2,?   e:1,5,6,7  
    e:1,5,6,7   b:3,7,?   
    c:2,4,?   d:3,8,?   
    f:4,5,6,8   f:4,5,6,8  
edges:   edges:   
    1:a,e X,?   3:b,d Y,?  
    2:a,c X,?   6:e,f Y,W  
    4:c,f X,?   7:e,b Y,?  
    5:e,f X,V   8:f,d Y,?  
faces:   faces:   
    X:1,2,3,4   Y:3,6,7,8  
    V:5,...   W:6,...  
    ?:...    ?:...

我們已經添加了頂點e和f，邊5和6以及fac es V和W.請注意，邊5和6是不同的對象，共享相同的頂點，但在不同的面之間。

當我們來到這兩個對象合併到一起，我們首先平凡合併兩個對象圖：

verts: 
    a:1,2,? 
    b:3,7,?   
    c:2,4,? 
    d:3,8,? 
    e:1,5,6,7   
    f:4,5,6,8 
edges: 
    1:a,e X,?   
    2:a,c X,?   
    3:b,d Y,?  
    4:c,f X,?   
    5:e,f X,V   
    6:e,f Y,W  
    7:e,b Y,? 
    8:f,d Y,?  
faces: 
    X:1,2,3,4 
    Y:3,6,7,8  
    V:5,...   
    W:6,...  
    ?:...

我們可以看到，面對V和W是由相同的切削平面製作，並且具有相同頂點集合，因此可以將它們與關聯的邊緣一起移除。與一對重合邊緣相關聯的兩個未移除面合併。

a--1--e-7-b 
|   | 
2 X  3 
|   | 
|   | 
c--4--f-8-d 

verts: 
    a:1,2,? 
    b:3,7,?   
    c:2,4,? 
    d:3,8,? 
    e:1,7   
    f:4,8 
edges: 
    1:a,e X,?   
    2:a,c X,?   
    3:b,d X,?  
    4:c,f X,?  
    7:e,b X,? 
    8:f,d X,?  
faces: 
    X:1,2,3,4,7,8 
    ?:...

然後，我們可以只用兩個相關邊緣去除的頂點，併合並那些邊緣：

verts: 
    a:1,2,? 
    b:1,3,?   
    c:2,4,? 
    d:3,8,? 
edges: 
    1:a,e X,?   
    2:a,c X,?   
    3:b,d Y,?  
    4:c,d X,? 
faces: 
    X:1,2,3,4 
    Y:3,6,7,8 
    ?:...

有關合並這些對象是什麼？

a--1--e 
|  5 
2 X g-3-b 
|  6 | 
|  9 Y 7 
c--4--f-8-d 

verts:   verts:   
    a:1,2,?   g:3,5,6,?  
    e:1,5,?   b:3,7,?   
    c:2,4,?   d:7,8,?   
    f:4,6,8,9,?  f:4,6,8,9,? 
edges:   edges:   
    1:a,e X,?   3:b,g Y,?  
    2:a,c X,?   9:f,g Y,W  
    4:c,f X,?   7:b,d Y,?  
    5:e,g X,V,?  8:f,d Y,?  
    6:f,g X,V 
faces:   faces:   
    X:1,2,4,5,6  Y:3,7,8,9 
    V:5,6,...   W:9,...  
    ?:...    ?:...

我們合併：

verts: 
    a:1,2,?  
    b:3,7,?    
    e:1,5,?   
    c:2,4,?   
    d:7,8,?   
    f:4,6,8,9,?   
    g:3,5,6,9,?  
edges: 
    1:a,e X,?   
    2:a,c X,?   
    3:b,g Y,?  
    4:c,f X,?   
    5:e,g X,V,?   
    6:f,g X,V 
    7:b,d Y,?  
    8:f,d Y,?  
    9:f,g Y,W  
faces: 
    X:1,2,4,5,6 
    Y:3,6,7,8  
    V:5,6,... 
    W:9,... 
    ?:...

，檢查面V和W，因爲他們已經通過同樣的剖切面創建。這次他們的頂點集合是不同的。刪除較小的臉。在兩個面，查找具有相同的頂點的邊緣，將其刪除：

a--1--e 
|  5 
2 X g-3-b 
|   | 
|   7 
c--4--f-8-d 

verts: 
    a:1,2,?  
    b:3,7,?    
    e:1,5,?   
    c:2,4,?   
    d:7,8,?   
    f:4,8   
    g:3,5,?  
edges: 
    1:a,e X,?   
    2:a,c X,?   
    3:b,g X,?  
    4:c,f X,?   
    5:e,g X,V,? 
    7:b,d X,?  
    8:f,d X,? 
faces: 
    X:1,2,3,4,5,7,8 
    V:5,... 
    ?:...

我們現在可以只用兩個關聯邊刪除無用的頂點：

a--1--e 
|  5 
2 X g-3-b 
|   | 
|   7 
c----4----d 

verts: 
    a:1,2,?  
    b:3,7,?    
    e:1,5,?   
    c:2,4,?   
    d:4,7,? 
    g:3,5,?  
edges: 
    1:a,e X,?   
    2:a,c X,?   
    3:b,g Y,?  
    4:c,d X,?   
    5:e,g X,? 
    7:b,d X,? 
faces: 
    X:1,2,3,4,5,7 
    V:5,... 
    ?:...

唷！希望這有助於...

來源

2012-10-12 10:58:55 ryanm

我結束了使用另一種解決方案，但你的建議幫助了我;謝謝！ – seb

兩個截面飛機的交集

回答

相關問題