From 4f2236f36446a5b097e28c0f76e4962ce7e115b1 Mon Sep 17 00:00:00 2001
From: Matthias Schiffer <matthias@gamezock.de>
Date: Thu, 10 Dec 2009 09:43:46 +0100
Subject: BSPTrees fertig

---
 BSPTree.cpp      | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 BSPTree.h        | 17 ++++++++++-------
 DisplayClass.cpp |  1 -
 Trapezocube.cpp  |  2 +-
 Triangle.h       |  1 +
 5 files changed, 69 insertions(+), 9 deletions(-)

diff --git a/BSPTree.cpp b/BSPTree.cpp
index e7e6416..00e916b 100644
--- a/BSPTree.cpp
+++ b/BSPTree.cpp
@@ -1,5 +1,57 @@
 #include "BSPTree.h"
 
+#include <iostream>
+
+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;
+    }
+  }
+}
+
 
 BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(0) {
   if(triangles.empty())
@@ -24,6 +76,11 @@ BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(
       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())
diff --git a/BSPTree.h b/BSPTree.h
index 4965318..a03327b 100644
--- a/BSPTree.h
+++ b/BSPTree.h
@@ -14,20 +14,20 @@ class BSPTree {
         Plane(const vmml::vec3f &n, float d0) : normal(n), d(d0) {}
         Plane(const Triangle &t) : normal(t.getNormal()), d(t.getVertex(0).dot(normal)) {}
 
-        bool contains(const vmml::vec3f &v) {
+        bool contains(const vmml::vec3f &v) const {
           return (fabsf(normal.dot(v) - d) < 1E-6);
         }
 
-        bool isBehind(const vmml::vec3f &v) {
+        bool isBehind(const vmml::vec3f &v) const {
           return (normal.dot(v) - d) < 0;
         }
 
-        bool isInFront(const vmml::vec3f &v) {
+        bool isInFront(const vmml::vec3f &v) const {
           return (normal.dot(v) - d) > 0;
         }
 
 
-        bool contains(const Triangle &t) {
+        bool contains(const Triangle &t) const {
           for(int i = 0; i < 3; ++i) {
             if(!contains(t.getVertex(i)))
               return false;
@@ -36,7 +36,7 @@ class BSPTree {
           return true;
         }
 
-        bool isBehind(const Triangle &t) {
+        bool isBehind(const Triangle &t) const {
           for(int i = 0; i < 3; ++i) {
             if(!isBehind(t.getVertex(i)) && !contains(t.getVertex(i)))
               return false;
@@ -45,7 +45,7 @@ class BSPTree {
           return true;
         }
 
-        bool isInFront(const Triangle &t) {
+        bool isInFront(const Triangle &t) const {
           for(int i = 0; i < 3; ++i) {
             if(!isInFront(t.getVertex(i)) && !contains(t.getVertex(i)))
               return false;
@@ -55,10 +55,13 @@ class BSPTree {
         }
 
 
-        const vmml::vec3f& getNormal() {
+        const vmml::vec3f& getNormal() const {
           return normal;
         }
 
+        vmml::vec3f intersection(const vmml::vec3f &p, const vmml::vec3f &dir) const;
+        void partition(const Triangle &t, std::list<Triangle> *front, std::list<Triangle> *back) const;
+
       private:
         vmml::vec3f normal;
         float d;
diff --git a/DisplayClass.cpp b/DisplayClass.cpp
index 206556e..69c4c17 100644
--- a/DisplayClass.cpp
+++ b/DisplayClass.cpp
@@ -1,6 +1,5 @@
 #include "DisplayClass.h"
 #include "gl.h"
-#include "Trapezocube.h"
 #include "BSPTree.h"
 
 
diff --git a/Trapezocube.cpp b/Trapezocube.cpp
index 271db7d..bfb82c3 100644
--- a/Trapezocube.cpp
+++ b/Trapezocube.cpp
@@ -7,7 +7,7 @@ std::list<Triangle> Trapezocube::getTriangles(/*const Matrix &modelview*/)
   // width, height, depth
 
   vmml::mat4f rotation(vmml::mat4f::IDENTITY);
-  rotation.rotate_y(rotate);
+  rotation.rotate_y(M_PI*rotate/180.0f);
 
   // Front face
   vmml::vec4f c(0.0, 0.0, 1.0, 0.5);
diff --git a/Triangle.h b/Triangle.h
index c053a8d..dc48071 100644
--- a/Triangle.h
+++ b/Triangle.h
@@ -8,6 +8,7 @@
 class Triangle
 {
   public:
+    Triangle() {}
     Triangle(const vmml::vec3f &v1, const vmml::vec3f &v2, const vmml::vec3f &v3, const vmml::vec4f &c0) : c(c0)
     {
       v[0] = v1;
-- 
cgit v1.2.3