diff options
Diffstat (limited to 'src/BSPTree.cpp')
-rw-r--r-- | src/BSPTree.cpp | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/src/BSPTree.cpp b/src/BSPTree.cpp new file mode 100644 index 0000000..a94c77a --- /dev/null +++ b/src/BSPTree.cpp @@ -0,0 +1,164 @@ +/* + * BSPTree.cpp + * + * Copyright (C) 2009 Matthias Schiffer <matthias@gamezock.de> + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published by the + * Free Software Foundation, either version 3 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 Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License along + * with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "BSPTree.h" + +namespace Zoom { + +vmml::vec3f BSPTree::Plane::intersection(const vmml::vec3f &p, const vmml::vec3f &dir) const { + float r = (d - p.dot(normal))/dir.dot(normal); + + return p + r*dir; +} + +void BSPTree::Plane::partition(const TriangleRecord &t, std::list<TriangleRecord> *front, std::list<TriangleRecord> *back) const { + for(int i = 0; i < 3; ++i) { + if(contains(t.triangle.getVertex(i))) { + const vmml::vec3f *v[3] = {&t.triangle.getVertex(i), &t.triangle.getVertex((i+1)%3), &t.triangle.getVertex((i+2)%3)}; + + vmml::vec3f is = intersection(*v[1], *v[2]-*v[1]); + + if(isInFront(*v[1])) { + front->push_back(TriangleRecord(Triangle(*v[0], *v[1], is, t.triangle.getColor()), t.data)); + back->push_back(TriangleRecord(Triangle(*v[0], is, *v[2], t.triangle.getColor()), t.data)); + } + else { + back->push_back(TriangleRecord(Triangle(*v[0], *v[1], is, t.triangle.getColor()), t.data)); + front->push_back(TriangleRecord(Triangle(*v[0], is, *v[2], t.triangle.getColor()), t.data)); + } + + return; + } + } + + for(int i = 0; i < 3; ++i) { + const vmml::vec3f *v[3] = {&t.triangle.getVertex(i), &t.triangle.getVertex((i+1)%3), &t.triangle.getVertex((i+2)%3)}; + + if((isInFront(*v[0]) && isBehind(*v[1]) && isBehind(*v[2])) + || (isBehind(*v[0]) && isInFront(*v[1]) && isInFront(*v[2]))) { + vmml::vec3f is1 = intersection(*v[0], *v[1]-*v[0]); + vmml::vec3f is2 = intersection(*v[0], *v[2]-*v[0]); + + if(isInFront(*v[0])) { + front->push_back(TriangleRecord(Triangle(*v[0], is1, is2, t.triangle.getColor()), t.data)); + back->push_back(TriangleRecord(Triangle(is1, *v[1], is2, t.triangle.getColor()), t.data)); + back->push_back(TriangleRecord(Triangle(*v[1], *v[2], is2, t.triangle.getColor()), t.data)); + } + else { + back->push_back(TriangleRecord(Triangle(*v[0], is1, is2, t.triangle.getColor()), t.data)); + front->push_back(TriangleRecord(Triangle(is1, *v[1], is2, t.triangle.getColor()), t.data)); + front->push_back(TriangleRecord(Triangle(*v[1], *v[2], is2, t.triangle.getColor()), t.data)); + } + + return; + } + } +} + + +BSPTree::BSPTree(const std::list<TriangleRecord> &triangles) : frontTree(0), backTree(0) { + const Triangle *planeT = findNearestTriangle(triangles, findCenter(triangles)); + + if(!planeT) + return; + + plane = Plane(*planeT); + + std::list<TriangleRecord> front, back; + + for(std::list<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { + if(t->triangle.isDegenerate()) + continue; + + if(plane.contains(t->triangle)) { + this->triangles.push_back(*t); + continue; + } + else if(plane.isInFront(t->triangle)) { + front.push_back(*t); + continue; + } + else if(plane.isBehind(t->triangle)) { + back.push_back(*t); + continue; + } + + plane.partition(*t, &front, &back); + } + + if(!front.empty()) + frontTree = new BSPTree(front); + + if(!back.empty()) + backTree = new BSPTree(back); +} + +BSPTree& BSPTree::operator=(const BSPTree &tree) { + if(frontTree) { + delete frontTree; + frontTree = 0; + } + + if(backTree) { + delete backTree; + backTree = 0; + } + + plane = tree.plane; + triangles = tree.triangles; + + if(tree.frontTree) + frontTree = new BSPTree(*tree.frontTree); + + if(tree.backTree) + backTree = new BSPTree(*tree.backTree); + + return *this; +} + +vmml::vec3f BSPTree::findCenter(const std::list<TriangleRecord> &triangles) { + vmml::vec3f v; + + for(std::list<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { + v += t->triangle.getCenter(); + } + + return v/triangles.size(); +} + +const Triangle* BSPTree::findNearestTriangle(const std::list<TriangleRecord> &triangles, const vmml::vec3f &v) { + const Triangle *current = 0; + float distanceSq; + + for(std::list<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { + if(t->triangle.isDegenerate()) + continue; + + float d = t->triangle.getCenter().squared_distance(v); + + if(!current || d < distanceSq) { + current = &t->triangle; + distanceSq = d; + } + } + + return current; +} + +} |