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