When CGAL falls down

I my last post I fantasized about breaking CGAL Nef Polyhedra (computer geometry shapes) down by it’s “Volumes”, and then making those into new Polyhedra, so we can get colors so we can have multicolor 3d printing AMF output from OpenSCAD.

And lo and behold, in theory it is not as hard as it looks – in fact several people have tried similar things before. For each volume in a Nef Polyhedron, make a new Polyhedron and Do Something With It.

The problem is, however, that this Crashes. Alot.

The problem is convert_inner_shell_to_polyhedron. If you google that function name you will come along several posts to the CGAL mailing list that give almost no information, other than the thing crashes alot. Alot.

Its theoretically undocumented, although it is kind of documented here, when discussing another topic:


And you can find it if you are wandering around inside of the CGAL source code for Nef Polyhedron.

But you know, it basically Doesnt Work.

Why shouldn’t it? I found that it crashed on several OpenSCAD Examples, These are Nef Polyhedrons that can be converted to a polyhedron perfectly well. OpenSCAD has been converting them for a long time – even in it’s test suite it does this. And that thing runs on everything from PPC64 to x86_32 to even, recently, ARM.

But if you try to take the volumes within the nef polyhedrons and make them into Ordinary CGAL Polyhedrons using that conversion function, it doesnt work. It just goes ‘blargh’ and dies.


lookup_halfedge(): input error: facet 26 shares a halfedge from vertex 0 to vertex 1 with facet 2.
CGAL error: assertion violation!
Expression : check_protocoll == 0
File       : ../openscad_deps/include/CGAL/Polyhedron_incremental_builder_3.h
Line       : 199
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html


add_vertex_to_facet(): vertex index 65 is out-of-range [0,39].
CGAL error: assertion violation!
Expression : check_protocoll == 0
File       : ../openscad_deps/include/CGAL/Polyhedron_incremental_builder_3.h
Line       : 199
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html


and on and on.



So what is going on? I don’t know.

There are two possibilities that might fix, that come to mind immediately….


One is this, again, found thru a google search of the function name.


By using an ‘Exact’ kernel, they appear to have an example of using the conversion function that the other examples dont do.

So something to try is to see if OpenSCAD using an ‘exact’ kernel will work (right now its not using an Exact kernel, although Marius recently added a branch that experiments with it). Maybe it will not crash.




The other thing to try, is to get down and dirty into the guts of the code that CGAL normally uses to convert Nef Polyhedron into ordinary Polyhedron. Including stuff like Incremental Polyhedron Builder and its related other pieces of code.

And it is not pretty. CGAL source code presumes a lot of familiarity with what is going on, and especially with really, really convoluted C++ STL tricks like templated function objects, delegators, etc etc etc. This ain’t python.


But surely there must be some way. After all. We are just talking about vertexes, and polygons here. It’s not rocket science…. There has to be some way to build a Polyhedron just given some 3d Polygons and Vertexes – – i mean they’ve already been arranged into a ‘shell’ for us… surely it can’t be impossible?

It might be super slow — but in the end it may be possible to simply reuse OpenSCADs own guts – create an OpenSCAD PolySet (somewhat straightfoward) and then feed that through the Polyhedron Creation code. Then use the ‘is_simple()’ quality control feature and Then. Output our AMF triangles.


The good news.


For two individual cubes, like this SCAD code:



translate([10,10]) cube(5);


it can currently output AMF with two distinct volumes. If only it didn’t crash we could be quite far along here. (famous last words?)



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s