From 3035d4c9e76d6f28579d0b5a024e1c1b2a538919 Mon Sep 17 00:00:00 2001
From: Matthias Schiffer <matthias@gamezock.de>
Date: Wed, 9 Dec 2009 16:25:16 +0100
Subject: BSPTrees angefangen

---
 BSPGenerator.cpp |  2 --
 BSPGenerator.h   |  9 ---------
 BSPTree.cpp      | 25 ++++++++++++++++++++++++
 BSPTree.h        | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 CMakeLists.txt   |  3 +--
 DisplayClass.cpp |  5 ++++-
 Triangle.h       |  4 ++++
 Vector.h         |  8 ++++++++
 Vertex.h         |  4 ++++
 9 files changed, 104 insertions(+), 14 deletions(-)
 delete mode 100644 BSPGenerator.cpp
 delete mode 100644 BSPGenerator.h
 create mode 100644 BSPTree.cpp

diff --git a/BSPGenerator.cpp b/BSPGenerator.cpp
deleted file mode 100644
index a4cab6e..0000000
--- a/BSPGenerator.cpp
+++ /dev/null
@@ -1,2 +0,0 @@
-#include "BSPGenerator.h"
-
diff --git a/BSPGenerator.h b/BSPGenerator.h
deleted file mode 100644
index f6195e8..0000000
--- a/BSPGenerator.h
+++ /dev/null
@@ -1,9 +0,0 @@
-#ifndef _BSPGENERATOR_H_
-#define _BSPGENERATOR_H_
-
-class BSPGenerator {
-  public:
-
-};
-
-#endif /* _BSPGENERATOR_H_ */
diff --git a/BSPTree.cpp b/BSPTree.cpp
new file mode 100644
index 0000000..b30c907
--- /dev/null
+++ b/BSPTree.cpp
@@ -0,0 +1,25 @@
+#include "BSPTree.h"
+#include <iostream>
+
+BSPTree::BSPTree(const std::list<Triangle> &t) {
+  Vertex center = findCenter(t);
+  std::cout << "Center at (" << center.getX() << ", " << center.getY() << ", " << center.getZ() << std::endl;
+
+
+}
+
+
+Vertex BSPTree::findCenter(const std::list<Triangle> &triangles) {
+  Vector v;
+
+  for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+    v += Vector(t->getCenter());
+  }
+
+  return v/triangles.size();
+}
+
+const Triangle* BSPTree::findNearestTriangle(const std::list<Triangle> &triangles, const Vertex &v) {
+  Triangle *current = 0;
+  float distance;
+}
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_ */
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 1f656ee..de4bf01 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -6,8 +6,7 @@ find_package(OpenGL REQUIRED)
 include_directories(${OPENGL_INCLUDE_DIR})
 
 add_executable(c3d
-  BSPGenerator.cpp BSPGenerator.h
-  BSPTree.h
+  BSPTree.cpp BSPTree.h
   Color.h
   Cubehole.cpp Cubehole.h
   Cuboid.cpp Cuboid.h
diff --git a/DisplayClass.cpp b/DisplayClass.cpp
index 2741fce..5c97cc4 100644
--- a/DisplayClass.cpp
+++ b/DisplayClass.cpp
@@ -2,7 +2,8 @@
 #include "Matrix.h"
 #include "gl.h"
 #include <algorithm>
-#include "Trapezocube.h"
+#include "Trapezocube.h"
+#include "BSPTree.h"
 
 
 DisplayClass::DisplayClass() {
@@ -53,6 +54,8 @@ void DisplayClass::renderScene(unsigned long delta)
   }*/
   std::list<Triangle> ct = cubeing.getTriangles(m);
   triangles.splice(triangles.end(), ct);
+
+  BSPTree tree(triangles);
 
   glLoadIdentity();
 
diff --git a/Triangle.h b/Triangle.h
index 807b5b9..ab51051 100644
--- a/Triangle.h
+++ b/Triangle.h
@@ -36,6 +36,10 @@ class Triangle
       }
     }
     
+    Vertex getCenter() const {
+      return (Vector(v[0])+Vector(v[1])+Vector(v[2]))/3;
+    }
+
   private:
     Vertex v[3];
     Color c;
diff --git a/Vector.h b/Vector.h
index f884c49..ece1230 100644
--- a/Vector.h
+++ b/Vector.h
@@ -12,6 +12,14 @@ class Vector : public Vertex {
       return Vector(x+v.x, y+v.y, z+v.z);
     }
     
+    Vector& operator+=(const Vector &v) {
+      x += v.x;
+      y += v.y;
+      z += v.z;
+
+      return *this;
+    }
+
     Vector operator*(float f) const {
       return Vector(x*f, y*f, z*f);
     }
diff --git a/Vertex.h b/Vertex.h
index c82bd59..665430d 100644
--- a/Vertex.h
+++ b/Vertex.h
@@ -10,6 +10,10 @@ class Vertex
     float getY() const {return y;}
     float getZ() const {return z;}
 
+    float distanceSq(const Vertex &v) const {
+      return x*v.x + y*v.y + z*v.z;
+    }
+
   protected:
     float x, y, z;
 };
-- 
cgit v1.2.3