summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/CGALCache.cc2
-rw-r--r--src/csgterm.cc121
-rw-r--r--src/csgterm.h3
-rw-r--r--src/csgtermnormalizer.cc150
-rw-r--r--src/csgtermnormalizer.h22
-rw-r--r--src/mainwin.cc24
6 files changed, 179 insertions, 143 deletions
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]);
}
}
contact: Jan Huwald // Impressum