diff options
Diffstat (limited to 'csgterm.cc')
| -rw-r--r-- | csgterm.cc | 155 |
1 files changed, 155 insertions, 0 deletions
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; + } +} + |