マーチングキューブ法:ボクセルからポリゴンへの変換【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

工業製品から生物標本まで。どんなものでも美しく、快適操作でおみせします。

Molcer Plus は、ボクセルデータを表示・計測・加工するためのソフトウェアです。
X線CTやMRIで得られた連続断面画像やSTLファイルから、3次元モデルを作成。データの表面・断面・内部構造をかんたんにみることができます。GPGPUによる超高速演算処理も実装しています。
さまざまな方法で計測・解析が可能。加工修正も容易です。3Dプリンタ用のファイルを作るときも役立ちます。

Molcer Plus はIT導入補助金支援対象ツールに認定されています。
  • Molcer Plus は、「製造業」の「商談管理(提案、見積、契約)」「分析機能、自動化・効率化ツール」として登録されています。
  • 補助率は1/2です。

*Molcer Plus の価格・ライセンス等はお問い合わせください。
*フリー版もあります:3D画像表示ソフトウェア Molcer
Molcer Plus パンフレット (v1.36)(PDF 2.2MB)