マーチングキューブ法
マーチングキューブ法（マーチングキューブほう、英: Marching cubes）は、コンピュータグラフィックスのアルゴリズムである。3次元の離散スカラーフィールド（その要素はボクセルと呼ばれることもある）から等値面のポリゴンメッシュを抽出するためのアルゴリズムである。1987年のSIGGRAPHにおいて、 ゼネラル・エレクトリック社のウィリアム・E・ロレンセン（William E. Lorensen,、1946-2019年）[1] と ハーベイ・E・クライン（Harvey E. Cline）[2] によって発表された[3]。
主にコンピュータ断層撮影（CT）や核磁気共鳴画像法（MRI）スキャンデータ画像などの医療用画像診断に利用されている。
開発の経緯
[編集]このアルゴリズムは、ゼネラル・エレクトリック社でCTやMRI装置からのデータを効率的に視覚化する方法に取り組んでいたウィリアム・E・ロレンセンとハーベイ・E・クラインによって、研究の結果として開発された[4]。
アルゴリズムの前提
[編集]このアルゴリズムの前提は、入力体積を離散的な立方体の集合に分割することである。線形再構成フィルタリングを仮定することで、与えられた等値面の一部を含む各立方体は、立方体の頂点のサンプル値がターゲットの等値面の値にまたがっていなければならないため、容易に識別することができる。等値面の一部分を含む各立方体について、内部の立方体におけるトリリニア補間の挙動を近似する三角メッシュが生成される。
アルゴリズム
[編集]カットオフ値もしくは特定のアルゴリズムで1,0に変換されたボクセルデータを対象とする。隣接された8点からなる立方体を1つの単位として考える。結果的に8つの頂点に0か1の数字をもった立方体が形成される。組み合わせは2の8乗の256通りが考えられる。しかし回転対称や1,0の反転を無視する(表裏を考えない)と図2に示すように15種類となる。この原理を用いてライブラリ化した処理をすることで変換の高速化を図ることができる。各キューブを行進するように順番に処理し表裏を考えない等値面でつなぐことでポリゴンデータに変換する。
アルゴリズムはスカラーフィールドを進み、一度に8つの近傍位置を取り（こうして想像上の立方体を形成する）、次にこの立方体を通過する等値面の部分を表現するのに必要なポリゴンを決定する。その後、個々のポリゴンを融合して目的のサーフェスにする。
これは、8つのスカラー値のそれぞれを8ビット整数のビットとして扱うことで、立方体内の256通りのポリゴン構成（28=256）の事前計算された配列へのインデックスを作成することで行われる。スカラーの値が等値より高ければ（つまりサーフェスの内側であれば）該当するビットに1がセットされ、低ければ（外側であれば）0がセットされる。8つのスカラーがすべてチェックされた後の最終値が、ポリゴンインデックス配列の実際のインデックスとなる。
最後に、生成されたポリゴンの各頂点は、その辺で結ばれた2つのスカラー値を線形補間することで、立方体の辺に沿って適切な位置に配置される。
各格子点におけるスカラー場の勾配は、その点から通過する仮想等曲面の法線ベクトルでもある。したがって、これらの法線を各立方体の辺に沿って補間して、生成されたメッシュを何らかの照明モデルでシェーディングするために不可欠な頂点の法線を求めることができる。
アルゴリズムの改良
[編集]このアルゴリズムの最初の公開バージョンは、回転対称性と線対称性を利用し、さらに符号変化も利用して、15のユニークなケースからなる表を構築した。しかし、立方体の面と内部におけるトリリニア補間動作に曖昧さが存在するため、マーチングキューブ法によって抽出されたメッシュには不連続性とトポロジー的な問題があった。グリッドの立方体が与えられたとき、面の曖昧さは、その面の頂点が交互に符号を持つ場合に発生する。つまり、この面の一方の対角線の頂点が正で、もう一方の対角線の頂点が負である。この場合、面の頂点の符号は、等値面の正しい三角形分割方法を決定するには不十分である。同様に、内部の曖昧さは、立方体の頂点の符号が正しい面の三角形分割を決定するのに不十分な場合、つまり、同じ立方体の構成で複数の三角形分割が可能な場合に発生する。
マーチングキューブ法が人気を博し、広く採用された結果、曖昧さに対処し、内挿線の挙動を正しく追跡するために、アルゴリズムにいくつかの改良が加えられた。1988年のDurst[5]は、LorensenとClineによって提案された三角形分割表が不完全であること、および特定のマーチングキューブ法のケースでは複数の三角形分割が可能であることを最初に指摘した。Durstの「追加参照」は，Wyvill, Wyvill and McPheeters[6]による初期の，より効率的な（de Araujo[7]を参照）等曲面ポリゴン化アルゴリズムであった．彼らは、立方体の面上の内挿体を正しく追跡するために、漸近デサイダーと呼ばれるテストを提案した。
その後、1991年にNielsonとHamann[8]は、立方体の面上の補間動作に曖昧さが存在することを観察した。彼らは、立方体の面上の内挿体を正しく追跡するために、漸近決定法と呼ばれるテストを提案した。実際、1994年にNatarajan[9]によって観測されたように、この曖昧性の問題は立方体の内部でも発生する。彼の研究では、補間臨界点に基づく曖昧性解消テストが提案され、マーチングキューブ法の三角形分割表に4つの新しいケース（ケース3、4、6、7のサブケース）が追加された。この時点では、アルゴリズムと三角形分割表に提案されたすべての改良を施しても、マーチングキューブ法によって生成されたメッシュにはトポロジーの不整合が残っていた。
1995年にChernyaev[10]によって提案されたマーチングキューブ法33は、トリリニア補間のトポロジーを保持することを意図した最初の等値面抽出アルゴリズムの1つである。彼の研究では、Chernyaevは三角形分割ルックアップテーブルのケース数を33に拡張した。そして、漸近的決定法に基づく、内部の曖昧さを解決するための異なるアプローチを提案している。その後、2003年にNielson[11]が、Chernyaevのルックアップテーブルが完全であり、トリリニア補間のすべての可能な振る舞いを表現できることを証明し、Lewinerなど[12]がこのアルゴリズムの実装を提案した。また、2003年には、Lopes and Brodlie[13]がNatarajanによって提案されたテストを拡張した[9]。2013年には、Custodioなど[14]が、Chernyaevによって提案されたマーチングキューブ法33アルゴリズムによって生成されたメッシュの位相幾何学的な正しさを損なうアルゴリズムの不正確さを指摘し、修正した[10]。
問題点と回避法の提案
[編集]隣接したキューブの等値面によって形成される共有面形状が四角形となることがある。そのため等値面のポリゴンが一意に形成されないこととなり、位相的な穴があく原因となる。穴があると、三次元画像として表示する場合には問題ないが、内外を判定する必要がある場合には問題となる。そのためポリゴンの穴を埋める作業が必要となる。この問題を回避するために、共有面形状がすべて三角形となる四面体分割法が考案されている。
利用
[編集]このアルゴリズムは、開発の経緯から、主にコンピュータ断層撮影（CT）や核磁気共鳴画像法（MRI）スキャンデータ画像などの医療用画像診断や、通常メタボールやその他のメタサーフェスと呼ばれるものを使った特殊効果や3Dモデリングなど、三次元表示や実体模型化などに利用されている。マーチングキューブ法アルゴリズムは3次元に使用されるもので、このアルゴリズムの2次元バージョンはマーチングスクエアアルゴリズムと呼ばれる。
特許問題
[編集]マーチングキューブ・アルゴリズムの実装は、米国特許4,710,876として成立したため[4]、マーチングキューブ法を用いることができず問題となった。特許を回避する目的で各種の類似手法が考案された。2005年に特許は失効したため現在では法的に問題なくマーチングキューブ法を用いることができる。
脚注
[編集]- ^ “William E. Lorensen （GE Global Research Center MS）”. General Electric, CA | GE Global Research Center. 2024年3月18日閲覧。
- ^ “Harvey E. Cline's research while affiliated with Harvard University and other places”. Harvard University. 2024年3月18日閲覧。
- ^ Lorensen, William E.; Cline, Harvey E. (1987-08-01). “Marching cubes: A high resolution 3D surface construction algorithm”. ACM SIGGRAPH Computer Graphics 21 (4): 163–169. doi:10.1145/37402.37422. ISSN 0097-8930.
- ^ a b US granted US4710876A, Cline, Harvey & Lorensen, William, "System and method for the display of surface structures contained within the interior region of a solid body", issued 1987-12-01
- ^ Dürst, Martin J. (1988-10-01). “Re: Additional reference to "marching cubes"”. ACM SIGGRAPH Computer Graphics 22 (5): 243. doi:10.1145/378267.378271. ISSN 0097-8930.
- ^ Wyvill, Geoff; Wyvill, Brian; McPheeters, Craig (1986). “Data structures for soft objects”. The Visual Computer 2 (4): 227–234. doi:10.1007/BF01900346.
- ^ de Araujo, Bruno; Lopes, Daniel; Jepp, Pauline; Jorge, Joaquim; Wyvill, Brian (2015). “A Survey on Implicit Surface Polygonization”. ACM Computing Surveys 47 (4): 60:1–60:39. doi:10.1145/2732197.
- ^ Nielson, G.M.; Hamann, B. (1991). “The asymptotic decider: Resolving the ambiguity in marching cubes”. Proceeding Visualization '91. pp. 83–91. doi:10.1109/visual.1991.175782. ISBN 978-0818622458
- ^ a b Natarajan, B. K. (January 1994). “On generating topologically consistent isosurfaces from uniform samples”. The Visual Computer 11 (1): 52–62. doi:10.1007/bf01900699. ISSN 0178-2789.
- ^ a b V., Chernyaev, E. (1995). Marching Cubes 33 : construction of topologically correct isosurfaces : presented at GRAPHICON '95, Saint-Petersburg, Russia, 03-07.07.1995. CERN. Computing and Networks Division. OCLC 897851506
- ^ Nielson, G.M. (2003). “On marching cubes”. IEEE Transactions on Visualization and Computer Graphics 9 (3): 283–297. doi:10.1109/TVCG.2003.1207437.
- ^ Lewiner, Thomas; Lopes, Hélio; Vieira, Antônio Wilson; Tavares, Geovan (January 2003). “Efficient Implementation of Marching Cubes' Cases with Topological Guarantees”. Journal of Graphics Tools 8 (2): 1–15. doi:10.1080/10867651.2003.10487582. ISSN 1086-7651.
- ^ Lopes, A.; Brodlie, K. (2003). “Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing”. IEEE Transactions on Visualization and Computer Graphics 9: 16–29. doi:10.1109/tvcg.2003.1175094. hdl:10316/12925.
- ^ Custodio, Lis; Etiene, Tiago; Pesco, Sinesio; Silva, Claudio (November 2013). “Practical considerations on Marching Cubes 33 topological correctness”. Computers & Graphics 37 (7): 840–850. doi:10.1016/j.cag.2013.04.004. ISSN 0097-8493.
外部リンク
[編集]- Some of the early history of マーチングキューブ法(英語、2011年1月21日確認)
- Overview and source code by Paul Bourke(英語、2011年1月21日確認)
- Introductory description with additional graphics(英語、2011年1月21日確認)
- マーチングキューブ(Timothy S. Newman and Hong Yia.)(英語、2011年1月21日確認)
- GameDev overview by Matthew Ward of Worcester Poly