Review and possibly clean up triangulation code

[donbright]

This issue is about reviewing and possibly cleaning up the different pieces of triangulation code we use in various places. Things are much cleaner now than when this was first raised, but a review is still needed, plus sync this with #793

Old text:

there should be different suface triangulation algorithms available when outputting STL.

per here:

http://forums.reprap.org/read.php?1,127368,164896#msg-164896

related to issue #337

(the code for 337 will directly make this much easier to accomplish)

---

Want to back this issue? Post a bounty on it! We accept bounties via Bountysource.

[vitalif]

Hi, I second this issue! :)

Current triangulation method (displayed on the left) often makes degenerate triangles... And I think the method itself is rather strange, yeah. Does it have some well-known name? Does it have any advantages over the second method?

And do you have some work-in-progress patch for this issue somewhere? Maybe I can test it?

[donbright]

there is a very small patch (2 lines?) you can make to src/CGAL_Nef3_workaround.h that will use a Constrained Delaunay Triangulation on STL output. someone (I forget their name, sorry.. its in the issues or mailing list archive somewhere) has tested it quite a bit but it hasn't made it to any branch that i can remember.

[vitalif]

Thanks, I assume you were talking about http://rocklinux.net/pipermail/openscad/2010-August/000572.html ? (btw, did someone answer that man ? I don't see any replies there... :)))

Now it's possible to do that without patching CGAL, see commit vitalif/openscad@f1cf6cb
It generates good triangulation. + also I've enabled it for OFF export.

What I want to ask is - does current triangulation method offer any advantages over Delaunay? If not - maybe just replace it totally?

[donbright]

2010, i did not know about that discussion! ... there was a discussion last year in 2013 that is basically the same. . . .

the introduction of the 'workaround' code is what allows this to exist without having to patch CGAL.. as you have shown!!

the current method of triangulation is whatever CGAL uses internally, i'm not sure of the name or if it's even documented. i assume its some kind of ear-clipping which, in theory, would be faster than Delaunay Triangulation because there is no 'refinement' step. (for readers who may not know, Ear Clipping triangulation of a polygon is really simple, as most algorithms go, you can google around and find some pseudo code that is only a few lines).

the disadvantage of switching is that we dont know if the CGAL delaunay is as stable as we would like, or if the slowdown is an issue. someone did a lot of testing and it seemed to be OK,.. (of course i cant find the link right now... i know someone did try the examples and they seemed to work)

maybe Marius would agree to enable this as the default triangulation in the 'unstable' branch. (I would like for us to at least try it...)

[vitalif]

:-) ok, please test it. I've already built some models with it, it seems to work good, and I didn't notice any slowdown.

[vitalif]

Hi again, did you try it?

[donbright]

not yet. how does it do on ctest -C All (doc/testing.txt) ?

[vitalif]

I've just ran the tests...

The following tests FAILED:
239 - cgalpngtest_issue495b (Failed)
243 - cgalpngtest_issue582 (Failed)
245 - cgalpngtest_issue585 (Failed)
246 - cgalpngtest_issue591 (Failed)
247 - cgalpngtest_issue593 (Failed)
248 - cgalpngtest_issue112 (Failed)
366 - opencsgtest_issue495 (Failed)
368 - opencsgtest_issue541 (Failed)
369 - opencsgtest_issue578 (Failed)
370 - opencsgtest_issue578b (Failed)
372 - opencsgtest_issue584 (Failed)
375 - opencsgtest_issue593 (Failed)
376 - opencsgtest_issue112 (Failed)
377 - opencsgtest_issue666 (Failed)
430 - throwntogethertest_polygon-tests (Failed)

[vitalif]

Oh, sorry. They fail anyway with the version I've tested, even without the delaunay patch :). So it doesn't affect the test output...
After pulling from master, rebuilding and re-running the tests - again, no difference between delaunay and non-delaunay, but some tests still fail:
192 - cgalpngtest_linear_extrude-scale-zero-tests (Failed)
260 - cgalpngtest_issue495b (Failed)
266 - cgalpngtest_issue591 (Failed)
268 - cgalpngtest_issue112 (Failed)
396 - opencsgtest_issue495 (Failed)
401 - opencsgtest_issue584 (Failed)
406 - opencsgtest_issue666 (Failed)

[kintel]

The issue tests are supposed to fail as they're related to open issues.

[vitalif]

ok, very good! :)
so does delaunay look OK to you?

[kintel]

I'll take a look at it soon

[t-paul]

I tried one of the patches to enable delaunay triangulation. It did produce nicer meshes but I still got quite a number of zero and intersecting faces flagged in the blender toolbox when exporting to STL. I did not collect performance data about that, but it seemed to have not much impact with the mildly complicated models I tried.

[vitalif]

And on which models did you test it? You say you've got some bad faces - so are they complex?

[t-paul]

Not sure, that was quite some time ago. I do think we should try out the delaunay triangulation, I just wanted to point out that we might still need some kind of mesh cleaning or STL export improvements as delaunay probably will not solve all the issues.

[kintel]

Does anyone have good examples to test with? The design causing the triangulation in the initial screenshot would also be nice to have.

[kintel]

I've put the patch in a separate branch for now: https://github.com/openscad/openscad/tree/issue414

[vitalif]

Does it enable delaunay for both STL and OFF export?
Because when I've tried it I discovered that another small fix is needed to enable it for both... Like in vitalif/openscad@5c55f05

[kintel]

I just applied the patch I found. We should probably refactor this a bit. Good triangulations might be needed in other places where we convert from Nef polyhedrons to something else.

[kintel]

I just realized that we have some other code lying around which should be looked at:
https://github.com/openscad/openscad/blob/master/src/export.cc#L234

[kintel]

also, to be able to test this properly, we should probably start looking at export testing (#622).

[MichaelAtOz]

The design causing the triangulation in the initial screenshot would also be nice to have.

Not sure if it is the same one but the smallgearmod_fixed_1.stl at Greg's Wade extruder for Prusa i3 look like it.

[MichaelAtOz]

Good new & bad news. Traced it back. But exported STL (with 2014.03) does not have the odd facets on the base. I'm presuming 'fixed' may have caused it???

Herringbone design Wades_Gears_helix.scad from Wade goes Fishing

Needs parametric_involute_gear_v5.0.scad from Parametric Involute Bevel and Spur Gears

Generates a few WARNING: Duplicate vertices and/or intersecting lines found during DXF Tessellation

[MichaelAtOz]

Model with odd facets seems to have come from Greg's Wade reloaded - Guidler, Tilt Screws, Fishbone Gears

In the comments "Hi, actually I only modified the STLs from Stoffel15's Extruder" (which is the Wade goes fishing above). Then in relation to the gears, "Not a real source file as you would expect, I just hacked Stoffel15's STL files via import(); in OpenSCAD". And "I modified the STLs via STL-import with OpenSCAD for better fit of the nut slot etc".

I couldn't see any scad code for that. So I suggest the 'fixed' may have done it.

[kintel]

@MichaelAtOz Thanks for hunting! I've tried to ping the original poster about this.

[kintel]

This need a bit more work. Triangulated geometry is being calculated in 4 different places:

• Geometry originating from 2D (e.g. linear_extrude of complex 2D polygons): We do delaunay tessellation in 2D and create Polysets and Nef polyhedrons from there. The input polygons can have holes.
• PolySets originating from OpenSCAD polyhedron() nodes: We do delaunay tessellation of the incoming polygons (can be concave but not have holes)
• Conversion from Nef polyhedrons for export: We tessellate using the nefworkaround component (the origins of this issue)
• Conversion from Nef polyhedrons for rendering: We use the code in OGL_helper from CGAL, which uses the GLU tessellator for handling concavities and holes.

I'll look into if we can collect some of these into more well-defined utilities.

[donbright]

I think I might be able to provide some more detail on that list and add one.

• Geometry from 2d - not too familiar with this, except that it's maybe using Agnus Johnson's Clipper to process holes, self intersection, dup verts, dup edges, etc, which converts all input to Integer coordinates during processing.. the size of the integer dependent on the machine. Output is converted from integer to whatever is desired (i assume binary-floating-point).

• PolySets from OpenSCAD polyhedron() -- input is ASCII Decimal, and assumes the user has input a simple polygon, no holes, no self intersects, no dup points, etc. Data is converted to floating-point-binary to make the PolySet, but not triangulated until Preview or Render time. Oskar Linde has a patch that will do the triangulation at polyhedron->PolySet creation time as an alternative Rendering error with concave polyhedron faces  #793.
  ** For F6 rendering currently the triangulator calls CGAL's Constrained Delaunay Triangulation using Exact Predicate Inexact Constructions Kernel (Filtered kernel using binary-floating-point). Output is binary-floating-point PolySet.... with no actualy point data changed, just edges added to the data structure to form new triangle faces. The major assumption here is that the input is Near Planar, and the user has constructed a valid and simple polyhedron() input, not self intersecting, no holes, no dup points, etc etc.
  ** For Preview rendering currently the polygons are drawn in polyset.cc which only works on convex polygons (see OpenGL triangulations below). see Rendering error with concave polyhedron faces  #793

• Conversion from Nef polyhedrons for export: (There is actually two things here. Input is whatever Nef Kernel is set to, currently CGAL GMP Rationals)
  ** NefPolyhedron conversion to CGAL Polyhedron. (Cgal's Default Nef->Polyhedron converter, using it's 'default' triangulation, which produces some thin polygons, ex. a cylinder's circle face is split like a fan). This triangulation is currently done in NefWorkaround.h which is simply a copy from CGAL's code, with a few catch() inserted for uncaught exceptions. (Recall, CGAL fails to properly catch exceptions thrown by its default triangulator, which is the whole reason for nef workaround in the first place. NefWorkaround basically catches those exceptions and keeps it from crashing). With two lines of code change, NefWorkaround can use Delaunay triangulation instead of the 'default' triangulation. Output is a CGAL Polyhedron (IIRC this is also using CGAL GMP Rationals), which then gets downconverted to ASCII Decimal for STL output (and some bad triangles are removed during this downconversion).

  ** NefPolyhedron direct to PolySet for STL: Code I wrote that was interrupted by the 527 thing. My code was originally designed as a 'fall back' when CGALs default NEF->Polyhedron failed due to non-Manifold problems. This code has to deal with multiple holes, limited self intersections, and some other kinds of trash that Nef Polyhedron faces sometimes contain. It uses a special form of CGAL's Delaunay triangulator that can handle these situations without barfing. Triangulation processing is done in CGAL Nef Kernel, currently CGAL GMP Rationals. Output is converted to binary-floating-point PolySet (IIRC)... which is then sent to STL ASCII Decimal.

• OpenGL triangulators:
  ** Preview renderers for ThrownTogether / OpenCSG, in polyset.cc, for OpenGL drawing of polygons... this triangulation currently only works properly for Convex polygons (see Oskar Linde's Rendering error with concave polyhedron faces  #793 recent patch for more discussion). Input is 3d binary-floating-point and output is OpenGL commands.
  ** NefPolyhedron->OpenGL -> As noted this is in OGL_Helper. Input is NefKernel (CGAL GMP Rationals), downconverted to binary-floating-point, output is OpenGL commands.

(updated to be more accurate in a few places, clarify Clipper, link to Oskar's patch/bug report)

---

note for future self.

the Boost library has a very new Voroni tessellation diagram generator that uses Integer arithmetic. It is apparently, according to the authors, quite fast.

The reader may be aware that Voroni tessellation is the 'dual' of the Delaunay triangulation. In other words, it is not 'rocket science' to convert a Voroni Tessellation to a Delaunay Triangulation.