CGAL intersectionは汎用的に作られているため、型が分からずバグるのか

接触判定のプログラムでの問題が起こった。

CGALのintersectionで三次元の三角形の接触部分の線分をとらえようと、テストコードを組んだ。それはうまくいったので、次に本プログラムに組み込んだら、なぜか接触している三角形の判定が漏れ始めた。

すると、こんな記事を見つけた。

https://stackoverflow.com/questions/32951886/wrong-inexact-intersection-between-3d-triangles-cgal/32965564#32965564

質問者も私同様に、接触判定漏れの問題を指摘している。その回答で、do_intersectしてから、intersectionを呼ぶと、型が分からず変な挙動をするとのこと。たしかに私もdo_intersectを呼んだあとなので、挙動としては同じである。

Cartesian_converterを使えば正しい呼び出しになるとのこと。

具体的な使い方は、こちらにある。

https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Cartesian__converter.html

結果、たしかにうまくいった。

私の場合、メッシュ処理のPMP::do_intersectを呼んだあとに、三角形の型Exact_predicates_inexact_constructions_kernel::Triangle_3で接触を見ようとしていたため、この問題が起こった。

この型をコンバーターを使った例の通りに変更するだけで、問題が消えた。

二つのメッシュの接触のメモ

CGALでの二つのメッシュの接触判定と結果の取得方についてのメモ

https://stackoverflow.com/questions/22900932/cgal-meshes-intersection-collision

良記事。手元で実験済みでうまくいくことも確認した。

face_descriptorのidx()はメッシュのindexで、二つのメッシュについて、pair<face_descriptor,face_descriptor>が出力の１要素となる。

vectorで出力されるので、back_inserterを引数で忘れないように。

CGALで形状の近似が実装されてたというメモ

 https://doc.cgal.org/latest/Surface_mesh_approximation/index.html#Chapter_Triangulated_Surface_Mesh_Approximation

figure 74.10が結構理想的

CGAL5.1でボロノイ図の頂点を参照する関数

Delaunay_triangulation_3をTriangulationとし、入力点群pを母点として、それらに対応したボロノイ領域の頂点を返すコードのメモ。

incident_cellsではなく、finite_incident_cellsでトラバースしないと、仮想のボロノイ領域まで参照してしまい、思い通りにならない。

vector<vector<Point>> compute_voronoi(vector<Point> p) {

vector<vector<Point>> vor;

Triangulation T;

vector<Vertex_handle> vh;

for (int i = 0; i < p.size();i++) {

vh.push_back(T.insert(p[i]));

}

for (int i = 0; i < p.size(); i++) {

vector<Cell_handle> cells;

//T.incident_cells(vh[i], back_inserter(cells));

T.finite_incident_cells(vh[i], back_inserter(cells));

vector<Point> cell;

for (auto& cit = cells.begin(); cit != cells.end(); cit++) {

auto VP = T.dual(*cit);

cell.push_back(VP);

}

vor.push_back(cell);

}

return vor;

}

iterator使えないと人間じゃないのか

オープンソースのライブラリはSTLをばりばり使ってて反復子が使えないと、プログラミングすらさせてくれません。これ、CGALのことですけど。

反復子をlistからとるとき、begin()かend()を呼ぶこと多いですが、end()を呼ぶときは要注意です。end()は、ポイントの後ろを指すので、終わったらit = end(); it--;としなければ最後尾を指せていません。なので要注意ということで。はい、おわり。1時間はまったわ。おわり。

CGAL 4.7インストールメモ

前に入れたのは4.6.3だったので、バージョンアップ。ついでにVisual Studio 2015 でcmakeします。ちなみにvisual stuido 2015は Community。OSはWindows 10。

未だに32bit版を使う人なので、boostは、これをインストール。
http://sourceforge.net/projects/boost/files/boost-binaries/1.60.0/boost_1_60_0-msvc-14.0-32.exe/download

CGALはこれをインストール。
https://github.com/CGAL/cgal/releases/tag/releases/CGAL-4.7

どちらもウィザードでインストール。注意として、アクセス制限されているようなところに展開すると面倒なので、cドライブの直下にboostとcgalフォルダを作ってその中に展開することをおすすめします。具体的にはこれらの場所です。
C:\boost
C:\cgal

boostのインストールはあっさり終わります。

次に、cgal。なぜかこういうアラートがでました。問題になれば後で修正することにしましょう。とりあえず無視。単純にパスのミス程度はあとでカバーできます。この手で問題になるのはプログラムを実行するタイミングとかです。

ということで、無事データの展開は終わりました。

次にビルドします。
cmakeを開いて、cgal4.7のルートと、visual studioのソリューションファイルの出力先を指定します。

Configureボタンを押して、コンパイラを指定します。
コンパイラは14を指定。

わーと文字がでますが、エラーじゃなければ、generateを押します。

もしエラーが出たら、boostのパスがミスっていることが多いので、boostの位置を指定しなおしましょう。慣れていない人にとってはこれが結構面倒だったりするので、がんばりましょう。

makeした場所に行くと、CGAL.clnというソリューションファイルができています。

これを開いて、ビルド。

ビルドからバッチビルドをクリックして、バッチビルドを仕掛けます。

ビルド。たぶん成功します。

成功したらbin、libができています。

これでインストールは終わりです。
次はテストプログラムを実行します。

2010から2013環境へ

Visual studio 2010で書いていたプログラムを2013環境に移しました。2015使えって感じですが、それ自体のインストールに時間がかかるので、これはまた後で。

移行作業は、丸1日かかりました。

移したプログラムは、cgalとmfc使っていたので、ライブラリの再インストールが必須でした。
これが大変です。

まずboostのインストールが結構手間です。ソースから入れようとすると失敗します。実際は失敗していないかもしれませんが、cgalのcmakeで、threadとsystemの名前で弾かれるので、目的達成できません。
初めからbinariesを選択したほうがよいです。
https://en.osdn.jp/projects/sfnet_boost/releases/


次にcgalをcmakeします。
boostがちゃんと入っていればだいたいうまくいきます。
コンパイラの選択だけです。

次にcmakeでできたslnファイルを実行して、debugとreleaseでビルドします。
指定したフォルダにlibとdllができるので、それを参照するとcgalは使えるようになります。

2010のmfcで、日本語を使っていたので、2013環境では入っていないmfc mbcs libraryを入れます。


これであとはリンクして終わりです。
こまごまとしたプロジェクトの設定は忘れましたが、ソースはそのままで実行できます。
知っていれば簡単なことも探しながらだと苦労します。おはよう活力。

VS2012 CGAL インストール

開発環境が変わるたびにインストールしなおすのが面倒ですがしょうがないです．
今回は半日もかかってしまいました．
開発環境はVisual studio 2012 VC11です．

CGAL4.2とboost 1.54をWindows 7とWindows 8にインストールして，3次元のconvex hullとVoronoiで挙動を確認できました ．

インストールは以下の3手順でできます．

1) boost 1.54のインストール
VC11での開発のためためにboostをインストールが必要です．
まず公式サイトからboostをダウンロードします．
zipでもなんでもいいです．
次に展開します．
管理者のみがファイルへできるフォルダに展開すると，今後の実行はすべて管理者権限で行ってください．
私は混乱するので，Cの直下にフォルダを作って展開します．
そして，コンパイルします．
コンパイルはVisual studio コマンドプロンプトを使います．
VS2012 の開発者コマンド プロンプトを実行します．
このとき「xxx は内部コマンドまたは外部コマンド、操作可能なプログラムまたはバッチ ファイルとして認識されていません。」とエラーが吐かれたら，管理者権限で実行するとうまくいきます．

そして，cdコマンドでboostの展開先に行き，
bootstrap
とたたき，実行します．
するとb2.exeとbjam.exeができます．
このb2を使ってboostをコンパイルします．
マルチスレッド対応にするために，オプションを含めて
b2 threading=multi
とたたき，実行します．
20分くらいしてboost/stage/の中にライブラリが出来上がります．
OSの環境変数に
BOOST_ROOTとBOOST_LIBRARYDIRを設定し，
値をそれぞれ，boostの展開フォルダとその下のstage\libにします．

2) CMakeでのコンパイル
CGALを公式サイトからダウンロードして，所望のフォルダに展開します．
私はここでもCの直下です．
CMakeを起動させます．
参照先と出力先をCGALのフォルダに設定します．
次に，Configureを押します．
すると
boost_thread boost_system
がないとエラーが吐かれます．
次に，Advanced にチェックして， CGAL_Boost_USE_STATIC_LIBSにチェックし，再度Configureします．
通るので，最後にgenerationを押します．

3)コンパイル
CGALのフォルダにCGAL.slnファイルができているのでVSで起動します．
バッチビルドを開き，すべてをビルドします．

以上の手順で，実行可能な状態まで持っていくことができました．

内部の例外を見えなくする件

しばらくCGALを触っているとVCのデバックにて， CGAL::Uncertain_conversion_exception という例外のメッセージを目にします．このメッセージはCGALのFAQによると無害のメッセージとのことです．ということは見えなくても問題ではなく，ただただ鬱陶しいだけです．同様に思っている人が表示させない方法を紹介してくれてるのでメモです．

http://www.helixoft.com/blog/archives/24

計算誤差のせいで現れるセルの排除

3次元ドロネー図を計算させるとき，計算誤差のせいでありもしないドロネーセルが呼ばれることがありますが，それは体積を計算して，極々小さいときに排除することで解決できます．
原因がわからなかっただけに二日も費やしてしまいました．

cmake→slnファイル→ビルド

インストールメモ．
CMAKEしたあと，作られたslnソリューションファイルを開いて，ビルドしなければ，ライブラリが生成されません．ビルド時は，ソリューション構成が4つ選択できるので，それぞれのビルドします．これでライブラリが生成され，参照できるようになります．

Polyhedron_incremental_builder_3でのインプットエラー

Polyhedron_incremental_builder_3でのインプットに関して，エラーが出たのでメモ．
facetを指定するとき，すべて同じ方向でインデックスを用意する必要があるようです．
たとえば下の例では，7654をコメントにして，//でコメントされた4567でfacetを指定すると，3267と反対になるため，エラーがでます．

 B.begin_facet();
        B.add_vertex_to_facet(3);
        B.add_vertex_to_facet(2);
        B.add_vertex_to_facet(6);
        B.add_vertex_to_facet(7);
 B.end_facet();
 B.begin_facet();
        B.add_vertex_to_facet(7);
        B.add_vertex_to_facet(6);
        B.add_vertex_to_facet(5);
        B.add_vertex_to_facet(4);
        //B.add_vertex_to_facet(4);
        //B.add_vertex_to_facet(5);
        //B.add_vertex_to_facet(6);
        //B.add_vertex_to_facet(7);
 B.end_facet();

ちなみにエラーはpolyhedron_incremental_builder_3.hの440行目でm_errorがtrueになることで発生します．
同じ方向の面を検出するチェッカーがこの行の前に入っていて，m_errorがtrueになることで次からの入力を拒絶しています．

Polyhedron_incremental_builder_3を使ってみる

これまで私も任意の多角形メッシュをCGALで扱ったことなかったので，知らなかったのですが，CGALでは Polyhedron_incremental_builder_3 を使って，閉じた多角形メッシュを作ることができます．
たとえば，examplesのソースをいじって六面体を作ると以下のようになります．

#include < CGAL/Simple_cartesian.h >
#include < CGAL/Polyhedron_incremental_builder_3.h >
#include < CGAL/Polyhedron_3.h >

template < class HDS >
class Build_mesh : public CGAL::Modifier_base< HDS > {
public:
    void operator()( HDS& hds) {
        // Postcondition: `hds' is a valid polyhedral surface.
        CGAL::Polyhedron_incremental_builder_3< HDS > B( hds, true);
        B.begin_surface( 8, 6 );
        typedef typename HDS::Vertex   Vertex;
        typedef typename Vertex::Point Point;
        B.add_vertex( Point( 0, 0, 0));
        B.add_vertex( Point( 0, 1, 0));
        B.add_vertex( Point( 1, 1, 0));
        B.add_vertex( Point( 1, 0, 0));
        B.add_vertex( Point( 0, 0, 1));
        B.add_vertex( Point( 0, 1, 1));
        B.add_vertex( Point( 1, 1, 1));
        B.add_vertex( Point( 1, 0, 1));
  B.begin_facet();
        B.add_vertex_to_facet(0);
        B.add_vertex_to_facet(1);
        B.add_vertex_to_facet(2);
        B.add_vertex_to_facet(3);
  B.end_facet();
  B.begin_facet();
        B.add_vertex_to_facet(3);
        B.add_vertex_to_facet(2);
        B.add_vertex_to_facet(6);
        B.add_vertex_to_facet(7);
  B.end_facet();
  B.begin_facet();
        B.add_vertex_to_facet(7);
        B.add_vertex_to_facet(6);
        B.add_vertex_to_facet(5);
        B.add_vertex_to_facet(4);
  B.end_facet();
  B.begin_facet();
        B.add_vertex_to_facet(4);
        B.add_vertex_to_facet(5);
        B.add_vertex_to_facet(1);
        B.add_vertex_to_facet(0);
  B.end_facet();
  B.begin_facet();
        B.add_vertex_to_facet(0);
        B.add_vertex_to_facet(3);
        B.add_vertex_to_facet(7);
        B.add_vertex_to_facet(4);
  B.end_facet();
  B.begin_facet();
        B.add_vertex_to_facet(1);
        B.add_vertex_to_facet(5);
        B.add_vertex_to_facet(6);
        B.add_vertex_to_facet(2);
  B.end_facet();
  B.end_surface();
    }

};

add_vertexで頂点を追加して，begin_facetとend_facetの間に面を定義します．
面の定義はadd_vertex_to_facetでインデックスを追加します．
これらをbegin_surfaceとend_surfaceではさめば，定義完了です．

呼び出して使うときは，まず以下を記述します．

typedef CGAL::Simple_cartesian < double >  Kernel;
typedef CGAL::Polyhedron_3 < Kernel >      Polyhedron;
typedef Polyhedron::HalfedgeDS          HalfedgeDS;

呼び出し側は，以下のようにPolyhedronを用意して，delegateするようにします．

Polyhedron P;
Build_mesh< HalfedgeDS > mesh;
P.delegate( mesh );

この例から任意の形状用に作りかえれば，細分割に任意の形状を突っ込むことができるようになります．
exampleがこのような構成になっているので，きっとこれでいいのだと思います．

subdivisionの例

CGALには頻繁に使われる細分割手法が実装されていて，かつそこそこ高速に計算してくれるので非常に使いやすいです．ただマニフォールドのみという制約があった(と記憶している)ので，そこは使用者が実装しなければならない(はず)です．
使い方はPolyhedronと分割数を関数に渡すだけです．

たとえば以下のコードで3回のDoo-Sabinです．
まず，関数を使えるようにヘッダーをインクルードします．

#include < CGAL/Subdivision_method_3.h >

呼び出し側で以下のコードです．

Polyhedron P;
Build_mesh< HalfedgeDS > mesh;
P.delegate( mesh);

CGAL::Subdivision_method_3::DooSabin_subdivision(P, 3);

ここでは，Build_meshで六面体のPolyhedronを生成して，delegate関数でPにデータを渡しています．
0-3回の例が以下です．






以上．
簡単でしょ．

VSでCGALを読み込んでコンパイルが通るまで

CGALを使ったプログラムのビルドが通らない原因はCGALのインストールがうまくいっていないことだと思います．私も結構苦労しました．2時間くらい調べたりしてようやくわかった感じです．ですので，ここでは，CGALが本当にインストールできたかをテストする方法を記述します．
下で示す手続きでビルド（コンパイル）を実行して通れば，CGALのインストールができていると言えます．逆にビルドが通らなかったら，CGALのインストールができていないと言えます．
ここではVisual studio 2010で実験しますので，ほかの開発環境ではどうなのか知りません．でも，だいたい似たようなものだと予想します．

さて，テスト用の手続きですが，ざっくりいうと次の5ステップです．
1 プロジェクトの作成
2 ソースのコピぺ
3 インクルードディレクトリーの設定
4 ライブラリディレクトリーの設定
5 ビルド
以上です．

1 プロジェクトの作成
VSではまず，プロジェクトを作成しなければビルドも何もできません．
ということで，作ります．
ここではテストなので，win32コンソールアプリケーションを選びます．
で，何も考えずに，完了です．





2 ソースのコピぺ
次にソースのコピペですが，こんなものは何でもいいので，CGALのサンプルからコピーして，貼り付けます．
ここでは，私がこれから着手するサブディビジョンのテスト用に，3D Surface Subdivision Methodsのサンプルをとってきます．



赤い波下線があり，コンパイルエラーが起こることがばっちりわかります．

3 インクルードディレクトリーの設定
次にプロジェクトのインクルードディレクトリーを設定します．
手順は，プロジェクトのプロパティを開いて，「C/C++」→「全般」→「追加のインクルードディレクトリ」にCGALのインクルードディレクトリとboostのインクルードディレクトリを追加します．



ここでのディレクトリは環境に依存するので，適宜調整してください．

4 ライブラリディレクトリーの設定
インクルードディレクトリー同様，リンカーの設定として，ライブラリを設定します．
手順は，プロジェクトのプロパティを開いて，「リンカー」→「全般」→「追加のライブラリディレクトリ」にCGALのライブラリとboostのライブラリを追加します．



これもインクルードディレクトリの設定と同様に，適宜調整してください．
この例では，デバック版を設定していますが，リリース版でビルドする場合は，リリース版を設定します．

5 ビルド
以上で準備は整いました．
ビルドします．



赤い波下線も消え，ログからビルドが正常終了したことがわかります．
これが確認できれば，CGALのインストールは成功しています．

もし，以上の手続きで，エラーが出るようでしたら，失敗しています．
経験上，失敗の例として，CMAKEを実行していない，CMAKE後にコンパイルしていない，CMAKEがミスってる，インストールしたboostのバージョンが悪い，そもそも必要な他のライブラリをインストールしていない等々です．


ユーザー名がKSakuraiってなっていますが，そのあたりは気にせず，無意味に特定しようとか思わないでください．

CGAL3.7リリースされてた

CGAL3.7がリリースされています．VS2010でも，インストールがしやすくなっています．

cgalをw7, vs2010にインストール

windows 7, visual studio 2010でのインストールの確認ができました．
正直知らなきゃ入らないし，もうしたくない気持ちです．
おおむね公式サイトのFAGに書いてある通りすれば，OKですが，ひとつ罠がありました．
http://www.cgal.org/FAQ.html#vc10

上記のサイトの通りすると，C:\Program Files (x86)\CGAL-3.6.1\auxiliary\gmp\libのフォルダ内に，libgmp-10.lib,libgmp-10.dll,libmpfr-4.lib, libmpfr-4.dllがある状態になります．
このlibgmp-10.libとlibmpfr-4.libの名前をgmp-vc100-mt.libとmpfr-vc100-mt.libに変更しなければ，コンパイルが通りませんでした．

私はコンピューターなんか全然詳しくないので，何が何でこういう変更が必要なのか，何が何でCGALはこの名前を指定するようにしているのか知りませんが，結構げんなりする罠でした．

あー

cgalがvisual studio 2010でcmakeできないんですけど

できるっぽいです．
boostがひっかかってるだけか．

cgalでのオブジェクトへのアクセス順

cgal全般に言えるのかもしれないけれど，オブジェクトをinsertした順にイタレータでアクセスできるわけではないみたいですね．
順にアクセスしたいときは，locate関数で位置を指定するのが定石なのか．

Faceのinfo, index

近隣のフェイスを参照するとき，これらのインデックスが着いていたほうが扱いやすいです．しかし，CGALでは標準でidを持ったfaceの形式がないため，別の情報で代替する必要があります．
ここで，適当なのはinfoで，どんな形式でも追加できる情報です．
今回は，Delaunay図でのインデックスを得る実験をします．
infoを持つfaceを使うために，以下のようにインクルードを指定します．

#include < CGAL/Exact_predicates_inexact_constructions_kernel.h >
#include < CGAL/Delaunay_triangulation_2.h >
#include < CGAL/Triangulation_vertex_base_with_id_2.h >
#include < CGAL/Triangulation_face_base_with_info_2.h >

最後のTriangulation_face_base_with_info_2.hがfaceにinfoを付加した形式です．
3番目はid付の頂点情報です．faceのインデックスの場合はこれである必要はありません．
typedefは以下のように設定します．

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_with_id_2< K > Tvb;
typedef CGAL::Triangulation_face_base_with_info_2< int, K > Tfb;
typedef CGAL::Triangulation_data_structure_2< Tvb,Tfb > Tds;
typedef CGAL::Delaunay_triangulation_2< K, Tds > Triangulation;

Triangulation_face_base_with_info_2< int, K > Tfbの最初の引数でinfoの形式を指定します．この場合は，intを指定します．

 int cnt;
 cnt = 0;
 for(Finite_vertices_iterator fvi = t.finite_vertices_begin (); 
fvi!=t.finite_vertices_end(); fvi++)
 {
  fvi->point().x();
  fvi->point().y();
  fvi->id() = cnt;
  cnt++;
 }

 cnt = 0;
 for(Finite_faces_iterator ffi = t.finite_faces_begin (); 
ffi!=t.finite_faces_end(); ffi++)
 {
  int f[3];
  f[0] = ffi->vertex(0)->id();//vertexから引いてくる
  f[1] = ffi->vertex(1)->id();
  f[2] = ffi->vertex(2)->id();
  ffi->info() = cnt;
  cnt++;
 }

前半は，vertexのidで，後半がこの話題の中心であるfaceのインデックスです．idの指定同様
ffi->info()に直に通し番号を入れていきます．
これで，faceのインデックスを参照できます．