ポリゴンメッシュ
3Dコンピュータグラフィックスとソリッドモデリングにおいて、ポリゴンメッシュとは、頂点、エッジsと面は多面体オブジェクトの表面の形状を定義します。ワイヤーフレームモデルのようにレンダリングを。面は通常、三角形（三角形メッシュ）、四角形（クアッド）、またはその他の単純な凸多角形（n角形凹多角形や穴のある多角形で構成されることもあります。
ポリゴンメッシュの研究は、コンピュータグラフィックス（特に3Dコンピュータグラフィックス）と幾何学モデリングの大きなサブフィールドです。ポリゴンメッシュの表現は、用途や目的に応じて様々です。メッシュに対して実行される様々な操作には、ブール論理（構成的立体幾何学）、スムージング、簡略化などがあります。また、レイトレーシング、衝突検出、ポリゴンメッシュを用いた剛体力学のためのアルゴリズムも存在します。メッシュの面ではなくエッジをレンダリングすると、モデルはワイヤーフレームモデルになります。
メッシュ生成にはマーチングキューブアルゴリズムを含むいくつかの方法がある。[1]
ボリューム メッシュは、構造の表面と内部領域の両方を明示的に表す点でポリゴン メッシュとは異なります。一方、ポリゴン メッシュは表面のみを明示的に表します (ボリュームは暗黙的です)。
要素
ポリゴンメッシュで作成されたオブジェクトは、異なる種類の要素を格納する必要があります。これには、頂点、エッジ、面、ポリゴン、サーフェスが含まれます。多くのアプリケーションでは、頂点、エッジ、および面またはポリゴンのいずれかのみが格納されます。レンダラーは3辺の面しかサポートしていないため、ポリゴンは上記のように、これらの面を複数組み合わせて構成する必要があります。しかし、多くのレンダラーは四角形や多角形ポリゴンをサポートしているか、ポリゴンを三角形にリアルタイムで変換できるため、メッシュを三角形形式で格納する必要はありません。
表現
ポリゴンメッシュは、頂点、辺、面のデータを格納するための様々な方法を用いて、様々な方法で表現できます。具体的には、以下の方法があります。
上記の各表現には、特定の利点と欠点があり、Smith (2006) でさらに議論されています。[2]データ構造の選択は、アプリケーション、必要なパフォーマンス、データのサイズ、および実行される操作によって決まります。たとえば、特に計算幾何学では、一般的なポリゴンよりも三角形を扱う方が簡単です。特定の操作では、エッジや隣接する面などの位相情報に高速にアクセスする必要があります。これには、ウィングドエッジ表現などのより複雑な構造が必要です。ハードウェアレンダリングでは、コンパクトで単純な構造が必要であるため、コーナーテーブル (三角形ファン) は、DirectXやOpenGLなどの低レベルのレンダリング API に一般的に組み込まれています。
頂点間メッシュ
.png){kind=link}
.png/1280px-Vertex-Vertex_Meshes_(VV).png)
頂点-頂点メッシュは、オブジェクトを他の頂点に接続された頂点の集合として表現します。これは最も単純な表現ですが、面と辺の情報が暗黙的であるため、広くは利用されていません。そのため、レンダリング用の面のリストを生成するには、データを走査する必要があります。さらに、辺と面に対する操作は容易ではありません。
しかし、VVメッシュは、記憶容量が小さく、形状を効率的に変形できるという利点があります。上図は、VVメッシュで表現された四辺形のボックスを示しています。各頂点は隣接する頂点にインデックスを付けています。「ボックスシリンダー」の上下中央にある最後の2つの頂点（8番と9番）は、5つではなく4つの頂点に接続されています。一般的なシステムでは、任意の頂点に接続された任意の数の頂点を処理できる必要があります。
VVメッシュの詳細な説明についてはSmith（2006）を参照のこと。[2]
面頂点メッシュ
面頂点メッシュは、オブジェクトを面の集合と頂点の集合として表現します。これは最も広く使用されているメッシュ表現であり、現代のグラフィックスハードウェアで一般的に受け入れられる入力です。
面頂点メッシュは、面の頂点と頂点を囲む面を明示的に参照できるという点で、モデリングにおいてVVメッシュを改良したものです。上図は、「ボックスシリンダー」の例をFVメッシュで示しています。頂点v5は、それを囲む面を示すために強調表示されています。この例では、すべての面がちょうど3つの頂点を持つ必要があることに注意してください。ただし、これはすべての頂点が同じ数の周囲の面を持つことを意味するわけではありません。
レンダリングでは、面リストは通常、頂点のインデックスセットとしてGPUに送信され、頂点は位置/色/法線構造として送信されます（図では位置のみが示されています）。この方法の利点は、面の接続性を更新することなく、頂点データを再送信するだけで、形状の変化（ジオメトリの変化ではない）を動的に更新できることです。
モデリングには、あらゆる構造を容易に横断できることが求められます。面頂点メッシュでは、面の頂点を見つけるのは簡単です。また、頂点リストには、各頂点に接続された面のリストが含まれます。VVメッシュとは異なり、面と頂点は両方とも明示的であるため、隣接する面と頂点の検出は定数時間で実行されます。しかし、辺は暗黙的であるため、特定の面を囲むすべての面を見つけるには依然として検索が必要です。面の分割や結合といったその他の動的な操作も、面頂点メッシュでは困難です。
翼状エッジメッシュ
1975年にバウムガルトによって導入されたウィングドエッジメッシュは、メッシュの頂点、面、および辺を明示的に表現します。この表現は、分割と結合の操作を迅速に行うことができるため、メッシュジオメトリを動的に変更する際の柔軟性を最大限に高めるため、モデリングプログラムで広く使用されています。主な欠点は、多くのインデックスを管理することによる膨大なストレージ要件と複雑さの増加です。ウィングドエッジメッシュの実装に関する詳細な議論は、書籍『Graphics Gems II』に記載されています。
ウィングドエッジメッシュは、エッジからエッジへと移動し、エッジの周囲に整列した面の集合を提供するという課題に対処します。任意のエッジに対して、出力エッジの数は任意です。これを簡素化するために、ウィングドエッジメッシュは、各端点に最も近い時計回りと反時計回りのエッジの4つだけを提供します。他のエッジは段階的に移動できます。したがって、各エッジの情報は蝶の形に似ており、「ウィングドエッジ」メッシュと呼ばれます。上図は、「ボックスシリンダー」をウィングドエッジメッシュとして示しています。エッジのデータ全体は、2つの頂点（端点）、2つの面（各辺）、および4つのエッジ（ウィングドエッジ）で構成されます。
グラフィックハードウェア向けのウィングドエッジメッシュのレンダリングには、面インデックスリストの生成が必要です。これは通常、ジオメトリが変更された場合にのみ実行されます。ウィングドエッジメッシュは、メッシュの変更が局所的に発生するため、サブディビジョンサーフェスやインタラクティブモデリングなどの動的ジオメトリに最適です。衝突検出に必要なメッシュ全体のトラバースも効率的に実行できます。
詳細についてはBaumgart（1975）を参照。[3]
動的メッシュをレンダリングする
ウイングエッジメッシュは、ジオメトリの動的な変化を可能にする唯一の表現方法ではありません。ウイングエッジメッシュと面頂点メッシュを組み合わせた新しい表現方法が、レンダーダイナミックメッシュです。これは、面の頂点と頂点の面（FVメッシュと同様）と、エッジの面と頂点（ウイングエッジと同様）の両方を明示的に格納します。
ダイナミックメッシュのレンダリングには、標準的なウィングドエッジメッシュよりもわずかに少ないストレージ容量しか必要とせず、面リストに頂点のインデックスが含まれているため、グラフィックスハードウェアで直接レンダリングできます。さらに、頂点から面へのトラバースは、面から頂点へのトラバースと同様に、明示的（定数時間）です。RDメッシュでは、4つの出力エッジは必要ありません。これは、エッジから面へ、そして面から隣接するエッジへとトラバースすることで、これらのエッジを見つけることができるためです。
RD メッシュは、ジオメトリを動的に更新できるため、ウィングド エッジ メッシュの機能を活用します。
詳細についてはTobler & Maierhofer (WSCG 2006)を参照。[4]
メッシュ表現の概要
| 手術 | 頂点-頂点 | 面頂点 | 翼端縁 | ダイナミックレンダリング | |
|---|---|---|---|---|---|
| VV | 頂点の周囲のすべての頂点 | 明示的な | V → f1、f2、f3、... → v1、v2、v3、... | V → e1、e2、e3、... → v1、v2、v3、... | V → e1、e2、e3、... → v1、v2、v3、... |
| EF | 面のすべてのエッジ | F(a,b,c) → {a,b}, {b,c}, {a,c} | F → {a,b}, {b,c}, {a,c} | 明示的な | 明示的な |
| VF | 面のすべての頂点 | F(a,b,c) → {a,b,c} | 明示的な | F → e1、e2、e3 → a、b、c | 明示的な |
| FV | 頂点の周りのすべての面 | ペア検索 | 明示的な | V → e1、e2、e3 → f1、f2、f3、... | 明示的な |
| EV | 頂点の周りのすべての辺 | V → {v,v1}、{v,v2}、{v,v3}、... | V → f1、f2、f3、... → v1、v2、v3、... | 明示的な | 明示的な |
| FE | エッジの両面 | リスト比較 | リスト比較 | 明示的な | 明示的な |
| VE | 辺の両方の頂点 | E(a,b) → {a,b} | E(a,b) → {a,b} | 明示的な | 明示的な |
| フルック | 与えられた頂点を持つ面を見つける | F(a,b,c) → {a,b,c} | v1、v2、v3の積集合 | v1、v2、v3の積集合 | v1、v2、v3の積集合 |
| ストレージサイズ | V*平均(V,V) | 3F + V*平均(F,V) | 3F + 8E + V*平均(E,V) | 6F + 4E + V*平均(E,V) | |
| 10 個の頂点、16 個の面、24 個の辺を持つ例: | |||||
| 10 * 5 = 50 | 3×16 + 10×5 = 98 | 3*16 + 8*24 + 10*5 = 290 | 6×16 + 4×24 + 10×5 = 242 | ||
| 図6: メッシュ表現操作の概要 | |||||
上記の表において、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の周囲の面を見つける必要があります。次に、それらの面から、面リストを使用してそれらの周囲の頂点を見つけます。ウィングドエッジメッシュはほぼすべての情報を明示的に保存し、他の操作では常に最初にエッジを走査して追加情報を取得します。頂点頂点メッシュは、特定の頂点の隣接頂点を明示的に保存する唯一の表現です。
メッシュ表現が複雑になるにつれて（概要の左から右へ）、明示的に保存される情報量が増加します。これにより、様々な要素のトラバースとトポロジへのより直接的かつ一定時間でのアクセスが可能になりますが、インデックスを適切に維持するためのオーバーヘッドとメモリ容量が増加します。
図7は、この記事で説明した4つの手法それぞれの接続情報を示しています。ハーフエッジテーブルやコーナーテーブルなど、他の表現方法も存在します。これらはすべて、頂点、面、エッジが互いにインデックスを付ける方法のバリエーションです。
一般的に、面頂点メッシュは、静的オブジェクトやモーフィングオブジェクトのリアルタイムレンダリングなど、ジオメトリ（接続性）は変化しないものの、形状（頂点位置）が変形または変化するグラフィックスハードウェア上でオブジェクトをレンダリングする必要がある場合に使用されます。ウィングドエッジメッシュまたはレンダリングダイナミックメッシュは、インタラクティブモデリングパッケージやサブディビジョンサーフェスの計算など、ジオメトリが変化する場合に使用されます。頂点頂点メッシュは、ハードウェアレンダリングが問題にならない限り、ジオメトリやトポロジの効率的で複雑な変更に最適です。
その他の表現
ファイル形式
ポリゴンメッシュデータを格納するためのファイル形式は数多く存在します。それぞれの形式は、作成者が意図した目的で使用すると最も効果的です。一般的な形式としては、.fbx、.dae、.obj、.stlなどがあります。以下に、これらの形式のいくつかを一覧表で示します。
| ファイルサフィックス | フォーマット名 | 組織 | プログラム | 説明 |
|---|---|---|---|---|
| 。生 | 生のメッシュ | 未知 | 様々な | オープンなASCII形式。各行にはスペースで区切られた3つの頂点が含まれ、三角形を形成します。例：X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 |
| 。ブレンド | Blenderファイル形式 | ブレンダー財団 | ブレンダー3D | オープンソース、バイナリのみの形式 |
| .fbx | Autodesk FBX 形式 | オートデスク | 様々な | 独自仕様。バイナリおよび ASCII 仕様が存在します。 |
| .3ds | 3ds Max ファイル | オートデスク | 3dsマックス | 頂点と面の数に16ビットの厳格な制限がある、一般的だが時代遅れのフォーマット。標準化されておらず、十分な文書化もされていないが、かつてはデータ交換の「事実上の標準」であった。 |
| .dae | デジタル アセット エクスチェンジ (COLLADA) | ソニー・コンピュータエンタテインメント、クロノス・グループ | 該当なし | 「 COLLA borative Design A activity」の略。互換性の問題を回避するために設計されたユニバーサルフォーマット。 |
| .dgn | MicroStation ファイル | ベントレーシステムズ | マイクロステーション | DGNファイル形式には、バージョン8以前とバージョン8（V8）の2種類があります。 |
| .3dm | Rhinoファイル | ロバート・マクニール＆アソシエイツ | ライノセロス3D | |
| .dxf、.dwg | 図面交換フォーマット | オートデスク | オートキャド | |
| .obj | ウェーブフロント OBJ | ウェーブフロントテクノロジーズ | 様々な | 3Dジオメトリを記述するASCII形式。すべての面の頂点は反時計回りに並べられ、面法線は暗黙的に示されます。滑らかな法線は頂点ごとに指定されます。 |
| 。プライ | ポリゴンファイル形式 | スタンフォード大学 | 様々な | バイナリとASCII |
| .pmd | ポリゴンムービーメーカーデータ | 樋口優 | ミクミクダンス | リギング、マテリアル、物理情報を含むヒューマノイド モデルのジオメトリを保存するための独自のバイナリ ファイル形式。 |
| .stl | ステレオリソグラフィーフォーマット | 3Dシステムズ | 多くの | もともとCNCを支援するために設計されたバイナリおよび ASCII 形式。 |
| .amf | 積層製造ファイル形式 | ASTMインターナショナル | 該当なし | STL 形式に似ていますが、ネイティブの色、マテリアル、星座のサポートが追加されています。 |
| .wrl | バーチャルリアリティモデリング言語 | Web3Dコンソーシアム | ウェブブラウザ | ISO規格14772-1:1997 |
| .wrz | VRML圧縮 | Web3Dコンソーシアム | ウェブブラウザ | |
| .x3d、.x3db、.x3dv | 拡張可能な3D | Web3Dコンソーシアム | ウェブブラウザ | XMLベース、オープンソース、ロイヤリティフリー、拡張可能、相互運用可能。色、テクスチャ、シーン情報もサポート。ISO規格19775/19776/19777 |
| .x3dz、.x3dbz、.x3dvz | X3D圧縮バイナリ | Web3Dコンソーシアム | ウェブブラウザ | |
| .c4d | Cinema 4D ファイル | マクソン | シネマ4D | |
| .lwo | LightWave 3D オブジェクト ファイル | ニューテック | ライトウェーブ3D | |
| .smb | スコアックapf | RPIスコア | プミ | PDE ベースのシミュレーション ワークフロー用のオープン ソースの並列適応型非構造化 3D メッシュ。 |
| .msh | Gmshメッシュ | GMsh 開発者 | GMshプロジェクト | オープンソース。1 次元から 3 次元までの線形および多項式補間要素の ASCII メッシュ記述を提供します。 |
| 。メッシュ | OGRE XML | OGRE開発チーム | OGRE、ピュアベーシック | オープンソース。バイナリ形式（.mesh）とASCII形式（.mesh.xml）が利用可能です。頂点アニメーションとモーフターゲットアニメーション（blendshape）のデータが含まれています。スケルタルアニメーションデータは別ファイル（.skeleton）に含まれています。 |
| .veg | Vega FEM 四面体メッシュ | ジェルネイ・バルビッチ | ベガ有限要素法 | オープンソース。FEMシミュレーション用の四面体メッシュとその材料特性を保存します。ASCII (.veg) およびバイナリ (.vegb) 形式が利用可能です。 |
| .z3d | Z3d | オレグ・メラシェンコ | ザノザ モデラー | - |
| .vtk | VTKメッシュ | VTK、キットウェア | VTK、パラビュー | ポイント データ、セル データ、フィールド データなど、さまざまなデータ フィールドを含むオープンな ASCII またはバイナリ形式。 |
| .l4d | LAI4D描画 | デザインのための人工知能研究所 | LAI4D | エンティティの階層ツリーを記述する ASCII データ形式。 |
参照
- 境界表現
- オイラー演算子
- ハイパーグラフ
- 多様体（メッシュは多様体または非多様体になります）
- メッシュの細分化（ポリゴンメッシュに詳細を追加する手法）
- ポリゴンモデリング
- ポリゴンナイザー
- シンプレックス
- Tスプライン
- 三角測量（幾何学）
- ワイヤーフレームモデル
参考文献
- ^ Lorensen, William E.; Cline, Harvey E. (1987年8月1日). 「マーチングキューブ：高解像度3Dサーフェス構築アルゴリズム」. ACM SIGGRAPH Computer Graphics . 21 (4): 163– 169. CiteSeerX 10.1.1.545.613 . doi :10.1145/37402.37422.
- ^ ab Colin Smith、「頂点間メッシュと幾何学的および生物学的モデリングにおけるその利用について」（PDF）
- ^ Bruce Baumgart, Winged-Edge Polyhedron Representation for Computer Vision. National Computer Conference, 1975年5月. 「Use of Polyhedra in computer vision. baumgart.org . 1975年5月. 2005年8月29日時点のオリジナルよりアーカイブ。 2005年8月29日閲覧。
- ^ Tobler & Maierhofer、「レンダリングとサブディビジョンのためのメッシュデータ構造」、2006年。（PDF）
外部リンク
- ワイスタイン、エリック・W.「単体複体」。MathWorld。
- ワイスタイン、エリック・W.「三角測量」。MathWorld。
- OpenMesh オープンソースのハーフエッジ メッシュ表現。
- ポリゴンメッシュ処理ライブラリ
- サーフェス メッシュは、計算幾何学アルゴリズム ライブラリCGALの章です。
