マーチングキューブ法:ボクセルからポリゴンへの変換


サーフェイスレンダリングで描画するボクセルデータの等値面ポリゴンは、一般的に、 マーチングキューブ法(Marching cubes)により作成されます。


マーチングキューブ法

マーチングキューブ法のアルゴリズム

  1. 互いに隣接する8個のボクセルの組を考える
  2. ボクセル値が等値面閾値の上になるか下になるかには、256通りの組み合わせが生じる(2の8乗)
  3. 256通りの組み合わせは、対称性を考慮するといくつかのパターンに分類できる
  4. 各パターンに対して、三角形ポリゴン群を割り当てる
  5. 三角形の頂点位置を、ボクセル値を参照して調整する

最初の論文は、
William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
です。この時点では、生成したポリゴンが閉曲面にならないという欠点がありましたが、その後の論文で修正されました。


特許

マーチングキューブ法には特許が取得されていましたが、現在は特許が切れています。 弊社ソフトウェア Molcer でもこの方法を用いています。 なお、Molcer Plus の製品販売は 2007年からで、特許切れを確認してからのリリースとなりました。


三角形パターンと頂点位置の調整

ポリゴンを構成する頂点の位置は、ボクセル値と等値面閾値により変化します。これを、等値面閾値より高いボクセル値をもつボクセルが1個、残りの7個が低い場合のパターンで説明します。

pattern1

オレンジの球が高いボクセル、青が低いボクセルです。オレンジと青の間に、等値面を構成する三角形を生成します。この例では、三角形1個です。
三角形の各頂点は、ボクセルとボクセルを結ぶ線上に配置されます。


いま、オレンジのボクセル値が 200、その左隣のボクセル値が 0 だとします。等値面閾値が 100 の場合は、三角形の頂点はボクセルの中間に置かれます。

pattern2

等値面閾値が 50 の場合は、三角形の頂点は、低いほうのボクセル寄りに、

pattern3

等値面閾値が 150 の場合は、三角形の頂点は、高いほうのボクセル寄りに調整されます。

pattern4

頂点位置を調整しない場合のサーフェイスレンダリングは、以下のように表面がガタガタになってしまいます。

pattern5

調整した場合は、表面がスムーズです。

pattern6