Qhullを用いて三次元凸包を取得する
こんにちは、しもむ～です。
初記事です。
ある作業中に3Dモデルの三次元凸包モデル出力をする必要があったので
Qhullを用いて三次元凸包を取得する方法をメモします
今回使用した言語はC++で
開発環境はVisual Studio 2017になります。
そもそも凸包とは
wikipediaによると
数学における凸包（とつほう、英: convex hull）または凸包絡（とつほうらく、英: convex envelope）は、与えられた集合を含む最小の凸集合である。例えば X がユークリッド平面内の有界な点集合のとき、その凸包は直観的には X をゴム膜で包んだときにゴム膜が作る図形として視認することができる。
とのことで、2次元の凸包だと
こんな感じになります。 で、三次元の凸包はどういう状態かというと
これが
こんな感じになります。
UnityにおけるMesh ColliderのConvex hullみたいなところで使われたりします。
Qhullについて
Qhullとは凸包やドローネ三角形分割、ボロノイ図を作成するための
ソフトウェアです。ソースコードが公開されており、
他のライブラリやソフトでもライブラリとして使用されています。
(使用例：PCL,scipy,MatLab,MeshLabなど)
Qhullの導入
Qhullのソリューションファイルを生成
まず
http://www.qhull.org/download/
からソースコードを落としてきて、解凍します。
解凍後はqhull-2015.2/build以下の物を削除します。
Cmakeを起動し、
- souce code欄にqhull-2015.2
- build the binaries欄にqhull-2015.2/build
を指定しContifireを押してターゲットのVisual Studioを選択し実行します。
実行後はAdd Entryで以下の物を追加します。
| 項目 | 内容 |
|---|---|
| Name: | CMAKE_DEBUG_POSTFIX |
| Value: | STRING |
| column | column |
| Value: | _d |
| Description |
DEBUGビルドのときに出力ファイルに_dを追加する
追加後にGenerateを押してソリューションファイルを生成します。
Qhullをビルド&インストール
Visual Studioを起動し生成したソリューションファイル(qhull2015.2/build/qhull.sin)を開きます。
- ALL_BUILD->ビルド
でQhullをビルドします。
- INSTALL->プロジェクトのみ->INSTALLのみをビルド
でQhullをインストールします。
ここまででqhullのインストールは完了です
QhullをVisual Studioで使用可能にする
Qhullを使用したいプロジェクトのプロパティを開きます。
構成プロパティ->C/C++->全般->追加のインクルードディレクトリ に
C:\Program Files\qhull\include
を追加
構成プロパティ->リンカー->全般->追加のライブラリディレクトリ に
C:\Program Files\qhull\lib
を追加
構成プロパティ->リンカー->入力->追加の依存ファイル に
qhullcpp.lib
qhullstatic_r.lib
を追加
qhullstatic.libを使用した場合実行時に
QH6248 qh_lib_check: Incorrect qhull library called. Caller uses reentrant Qhull while library is non-reentrant
QH6249 qh_lib_check: Incorrect qhull library called. Size of qhT for caller is 6632, but for library is 2432.
QH6256 qh_lib_check: Cannot continue. Library 'qhull 7.2.0 (2015.2 2016/01/18)' uses a static qhT (e.g., libqhull.so)
とエラーが生じることがあります。
qhullstatic_r.libを使用することでこれが回避できます。
ここまででQhullの導入は完了です。
実際にQhullを使ってみる
実際にC++からQhullを使用するサンプルが以下のようになります。
なお、Qhullの実行結果から面の法線方向も取得できるようですが、
今回は頂点情報のみを取得します。
//一部抜粋 全ソースコードは記事の最後に #include <libqhullcpp\Qhull.h> #include <libqhullcpp\PointCoordinates.h> #include <libqhullcpp\QhullFacet.h> #include <libqhullcpp\QhullFacetList.h> #include <libqhullcpp\QhullVertexSet.h> void ConvexHull::execute() { std::cout << "Start Convex hull" << std::endl; orgQhull::Qhull qhull; orgQhull::PointCoordinates points; //3次元を扱う points.setDimension(3); //qhullに渡す頂点情報を作成 //配列の中身は{x0, y0, z0, x1, y1, z1, x2, y2, ...}となる //QhullではcoorT型を使うが、実質double std::vector<coordT> allpoint; for (auto v : m_input_vertexes) { allpoint.push_back(v); } points.append( allpoint); //qhullの実行 qhull.runQhull(points.comment().c_str(), points.dimension(), points.count(), points.coordinates(), "Qt"); //qhullの結果から面を取得 orgQhull::QhullFacetList faceList = qhull.facetList(); for (auto itr = faceList.begin(); itr != faceList.end(); itr++) { //面から頂点情報を取得 orgQhull::QhullVertexSet vset = (*itr).vertices(); for (auto vitr = vset.begin(); vitr != vset.end(); vitr++) { orgQhull::QhullPoint p = (*vitr).point(); double * coords = p.coordinates(); m_convex_vertexes.push_back(coords[0]); m_convex_vertexes.push_back(coords[1]); m_convex_vertexes.push_back(coords[2]); } } std::cout << "End convex hull" << std::endl; }
また、Qhullの処理時に発生する例外はQhullErrorで拾うことができます。
ConvexHull convex; convex.setVertexes(stl.vertexes()); try { convex.execute(); } catch(orgQhull::QhullError &e){ std::cerr << e.errorCode() << std::endl; std::cerr << e.what() << std::endl; }
Qhullに渡した頂点情報に不備がある等の処理失敗時に例外が発生します。
