CGAL users discussion list

[Ben Supnik <>]

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: 

Developer mailing list: