The GNU Triangulated Surface Library

I haven't looked at GTS's Delaunay code at all, so take what I say with a
grain of salt.  I suspect this is probably due to the algorithm used rather
than any compliation or implementation issues.  The Delaunay algorithm in
GTS is an incremental one (you can add and remove sites dynamically), and
these unfortunately tend to be less time-efficient than non-incremental ones
where you give it the whole point set and let 'er rip.

Not to turn you away from GTS, but if all you're doing is 2-D Delaunay, and
you don't need incremental insertion or deletion, you might want to take a
look at QHull (http://www.geom.umn.edu/software/qhull/) or Triangle
(http://www.cs.cmu.edu/~quake/triangle.html).  QHull is fairly actively
maintained, don't know much about Triangle, but I do know both seem to be
well-respected.

> -----Original Message-----
> From: gts-general-admin@...
> [mailto:gts-general-admin@... Behalf Of Charles
> Werner
> Sent: Friday, June 15, 2001 4:36 AM
> To: gts-general@...
> Subject: [gts-general] gts delaunay performance
>
>
> I am working with triangulations of large data sets > 500000
> points. Consequently speed is
> an important criterium.  When I run the delaunay program in the
> test directory the speed
> for 10000 points is about 15 seconds on a PII 450 Mhz machine
> running Linux. This is an order
> of magnitude slower than I had expected.  Is there some way to
> speed this up with GTS?
> I used the normal compilaton flags generated by the configure script
>
> Thanks
>
> Dr. Charles L. Werner
> Gamma Remote Sensing AG
> Thunstrasse 130
> CH-3110 Muri b. Bern, Switzerland
>
> Tel: +41 31 951.7005
> FAX: +41 31 951.7008
> http://www.gamma-rs.ch
>
>
> _______________________________________________
> Gts-general mailing list
> Gts-general@...
> http://lists.sourceforge.net/lists/listinfo/gts-general
>

Charles Werner writes:
 > I am working with triangulations of large data sets > 500000 points. Consequently speed is
 > an important criterium.  When I run the delaunay program in the test directory the speed
 > for 10000 points is about 15 seconds on a PII 450 Mhz machine running Linux. This is an order
 > of magnitude slower than I had expected.  Is there some way to speed this up with GTS?
 > I used the normal compilaton flags generated by the configure script

Hi Charles,

The "cartesian" test case in the test suite is a very particular case
where many vertices are almost (or exactly) cocircular or colinear
(they are the vertices of a regular square cartesian grid) which means
that the adaptive floating-point geometric predicates must be used
down to absolute (not machine) accuracy which is much slower than in
the general case.

Here is a comparison of triangulation speeds between this cartesian
test case and a "random" test case where the vertices coordinates are
chosen randomly.

This is on a pentium 350 so you should expect higher figures on your
machine.

# cartesian test case
# of vertices  speed (vertices/s)
1024		2722
2025		2048
4096		1466
8100		1021
16384		693

# random test case
# of vertices  speed (vertices/s)
1000		9356
2000		8647
4000		7627
8000		7157
16000		6248
32000		5516
64000		4763
128000		4072

There is indeed an order of magnitude difference in speed. You can
also note that the speed decreases with the number of vertices
added. The asymptotic behaviour for the time taken by the algorithm is 
actually in n^1/3 where n is the number of vertices to triangulate.

If you are only interested in triangulating a point set without
dynamic insertion or deletion and that speed is your primary concern,
I would agree with Gary and you should probably use triangle
(http://www.cs.cmu.edu/~quake/triangle.html).

Cheers,

Stephane

Stephane, any suggestions as to use of the various
parameters
in the example program "coarsen?

I want to maximize keeping the free edges the same while
coarsening
the interior of each surface.

And I would rather any coarsening stay reasonably close to
the
original shape. What I really want to avoid are the
horrendous
spikes I seem to get.

Tom Browder

Tom Browder writes:
 > Stephane, any suggestions as to use of the various
 > parameters
 > in the example program "coarsen?
 > 
 > I want to maximize keeping the free edges the same while
 > coarsening
 > the interior of each surface.
 > 
 > And I would rather any coarsening stay reasonably close to
 > the
 > original shape. What I really want to avoid are the
 > horrendous
 > spikes I seem to get.

Hi Tom,

Can you send me the file you start with and the file you obtain
together with the command line you used?

Thanks,

Stephane

Ok, but first let me explain what I have done:

I have a collection of components each consisting
of one or more connected sets of triangles.  One
component at a time I turn them into a GTS file,
operate on the file with coarsen, and then read
the results back into my program.

The test case at hand consists of about 300
such components (i.e., about 600 files).  I'll
try to trim that down some.

Tom Browder

Stephane, attached is a tarball with four files
(I think the names are self-explanatory):

1. The input file of triangles for coarsen.
2. The output from running "coarsen < infil > outfil" (note
I used default arguments).
3. An eps file of the input data set.
4. An eps file of the output set.

Thanks for taking a look.

Tom Browder

Tom Browder writes:
 > Stephane, attached is a tarball with four files
 > (I think the names are self-explanatory):
 > 
 > 1. The input file of triangles for coarsen.
 > 2. The output from running "coarsen < infil > outfil" (note
 > I used default arguments).
 > 3. An eps file of the input data set.
 > 4. An eps file of the output set.
 > 
 > Thanks for taking a look.
 > 
 > Tom Browder

Hi Tom,

Thanks for the file. I am afraid the coarsening routine in GTS can't
be of much help for what you want to do. The object you want to
coarsen is already very "coarse" (only 912 faces) and moreover is made 
of many disconnected components. The coarsening algorithm of GTS will
try and coarsen each element individually i.e. in your case it will
try to coarsen the box-shaped elements, cylinders etc... Each of these 
elements are very coarse already (12 faces or so for the box-shaped
elements for example) and not much coarsening can be done. Moreover
GTS conserves the volume of the elements being coarsened (this is a
desirable property both for practical purpose and for visual
accuracy). That's why in the coarsened output you see very thin and
long tetrahedra replacing (for example) your box-shaped elements.

It is important to realize that visually pleasing coarsening of an
original mesh can be obtained only if the mesh is over-resolved for
the graphical accuracy you require. Which is obviously not the case
for the example you sent.

Stephane

Thanks, anyway.  I am stuck with inputs of known
non-manifold and degenerate surfaces at the moment
and have no choice about it.

Tom Browder