Loading article…
マーチングキューブは、1987年のSIGGRAPH論文集でLorensenとClineによって発表されたコンピュータグラフィックスアルゴリズム[ 1 ]で、 3次元離散スカラー場（その要素はボクセルと呼ばれることもある）から等値面の多角形メッシュを抽出するためのものです。このアルゴリズムの応用は主に、CTやMRIスキャンデータ画像などの医療可視化、特殊効果、またはメタボールやその他のメタサーフェスと呼ばれるものを使用した3Dモデリングに関係しています。マーチングキューブアルゴリズムは3Dで使用することを目的としており、このアルゴリズムの2Dバージョンはマーチングスクエアアルゴリズムと呼ばれます。
このアルゴリズムは、ウィリアム・E・ローレンセン（1946-2019）とハーベイ・E・クラインがゼネラル・エレクトリック社での研究の結果として開発したものです。ゼネラル・エレクトリック社では、CTおよびMRI装置からのデータを効率的に視覚化する方法に取り組んでいました。[ 2 ]
このアルゴリズムの前提は、入力ボリュームを離散的な立方体の集合に分割することです。線形再構成フィルタリングを仮定することで、特定の等値面の一部を含む各立方体は、立方体の頂点におけるサンプル値が目標の等値面値を網羅する必要があるため、容易に識別できます。等値面の一部を含む各立方体に対して、内部立方体における三線形補間関数の挙動を近似する三角形メッシュが生成されます。
アルゴリズムの最初の公開バージョンでは、回転対称性、反射対称性、および符号の変化を利用して、15 の固有のケースを含むテーブルを作成しました。しかし、立方体の面と内部における三線形補間動作に曖昧さが存在するため、マーチングキューブによって抽出されたメッシュには不連続性とトポロジの問題が生じました。グリッドの立方体の場合、面の頂点の符号が交互に変わると、面の曖昧さが発生します。つまり、この面の一方の対角線の頂点は正で、もう一方の対角線の頂点は負です。この場合、面の頂点の符号だけでは、等値面を正しく三角形分割する方法を決定するには不十分であることに注意してください。同様に、立方体の頂点の符号だけでは正しい表面三角形分割を決定するには不十分な場合、つまり、同じ立方体構成に対して複数の三角形分割が可能な場合、内部の曖昧さが発生します。
マーチングキューブの人気と普及により、曖昧さに対処し、補間関数の挙動を正しく追跡するためのアルゴリズムの改良がいくつか行われた。1988 年、Durst [ 3 ]は、Lorensen と Cline が提案した三角形分割テーブルが不完全であり、特定のマーチングキューブのケースでは複数の三角形分割が可能であることに初めて気づいた。Durst の「追加の参照」は、Wyvill、Wyvill、および McPheeters による、より効率的な (de Araujo [ 4 ]を参照) 等値面多角形化アルゴリズムであった。 [ 5 ]その後、1991 年に Nielson と Hamann [ 6 ]は、立方体の面上の補間関数の挙動に曖昧さが存在することに気づいた。彼らは、立方体の面上の補間関数を正しく追跡するための漸近判定器と呼ばれるテストを提案した。実際、1994 年に Natarajan [ 7 ]が指摘したように、この曖昧さの問題は立方体の内部でも発生します。著者は、補間臨界点に基づく曖昧さ解消テストを提案し、マーチングキューブの三角形分割テーブルに 4 つの新しいケース (ケース 3、4、6、7 のサブケース) を追加しました。この時点で、アルゴリズムとその三角形分割テーブルに提案されたすべての改善にもかかわらず、マーチングキューブによって生成されたメッシュには、依然としてトポロジー的な不整合がありました。
1995 年に Chernyaev [ 8 ]によって提案された Marching Cubes 33 は、3 線補間のトポロジーを保持することを目的とした最初の等値面抽出アルゴリズムの 1 つです。Chernyaev は、この研究で、三角形分割ルックアップ テーブル内のケース数を 33 に拡張しました。次に、漸近決定器に基づく、内部の曖昧さを解決するための別のアプローチを提案しました。その後、2003 年に Nielson [ 9 ]は、Chernyaev のルックアップ テーブルが完全であり、3 線補間のすべての可能な動作を表現できることを証明し、Lewiner ら[ 10 ]は、このアルゴリズムの実装を提案しました。また、2003 年に Lopes と Brodlie [ 11 ]は、Natarajan [ 7 ]によって提案されたテストを拡張しました。2013年に Custodio らは、[ 12 ]チェルニャエフが提案したマーチングキューブ33アルゴリズムによって生成されたメッシュのトポロジーの正確さを損なうアルゴリズムの不正確さを指摘し、修正した。[ 8 ]
このアルゴリズムは、スカラー場を順に処理し、一度に8つの近傍位置を取得して（仮想的な立方体を形成する）、この立方体を通過する等値面の部分を表すために必要な多角形を決定します。その後、個々の多角形を結合して目的の表面を作成します。
これは、8つのスカラー値をそれぞれ8ビット整数の1ビットとして扱い、立方体内の256個の可能な多角形構成（2⁸ = 256）の事前計算された配列へのインデックスを作成することによって行われます。スカラー値が等値面の値より大きい場合（つまり、表面の内側にある場合）、該当するビットは1に設定され、小さい場合（外側にある場合）は0に設定されます。8つのスカラー値すべてがチェックされた後の最終値が、多角形インデックス配列への実際のインデックスとなります。
最後に、生成された多角形の各頂点は、その辺で接続されている2つのスカラー値を線形補間することによって、立方体の辺に沿った適切な位置に配置される。
各グリッド点におけるスカラー場の勾配は、その点を通る仮想的な等値面の法線ベクトルでもあります。したがって、これらの法線を各立方体の辺に沿って補間することで、生成された頂点の法線を求めることができます。この法線は、結果として得られるメッシュを何らかの照明モデルでシェーディングするために不可欠です。
マーチングキューブアルゴリズムの実装は、米国特許第4,710,876号として特許を取得しました。[ 2 ]この特許を回避するとともに、一部の立方体構成におけるマーチングキューブのわずかな曖昧さの問題を解決するために、マーチングテトラヘドラと呼ばれる別の類似アルゴリズムが開発されました。この特許は2005年に失効し、発行日（1987年12月1日[ 2 ] ）から20年以上経過しているため、グラフィックスコミュニティはロイヤリティなしでこれを合法的に使用できます。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)