STL export of an object with an internal cavity has the internal faces the wrong way round [$150 awarded]

[nophead]

Summary:

• Objects with cavities are exported with the cavity polygons facing the wrong way. This is probably a CGAL bug. See proposed fix from CGAL below
• Objects with cavities (with correct winding) are not converted correctly to Nef polyhedrons and won't behave correctly in CSG operations. This goes both for imported objects and for polyhedron()-defined objects.

To close this issue, both these things should be fixed.

This is with OpenScad 2013.06.

module hollow_cube()
    difference() {
        cube(20, center = true);
        cube(10, center = true);
    }

// set X to 0 and export cube.stl
// set X to 1 to see what it should be
// set X to 2 and see it is broken

x = 0;

if(x == 0)
    hollow_cube();

if(x == 1)
    difference() {
        hollow_cube();
        translate([-20, 0, -20]) cube(100);
    }

if(x == 2) 
    difference() {
        import("cube.stl", convexity = 5);
        translate([-20, 0, -20]) cube(100);
    }

When the object is exported to an STL and then imported again to take a cross section it looks like this.

The exported object is also wrong when cross sectioned in NetFabb stdio.

---

The $150 bounty on this issue has been claimed at Bountysource.

[kintel]

I just verified that this also happens when exporting to OFF.
Rendering the x = 2 object with CGAL is an obvious test case.

I don't have a good idea why this happens. Perhaps @donbright or @GilesBathgate has some input based on experience?

For reference, this is a polyhedron equivalent to the exported STL/OFF file:

difference() {
  polyhedron(faces=[[2,1,0],[3,1,2],[2,5,4],[2,4,3],[1,4,6],[3,4,1],[0,7,5],[0,5,2],[0,6,7],[1,6,0],[5,7,6],[5,6,4],[10,9,8],[11,9,10],[10,13,12],[10,12,11],[9,12,14],[11,12,9],[8,15,13],[8,13,10],[8,14,15],[9,14,8],[13,15,14],[13,14,12]],
points=[[-10,10,10],
        [-10,10,-10],
        [-10,-10,10],
        [-10,-10,-10],
        [10,-10,-10],
        [10,-10,10],
        [10,10,-10],
        [10,10,10],
        [-5,5,5],
        [-5,5,-5],
        [-5,-5,5],
        [-5,-5,-5],
        [5,-5,-5],
        [5,-5,5],
        [5,5,-5],
        [5,5,5]]);
  translate([-20, 0, -20]) cube(100);
}

[donbright]

im pretty sure the problem is here inside CGAL's Nef Polyhedron3 .h code... that is responsible for converting Nef3 into ordinary Polyhedron3 (which then becomes STL in OpenSCAD):

    Visitor V(B,scd,VI);
    typename Nef::Volume_const_handle c;
    CGAL_forall_volumes(c,scd) {
      if(skip_volumes-- <= 0) {
        scd.visit_shell_objects(typename Nef:: SFace_const_handle(c->shells_begin()),V);
      }
    } 

To summarize, on nop head's example, this code above is actually reading the facets of Empty Space inside the cube, and Empty Space facets are oriented backwards from how Objects facets are oriented.

Note the contrast with most other Shell Visitor patterns found on the web for Nef Polyhedrons... this code in Nef Polyhedron does not skip Volumes with mark 0 (Empty Space) volumes, and it also doesnt use the forall_shells code, instead apparently only processing the first shell of each volume. This results in the reading of the 'backwards' facets from the Empty volume inside the cube.

Details:

Just for my own future references, I'd like to recall here in exhausting detail how Nef Polyhedron's deal with Empty Space.. Sort of like the Tao Te Ching, Empty Space is considered Useful, in fact in CGAL it is basically 'just another object', and has the same data structures, features, etc.

A simple cube, for example, has two volumes, each volume has a shell, each shell has 6 halffacets. halffacets are just flat polygons in 3d space.... but the trick is they are 'oriented', with vertices being numbered either clockwise or counterclockwise depending on which side of the polygon should be considered 'inside' or 'outside'.

Volume one actually has a 'mark' of 0, meaning that it represents Empty Space. Volume two is the 'cube', and it has a 'mark' of 1. Both volumes have a shell, and both shells have half-facets. In other words, Empty Space surrounding the cube actually has 6 sides, just like the cube itself has 6 sides.

The halffacets for Empty Space are a bit like a house that has had it's walls turned inside out, like in an old Douglas Adams story. So, if you are 'outside' the cube you are technically 'inside' empty space, so the facets for empty space, when you look at them from the 'inside' of 'empty space', will appear to have their 'inside' faces pointed at you... and vice versa.

As you can then imagine, the Faces for the Cube volume are actually oriented exactly the 'opposite' of the facets for the Empty Space volume. Because for the cube, 'inside' and 'outside' are as we would normally think of them.

Now.... for your example, a cube inside a cube... Nef Polyhedron actually creates three volumes.

The first volume is the empty space 'outside' of the cube. It has 1 shell and six facets.

The second volume is the soild-ness of the cube itself. It has two shells and 12 half-facets. The first shell is the 'outer' shell and the second shell is the 'inner' shell surrounding the hole in it's middle.

The third volume is the 'empty space' that is 'inside' the cube. It has 1 shell and six facets.

You can tell this if you use some of the svg.cc Nef Polyhedron debugging functions. (Look for it in a soon-to-be-submitted patch openscad --debug=all )

Now the problem with the Nef Polyhedron->STL conversion is that when it goes from NefPolyhedron to Polyhedron, in the above code, it is actually skipping over the second shell of the second volume. If you stick some PRINT() statements into CGAL's code, you can see this explicitly happening.

  Visitor V(B,scd,VI);
  typename Nef::Volume_const_handle c;
  CGAL_forall_volumes(c,scd) {
    PRINTB("volume mark",c->mark());
    if(skip_volumes-- <= 0) {
      scd.visit_shell_objects(typename Nef:: SFace_const_handle(c->shells_begin()),V);
    }
  }

Then we go back up to the Visitor code and change this:

        CGAL_NEF_TRACEN("   add vertex " << hc_start->source()->center_vertex()->point();

into

        PRINTB("   add point %s ", hc_start->source()->center_vertex()->point());

and

        CGAL_NEF_TRACEN("  insert point" << sfc->source()->source()->point($ to
        PRINTB("   add point %s ", sfc->source()->source()->point());

The result is as follows

 don@serebryanya:~/openscad/binmaster$ ./openscad x.scad -o x.stl
 CGAL Cache insert: cube(size=[20,20,20],center=true); (10872 bytes)
 CGAL Cache insert: cube(size=[10,10,10],center=true); (10872 bytes)
 CGAL Cache insert: difference(){cube(size=[20,20,20],center (21648 bytes)
 CGAL Cache insert: group(){difference(){cube(size=[20,20,20 (21648 bytes)
 volume mark 0
 volume mark 1
 add point -10/1 10/1 -10/1 
 add point -10/1 -10/1 -10/1 
 add point -10/1 -10/1 10/1 
 add point -10/1 10/1 10/1 

 add point -10/1 -10/1 10/1 
 add point -10/1 -10/1 -10/1 
 add point 10/1 -10/1 -10/1 
 add point 10/1 -10/1 10/1 

 add point 10/1 -10/1 -10/1 
 add point -10/1 -10/1 -10/1 
 add point -10/1 10/1 -10/1 
 add point 10/1 10/1 -10/1 

 add point 10/1 10/1 -10/1 
 add point -10/1 10/1 -10/1 
 add point -10/1 10/1 10/1 
 add point 10/1 10/1 10/1 

 add point -10/1 10/1 10/1 
 add point -10/1 -10/1 10/1 
 add point 10/1 -10/1 10/1 
 add point 10/1 10/1 10/1 

 add point 10/1 -10/1 10/1 
 add point 10/1 -10/1 -10/1 
 add point 10/1 10/1 -10/1 
 add point 10/1 10/1 10/1 

 volume mark 0
 add point -5/1 5/1 -5/1 
 add point -5/1 -5/1 -5/1 
 add point -5/1 -5/1 5/1 
 add point -5/1 5/1 5/1 

 add point -5/1 -5/1 5/1 
 add point -5/1 -5/1 -5/1 
 add point 5/1 -5/1 -5/1 
 add point 5/1 -5/1 5/1 

 add point 5/1 -5/1 -5/1 
 add point -5/1 -5/1 -5/1 
 add point -5/1 5/1 -5/1 
 add point 5/1 5/1 -5/1 

 add point 5/1 5/1 -5/1 
 add point -5/1 5/1 -5/1 
 add point -5/1 5/1 5/1 
 add point 5/1 5/1 5/1 

 add point -5/1 5/1 5/1 
 add point -5/1 -5/1 5/1 
 add point 5/1 -5/1 5/1 
 add point 5/1 5/1 5/1 

 add point 5/1 -5/1 5/1 
 add point 5/1 -5/1 -5/1 
 add point 5/1 5/1 -5/1 
 add point 5/1 5/1 5/1 

We see that basically the program Skips the first Volume. The first volume, we recall, is the empty space on the outside of the cube. No points are added.

Then it goes to the Second volume.... the cube.... but it only processes the First Shell! You can tell because the only points processed are at coordinate '10'. (Note the 10/1 are because our Kernel deals with Rationals.. thats another topic we will not deal with here). If it had processed the second shell, the 'inner' shell, it would have some 5/1 coordinates. But it skips over the second shell.

The problem comes when we process Volume 3, which is the Empty Space 'inside' the cube. Note that it is actually pulling the 'Empty Space' volume's halffacets and putting them into the Polyhedron builder! As we have noted above.... Empty Space shells have half-facets that are oriented exactly the opposite from the Object shell half-facets.

We can look, for example, at the top face... I have grouped the add_point calls into groups of four... consider the group where Z is four +10s, and then compare with the group where Z is four +5s. Note they are both 'counter clockwise' if you look at them from the top! This is a problem. If you think about it, the top face on the outside of the cube should be oriented opposite of the top face of the inside hole-cube. This shows exactly the problem.

Thus. CGAL's Nef polyhedron code is creating backwards facets.

Why does it do this? Again, we can look at the loop code

     Visitor V(B,scd,VI);
     typename Nef::Volume_const_handle c;
     CGAL_forall_volumes(c,scd) {
       if(skip_volumes-- <= 0) {
         scd.visit_shell_objects(typename Nef:: SFace_const_handle(c->shells_begin()),V);
       }
     } 

Compare this with the Visitor Pattern from https://doc.cgal.org/4.2/CGAL.CGAL.3D-Boolean-Operations-on-Nef-Polyhedra/html/index.html .... you can see there is no 'CGAL_forall_shells_of' statement here. It's only visiting the First Shell of the volumes it considers.... and besides that, it's visiting Empty Space volumes! In the other examples of Nef Polyhedron processing you find around the web, typically the code will skip every volume with Mark of 0,,, but for some reason CGAL's own Nef->Ppolyhedron3Builder code is not doing that.

I dont know why CGAL has things working this way. Maybe there is some reason?

Now, in the 'nef polyset' branch of OpenSCAD, where we go Directly from Nef Polyhedron into OpenSCAD's PolySet type, and then directly from that to STL, the resulting facets are, in fact, properly oriented. Why? Because in the 'nef polyset' branch, we are not processing any of the Empty Space volumes. Instead, we follow the visitor pattern code and only process volumes with Mark 1.

This creates the correct STL.

However. Importing is another question. I have not investigated it in depth, but essentially the Nef Builder does not work right, even if your Polyhedron3 input is accurate.

So. We can fix 'export'.... but as for fixing Import.... its a large amount of work IMHO

-DB

[donbright]

Just wanted to add some pictures. This is a 'debug dump' of the Nef Polyhedron generated by nop head's example. a Cube Cavity inside a Cube.

The first volume is Empty Space for the outside of the cube

The second volume is the cube itself, showing the two shells, outer and inner

The third volume is the Empty Space of the cavity inside the cube.

As explained above, the problem here is that CGAL Nef Polyhedron->Polyhedron3 converter is reading the facets from the third volume instead of from the Second Shell of the Second volume.... and since Empty Space facets are oriented 'backwards' from Solid Space facets, we wind up with wrong-facing Polyhedron3 inner facets, and thus wrong STL.

[kintel]

Thanks a lot for that clarification Don! I have a feeling that Nef polyhedrons are not very widely used in the wild, so this might actually be a long-standing bug in CGAL which has gone unnoticed..

[kintel]

I managed to reproduce without OpenSCAD and posted this on cgal-discuss:
http://cgal-discuss.949826.n4.nabble.com/Multiple-volumes-Bug-converting-Nef-polyhedron-to-Polyhedron-3-tt4658599.html

[kintel]

..and I got an answer with a bugfix from the CGAL guys :)
http://cgal-discuss.949826.n4.nabble.com/Multiple-volumes-Bug-converting-Nef-polyhedron-to-Polyhedron-3-tp4658599p4658600.html

A quick check shows that this fixes the issue, at least for this particular model, although the patch might need some work to retest/reintegrate with Don's nef3 workaround.

[GilesBathgate]

@kintel Which nef3 workaround did you mean? If you are taking about the assert throwing an exception from a destructor, did you see my fix, which doesn't require pulling modified copies of the CGAL source code into each our perspective code bases?

[GilesBathgate]

Great news about the convert_all_inner_shells_to_polyhedron function though, do you think this would eventually replace convert_to_polyhedron, or would one have to detect that the polyhedron had inner shells and call the correct function?

[kintel]

@GilesBathgate The workaround was what fixed #410. I cannot recall seeing your fix - did you apply it to RapCAD?

[kintel]

@GilesBathgate AFAIU, convert_all_inner_shells_to_polyhedron() is a suggested replacement for convert_to_polyhedron(). They just didn't apply it yet since they're not sure it works as expected.

[GilesBathgate]

@kintel yeah, in essence I replace:

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

with

    ~Polyhedron_incremental_builder_3() {
        CGAL::possibly(EX)||std::uncaught_exception()?(static_cast<void>(0)): ::CGAL::assertion_fail( # EX , __FILE__, __LINE__))
    }

I do so by with some c preprocessor hacking. But the main point was that it was one line of code, as opposed to dons solution which was a bit more involved. std::uncaught_exception() is the key here.

https://github.com/GilesBathgate/RapCAD/commits/master/src/cgalassert.h

[kintel]

@GilesBathgate pointed out a related issue: When constructing a polyhedron with a cavity, or when importing a correctly oriented STL with a cavity, CGAL will fail to construct a Nef polyhedron which models the cavity correctly. See issue495b.scad which will render incorrectly in CGAL mode.

[GilesBathgate]

The cause of this related issue is actually the way that OpenSCAD, (and RapCAD for that matter) creates Polyhedrons from STL's, and polysets.

We do something along the lines of:

builder.begin_surface(...);

for(...) { //all vertexes
    builder.add_vertex(v);
}

for(...) { //all facets
  builder.begin_facet();
  for(...) { //all vertexes in facet
    builder.add_vertex_to_facet(index);
  }
 builder.end_facet();
}
builder.end_surface();

The clue to how to fix this is actually in the patch provided by Sebastian from CGAL.
see: https://gist.github.com/GilesBathgate/8235625

Basically he is using Triangulation_handler2<YZ> th(f);

I believe adding the triangulation part to the polyset->polyhedron code in OpenSCAD will fix the related issue.
I believe that the later polyhedron->nef conversion should also just work without any further ado.

[donbright]

Cool beans Marius,

However If you test his patch against that Issue #410 bug however, I
believe it will probably still crash, because they still are not catching
the exceptions thrown by their Triangulator code.

-DB

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

..and I got an answer with a bugfix from the CGAL guys :)

http://cgal-discuss.949826.n4.nabble.com/Multiple-volumes-Bug-converting-Nef-polyhedron-to-Polyhedron-3-tp4658599p4658600.html

A quick check shows that this fixes the issue, at least for this
particular model, although the patch might need some work to
retest/reintegrate with Don's nef3 workaround.

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

[kintel]

Yes, the #410 fix probably have to be applied to the new function as well. I didn't investigate that.

[donbright]

#718 from @andromodon

"difference()
{
cube(10);
translate([3,3,3]) cube(4);
}"

2.) Render as needed and export to an .stl file.

[OskarLinde]

The two commits above should resolve the two parts of this issue.

[kintel]

This was fixed by @OskarLinde

[nophead]

@OskarLinde https://github.com/OskarLinde don't forget to claim the
bounty.

On 10 June 2014 04:22, Marius Kintel notifications@github.com wrote:

Closed #495 #495.

Reply to this email directly or view it on GitHub
#495 (comment).