計算速度

CGALの計算速度について議論する．

• デフォルトでは, 有限長の浮動小数点数ではなく, 無限精度の計算を行う．これは, 遅い．

どのくらい遅いか? 添付の model3d.hpp を利用して, 100セットの集合の交差部分の体積を求めてみよう.

#include <iostream>
#include "model3d_cgal.hpp"
#include <boost/timer/timer.hpp>
int main(int argc, const char * argv[]) {
	boost::timer::cpu_timer cputime;
	M3D<CGAL::Exact_predicates_exact_constructions_kernel> Exact;
  	int N=20;
	double dx=1./N;
  	cputime.start();
	{
		double sum=0;
        for(int i=0;i<N;i++) for(int j=0;j<N;j++) {
           double fr_0[3] {dx*i,0.0,0.0};
           double fr_1[3] {0.0,dx*j,0.0};
           double vv_0[3] {1.0,+1.0,+1./std::sqrt(2.)};
           double vv_1[3] {1.0,-1.0,+1./std::sqrt(2.)};
           double ww_0[3] {dx,1.0,.1};
           double ww_1[3] {1.0,dx,.1};
           auto P0=Exact.Parallelepiped(fr_0, ww_0,9, vv_0);
           auto P1=Exact.Parallelepiped(fr_1, ww_1,9, vv_1);
           double V=Exact.Volume(Exact.Mult(P0,P1));
           sum+=V;
    }
    cputime.stop();
    std::cout << "精密計算速度(sec) " << N*N << " 多角形 " << cputime.elapsed().user*1e-9 <<  "sum= " << sum <<std::endl;
}

たった40個の体積(合計 0.176777)だが, MacbookPro(2017, オプション Release)で33.57秒かかる.

• 整数だと, もっと早いよ．と言う人がいる.
  • CGALは実装が無限精度実数ベースであり, 理論研究には良いが, 実用には適さない面があるのだ
• BlenderはCRAVEを使っている．100倍早いと言う人と, 大して変わらねえよ, という人がいる.
• いや, Blenderは最近CRAVEからBMeshに変えたと言う情報もある
• BMeshでたらめすぎ，と文句を言っている人がいる
• IGLが良いのでは, という人もいる
  • IGLとは, CGALを使って高速な計算を試みてくれるライブラリーである．
  • 上の例を 20.6秒で計算できる. 
  • ・・・そこまで言うほど早いか？
  • おまけに，IGL-CGALの結合部分が, Linuxクラスターでバグって動かない．難しすぎて，直せない．困った．無理だこりゃ．