マーチングキューブ

マーチングキューブは、1987年のSIGGRAPHの議事録でロレンセンとクライン^{[1]によって発表された}コンピュータグラフィックス アルゴリズムであり、3次元の離散スカラー場（その要素はボクセルと呼ばれることもある）から等値面のポリゴンメッシュを抽出するためのものである。このアルゴリズムの用途は主に、CTやMRIのスキャンデータ画像などの医療視覚化、および通常メタボールやその他のメタサーフェスと呼ばれるものを使用した特殊効果や3Dモデリングに関係している。マーチングキューブアルゴリズムは3Dで使用することを目的としており、このアルゴリズムの2Dバージョンはマーチングスクエアアルゴリズムと呼ばれている。

このアルゴリズムは、ウィリアム・E・ロレンセン（1946-2019）とハーヴェイ・E・クラインがゼネラル・エレクトリックで行った研究の結果として開発されました。ゼネラル・エレクトリックでは、CTやMRI装置からのデータを効率的に視覚化する方法に取り組んでいました。^[2]

アルゴリズムの前提は、入力ボリュームを個別の立方体の集合に分割することです。線形再構成フィルタリングを想定すると、立方体の頂点のサンプル値がターゲットの等値面値にまたがる必要があるため、特定の等値面の一部を含む各立方体を簡単に識別できます。等値面の一部を含む各立方体に対して、内部立方体の 三線補間の動作を近似する三角形メッシュが生成されます。

最初に公開されたバージョンのアルゴリズムでは、回転対称性と反射対称性、および符号の変更を利用して、15 個の固有のケースを含むテーブルを作成しました。ただし、立方体の面と内部の三線補間動作に曖昧さが存在するため、マーチング キューブによって抽出されたメッシュには不連続性と位相の問題がありました。グリッドの立方体を考えると、面の頂点の符号が交互に変わると、面の曖昧さが発生します。つまり、この面の 1 つの対角線の頂点は正で、もう 1 つの対角線の頂点は負です。この場合、面の頂点の符号は、等値面を三角形に分割する正しい方法を決定するのに不十分であることに注意してください。同様に、内部の曖昧さは、立方体の頂点の符号が正しい表面の三角形分割を決定するのに不十分な場合、つまり、同じ立方体構成に対して複数の三角形分割が可能な場合に発生します。

マーチングキューブの人気と広範な採用により、あいまいさに対処し、補間関数の動作を正しく追跡するためのアルゴリズムがいくつか改良されました。1988年にDurst ^[3]は、LorensenとClineによって提案された三角形分割テーブルが不完全であり、特定のマーチングキューブのケースでは複数の三角形分割が可能であることに初めて言及しました。Durstの「追加の参照」は、Wyvill、Wyvill、およびMcPheeters ^{[5]による、より初期の、より効率的な（de Araujo [4]}を参照）等値面ポリゴン化アルゴリズムでした。その後、1991年にNielsonとHamann ^{[6]は、立方体の表面上の補間関数の動作にあいまいさがあることを観察しました。彼らは、立方体の表面上の補間関数を正しく追跡するための}Asymptotic Deciderと呼ばれるテストを提案しました。実際、1994年にNatarajan ^[7]が観察したように、このあいまいさの問題は立方体の内部でも発生します。著者は、この研究で、補間臨界点に基づく曖昧さ解消テストを提案し、マーチング キューブの三角測量表に 4 つの新しいケース (ケース 3、4、6、7 のサブケース) を追加しました。この時点では、アルゴリズムとその三角測量表に提案されたすべての改善にもかかわらず、マーチング キューブによって生成されたメッシュには依然としてトポロジーの不整合がありました。

^{1995年にチェルニャエフ[8]}が提案したマーチングキューブは、三線補間の位相を保存することを目的とした最初の等値面抽出アルゴリズムの1つです。チェルニャエフは、その研究で、三角測量ルックアップテーブルのケース数を33に拡張しています。次に、漸近決定子に基づく内部の曖昧さを解決するための別のアプローチを提案しています。その後、2003年に、ニールソン^[9]は、チェルニャエフのルックアップテーブルが完全であり、三線補間のすべての可能な動作を表現できることを証明し、ルウィナーら^[10]はアルゴリズムの実装を提案しました。また、2003年にロペスとブロドリー^[11]は、ナタラジャン^[7]が提案したテストを拡張しました。^[12]は、チェルニャエフが提案したマーチングキューブ33アルゴリズムによって生成されたメッシュの位相的な正確性を損なうアルゴリズムの不正確さを指摘し、修正した。^[8]

アルゴリズムはスカラー フィールドを進み、一度に 8 つの隣接位置を取得し (仮想立方体を形成します)、この立方体を通過する等値面の部分を表すために必要なポリゴンを決定します。その後、個々のポリゴンが結合されて目的のサーフェスが作成されます。

これは、8 つのスカラー値のそれぞれを 8 ビット整数のビットとして扱い、立方体内の 256 の可能なポリゴン構成 (2 ⁸ =256) の事前計算された配列へのインデックスを作成することによって行われます。スカラー値が等値よりも高い場合 (つまり、表面の内側にある場合) は、適切なビットが 1 に設定され、低い場合 (外側にある場合) は、適切なビットが 0 に設定されます。8 つのスカラーがすべてチェックされた後の最終値が、ポリゴン インデックス配列への実際のインデックスになります。

最後に、生成されたポリゴンの各頂点は、そのエッジによって接続された 2 つのスカラー値を線形補間することによって、立方体のエッジに沿った適切な位置に配置されます。

各グリッド ポイントでのスカラー フィールドの勾配は、そのポイントを通過する仮想等値面の法線ベクトルでもあります。したがって、これらの法線を各立方体のエッジに沿って補間して、生成された頂点の法線を見つけることができます。この法線は、結果のメッシュを何らかの照明モデルでシェーディングするために不可欠です。

マーチングキューブアルゴリズムの実装は、米国特許4,710,876として特許を取得しました。^{[2]特許を回避し、いくつかのキューブ構成でのマーチングキューブの軽微な曖昧性の問題を解決するために、}マーチングテトラヘドラと呼ばれる別の類似アルゴリズムが開発されました。特許は2005年に失効し、発行日（1987年12月1日^[2] ）から20年以上経過したため、グラフィックスコミュニティがロイヤリティなしで使用することが合法になりました。

• 画像ベースのメッシュ
• 行進する四面体

ウィキメディア・コモンズには、マーチングキューブに関連するメディアがあります。

• Lorensen, WE; Cline, Harvey E. (1987). 「マーチングキューブ: 高解像度 3D サーフェス構築アルゴリズム」. ACM コンピュータグラフィックス. 21 (4): 163–169. CiteSeerX  10.1.1.545.613 . doi :10.1145/37402.37422.
• Nielson, GM; Hamann, B. (1991)。「漸近的決定子: マーチングキューブの曖昧さの解決」。Proceeding Visualization '91。pp. 83–91。doi : 10.1109 / VISUAL.1991.175782。ISBN 9780818622458. S2CID  35739150。
• Montani, Claudio; Scateni, Riccardo; Scopigno, Roberto (1994). 「マーチングキューブの暗黙的な曖昧さ解消のための修正ルックアップテーブル」. The Visual Computer . 10 (6): 353–355. doi :10.1007/BF01900830. S2CID  31316542.
• Nielson, GM; Junwon Sung (1997)。「インターバルボリュームテトラヘドライゼーション」。Proceedings。Visualization '97 ( Cat. No. 97CB36155)。pp. 221–228。doi :10.1109/VISUAL.1997.663886。ISBN 978-0-8186-8262-9. S2CID  5575097。
• Paul Bourke。「概要とソースコード」。
• Matthew Ward。「GameDev の概要」。
• 「追加のグラフィックによる紹介説明」。
• 「マーチングキューブ」。マーチングキューブの初期の歴史の一部。
• Newman, Timothy S.; Yi, Hong (2006). 「マーチングキューブアルゴリズムの調査」. Computers and Graphics . 30 (5): 854–879. CiteSeerX  10.1.1.413.7458 . doi :10.1016/j.cag.2006.07.021.
• Stephan Diehl. 「視覚化アルゴリズムの特化」(PDF)。