performance of Delaunay Triangulation of random 3D points

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

performance of Delaunay Triangulation of random 3D points

Feng Ding
Dear all,

There are some statements saying that CGAL can perform 3D DT of 1M random
points under 20 sec (13 or 16 sec). However, I tried the example provided in
the CGAL manual, 3D DT of only 0.125M points took 52.59 sec on a 2.13 GHz Core
2 Duo computer with 2G memory (Mac OSX 10.5). So I'm just wondering if any
options need to be set for better performance. Thank you!

The testing code is as follows, which is almost the same as provided in the
manual.

/******************* code begin *******************/
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/Triangulation_hierarchy_3.h>

#include <cassert>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef CGAL::Triangulation_vertex_base_3<K> Vb;
typedef CGAL::Triangulation_hierarchy_vertex_base_3<Vb>  Vbh;
typedef CGAL::Triangulation_data_structure_3<Vbh> Tds;
typedef CGAL::Delaunay_triangulation_3<K,Tds> Dt;
typedef CGAL::Triangulation_hierarchy_3<Dt> Dh;

typedef Dh::Finite_vertices_iterator Finite_vertices_iterator;
typedef Dh::Vertex_handle     Vertex_handle;
typedef Dh::Point     Point;

#include <boost/progress.hpp>

int main()
{
  // generating points on a grid.
  std::vector<Point> P;

  for (int z=0 ; z<50 ; z++)
    for (int y=0 ; y<50 ; y++)
      for (int x=0 ; x<50 ; x++)
          P.push_back(Point(x,y,z));

  Dh T;

  {
      boost::progress_timer timer(std::cout);
      T.insert (P.begin(), P.end());
  }


  return 0;
}

/******************* code end *******************/


regards,
df
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: performance of Delaunay Triangulation of random

Sylvain Pion
Administrator
Hi,

Ding wrote:
> There are some statements saying that CGAL can perform 3D DT of 1M random
> points under 20 sec (13 or 16 sec). However, I tried the example provided in
> the CGAL manual, 3D DT of only 0.125M points took 52.59 sec on a 2.13 GHz Core
> 2 Duo computer with 2G memory (Mac OSX 10.5). So I'm just wondering if any
> options need to be set for better performance. Thank you!

You are not using random points.
Points on a grid may exhibit worse performance than random distributions.

Moreover, you do not mention the compiler optimization you use.
Best is something like -O2 -DNDEBUG.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: performance of Delaunay Triangulation of random

Ben Supnik
In reply to this post by Feng Ding
Hi df,

In my work with the 2-d DT code in CGAL I found that the insert order of
the points makes an immense difference in performance!

Unfortunately, I tuned my DT code almost 3 years ago and do not exactly
remember what I found. :-(

But...if I remember correctly, Dt insertion is much faster when
inserting a point into a "relatively small" bounded area of the
mesh...and inserting points outside mesh is slow.

I think that if you insert a point in at triangle, the mese locally
produces three sub triangles, and then does a localized bunch of
edge-flips.

By comparison, if you insert a point outside the mesh (which is a convex
hull) then the code must calculate "visibility" around the entire hull
and build a potentially large number of triangles which will all get
nuked later as you insert your points.

My point set was a sub-sampling of a regular grid, so I used sort of an
Adam-7-like iteration to build the bounds first, then course grids, then
the bulk points.  The result was that most inserts were local and much
faster.

(My code inserts the points one at a time - I do not know if the bulk
inserter attempts to do something smarter.)

Now that is all 2-d, and probably wrong since it is from memory,
but...looking at your in-order nested for loop definitely jogged my
memory.  (My first attempt was to iterate across my grid in order and
insert each "keeper" point, and it was sloooow.)

So...perhaps experiment with different ordering of the points and time
the results?

The other issue would be (and this is not as much a factor with DT as
other parts of CGAL) to check your optimizer and #define settings
carefully...you'll want to make sure that all condition checking is
compiled out and that the optimizer is inlining...from what I can tell
GCC on OS X won't inline if the optimizer is off, which makes virtually
any template code under-perform.

cheers
Ben



Ding wrote:

> Dear all,
>
> There are some statements saying that CGAL can perform 3D DT of 1M random
> points under 20 sec (13 or 16 sec). However, I tried the example provided in
> the CGAL manual, 3D DT of only 0.125M points took 52.59 sec on a 2.13 GHz Core
> 2 Duo computer with 2G memory (Mac OSX 10.5). So I'm just wondering if any
> options need to be set for better performance. Thank you!
>
> The testing code is as follows, which is almost the same as provided in the
> manual.
>
> /******************* code begin *******************/
> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> #include <CGAL/Delaunay_triangulation_3.h>
> #include <CGAL/Triangulation_hierarchy_3.h>
>
> #include <cassert>
> #include <vector>
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
>
> typedef CGAL::Triangulation_vertex_base_3<K> Vb;
> typedef CGAL::Triangulation_hierarchy_vertex_base_3<Vb>  Vbh;
> typedef CGAL::Triangulation_data_structure_3<Vbh> Tds;
> typedef CGAL::Delaunay_triangulation_3<K,Tds> Dt;
> typedef CGAL::Triangulation_hierarchy_3<Dt> Dh;
>
> typedef Dh::Finite_vertices_iterator Finite_vertices_iterator;
> typedef Dh::Vertex_handle     Vertex_handle;
> typedef Dh::Point     Point;
>
> #include <boost/progress.hpp>
>
> int main()
> {
>   // generating points on a grid.
>   std::vector<Point> P;
>
>   for (int z=0 ; z<50 ; z++)
>     for (int y=0 ; y<50 ; y++)
>       for (int x=0 ; x<50 ; x++)
>  P.push_back(Point(x,y,z));
>
>   Dh T;
>
>   {
>       boost::progress_timer timer(std::cout);
>       T.insert (P.begin(), P.end());
>   }
>
>
>   return 0;
> }
>
> /******************* code end *******************/
>
>
> regards,
> df

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: [hidden email]
Developer mailing list: [hidden email]
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

about using qt3 to dislay a triangulation generated

Kwok Jasper
In reply to this post by Sylvain Pion
Excuse me, may I ask something about using Qt3.2.1 Non-commercial with CGAL?
 
I have installed Qt3.2.1 non-commercial and CGAL
then, when I tried to complie the code in Miscosoft Visual C++ 2005, I get the following error

error LNK2019: 無法解析的外部符號 "__declspec(dllimport) public: virtual __thiscall QApplication::~QApplication(void)" ([hidden email]) 在函式 _main 中被參考 tr.obj 
 
I am using the code below which is from the official web site of CGAL. May I ask what can I do to deal with the above error?
 
Thank you very much.
#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/IO/Qt_widget_Delaunay_triangulation_2.h>
#include <CGAL/IO/Qt_widget.h>
#include <CGAL/IO/Qt_widget_layer.h>
#include <qapplication.h>

typedef CGAL::Cartesian<double>             Rep;
typedef CGAL::Point_2<Rep>                  Point;
typedef CGAL::Delaunay_triangulation_2<Rep> Delaunay;

Delaunay dt;

class My_layer : public CGAL::Qt_widget_layer{
  void draw(){
    *widget << dt;
  }
};

class My_window : public CGAL::Qt_widget {
public:
  My_window(int x, int y)
  {
    resize(x,y);
    attach(&layer);
  };
private:
  //this method is called when the user presses the mouse
  void mousePressEvent(QMouseEvent *e)
  {
    Qt_widget::mousePressEvent(e);
    dt.insert(Point(x_real(e->x()), y_real(e->y())));
    redraw();
  }
  My_layer layer;
};

int main( int argc, char **argv )
{
    QApplication app( argc, argv );
    My_window *W = new My_window(400,400);
    app.setMainWidget(W);
    W->show();
    W->set_window(0, 400, 0, 400);
    return app.exec();
}

 


想同MSN Buddy傾計了解佢多d? 參觀MSN Buddy部屋啦!
Reply | Threaded
Open this post in threaded view
|

Re: performance of Delaunay Triangulation of random

Sylvain Pion
Administrator
In reply to this post by Ben Supnik
Hi Ben,

Ben Supnik wrote:
> [...]
>
> So...perhaps experiment with different ordering of the points and time
> the results?

The order of insertion is indeed important.
Fortunately, the insert() function taking an iterator range takes
care of this automagically (using a BRIO, aka random shuffle and
spatial sorting).  So, it's not the problem here.

> The other issue would be (and this is not as much a factor with DT as
> other parts of CGAL) to check your optimizer and #define settings
> carefully...you'll want to make sure that all condition checking is
> compiled out and that the optimizer is inlining...from what I can tell
> GCC on OS X won't inline if the optimizer is off, which makes virtually
> any template code under-perform.

This is most probably the problem here:
I get 4.11s on my Mac with -O2 -DNDEBUG, and 42.31s otherwise.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: performance of Delaunay Triangulation of random

Feng Ding
In reply to this post by Feng Ding
Thanks a lot for the detailed explanation.

Optimization option "-O2 -DNDEBUG" sovles the problem. Now DT of 0.125M 3D grid
points on takes 4.93 sec, and DT of 1M 3D grid points takes 40.11 sec.

Another question is that if the 3D points are all on a smooth surface, e.g.,
vertices on a surface mesh, is there any way to accelerate DT on such points?

regards,
df
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: about using qt3 to dislay a triangulation generated

Laurent Rineau (GeometryFactory)
In reply to this post by Kwok Jasper
On Saturday 20 December 2008 17:46:32 Kwok Jasper wrote:
> Excuse me, may I ask something about using Qt3.2.1 Non-commercial with
> CGAL?
>
> I have installed Qt3.2.1 non-commercial and CGAL
> then, when I tried to complie the code in Miscosoft Visual C++ 2005, I get
> the following errorerror LNK2019: 無法解析的外部符號 "__declspec(dllimport) public:
> virtual __thiscall QApplication::~QApplication(void)"
> (__imp_??1QApplication@@UAE@XZ) 在函式 _main 中被參考 tr.obj


You need to recompile Qt3 non-commercial using Visual C++. The one you use is probably for MinGW (a sort of g++ compiler, for Windows), and that version is not binary-compatible with C++ code made by Visual C++. Unfortunately, Trolltech does not support the compilation of Qt3 non-commercial using Visual. You will need to find patches on the Internet.


Are you stuck with Qt3 ? The free version of Qt4 is quite easily compilable using Visual C++. Next release of CGAL, 3.4, has some demos that have been reworked with Qt4. The 2D Triangulation demo has been is now using Qt4. A beta version of CGAL-3.4 has been released yesterday. If you feel sufficiently adventurous to test a beta software, maybe you will be more successful with that new versions of CGAL and Qt


--
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/


Reply | Threaded
Open this post in threaded view
|

Re: performance of Delaunay Triangulation of random

Sylvain Pion
Administrator
In reply to this post by Feng Ding
Ding wrote:
> Another question is that if the 3D points are all on a smooth surface, e.g.,
> vertices on a surface mesh, is there any way to accelerate DT on such points?

There is nothing special to do for such point distributions.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: about using qt3 to dislay a triangulation

Kwok Jasper
In reply to this post by Laurent Rineau (GeometryFactory)
Thank you very much for your reply.
 
May I ask for something about the istallation of the CGAL3.4 ?
In the installation manual, it said that the configuration has to be done using cmake.
 
But I cannot find cmake-gui inside the package on the CGAL3.4.
And when I typed cmake-gui in the cmd of the window XP, nothing happen.
 
May I ask if the cmake-gui is something that I should download somewhere in the Internet?
 
Thank you very much
 
 
 
 



From: [hidden email]
To: [hidden email]
Date: Sat, 20 Dec 2008 18:58:50 +0100
Subject: Re: [cgal-discuss] about using qt3 to dislay a triangulation generated

On Saturday 20 December 2008 17:46:32 Kwok Jasper wrote:
> Excuse me, may I ask something about using Qt3.2.1 Non-commercial with
> CGAL?
>
> I have installed Qt3.2.1 non-commercial and CGAL
> then, when I tried to complie the code in Miscosoft Visual C++ 2005, I get
> the following errorerror LNK2019: 無法解析的外部符號 "__declspec(dllimport) public:
> virtual __thiscall QApplication::~QApplication(void)"
> (__imp_??1QApplication@@UAE@XZ) 在函式 _main 中被參考 tr.obj


You need to recompile Qt3 non-commercial using Visual C++. The one you use is probably for MinGW (a sort of g++ compiler, for Windows), and that version is not binary-compatible with C++ code made by Visual C++. Unfortunately, Trolltech does not support the compilation of Qt3 non-commercial using Visual. You will need to find patches on the Internet.


Are you stuck with Qt3 ? The free version of Qt4 is quite easily compilable using Visual C++. Next release of CGAL, 3.4, has some demos that have been reworked with Qt4. The 2D Triangulation demo has been is now using Qt4. A beta version of CGAL-3.4 has been released yesterday. If you feel sufficiently adventurous to test a beta software, maybe you will be more successful with that new versions of CGAL and Qt


--
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/




Reply | Threaded
Open this post in threaded view
|

Re: about using qt3 to dislay a triangulation

andreas.fabri
Kwok Jasper wrote:
> Thank you very much for your reply.
>  
> May I ask for something about the istallation of the CGAL3.4 ?
> In the installation manual, it said that the configuration has to be
> done using cmake.


Please have a look at the installation manual
http://www.cgal.org/Manual/3.4/doc_html/installation_manual/Chapter_installation_manual.html#Subsection_2.2

where we write:


2.2   cmake

In order to configure, build and install the CGAL libraries, as well as the examples and demos, you need CMake, a cross-platform ``makefile generator''. If CMake is not
installed already you can obtain it from http://www.cmake.org/. We recommend the usage of CMake release 2.6, and you need at least CMake release 2.4-patch-7.


Best regards,

andreas

>  
> But I cannot find cmake-gui inside the package on the CGAL3.4.
> And when I typed cmake-gui in the cmd of the window XP, nothing happen.
>  
> May I ask if the cmake-gui is something that I should download somewhere
> in the Internet?
>  
> Thank you very much
>  
>  
>  
>  
>
>
> ------------------------------------------------------------------------
> From: [hidden email]
> To: [hidden email]
> Date: Sat, 20 Dec 2008 18:58:50 +0100
> Subject: Re: [cgal-discuss] about using qt3 to dislay a triangulation
> generated
>
> On Saturday 20 December 2008 17:46:32 Kwok Jasper wrote:
>  > Excuse me, may I ask something about using Qt3.2.1 Non-commercial with
>  > CGAL?
>  >
>  > I have installed Qt3.2.1 non-commercial and CGAL
>  > then, when I tried to complie the code in Miscosoft Visual C++ 2005,
> I get
>  > the following errorerror LNK2019: 無法解析的外部符號
> "__declspec(dllimport) public:
>  > virtual __thiscall QApplication::~QApplication(void)"
>  > (__imp_??1QApplication@@UAE@XZ) 在函式 _main 中被參考 tr.obj
>
>
> You need to recompile Qt3 non-commercial using Visual C++. The one you
> use is probably for MinGW (a sort of g++ compiler, for Windows), and
> that version is not binary-compatible with C++ code made by Visual C++.
> Unfortunately, Trolltech does not support the compilation of Qt3
> non-commercial using Visual. You will need to find patches on the Internet.
>
>
> Are you stuck with Qt3 ? The free version of Qt4 is quite easily
> compilable using Visual C++. Next release of CGAL, 3.4, has some demos
> that have been reworked with Qt4. The 2D Triangulation demo has been is
> now using Qt4. A beta version of CGAL-3.4 has been released yesterday.
> If you feel sufficiently adventurous to test a beta software, maybe you
> will be more successful with that new versions of CGAL and Qt
>
>
> --
> Laurent Rineau, PhD
> Engineer at GeometryFactory
> http://www.geometryfactory.com/
>
>
>
> ------------------------------------------------------------------------

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss