ボクセルデータからポリゴンデータに変換するアルゴリズム、マーチングキューブ法について解説します。
サーフェイスレンダリングで描画するボクセルデータの等値面ポリゴンは、一般的に、 マーチングキューブ法（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 の場合は、三角形の頂点は、高いほうのボクセル寄りに調整されます。
頂点位置を調整しない場合のサーフェイスレンダリングは、以下のように表面がガタガタになってしまいます。
調整した場合は、表面がスムーズです。
3D技術解説シリーズ
データの種類：ピクセルとボクセルとポリゴン【3D技術解説①】
サーフェイスレンダリングとボリュームレンダリング【3D技術解説②】
マーチングキューブ法：ボクセルからポリゴンへの変換【3D技術解説③】
3Dプリンタで扱えるポリゴン数【3D技術解説④】
CTデータの領域分割：三次元画像への Watershed 法の適用【3D技術解説⑤】
CTデータの画像処理：平滑化によるノイズ除去【3D技術解説⑥】
CTデータの画像処理：モルフォロジー演算（膨張収縮）【3D技術解説⑦】
凸包の作成：Quickhull 法【3D技術解説⑧】
ポリゴン削減（ポリゴンリダクション）：QEM(Quadratic Error Metrics)【3D技術解説⑨】
GPGPUとは：グラフィックカードによる高速化のしくみ【3D技術解説⑩】
サーフェイスレンダリングでの等値面の修正：CTデータを加工する【3D技術解説⑪】
弊社の主力製品です
工業製品から生物標本まで。どんなものでも美しく、快適操作でおみせします。
Molcer Plus は、X線CT画像などのボクセルデータを、計測・加工・解析するためのソフトウェアです。
＊フリー版もあります：3D画像表示ソフトウェア Molcer
＊Molcer Plus パンフレット (v1.8.5)
＊粒子空隙解析パンフレット
＊配向解析パンフレット