3D技術解説

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

  • このエントリーをはてなブックマークに追加

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

マーチングキューブ法

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

  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個が低い場合のパターンで説明します。
マーチングキューブ法
オレンジの球が高いボクセル、青が低いボクセルです。オレンジと青の間に、等値面を構成する三角形を生成します。この例では、三角形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技術解説⑪】

SNSで最新情報をお届けいたします。

弊社の主力製品です

3D画像解析/処理ソフトウェア Molcer Plus
X線CT画像などの3次元画像データを、計測・加工・解析するためのソフトウェアです。工業製品から生物標本まで、どんなものでも美しく、快適操作でおみせします。
*フリー版もあります:3D画像表示ソフトウェア Molcer
  • このエントリーをはてなブックマークに追加