凸包の作成:Quickhull 法【3D技術解説⑧】

凸包作成の高速アルゴリズム、Quickhull 法について解説します。
last update: 2017/05/02

点群(点データの集合体)を凹みのないように覆った図形を凸包と呼びます。凸包作成アルゴリズムはいくつかありますが、Molcer Plus では高速な Quickhull 法を採用しています。

Quickhull 法

凸包

Quickhull 法

1,座標の最大・最小点を求める
Quickhull 法
2,2点で領域分割
Quickhull 法
3,直線の再遠点を求める
Quickhull 法
4,エッジ作成
Quickhull 法
5,内側の点とエッジを無視する
Quickhull 法
6,3に戻る(各エッジの外側について再帰的に行う。外側の点が無くなったら終了)
Quickhull 法

 

上記は二次元平面における凸包です。これを三次元空間に数学的に拡張して3Dデータの凸包を作成します。
三次元の場合は四面体を形成してから各面を処理していきます。また、凹みや谷折れ構造の修正が必要になってきます。

 

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 は、ボクセルデータを表示・計測・加工するためのソフトウェアです。

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