行進する四面体
 |
マーチング・テトラヘドラは、コンピュータグラフィックス分野における暗黙曲面のレンダリングアルゴリズムである。これは、いくつかの立方体構成におけるマーチング・キューブ・アルゴリズムの軽微な曖昧性問題を解決する。1991年に初めて導入された。[ 1 ]
オリジナルのマーチングキューブアルゴリズムはソフトウェア特許で保護されていましたが、マーチングテトラヘドロンでは特許ライセンスを必要としない代替アルゴリズムが提供されました。特許出願日（1985年6月5日）から20年以上が経過し、マーチングキューブアルゴリズムは現在、自由に使用できます。また、マーチングテトラヘドロンに施された軽微な改良により、一部の構成において前述の曖昧さを修正することも可能です。
マーチング・テトラヘドラでは、立方体を3回半分に分割し、3組の向かい合う面をそれぞれ対角線で切断することで、6つの不規則な四面体に分割されます。これにより、すべての四面体が立方体の主対角線のいずれかを共有します。立方体の12辺の代わりに、19辺になります。元の12辺、6辺の面対角線、そして主対角線です。 マーチング・キューブと同様に、これらの辺と等値面の交点は、グリッドポイントの値を線形補間することで近似されます。
隣接する立方体は、接続面のすべての辺（同じ対角線を含む）を共有します。これは、レンダリングされたサーフェスにひび割れが生じるのを防ぐために重要な特性です。なぜなら、面の2つの異なる対角線を補間すると、通常、わずかに異なる交点が生じるからです。さらに、隣接する立方体を処理する際に、最大5つの計算済み交点を再利用できるという利点もあります。これには、交点における 計算済みサーフェス法線やその他のグラフィックス属性が含まれます。
各四面体には16通りの配置があり、交差なし、1つの三角形の交差、2つの（隣接する）三角形の交差の3つのクラスに分類されます。16通りの配置すべてを列挙し、適切な三角形ストリップを定義する頂点インデックスリストにマッピングするのは簡単です。
マーチングキューブとの比較
マーチング・テトラヘドラは、キューブ1つにつき最大19個のエッジ交差を計算します。マーチング・キューブでは12個で済みます。これらの交差のうち、隣接するキューブ（主対角線上にあるもの）と共有できないのは1つだけですが、キューブのすべての面で共有するとアルゴリズムが複雑になり、必要なメモリ量が大幅に増加します。一方で、交差数が増えることで、サンプリング解像度はわずかに向上します。
一般的に使用されるルックアップテーブルのサイズを決定する構成の数は、四面体ごとに8つの頂点ではなく4つの頂点しか必要としないため、はるかに少なくなります。処理対象となる四面体は1つの立方体ではなく6つです。この処理は明確なため、追加の曖昧性処理は必要ありません。
欠点は、立方体を四面体でテッセレーションする際に四面体の向きを選択する必要があり、面の対角線に沿った補間により等値面に人工的な「隆起」が生じる可能性があることである。[ 2 ]
ダイヤモンド格子セル - 代替キューブスライス法
メッシュ化する立方体セルは、ダイヤモンド立方格子を基礎として、5つの四面体にスライスすることもできます[ 3 ]。立方体は、立方体の重心を中心として四面体の向きが反対の向きになるように、各辺で互いに結合します。交互の頂点には異なる数の四面体が交差するため、位置によってメッシュがわずかに異なります。このようにスライスすると、対称面が追加されます。立方体の重心を中心として四面体を配置すると、面の外側にある点の周りに非常に広い空間が生成されます。
ダイヤモンドキュービックには様々な視覚化方法があります。空のセルの代わりに、各セルは交互に内部の四面体で埋められます。立方体に内接する各四面体について、立方体の頂点と面と交差する辺を用いて、四面体は4つの点を占めます。残りの4点は、反転した四面体の頂点となります。立方体のセルは、セルの位置（x+y+z+...）が奇数の場合は片方を使用し、そうでない場合は反転した方を使用します。奇数でない場合、近接するセルは異なる対角線を使用して交差を計算します。
空間テクスチャシステム[ 4 ]に基づく色の計算は、現在のフラグメントの位置を使用して、テクセル座標のペア(x,y)、(y,z)、(x,z)に基づいて繰り返しテクスチャを選択し、それらの値を法線z、x、yの各成分の絶対値でそれぞれスケーリングすることで実行できます。テクスチャデカールは、デカールの法線の方向に現在のフラグメントの位置を、原点と法線で指定されたテクスチャの平面に投影し、次に「上」または「右」の方向ベクトルを使用してテクスチャ座標を計算することで、テクスチャスプラッティングとして適用できます。
この手法は、等値面の項で挙げられているデュアルコンターリングとより密接に比較される。DCL四面体では、立方体の面を横切る対角線の追加計算が必要となるが、デュアルコンターリングではそうではない。また、この手法は、面の「内側」にある2つの近傍点が面から1未満の距離にある場合、つまり、辺上に1点ではなく2点を生成する必要がある場合にも対処していない。関連する修正として、マニフォールドデュアルコンターリングがある。[ 5 ]
参照
参考文献
- ^土井明夫、小出明夫. 「四面体セルを用いた等価曲面の効率的な三角形分割法」電子情報通信学会論文誌, Vol.E74-D, No. 1, 1991
- ^ Charles D. Hansen; Chris R. Johnson (2004). Visualization Handbook . Academic Press. pp. 9– 11. ISBN 978-0-12-387582-2。
- ^ d3x0r (2020年4月14日). 「Githubプロジェクト - マーチングダイヤモンド格子四面体」 . GitHub .
{{cite web}}: CS1 maint: 数値名: 著者リスト (リンク) - ^ d3x0r (2020年4月22日). 「Githubプロジェクト - Isosurfaceマルチテクスチャリング」 . GitHub .
{{cite web}}: CS1 maint: 数値名: 著者リスト (リンク) - ^ Lin X (2015年12月30日).マニフォールドデュアルコンターリング.
外部リンク
- 適応型四面体化を用いた暗黙曲面の可視化 (Heinrich Muller、Michael Wehle)
- Mikolalysenko による等値面生成器。アルゴリズムの 1 つとして Marching Tetrahedra が含まれています。
- Mikolalysenko の等値面生成器と、追加アルゴリズムとしての DCL Marching Tetrahedra (WebGL)
- ボクセル タイプに基づく空間テクスチャリングを備えた Mikolalysenko の等値面ジェネレーターが DCL Marching Tetrahedra(WebGL2) に追加されました
- 正規化されたマーチングテトラヘドラ：等値面抽出の改善
