Refactored normalization into a separate class, hard-limited normalization to stop at 5000 nodes to keep from normalizing 'forever'

9 files changed, 187 insertions, 159 deletions

diff --git a/openscad.pro b/openscad.pro
index 344363a..0feca74 100644
--- a/openscad.pro
+++ b/openscad.pro
@@ -146,6 +146,7 @@ HEADERS += src/renderer.h \
            src/builtin.h \
            src/context.h \
            src/csgterm.h \
+           src/csgtermnormalizer.h \
            src/dxfdata.h \
            src/dxfdim.h \
            src/dxftess.h \
@@ -197,6 +198,7 @@ SOURCES += src/mathc99.cc \
            src/node.cc \
            src/context.cc \
            src/csgterm.cc \
+           src/csgtermnormalizer.cc \
            src/polyset.cc \
            src/csgops.cc \
            src/transform.cc \
diff --git a/src/CGALCache.cc b/src/CGALCache.cc
index 6bdad41..84de722 100644
--- a/src/CGALCache.cc
+++ b/src/CGALCache.cc
@@ -7,7 +7,9 @@ CGALCache *CGALCache::inst = NULL;
 void CGALCache::insert(const std::string &id, const CGAL_Nef_polyhedron &N)
 {
 	this->cache.insert(id, new CGAL_Nef_polyhedron(N), N.weight());
+#ifdef DEBUG
 	PRINTF("CGAL Cache insert: %s (%d verts)", id.substr(0, 40).c_str(), N.weight());
+#endif
 }
 
 void CGALCache::print()
diff --git a/src/csgterm.cc b/src/csgterm.cc
index 56fcbb5..b368072 100644
--- a/src/csgterm.cc
+++ b/src/csgterm.cc
@@ -140,127 +140,6 @@ void CSGTerm::initBoundingBox()
 	}
 }
 
-shared_ptr<CSGTerm> CSGTerm::normalize(shared_ptr<CSGTerm> term)
-{
-	// This function implements the CSG normalization
-  // Reference:
-	// Goldfeather, J., Molnar, S., Turk, G., and Fuchs, H. Near
-	// Realtime CSG Rendering Using Tree Normalization and Geometric
-	// Pruning. IEEE Computer Graphics and Applications, 9(3):20-28,
-	// 1989.
-  // http://www.cc.gatech.edu/~turk/my_papers/pxpl_csg.pdf
-
-	if (term->type == TYPE_PRIMITIVE) {
-		return term;
-	}
-
-	do {
-		while (term && normalize_tail(term)) { }
-		if (!term || term->type == TYPE_PRIMITIVE) return term;
-		term->left = normalize(term->left);
-	} while (term->type != TYPE_UNION &&
-					 (term->right->type != TYPE_PRIMITIVE || term->left->type == TYPE_UNION));
-	term->right = normalize(term->right);
-
-	// FIXME: Do we need to take into account any transformation of item here?
-	if (!term->right) {
-		if (term->type == TYPE_UNION || term->type == TYPE_DIFFERENCE) return term->left;
-		else return term->right;
-	}
-	if (!term->left) {
-		if (term->type == TYPE_UNION) return term->right;
-		else return term->left;
-	}
-
-	return term;
-}
-
-bool CSGTerm::normalize_tail(shared_ptr<CSGTerm> &term)
-{
-	if (term->type == TYPE_UNION || term->type == TYPE_PRIMITIVE) return false;
-
-	// Part A: The 'x . (y . z)' expressions
-
-	shared_ptr<CSGTerm> x = term->left;
-	shared_ptr<CSGTerm> y = term->right->left;
-	shared_ptr<CSGTerm> z = term->right->right;
-
-	shared_ptr<CSGTerm> result = term;
-
-	// 1.  x - (y + z) -> (x - y) - z
-	if (term->type == TYPE_DIFFERENCE && term->right->type == TYPE_UNION) {
-		term = createCSGTerm(TYPE_DIFFERENCE, 
-												 createCSGTerm(TYPE_DIFFERENCE, x, y),
-												 z);
-		return true;
-	}
-	// 2.  x * (y + z) -> (x * y) + (x * z)
-	else if (term->type == TYPE_INTERSECTION && term->right->type == TYPE_UNION) {
-		term = createCSGTerm(TYPE_UNION, 
-												 createCSGTerm(TYPE_INTERSECTION, x, y), 
-												 createCSGTerm(TYPE_INTERSECTION, x, z));
-		return true;
-	}
-	// 3.  x - (y * z) -> (x - y) + (x - z)
-	else if (term->type == TYPE_DIFFERENCE && term->right->type == TYPE_INTERSECTION) {
-		term = createCSGTerm(TYPE_UNION, 
-												 createCSGTerm(TYPE_DIFFERENCE, x, y), 
-												 createCSGTerm(TYPE_DIFFERENCE, x, z));
-		return true;
-	}
-	// 4.  x * (y * z) -> (x * y) * z
-	else if (term->type == TYPE_INTERSECTION && term->right->type == TYPE_INTERSECTION) {
-		term = createCSGTerm(TYPE_INTERSECTION, 
-												 createCSGTerm(TYPE_INTERSECTION, x, y),
-												 z);
-		return true;
-	}
-	// 5.  x - (y - z) -> (x - y) + (x * z)
-	else if (term->type == TYPE_DIFFERENCE && term->right->type == TYPE_DIFFERENCE) {
-		term = createCSGTerm(TYPE_UNION, 
-												 createCSGTerm(TYPE_DIFFERENCE, x, y), 
-												 createCSGTerm(TYPE_INTERSECTION, x, z));
-		return true;
-	}
-	// 6.  x * (y - z) -> (x * y) - z
-	else if (term->type == TYPE_INTERSECTION && term->right->type == TYPE_DIFFERENCE) {
-		term = createCSGTerm(TYPE_DIFFERENCE, 
-												 createCSGTerm(TYPE_INTERSECTION, x, y),
-												 z);
-		return true;
-	}
-
-	// Part B: The '(x . y) . z' expressions
-
-	x = term->left->left;
-	y = term->left->right;
-	z = term->right;
-
-	// 7. (x - y) * z  -> (x * z) - y
-	if (term->left->type == TYPE_DIFFERENCE && term->type == TYPE_INTERSECTION) {
-		term = createCSGTerm(TYPE_DIFFERENCE, 
-												 createCSGTerm(TYPE_INTERSECTION, x, z), 
-												 y);
-		return true;
-	}
-	// 8. (x + y) - z  -> (x - z) + (y - z)
-	else if (term->left->type == TYPE_UNION && term->type == TYPE_DIFFERENCE) {
-		term = createCSGTerm(TYPE_UNION, 
-												 createCSGTerm(TYPE_DIFFERENCE, x, z), 
-												 createCSGTerm(TYPE_DIFFERENCE, y, z));
-		return true;
-	}
-	// 9. (x + y) * z  -> (x * z) + (y * z)
-	else if (term->left->type == TYPE_UNION && term->type == TYPE_INTERSECTION) {
-		term = createCSGTerm(TYPE_UNION, 
-												 createCSGTerm(TYPE_INTERSECTION, x, z), 
-												 createCSGTerm(TYPE_INTERSECTION, y, z));
-		return true;
-	}
-
-	return false;
-}
-
 std::string CSGTerm::dump()
 {
 	std::stringstream dump;
diff --git a/src/csgterm.h b/src/csgterm.h
index 4930349..2e72dbc 100644
--- a/src/csgterm.h
+++ b/src/csgterm.h
@@ -33,9 +33,6 @@ public:
 
 	const BoundingBox &getBoundingBox() const { return this->bbox; }
 
-	static shared_ptr<CSGTerm> normalize(shared_ptr<CSGTerm> term);
-	static bool normalize_tail(shared_ptr<CSGTerm> &term);
-
 	std::string dump();
 private:
 	CSGTerm(type_e type, shared_ptr<CSGTerm> left, shared_ptr<CSGTerm> right);
diff --git a/src/csgtermnormalizer.cc b/src/csgtermnormalizer.cc
new file mode 100644
index 0000000..a830422
--- /dev/null
+++ b/src/csgtermnormalizer.cc
@@ -0,0 +1,150 @@
+#include "csgtermnormalizer.h"
+#include "csgterm.h"
+#include "printutils.h"
+
+shared_ptr<CSGTerm> CSGTermNormalizer::normalize(const shared_ptr<CSGTerm> &root)
+{
+	shared_ptr<CSGTerm> temp = root;
+	while (1) {
+		shared_ptr<CSGTerm> n = normalizePass(temp);
+		if (temp == n) break;
+		temp = n;
+
+		int num = count(temp);
+#ifdef DEBUG
+		PRINTF("Normalize count: %d\n", num);
+#endif
+		if (num > 5000) {
+			PRINTF("WARNING: Normalized tree is growing past 5000 elements. Aborting normalization.\n");
+			return root;
+		}
+	}
+	return temp;
+}
+
+shared_ptr<CSGTerm> CSGTermNormalizer::normalizePass(shared_ptr<CSGTerm> term)
+{
+	// This function implements the CSG normalization
+  // Reference:
+	// Goldfeather, J., Molnar, S., Turk, G., and Fuchs, H. Near
+	// Realtime CSG Rendering Using Tree Normalization and Geometric
+	// Pruning. IEEE Computer Graphics and Applications, 9(3):20-28,
+	// 1989.
+  // http://www.cc.gatech.edu/~turk/my_papers/pxpl_csg.pdf
+
+	if (term->type == CSGTerm::TYPE_PRIMITIVE) {
+		return term;
+	}
+
+	do {
+		while (term && normalize_tail(term)) { }
+		if (!term || term->type == CSGTerm::TYPE_PRIMITIVE) return term;
+		term->left = normalizePass(term->left);
+	} while (term->type != CSGTerm::TYPE_UNION &&
+					 (term->right->type != CSGTerm::TYPE_PRIMITIVE || term->left->type == CSGTerm::TYPE_UNION));
+	term->right = normalizePass(term->right);
+
+	// FIXME: Do we need to take into account any transformation of item here?
+	if (!term->right) {
+		if (term->type == CSGTerm::TYPE_UNION || term->type == CSGTerm::TYPE_DIFFERENCE) return term->left;
+		else return term->right;
+	}
+	if (!term->left) {
+		if (term->type == CSGTerm::TYPE_UNION) return term->right;
+		else return term->left;
+	}
+
+	return term;
+}
+
+bool CSGTermNormalizer::normalize_tail(shared_ptr<CSGTerm> &term)
+{
+	if (term->type == CSGTerm::TYPE_UNION || term->type == CSGTerm::TYPE_PRIMITIVE) return false;
+
+	// Part A: The 'x . (y . z)' expressions
+
+	shared_ptr<CSGTerm> x = term->left;
+	shared_ptr<CSGTerm> y = term->right->left;
+	shared_ptr<CSGTerm> z = term->right->right;
+
+	shared_ptr<CSGTerm> result = term;
+
+	// 1.  x - (y + z) -> (x - y) - z
+	if (term->type == CSGTerm::TYPE_DIFFERENCE && term->right->type == CSGTerm::TYPE_UNION) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, x, y),
+												 z);
+		return true;
+	}
+	// 2.  x * (y + z) -> (x * y) + (x * z)
+	else if (term->type == CSGTerm::TYPE_INTERSECTION && term->right->type == CSGTerm::TYPE_UNION) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_UNION, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, y), 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, z));
+		return true;
+	}
+	// 3.  x - (y * z) -> (x - y) + (x - z)
+	else if (term->type == CSGTerm::TYPE_DIFFERENCE && term->right->type == CSGTerm::TYPE_INTERSECTION) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_UNION, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, x, y), 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, x, z));
+		return true;
+	}
+	// 4.  x * (y * z) -> (x * y) * z
+	else if (term->type == CSGTerm::TYPE_INTERSECTION && term->right->type == CSGTerm::TYPE_INTERSECTION) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, y),
+												 z);
+		return true;
+	}
+	// 5.  x - (y - z) -> (x - y) + (x * z)
+	else if (term->type == CSGTerm::TYPE_DIFFERENCE && term->right->type == CSGTerm::TYPE_DIFFERENCE) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_UNION, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, x, y), 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, z));
+		return true;
+	}
+	// 6.  x * (y - z) -> (x * y) - z
+	else if (term->type == CSGTerm::TYPE_INTERSECTION && term->right->type == CSGTerm::TYPE_DIFFERENCE) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, y),
+												 z);
+		return true;
+	}
+
+	// Part B: The '(x . y) . z' expressions
+
+	x = term->left->left;
+	y = term->left->right;
+	z = term->right;
+
+	// 7. (x - y) * z  -> (x * z) - y
+	if (term->left->type == CSGTerm::TYPE_DIFFERENCE && term->type == CSGTerm::TYPE_INTERSECTION) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, z), 
+												 y);
+		return true;
+	}
+	// 8. (x + y) - z  -> (x - z) + (y - z)
+	else if (term->left->type == CSGTerm::TYPE_UNION && term->type == CSGTerm::TYPE_DIFFERENCE) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_UNION, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, x, z), 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_DIFFERENCE, y, z));
+		return true;
+	}
+	// 9. (x + y) * z  -> (x * z) + (y * z)
+	else if (term->left->type == CSGTerm::TYPE_UNION && term->type == CSGTerm::TYPE_INTERSECTION) {
+		term = CSGTerm::createCSGTerm(CSGTerm::TYPE_UNION, 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, x, z), 
+												 CSGTerm::createCSGTerm(CSGTerm::TYPE_INTERSECTION, y, z));
+		return true;
+	}
+
+	return false;
+}
+
+int CSGTermNormalizer::count(const shared_ptr<CSGTerm> &term) const
+{
+	if (!term) return 0;
+	return term->type == CSGTerm::TYPE_PRIMITIVE ? 1 : 0 + count(term->left) + count(term->right);
+}
diff --git a/src/csgtermnormalizer.h b/src/csgtermnormalizer.h
new file mode 100644
index 0000000..df37441
--- /dev/null
+++ b/src/csgtermnormalizer.h
@@ -0,0 +1,22 @@
+#ifndef CSGTERMNORMALIZER_H_
+#define CSGTERMNORMALIZER_H_
+
+#include "memory.h"
+
+class CSGTermNormalizer
+{
+public:
+	CSGTermNormalizer() : counter(0) {}
+	~CSGTermNormalizer() {}
+
+	shared_ptr<class CSGTerm> normalize(const shared_ptr<CSGTerm> &term);
+
+private:
+	shared_ptr<CSGTerm> normalizePass(shared_ptr<CSGTerm> term) ;
+	bool normalize_tail(shared_ptr<CSGTerm> &term);
+	int count(const shared_ptr<CSGTerm> &term) const;
+
+	int counter;
+};
+
+#endif
diff --git a/src/mainwin.cc b/src/mainwin.cc
index a169ab1..1b90b60 100644
--- a/src/mainwin.cc
+++ b/src/mainwin.cc
@@ -45,6 +45,7 @@
 #include "ProgressWidget.h"
 #endif
 #include "ThrownTogetherRenderer.h"
+#include "csgtermnormalizer.h"
 
 #include <QMenu>
 #include <QTime>
@@ -782,15 +783,8 @@ void MainWindow::compileCSG(bool procevents)
 		if (procevents)
 			QApplication::processEvents();
 		
-		this->root_norm_term = this->root_raw_term;
-		
-		// CSG normalization
-		while (1) {
-			shared_ptr<CSGTerm> n = CSGTerm::normalize(this->root_norm_term);
-			if (this->root_norm_term == n) break;
-			this->root_norm_term = n;
-		}
-		
+		CSGTermNormalizer normalizer;
+		this->root_norm_term = normalizer.normalize(this->root_raw_term);
 		assert(this->root_norm_term);
 
 		root_chain = new CSGChain();
@@ -804,11 +798,7 @@ void MainWindow::compileCSG(bool procevents)
 			
 			highlights_chain = new CSGChain();
 			for (unsigned int i = 0; i < highlight_terms.size(); i++) {
-				while (1) {
-					shared_ptr<CSGTerm> n = CSGTerm::normalize(highlight_terms[i]);
-					if (highlight_terms[i] == n) break;
-					highlight_terms[i] = n;
-				}
+				highlight_terms[i] = normalizer.normalize(highlight_terms[i]);
 				highlights_chain->import(highlight_terms[i]);
 			}
 		}
@@ -821,11 +811,7 @@ void MainWindow::compileCSG(bool procevents)
 			
 			background_chain = new CSGChain();
 			for (unsigned int i = 0; i < background_terms.size(); i++) {
-				while (1) {
-					shared_ptr<CSGTerm> n = CSGTerm::normalize(background_terms[i]);
-					if (background_terms[i] == n) break;
-					background_terms[i] = n;
-				}
+				background_terms[i] = normalizer.normalize(background_terms[i]);
 				background_chain->import(background_terms[i]);
 			}
 		}
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index b374188..2c49d94 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -253,6 +253,7 @@ set(CORE_SOURCES
   ../src/node.cc 
   ../src/context.cc 
   ../src/csgterm.cc 
+  ../src/csgtermnormalizer.cc 
   ../src/polyset.cc 
   ../src/csgops.cc 
   ../src/transform.cc 
diff --git a/tests/csgtestcore.cc b/tests/csgtestcore.cc
index c2be326..e8a6878 100644
--- a/tests/csgtestcore.cc
+++ b/tests/csgtestcore.cc
@@ -19,6 +19,7 @@
 #include "ThrownTogetherRenderer.h"
 
 #include "csgterm.h"
+#include "csgtermnormalizer.h"
 #include "OffscreenView.h"
 
 #include <QApplication>
@@ -315,12 +316,8 @@ int csgtestcore(int argc, char *argv[], test_type_e test_type)
 	}
 
 	// CSG normalization
-	csgInfo.root_norm_term = root_raw_term;
-	while (1) {
-		shared_ptr<CSGTerm> n = CSGTerm::normalize(csgInfo.root_norm_term);
-		if (csgInfo.root_norm_term == n) break;
-		csgInfo.root_norm_term = n;
-	}
+	CSGTermNormalizer normalizer;
+	csgInfo.root_norm_term = normalizer.normalize(root_raw_term);
 		
 	assert(csgInfo.root_norm_term);
 
@@ -333,11 +330,7 @@ int csgtestcore(int argc, char *argv[], test_type_e test_type)
 		
 		csgInfo.highlights_chain = new CSGChain();
 		for (unsigned int i = 0; i < csgInfo.highlight_terms.size(); i++) {
-			while (1) {
-				shared_ptr<CSGTerm> n = CSGTerm::normalize(csgInfo.highlight_terms[i]);
-				if (csgInfo.highlight_terms[i] == n) break;
-				csgInfo.highlight_terms[i] = n;
-			}
+			csgInfo.highlight_terms[i] = normalizer.normalize(csgInfo.highlight_terms[i]);
 			csgInfo.highlights_chain->import(csgInfo.highlight_terms[i]);
 		}
 	}
@@ -347,11 +340,7 @@ int csgtestcore(int argc, char *argv[], test_type_e test_type)
 		
 		csgInfo.background_chain = new CSGChain();
 		for (unsigned int i = 0; i < csgInfo.background_terms.size(); i++) {
-			while (1) {
-				shared_ptr<CSGTerm> n = CSGTerm::normalize(csgInfo.background_terms[i]);
-				if (csgInfo.background_terms[i] == n) break;
-				csgInfo.background_terms[i] = n;
-			}
+			csgInfo.background_terms[i] = normalizer.normalize(csgInfo.background_terms[i]);
 			csgInfo.background_chain->import(csgInfo.background_terms[i]);
 		}
 	}