From ff7b7c8838f55dc0f2e76f903630f1d3d2941d5a Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Mon, 14 Dec 2009 13:54:34 +0100 Subject: Added everything... -.- --- BSPTree.cpp | 83 ++++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 49 insertions(+), 34 deletions(-) (limited to 'BSPTree.cpp') diff --git a/BSPTree.cpp b/BSPTree.cpp index fa2f1c0..a94c77a 100644 --- a/BSPTree.cpp +++ b/BSPTree.cpp @@ -1,5 +1,23 @@ -#include "BSPTree.h" +/* + * 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 { @@ -9,20 +27,20 @@ vmml::vec3f BSPTree::Plane::intersection(const vmml::vec3f &p, const vmml::vec3f return p + r*dir; } -void BSPTree::Plane::partition(const Triangle &t, std::list *front, std::list *back) const { +void BSPTree::Plane::partition(const TriangleRecord &t, std::list *front, std::list *back) const { for(int i = 0; i < 3; ++i) { - if(contains(t.getVertex(i))) { - const vmml::vec3f *v[3] = {&t.getVertex(i), &t.getVertex((i+1)%3), &t.getVertex((i+2)%3)}; + 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(Triangle(*v[0], *v[1], is, t.getColor())); - back->push_back(Triangle(*v[0], is, *v[2], t.getColor())); + 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(Triangle(*v[0], *v[1], is, t.getColor())); - front->push_back(Triangle(*v[0], is, *v[2], t.getColor())); + 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; @@ -30,7 +48,7 @@ void BSPTree::Plane::partition(const Triangle &t, std::list *front, st } for(int i = 0; i < 3; ++i) { - const vmml::vec3f *v[3] = {&t.getVertex(i), &t.getVertex((i+1)%3), &t.getVertex((i+2)%3)}; + 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]))) { @@ -38,14 +56,14 @@ void BSPTree::Plane::partition(const Triangle &t, std::list *front, st vmml::vec3f is2 = intersection(*v[0], *v[2]-*v[0]); if(isInFront(*v[0])) { - front->push_back(Triangle(*v[0], is1, is2, t.getColor())); - back->push_back(Triangle(is1, *v[1], is2, t.getColor())); - back->push_back(Triangle(*v[1], *v[2], is2, t.getColor())); + 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(Triangle(*v[0], is1, is2, t.getColor())); - front->push_back(Triangle(is1, *v[1], is2, t.getColor())); - front->push_back(Triangle(*v[1], *v[2], is2, t.getColor())); + 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; @@ -54,7 +72,7 @@ void BSPTree::Plane::partition(const Triangle &t, std::list *front, st } -BSPTree::BSPTree(const std::list &triangles) : frontTree(0), backTree(0) { +BSPTree::BSPTree(const std::list &triangles) : frontTree(0), backTree(0) { const Triangle *planeT = findNearestTriangle(triangles, findCenter(triangles)); if(!planeT) @@ -62,29 +80,26 @@ BSPTree::BSPTree(const std::list &triangles) : frontTree(0), backTree( plane = Plane(*planeT); - std::list front, back; + std::list front, back; - for(std::list::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { - if(t->getNormal().squared_length() == 0) + for(std::list::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { + if(t->triangle.isDegenerate()) continue; - if(plane.contains(*t)) { + if(plane.contains(t->triangle)) { this->triangles.push_back(*t); continue; } - else if(plane.isInFront(*t)) { + else if(plane.isInFront(t->triangle)) { front.push_back(*t); continue; } - else if(plane.isBehind(*t)) { + else if(plane.isBehind(t->triangle)) { back.push_back(*t); continue; } - std::list frontPart, backPart; - plane.partition(*t, &frontPart, &backPart); - front.splice(front.end(), frontPart); - back.splice(back.end(), backPart); + plane.partition(*t, &front, &back); } if(!front.empty()) @@ -117,28 +132,28 @@ BSPTree& BSPTree::operator=(const BSPTree &tree) { return *this; } -vmml::vec3f BSPTree::findCenter(const std::list &triangles) { +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->getCenter(); + 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* 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->getNormal().squared_length() == 0) + for(std::list::const_iterator t = triangles.begin(); t != triangles.end(); ++t) { + if(t->triangle.isDegenerate()) continue; - float d = t->getCenter().squared_distance(v); + float d = t->triangle.getCenter().squared_distance(v); if(!current || d < distanceSq) { - current = &*t; + current = &t->triangle; distanceSq = d; } } -- cgit v1.2.3