From 3c3fbdfeddbf555849581399ccff468901826027 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Constantin=20Ri=C3=9F?= Date: Wed, 28 Apr 2010 17:18:19 +0200 Subject: =?UTF-8?q?lange=20nix=20mehr=20ge=C3=A4ndert#?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- BSPTree.cpp | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ BSPTree.h | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 278 insertions(+) create mode 100644 BSPTree.cpp create mode 100644 BSPTree.h diff --git a/BSPTree.cpp b/BSPTree.cpp new file mode 100644 index 0000000..ff43274 --- /dev/null +++ b/BSPTree.cpp @@ -0,0 +1,146 @@ +#include "BSPTree.h" + +#include + +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 Triangle &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)}; + + 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())); + } + else { + back->push_back(Triangle(*v[0], *v[1], is, t.getColor())); + front->push_back(Triangle(*v[0], is, *v[2], t.getColor())); + } + + return; + } + } + + 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)}; + + 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(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())); + } + 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())); + } + + 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->getNormal().squared_length() == 0) + continue; + + if(plane.contains(*t)) { + this->triangles.push_back(*t); + continue; + } + else if(plane.isInFront(*t)) { + front.push_back(*t); + continue; + } + else if(plane.isBehind(*t)) { + back.push_back(*t); + continue; + } + + std::list frontPart, backPart; + plane.partition(*t, &frontPart, &backPart); + front.splice(front.end(), frontPart); + back.splice(back.end(), backPart); + } + + 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->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->getNormal().squared_length() == 0) + continue; + + float d = t->getCenter().squared_distance(v); + + if(!current || d < distanceSq) { + current = &*t; + distanceSq = d; + } + } + + return current; +} diff --git a/BSPTree.h b/BSPTree.h new file mode 100644 index 0000000..c005507 --- /dev/null +++ b/BSPTree.h @@ -0,0 +1,132 @@ +#ifndef _BSPTREE_H_ +#define _BSPTREE_H_ + +#include "Triangle.h" +#include +#include +#include + +class BSPTree { + private: + class Plane { + public: + Plane() : d(0) {} + Plane(const vmml::vec3f &n, float d0) : normal(n), d(d0) {} + Plane(const Triangle &t) : normal(t.getNormal()), d(t.getVertex(0).dot(normal)) {} + + bool contains(const vmml::vec3f &v) const { + return (fabsf(normal.dot(v) - d) < 1E-6); + } + + bool isBehind(const vmml::vec3f &v) const { + return (normal.dot(v) - d) < 0; + } + + bool isInFront(const vmml::vec3f &v) const { + return (normal.dot(v) - d) > 0; + } + + + bool contains(const Triangle &t) const { + for(int i = 0; i < 3; ++i) { + if(!contains(t.getVertex(i))) + return false; + } + + return true; + } + + bool isBehind(const Triangle &t) const { + for(int i = 0; i < 3; ++i) { + if(!isBehind(t.getVertex(i)) && !contains(t.getVertex(i))) + return false; + } + + return true; + } + + bool isInFront(const Triangle &t) const { + for(int i = 0; i < 3; ++i) { + if(!isInFront(t.getVertex(i)) && !contains(t.getVertex(i))) + return false; + } + + return true; + } + + + const vmml::vec3f& getNormal() const { + return normal; + } + + vmml::vec3f intersection(const vmml::vec3f &p, const vmml::vec3f &dir) const; + void partition(const Triangle &t, std::list *front, std::list *back) const; + + private: + vmml::vec3f normal; + float d; + }; + + public: + BSPTree(const std::list &triangles); + + BSPTree(const BSPTree &tree) : frontTree(0), backTree(0) { + *this = tree; + } + + virtual ~BSPTree() { + if(frontTree) + delete frontTree; + + if(backTree) + delete backTree; + } + + BSPTree& operator=(const BSPTree &tree); + + template + void visit(const T& visitor, const vmml::vec3f &p) { + doVisit(visitor, p); + } + + template + void visit(T& visitor, const vmml::vec3f &p) { + doVisit(visitor, p); + } + + private: + Plane plane; + std::list triangles; + BSPTree *frontTree, *backTree; + + template + void doVisit(T& visitor, const vmml::vec3f &p) { + if(plane.isBehind(p)) { + if(frontTree) + frontTree->visit(visitor, p); + + for(std::list::iterator t = triangles.begin(); t != triangles.end(); ++t) { + visitor(*t); + } + + if(backTree) + backTree->visit(visitor, p); + } + else { + if(backTree) + backTree->visit(visitor, p); + + for(std::list::iterator t = triangles.begin(); t != triangles.end(); ++t) { + visitor(*t); + } + + if(frontTree) + frontTree->visit(visitor, p); + } + } + + static vmml::vec3f findCenter(const std::list &triangles); + static const Triangle* findNearestTriangle(const std::list &triangles, const vmml::vec3f &v); +}; + +#endif /* _BSPTREE_H_ */ -- cgit v1.2.3