1 files changed, 177 insertions, 0 deletions
diff --git a/src/BSPTree.h b/src/BSPTree.h
new file mode 100644
index 0000000..1944ef1
--- /dev/null
+++ b/src/BSPTree.h
@@ -0,0 +1,177 @@
+/*
+ * BSPTree.h
+ *
+ * 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/>.
+ */
+
+#ifndef ZOOM_BSPTREE_H_
+#define ZOOM_BSPTREE_H_
+
+#include "Triangle.h"
+#include <list>
+#include <cmath>
+
+#include <vmmlib/vector.hpp>
+#include <boost/shared_ptr.hpp>
+
+namespace Zoom {
+
+class BSPTree {
+  public:
+    class TriangleData {
+      protected:
+      TriangleData() {}
+
+      public:
+      virtual ~TriangleData() {}
+    };
+
+    struct TriangleRecord {
+      public:
+        TriangleRecord(Triangle triangle0, boost::shared_ptr<TriangleData> data0)
+        : triangle(triangle0), data(data0) {}
+        TriangleRecord(Triangle triangle0) : triangle(triangle0) {}
+        TriangleRecord() {}
+
+        Triangle triangle;
+        boost::shared_ptr<TriangleData> data;
+    };
+
+  private:
+    class Plane {
+      public:
+        Plane() : d(0) {}
+        Plane(const vmml::vec3f &n, float d0) : normal(n), d(d0) {}
+        Plane(const Triangle &t) : normal(t.computeNormal()), 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 TriangleRecord &t, std::list<TriangleRecord> *front, std::list<TriangleRecord> *back) const;
+
+      private:
+        vmml::vec3f normal;
+        float d;
+    };
+
+  public:
+    BSPTree(const std::list<TriangleRecord> &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<typename T>
+    void visit(const T& visitor, const vmml::vec3f &p) const {
+      doVisit<const T>(visitor, p);
+    }
+
+    template<typename T>
+    void visit(T& visitor, const vmml::vec3f &p) const {
+      doVisit(visitor, p);
+    }
+
+  private:
+    Plane plane;
+    std::list<TriangleRecord> triangles;
+    BSPTree *frontTree, *backTree;
+
+    template<typename T>
+    void doVisit(T& visitor, const vmml::vec3f &p) const {
+      if(plane.isBehind(p)) {
+        if(frontTree)
+          frontTree->visit(visitor, p);
+
+        for(std::list<TriangleRecord>::const_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<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+          visitor(*t);
+        }
+
+        if(frontTree)
+          frontTree->visit(visitor, p);
+      }
+    }
+
+    static vmml::vec3f findCenter(const std::list<TriangleRecord> &triangles);
+    static const Triangle* findNearestTriangle(const std::list<TriangleRecord> &triangles, const vmml::vec3f &v);
+};
+
+}
+
+#endif /* ZOOM_BSPTREE_H_ */