CGAL users discussion list

[Marius Kintel <>]

Hi all,

This is a bit long, but I believe it’s a valid issue:

I’ve encountered another corner case, eventually causing a segmentation fault 
in CGAL.
See attached test program and nef3 file. The nef3 file was serialized from 
the result of a union.

What I’m doing:
o Iterate over all facets in the Nef polyhedron and collect vertices for all 
cycles. This gives me polygons (possibly with holes).
o Extract the plane normal vector from each facet’s plane.
o Pass each polygon and normal to the constrained delaunay triangulator 
(using filtered projection traits)
o (for simplicity I ignore holes in this test program)

What goes wrong:
o One of the planes reports a wrong normal vector
o When passing this normal vector to the delaunay triangulator, it goes into 
an infinite recursion while repeatedly reporting "intersection not inside”
o ..and eventually crashes (stack overflow)

FYI: One of the polygons in question:
6, -25,  29.285714285714285
6, -26.732050855686023,  29.020513307787397
6, -26.732050855686026,  29.020513307787397
6, -26,  29.132600433972414

..with the (clearly wrong) normal vector [14, -3.751289, 24.5]

I can reproduce the problem by passing _only_ this polygon and normal 
directly to the CDT, but I can see how a proper normal is a valid 
precondition.

Also, just FYI, the reason I’m doing it this way, instead of e.g. going 
through a Polyhedron, is that Polyhedrons have a strict manifold requirement, 
and some of my Nef polyhedrons are not technically manifold (e.g. two objects 
sharing an edge). Of course, there might be more elegant ways of resolving 
this but I haven’t found any.

Any idea why this goes wrong?
My proposed workaround is to assume that planes we get from Nef polyhedrons 
are broken and always calculate our own normals instead.

Cheers,

 -Marius

Attachment: crash.nef3.gz
Description: GNU Zip compressed data

Attachment: nefcrash.cpp
Description: Binary data