summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--BSPTree.cpp68
-rw-r--r--BSPTree.h75
-rw-r--r--DisplayClass.cpp12
-rw-r--r--DisplayClass.h4
-rw-r--r--Triangle.h4
-rw-r--r--Vector.h19
-rw-r--r--Vertex.h21
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_*/