ポリゴンメッシュ
3Dコンピュータグラフィックスとソリッドモデリングにおいて、ポリゴンメッシュとは、頂点、エッジsと面は多面体オブジェクトの表面の形状を定義します。ワイヤーフレームモデルのようにレンダリングを。面は通常、三角形（三角形メッシュ）、四角形（クアッド）、またはその他の単純な凸多角形（n角形凹多角形や穴のある多角形で構成されることもあります。
ポリゴンメッシュの研究は、コンピュータグラフィックス（特に3Dコンピュータグラフィックス）と幾何学モデリングの大きなサブフィールドです。ポリゴンメッシュの表現は、用途や目的に応じて様々です。メッシュに対して実行される様々な操作には、ブール論理（構成的立体幾何学）、スムージング、簡略化などがあります。また、レイトレーシング、衝突検出、ポリゴンメッシュを用いた剛体力学のためのアルゴリズムも存在します。メッシュの面ではなくエッジをレンダリングすると、モデルはワイヤーフレームモデルになります。
メッシュ生成にはマーチングキューブアルゴリズムを含むいくつかの方法がある。[ 1 ]
ボリューム メッシュは、構造の表面と内部領域の両方を明示的に表す点でポリゴン メッシュとは異なります。一方、ポリゴン メッシュは表面のみを明示的に表します (ボリュームは暗黙的です)。
要素
ポリゴンメッシュで作成されたオブジェクトは、異なる種類の要素を格納する必要があります。これには、頂点、エッジ、面、ポリゴン、サーフェスが含まれます。多くのアプリケーションでは、頂点、エッジ、および面またはポリゴンのいずれかのみが格納されます。レンダラーは3辺の面しかサポートしていないため、ポリゴンは上記のように、これらの面を複数組み合わせて構成する必要があります。しかし、多くのレンダラーは四角形や多角形ポリゴンをサポートしているか、ポリゴンを三角形にリアルタイムで変換できるため、メッシュを三角形形式で格納する必要はありません。
頂点
コンピュータグラフィックスにおける頂点（複数形はvertices）は、2次元または3次元空間における面上の点の位置を少なくとも記述するデータ構造です。三角形の頂点は、空間位置だけでなく、オブジェクトを正しくレンダリングするために使用される他の値である属性にも関連付けられることがよくあります。頂点のほとんどの属性は、レンダリングされる空間内のベクトルを表します。これらのベクトルは通常、1次元（x）、2次元（x,y）、または3次元（x,y,z）であり、4番目の同次座標（w ）を含むことができます。これらの値は、マテリアル記述によって意味が与えられます。リアルタイムレンダリングでは、これらのプロパティは頂点シェーダーまたは頂点パイプラインによって使用されます。このような属性には以下が含まれます
ポリゴン
ポリゴンは、コンピュータグラフィックスにおいて、3次元的な外観の画像を構成するために使用され、 [ 2 ]、コンピュータグラフィックスで最も人気のある幾何学的構成要素の1つです。[ 3 ]ポリゴンは頂点で構成され、通常は三角形として使用されます
モデルのポリゴンは、ワイヤーフレームモデルでシンプルにレンダリングされ、確認することができます。ワイヤーフレームモデルでは、ポリゴンの輪郭がシェーディングではなく、目に見える形で表示されます。これが、コンピュータアニメーションにおけるポリゴンステージの理由です。ポリゴン数とは、フレームごとにレンダリングされるポリゴンの数を指します。
第5 世代のビデオ ゲーム コンソールから、ポリゴンの使用がより一般的になり、世代が進むにつれてポリゴン モデルはますます複雑になりました。
表現
ポリゴンメッシュは、頂点、辺、面のデータを格納するための様々な方法を用いて、様々な方法で表現できます。これには以下が含まれます
上記の各表現には、特定の利点と欠点があり、Smith (2006) でさらに議論されています。[ 4 ] データ構造の選択は、アプリケーション、必要なパフォーマンス、データのサイズ、および実行される操作によって決まります。たとえば、特に計算幾何学では、一般的なポリゴンよりも三角形を扱う方が簡単です。特定の操作では、エッジや隣接する面などの位相情報に高速にアクセスする必要があります。これには、ウィングドエッジ表現などのより複雑な構造が必要です。ハードウェアレンダリングでは、コンパクトで単純な構造が必要であるため、コーナーテーブル (三角形ファン) は、DirectXやOpenGLなどの低レベルのレンダリング API に一般的に組み込まれています。
頂点-頂点メッシュ
.png)
頂点-頂点メッシュは、オブジェクトを他の頂点に接続された頂点の集合として表現します。これは最も単純な表現ですが、面と辺の情報が暗黙的であるため、広く使用されていません。そのため、レンダリング用の面のリストを生成するには、データを走査する必要があります。さらに、辺と面に対する操作は容易に実行できません
しかし、VVメッシュは、記憶容量が小さく、形状を効率的に変形できるという利点があります。上図は、VVメッシュで表現された四辺形のボックスを示しています。各頂点は隣接する頂点にインデックスを付けています。「ボックスシリンダー」の上下中央にある最後の2つの頂点（8番と9番）は、5つではなく4つの頂点に接続されています。一般的なシステムでは、任意の頂点に接続された任意の数の頂点を処理できる必要があります。
VVメッシュの詳細な説明についてはSmith（2006）を参照のこと。[ 4 ]
面頂点メッシュ
面頂点メッシュは、オブジェクトを面の集合と頂点の集合として表現します。これは最も広く使用されているメッシュ表現であり、現代のグラフィックスハードウェアで一般的に受け入れられる入力です
面頂点メッシュは、面の頂点と頂点を囲む面を明示的に参照できるという点で、モデリングにおいてVVメッシュを改良したものです。上図は、「ボックスシリンダー」の例をFVメッシュで示しています。頂点v5は、それを囲む面を示すために強調表示されています。この例では、すべての面がちょうど3つの頂点を持つ必要があることに注意してください。ただし、これはすべての頂点が同じ数の周囲の面を持つことを意味するわけではありません。
レンダリングでは、面リストは通常、頂点のインデックスセットとしてGPUに送信され、頂点は位置/色/法線構造として送信されます（図では位置のみが示されています）。この方法の利点は、面の接続性を更新することなく、頂点データを再送信するだけで、形状の変化（ジオメトリの変化ではない）を動的に更新できることです。
モデリングには、あらゆる構造を容易に横断できることが求められます。面頂点メッシュでは、面の頂点を見つけるのは簡単です。また、頂点リストには、各頂点に接続された面のリストが含まれます。VVメッシュとは異なり、面と頂点は両方とも明示的であるため、隣接する面と頂点の検出は定数時間で実行されます。しかし、辺は暗黙的であるため、特定の面を囲むすべての面を見つけるには依然として検索が必要です。面の分割や結合といったその他の動的な操作も、面頂点メッシュでは困難です。
ウィングドエッジメッシュ
1975年にBaumgartによって導入されたウィングドエッジメッシュは、メッシュの頂点、面、およびエッジを明示的に表現します。この表現は、分割と結合の操作を迅速に行うことができるため、メッシュジオメトリを動的に変更する際の柔軟性を最大限に高めるため、モデリングプログラムで広く使用されています。主な欠点は、多くのインデックスを維持することによる大きなストレージ要件と複雑さの増加です。ウィングドエッジメッシュの実装に関する詳細な議論は、書籍『Graphics Gems II』に 記載されています
ウィングドエッジメッシュは、エッジからエッジへと移動し、エッジの周囲に整列した面の集合を提供するという課題に対処します。任意のエッジに対して、出力エッジの数は任意です。これを簡素化するために、ウィングドエッジメッシュは、各端点に最も近い時計回りと反時計回りのエッジの4つだけを提供します。他のエッジは段階的に移動できます。したがって、各エッジの情報は蝶の形に似ており、「ウィングドエッジ」メッシュと呼ばれます。上図は、「ボックスシリンダー」をウィングドエッジメッシュとして示しています。エッジのデータ全体は、2つの頂点（端点）、2つの面（各辺）、および4つのエッジ（ウィングドエッジ）で構成されます。
グラフィックハードウェア向けのウィングドエッジメッシュのレンダリングには、面インデックスリストの生成が必要です。これは通常、ジオメトリが変更された場合にのみ実行されます。ウィングドエッジメッシュは、メッシュの変更が局所的に発生するため、サブディビジョンサーフェスやインタラクティブモデリングなどの動的ジオメトリに最適です。衝突検出に必要なメッシュ全体のトラバースも効率的に実行できます。
詳細についてはBaumgart（1975）を参照。[ 5 ]
動的メッシュをレンダリングする
ウイングエッジメッシュは、ジオメトリの動的な変化を可能にする唯一の表現方法ではありません。ウイングエッジメッシュと面頂点メッシュを組み合わせた新しい表現方法が、レンダーダイナミックメッシュです。これは、面の頂点と頂点の面（FVメッシュと同様）と、エッジの面と頂点（ウイングエッジと同様）の両方を明示的に格納します。
ダイナミックメッシュのレンダリングには、標準的なウィングドエッジメッシュよりもわずかに少ないストレージ容量しか必要とせず、面リストに頂点のインデックスが含まれているため、グラフィックスハードウェアで直接レンダリングできます。さらに、頂点から面へのトラバースは、面から頂点へのトラバースと同様に、明示的（定数時間）です。RDメッシュでは、4つの出力エッジは必要ありません。これは、エッジから面へ、そして面から隣接するエッジへとトラバースすることで、これらのエッジを見つけることができるためです。
RD メッシュは、ジオメトリを動的に更新できるため、ウィングド エッジ メッシュの機能を活用します。
詳細についてはTobler & Maierhofer ( WSCG 2006)を参照。 [ 6 ]
要約
| 演算 | 頂点間 | 面頂点 | 翼端 | ダイナミックレンダリング | |
|---|---|---|---|---|---|
| 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などがあります。以下に、これらの形式のいくつかを一覧表で示します。
| ファイル拡張子 | フォーマット名 | 組織 | プログラム | 説明 |
|---|---|---|---|---|
| .raw | 生メッシュ | 不明 | 各種 | オープンなASCII形式。各行にはスペースで区切られた3つの頂点が含まれ、三角形を形成します。例：X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 |
| .blend | Blenderファイル形式 | Blender Foundation | Blender 3D | オープンソース、バイナリのみの形式 |
| .fbx | オートデスクFBXフォーマット | オートデスク | 各種 | 独自仕様。バイナリとASCIIの仕様が存在します |
| 3ds | 3ds Maxファイル | オートデスク | 3ds Max | 頂点と面の数に16ビットの厳格な制限がある、一般的だが時代遅れのフォーマットです。標準化されておらず、十分な文書化もされていませんが、かつてはデータ交換の「事実上の標準」でした |
| .dae | デジタル資産取引所（COLLADA） | ソニー・コンピュータエンタテインメント、クロノス・グループ | 該当なし | 「 COLLA borative Design A activity（コラボレーションデザイン活動） 」の略。非互換性を防ぐために設計されたユニバーサルフォーマット |
| .dgn | MicroStationファイル | ベントレーシステムズ | マイクロステーション | DGNファイル形式には、バージョン8以前とバージョン8（V8）の2種類があります。 |
| .3dm | ライノファイル | ロバート・マクニール＆アソシエイツ | ライノセラス3D | |
| .dxf、.dwg | 図面交換フォーマット | オートデスク | AutoCAD | |
| .obj | Wavefront OBJ | ウェーブフロントテクノロジーズ | 各種 | 3Dジオメトリを記述するASCII形式。すべての面の頂点は反時計回りに並べられ、面法線は暗黙的に示されます。滑らかな法線は頂点ごとに指定されます |
| .ply | ポリゴンファイル形式 | スタンフォード大学 | 各種 | バイナリと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ファイル | マクソン | CINEMA 4D | |
| .lwo | LightWave 3Dオブジェクトファイル | NewTek | LightWave 3D | |
| .smb | スコア apf | RPIスコア | PUMI | PDEベースのシミュレーションワークフロー向けのオープンソースの並列適応型非構造3Dメッシュ |
| .msh | GMshメッシュ | GMsh開発者 | GMshプロジェクト | オープンソース。1 次元から 3 次元までの線形および多項式補間要素の ASCII メッシュ記述を提供します。 |
| .mesh | OGRE XML | OGRE開発チーム | OGRE、purebasic | オープンソース。バイナリ（.mesh）およびASCII（.mesh.xml）形式が利用可能。頂点アニメーションとモーフターゲットアニメーション（blendshape）のデータが含まれています。スケルタルアニメーションデータは別ファイル（.skeleton）に 含まれています |
| .veg | Vega FEM 四面体メッシュ | イェルネイ・バルビッチ | 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
- ^ Bailey, Kat (2016年4月18日). 「スターフォックスの革新の歴史、良くも悪くも」 . usgamer . 2022年10月22日時点のオリジナルよりアーカイブ。2022年7月17日閲覧。
若き日のディラン・カスバートが在籍していたスタジオ、アルゴノート・ソフトウェアが一部開発を担当したこのゲームは、スーパーファミコンの限界を極限まで押し上げた。今では時代遅れに見えるが、当時スターフォックスのポリゴングラフィックは洗練されていてクールで、競合製品のどれをもはるかに凌駕していた。
- ^ポール・S・ヘックバート (1994). 「ポリゴンと多面体」. ポール・S・ヘックバート編. 『グラフィックス・ジェムズIV』第4巻. モーガン・カウフマン. p. 1. ISBN 978-0-12-336155-4。
- ^ a bコリン・スミス著、「頂点間メッシュと幾何学的および生物学的モデリングにおけるその利用について」（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の章。
