CGAL users discussion list

[Matthijs Sypkens Smit <>]

On Tuesday 16 October 2007 11:29, Laurent Rineau wrote:

> On Wednesday 10 October 2007 11:53:50 Matthijs Sypkens Smit wrote:
> > Using a CGAL Nef polyhdron to do inside/outside tests on a polyhedron
> > is relatively inefficient in my experience. From the limited tests
> > that I did with some triangulated models it was in the order of 10000
> > times slower than using a (constrained) Delaunay triangulation.
> > Another very fast method is the use of a binary space partition of
> > your triangulated models. Both methods (Delaunay and BSP) have the
> > drawback that the initial data structure is hard to create.
>
> Mister Sypkens Smit, do you have an implementation of such a data
> structure, that is usable for that task?

Dear Laurent,

I do not have an implementation of a 3D BSP. For the construction of 
constrained Delaunay triangulations I have been using Tetgen[1]. Tetgen 
creates the triangulation and from Tetgen's datastructure I construct a 
CGAL Triangulation, that is effectively a CDT. Drawback is that I had to 
make a small modification to the Tetgen source. I think it should be 
possible to do it without the modification, but I don't have that 
currently. Also, Tetgen fails on some models. I have not investigated it 
in detail, so I cannot be sure if it is the robustness of Tetgen or that 
the fault lies with the models.

1] http://tetgen.berlios.de/

So, I guess the answer depends on your definition of "usable for the task". 
If you are still interested, I can send you code/instructions privately. 
It is by no means suitable for release or incorporation into CGAL.


I have also partly implemented the algorithm of Cohen-Steiner/de 
Verdière/Yvinec for creating a conforming Delaunay triangulation. This is 
not finished yet, but it is very slow and resource-intensive on large 
models (containing a lot of triangles). It also tends to yield many more 
elements than you originally started with.


-- 
Matthijs Sypkens Smit