Loading article…
クワッドエッジ データ構造は、 2次元または3次元マップのトポロジ、つまり（閉じた）表面上に描かれたグラフのコンピュータ表現です。これは、 Jorge StolfiとLeonidas J. Guibasによって最初に説明されました。[1]これは、以前のウィングドエッジデータ構造 のバリエーションです。
概要
四辺形エッジ構造の基本的な考え方は、閉じたポリゴン メッシュ トポロジ内の単一のエッジが、正確に 2 つの面と 2 つの頂点の間にあるという認識です。
四辺形エッジデータ構造は、グラフのトポロジーをエンコードするために、隣接する頂点と面の周囲で接続されたエッジとともにエッジを表します。四辺形エッジデータ型の実装例は次のとおりです。
typedef struct { quadedge_ref e [ 4 ]; }四辺形エッジ;
typedef struct { quadedge * next ; unsigned int rot ; } quadedge_ref ;
各四角形エッジには、隣接する四角形エッジへの参照が 4 つ含まれています。4 つの参照はそれぞれ、頂点または面の周りを反時計回りに次のエッジを指します。これらの参照はそれぞれ、エッジの元の頂点、右面、目的の頂点、または左面のいずれかを表します。各四角形エッジ参照は、四角形エッジと、それが指す「アーム」の回転 (0 から 3) を指します。
この表現により、四辺形エッジは次のようになります。
- グラフ、その双対、およびその鏡像を表します。
- グラフの双対は、頂点と面に関する慣習を単純に逆転させることで得られる。
- 1 次と 2 次の頂点と面を許容する、最も一般的な形式のマップを表すことができます。
詳細
クアッドエッジ構造は、それらを格納する一般的なメカニズムからその名前が付けられています。 概念的には、1 つのエッジ構造に、最大 2 つの面、2 つの頂点、および 4 つのエッジへの参照が格納されます。 格納される 4 つのエッジは、格納された 2 つの面に接続されている 2 つの頂点から始まるエッジです。
用途
Winged Edgeと同様に、quad-edge 構造は、2D または3D ポリゴン メッシュのトポロジを格納するためにプログラムで使用されます。有効な quad-edge 構造を形成するために、メッシュ自体が閉じている必要はありません。
四辺形エッジ構造を使用すると、トポロジーの反復処理が非常に簡単になります。多くの場合、四辺形エッジ トポロジーへのインターフェイスは、有向エッジを介して行われます。これにより、2 つの頂点に明示的な名前 (開始と終了) が付けられ、面にも明示的な名前が付けられます (開始に立って終了の方向を見ている人に対して左と右)。4 つのエッジにも、頂点と面に基づいて、開始左、開始右、終了左、終了右という名前が付けられます。有向エッジを反転して、反対方向のエッジを生成することができます。
特定の面の周りを反復処理するには、その面が左側にある単一の有向エッジ (慣例により) を用意し、元のエッジに到達するまですべての開始左エッジを通過するだけです。