ポリゴンメッシュ

コンピュータグラフィックスにおける頂点とは、サーフェス上の 2、3、または 4D空間における点の位置を、オプションの属性 (オブジェクトを正しくレンダリングするために使用されるその他の値) とともに記述するデータ構造です。頂点のほとんどの属性は、レンダリング対象空間内のベクトルを表します。これらのベクトルは通常 2 ( x, y ) または 3 ( x, y, z ) 次元であり、4 番目の同次座標( w )を含むことができます。リアルタイムレンダリングでは、これらのプロパティは頂点シェーダーまたは頂点パイプラインによって使用されます。

属性には、位置、色、反射率、鏡面反射率、テクスチャマッピング座標、 法線ベクトル、および変位マッピングが含まれます。

頂点メッシュは、オブジェクトを他の頂点と接続された頂点の集合として表現します。これは最も単純な表現方法ですが、面とエッジの情報が暗黙的であるため、広くは使用されていません。そのため、レンダリング用の面のリストを生成するには、データを走査する必要があります。さらに、エッジや面に対する操作も容易ではありません。

しかし、VVメッシュは、ストレージ容量が少なく、形状のモーフィングが効率的であるという利点があります。上の図は、VVメッシュで表現された四角形のボックスを示しています。各頂点は、隣接する頂点をインデックス付けします。「ボックスシリンダー」の上部と下部の中心にある最後の2つの頂点、8と9は、5つではなく4つの頂点に接続されています。一般的なシステムは、任意の頂点に接続された任意の数の頂点を処理できる必要があります。

VVメッシュの詳細な説明については、Smith（2006）を参照してください。^{[ 2 ]}

面・頂点メッシュは、オブジェクトを面の集合と頂点の集合として表現します。これは最も広く使用されているメッシュ表現であり、現代のグラフィックスハードウェアが通常受け入れる入力形式です。

面-頂点メッシュは、面の頂点と、その頂点を取り囲む面を明示的に参照できるため、モデリングにおいてVVメッシュよりも優れています。上の図は、「ボックス-シリンダー」の例をFVメッシュとして示したものです。頂点v5は、それを囲む面を示すために強調表示されています。この例では、すべての面が正確に3つの頂点を持つ必要があることに注意してください。ただし、これはすべての頂点が同じ数の周囲面を持つことを意味するものではありません。

レンダリングの場合、面リストは通常​​、頂点へのインデックスのセットとしてGPUに送信され、頂点は位置/色/法線構造として送信されます（図では位置のみが示されています）。この方法の利点は、面の接続性を更新することなく、頂点データを再送信するだけで、形状の変化（ジオメトリの変化ではない）を動的に更新できることです。

モデリングでは、すべての構造を容易に走査できることが求められます。面・頂点メッシュでは、面の頂点を簡単に見つけることができます。また、頂点リストには、各頂点に接続されている面のリストが含まれています。VVメッシュとは異なり、面と頂点の両方が明示的であるため、隣接する面や頂点の位置特定は定数時間で行えます。ただし、エッジは暗黙的であるため、特定の面を囲むすべての面を見つけるには、依然として検索が必要です。面の分割や結合などの他の動的な操作も、面・頂点メッシュでは困難です。

1975年にバウムガルトによって導入されたウィングエッジメッシュ^{[ 3 ]}は、メッシュの頂点、面、エッジを明示的に表現します。この表現は、分割および結合操作を迅速に行えるため、メッシュ形状を動的に変更する際の柔軟性を最大限に高めるために、モデリングプログラムで広く使用されています。主な欠点は、多くのインデックスを維持する必要があるため、ストレージ要件が大きく、複雑さが増すことです。ウィングエッジメッシュの実装上の問題に関する詳しい説明は、書籍「Graphics Gems II 」 ^{[ 4 ]}に記載されています。

翼状エッジメッシュは、エッジからエッジへの移動と、エッジの周囲に順序付けられた面のセットを提供するという問題に対処します。任意のエッジに対して、出ていくエッジの数は任意です。これを簡略化するために、翼状エッジメッシュは、両端の最も近い時計回りと反時計回りのエッジの 4 つだけを提供します。他のエッジは段階的に移動できます。したがって、各エッジの情報は蝶に似ているため、「翼状エッジ」メッシュと呼ばれます。上の図は、「ボックス シリンダー」を翼状エッジメッシュとして示しています。エッジの全データは、2 つの頂点 (端点)、2 つの面 (各側面)、および 4 つのエッジ (翼状エッジ) で構成されます。

グラフィックスハードウェアで翼状エッジメッシュをレンダリングするには、面インデックスリストを生成する必要がありますが、これは通常、ジオメトリが変更された場合にのみ行われます。翼状エッジメッシュは、メッシュの変更が局所的に発生するため、サブディビジョンサーフェスやインタラクティブモデリングなどの動的なジオメトリに最適です。衝突検出などで必要となるメッシュ全体の走査も効率的に実行できます。

翼状エッジメッシュは、ジオメトリの動的な変更を可能にする唯一の表現方法ではありません。翼状エッジメッシュと面頂点メッシュを組み合わせた表現方法として、レンダリングダイナミックメッシュ（RDM）があります。RDMは、面の頂点と頂点の面（FVメッシュと同様）、およびエッジの面と頂点（翼状エッジと同様）の両方を明示的に格納します。

RDMは、標準的なウィングエッジメッシュよりも必要なストレージ容量が少なく、面リストに頂点のインデックスが含まれているため、グラフィックスハードウェアで直接レンダリングできます。さらに、頂点から面へのトラバーサルは明示的（定数時間）であり、面から頂点へのトラバーサルも同様です。RDMは、エッジから面、次に面から隣接するエッジへとトラバーサルすることで4つの出力エッジを見つけることができるため、4つの出力エッジを必要としません。RDMは、ジオメトリを動的に更新できるため、ウィングエッジメッシュの機能の恩恵を受けています。

詳細については、Tobler & Maierhofer ( WSCG 2006) を参照してください。 ^{[ 5 ]}

次の表では、explicit はデータが直接格納されるため、操作を定数時間で実行できることを示します。list compare は、操作を実行するために 2 つのリスト間のリスト比較を実行する必要があることを示します。pair search は、 2 つのインデックスに対して検索を実行する必要があることを示します。表記avg(V,V)は、指定された頂点に接続されている頂点の平均数を意味します。avg (E,V)は、指定された頂点に接続されているエッジの平均数を意味し、avg(F,V)は、指定された頂点に接続されている面の平均数を意味します。

表記「V → f1, f2, f3, ... → v1, v2, v3, ...」は、操作を実行するために複数の要素を走査する必要があることを示しています。たとえば、面-頂点メッシュを使用して「指定された頂点 V の周囲のすべての頂点」を取得するには、まず頂点リストを使用して指定された頂点 V の周囲の面を見つける必要があります。次に、それらの面から、面リストを使用してそれらの周囲の頂点を見つけます。翼状エッジメッシュは、ほぼすべての情報を明示的に格納し、他の操作は常に最初にエッジを走査して追加情報を取得します。頂点-頂点メッシュは、指定された頂点の隣接する頂点を明示的に格納する唯一の表現です。

メッシュ表現が複雑になるにつれて（概要図の左から右へ）、明示的に格納される情報量が増加します。これにより、さまざまな要素の走査やトポロジーへのアクセスがより直接的かつ一定時間で可能になりますが、インデックスを適切に維持するためのオーバーヘッドとメモリ使用量が増加するという代償を伴います。

一般的に、オブジェクトをグラフィックスハードウェア上でレンダリングする際に、ジオメトリ（接続性）は変化しないものの、形状（頂点位置）が変形または変化する可能性がある場合（例えば、静的オブジェクトやモーフィングオブジェクトのリアルタイムレンダリングなど）には、面頂点メッシュが使用されます。ジオメトリが変化する場合には、インタラクティブモデリングパッケージやサブディビジョンサーフェスの計算などにおいて、翼状エッジメッシュまたは動的レンダリングメッシュが使用されます。頂点頂点メッシュは、ハードウェアレンダリングが問題とならない限り、ジオメトリやトポロジーの効率的かつ複雑な変更に最適です。