Clifford Wolf:

	Preps for OpenCSG interface
	Invented AbstractPolyNode



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

10 files changed, 598 insertions, 117 deletions

diff --git a/README b/README
index 2ae9eb4..cf11f53 100644
--- a/README
+++ b/README
@@ -22,9 +22,18 @@ may not work as well..
 * CGAL (3.4):
   http://www.cgal.org/
 
+* boost (1.35, required by CGAL)
+  http://www.boost.org/
+
+* cmake (2.6.2, required by CGAL)
+  http://www.cmake.org/
+
 * OpenCSG (1.1.0):
   http://www.opencsg.org/
 
+* GLEW (bundled with OpenCSG)
+  http://glew.sourceforge.net/
+
 * GCC C++ Compiler (4.3.1):
   http://gcc.gnu.org/
 
diff --git a/csg.cc b/csg.cc
index de3b6b9..bc57d75 100644
--- a/csg.cc
+++ b/csg.cc
@@ -44,6 +44,9 @@ public:
 #ifdef ENABLE_CGAL
         virtual CGAL_Nef_polyhedron render_cgal_nef_polyhedron() const;
 #endif
+#ifdef ENABLE_OPENCSG
+	CSGTerm *render_csg_term(double m[16]) const;
+#endif
         virtual QString dump(QString indent) const;
 };
 
@@ -82,9 +85,33 @@ CGAL_Nef_polyhedron CsgNode::render_cgal_nef_polyhedron() const
 
 #endif /* ENABLE_CGAL */
 
+#ifdef ENABLE_OPENCSG
+
+CSGTerm *CsgNode::render_csg_term(double m[16]) const
+{
+	CSGTerm *t1 = NULL;
+	foreach (AbstractNode *v, children) {
+		CSGTerm *t2 = v->render_csg_term(m);
+		if (t2 && !t1) {
+			t1 = t2;
+		} else if (t2 && t1) {
+			if (type == UNION) {
+				t1 = new CSGTerm(CSGTerm::UNION, t1, t2);
+			} else if (type == DIFFERENCE) {
+				t1 = new CSGTerm(CSGTerm::DIFFERENCE, t1, t2);
+			} else if (type == INTERSECTION) {
+				t1 = new CSGTerm(CSGTerm::INTERSECTION, t1, t2);
+			}
+		}
+	}
+	return t1;
+}
+
+#endif /* ENABLE_OPENCSG */
+
 QString CsgNode::dump(QString indent) const
 {
-	QString text = indent;
+	QString text = indent + QString("n%1: ").arg(idx);
 	if (type == UNION)
 		text += "union() {\n";
 	if (type == DIFFERENCE)
diff --git a/csgterm.cc b/csgterm.cc
new file mode 100644
index 0000000..58c5177
--- /dev/null
+++ b/csgterm.cc
@@ -0,0 +1,155 @@
+/*
+ *  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"
+
+CSGTerm::CSGTerm(PolySet *polyset, double m[16])
+{
+	this->type = PRIMITIVE;
+	this->polyset = polyset;
+	this->left = NULL;
+	this->right = NULL;
+	for (int i=0; i<16; i++)
+		this->m[i] = m[i];
+	refcounter = 1;
+}
+
+CSGTerm::CSGTerm(type_e type, CSGTerm *left, CSGTerm *right)
+{
+	this->type = type;
+	this->polyset = NULL;
+	this->left = left;
+	this->right = right;
+	for (int i=0; i<16; i++)
+		this->m[i] = 0;
+	refcounter = 1;
+}
+
+CSGTerm *CSGTerm::normalize(bool &changed)
+{
+	// This function implements the CSG normalization
+	// Reference: Florian Kirsch, Juergen Doeller,
+	// OpenCSG: A Library for Image-Based CSG Rendering,
+	// University of Potsdam, Hasso-Plattner-Institute, Germany
+	// http://www.opencsg.org/data/csg_freenix2005_paper.pdf
+
+	if (type == PRIMITIVE)
+		return link();
+
+	CSGTerm *x, *y, *z;
+
+	x = left->normalize(changed);
+	left->unlink();
+	left = x;
+
+	x = right->normalize(changed);
+	right->unlink();
+	right = x;
+
+	// Part A: The 'x . (y . z)' expressions
+
+	x = left;
+	y = right->left;
+	z = right->right;
+
+	// 1.  x - (y + z) -> (x - y) - z
+	if (type == DIFFERENCE && right->type == UNION) {
+		changed = true;
+		return new CSGTerm(DIFFERENCE, new CSGTerm(DIFFERENCE, x->link(), y->link()), z->link());
+	}
+
+	// 2.  x * (y + z) -> (x * y) + (x * z)
+	if (type == INTERSECTION && right->type == UNION) {
+		changed = true;
+		return new CSGTerm(UNION, new CSGTerm(INTERSECTION, x->link(), y->link()), new CSGTerm(INTERSECTION, x->link(), z->link()));
+	}
+
+	// 3.  x - (y * z) -> (x - y) + (x - z)
+	if (type == DIFFERENCE && right->type == INTERSECTION) {
+		changed = true;
+		return new CSGTerm(UNION, new CSGTerm(DIFFERENCE, x->link(), y->link()), new CSGTerm(DIFFERENCE, x->link(), z->link()));
+	}
+
+	// 4.  x * (y * z) -> (x * y) * z
+	if (type == INTERSECTION && right->type == INTERSECTION) {
+		changed = true;
+		return new CSGTerm(INTERSECTION, new CSGTerm(INTERSECTION, x->link(), y->link()), z->link());
+	}
+
+	// 5.  x - (y - z) -> (x - y) + (x * z)
+	if (type == DIFFERENCE && right->type == DIFFERENCE) {
+		changed = true;
+		return new CSGTerm(UNION, new CSGTerm(DIFFERENCE, x->link(), y->link()), new CSGTerm(INTERSECTION, x->link(), z->link()));
+	}
+
+	// 6.  x * (y - z) -> (x * y) - z
+	if (type == INTERSECTION && right->type == DIFFERENCE) {
+		changed = true;
+		return new CSGTerm(DIFFERENCE, new CSGTerm(INTERSECTION, x->link(), y->link()), z->link());
+	}
+
+	// Part B: The '(x . y) . z' expressions
+
+	x = left->left;
+	y = left->right;
+	z = right;
+
+	// 7. (x - y) * z  -> (x * z) - y
+	if (left->type == DIFFERENCE && type == INTERSECTION) {
+		changed = true;
+		return new CSGTerm(DIFFERENCE, new CSGTerm(INTERSECTION, x->link(), z->link()), y->link());
+	}
+
+	// 8. (x + y) - z  -> (x - z) + (y - z)
+	if (left->type == UNION && type == DIFFERENCE) {
+		changed = true;
+		return new CSGTerm(UNION, new CSGTerm(DIFFERENCE, x->link(), z->link()), new CSGTerm(DIFFERENCE, y->link(), z->link()));
+	}
+
+	// 9. (x + y) * z  -> (x * z) + (y * z)
+	if (left->type == UNION && type == INTERSECTION) {
+		changed = true;
+		return new CSGTerm(UNION, new CSGTerm(INTERSECTION, x->link(), z->link()), new CSGTerm(INTERSECTION, y->link(), z->link()));
+	}
+
+	return this;
+}
+
+CSGTerm *CSGTerm::link()
+{
+	refcounter++;
+	return this;
+}
+
+void CSGTerm::unlink()
+{
+	if (--refcounter <= 0) {
+		if (polyset)
+			delete polyset;
+		if (left)
+			left->unlink();
+		if (right)
+			right->unlink();
+		delete this;
+	}
+}
+
diff --git a/mainwin.cc b/mainwin.cc
index c6e3402..f9c447b 100644
--- a/mainwin.cc
+++ b/mainwin.cc
@@ -35,7 +35,9 @@ MainWindow::MainWindow(const char *filename)
 
 	root_module = NULL;
 	root_node = NULL;
+#ifdef ENABLE_CGAL
 	root_N = NULL;
+#endif
 
 	if (filename) {
 		this->filename = QString(filename);
@@ -60,7 +62,8 @@ MainWindow::MainWindow(const char *filename)
 		menu->addAction("Compile and &Render (CGAL)", this, SLOT(actionRenderCGAL()));
 #endif
 		menu->addAction("Display &AST...", this, SLOT(actionDisplayAST()));
-		menu->addAction("Display &CSG...", this, SLOT(actionDisplayCSG()));
+		menu->addAction("Display CSG &Tree...", this, SLOT(actionDisplayCSGTree()));
+		menu->addAction("Display CSG &Products...", this, SLOT(actionDisplayCSGProducts()));
 		menu->addAction("Export as &STL...", this, SLOT(actionExportSTL()));
 		menu->addAction("Export as &OFF...", this, SLOT(actionExportOFF()));
 	}
@@ -135,8 +138,10 @@ MainWindow::~MainWindow()
 		delete root_module;
 	if (root_node)
 		delete root_node;
+#ifdef ENABLE_CGAL
 	if (root_N)
 		delete root_N;
+#endif
 }
 
 void MainWindow::actionNew()
@@ -215,8 +220,9 @@ void MainWindow::actionCompile()
 		root_node = NULL;
 	}
 
-	console->append("Compiling design (CSG generation)...");
+	console->append("Compiling design (CSG Tree generation)...");
 	QApplication::processEvents();
+	AbstractNode::idx_counter = 1;
 	root_node = root_module->evaluate(&root_ctx, QVector<QString>(), QVector<Value>(), QVector<AbstractNode*>());
 
 	if (!root_node) {
@@ -287,7 +293,7 @@ void MainWindow::actionDisplayAST()
 	e->resize(600, 400);
 }
 
-void MainWindow::actionDisplayCSG()
+void MainWindow::actionDisplayCSGTree()
 {
 	QTextEdit *e = new QTextEdit(NULL);
 	e->setTabStopWidth(30);
@@ -301,6 +307,20 @@ void MainWindow::actionDisplayCSG()
 	e->resize(600, 400);
 }
 
+void MainWindow::actionDisplayCSGProducts()
+{
+	QTextEdit *e = new QTextEdit(NULL);
+	e->setTabStopWidth(30);
+	e->setWindowTitle("CSG Dump");
+	if (root_node) {
+		e->setPlainText("Fixme!");
+	} else {
+		e->setPlainText("No CSG to dump. Please try compiling first...");
+	}
+	e->show();
+	e->resize(600, 400);
+}
+
 void MainWindow::actionExportSTL()
 {
 	console->append(QString("Function %1 is not implemented yet!").arg(QString(__PRETTY_FUNCTION__)));
diff --git a/module.cc b/module.cc
index 9f9a21b..0d275a6 100644
--- a/module.cc
+++ b/module.cc
@@ -192,6 +192,13 @@ void destroy_builtin_modules()
 	builtin_modules.clear();
 }
 
+int AbstractNode::idx_counter;
+
+AbstractNode::AbstractNode()
+{
+	idx = idx_counter++;
+}
+
 AbstractNode::~AbstractNode()
 {
 	foreach (AbstractNode *v, children)
@@ -211,9 +218,27 @@ CGAL_Nef_polyhedron AbstractNode::render_cgal_nef_polyhedron() const
 
 #endif /* ENABLE_CGAL */
 
+#ifdef ENABLE_OPENCSG
+
+CSGTerm *AbstractNode::render_csg_term(double m[16]) const
+{
+	CSGTerm *t1 = NULL;
+	foreach(AbstractNode * v, children) {
+		CSGTerm *t2 = v->render_csg_term(m);
+		if (t2 && !t1) {
+			t1 = t2;
+		} else if (t2 && t1) {
+			t1 = new CSGTerm(CSGTerm::UNION, t1, t2);
+		}
+	}
+	return t1;
+}
+
+#endif /* ENABLE_OPENCSG */
+
 QString AbstractNode::dump(QString indent) const
 {
-	QString text = indent + "group() {\n";
+	QString text = indent + QString("n%1: group() {\n").arg(idx);
 	foreach (AbstractNode *v, children)
 		text += v->dump(indent + QString("\t"));
 	return text + indent + "}\n";
diff --git a/openscad.h b/openscad.h
index 9ca09d9..3003256 100644
--- a/openscad.h
+++ b/openscad.h
@@ -21,6 +21,16 @@
 #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];
+}
+
 #include <QHash>
 #include <QVector>
 #include <QMainWindow>
@@ -261,6 +271,58 @@ typedef CGAL_Nef_polyhedron::Point_3 CGAL_Point;
 
 #endif /* ENABLE_CGAL */
 
+class PolySet
+{
+public:
+	struct Point {
+		double x, y, z;
+		Point() : x(0), y(0), z(0) { }
+		Point(double x, double y, double z) : x(x), y(y), z(z) { }
+	};
+	typedef QList<Point> Polygon;
+	QVector<Polygon> polygons;
+
+	PolySet();
+
+	void append_poly();
+	void append_vertex(double x, double y, double z);
+	void insert_vertex(double x, double y, double z);
+
+	void render_opengl() const;
+
+#ifdef ENABLE_CGAL
+	CGAL_Nef_polyhedron render_cgal_nef_polyhedron() const;
+#endif
+};
+
+#ifdef ENABLE_OPENCSG
+class CSGTerm
+{
+public:
+	enum type_e {
+		PRIMITIVE,
+		UNION,
+		INTERSECTION,
+		DIFFERENCE
+	};
+
+	type_e type;
+	PolySet *polyset;
+	CSGTerm *left;
+	CSGTerm *right;
+	int refcounter;
+	double m[16];
+
+	CSGTerm(PolySet *polyset, double m[16]);
+	CSGTerm(type_e type, CSGTerm *left, CSGTerm *right);
+
+	CSGTerm *normalize(bool &changed);
+
+	CSGTerm *link();
+	void unlink();
+};
+#endif
+
 class AbstractNode
 {
 public:
@@ -270,13 +332,36 @@ public:
 	void progress_prepare();
 	void progress_report() const;
 
+	int idx;
+	static int idx_counter;
+
+	AbstractNode();
 	virtual ~AbstractNode();
 #ifdef ENABLE_CGAL
 	virtual CGAL_Nef_polyhedron render_cgal_nef_polyhedron() const;
 #endif
+#ifdef ENABLE_OPENCSG
+	virtual CSGTerm *render_csg_term(double m[16]) const;
+#endif
 	virtual QString dump(QString indent) const;
 };
 
+class AbstractPolyNode : public AbstractNode
+{
+public:
+	enum render_mode_e {
+		RENDER_CGAL,
+		RENDER_OPENCSG
+	};
+	virtual PolySet *render_polyset(render_mode_e mode) const;
+#ifdef ENABLE_CGAL
+	virtual CGAL_Nef_polyhedron render_cgal_nef_polyhedron() const;
+#endif
+#ifdef ENABLE_OPENCSG
+	virtual CSGTerm *render_csg_term(double m[16]) const;
+#endif
+};
+
 extern int progress_report_count;
 extern void (*progress_report_f)(const class AbstractNode*, void*, int);
 extern void *progress_report_vp;
@@ -286,6 +371,7 @@ void progress_report_fin();
 
 #else
 
+// Needed for Mainwin::root_N
 // this is a bit hackish - but a pointer is a pointer..
 struct CGAL_Nef_polyhedron;
 
@@ -359,7 +445,8 @@ private slots:
 	void actionRenderCGAL();
 #endif
 	void actionDisplayAST();
-	void actionDisplayCSG();
+	void actionDisplayCSGTree();
+	void actionDisplayCSGProducts();
 	void actionExportSTL();
 	void actionExportOFF();
 };
diff --git a/openscad.pro b/openscad.pro
index 5e05b0e..30caf29 100644
--- a/openscad.pro
+++ b/openscad.pro
@@ -5,13 +5,17 @@ TEMPLATE = app
 DEFINES += "ENABLE_CGAL=1"
 LIBS += -lCGAL -lmpfr
 
+DEFINES += "ENABLE_OPENCSG=1"
+LIBS += -lopencsg -lGLEW
+
 LEXSOURCES += lexer.l
 YACCSOURCES += parser.y
 
 HEADERS += openscad.h
 SOURCES += openscad.cc mainwin.cc glview.cc
 SOURCES += value.cc expr.cc func.cc module.cc context.cc
-SOURCES += csg.cc trans.cc primitive.cc
+SOURCES += csgterm.cc polyset.cc csg.cc trans.cc
+SOURCES += primitive.cc
 
 QT += opengl
 
diff --git a/polyset.cc b/polyset.cc
new file mode 100644
index 0000000..f4304e3
--- /dev/null
+++ b/polyset.cc
@@ -0,0 +1,154 @@
+/*
+ *  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"
+
+PolySet::PolySet()
+{
+}
+
+void PolySet::append_poly()
+{
+	polygons.append(Polygon());
+}
+
+void PolySet::append_vertex(double x, double y, double z)
+{
+	polygons.last().append(Point(x, y, z));
+}
+
+void PolySet::insert_vertex(double x, double y, double z)
+{
+	polygons.last().insert(0, Point(x, y, z));
+}
+
+void PolySet::render_opengl() const
+{
+	for (int i = 0; i < polygons.size(); i++) {
+		const Polygon *poly = &polygons[i];
+		glBegin(GL_POLYGON);
+		for (int j = 0; j < poly->size(); j++) {
+			const Point *p = &poly->at(j);
+			glVertex3d(p->x, p->y, p->z);
+		}
+		glEnd();
+	}
+}
+
+#ifdef ENABLE_CGAL
+
+class CGAL_Build_PolySet : public CGAL::Modifier_base<CGAL_HDS>
+{
+public:
+	typedef CGAL_HDS::Vertex::Point Point;
+
+	const PolySet *ps;
+	CGAL_Build_PolySet(const PolySet *ps) : ps(ps) { }
+
+	void operator()(CGAL_HDS& hds)
+	{
+		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;
+
+		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();
+					vertices.append(*p);
+				}
+			}
+		}
+
+		B.begin_surface(vertices.size(), ps->polygons.size());
+
+		for (int i = 0; i < vertices.size(); i++) {
+			const PolySet::Point *p = &vertices[i];
+			B.add_vertex(Point(p->x, p->y, p->z));
+		}
+
+		for (int i = 0; i < ps->polygons.size(); i++) {
+			const PolySet::Polygon *poly = &ps->polygons[i];
+			B.begin_facet();
+			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);
+				B.add_vertex_to_facet(vertices_idx[pk]);
+			}
+			B.end_facet();
+		}
+
+		B.end_surface();
+
+		#undef PointKey
+	}
+};
+
+CGAL_Nef_polyhedron PolySet::render_cgal_nef_polyhedron() const
+{
+	CGAL_Polyhedron P;
+	CGAL_Build_PolySet builder(this);
+	P.delegate(builder);
+#if 0
+	std::cout << P;
+#endif
+	CGAL_Nef_polyhedron N(P);
+	return N;
+}
+
+#endif /* ENABLE_CGAL */
+
+PolySet *AbstractPolyNode::render_polyset(render_mode_e) const
+{
+	return NULL;
+}
+
+#ifdef ENABLE_CGAL
+
+CGAL_Nef_polyhedron AbstractPolyNode::render_cgal_nef_polyhedron() const
+{
+	PolySet *ps = render_polyset(RENDER_CGAL);
+	CGAL_Nef_polyhedron N = ps->render_cgal_nef_polyhedron();
+	progress_report();
+	delete ps;
+	return N;
+}
+
+#endif /* ENABLE_CGAL */
+
+#ifdef ENABLE_OPENCSG
+
+CSGTerm *AbstractPolyNode::render_csg_term(double m[16]) const
+{
+	PolySet *ps = render_polyset(RENDER_OPENCSG);
+	return new CSGTerm(ps, m);
+}
+
+#endif /* ENABLE_OPENCSG */
+
diff --git a/primitive.cc b/primitive.cc
index 1f3815d..a3846a4 100644
--- a/primitive.cc
+++ b/primitive.cc
@@ -36,16 +36,14 @@ public:
 	virtual AbstractNode *evaluate(const Context *ctx, const QVector<QString> &call_argnames, const QVector<Value> &call_argvalues, const QVector<AbstractNode*> child_nodes) const;
 };
 
-class PrimitiveNode : public AbstractNode
+class PrimitiveNode : public AbstractPolyNode
 {
 public:
 	bool center;
 	double x, y, z, h, r1, r2;
 	primitive_type_e type;
 	PrimitiveNode(primitive_type_e type) : type(type) { }
-#ifdef ENABLE_CGAL
-	virtual CGAL_Nef_polyhedron render_cgal_nef_polyhedron() const;
-#endif
+	virtual PolySet *render_polyset(render_mode_e mode) const;
 	virtual QString dump(QString indent) const;
 };
 
@@ -134,124 +132,126 @@ void register_builtin_primitive()
 	builtin_modules["cylinder"] = new PrimitiveModule(CYLINDER);
 }
 
-#ifdef ENABLE_CGAL
 
-static int cube_facets[6][4] = {
-	{ 0, 1, 2, 3 },
-	{ 7, 6, 5, 4 },
-	{ 4, 5, 1, 0 },
-	{ 5, 6, 2, 1 },
-	{ 6, 7, 3, 2 },
-	{ 7, 4, 0, 3 }
-};
-
-class CGAL_Build_cube : public CGAL::Modifier_base<CGAL_HDS>
+PolySet *PrimitiveNode::render_polyset(render_mode_e mode) const
 {
-public:
-	typedef CGAL_HDS::Vertex::Point Point;
+	PolySet *p = new PolySet();
+
+	if (type == CUBE && x > 0 && y > 0 && z > 0)
+	{
+		double x1, x2, y1, y2, z1, z2;
+		if (center) {
+			x1 = -x/2;
+			x2 = +x/2;
+			y1 = -y/2;
+			y2 = +y/2;
+			z1 = -z/2;
+			z2 = +z/2;
+		} else {
+			x1 = y1 = z1 = 0;
+			x2 = x;
+			y2 = y;
+			z2 = z;
+		}
+
+		p->append_poly(); // top
+		p->append_vertex(x1, y1, z2);
+		p->append_vertex(x2, y1, z2);
+		p->append_vertex(x2, y2, z2);
+		p->append_vertex(x1, y2, z2);
+
+		p->append_poly(); // bottom
+		p->append_vertex(x1, y2, z1);
+		p->append_vertex(x2, y2, z1);
+		p->append_vertex(x2, y1, z1);
+		p->append_vertex(x1, y1, z1);
+
+		p->append_poly(); // side1
+		p->append_vertex(x1, y1, z1);
+		p->append_vertex(x2, y1, z1);
+		p->append_vertex(x2, y1, z2);
+		p->append_vertex(x1, y1, z2);
+
+		p->append_poly(); // side2
+		p->append_vertex(x2, y1, z1);
+		p->append_vertex(x2, y2, z1);
+		p->append_vertex(x2, y2, z2);
+		p->append_vertex(x2, y1, z2);
+
+		p->append_poly(); // side3
+		p->append_vertex(x2, y2, z1);
+		p->append_vertex(x1, y2, z1);
+		p->append_vertex(x1, y2, z2);
+		p->append_vertex(x2, y2, z2);
+
+		p->append_poly(); // side4
+		p->append_vertex(x1, y2, z1);
+		p->append_vertex(x1, y1, z1);
+		p->append_vertex(x1, y1, z2);
+		p->append_vertex(x1, y2, z2);
+	}
 
-	const PrimitiveNode *n;
-	CGAL_Build_cube(const PrimitiveNode *n) : n(n) { }
+	if (type == SPHERE && r1 > 0)
+	{
+		/* FIXME */
+	}
 
-	void operator()(CGAL_HDS& hds)
+	if (type == CYLINDER && h > 0 && r1 >=0 && r2 >= 0 && (r1 > 0 || r2 > 0))
 	{
-		CGAL_Polybuilder B(hds, true);
-
-		if (n->type == CUBE) {
-			B.begin_surface(8, 6, 24);
-			double x1, x2, y1, y2, z1, z2;
-			if (n->center) {
-				x1 = -n->x/2;
-				x2 = +n->x/2;
-				y1 = -n->y/2;
-				y2 = +n->y/2;
-				z1 = -n->z/2;
-				z2 = +n->z/2;
-			} else {
-				x1 = y1 = z1 = 0;
-				x2 = n->x;
-				y2 = n->y;
-				z2 = n->z;
-			}
-			B.add_vertex(Point(x1, y1, z2)); // 0
-			B.add_vertex(Point(x2, y1, z2)); // 1
-			B.add_vertex(Point(x2, y2, z2)); // 2
-			B.add_vertex(Point(x1, y2, z2)); // 3
-			B.add_vertex(Point(x1, y1, z1)); // 4
-			B.add_vertex(Point(x2, y1, z1)); // 5
-			B.add_vertex(Point(x2, y2, z1)); // 6
-			B.add_vertex(Point(x1, y2, z1)); // 7
-			for (int i = 0; i < 6; i++) {
-				B.begin_facet();
-				for (int j = 0; j < 4; j++)
-					B.add_vertex_to_facet(cube_facets[i][j]);
-				B.end_facet();
-			}
-			B.end_surface();
+		int fragments = 10;
+
+		double z1, z2;
+		if (center) {
+			z1 = -h/2;
+			z2 = +h/2;
+		} else {
+			z1 = 0;
+			z2 = h;
+		}
+
+		struct point2d {
+			double x, y;
+		};
+
+		point2d circle1[fragments];
+		point2d circle2[fragments];
+
+		for (int i=0; i<fragments; i++) {
+			double phi = (M_PI*2*i) / fragments;
+			circle1[i].x = r1*cos(phi);
+			circle1[i].y = r1*sin(phi);
+			circle2[i].x = r2*cos(phi);
+			circle2[i].y = r2*sin(phi);
+		}
+		
+		for (int i=0; i<fragments; i++) {
+			int j = (i+1) % fragments;
+			p->append_poly();
+			p->append_vertex(circle1[i].x, circle1[i].y, z1);
+			p->append_vertex(circle2[i].x, circle2[i].y, z2);
+			p->append_vertex(circle1[j].x, circle1[j].y, z1);
+			p->append_poly();
+			p->append_vertex(circle2[i].x, circle2[i].y, z2);
+			p->append_vertex(circle2[j].x, circle2[j].y, z2);
+			p->append_vertex(circle1[j].x, circle1[j].y, z1);
 		}
 
-		if (n->type == SPHERE) {
-			/* FIXME */
+		if (r1 > 0) {
+			p->append_poly();
+			for (int i=0; i<fragments; i++)
+				p->append_vertex(circle1[i].x, circle1[i].y, z1);
 		}
 
-		if (n->type == CYLINDER) {
-			int fragments = 10;
-			B.begin_surface(fragments*2, fragments*2+2);
-			double z1, z2;
-			if (n->center) {
-				z1 = -n->h/2;
-				z2 = +n->h/2;
-			} else {
-				z1 = 0;
-				z2 = n->h;
-			}
-			for (int i=0; i<fragments; i++) {
-				double phi = (M_PI*2*i) / fragments;
-				B.add_vertex(Point(n->r1*cos(phi), n->r1*sin(phi), z1));
-				B.add_vertex(Point(n->r2*cos(phi), n->r2*sin(phi), z2));
-			}
-			for (int i=0; i<fragments; i++) {
-				B.begin_facet();
-				B.add_vertex_to_facet(i*2);
-				B.add_vertex_to_facet(i*2+1);
-				B.add_vertex_to_facet(((i+1)%fragments)*2);
-				B.end_facet();
-				B.begin_facet();
-				B.add_vertex_to_facet(i*2+1);
-				B.add_vertex_to_facet(((i+1)%fragments)*2+1);
-				B.add_vertex_to_facet(((i+1)%fragments)*2);
-				B.end_facet();
-			}
-			B.begin_facet();
-			for (int i=0; i<fragments; i++) {
-				B.add_vertex_to_facet(i*2);
-			}
-			B.end_facet();
-			B.begin_facet();
-			for (int i=fragments-1; i>=0; i--) {
-				B.add_vertex_to_facet(i*2+1);
-			}
-			B.end_facet();
-			B.end_surface();
+		if (r2 > 0) {
+			p->append_poly();
+			for (int i=0; i<fragments; i++)
+				p->insert_vertex(circle2[i].x, circle2[i].y, z2);
 		}
 	}
-};
 
-CGAL_Nef_polyhedron PrimitiveNode::render_cgal_nef_polyhedron() const
-{
-	CGAL_Polyhedron P;
-	CGAL_Build_cube builder(this);
-	P.delegate(builder);
-#if 0
-	std::cout << P;
-#endif
-	CGAL_Nef_polyhedron N(P);
-	progress_report();
-	return N;
+	return p;
 }
 
-#endif /* ENABLE_CGAL */
-
 QString PrimitiveNode::dump(QString indent) const
 {
 	QString text;
@@ -261,6 +261,6 @@ QString PrimitiveNode::dump(QString indent) const
 		text.sprintf("sphere(r = %f);\n", r1);
 	if (type == CYLINDER)
 		text.sprintf("cylinder(h = %f, r1 = %f, r2 = %f, center = %s);\n", h, r1, r2, center ? "true" : "false");
-	return indent + text;
+	return indent + QString("n%1: ").arg(idx) + text;
 }
 
diff --git a/trans.cc b/trans.cc
index 71498bb..978de53 100644
--- a/trans.cc
+++ b/trans.cc
@@ -73,7 +73,7 @@ CGAL_Nef_polyhedron TransNode::render_cgal_nef_polyhedron() const
 QString TransNode::dump(QString indent) const
 {
 	QString text;
-	text.sprintf("trans([%f %f %f])", x, y, z);
+	text.sprintf("n%d: trans([%f %f %f])", idx, x, y, z);
 	text = indent + text + " {\n";
 	foreach (AbstractNode *v, children)
 		text += v->dump(indent + QString("\t"));