CGAL users discussion list

[Monique Teillaud <>]

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.

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).

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.

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

Le 23/01/12 00:37, Juan Carlos Lopez Alfonso a écrit :
> Hi There
>
> Again I want to ask about the coplanar test in 3D Delaunay
> triangulation, because after read the documentation I have not solved my
> problem. I have tested different Delaunay tirangulations and in
> different cases (different distributions of points) the resultant
> triangulations have several almost coplanar tetrahedras (very very small
> volume) and these are no very good triangulations. Before attempting to
> use another library to triangulate, I have some questions:
>
> - if Delaunay  triangulations are not uniques, Are there forms in Cgal
> to obtian different Delaunay triangulations for the same point
> distributions? in order to avoid this problem.
>
> - Are there forms in CGAL to impose a minimum volume for tetrahedras?
> something like a epsilon?
> On the other hand, I still do not understand how in cgal when the
> jacobian using double precision is equal to zero, the triangulation give
> us coplanar tetrahedras (where the jacobians are about 1.0e-18). I will
> use this triangulation to optimizing a variational problem, and when the
> algorithm detect this tetrahedras the results are unexpected and erroneous.
>
> Could you give suggestions to obtain better triangulations?
>
> Sorry for these successive questions, but I dont know what I need to do
> to solve this problem, which is the only thing I need to complete the
> practical part of my model.
>
> Best Regards and thank you in advance
> Juan Carlos