特定のタイプの要素（三角形、四面体など）を含むメッシュがあります。各要素について、そのすべての頂点を知っています。つまり、三角形の 2D 要素には、x、y、z 座標がわかっている 3 つの頂点 v1、v2、および v3 があります。
質問1
すべてのエッジを返すアルゴリズムを探しています...この場合:
エッジ (v1、v2)、エッジ (v1、v3)、エッジ (v2、v3)。各要素が持っている頂点の数に基づいて、アルゴリズムはエッジを効率的に決定する必要があります。
質問2
私は C++ を使用しているので、上記のアルゴリズムによって返されたエッジに関する情報を保存する最も効率的な方法は何でしょうか? 例として、私が興味を持っているのは、計算に使用したいタプル (v1, v2) だけです。
ありがとうございました
ハーフエッジ データ構造を使用できます。
基本的に、メッシュにはエッジのリストもあり、各方向の頂点のペアごとに 1 つのエッジ構造があります。つまり、頂点 A と B がある場合、A->B 用と B->A 用の 2 つのエッジ構造がどこかに保存されます。各エッジには 3 つのポインターがあり、1 つは前、1 つは次、もう 1 つはツインと呼ばれます。次および前のポインターをたどると、メッシュ内の三角形またはポリゴンのエッジをたどることができます。Twin を呼び出すと、隣接するポリゴンまたは三角形の隣接するエッジに移動します。(写真の矢印を見てください) これは、私が知っている中で最も便利で詳細なエッジ データ構造です。これを使用して、新しいエッジを作成し、ポインターを更新してメッシュを滑らかにしました。ところで、各エッジは頂点を指す必要があるため、空間内のどこにあるかがわかります。
あなたの質問には、2 つではなく 3 つの部分があります。
適切な答えを見つけるには、追加の質問をする必要があります。
メッシュを表現するには、どのデータ構造を使用する必要がありますか?
どの要素タイプを処理する必要がありますか?
ポリゴン (閉じたループ) とシンプリシアル (すべてのノードが四面体などの要素内の他のすべてのノードに接続されている) のみを処理する必要がある場合は、ノードのリストからエッジを暗示できるため、順序付けられたノード リストで十分です。一方、六面体、プリズム、または一般的な多面体などの要素タイプを処理する必要がある場合は、要素トポロジに関する詳細情報が必要です。多くの場合、エッジ マッピングの単純な配列で十分です。これは、特定の要素タイプのドットを接続する方法を示す、要素のノード リストへのインデックスの単なる配列[][2]です。
Chris によって記述されたハーフエッジ構造は、2D のみに適しています。3D では、2 つだけでなく、任意の数の要素を各エッジに接続できます。風車構造と呼ばれるハーフエッジ表現への 3D 拡張があります。
任意の要素タイプをサポートする必要がある場合は、より完全なデータ構造を使用して要素のトポロジを表現することをお勧めします。一般的なオプションは、エッジと共同エッジを使用することです。接続されたノードのペアごとにエッジ構造があり、要素内でそのエッジを使用するたびに共同エッジがあります。風車のアプローチに似ていますが、もう少し明確です。
要素からエッジを抽出するには、どのアルゴリズムを使用すればよいですか?
速度やメモリはどれくらい重要ですか? 結果には、各エッジを要素ごとに 1 回含める必要がありますか?それとも、それを使用する要素の数に関係なく 1 回だけ含める必要がありますか? 結果のエッジの順序は重要ですか? 各エッジのノードの順序は重要ですか?
各エッジに一度だけアクセスする任意の要素タイプのアルゴリズムを考え出すのは非常に困難です。各エッジが一度だけ表示されるようにするには、結果をフィルタリングするか、少しハックして各エッジに「訪問済み」ビットを保持して、結果に2回貼り付けないようにすることができます。
結果をどのように表現すればよいですか？
結果の使用方法について何が重要ですか?
計算負荷の高い計算で結果を使用する場合は、座標の大きな配列が最適なオプションである可能性があります。計算中にノード座標を何度も再取得する必要はありません。ただし、結果をフィルタリングして重複するエッジを削除する場合、座標の比較 (ノード ペアに対して 6 つの double) は適切ではありません。フィルタリングする場合は、最初にエッジ構造へのポインタのリストを生成し、次に重複を除外してから、座標のリストを生成します。ノード ペアでもこのアプローチを使用できますが、エッジごとに可能な両方のノード順序に対してフィルタリングする必要があり、フィルタリングにかかる時間が 2 倍になります。
パフォーマンスよりもメモリが重要な場合は、エッジ ポインターのリストも有効です。ただし、エッジ リストを座標リストに変換する代わりに、計算中に座標を調べます。その方法ではノード座標の取得は遅くなりますが、大量の座標リストを作成することは避けられます。つまり、エッジごとに 6 つの double ではなく、エッジごとに 1 つのポインターを格納します。
多くのメッシュ アプリケーションは、すべての座標を大きなグローバル配列に格納し、各ノードは配列へのインデックスを持ちます。この場合、エッジ リストを座標配列に変換する代わりに、グローバル座標配列へのインデックスのリストに変換します。パフォーマンスがローカル座標配列から大きくずれることはありませんが、メモリと人口のオーバーヘッドはありません。
アルゴリズムはありませんが、どこを見ればよいかは教えてくれます。
「Point Set Triangulation」はあなたが探しているものです。
これを行ういくつかのオープン ソース ライブラリを次に示します (アルゴリズムのコードを参照してください)。