/* * BSPTree.cpp * * Copyright (C) 2009 Matthias Schiffer * * 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 . */ #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 *front, std::list *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 &triangles) : frontTree(0), backTree(0) { const Triangle *planeT = findNearestTriangle(triangles, findCenter(triangles)); if(!planeT) return; plane = Plane(*planeT); std::list front, back; for(std::list::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 &triangles) { vmml::vec3f v; for(std::list::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { v += t->triangle.getCenter(); } return v/triangles.size(); } const Triangle* BSPTree::findNearestTriangle(const std::list &triangles, const vmml::vec3f &v) { const Triangle *current = 0; float distanceSq; for(std::list::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; } }