summaryrefslogtreecommitdiffstats
path: root/BSPTree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'BSPTree.cpp')
-rw-r--r--BSPTree.cpp83
1 files changed, 49 insertions, 34 deletions
diff --git a/BSPTree.cpp b/BSPTree.cpp
index fa2f1c0..a94c77a 100644
--- a/BSPTree.cpp
+++ b/BSPTree.cpp
@@ -1,5 +1,23 @@
-#include "BSPTree.h"
+/*
+ * BSPTree.cpp
+ *
+ * Copyright (C) 2009 Matthias Schiffer <matthias@gamezock.de>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License along
+ * with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+#include "BSPTree.h"
namespace Zoom {
@@ -9,20 +27,20 @@ vmml::vec3f BSPTree::Plane::intersection(const vmml::vec3f &p, const vmml::vec3f
return p + r*dir;
}
-void BSPTree::Plane::partition(const Triangle &t, std::list<Triangle> *front, std::list<Triangle> *back) const {
+void BSPTree::Plane::partition(const TriangleRecord &t, std::list<TriangleRecord> *front, std::list<TriangleRecord> *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)};
+ if(contains(t.triangle.getVertex(i))) {
+ const vmml::vec3f *v[3] = {&t.triangle.getVertex(i), &t.triangle.getVertex((i+1)%3), &t.triangle.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()));
+ front->push_back(TriangleRecord(Triangle(*v[0], *v[1], is, t.triangle.getColor()), t.data));
+ back->push_back(TriangleRecord(Triangle(*v[0], is, *v[2], t.triangle.getColor()), t.data));
}
else {
- back->push_back(Triangle(*v[0], *v[1], is, t.getColor()));
- front->push_back(Triangle(*v[0], is, *v[2], t.getColor()));
+ back->push_back(TriangleRecord(Triangle(*v[0], *v[1], is, t.triangle.getColor()), t.data));
+ front->push_back(TriangleRecord(Triangle(*v[0], is, *v[2], t.triangle.getColor()), t.data));
}
return;
@@ -30,7 +48,7 @@ void BSPTree::Plane::partition(const Triangle &t, std::list<Triangle> *front, st
}
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)};
+ const vmml::vec3f *v[3] = {&t.triangle.getVertex(i), &t.triangle.getVertex((i+1)%3), &t.triangle.getVertex((i+2)%3)};
if((isInFront(*v[0]) && isBehind(*v[1]) && isBehind(*v[2]))
|| (isBehind(*v[0]) && isInFront(*v[1]) && isInFront(*v[2]))) {
@@ -38,14 +56,14 @@ void BSPTree::Plane::partition(const Triangle &t, std::list<Triangle> *front, st
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()));
+ front->push_back(TriangleRecord(Triangle(*v[0], is1, is2, t.triangle.getColor()), t.data));
+ back->push_back(TriangleRecord(Triangle(is1, *v[1], is2, t.triangle.getColor()), t.data));
+ back->push_back(TriangleRecord(Triangle(*v[1], *v[2], is2, t.triangle.getColor()), t.data));
}
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()));
+ back->push_back(TriangleRecord(Triangle(*v[0], is1, is2, t.triangle.getColor()), t.data));
+ front->push_back(TriangleRecord(Triangle(is1, *v[1], is2, t.triangle.getColor()), t.data));
+ front->push_back(TriangleRecord(Triangle(*v[1], *v[2], is2, t.triangle.getColor()), t.data));
}
return;
@@ -54,7 +72,7 @@ void BSPTree::Plane::partition(const Triangle &t, std::list<Triangle> *front, st
}
-BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(0) {
+BSPTree::BSPTree(const std::list<TriangleRecord> &triangles) : frontTree(0), backTree(0) {
const Triangle *planeT = findNearestTriangle(triangles, findCenter(triangles));
if(!planeT)
@@ -62,29 +80,26 @@ BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(
plane = Plane(*planeT);
- std::list<Triangle> front, back;
+ std::list<TriangleRecord> front, back;
- for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
- if(t->getNormal().squared_length() == 0)
+ for(std::list<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+ if(t->triangle.isDegenerate())
continue;
- if(plane.contains(*t)) {
+ if(plane.contains(t->triangle)) {
this->triangles.push_back(*t);
continue;
}
- else if(plane.isInFront(*t)) {
+ else if(plane.isInFront(t->triangle)) {
front.push_back(*t);
continue;
}
- else if(plane.isBehind(*t)) {
+ else if(plane.isBehind(t->triangle)) {
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);
+ plane.partition(*t, &front, &back);
}
if(!front.empty())
@@ -117,28 +132,28 @@ BSPTree& BSPTree::operator=(const BSPTree &tree) {
return *this;
}
-vmml::vec3f BSPTree::findCenter(const std::list<Triangle> &triangles) {
+vmml::vec3f BSPTree::findCenter(const std::list<TriangleRecord> &triangles) {
vmml::vec3f v;
- for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
- v += t->getCenter();
+ for(std::list<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+ v += t->triangle.getCenter();
}
return v/triangles.size();
}
-const Triangle* BSPTree::findNearestTriangle(const std::list<Triangle> &triangles, const vmml::vec3f &v) {
+const Triangle* BSPTree::findNearestTriangle(const std::list<TriangleRecord> &triangles, const vmml::vec3f &v) {
const Triangle *current = 0;
float distanceSq;
- for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
- if(t->getNormal().squared_length() == 0)
+ for(std::list<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+ if(t->triangle.isDegenerate())
continue;
- float d = t->getCenter().squared_distance(v);
+ float d = t->triangle.getCenter().squared_distance(v);
if(!current || d < distanceSq) {
- current = &*t;
+ current = &t->triangle;
distanceSq = d;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-03 09:50:02 +0200