0

2 つ (またはそれ以上) の断面平面を使用して 3D オブジェクトをカットするアルゴリズムを見つけようとしています。オブジェクトは、両方の断面が切断されている場所でのみ切断する必要があります。したがって、2 つのセクション平面 s0 と s1 が交差する次の abcd 長方形を考えてみましょう。s1 は右方向にカットし、s0 は上方向にカットします。私が望むのは、結果の ajikcd 形状を持つことです。

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

これは非常に単純化された例ですが、私が何を達成しようとしているのかが明確になることを願っています。さらに、これは 3D で行う必要があります。

それを行うライブラリ、またはそれを行うアルゴリズムを知っている人はいますか? これは、私の前に誰かが解決したに違いない重要な問題のようです! :)

基本（面/面/エッジとの平面の交差）を行う方法を知っていることを付け加えなければなりません。私が見ることができないのは、考えられるすべてのケースを解決するスマートな方法があるかどうか (このケースでは 2 つの面を追加する必要がありますが、他のいくつかの面では 1 つの面しか作成できないなど)、またはそれらを処理する必要があるかどうかです。別々に。

追加する必要があるもう 1 つのことは、レンダリング部分については心配していないということです。クリッピング プレーンを使用して OpenGL でレンダリングする方法を知っています。私が望むのは、オブジェクトの新しいトポロジを計算できるようにすることです。

4

1 に答える 1

0

これは、オブジェクトをスライスし、不要な部分を削除してから、面をマージして残りの部分を接着することで、かなり簡単に解決できると思います。

オブジェクトを完全にリンクされたグラフとしてモデル化していると仮定します

  • 頂点のリスト。それぞれにエッジのリストがあります。
  • それぞれが2つの頂点と2つの面を参照するエッジのリスト
  • それぞれがエッジのリストを持つ面のリスト

このグラフの保守と操作に注意を払っている限り、オブジェクトをすばやく切り取ってマージするために必要なすべての情報が保持されます。

この回答で説明されているアルゴリズムを使用して、カットの結果として生じる新しい面を計算できます。

つまり、アルゴリズムへの入力は、切断面のリストとオブジェクトのリストです。最初は1つだけです。切断面ごとに、リストオブジェクト内の各オブジェクトを2つにスライスし、リストに戻します。追加される2つの面（新しいオブジェクトのそれぞれに1つ）は、それらを生成した切断面への参照を保持する必要があります。平面によって半分にカットされた面の場合、生成された2つの新しい面は、この参照が存在する場合はそれを継承する必要があることに注意してください。新しいオブジェクトは、平面のどちら側にあるかを記録する必要があります（ブール値は「保持」または「破棄」を意味します）。これらの記録は、オブジェクトがさらに細分化されるときにも保持する必要があります。

すべてのカットが完了すると、オブジェクトのリストが作成されます。各オブジェクトには、カット面のどちら側にあるかを詳細に示すレコードのリストがあります。それらのレコードがすべて「破棄」されているオブジェクトを見つけて、それらを破棄します。

ここで、オブジェクトを元に戻す必要があります。

オブジェクトグラフを簡単にマージすることから始めます。頂点、エッジ、面のすべてのリストを1つのオブジェクトに結合するだけです。ここで、同じ切断面によって作成された2つの面を調べます。

  • 2つの面が同一である場合（つまり、同じ頂点のセットを共有している場合）、両方の面と関連するすべてのエッジを削除できます。
  • 一方の面の頂点セットがもう一方の面よりも大きい場合は、小さい方の面とすべての共有エッジを削除します。

これで、マージされたオブジェクトが作成されますが、いくつかの無関係な頂点があります。単純に頂点を反復処理し、関連するエッジが2つしかない頂点を削除します。

カットがどのように機能するかの例を次に示します。

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

1つのオブジェクトから始めます（？は表示されていないエッジまたは面を示します）：

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で切断すると、2つのオブジェクトになります。

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、および面VとWを追加しました。エッジ5と6は別個のオブジェクトであり、同じ頂点を共有しますが、異なる面間であることに注意してください。

これらの2つのオブジェクトをマージして戻す場合、最初に2つのオブジェクトグラフを簡単にマージします。

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は同じ切断面で作成され、同じ頂点セットを持っているため、関連するエッジとともに削除できることがわかります。一致するエッジのペアに関連付けられた2つの削除されていない面がマージされます。

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
  ?:...

次に、2つのエッジが関連付けられている頂点を削除し、それらのエッジをマージできます。

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を調べます。今回はそれらの頂点セットが異なります。小さい方の顔を削除します。2つの面で、同じ頂点を持つエッジを見つけて削除します。

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,...
  ?:...

これで、入射エッジが2つしかない不要な頂点を削除できます。

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-12T10:58:55.767 に答える