1 files changed, 107 insertions, 9 deletions

diff --git a/BSPTree.cpp b/BSPTree.cpp
index b30c907..00e916b 100644
--- a/BSPTree.cpp
+++ b/BSPTree.cpp
@@ -1,25 +1,123 @@
 #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;
+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<Triangle> *front, std::list<Triangle> *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;
+    }
+  }
 }
 
 
-Vertex BSPTree::findCenter(const std::list<Triangle> &triangles) {
-  Vector v;
+BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(0) {
+  if(triangles.empty())
+    return;
+
+  const Triangle *planeT = findNearestTriangle(triangles, findCenter(triangles));
+
+  plane = Plane(*planeT);
+
+  std::list<Triangle> front, back;
 
   for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
-    v += Vector(t->getCenter());
+    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<Triangle> 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);
+}
+
+
+vmml::vec3f BSPTree::findCenter(const std::list<Triangle> &triangles) {
+  vmml::vec3f v;
+
+  for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+    v += t->getCenter();
   }
 
   return v/triangles.size();
 }
 
-const Triangle* BSPTree::findNearestTriangle(const std::list<Triangle> &triangles, const Vertex &v) {
-  Triangle *current = 0;
-  float distance;
+const Triangle* BSPTree::findNearestTriangle(const std::list<Triangle> &triangles, const vmml::vec3f &v) {
+  if(triangles.empty())
+    return 0;
+
+  std::list<Triangle>::const_iterator t = triangles.begin();
+
+  const Triangle *current = &*t;
+  float distanceSq = current->getCenter().squared_distance(v);
+
+  for(++t; t != triangles.end(); ++t) {
+    float d = t->getCenter().squared_distance(v);
+
+    if(d < distanceSq) {
+      current = &*t;
+      distanceSq = d;
+    }
+  }
+
+  return current;
 }