CGAL users discussion list

[Monique Teillaud <>]

Le 23/01/12 11:38, Laurent Rineau (GeometryFactory) a écrit :
> Le lundi 23 janvier 2012 09:48:05 Monique Teillaud a écrit :
> > Dear Juan Carlos,
> >
> > You can use another library, it will not change the Delaunay
> > triangulation. The Delaunay triangulation is known to have slivers, i.e.
> > tetrahedra whose vertices are almost coplanar and cocircular. As long as
> > they have an empty circumscribing sphere, they are Delaunay tetrahedra.
> > There is a huge literature on this topic.
>
> In a Delaunay triangulation you can have every all types of almost degenerate
> tetrahedra, not only slivers.
>
> > You may want to use another triangulation. The regular triangulation, or
> > weighted Delaunay triangulation, allows to avoid slivers. So, you can
> > probably use the CGAL 3D Regular Triangulation, but you will need to
> > choose the weights of your points in an appropriate way.
> > There is in particular a paper by Dey, Edelsbrunner and others about
> > this method (I don't have time right now to dig for the precise reference).

@inproceedings{cdeft-se-99
, author =      "Siu-Wing Cheng and Tamal K. Dey and Herbert
Edelsbrunner and Michael A. Facello and Shang-Hua Teng"
, title =       "Sliver Exudation"
, booktitle =   "Proc. 15th Annu. Sympos. Comput. Geom."
, year =        1999
, pages =       "1--13"
}

@article{cdeft-se-00
, author =      "Siu-Wing Cheng and Tamal K. Dey and Herbert
Edelsbrunner and Michael A. Facello and Shang-Hua Teng"
, title =       "Sliver Exudation"
, journal = "J. ACM"
, volume = 47
, year = 2000
, pages = "883--904"
}

> > In fact this method is already coded in the 3D CGAL mesh package as one
> > of the optimization methods to improve dihedral angles, you might be
> > able to reuse some code from this method.
>
> Those optimization methods have been designed to work on regular
> triangulations that are made by the mesh generator that does Delaunay
> refinement. Those special triangulations are known to have no almost
> degenerate tetrahedra but slivers. That is a special case of Delaunay
> triangulations. I cannot certify that those optimization methods can do
> anything useful on other triangulations.


--
Monique Teillaud
INRIA Sophia Antipolis - Méditerranée
http://www.inria.fr/sophia/members/Monique.Teillaud/