1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#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())
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) {
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 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;
}
|
