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
|
/*
* BSPTree.h
*
* 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/>.
*/
#ifndef ZOOM_BSPTREE_H_
#define ZOOM_BSPTREE_H_
#include "Triangle.h"
#include "MathUtil.h"
#include <list>
#include <cmath>
#include <vmmlib/vector.hpp>
#include <boost/shared_ptr.hpp>
namespace Zoom {
class BSPTree {
public:
class TriangleData {
protected:
TriangleData() {}
public:
virtual ~TriangleData() {}
};
struct TriangleRecord {
public:
TriangleRecord(Triangle triangle0, boost::shared_ptr<TriangleData> data0)
: triangle(triangle0), data(data0) {}
TriangleRecord(Triangle triangle0) : triangle(triangle0) {}
TriangleRecord() {}
Triangle triangle;
boost::shared_ptr<TriangleData> data;
};
public:
BSPTree(const std::list<TriangleRecord> &triangles);
BSPTree(const BSPTree &tree) : frontTree(0), backTree(0) {
*this = tree;
}
virtual ~BSPTree() {
if(frontTree)
delete frontTree;
if(backTree)
delete backTree;
}
BSPTree& operator=(const BSPTree &tree);
template<typename T>
void visit(const T& visitor, const vmml::vec3f &p) const {
doVisit<const T>(visitor, p);
}
template<typename T>
void visit(T& visitor, const vmml::vec3f &p) const {
doVisit(visitor, p);
}
private:
MathUtil::Plane plane;
std::list<TriangleRecord> triangles;
BSPTree *frontTree, *backTree;
template<typename T>
void doVisit(T& visitor, const vmml::vec3f &p) const {
if(plane.isBehind(p)) {
if(frontTree)
frontTree->visit(visitor, p);
for(std::list<TriangleRecord>::const_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<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
visitor(*t);
}
if(frontTree)
frontTree->visit(visitor, p);
}
}
void partition(const TriangleRecord &t, std::list<TriangleRecord> *front, std::list<TriangleRecord> *back) const;
static vmml::vec3f findCenter(const std::list<TriangleRecord> &triangles);
static const Triangle* findNearestTriangle(const std::list<TriangleRecord> &triangles, const vmml::vec3f &v);
};
}
#endif /* ZOOM_BSPTREE_H_ */
|
