Clifford Wolf:

	Generate CSG Products as part of compilation process



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

6 files changed, 128 insertions, 54 deletions

diff --git a/csgterm.cc b/csgterm.cc
index 58c5177..359d3b5 100644
--- a/csgterm.cc
+++ b/csgterm.cc
@@ -22,10 +22,11 @@
 
 #include "openscad.h"
 
-CSGTerm::CSGTerm(PolySet *polyset, double m[16])
+CSGTerm::CSGTerm(PolySet *polyset, QString label, double m[16])
 {
 	this->type = PRIMITIVE;
 	this->polyset = polyset;
+	this->label = label;
 	this->left = NULL;
 	this->right = NULL;
 	for (int i=0; i<16; i++)
@@ -44,7 +45,7 @@ CSGTerm::CSGTerm(type_e type, CSGTerm *left, CSGTerm *right)
 	refcounter = 1;
 }
 
-CSGTerm *CSGTerm::normalize(bool &changed)
+CSGTerm *CSGTerm::normalize()
 {
 	// This function implements the CSG normalization
 	// Reference: Florian Kirsch, Juergen Doeller,
@@ -55,15 +56,31 @@ CSGTerm *CSGTerm::normalize(bool &changed)
 	if (type == PRIMITIVE)
 		return link();
 
-	CSGTerm *x, *y, *z;
+	CSGTerm *t1, *t2, *x, *y;
+
+	x = left->normalize();
+	y = right->normalize();
+
+	if (x != left || y != right) {
+		t1 = new CSGTerm(type, x, y);
+	} else {
+		t1 = link();
+		x->unlink();
+		y->unlink();
+	}
+
+	do {
+		t2 = t1->normalize_tail();
+		t1->unlink();
+		t1 = t2;
+	} while (t1 != t2);
 
-	x = left->normalize(changed);
-	left->unlink();
-	left = x;
+	return t1;
+}
 
-	x = right->normalize(changed);
-	right->unlink();
-	right = x;
+CSGTerm *CSGTerm::normalize_tail()
+{
+	CSGTerm *x, *y, *z;
 
 	// Part A: The 'x . (y . z)' expressions
 
@@ -72,40 +89,28 @@ CSGTerm *CSGTerm::normalize(bool &changed)
 	z = right->right;
 
 	// 1.  x - (y + z) -> (x - y) - z
-	if (type == DIFFERENCE && right->type == UNION) {
-		changed = true;
+	if (type == DIFFERENCE && right->type == UNION)
 		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;
+	if (type == INTERSECTION && right->type == UNION)
 		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;
+	if (type == DIFFERENCE && right->type == INTERSECTION)
 		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;
+	if (type == INTERSECTION && right->type == INTERSECTION)
 		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;
+	if (type == DIFFERENCE && right->type == DIFFERENCE)
 		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;
+	if (type == INTERSECTION && right->type == DIFFERENCE)
 		return new CSGTerm(DIFFERENCE, new CSGTerm(INTERSECTION, x->link(), y->link()), z->link());
-	}
 
 	// Part B: The '(x . y) . z' expressions
 
@@ -114,24 +119,18 @@ CSGTerm *CSGTerm::normalize(bool &changed)
 	z = right;
 
 	// 7. (x - y) * z  -> (x * z) - y
-	if (left->type == DIFFERENCE && type == INTERSECTION) {
-		changed = true;
+	if (left->type == DIFFERENCE && type == INTERSECTION)
 		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;
+	if (left->type == UNION && type == DIFFERENCE)
 		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;
+	if (left->type == UNION && type == INTERSECTION)
 		return new CSGTerm(UNION, new CSGTerm(INTERSECTION, x->link(), z->link()), new CSGTerm(INTERSECTION, y->link(), z->link()));
-	}
 
-	return this;
+	return link();
 }
 
 CSGTerm *CSGTerm::link()
@@ -153,3 +152,13 @@ void CSGTerm::unlink()
 	}
 }
 
+QString CSGTerm::dump()
+{
+	if (type == UNION)
+		return QString("(%1 + %2)").arg(left->dump(), right->dump());
+	if (type == INTERSECTION)
+		return QString("(%1 * %2)").arg(left->dump(), right->dump());
+	if (type == DIFFERENCE)
+		return QString("(%1 - %2)").arg(left->dump(), right->dump());
+	return label;
+}
diff --git a/example.scad b/example.scad
index 8583963..65d20f4 100644
--- a/example.scad
+++ b/example.scad
@@ -33,10 +33,15 @@ module test003()
 {
 	intersection() {
 		difference() {
-			cube([3 3 3], center = true);
-			cube([5 1 1], center = true);
-			cube([1 5 1], center = true);
-			cube([1 1 5], center = true);
+			union() {
+				cube([3 3 3], center = true);
+				trans([0 0 -2.5]) cube([1.5 1.5 5], center = true);
+			}
+			union() {
+				cube([5 1 1], center = true);
+				cube([1 5 1], center = true);
+				cube([1 1 5], center = true);
+			}
 		}
 		trans([0 0 0.5])
 			cylinder(h = 5, r1 = 2, r2 = 0.5, center = true);
diff --git a/lexer.l b/lexer.l
index 56b33e6..644512e 100644
--- a/lexer.l
+++ b/lexer.l
@@ -51,7 +51,7 @@ extern const char *parser_input_buffer;
 "false"		return TOK_FALSE;
 "undef"		return TOK_UNDEF;
 
-[0-9][0-9.]* { parserlval.number = atof(yytext); return TOK_NUMBER; }
+[+-]?[0-9][0-9.]* { parserlval.number = atof(yytext); return TOK_NUMBER; }
 [a-zA-Z0-9_]+ { parserlval.text = strdup(yytext); return TOK_ID; }
 \"[^"]*\" { parserlval.text = strdup(yytext); return TOK_STRING; }
 
diff --git a/mainwin.cc b/mainwin.cc
index f9c447b..86c37ed 100644
--- a/mainwin.cc
+++ b/mainwin.cc
@@ -35,6 +35,10 @@ MainWindow::MainWindow(const char *filename)
 
 	root_module = NULL;
 	root_node = NULL;
+#ifdef ENABLE_OPENCSG
+	root_raw_term = NULL;
+	root_norm_term = NULL;
+#endif
 #ifdef ENABLE_CGAL
 	root_N = NULL;
 #endif
@@ -63,7 +67,9 @@ MainWindow::MainWindow(const char *filename)
 #endif
 		menu->addAction("Display &AST...", this, SLOT(actionDisplayAST()));
 		menu->addAction("Display CSG &Tree...", this, SLOT(actionDisplayCSGTree()));
+#ifdef ENABLE_OPENCSG
 		menu->addAction("Display CSG &Products...", this, SLOT(actionDisplayCSGProducts()));
+#endif
 		menu->addAction("Export as &STL...", this, SLOT(actionExportSTL()));
 		menu->addAction("Export as &OFF...", this, SLOT(actionExportOFF()));
 	}
@@ -201,13 +207,14 @@ void MainWindow::actionSaveAs()
 
 void MainWindow::actionCompile()
 {
+	console->append("Parsing design (AST generation)...");
+	QApplication::processEvents();
+
 	if (root_module) {
 		delete root_module;
 		root_module = NULL;
 	}
 
-	console->append("Parsing design (AST generation)...");
-	QApplication::processEvents();
 	root_module = parse(editor->toPlainText().toAscii().data(), false);
 
 	if (!root_module) {
@@ -215,13 +222,14 @@ void MainWindow::actionCompile()
 		return;
 	}
 
+	console->append("Compiling design (CSG Tree generation)...");
+	QApplication::processEvents();
+
 	if (root_node) {
 		delete root_node;
 		root_node = NULL;
 	}
 
-	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*>());
 
@@ -230,6 +238,46 @@ void MainWindow::actionCompile()
 		return;
 	}
 
+#ifdef ENABLE_OPENCSG
+	console->append("Compiling design (CSG Products generation)...");
+	QApplication::processEvents();
+
+	if (root_raw_term) {
+		root_raw_term->unlink();
+		root_raw_term = NULL;
+	}
+
+	double m[16];
+	root_raw_term = root_node->render_csg_term(m);
+
+	if (!root_raw_term) {
+		console->append("Compilation failed!");
+		return;
+	}
+
+	console->append("Compiling design (CSG Products normalization)...");
+	QApplication::processEvents();
+
+	if (root_norm_term) {
+		root_norm_term->unlink();
+		root_norm_term = NULL;
+	}
+
+	root_norm_term = root_raw_term->link();
+
+	CSGTerm *n;
+	do {
+		n = root_norm_term->normalize();
+		root_norm_term->unlink();
+		root_norm_term = n;
+	} while (root_norm_term != n);
+
+	if (!root_norm_term) {
+		console->append("Compilation failed!");
+		return;
+	}
+#endif /* ENABLE_OPENCSG */
+
 	console->append("Compilation finished.");
 }
 
@@ -307,20 +355,20 @@ void MainWindow::actionDisplayCSGTree()
 	e->resize(600, 400);
 }
 
+#ifdef ENABLE_OPENCSG
+
 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->setPlainText(QString("\nCSG before normalization:\n%1\n\n\nCSG after normalization:\n%2\n").arg(root_raw_term ? root_raw_term->dump() : "N/A", root_norm_term ? root_norm_term->dump() : "N/A"));
 	e->show();
 	e->resize(600, 400);
 }
 
+#endif /* ENABLE_OPENCSG */
+
 void MainWindow::actionExportSTL()
 {
 	console->append(QString("Function %1 is not implemented yet!").arg(QString(__PRETTY_FUNCTION__)));
diff --git a/openscad.h b/openscad.h
index 3003256..af35ee5 100644
--- a/openscad.h
+++ b/openscad.h
@@ -59,7 +59,10 @@ class ModuleInstanciation;
 class Module;
 
 class Context;
+class CSGTerm;
+class PolySet;
 class AbstractNode;
+class AbstractPolyNode;
 
 class Value
 {
@@ -308,18 +311,21 @@ public:
 
 	type_e type;
 	PolySet *polyset;
+	QString label;
 	CSGTerm *left;
 	CSGTerm *right;
 	int refcounter;
 	double m[16];
 
-	CSGTerm(PolySet *polyset, double m[16]);
+	CSGTerm(PolySet *polyset, QString label, double m[16]);
 	CSGTerm(type_e type, CSGTerm *left, CSGTerm *right);
 
-	CSGTerm *normalize(bool &changed);
+	CSGTerm *normalize();
+	CSGTerm *normalize_tail();
 
 	CSGTerm *link();
 	void unlink();
+	QString dump();
 };
 #endif
 
@@ -428,6 +434,10 @@ public:
 	Context root_ctx;
 	AbstractModule *root_module;
 	AbstractNode *root_node;
+#ifdef ENABLE_OPENCSG
+	CSGTerm *root_raw_term;
+	CSGTerm *root_norm_term;
+#endif
 #ifdef ENABLE_CGAL
 	CGAL_Nef_polyhedron *root_N;
 #endif
@@ -446,7 +456,9 @@ private slots:
 #endif
 	void actionDisplayAST();
 	void actionDisplayCSGTree();
+#ifdef ENABLE_OPENCSG
 	void actionDisplayCSGProducts();
+#endif
 	void actionExportSTL();
 	void actionExportOFF();
 };
diff --git a/polyset.cc b/polyset.cc
index f4304e3..a60828b 100644
--- a/polyset.cc
+++ b/polyset.cc
@@ -147,7 +147,7 @@ CGAL_Nef_polyhedron AbstractPolyNode::render_cgal_nef_polyhedron() const
 CSGTerm *AbstractPolyNode::render_csg_term(double m[16]) const
 {
 	PolySet *ps = render_polyset(RENDER_OPENCSG);
-	return new CSGTerm(ps, m);
+	return new CSGTerm(ps, QString("n%1").arg(idx), m);
 }
 
 #endif /* ENABLE_OPENCSG */