BSPTrees angefangen

1 files changed, 58 insertions, 0 deletions

diff --git a/BSPTree.h b/BSPTree.h
index 345f143..dc7e2df 100644
--- a/BSPTree.h
+++ b/BSPTree.h
@@ -3,10 +3,68 @@
 
 #include "Triangle.h"
 #include <list>
+#include <cmath>
 
 class BSPTree {
   private:
+    class Plane {
+      public:
+        Plane() : d(0) {}
+        Plane(const Vector &n, float d0) : normal(n), d(d0) {}
 
+        bool contains(Vertex v) {
+          return (fabsf(normal.dot(Vector(v)) - d) < 1E-6);
+        }
+
+        bool isBehind(Vertex v) {
+          return (normal.dot(Vector(v)) - d) < 0;
+        }
+
+        const Vector& getNormal() {
+          return normal;
+        }
+
+      private:
+        Vector normal;
+        float d;
+    };
+
+  public:
+    BSPTree(const std::list<Triangle> &triangles);
+
+    template<typename T>
+    void visit(T& visitor, const Vector &v) {
+      if(plane.getNormal().dot(v) > 0) {
+        if(frontTree)
+          frontTree->visit(visitor, v);
+
+        for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
+          visitor(*t);
+        }
+
+        if(backTree)
+          backTree->visit(visitor, v);
+      }
+      else {
+        if(backTree)
+          backTree->visit(visitor, v);
+
+        for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
+          visitor(*t);
+        }
+
+        if(frontTree)
+          frontTree->visit(visitor, v);
+      }
+    }
+
+  private:
+    Plane plane;
+    std::list<Triangle> triangles;
+    BSPTree *frontTree, *backTree;
+
+    static Vertex findCenter(const std::list<Triangle> &triangles);
+    static const Triangle* findNearestTriangle(const std::list<Triangle> &triangles, const Vertex &v);
 };
 
 #endif /* _BSPTREE_H_ */