From d9f44af7aee41a111a3d7427d8735bc821f1824f Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Tue, 15 Dec 2009 19:37:12 +0100 Subject: Moved source files to src; sort triangles by texture. --- BSPTree.cpp | 164 ------------------------------------------------------------ 1 file changed, 164 deletions(-) delete mode 100644 BSPTree.cpp (limited to 'BSPTree.cpp') diff --git a/BSPTree.cpp b/BSPTree.cpp deleted file mode 100644 index a94c77a..0000000 --- a/BSPTree.cpp +++ /dev/null @@ -1,164 +0,0 @@ -/* - * 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; -} - -} -- cgit v1.2.3