diff options
| -rw-r--r-- | BSPTree.cpp | 68 | ||||
| -rw-r--r-- | BSPTree.h | 75 | ||||
| -rw-r--r-- | DisplayClass.cpp | 12 | ||||
| -rw-r--r-- | DisplayClass.h | 4 | ||||
| -rw-r--r-- | Triangle.h | 4 | ||||
| -rw-r--r-- | Vector.h | 19 | ||||
| -rw-r--r-- | Vertex.h | 21 |
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; } @@ -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_*/ @@ -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: @@ -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_*/ @@ -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_*/ |