行進する四面体

マーチングテトラヘドラは、コンピュータグラフィックスの分野で暗黙的な表面をレンダリングするアルゴリズムです。これは、いくつかのキューブ構成でマーチングキューブアルゴリズムの軽微な曖昧さの問題を明確にします。これは1991年に最初に導入されました。^[1]

オリジナルのマーチング キューブ アルゴリズムはソフトウェア特許で保護されていましたが、マーチング テトラヘドロンでは特許ライセンスを必要としない代替アルゴリズムが提供されました。特許出願日 (1985 年 6 月 5 日) から 20 年以上経過し、マーチング キューブ アルゴリズムは現在自由に使用できます。オプションで、マーチング テトラヘドロンを少し改良して、一部の構成で前述の曖昧さを修正することもできます。

マーチング テトラヘドラでは、各立方体は、3 組の反対面のそれぞれを斜めに切断して、立方体を 3 回半分に切断することにより、6 つの不規則なテトラヘドラに分割されます。このようにして、すべてのテトラヘドラが立方体の主対角線の 1 つを共有します。立方体の 12 辺の代わりに、元の 12 辺、6 面の対角線、および主対角線の合計 19 辺を持つことになります。 マーチング キューブと同様に、これらの辺と等値面の交点は、グリッド ポイントの値を線形補間することによって近似されます。

隣接する立方体は、同じ対角線を含む接続面のすべてのエッジを共有します。これは、面の 2 つの異なる対角線の補間で通常わずかに異なる交差点が得られるため、レンダリングされたサーフェスの亀裂を防ぐための重要な特性です。追加の利点は、隣接する立方体を処理するときに、最大 5 つの計算された交差点を再利用できることです。これには、交差点での 計算されたサーフェス法線やその他のグラフィックス属性が含まれます。

各四面体には 16 通りの構成があり、交差なし、1 つの三角形の交差、2 つの (隣接する) 三角形の交差の 3 つのクラスに分類されます。16 通りの構成すべてを列挙し、適切な三角形ストリップを定義する頂点インデックス リストにマッピングするのは簡単です。

マーチング テトラヘドラは、キューブごとに最大 19 個のエッジ交差を計算しますが、マーチング キューブでは 12 個しか必要ありません。これらの交差のうち 1 つだけは、隣接するキューブと共有できません (主対角線上にあるもの)。ただし、キューブのすべての面で共有すると、アルゴリズムが複雑になり、メモリ要件が大幅に増加します。一方、交差が追加されると、サンプリング解像度がわずかに向上します。

一般的に使用されるルックアップ テーブルのサイズを決定する構成の数は、四面体ごとに 8 つの頂点ではなく 4 つの頂点のみが関係するため、はるかに少なくなります。処理する四面体は 1 つの立方体ではなく 6 つになります。このプロセスは明確なので、追加の曖昧さの処理は必要ありません。

欠点は、四面体による立方体のテッセレーションでは四面体の向きを選択する必要があり、面の対角線に沿った補間により等値面に人工的な「隆起」が生成される可能性があることである。^[2]

メッシュ化する立方体セルは、(ダイヤモンド立方)格子を基礎として5つの四面体にスライスすることもできます^[3]。立方体は、立方体の重心の周りの四面体の反対の配置を持つ別の立方体と各面で結合されます。交互の頂点には異なる数の四面体が交差するため、位置に応じてわずかに異なるメッシュが生成されます。このようにスライスすると、追加の対称面が提供されます。立方体の重心の周囲に四面体があると、表面の外側にあるポイントの周囲に非常に開いたスペースも生成されます。

ダイヤモンド キュービックにはさまざまな視覚化があります。空のセルの代わりに、各セルは交互に内部の四面体で埋められます。立方体に内接する四面体ごとに、立方体の頂点と立方体の面を横切る辺を使用して、四面体は 4 つのポイントを占めます。他の 4 つのポイントは反転した四面体の角を形成します。立方体のセルは、セルの位置 (x+y+z+...) が奇数になるように並べられます。奇数の場合は 1 つを使用し、そうでない場合は反転したものを使用します。そうでない場合は、近くのセルは交差を計算するために異なる対角線を使用します。

空間テクスチャシステム^[4]に基づく色の計算は、現在のフラグメントの位置を使用して、テクセル座標のペア (x,y)、(y,z)、(x,z) に基づいて繰り返しテクスチャを選択し、それらの値を法線 z、x、y の各コンポーネントの絶対値でそれぞれスケーリングすることで実行できます。テクスチャ デカールは、デカールの法線の方向に現在のフラグメントの位置を投影し、原点と法線によって指定されたテクスチャの平面に投影し、次に「上」または「右」の方向ベクトルを使用してテクスチャ座標を計算することで、テクスチャ スプラッティングとして適用できます。

この手法は、潜在的な手法として等値面の項に挙げられているデュアル コンターリングとより密接に比較されます。DCL 四面体では、立方体の面を横切る対角線の追加計算が必要ですが、デュアル コンターリングでは必要ありません。また、この手法では、サーフェスの「内側」にある 2 つの近くの点がサーフェスから 1 未満の距離にある場合、エッジ上に 1 点ではなく 2 点を生成する必要があるという問題にも対処していません。関連する修正は、マニフォールド デュアル コンターリングです。^[5]

• 等値面
• マーチングキューブ
• 漸近決定子
• 画像ベースのメッシュ

• 適応型四面体化を使用した暗黙的表面の可視化 (Heinrich Muller、Michael Wehle)
• Mikolalysenko による等値面生成器。アルゴリズムの 1 つとして Marching Tetrahedra が含まれています。
• Mikolalysenko の等値面ジェネレーターと、追加アルゴリズムとしての DCL Marching Tetrahedra (WebGL)
• ボクセル タイプに基づく空間テクスチャリングを備えた Mikolalysenko の等値面ジェネレーターが DCL Marching Tetrahedra(WebGL2) に追加されました
• 正規化されたマーチングテトラヘドラ：等値面抽出の改善