マーチングキューブ法
マーチングキューブ法(マーチングキューブほう、Marching cubes)は、コンピュータグラフィックスのアルゴリズムである。スカラー[要曖昧さ回避]データで埋まった等方向3次元ボクセルデータを、ポリゴンデータに変換するアルゴリズムである。1987年のSIGGRAPHでLorensenとCline[1]によって発表された。
カットオフ値もしくは特定のアルゴリズムで1,0に変換されたボクセルデータを対象とする。隣接された8点からなる立方体を1つの単位として考える。結果的に8つの頂点に0か1の数字をもった立方体が形成される。組み合わせは2の8乗の256通りが考えられる。しかし回転対称や1,0の反転を無視する(表裏を考えない)と図1に示すように15種類となる。この原理を用いてライブラリ化した処理をすることで変換の高速化を図ることができる。各キューブを行進するように順番に処理し表裏を考えない等値面でつなぐことでポリゴンデータに変換する。
利用[編集]
産業分野のみならず、医療分野でもCTやMRIなどの三次元ボクセルデータをポリゴンデータに変換するのに利用されている。三次元表示や実体模型化などに利用されている。
問題点[編集]
隣接したキューブの等値面によって形成される共有面形状が四角形となることがある。そのため等値面のポリゴンが一意に形成されないこととなり、位相的な穴があく原因となる。穴があると、三次元画像として表示する場合には問題ないが、内外を判定する必要がある場合には問題となる。そのためポリゴンの穴を埋める作業が必要となる。この問題を回避するために、共有面形状がすべて三角形となる四面体分割法が考案されている。
特許問題[編集]
最初特許として成立したため、各ソフトウェアメーカーがMarching cubesを用いることができず問題となった。特許を回避する目的で各種の類似手法が考案された。2005年に特許は失効したため現在では法的に問題なくMarching cubesを用いることができる。
脚注[編集]
- ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
外部リンク[編集]
- Some of the early history of Marching Cubes(英語、2011年1月21日確認)
- Overview and source code by Paul Bourke(英語、2011年1月21日確認)
- Introductory description with additional graphics(英語、2011年1月21日確認)
- Marching Cubes(Timothy S. Newman and Hong Yia.)(英語、2011年1月21日確認)
- GameDev overview by Matthew Ward of Worcester Polytechnic Institute survey article(英語、2011年1月21日確認できず)
