Clifford Wolf:

	Added Grid2d/Grid3d API
	Moved dxf tesselation to extra file



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

6 files changed, 356 insertions, 234 deletions

diff --git a/dxflinextrude.cc b/dxflinextrude.cc
index 0fa285c..76261cb 100644
--- a/dxflinextrude.cc
+++ b/dxflinextrude.cc
@@ -125,216 +125,6 @@ static void add_slice(PolySet *ps, DxfData::Path *pt, double h1, double h2)
 	}
 }
 
-struct tess_vdata {
-	GLdouble v[3];
-};
-
-struct tess_triangle {
-	GLdouble *p[3];
-	tess_triangle() { p[0] = NULL; p[1] = NULL; p[2] = NULL; }
-	tess_triangle(double *p1, double *p2, double *p3) { p[0] = p1; p[1] = p2; p[2] = p3; }
-};
-
-static GLenum tess_type;
-static int tess_count;
-static QVector<tess_triangle> tess_tri;
-static GLdouble *tess_p1, *tess_p2;
-
-static void tess_vertex(void *vertex_data)
-{
-	GLdouble *p = (double*)vertex_data;
-#if 0
-	printf("  %d: %f %f %f\n", tess_count, p[0], p[1], p[2]);
-#endif
-	if (tess_type == GL_TRIANGLE_FAN) {
-		if (tess_count == 0) {
-			tess_p1 = p;
-		}
-		if (tess_count == 1) {
-			tess_p2 = p;
-		}
-		if (tess_count > 1) {
-			tess_tri.append(tess_triangle(tess_p1, tess_p2, p));
-			tess_p2 = p;
-		}
-	}
-	if (tess_type == GL_TRIANGLE_STRIP) {
-		if (tess_count == 0) {
-			tess_p1 = p;
-		}
-		if (tess_count == 1) {
-			tess_p2 = p;
-		}
-		if (tess_count > 1) {
-			if (tess_count % 2 == 1) {
-				tess_tri.append(tess_triangle(tess_p2, tess_p1, p));
-			} else {
-				tess_tri.append(tess_triangle(tess_p1, tess_p2, p));
-			}
-			tess_p1 = tess_p2;
-			tess_p2 = p;
-		}
-	}
-	if (tess_type == GL_TRIANGLES) {
-		if (tess_count == 0) {
-			tess_p1 = p;
-		}
-		if (tess_count == 1) {
-			tess_p2 = p;
-		}
-		if (tess_count == 2) {
-			tess_tri.append(tess_triangle(tess_p1, tess_p2, p));
-			tess_count = -1;
-		}
-	}
-	tess_count++;
-}
-
-static void tess_begin(GLenum type)
-{
-#if 0
-	if (type == GL_TRIANGLE_FAN) {
-		printf("GL_TRIANGLE_FAN:\n");
-	}
-	if (type == GL_TRIANGLE_STRIP) {
-		printf("GL_TRIANGLE_STRIP:\n");
-	}
-	if (type == GL_TRIANGLES) {
-		printf("GL_TRIANGLES:\n");
-	}
-#endif
-	tess_count = 0;
-	tess_type = type;
-}
-
-static void tess_end(void)
-{
-	/* nothing to be done here */
-}
-
-static void tess_error(GLenum errno)
-{
-	PRINTF("GLU tesselation error %d!", errno);
-}
-
-static bool point_on_line(double *p1, double *p2, double *p3)
-{
-	if (fabs(p1[0] - p2[0]) < 0.0001 && fabs(p1[1] - p2[1]) < 0.0001)
-		return false;
-
-	if (fabs(p3[0] - p2[0]) < 0.0001 && fabs(p3[1] - p2[1]) < 0.0001)
-		return false;
-
-	double v1[2] = { p2[0] - p1[0], p2[1] - p1[1] };
-	double v2[2] = { p3[0] - p1[0], p3[1] - p1[1] };
-
-	if (fabs(atan2(v1[0], v1[1]) - atan2(v2[0], v2[1])) < 0.0001 &&
-			sqrt(v1[0]*v1[0] + v1[1]*v1[1]) < sqrt(v2[0]*v2[0] + v2[1]*v2[1])) {
-#if 0
-		printf("Point on line: %f/%f %f/%f %f/%f\n", p1[0], p1[1], p2[0], p2[1], p3[0], p3[1]);
-#endif
-		return true;
-	}
-
-	return false;
-}
-
-static void tess(PolySet *ps, DxfData *dxf, bool up, double h)
-{
-	GLUtesselator *tobj = gluNewTess();
-
-	gluTessCallback(tobj, GLU_TESS_VERTEX, (GLvoid(*)())&tess_vertex);
-	gluTessCallback(tobj, GLU_TESS_BEGIN, (GLvoid(*)())&tess_begin);
-	gluTessCallback(tobj, GLU_TESS_END, (GLvoid(*)())&tess_end);
-	gluTessCallback(tobj, GLU_TESS_ERROR, (GLvoid(*)())&tess_error);
-
-	tess_tri.clear();
-	QList<tess_vdata> vl;
-
-	gluTessBeginPolygon(tobj, NULL);
-
-	for (int i = 0; i < dxf->paths.count(); i++) {
-		if (!dxf->paths[i].is_closed)
-			continue;
-		gluTessBeginContour(tobj);
-		if (up != dxf->paths[i].is_inner) {
-			for (int j = 1; j < dxf->paths[i].points.count(); j++) {
-				vl.append(tess_vdata());
-				vl.last().v[0] = dxf->paths[i].points[j]->x;
-				vl.last().v[1] = dxf->paths[i].points[j]->y;
-				vl.last().v[2] = h;
-				gluTessVertex(tobj, vl.last().v, vl.last().v);
-			}
-		} else {
-			for (int j = dxf->paths[i].points.count() - 1; j > 0; j--) {
-				vl.append(tess_vdata());
-				vl.last().v[0] = dxf->paths[i].points[j]->x;
-				vl.last().v[1] = dxf->paths[i].points[j]->y;
-				vl.last().v[2] = h;
-				gluTessVertex(tobj, vl.last().v, vl.last().v);
-			}
-		}
-		gluTessEndContour(tobj);
-	}
-
-	gluTessEndPolygon(tobj);
-	gluDeleteTess(tobj);
-
-#if 0
-	for (int i = 0; i < tess_tri.count(); i++) {
-		printf("~~~\n");
-		printf("  %f %f %f\n", tess_tri[i].p[0][0], tess_tri[i].p[0][1], tess_tri[i].p[0][2]);
-		printf("  %f %f %f\n", tess_tri[i].p[1][0], tess_tri[i].p[1][1], tess_tri[i].p[1][2]);
-		printf("  %f %f %f\n", tess_tri[i].p[2][0], tess_tri[i].p[2][1], tess_tri[i].p[2][2]);
-	}
-#endif
-
-	// GLU tessing sometimes generates degenerated triangles. We must find and remove
-	// them so we can use the triangle array with CGAL..
-	for (int i = 0; i < tess_tri.count(); i++) {
-		if (point_on_line(tess_tri[i].p[0], tess_tri[i].p[1], tess_tri[i].p[2]) ||
-				point_on_line(tess_tri[i].p[1], tess_tri[i].p[2], tess_tri[i].p[0]) ||
-				point_on_line(tess_tri[i].p[2], tess_tri[i].p[0], tess_tri[i].p[1])) {
-			tess_tri.remove(i--);
-		}
-	}
-
-	// GLU tessing might merge points into edges. This is ok for GL displaying but
-	// creates invalid polyeders for CGAL. So we split this tirangles up again in order
-	// to create polyeders that are also accepted by CGAL..
-	bool added_triangles = true;
-	while (added_triangles)
-	{
-		added_triangles = false;
-		for (int i = 0; i < tess_tri.count(); i++)
-		for (int j = 0; j < tess_tri.count(); j++)
-		for (int k = 0; k < 3; k++)
-		for (int l = 0; l < 3; l++) {
-			if (point_on_line(tess_tri[i].p[k], tess_tri[j].p[l], tess_tri[i].p[(k+1)%3])) {
-				tess_tri.append(tess_triangle(tess_tri[j].p[l],
-						tess_tri[i].p[(k+1)%3], tess_tri[i].p[(k+2)%3]));
-				tess_tri[i].p[(k+1)%3] = tess_tri[j].p[l];
-				added_triangles = true;
-			}
-		}
-	}
-
-	for (int i = 0; i < tess_tri.count(); i++) {
-#if 0
-		printf("---\n");
-		printf("  %f %f %f\n", tess_tri[i].p[0][0], tess_tri[i].p[0][1], tess_tri[i].p[0][2]);
-		printf("  %f %f %f\n", tess_tri[i].p[1][0], tess_tri[i].p[1][1], tess_tri[i].p[1][2]);
-		printf("  %f %f %f\n", tess_tri[i].p[2][0], tess_tri[i].p[2][1], tess_tri[i].p[2][2]);
-#endif
-		ps->append_poly();
-		ps->insert_vertex(tess_tri[i].p[0][0], tess_tri[i].p[0][1], tess_tri[i].p[0][2]);
-		ps->insert_vertex(tess_tri[i].p[1][0], tess_tri[i].p[1][1], tess_tri[i].p[1][2]);
-		ps->insert_vertex(tess_tri[i].p[2][0], tess_tri[i].p[2][1], tess_tri[i].p[2][2]);
-	}
-
-	tess_tri.clear();
-}
-
 PolySet *DxfLinearExtrudeNode::render_polyset(render_mode_e) const
 {
 	DxfData dxf(fn, fs, fa, filename, layername, origin_x, origin_y, scale);
@@ -359,8 +149,8 @@ PolySet *DxfLinearExtrudeNode::render_polyset(render_mode_e) const
 		add_slice(ps, &dxf.paths[i], h1, h2);
 	}
 
-	tess(ps, &dxf, false, h1);
-	tess(ps, &dxf, true, h2);
+	dxf_tesselate(ps, &dxf, false, h1);
+	dxf_tesselate(ps, &dxf, true, h2);
 
 	return ps;
 }
diff --git a/dxftess.cc b/dxftess.cc
new file mode 100644
index 0000000..e62789f
--- /dev/null
+++ b/dxftess.cc
@@ -0,0 +1,234 @@
+/*
+ *  OpenSCAD (www.openscad.at)
+ *  Copyright (C) 2009  Clifford Wolf <clifford@clifford.at>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ */
+
+#define INCLUDE_ABSTRACT_NODE_DETAILS
+
+#include "openscad.h"
+
+struct tess_vdata {
+	GLdouble v[3];
+};
+
+struct tess_triangle {
+	GLdouble *p[3];
+	tess_triangle() { p[0] = NULL; p[1] = NULL; p[2] = NULL; }
+	tess_triangle(double *p1, double *p2, double *p3) { p[0] = p1; p[1] = p2; p[2] = p3; }
+};
+
+static GLenum tess_type;
+static int tess_count;
+static QVector<tess_triangle> tess_tri;
+static GLdouble *tess_p1, *tess_p2;
+
+static void tess_vertex(void *vertex_data)
+{
+	GLdouble *p = (double*)vertex_data;
+#if 0
+	printf("  %d: %f %f %f\n", tess_count, p[0], p[1], p[2]);
+#endif
+	if (tess_type == GL_TRIANGLE_FAN) {
+		if (tess_count == 0) {
+			tess_p1 = p;
+		}
+		if (tess_count == 1) {
+			tess_p2 = p;
+		}
+		if (tess_count > 1) {
+			tess_tri.append(tess_triangle(tess_p1, tess_p2, p));
+			tess_p2 = p;
+		}
+	}
+	if (tess_type == GL_TRIANGLE_STRIP) {
+		if (tess_count == 0) {
+			tess_p1 = p;
+		}
+		if (tess_count == 1) {
+			tess_p2 = p;
+		}
+		if (tess_count > 1) {
+			if (tess_count % 2 == 1) {
+				tess_tri.append(tess_triangle(tess_p2, tess_p1, p));
+			} else {
+				tess_tri.append(tess_triangle(tess_p1, tess_p2, p));
+			}
+			tess_p1 = tess_p2;
+			tess_p2 = p;
+		}
+	}
+	if (tess_type == GL_TRIANGLES) {
+		if (tess_count == 0) {
+			tess_p1 = p;
+		}
+		if (tess_count == 1) {
+			tess_p2 = p;
+		}
+		if (tess_count == 2) {
+			tess_tri.append(tess_triangle(tess_p1, tess_p2, p));
+			tess_count = -1;
+		}
+	}
+	tess_count++;
+}
+
+static void tess_begin(GLenum type)
+{
+#if 0
+	if (type == GL_TRIANGLE_FAN) {
+		printf("GL_TRIANGLE_FAN:\n");
+	}
+	if (type == GL_TRIANGLE_STRIP) {
+		printf("GL_TRIANGLE_STRIP:\n");
+	}
+	if (type == GL_TRIANGLES) {
+		printf("GL_TRIANGLES:\n");
+	}
+#endif
+	tess_count = 0;
+	tess_type = type;
+}
+
+static void tess_end(void)
+{
+	/* nothing to be done here */
+}
+
+static void tess_error(GLenum errno)
+{
+	PRINTF("GLU tesselation error %d!", errno);
+}
+
+static bool point_on_line(double *p1, double *p2, double *p3)
+{
+	if (fabs(p1[0] - p2[0]) < 0.0001 && fabs(p1[1] - p2[1]) < 0.0001)
+		return false;
+
+	if (fabs(p3[0] - p2[0]) < 0.0001 && fabs(p3[1] - p2[1]) < 0.0001)
+		return false;
+
+	double v1[2] = { p2[0] - p1[0], p2[1] - p1[1] };
+	double v2[2] = { p3[0] - p1[0], p3[1] - p1[1] };
+
+	if (fabs(atan2(v1[0], v1[1]) - atan2(v2[0], v2[1])) < 0.0001 &&
+			sqrt(v1[0]*v1[0] + v1[1]*v1[1]) < sqrt(v2[0]*v2[0] + v2[1]*v2[1])) {
+#if 0
+		printf("Point on line: %f/%f %f/%f %f/%f\n", p1[0], p1[1], p2[0], p2[1], p3[0], p3[1]);
+#endif
+		return true;
+	}
+
+	return false;
+}
+
+void dxf_tesselate(PolySet *ps, DxfData *dxf, bool up, double h)
+{
+	GLUtesselator *tobj = gluNewTess();
+
+	gluTessCallback(tobj, GLU_TESS_VERTEX, (GLvoid(*)())&tess_vertex);
+	gluTessCallback(tobj, GLU_TESS_BEGIN, (GLvoid(*)())&tess_begin);
+	gluTessCallback(tobj, GLU_TESS_END, (GLvoid(*)())&tess_end);
+	gluTessCallback(tobj, GLU_TESS_ERROR, (GLvoid(*)())&tess_error);
+
+	tess_tri.clear();
+	QList<tess_vdata> vl;
+
+	gluTessBeginPolygon(tobj, NULL);
+
+	for (int i = 0; i < dxf->paths.count(); i++) {
+		if (!dxf->paths[i].is_closed)
+			continue;
+		gluTessBeginContour(tobj);
+		if (up != dxf->paths[i].is_inner) {
+			for (int j = 1; j < dxf->paths[i].points.count(); j++) {
+				vl.append(tess_vdata());
+				vl.last().v[0] = dxf->paths[i].points[j]->x;
+				vl.last().v[1] = dxf->paths[i].points[j]->y;
+				vl.last().v[2] = h;
+				gluTessVertex(tobj, vl.last().v, vl.last().v);
+			}
+		} else {
+			for (int j = dxf->paths[i].points.count() - 1; j > 0; j--) {
+				vl.append(tess_vdata());
+				vl.last().v[0] = dxf->paths[i].points[j]->x;
+				vl.last().v[1] = dxf->paths[i].points[j]->y;
+				vl.last().v[2] = h;
+				gluTessVertex(tobj, vl.last().v, vl.last().v);
+			}
+		}
+		gluTessEndContour(tobj);
+	}
+
+	gluTessEndPolygon(tobj);
+	gluDeleteTess(tobj);
+
+#if 0
+	for (int i = 0; i < tess_tri.count(); i++) {
+		printf("~~~\n");
+		printf("  %f %f %f\n", tess_tri[i].p[0][0], tess_tri[i].p[0][1], tess_tri[i].p[0][2]);
+		printf("  %f %f %f\n", tess_tri[i].p[1][0], tess_tri[i].p[1][1], tess_tri[i].p[1][2]);
+		printf("  %f %f %f\n", tess_tri[i].p[2][0], tess_tri[i].p[2][1], tess_tri[i].p[2][2]);
+	}
+#endif
+
+	// GLU tessing sometimes generates degenerated triangles. We must find and remove
+	// them so we can use the triangle array with CGAL..
+	for (int i = 0; i < tess_tri.count(); i++) {
+		if (point_on_line(tess_tri[i].p[0], tess_tri[i].p[1], tess_tri[i].p[2]) ||
+				point_on_line(tess_tri[i].p[1], tess_tri[i].p[2], tess_tri[i].p[0]) ||
+				point_on_line(tess_tri[i].p[2], tess_tri[i].p[0], tess_tri[i].p[1])) {
+			tess_tri.remove(i--);
+		}
+	}
+
+	// GLU tessing might merge points into edges. This is ok for GL displaying but
+	// creates invalid polyeders for CGAL. So we split this tirangles up again in order
+	// to create polyeders that are also accepted by CGAL..
+	bool added_triangles = true;
+	while (added_triangles)
+	{
+		added_triangles = false;
+		for (int i = 0; i < tess_tri.count(); i++)
+		for (int j = 0; j < tess_tri.count(); j++)
+		for (int k = 0; k < 3; k++)
+		for (int l = 0; l < 3; l++) {
+			if (point_on_line(tess_tri[i].p[k], tess_tri[j].p[l], tess_tri[i].p[(k+1)%3])) {
+				tess_tri.append(tess_triangle(tess_tri[j].p[l],
+						tess_tri[i].p[(k+1)%3], tess_tri[i].p[(k+2)%3]));
+				tess_tri[i].p[(k+1)%3] = tess_tri[j].p[l];
+				added_triangles = true;
+			}
+		}
+	}
+
+	for (int i = 0; i < tess_tri.count(); i++) {
+#if 0
+		printf("---\n");
+		printf("  %f %f %f\n", tess_tri[i].p[0][0], tess_tri[i].p[0][1], tess_tri[i].p[0][2]);
+		printf("  %f %f %f\n", tess_tri[i].p[1][0], tess_tri[i].p[1][1], tess_tri[i].p[1][2]);
+		printf("  %f %f %f\n", tess_tri[i].p[2][0], tess_tri[i].p[2][1], tess_tri[i].p[2][2]);
+#endif
+		ps->append_poly();
+		ps->insert_vertex(tess_tri[i].p[0][0], tess_tri[i].p[0][1], tess_tri[i].p[0][2]);
+		ps->insert_vertex(tess_tri[i].p[1][0], tess_tri[i].p[1][1], tess_tri[i].p[1][2]);
+		ps->insert_vertex(tess_tri[i].p[2][0], tess_tri[i].p[2][1], tess_tri[i].p[2][2]);
+	}
+
+	tess_tri.clear();
+}
+
diff --git a/examples/example007.scad b/examples/example007.scad
index efab3bd..19415bf 100644
--- a/examples/example007.scad
+++ b/examples/example007.scad
@@ -63,4 +63,8 @@ module cutview()
 	}
 }
 
-cutview();
+translate([0 0 -10])
+	clip();
+
+// cutview();
+
diff --git a/openscad.h b/openscad.h
index 9676947..7eae41f 100644
--- a/openscad.h
+++ b/openscad.h
@@ -21,16 +21,6 @@
 #ifndef OPENSCAD_H
 #define OPENSCAD_H
 
-// this must be defined as early as possible
-// so QHash<> and friends can see it..
-#include <qglobal.h>
-static inline uint qHash(double v) {
-	// not beauty but good enough..
-	union { double d; uint u[2]; } x;
-	x.u[0] = 0; x.u[1] = 0; x.d = v;
-	return x.u[0] ^ x.u[1];
-}
-
 #ifdef ENABLE_OPENCSG
 // this must be included before the GL headers
 #  include <GL/glew.h>
@@ -72,6 +62,110 @@ class CSGChain;
 class AbstractNode;
 class AbstractPolyNode;
 
+template <typename T>
+class Grid2d
+{
+public:
+	double res;
+	QHash<QPair<int,int>, T> db;
+
+	Grid2d(double resolution = 0.001) {
+		res = resolution;
+	}
+	T &align(double &x, double &y) {
+		int ix = round(x / res);
+		int iy = round(y / res);
+		x = ix * res, y = iy * res;
+		if (db.contains(QPair<int,int>(ix, iy)))
+			return db[QPair<int,int>(ix, iy)];
+		int dist = 10;
+		T *ptr = NULL;
+		for (int jx = ix - 1; jx <= ix + 1; jx++)
+		for (int jy = iy - 1; jy <= iy + 1; jy++) {
+			if (!db.contains(QPair<int,int>(jx, jy)))
+				continue;
+			if (abs(ix-jx) + abs(iy-jy) < dist) {
+				x = jx * res, y = jy * res;
+				dist = abs(ix-jx) + abs(iy-jy);
+				ptr = &db[QPair<int,int>(jx, jy)];
+			}
+		}
+		if (ptr)
+			return *ptr;
+		return db[QPair<int,int>(ix, iy)];
+	}
+	bool has(double x, double y) {
+		int ix = round(x / res);
+		int iy = round(y / res);
+		if (db.contains(QPair<int,int>(ix, iy)))
+			return true;
+		for (int jx = ix - 1; jx <= ix + 1; jx++)
+		for (int jy = iy - 1; jy <= iy + 1; jy++) {
+			if (db.contains(QPair<int,int>(jx, jy)))
+				true;
+		}
+		return false;
+	}
+	T &data(double x, double y) {
+		return align(x, y);
+	}
+};
+
+template <typename T>
+class Grid3d
+{
+public:
+	double res;
+	QHash<QPair<QPair<int,int>,int>, T> db;
+
+	Grid3d(double resolution = 0.001) {
+		res = resolution;
+	}
+	T &align(double &x, double &y, double &z) {
+		int ix = round(x / res);
+		int iy = round(y / res);
+		int iz = round(z / res);
+		x = ix * res, y = iy * res, z = iz * res;
+		if (db.contains(QPair<QPair<int,int>,int>(QPair<int,int>(ix, iy), iz)))
+			return db[QPair<QPair<int,int>,int>(QPair<int,int>(ix, iy), iz)];
+		int dist = 10;
+		T *ptr = NULL;
+		for (int jx = ix - 1; jx <= ix + 1; jx++)
+		for (int jy = iy - 1; jy <= iy + 1; jy++)
+		for (int jz = iz - 1; jz <= iz + 1; jz++) {
+			if (!db.contains(QPair<QPair<int,int>,int>(QPair<int,int>(jx, jy), jz)))
+				continue;
+			if (abs(ix-jx) + abs(iy-jy) + abs(iz-jz) < dist) {
+				x = jx * res, y = jy * res, z = jz * res;
+				dist = abs(ix-jx) + abs(iy-jy) + abs(iz-jz);
+				ptr = &db[QPair<QPair<int,int>,int>(QPair<int,int>(jx, jy), jz)];
+			}
+		}
+		if (ptr)
+			return *ptr;
+		return db[QPair<QPair<int,int>,int>(QPair<int,int>(ix, iy), iz)];
+		
+	}
+	bool has(double x, double y, double z) {
+		int ix = round(x / res);
+		int iy = round(y / res);
+		int iz = round(z / res);
+		if (db.contains(QPair<QPair<int,int>,int>(QPair<int,int>(ix, iy), iz)))
+			return true;
+		for (int jx = ix - 1; jx <= ix + 1; jx++)
+		for (int jy = iy - 1; jy <= iy + 1; jy++)
+		for (int jz = iz - 1; jz <= iz + 1; jz++) {
+			if (db.contains(QPair<QPair<int,int>,int>(QPair<int,int>(jx, jy), jz)))
+				return true;
+		}
+		return false;
+		
+	}
+	T &data(double x, double y, double z) {
+		return align(x, y, z);
+	}
+};
+
 class Value
 {
 public:
@@ -356,6 +450,7 @@ public:
 	};
 	typedef QList<Point> Polygon;
 	QVector<Polygon> polygons;
+	Grid3d<void*> grid;
 	double m[16];
 	int convexity;
 
@@ -471,6 +566,8 @@ 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, bool up, double h);
+
 #else
 
 // Needed for Mainwin::root_N
diff --git a/openscad.pro b/openscad.pro
index 2e7d8f1..cb162d5 100644
--- a/openscad.pro
+++ b/openscad.pro
@@ -16,7 +16,7 @@ SOURCES += openscad.cc mainwin.cc glview.cc
 SOURCES += value.cc expr.cc func.cc module.cc context.cc
 SOURCES += csgterm.cc polyset.cc csgops.cc transform.cc
 SOURCES += primitives.cc control.cc render.cc
-SOURCES += dxfdata.cc dxflinextrude.cc dxfrotextrude.cc
+SOURCES += dxfdata.cc dxftess.cc dxflinextrude.cc dxfrotextrude.cc
 
 QMAKE_CXXFLAGS += -O0
 // QMAKE_CXXFLAGS += -O3 -march=pentium
diff --git a/polyset.cc b/polyset.cc
index 0acc78b..bd2a085 100644
--- a/polyset.cc
+++ b/polyset.cc
@@ -36,11 +36,13 @@ void PolySet::append_poly()
 
 void PolySet::append_vertex(double x, double y, double z)
 {
+	grid.align(x, y, z);
 	polygons.last().append(Point(x, y, z));
 }
 
 void PolySet::insert_vertex(double x, double y, double z)
 {
+	grid.align(x, y, z);
 	polygons.last().insert(0, Point(x, y, z));
 }
 
@@ -194,19 +196,15 @@ public:
 	{
 		CGAL_Polybuilder B(hds, true);
 
-		typedef QPair<QPair<double,double>,double> PointKey_t;
-		#define PointKey(_x,_y,_z) PointKey_t(QPair<double,double>(_x,_y),_z)
-
 		QVector<PolySet::Point> vertices;
-		QHash<PointKey_t,int> vertices_idx;
+		Grid3d<int> vertices_idx;
 
 		for (int i = 0; i < ps->polygons.size(); i++) {
 			const PolySet::Polygon *poly = &ps->polygons[i];
 			for (int j = 0; j < poly->size(); j++) {
 				const PolySet::Point *p = &poly->at(j);
-				PointKey_t pk = PointKey(p->x, p->y, p->z);
-				if (!vertices_idx.contains(pk)) {
-					vertices_idx[pk] = vertices.size();
+				if (!vertices_idx.has(p->x, p->y, p->z)) {
+					vertices_idx.data(p->x, p->y, p->z) = vertices.size();
 					vertices.append(*p);
 				}
 			}
@@ -233,11 +231,10 @@ public:
 #endif
 			for (int j = 0; j < poly->size(); j++) {
 				const PolySet::Point *p = &poly->at(j);
-				PointKey_t pk = PointKey(p->x, p->y, p->z);
 #ifdef GEN_SURFACE_DEBUG
-				printf(" %d", vertices_idx[pk]);
+				printf(" %d", vertices_idx.data(p->x, p->y, p->z));
 #endif
-				B.add_vertex_to_facet(vertices_idx[pk]);
+				B.add_vertex_to_facet(vertices_idx.data(p->x, p->y, p->z));
 			}
 #ifdef GEN_SURFACE_DEBUG
 			printf("\n");