三角形メッシュ

コンピュータグラフィックスでは、三角形メッシュはポリゴンメッシュの一種で、共通の辺または頂点で接続された三角形のセット(通常は3 次元) で構成されます。

多くのグラフィックス ソフトウェアパッケージとハードウェア デバイスは、メッシュにグループ化された三角形に対して、個別に提示された同数の三角形に対してよりも効率的に操作できます。これは通常、コンピュータ グラフィックスが三角形の角にある頂点に対して操作を行うためです。個々の三角形の場合、システムは三角形ごとに 3 つの頂点に対して操作を行う必要があります。大きなメッシュでは、1 つの頂点で 8 つ以上の三角形が交わる場合があります。これらの頂点を 1 回だけ処理することで、作業の一部のみを行い、同じ効果を得ることができます。^{[引用が必要]}

多くのコンピュータ グラフィックス アプリケーションでは、三角形のメッシュを管理する必要があります。メッシュ コンポーネントは、頂点、エッジ、三角形です。アプリケーションでは、メッシュ コンポーネント間のさまざまな接続についての知識が必要になる場合があります。これらの接続は、実際の頂点の位置とは関係なく管理できます。このドキュメントでは、接続を管理するのに便利な単純なデータ構造について説明します。これは、唯一の可能なデータ構造ではありません。他にも多くのタイプが存在し、メッシュに関するさまざまなクエリをサポートしています。^{[引用が必要]}

コンピュータのメモリにメッシュを保存して操作する方法はさまざまです。OpenGLおよびDirectX APIでは、三角形メッシュをグラフィックス ハードウェアに渡す主な方法は、三角形ストリップとインデックス配列の 2 つです。 ^{[引用が必要]}

三角形間で頂点データを共有する方法の 1 つに、三角形ストリップがあります。三角形ストリップでは、各三角形は 1 つの完全な辺を隣の三角形と共有し、もう 1 つの辺を次の三角形と共有します。もう 1 つの方法は、三角形ファンです。これは、1 つの中心頂点を共有する接続された三角形のセットです。これらの方法を使用すると、頂点が効率的に処理され、N 個の三角形を描画するために N+2 個の頂点を処理するだけで済みます。^{[引用が必要]}

三角形ストリップは効率的ですが、任意の三角形メッシュをストリップに変換する方法が明確でなかったり、便利でない場合があるという欠点があります。^{[引用が必要]}

メッシュを表すデータ構造は、三角形の挿入と三角形の削除という 2 つの基本操作をサポートしています。また、三角形のデシメーション スキームで役立つエッジ縮小操作もサポートしています。この構造は頂点の位置をサポートしていませんが、各頂点に一意の整数識別子 (通常は連続する頂点の位置の配列におけるその頂点のインデックス) が割り当てられていると想定しています。メッシュ頂点は 1 つの整数で定義され、hvi で示されます。メッシュ エッジは 1 組の整数 hv0、v1i で定義され、各整数はエッジの終点に対応します。エッジ マップをサポートするために、エッジは v0 = min(v0、v1) となるように格納されます。三角形コンポーネントは 3 組の整数 hv0、v1、v2i で定義され、各整数は三角形の頂点に対応します。三角形マップをサポートするために、三角形は v0 = min(v0、v1、v2) となるように格納されます。 hv0,v1,v2i と hv0,v2,v1i は異なる三角形として扱われることに注意してください。両面三角形を必要とするアプリケーションでは、両方のトリプルをデータ構造に挿入する必要があります。インデックスの順序について常に注意する必要がないように、ドキュメントの残りの部分では、ペア/トリプル情報は頂点が何らかの方法で順序付けられていることを意味しません (実装では順序付けを処理しますが)。^{[引用が必要]}

構成要素間の接続は、三角形を表す 3 つの要素の集合によって完全に決定されます。三角形 t = hv0,v1,v2i には、頂点 v0、v1、v2 があります。辺 e0 = hv0,v1i、e1 = hv1,v2i、e2 = hv2,v0i があります。逆の接続も知られています。頂点 v0 は、辺 e0 と e2 および三角形 t に隣接しています。頂点 v1 は、辺 e0 と e1 および三角形 t に隣接しています。頂点 v2 は、辺 e1 と e2 および三角形 t に隣接しています。3 つの辺 e0、e1、e2 はすべて t に隣接しています。^{[引用が必要]}

データ構造がどの程度の情報を格納できるかは、アプリケーションのニーズによって異なります。さらに、アプリケーションでは、コンポーネントに追加情報を格納したい場合があります。頂点、エッジ、または三角形に格納される情報は、頂点属性、エッジ属性、または三角形属性と呼ばれます。ここで説明する単純なデータ構造のこれらの抽象表現は次のとおりです^{[引用が必要]}

頂点 = <整数>; // v
エッジ = <整数, 整数>; // v0, v1
三角形 <整数,整数,整数>; // v0, v1, v2
VData = <アプリケーション固有の頂点データ>;
EData = <アプリケーション固有のエッジデータ>;
TData = <アプリケーション固有の三角形データ>;
VAttribute = <VData, set<Edge>,set<Triangle>>; // データ、eset、tset
EAttribute = <EData, set<Triangle>>; // データ、tset
TAttribute = <TData>; // データ
VPair = ペア<頂点、V属性>;
EPair = ペア<Edge,EAttribute>;
TPair = ペア<三角形、T属性>;
VMap = map<VPair>;
EMap = map<EPair>;
TMap = マップ<TPair>;
Mesh = <VMap,EMap,TMap>; // vmap、emap、tmap

マップはハッシュ テーブルの標準的な挿入および削除機能をサポートします。挿入はアイテムがまだ存在しない場合にのみ行われます。削除はアイテムが存在する場合にのみ行われます。^{[引用が必要]}

この操作では、エッジ hvk、vti を識別します。ここで、vk はキープ頂点、vt はスロー頂点と呼ばれます。このエッジを共有する三角形はメッシュから削除されます。頂点 vt もメッシュから削除されます。vt を共有していた三角形は、その頂点が vk に置き換えられます。図 1 ^{[どこですか? ]}は、三角形メッシュと、メッシュに適用された 3 つのエッジの縮小のシーケンスを示しています。^{[引用が必要]}

インデックス配列では、メッシュは 2 つの別々の配列で表されます。1 つの配列は頂点を保持し、もう 1 つの配列は三角形を定義する 3 つのインデックスのセットを保持します。グラフィックス システムは、まず頂点を処理し、その後、変換されたデータで動作するインデックス セットを使用して三角形をレンダリングします。OpenGL では、頂点バッファー オブジェクト(VBO)を使用する場合、glDrawElements()プリミティブによってこれがサポートされます。^{[引用が必要]}

この方法を使用すると、任意の数の頂点を共有する任意の三角形のセットを、中間処理なしで保存、操作し、グラフィックス API に渡すことができます。^{[引用が必要]}

• ハイパーグラフ
• 光線と三角形の交差に関するMöller-Trumboreアルゴリズム
• 鈍角でないメッシュ
• 非一様有理Bスプライン
• 点群
• ポリゴンメッシュ
• 三角測量（トポロジー）
• 三角測量（幾何学）
  • ドロネー三角測量
  • 三角形の不規則ネットワーク