Clifford Wolf:

	Tesselation magic: cgal 2d and 3d nefs have different constraints on
	the tesselation results



git-svn-id: http://svn.clifford.at/openscad/trunk@217 b57f626f-c46c-0410-a088-ec61d464b74c

7 files changed, 59 insertions, 56 deletions

diff --git a/dxflinextrude.cc b/dxflinextrude.cc
index 928bf5c..dc4ec9c 100644
--- a/dxflinextrude.cc
+++ b/dxflinextrude.cc
@@ -200,8 +200,8 @@ PolySet *DxfLinearExtrudeNode::render_polyset(render_mode_e) const
 
 	if (has_twist)
 	{
-		dxf_tesselate(ps, &dxf, 0, false, h1);
-		dxf_tesselate(ps, &dxf, twist, true, h2);
+		dxf_tesselate(ps, &dxf, 0, false, true, h1);
+		dxf_tesselate(ps, &dxf, twist, true, true, h2);
 		for (int j = 0; j < slices; j++)
 		{
 			double t1 = twist*j / slices;
@@ -218,8 +218,8 @@ PolySet *DxfLinearExtrudeNode::render_polyset(render_mode_e) const
 	}
 	else
 	{
-		dxf_tesselate(ps, &dxf, 0, false, h1);
-		dxf_tesselate(ps, &dxf, 0, true, h2);
+		dxf_tesselate(ps, &dxf, 0, false, true, h1);
+		dxf_tesselate(ps, &dxf, 0, true, true, h2);
 		for (int i = 0; i < dxf.paths.count(); i++)
 		{
 			if (!dxf.paths[i].is_closed)
diff --git a/dxftess.cc b/dxftess.cc
index bf89557..00a2f0e 100644
--- a/dxftess.cc
+++ b/dxftess.cc
@@ -161,7 +161,7 @@ static bool point_on_line(double *p1, double *p2, double *p3)
 	return true;
 }
 
-void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, double h)
+void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, bool do_triangle_splitting, double h)
 {
 	GLUtesselator *tobj = gluNewTess();
 
@@ -230,60 +230,63 @@ void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, double h)
 	// value are compared. This speeds up this code block dramatically (compared to the
 	// n^2 compares that are neccessary in the trivial implementation).
 #if 1
-	bool added_triangles = true;
-	typedef QPair<int,int> QPair_ii;
-	QHash<int, QPair_ii> tri_by_atan2;
-	for (int i = 0; i < tess_tri.count(); i++)
-	for (int j = 0; j < 3; j++) {
-		int ai = (int)round(atan2(fabs(tess_tri[i].p[(j+1)%3][0] - tess_tri[i].p[j][0]),
-				fabs(tess_tri[i].p[(j+1)%3][1] - tess_tri[i].p[j][1])) / 0.001);
-		tri_by_atan2.insertMulti(ai, QPair<int,int>(i, j));
-	}
-	while (added_triangles)
+	if (do_triangle_splitting)
 	{
-		added_triangles = false;
-#ifdef DEBUG_TRIANGLE_SPLITTING
-		printf("*** Triangle splitting (%d) ***\n", tess_tri.count()+1);
-#endif
+		bool added_triangles = true;
+		typedef QPair<int,int> QPair_ii;
+		QHash<int, QPair_ii> tri_by_atan2;
 		for (int i = 0; i < tess_tri.count(); i++)
-		for (int k = 0; k < 3; k++)
+		for (int j = 0; j < 3; j++) {
+			int ai = (int)round(atan2(fabs(tess_tri[i].p[(j+1)%3][0] - tess_tri[i].p[j][0]),
+					fabs(tess_tri[i].p[(j+1)%3][1] - tess_tri[i].p[j][1])) / 0.001);
+			tri_by_atan2.insertMulti(ai, QPair<int,int>(i, j));
+		}
+		while (added_triangles)
 		{
-			QHash<QPair_ii, QPair_ii> possible_neigh;
-			int ai = (int)floor(atan2(fabs(tess_tri[i].p[(k+1)%3][0] - tess_tri[i].p[k][0]),
-					fabs(tess_tri[i].p[(k+1)%3][1] - tess_tri[i].p[k][1])) / 0.001 - 0.5);
-			for (int j = 0; j < 2; j++) {
-				foreach (QPair_ii jl, tri_by_atan2.values(ai+j))
-					if (i != jl.first)
-						possible_neigh[jl] = jl;
-			}
+			added_triangles = false;
 #ifdef DEBUG_TRIANGLE_SPLITTING
-			printf("%d/%d: %d\n", i, k, possible_neigh.count());
+			printf("*** Triangle splitting (%d) ***\n", tess_tri.count()+1);
 #endif
-			foreach (QPair_ii jl, possible_neigh) {
-				int j = jl.first;
-				for (int l = jl.second; l != (jl.second + 2) % 3; l = (l + 1) % 3)
-				if (point_on_line(tess_tri[i].p[k], tess_tri[j].p[l], tess_tri[i].p[(k+1)%3])) {
+			for (int i = 0; i < tess_tri.count(); i++)
+			for (int k = 0; k < 3; k++)
+			{
+				QHash<QPair_ii, QPair_ii> possible_neigh;
+				int ai = (int)floor(atan2(fabs(tess_tri[i].p[(k+1)%3][0] - tess_tri[i].p[k][0]),
+						fabs(tess_tri[i].p[(k+1)%3][1] - tess_tri[i].p[k][1])) / 0.001 - 0.5);
+				for (int j = 0; j < 2; j++) {
+					foreach (QPair_ii jl, tri_by_atan2.values(ai+j))
+						if (i != jl.first)
+							possible_neigh[jl] = jl;
+				}
 #ifdef DEBUG_TRIANGLE_SPLITTING
-					printf("%% %f %f %f %f %f %f [%d %d]\n",
-							tess_tri[i].p[k][0], tess_tri[i].p[k][1],
-							tess_tri[j].p[l][0], tess_tri[j].p[l][1],
-							tess_tri[i].p[(k+1)%3][0], tess_tri[i].p[(k+1)%3][1],
-							i, j);
+				printf("%d/%d: %d\n", i, k, possible_neigh.count());
 #endif
-					tess_tri.append(tess_triangle(tess_tri[j].p[l],
-							tess_tri[i].p[(k+1)%3], tess_tri[i].p[(k+2)%3]));
-					for (int m = 0; m < 2; m++) {
-						int ai = (int)round(atan2(fabs(tess_tri.last().p[(m+1)%3][0] - tess_tri.last().p[m][0]),
-								fabs(tess_tri.last().p[(m+1)%3][1] - tess_tri.last().p[m][1])) / 0.001 );
-						tri_by_atan2.insertMulti(ai, QPair<int,int>(tess_tri.count()-1, m));
-					}
-					tess_tri[i].p[(k+1)%3] = tess_tri[j].p[l];
-					for (int m = 0; m < 2; m++) {
-						int ai = (int)round(atan2(fabs(tess_tri[i].p[(m+1)%3][0] - tess_tri[i].p[m][0]),
-								fabs(tess_tri[i].p[(m+1)%3][1] - tess_tri[i].p[m][1])) / 0.001 );
-						tri_by_atan2.insertMulti(ai, QPair<int,int>(i, m));
+				foreach (QPair_ii jl, possible_neigh) {
+					int j = jl.first;
+					for (int l = jl.second; l != (jl.second + 2) % 3; l = (l + 1) % 3)
+					if (point_on_line(tess_tri[i].p[k], tess_tri[j].p[l], tess_tri[i].p[(k+1)%3])) {
+#ifdef DEBUG_TRIANGLE_SPLITTING
+						printf("%% %f %f %f %f %f %f [%d %d]\n",
+								tess_tri[i].p[k][0], tess_tri[i].p[k][1],
+								tess_tri[j].p[l][0], tess_tri[j].p[l][1],
+								tess_tri[i].p[(k+1)%3][0], tess_tri[i].p[(k+1)%3][1],
+								i, j);
+#endif
+						tess_tri.append(tess_triangle(tess_tri[j].p[l],
+								tess_tri[i].p[(k+1)%3], tess_tri[i].p[(k+2)%3]));
+						for (int m = 0; m < 2; m++) {
+							int ai = (int)round(atan2(fabs(tess_tri.last().p[(m+1)%3][0] - tess_tri.last().p[m][0]),
+									fabs(tess_tri.last().p[(m+1)%3][1] - tess_tri.last().p[m][1])) / 0.001 );
+							tri_by_atan2.insertMulti(ai, QPair<int,int>(tess_tri.count()-1, m));
+						}
+						tess_tri[i].p[(k+1)%3] = tess_tri[j].p[l];
+						for (int m = 0; m < 2; m++) {
+							int ai = (int)round(atan2(fabs(tess_tri[i].p[(m+1)%3][0] - tess_tri[i].p[m][0]),
+									fabs(tess_tri[i].p[(m+1)%3][1] - tess_tri[i].p[m][1])) / 0.001 );
+							tri_by_atan2.insertMulti(ai, QPair<int,int>(i, m));
+						}
+						added_triangles = true;
 					}
-					added_triangles = true;
 				}
 			}
 		}
diff --git a/import.cc b/import.cc
index 2a407ad..3bdad66 100644
--- a/import.cc
+++ b/import.cc
@@ -180,7 +180,7 @@ PolySet *ImportNode::render_polyset(render_mode_e) const
 	{
 		DxfData dd(fn, fs, fa, filename, layername, origin_x, origin_y, scale);
 		p->is2d = true;
-		dxf_tesselate(p, &dd, 0, true, 0);
+		dxf_tesselate(p, &dd, 0, true, false, 0);
 		dxf_border_to_ps(p, &dd);
 	}
 
diff --git a/mainwin.cc b/mainwin.cc
index 5fcead0..c34cce9 100644
--- a/mainwin.cc
+++ b/mainwin.cc
@@ -1280,7 +1280,7 @@ static void renderGLviaCGAL(void *vp)
 			DxfData dd(*m->root_N);
 			m->cgal_ogl_ps = new PolySet();
 			m->cgal_ogl_ps->is2d = true;
-			dxf_tesselate(m->cgal_ogl_ps, &dd, 0, true, 0);
+			dxf_tesselate(m->cgal_ogl_ps, &dd, 0, true, false, 0);
 		}
 
 		glDisable(GL_LIGHTING);
diff --git a/openscad.h b/openscad.h
index 6350e08..e93b5db 100644
--- a/openscad.h
+++ b/openscad.h
@@ -687,7 +687,7 @@ extern void *progress_report_vp;
 void progress_report_prep(AbstractNode *root, void (*f)(const class AbstractNode *node, void *vp, int mark), void *vp);
 void progress_report_fin();
 
-void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, double h);
+void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, bool do_triangle_splitting, double h);
 void dxf_border_to_ps(PolySet *ps, DxfData *dxf);
 
 #endif /* INCLUDE_ABSTRACT_NODE_DETAILS */
diff --git a/render.cc b/render.cc
index 2f1e849..190bce5 100644
--- a/render.cc
+++ b/render.cc
@@ -172,7 +172,7 @@ CSGTerm *RenderNode::render_csg_term(double m[16], QVector<CSGTerm*> *highlights
 		DxfData dd(N);
 		ps = new PolySet();
 		ps->is2d = true;
-		dxf_tesselate(ps, &dd, 0, true, 0);
+		dxf_tesselate(ps, &dd, 0, true, false, 0);
 		dxf_border_to_ps(ps, &dd);
 	}
 
diff --git a/transform.cc b/transform.cc
index 27a3d66..f06e841 100644
--- a/transform.cc
+++ b/transform.cc
@@ -233,7 +233,7 @@ CGAL_Nef_polyhedron TransformNode::render_cgal_nef_polyhedron() const
 
 		PolySet ps;
 		ps.is2d = true;
-		dxf_tesselate(&ps, &dd, 0, true, 0);
+		dxf_tesselate(&ps, &dd, 0, true, false, 0);
 
 		N = ps.render_cgal_nef_polyhedron();
 		ps.refcount = 0;