ポリゴンメッシュ

3Dコンピュータグラフィックスとソリッドモデリングでは、ポリゴンメッシュは頂点、エッジと​面は、多面体オブジェクトの表面の形状を定義します。ワイヤーフレーム モデルのように、レンダリングを。面は通常、三角形(三角形メッシュ)、四辺形(四角形)、またはその他の単純な凸多角形(n 角形凹多角形、または穴のある多角形で構成されることもあります。

ポリゴンメッシュの研究は、コンピュータ グラフィックス(特に 3D コンピュータ グラフィックス) と幾何学モデリングの大きなサブフィールドです。さまざまなアプリケーションや目的に応じて、さまざまなポリゴン メッシュの表現が使用されます。メッシュに対して実行されるさまざまな操作には、ブール論理(構成的立体幾何学)、スムージング、簡略化などがあります。また、ポリゴン メッシュを使用したレイ トレーシング、衝突検出、剛体ダイナミクスのアルゴリズムも存在します。メッシュの面ではなくエッジがレンダリングされると、モデルはワイヤーフレーム モデルになります。

メッシュ生成にはマーチングキューブアルゴリズムを含むいくつかの方法がある。^[1]

ボリューム メッシュは、構造の表面と内部領域の両方を明示的に表す点でポリゴン メッシュとは異なります。一方、ポリゴン メッシュは表面のみを明示的に表します (ボリュームは暗黙的です)。

ポリゴン メッシュで作成されたオブジェクトには、さまざまなタイプの要素を保存する必要があります。これには、頂点、エッジ、面、ポリゴン、サーフェスが含まれます。多くのアプリケーションでは、頂点、エッジ、面またはポリゴンのいずれかのみを保存します。レンダラーは 3 辺の面のみをサポートする場合があるため、上記のように、ポリゴンはこれらの面を多数使用して構成する必要があります。ただし、多くのレンダラーは四角形と多辺形のポリゴンをサポートしているか、ポリゴンをその場で三角形に変換できるため、メッシュを三角形の形式で保存する必要はありません。

ポリゴン メッシュは、頂点、エッジ、面のデータを格納するさまざまな方法を使用して、さまざまな方法で表現できます。これには次のものが含まれます。

上記の各表現には特定の利点と欠点があり、Smith (2006) でさらに議論されています。^[2] データ構造の選択は、アプリケーション、必要なパフォーマンス、データのサイズ、および実行される操作によって決まります。たとえば、特に計算幾何学では、一般的な多角形よりも三角形を扱う方が簡単です。特定の操作では、エッジや隣接する面などの位相情報に高速にアクセスする必要があります。これには、翼付きエッジ表現などのより複雑な構造が必要です。ハードウェアレンダリングでは、コンパクトで単純な構造が必要であるため、コーナーテーブル (三角形ファン) は、DirectXやOpenGLなどの低レベルレンダリング API によく組み込まれています。

頂点-頂点メッシュは、オブジェクトを他の頂点に接続された頂点のセットとして表現します。これは最も単純な表現ですが、面とエッジの情報が暗黙的であるため、広く使用されていません。したがって、レンダリング用の面のリストを生成するには、データをトラバースする必要があります。さらに、エッジと面に対する操作は簡単に実行できません。

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

VVメッシュの詳細な説明についてはSmith (2006)を参照のこと。^[2]

面頂点メッシュは、オブジェクトを面のセットと頂点のセットとして表現します。これは最も広く使用されているメッシュ表現であり、現代のグラフィックス ハードウェアで一般的に受け入れられる入力です。

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

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

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

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

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

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

詳細についてはBaumgart（1975）を参照。^[3]

ウイングエッジ メッシュは、ジオメトリの動的な変更を可能にする唯一の表現ではありません。ウイングエッジ メッシュと面頂点メッシュを組み合わせた新しい表現は、レンダリング ダイナミック メッシュです。これは、面の頂点と頂点の面 (FV メッシュなど) と、エッジの面と頂点 (ウイングエッジなど) の両方を明示的に格納します。

レンダリング ダイナミック メッシュは、標準のウィング エッジ メッシュよりもわずかに少ないストレージ スペースしか必要とせず、面リストに頂点のインデックスが含まれているため、グラフィックス ハードウェアによって直接レンダリングできます。さらに、頂点から面へのトラバースは、面から頂点へのトラバースと同様に、明示的 (一定時間) です。RD メッシュでは、4 つの出力エッジは必要ありません。これは、エッジから面へのトラバース、次に面から隣接エッジへのトラバースによってこれらのエッジを見つけることができるためです。

RD メッシュは、ジオメトリを動的に更新できるため、ウィングエッジ メッシュの機能の恩恵を受けます。

詳細についてはTobler & Maierhofer (WSCG 2006)を参照。^[4]

上記の表で、明示的はデータが直接保存されるため、操作が定数時間で実行できることを示します。リスト比較は、操作を実行するために 2 つのリスト間のリスト比較を実行する必要があることを示します。ペア検索は、 2 つのインデックスで検索を実行する必要があることを示します。表記avg(V,V)は、特定の頂点に接続されている頂点の平均数を意味します。avg (E,V) は、特定の頂点に接続されている辺の平均数を意味します。avg (F,V) は、特定の頂点に接続されている面の平均数を意味します。

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

メッシュ表現が複雑になるにつれて (概要の左から右へ)、明示的に保存される情報の量が増加します。これにより、さまざまな要素のトラバースとトポロジーに、より直接的かつ一定時間でアクセスできるようになりますが、インデックスを適切に維持するためのオーバーヘッドとスペースが増加します。

図 7 は、この記事で説明した 4 つの手法それぞれの接続情報を示しています。ハーフエッジ テーブルやコーナー テーブルなどの他の表現も存在します。これらはすべて、頂点、面、エッジが互いにインデックスを付ける方法のバリエーションです。

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

ポリゴン メッシュ データを保存するためのファイル形式は数多くあります。各形式は、作成者が意図した目的に使用すると最も効果的です。一般的な形式には、 .fbx、.dae、.obj、.stlなどがあります。これらの形式のいくつかを以下に表に示します。

• 境界表現
• オイラー演算子
• ハイパーグラフ
• 多様体（メッシュは多様体または非多様体になります）
• メッシュの細分化（ポリゴンメッシュに詳細を追加する手法）
• ポリゴンモデリング
• ポリゴン化
• シンプレックス
• Tスプライン
• 三角測量（幾何学）
• ワイヤーフレームモデル

• Weisstein、Eric W.「単体複体」。MathWorld。
• Weisstein、Eric W.「三角測量」。MathWorld。
• OpenMesh オープンソースのハーフエッジ メッシュ表現。
• ポリゴンメッシュ処理ライブラリ