STL export and triangulation

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

STL export and triangulation

Owen Taylor
I had some trouble uploading a model built in OpenSCAD to Shapeways.
After some consultation with Shapeways support, the problem was
tracked down to zero-area faces being detected as self-intersections.

You can see some examples of problematical triangulation circled in:

 http://fishsoup.net/images/openscad-triangulation-t-vertices.png

(The simplified model shown there is attached to this email.) What you
see is the so-called T-vertex where it looks like one edge is meeting
at the middle of another edge, but really, there's a zero-width
triangle in between.

I looked into what was causing this, and in detail what's going on is
that during the Nef_polyhedron_3 to Polyhedron_3 conversion in the STL
export process, CGAL is picking bad triangulations of polygonal facets
- a tetrahedral face:

A---B----C
  \      /
     D

With A, B, C collinear is sometimes triangulated as:


A---B----C

A-------C
  \    /
    D

(ASCII art may not survive email.) After some dead-ends, I tried
making the following two line change to Nef_polyhedron.h in my CGAL
install:

--- Nef_polyhedron_3.h.bak      2010-08-25 19:48:12.512975219 -0400
+++ Nef_polyhedron_3.h  2010-08-25 19:51:17.497100940 -0400
@@ -67,7 +67,7 @@
 #include <CGAL/Nef_3/SNC_point_locator.h>
 #include <CGAL/assertions.h>

-#include <CGAL/Constrained_triangulation_2.h>
+#include <CGAL/Constrained_Delaunay_triangulation_2.h>
 #include <CGAL/Triangulation_data_structure_2.h>
 #include <CGAL/Triangulation_euclidean_traits_xy_3.h>
 #include <CGAL/Triangulation_euclidean_traits_yz_3.h>
@@ -583,7 +583,7 @@
    typedef typename CGAL::Triangulation_vertex_base_2<Kernel> Vb;
    typedef typename CGAL::Constrained_triangulation_face_base_2<Kernel>     Fb;
    typedef typename CGAL::Triangulation_data_structure_2<Vb,Fb>      TDS;
-    typedef typename CGAL::Constrained_triangulation_2<Kernel,TDS>      CT;
+   typedef typename
CGAL::Constrained_Delaunay_triangulation_2<Kernel,TDS>           CT;

   typedef typename CT::Face_handle           Face_handle;
   typedef typename CT::Vertex_handle         CTVertex_handle;

And got much better results after recompiling OpenSCAD - the
T-vertices were gone, and the resulting triangulation contained many
less pathologically skinny triangles. On more complex models, it
definitely looked like the result would be much easier to
hand-manipulate, if you wanted to do that. The results for the model
in the earlier screenshot can be seen in:

 http://fishsoup.net/images/openscad-triangulation-delaunay.png

(In terms of performance it seems slightly slower, but the export is
still many times faster than the CGAL rendering step.)

So I'm wondering:

 - Have other people hit this sort of problem?
 - How did you deal with it?
 - What are the possibilities for a real fix other than people hacking
up their CGAL sources? I thought of adding a post-process step on the
generated Polyhedron_3 which puts back together adjacent coplanar
triangles into the original planar facets and retriangulates them, but
that's just silly.

- Owen

t-vertices.scad (247 bytes) Download Attachment