export to STL causes crash [$50 awarded]

[ecopoesis]

When combined with fume_extractor_head.stl from http://www.thingiverse.com/thing:69729 I can render correctly, but when I export the STL OpenSCAD crashes, leaving a 0 byte STL file. THis is using 2013.1 on MacOS 10.8.4

// print_anchors.scad
// Prescott Ogden <ogden@pres.co.tt>

// This is a very simple script that takes an stl file as input and generates 
// a model with print anchors, as seen in thing 16596.
// It was written to enable designers to distribute files that may need such
// anchors in a way that is not process-specific, and can be used on well
// calibrated FDM machines as well as with SLS and LOM technologies.
// A user who needs print anchors can apply this script as a pre-processing step,
// before handing to a toolpath generator. Ideally, this will be made obsolete by 
// plugins to various toolpath generators, and ultimately improvements in raftless
// printing, but for now, this is extremely simple to implement and acheives 
// the desired effect.

file = "fume_extractor_head.stl"; // The input file, with printbed on xy plane.
anchor_height = 0.3; // height of print anchor in mm,
anchor_margin = 15;  // distance the anchor extends from the base of the part

epsilon = 0.001; // a very tiny distance, because openSCAD cannot yet 
            // do minkowski sums in 2D

union(){
    minkowski(){
        linear_extrude( height = epsilon, center = false, convexity = 10, twist = 0)
            projection (cut = true) import(file);

        cylinder(r = anchor_margin, h = anchor_height - epsilon, center = false);
    }

    translate([0, 0, anchor_height])
        import(file);
}

--- The **[$50 bounty](https://app.bountysource.com/issues/416595-export-to-stl-causes-crash?utm_campaign=plugin&utm_content=tracker%2F52063&utm_medium=issues&utm_source=github)** on this issue has been claimed at [Bountysource](https://app.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F52063&utm_medium=issues&utm_source=github).

[kintel]

See also https://github.com/openscad/openscad/blob/master/testdata/scad/bugs/stl-cgal-convert_to_Polyhedron-crash.scad

I thought we had an issue on this, but apparently not..

As this looks like a CGAL bug, we should try to reproduce this in an isolated CGAL example and submit it to them.

[kintel]

Here's the stack trace. The crash happens in CGAL's Nef_polyhedron_3::convert_to_Polyhedron() method.

There are two issues we should resolve: 1) Be able to export, since the model itself looks like it's a valid manifold 2) If 1) is somehow not possible, catch the crash so the it doesn't take the OpenSCAD process down

#0  0x00007fff8bc6e212 in __pthread_kill ()
#1  0x00007fff8a119b24 in pthread_kill ()
#2  0x00007fff8a15df61 in abort ()
#3  0x00007fff892f89eb in abort_message ()
#4  0x00007fff892f639a in default_terminate() ()
#5  0x00007fff8301a887 in _objc_terminate() ()
#6  0x00007fff826f7527 in std::terminate() ()
#7  0x0000000100008c36 in __clang_call_terminate ()
#8  0x000000010018344e in CGAL::Nef_polyhedron_3<CGAL::Epeck, CGAL::SNC_indexed_items, bool>::Build_polyhedron<CGAL::HalfedgeDS_default<CGAL::Epeck, CGAL::I_Polyhedron_derived_items_3<CGAL::Polyhedron_items_3>, std::allocator<int> > >::operator()(CGAL::HalfedgeDS_default<CGAL::Epeck, CGAL::I_Polyhedron_derived_items_3<CGAL::Polyhedron_items_3>, std::allocator<int> >&) at include/CGAL/Nef_polyhedron_3.h:827
#9  0x0000000100182df0 in CGAL::Polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> >::delegate(CGAL::Modifier_base<CGAL::HalfedgeDS_default<CGAL::Epeck, CGAL::I_Polyhedron_derived_items_3<CGAL::Polyhedron_items_3>, std::allocator<int> > >&) at include/CGAL/Polyhedron_3.h:1400
#10 0x0000000100182abc in void CGAL::Nef_polyhedron_3<CGAL::Epeck, CGAL::SNC_indexed_items, bool>::convert_to_polyhedron<CGAL::Polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> > >(CGAL::Polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> >&) const at include/CGAL/Nef_polyhedron_3.h:1044
#11 0x00000001001701bd in void CGAL::Nef_polyhedron_3<CGAL::Epeck, CGAL::SNC_indexed_items, bool>::convert_to_Polyhedron<CGAL::Polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> > >(CGAL::Polyhedron_3<CGAL::Epeck, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default, std::allocator<int> >&) const at include/CGAL/Nef_polyhedron_3.h:1035
#12 0x000000010016d1e5 in export_stl(CGAL_Nef_polyhedron*, std::ostream&) at openscad/src/export.cc:45

[donbright]

re the uncatchable exception we may be looking at this.

http://stackoverflow.com/questions/18044666/gcc-4-8-1-c11-shared-libraries-and-exception-handling-trouble

working on it...

[donbright]

yeah it looks like CGAL is calling an C++ Exception from the destructor of uhm... specifically it's ::~Polyhedron_incremental_builder_3

  /usr/include/CGAL/Polyhedron_incremental_builder_3.h:201

   ~Polyhedron_incremental_builder_3() {
        CGAL_assertion( check_protocoll == 0);
    }

If you run gcc -E this unpacks to....

    ~Polyhedron_incremental_builder_3() {
         (CGAL::possibly(check_protocoll == 0)?(static_cast<void>(0)): ::CGAL::assertion_fail( "check_protocoll == 0" , "/usr/include/CGAL/Polyhedron_incremental_builder_3.h", 200));
     }

and assertion_fail is:

    __attribute__ ((visibility ("default"))) void assertion_fail ( const char*, const char*, int, const char* = "") __attribute__ ((__noreturn__));

assertion_fail is some kind of function from cgal:

 assertion_fail( const char* expr,
            const char* file,
            int         line,
            const char* msg)
{
   _error_handler("assertion", expr, file, line, msg);
   switch (_error_behaviour) {
   case ABORT:
       std::abort();
   case EXIT:
       std::exit(1);  // EXIT_FAILURE
   case EXIT_WITH_SUCCESS:
       std::exit(0);  // EXIT_SUCCESS
   case CONTINUE: // The CONTINUE case should not be used anymore.
   case THROW_EXCEPTION:
   default:
       throw Assertion_exception("CGAL", expr, file, line, msg);
   }
 }

Since the CGAL Behaviour has been set by OpenSCAD to be THROW Exception, we get this:

          'throw Assertion_Exception'

Which is...

 class Assertion_exception : public Failure_exception {
public:
   Assertion_exception( std::string lib,
                   std::string expr,
                   std::string file,
                   int line,
                   std::string msg)
       : Failure_exception( lib, expr, file, line, msg,
                           "assertion violation") {}
    };

Failure Exception is apparently a collection of strings and std::logic_error

So those exceptions are being thrown from the Destructor of CGAL's Incremental_Polyhedron_Builder if it fails for some reason.... and it will fail if the input data has some kind of problem, since it does lots of internal quality checks as you add facets to the Polyhedron.

And since CGAL's Nef Polyhedron uses Incremental Polyhedron Builder to convert itself to an 'ordinary' Polyhedron, ... its going to have this issue if the Nef has some kind of malformation that it feeds to the Builder.

So I guess maybe the solution to 'cant catch' the exception is perhaps somewhere in looking into how compilers deal with exceptions thrown in a destructor. There are a lot of websites discussing problems that happen when exceptions are thrown from a destructor. There have apparently been some changes recently in GCC for exception handling and destructors, although it will require more research to see if thats the exact issue

hrm....

[kintel]

hm, question is if it makes sense to report it to CGAL, but not sure there is much they can do either.

[GilesBathgate]

FYI the exception I get from rapcad when I try to export the same STL is:

 sorry, this triangulation does not deal with
 intersecting constraints
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: check_protocoll == 0
File: /usr/include/CGAL/Polyhedron_incremental_builder_3.h
Line: 198

[GilesBathgate]

I think the real exception is being hidden by the check in Polyhedron_incremental_builder_3.h The exception: sorry, this triangulation does not deal with intersecting constraints is coming from /usr/include/CGAL/Constrained_triangulation_2.h line 623

[kintel]

@GilesBathgate Are you saying that you export STLs in a different way than OpenSCAD (i.e. not going through a Polyhedron3) ?

[GilesBathgate]

No the exception trace in my first message was with the "non-experimental" stl export, its essentially the same as openscads version. Afterwards I was trying to get to the root of the problem. I made a hack whereby I redefined the CGAL_assertion() macro from CGAL/assertions.h so that I could hook the assertion_fail function into my own code. I was then able to ignore the specific assertion fail coming from the destructor of Polyhedron_incremental_builder_3, by just looking at the line parameter (don't throw exception if line==198). My hope was that I could prevent a process terminate crash by not allowing an exception thrown from the destructor. Alas I just uncovered the new assertion fail from line 623.

[GilesBathgate]

Given the original error message though and my investigations, I think that the CGAL_assertion( check_protocoll == 0); is a red herring. You might have better luck debugging from /usr/include/CGAL/Constrained_triangulation_2.h line 623 (Thats where I would put my breakpoint)

[donbright]

the problem is that when they throw the exception inside the Destructor for Polyhedron Incremental Builder, it "hides" the Triangulation exceptions.

There are literally dozens of pages on the internet describing all the problems that are caused by throwing Exceptions inside of destructors.

I have a solution but I'm not sure what you will think of it Marius

Basically I go into CGAL's Nef_Polyhedron3.h and rip out out Triangulation_handler2, Build_polyhedron, and convert_to_Polyhedron.

Then I put them in a file, nef_helper.h. I insert a handful of lines, for example a try() catch() around the Triangulation code, and an error variable in the PolyhedronBuilder to communicate with the calling process without using Exceptions. Then I go through OpenSCAD and replace all the calls to Nef3->convert_to_Polyhedron with nefhelper_convert_nef_to_poly() ....

The result is that the stated .stl / .scad file no longer crashes the program. It prints out a Warning about a corrupted Mesh. And indeed, when you open up the resulting STL, it is 'partially built', in other words an entire face of the polyhedron is essentially 'missing'.

Now if you want to fix that.... I'd say you need to switch out the triangulator with something else. Maybe some pre-processing, maybe just a better algorithm. That's actually what you have to do anyways if you want 'customizable' face tessellation from Nefs into STL . . . so it's not actually a crazy idea. I have an experimental dead-simple "ear clipping" triangulator that essentially replaces CGAL's face triangulation process.

[kintel]

@donbright I think making our process not crash is a decent enough fix for now. Invalidating the STL instead of partially outputting it is probably smarter to avoid exporting broken files. We can always report this as a bug to CGAL, so that we can remove our code in the future.

To be more robust is a different issue, but we should probably open an issue on that topic for future hacking.

[GilesBathgate]

If you don't want openscad to crash why not just use -DCGAL_NDEBUG as a compile option? This will disable the CGAL_assertions...

[kintel]

Hm, I thought the assertions were there to avoid the underlying CGAL algorithms crashing hard?

[GilesBathgate]

I think essentially what I am getting at is you should detect the cause, not fix the symptom.

[kintel]

I agree - the question is how to detect what causes CGAL to throw that exception so that we can avoid calling convert_to_Polyhedron() if we know it will crash? (without essentially doing the same calculation twice)

[donbright]

Right on, I will submit a patch sometime soon (TM).

So when CGAL's Nef Face Triangulator fails, you want to output an ERROR: message and then .. basically, stop the render?

On Sun, Nov 24, 2013 at 11:51 AM, Marius Kintel notifications@github.comwrote:

I agree - the question is how to detect what causes CGAL to throw that exception so that we can avoid calling convert_to_Polyhedron() if we know it will crash? (without essentially doing the same calculation twice)

— Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/410#issuecomment-29161133 .

[kintel]

@donbright Yes, that's a good enough fix. Next step is to be able to export it, but that's another issue. This issue is just about making it not crash.

[donbright]

that patch will stop the crash, but it wont actually generate an STL (ecopoesis' original issue)

another note, ecopoesis original fume hood example takes over 20 minutes to render anything, its not a good example.

[donbright]

"I agree - the question is how to detect what causes CGAL to throw that exception so that we can avoid calling convert_to_Polyhedron() if we know it will crash? (without essentially doing the same calculation twice) "

IMHO it's a question of Garbage In, Garbage Out. I think that taking an arbitrary junky STL model input and transforming it into a 2-manifold is a highly non-trivial problem. CGALS Nef Polyhedron is_simple and/or is_valid simply "Just Don't Work" like they are supposed to.

Now the fact that OpenSCAD's export might be generating the garbage in the first place, is a different issue. even if OpenSCAD has a perfect export routine, that wont stop other STL generation programs from creating junk that we need to deal with.

[kintel]

The bounty was for the crash fix. The STL issue is a larger issue.

[ccverg]

@donbright you should go claim the bounty on this issue!

[kintel]

@donbright What do you think about @GilesBathgate's alternative workaround? https://github.com/GilesBathgate/RapCAD/blob/1c8a5efb2237863579cd8d3778152576814352a6/src/cgalassert.h

[donbright]

It's theoretically better than mine because its short and sweet.

On Thu, Jan 2, 2014 at 3:31 PM, Marius Kintel notifications@github.comwrote:

@donbright https://github.com/donbright What do you think about @GilesBathgate https://github.com/GilesBathgate's alternative workaround? https://github.com/GilesBathgate/RapCAD/blob/1c8a5efb2237863579cd8d3778152576814352a6/src/cgalassert.h

— Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/410#issuecomment-31486406 .

[GilesBathgate]

I would like to submit a nice clean patch for this for the CGAL people to consider. My Idea was to create a new assert macro called CGAL_assertion_in_destructor(EX), which would have the following:

#define CGAL_assertion_in_destructor(EX) \
   (CGAL::possibly(EX)||std::uncaught_exception()?(static_cast<void>(0)): ::CGAL::assertion_fail( # EX , __FILE__, __LINE__))

And then amend Polyhedron_incremental_builder.h to use that macro instead of the current one.

[kintel]

I asked on the mailing list recently, but no answer yet: http://cgal-discuss.949826.n4.nabble.com/Uncatchable-exception-converting-from-Nef-polyhedron-to-Polyhedron-3-td4658603.html

[GilesBathgate]

Well perhaps it went under the radar. If I post, perhaps add a bit more wording about the technical nuances of throwing from a destructor, and give a patch, it might receive some attention.