Loading article…
クワッドエッジデータ構造は、 2次元または3次元マップのトポロジー、つまり（閉じた）曲面上に描かれたグラフのコンピュータ表現です。これは、ホルヘ・ストルフィとレオニダス・J・ギバスによって最初に記述されました。[ 1 ]これは、以前のウィングドエッジデータ構造の変種です。
四辺形構造の基本的な考え方は、閉じた多角形メッシュトポロジーにおいて、1つの辺がちょうど2つの面とちょうど2つの頂点の間に存在するという認識に基づいている。
クワッドエッジデータ構造は、エッジと、隣接する頂点および面の周囲で接続されているエッジを表し、グラフのトポロジーをエンコードします。クワッドエッジデータ型の実装例は次のとおりです。
typedef struct { quadedge_ref e [ 4 ]; } quadedge ;typedef struct { quadedge * next ; unsigned int rot ; } quadedge_ref ;各四角形エッジには、隣接する四角形エッジへの参照が4つ含まれています。4つの参照はそれぞれ、頂点または面の周りを反時計回りにたどった次のエッジを指しています。これらの参照はそれぞれ、エッジの始点となる頂点、右側面、終点となる頂点、または左側面を表します。各四角形エッジ参照は、四角形エッジと、それが指す「アーム」の回転角度（0～3）を指しています。
この表現により、四辺形エッジは次のようになります。
クワッドエッジ構造は、その格納方法の一般的なメカニズムからその名が付けられています。単一のエッジ構造は、概念的には最大2つの面、2つの頂点、および4つのエッジへの参照を格納します。格納される4つのエッジは、格納された2つの面に接続されている2つの頂点から始まるエッジです。
翼状エッジと同様に、四角形エッジ構造は、2Dまたは3D多角形メッシュのトポロジーを格納するためにプログラムで使用されます。有効な四角形エッジ構造を形成するために、メッシュ自体が閉じている必要はありません。
四辺構造を使用すると、トポロジーの反復処理は非常に簡単です。四辺トポロジーへのインターフェースは、多くの場合、有向エッジを介して行われます。これにより、2つの頂点に明示的な名前（開始と終了）を付けることができ、面にも明示的な名前（開始に立って終了の方向を見ている人を基準とした左と右）を付けることができます。4つのエッジにも、頂点と面に基づいて、開始左、開始右、終了左、終了右という名前が付けられます。有向エッジを反転させることで、反対方向のエッジを生成できます。
特定の面を周回するには、その面が左側にある単一の有向エッジ（慣例による）を用意し、開始位置の左側にあるすべてのエッジをたどって、元のエッジに到達するだけでよい。