BSPTrees weiter aufbauen

7 files changed, 170 insertions, 33 deletions

diff --git a/BSPTree.cpp b/BSPTree.cpp
index b30c907..cb182a9 100644
--- a/BSPTree.cpp
+++ b/BSPTree.cpp
@@ -1,25 +1,79 @@
 #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;
+BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(0) {
+  if(triangles.empty())
+    return;
 
+  Vertex center = findCenter(triangles);
+  std::cout << "Center at (" << center.getX() << ", " << center.getY() << ", " << center.getZ() << ")" << std::endl;
 
+  const Triangle *planeT = findNearestTriangle(triangles, center);
+
+  plane = Plane(*planeT);
+  std::cout << "The plane normal is (" << plane.getNormal().getX() << ", " << plane.getNormal().getY() << ", " << plane.getNormal().getZ() << ")" << std::endl;
+
+  std::list<Triangle> front, back;
+
+  for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+    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::cout << "All in all: " << triangles.size() << " triangles" << std::endl;
+  std::cout << "Coplanar: " << this->triangles.size() << " triangles" << std::endl;
+  std::cout << "Front: " << front.size() << " triangles" << std::endl;
+  std::cout << "Back: " << back.size() << " triangles" << std::endl;
+
+  if(!front.empty())
+    frontTree = new BSPTree(front);
+
+  if(!back.empty())
+    backTree = new BSPTree(back);
 }
 
 
 Vertex BSPTree::findCenter(const std::list<Triangle> &triangles) {
-  Vector v;
+  Vertex v;
 
   for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
-    v += Vector(t->getCenter());
+    v += t->getCenter();
   }
 
   return v/triangles.size();
 }
 
 const Triangle* BSPTree::findNearestTriangle(const std::list<Triangle> &triangles, const Vertex &v) {
-  Triangle *current = 0;
-  float distance;
+  if(triangles.empty())
+    return 0;
+
+  std::list<Triangle>::const_iterator t = triangles.begin();
+
+  const Triangle *current = &*t;
+  float distanceSq = current->getCenter().distanceSq(v);
+
+  for(++t; t != triangles.end(); ++t) {
+    float d = t->getCenter().distanceSq(v);
+
+    if(d < distanceSq) {
+      current = &*t;
+      distanceSq = d;
+    }
+  }
+
+  Vertex tCenter = current->getCenter();
+  std::cout << "Nearest triangle center at (" << tCenter.getX() << ", " << tCenter.getY() << ", " << tCenter.getZ() << ")" << std::endl;
+  std::cout << "DistanceSq is " << distanceSq << std::endl;
+
+  return current;
 }
diff --git a/BSPTree.h b/BSPTree.h
index dc7e2df..78ec81f 100644
--- a/BSPTree.h
+++ b/BSPTree.h
@@ -11,15 +11,49 @@ class BSPTree {
       public:
         Plane() : d(0) {}
         Plane(const Vector &n, float d0) : normal(n), d(d0) {}
+        Plane(const Triangle &t) : normal(t.getNormal()), d(t.getVertex(0).dot(normal)) {}
 
-        bool contains(Vertex v) {
-          return (fabsf(normal.dot(Vector(v)) - d) < 1E-6);
+        bool contains(const Vertex &v) {
+          return (fabsf(normal.dot(v) - d) < 1E-6);
         }
 
-        bool isBehind(Vertex v) {
-          return (normal.dot(Vector(v)) - d) < 0;
+        bool isBehind(const Vertex &v) {
+          return (normal.dot(v) - d) < 0;
         }
 
+        bool isInFront(const Vertex &v) {
+          return (normal.dot(v) - d) > 0;
+        }
+
+
+        bool contains(const Triangle &t) {
+          for(int i = 0; i < 3; ++i) {
+            if(!contains(t.getVertex(i)))
+              return false;
+          }
+
+          return true;
+        }
+
+        bool isBehind(const Triangle &t) {
+          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) {
+          for(int i = 0; i < 3; ++i) {
+            if(!isInFront(t.getVertex(i)) && !contains(t.getVertex(i)))
+              return false;
+          }
+
+          return true;
+        }
+
+
         const Vector& getNormal() {
           return normal;
         }
@@ -31,6 +65,39 @@ class BSPTree {
 
   public:
     BSPTree(const std::list<Triangle> &triangles);
+    virtual ~BSPTree() {
+      if(frontTree)
+        delete frontTree;
+
+      if(backTree)
+        delete backTree;
+    }
+
+    template<typename T>
+    void visit(const 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);
+      }
+    }
 
     template<typename T>
     void visit(T& visitor, const Vector &v) {
diff --git a/DisplayClass.cpp b/DisplayClass.cpp
index cefa6ae..f320f3c 100644
--- a/DisplayClass.cpp
+++ b/DisplayClass.cpp
@@ -6,6 +6,11 @@
 #include "BSPTree.h"
 
 
+void DisplayClass::RenderVisitor::operator() (const Triangle &t) const {
+  t.render();
+}
+
+
 DisplayClass::DisplayClass() {
   static const float pos[5] = {-3.0, -2.0, 0.0, 2.0, 3.0};
 
@@ -78,10 +83,13 @@ void DisplayClass::renderScene(unsigned long delta)
 
   //glLoadIdentity();
 
+  BSPTree tree(triangles);
+
   glBegin(GL_TRIANGLES);
-  for(std::list<Triangle>::reverse_iterator t = triangles.rbegin(); t != triangles.rend(); ++t) {
+  /*for(std::list<Triangle>::reverse_iterator t = triangles.rbegin(); t != triangles.rend(); ++t) {
     t->render();
-  }
+  }*/
+  tree.visit(RenderVisitor(), Vector(0, 0, -1));
   glEnd();
   
   glFlush();
diff --git a/DisplayClass.h b/DisplayClass.h
index 51f8636..d297ca4 100644
--- a/DisplayClass.h
+++ b/DisplayClass.h
@@ -12,6 +12,10 @@ class DisplayClass
     void renderScene(unsigned long delta);
 
   private:
+    struct RenderVisitor {
+      void operator() (const Triangle &t) const;
+    };
+
     Cuboid cubes[5][5][5];

 };

 #endif /*_DISPLAYCLASS_H_*/
diff --git a/Triangle.h b/Triangle.h
index ddb9d97..1231ece 100644
--- a/Triangle.h
+++ b/Triangle.h
@@ -20,7 +20,7 @@ class Triangle
     const Vertex& getVertex(int i) const {return v[i];}
     const Color& getColor() const {return c;}
     
-    Vertex getNormal() const {
+    Vector getNormal() const {
       Vector v1 = v[0]-v[2];
       Vector v2 = v[0]-v[1];
 
@@ -54,7 +54,7 @@ class Triangle
     }
     
     Vertex getCenter() const {
-      return (Vector(v[0])+Vector(v[1])+Vector(v[2]))/3;
+      return (v[0]+v[1]+v[2])/3;
     }
 
   private:
diff --git a/Vector.h b/Vector.h
index f03c4b4..49a5597 100644
--- a/Vector.h
+++ b/Vector.h
@@ -1,14 +1,16 @@
 #ifndef _VECTOR_H_
 #define _VECTOR_H_
 
-#include "Vertex.h"
-#include <math.h>
+#include <cmath>
 
-class Vector : public Vertex {
+class Vector {
   public:
-    Vector(float x0 = 0, float y0 = 0, float z0 = 0) : Vertex(x0, y0, z0) {}
-    Vector(const Vertex &v) : Vertex(v) {}
+    Vector(float x0 = 0, float y0 = 0, float z0 = 0) : x(x0), y(y0), z(z0) {}
     
+    float getX() const {return x;}
+    float getY() const {return y;}
+    float getZ() const {return z;}
+
     Vector operator+(const Vector &v) const {
       return Vector(x+v.x, y+v.y, z+v.z);
     }
@@ -50,11 +52,10 @@ class Vector : public Vertex {
     Vector normalize() const {
       return *this/length();
     }
-};
 
-static inline Vector operator-(const Vertex &v1, const Vertex &v2) {
-  return Vector(v1.getX()-v2.getX(), v1.getY()-v2.getY(), v1.getZ()-v2.getZ());
-}
+  protected:
+    float x, y, z;
+};
 
 #endif /*_VECTOR_H_*/
 
diff --git a/Vertex.h b/Vertex.h
index 665430d..801d029 100644
--- a/Vertex.h
+++ b/Vertex.h
@@ -1,21 +1,24 @@
 #ifndef _VERTEX_H_
 #define _VERTEX_H_
 
-class Vertex
+#include "Vector.h"
+
+class Vertex : public Vector
 {
   public:
-    Vertex(float x0 = 0, float y0 = 0, float z0 = 0) : x(x0), y(y0), z(z0) {}
+    Vertex(float x0 = 0, float y0 = 0, float z0 = 0) : Vector(x0, y0, z0) {}
+    Vertex(const Vector &v) : Vector(v) {}
     
-    float getX() const {return x;}
-    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;
+      Vector delta = *this - v;
+
+      return delta.dot(delta);
+    }
+
+    Vector operator-(const Vertex &v) const {
+      return Vector(x-v.x, y-v.y, z-v.z);
     }
 
-  protected:
-    float x, y, z;
 };
 
 #endif /*_VERTEX_H_*/