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
124
125
|
#ifndef _BSPTREE_H_
#define _BSPTREE_H_
#include "Triangle.h"
#include <list>
#include <cmath>
#include <vmmlib/vector.hpp>
class BSPTree {
private:
class Plane {
public:
Plane() : d(0) {}
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) const {
return (fabsf(normal.dot(v) - d) < 1E-6);
}
bool isBehind(const vmml::vec3f &v) const {
return (normal.dot(v) - d) < 0;
}
bool isInFront(const vmml::vec3f &v) const {
return (normal.dot(v) - d) > 0;
}
bool contains(const Triangle &t) const {
for(int i = 0; i < 3; ++i) {
if(!contains(t.getVertex(i)))
return false;
}
return true;
}
bool isBehind(const Triangle &t) const {
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) const {
for(int i = 0; i < 3; ++i) {
if(!isInFront(t.getVertex(i)) && !contains(t.getVertex(i)))
return false;
}
return true;
}
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;
};
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 vmml::vec3f &p) {
doVisit<const T>(visitor, p);
}
template<typename T>
void visit(T& visitor, const vmml::vec3f &p) {
doVisit(visitor, p);
}
private:
Plane plane;
std::list<Triangle> triangles;
BSPTree *frontTree, *backTree;
template<typename T>
void doVisit(T& visitor, const vmml::vec3f &p) {
if(plane.isBehind(p)) {
if(frontTree)
frontTree->visit(visitor, p);
for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
visitor(*t);
}
if(backTree)
backTree->visit(visitor, p);
}
else {
if(backTree)
backTree->visit(visitor, p);
for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
visitor(*t);
}
if(frontTree)
frontTree->visit(visitor, p);
}
}
static vmml::vec3f findCenter(const std::list<Triangle> &triangles);
static const Triangle* findNearestTriangle(const std::list<Triangle> &triangles, const vmml::vec3f &v);
};
#endif /* _BSPTREE_H_ */
|
