マーチングキューブ法：ボクセルからポリゴンへの変換【3D技術解説③】

ボクセルデータからポリゴンデータに変換するアルゴリズム、マーチングキューブ法について解説します。
サーフェイスレンダリングで描画するボクセルデータの等値面ポリゴンは、一般的に、マーチングキューブ法（Marching cubes）により作成されます。
last update: 2017/04/07

マーチングキューブ法

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

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

最初の論文は、
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個が低い場合のパターンで説明します。
マーチングキューブ法
オレンジの球が高いボクセル、青が低いボクセルです。オレンジと青の間に、等値面を構成する三角形を生成します。この例では、三角形1個です。
三角形の各頂点は、ボクセルとボクセルを結ぶ線上に配置されます。

いま、オレンジのボクセル値が 200、その左隣のボクセル値が 0 だとします。等値面閾値が 100 の場合は、三角形の頂点はボクセルの中間に置かれます。
マーチングキューブ法
等値面閾値が 50 の場合は、三角形の頂点は、低いほうのボクセル寄りに、

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

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