マーチングキューブ法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
150枚のMRIスライス画像からMarching Cube法でポリゴンに変換された頭部画像 (約150,000枚のポリゴンから構成されている)

Marching cubes (マーチングキューブ法)は、コンピュータグラフィックスアルゴリズムである。スカラーデータで埋まった等方向3次元ボクセルデータを、ポリゴンデータに変換するアルゴリズムである。1987年にSIGGRAPHのLorensen Cline[1]によって発表された。

カットオフ値もしくは特定のアルゴリズムで1,0に変換されたボクセルデータを対象とする。隣接された8点からなる立方体を1つの単位として考える。結果的に8つの頂点に0か1の数字をもった立方体が形成される。組み合わせは2の8乗の256通りが考えられる。しかし回転対称や1,0の反転を無視する(表裏を考えない)と図1に示すように15種類となる。この原理を用いてライブラリ化した処理をすることで変換の高速化を図ることができる。各キューブを行進するように順番に処理し表裏を考えない等値面でつなぐことでポリゴンデータに変換する。

15個の基本となる立体図形

利用[編集]

産業分野のみならず、医療分野でもCTMRIなどの三次元ボクセルデータをポリゴンデータに変換するのに利用されている。三次元表示や実体模型化などに利用されている。

問題点[編集]

隣接したキューブの等値面によって形成される共有面形状が四角形となることがある。そのため等値面のポリゴンが一意に形成されないこととなり、位相的な穴があく原因となる。穴があると、三次元画像として表示する場合には問題ないが、内外を判定する必要がある場合には問題となる。そのためポリゴンの穴を埋める作業が必要となる。この問題を回避するために、共有面形状がすべて三角形となる四面体分割法が考案されている。

特許問題[編集]

最初特許として成立したため、各ソフトウェアメーカーがMarching cubesを用いることができず問題となった。特許を回避する目的で各種の類似手法が考案された。2005年に特許は失効したため現在では法的に問題なくMarching cubesを用いることができる。

脚注[編集]

  1. ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987

外部リンク[編集]

survey article](英語、2011年1月21日確認できず)