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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
/***************************************************************************
OctTree.cpp - description
-------------------
begin : Sun Mar 19 2000
copyright : (C) 2000 by Henrik Enqvist
email : henqvist@excite.com
***************************************************************************/
#include <iostream>
#include "Private.h"
#include "OctTree.h"
#include "Group.h"
#include "CollisionBounds.h"
/* QuadTrees ignore Y axis */
OctTree::OctTree(int depth, float size, float x, float y, float z) {
// m_fR = (float)(rand())/RAND_MAX;
// m_fG = (float)(rand())/RAND_MAX;
// m_fB = (float)(rand())/RAND_MAX;
EmAssert(depth > 0, "Depth must be larger than 0");
EM_COUT("OctTree() size"<< size <<" pos "<< x <<" "<< y <<" "<< z << endl, 0);
m_vtx.x = x;
m_vtx.y = y;
m_vtx.z = z;
m_fSize = size;
if (depth > 1) {
#if EM_USE_QUADTREE
m_vOctTree.reserve(4);
#else
m_vOctTree.reserve(8);
#endif
}
this->split(depth-1);
}
OctTree::~OctTree() {
}
void OctTree::split(int depth) {
if (depth < 1) return;
EM_COUT("OctTree::split() "<< depth << endl, 0);
// TODO: Speed things up by allocating all octtrees as an array
// at the top octtree instead of allocating them one by one
for (int a=-1; a<2; a+=2) {
for (int b=-1; b<2; b+=2) {
#if EM_USE_QUADTREE
OctTree* ot =
new OctTree(depth, m_fSize*0.5, m_vtx.x + a*m_fSize*0.5, 0, m_vtx.z + b*m_fSize*0.5);
m_vOctTree.push_back(ot);
#else
for (int c=-1; c<2; c+=2) {
OctTree* ot =
new OctTree(depth, m_fSize*0.5, m_vtx.x + a*m_fSize*0.5,
m_vtx.y + b*m_fSize*0.5, m_vtx.z + c*m_fSize*0.5);
m_vOctTree.push_back(ot);
}
#endif
}
}
}
void OctTree::clear() {
m_vGroup.clear();
vector<OctTree*>::iterator iter = m_vOctTree.begin();
vector<OctTree*>::iterator end = m_vOctTree.end();
for (; iter != end; iter++) {
(*iter)->clear();
}
}
bool OctTree::insertGroup(Group * g) {
EmAssert(g != NULL, "OctTree::insertGroup() group NULL");
EmAssert(g->p_CollisionBounds, "OctTree::insertGroup() collisionbounds NULL");
if (this->surround(g->p_CollisionBounds)) {
// try to add the group to a child, exit if it was added
vector<OctTree*>::iterator iter = m_vOctTree.begin();
vector<OctTree*>::iterator end = m_vOctTree.end();
for ( ; iter != end; iter++) {
if ((*iter)->insertGroup(g)) {
return true;
}
}
// none of the children surrounded the group, insert it here
m_vGroup.push_back(g);
EM_COUT("OctTree() size " << m_vGroup.size(), 0);
return true;
}
return false;
}
bool OctTree::surround(CollisionBounds * cb) {
EmAssert(cb != NULL, "OctTree::surround() collisionbounds NULL");
// observe factor , loose octtrees if over 1.
#define FACTOR 1.5f
#if EM_USE_QUADTREE
if ((cb->m_vtxTrans.x + cb->m_fRadius) < (m_vtx.x + m_fSize*FACTOR) &&
(cb->m_vtxTrans.x - cb->m_fRadius) > (m_vtx.x - m_fSize*FACTOR) &&
(cb->m_vtxTrans.z + cb->m_fRadius) < (m_vtx.z + m_fSize*FACTOR) &&
(cb->m_vtxTrans.z - cb->m_fRadius) > (m_vtx.z - m_fSize*FACTOR)) {
return true;
}
#else
if ((cb->m_vtxTrans.x + cb->m_fRadius) < (m_vtx.x + m_fSize*FACTOR) &&
(cb->m_vtxTrans.x - cb->m_fRadius) > (m_vtx.x - m_fSize*FACTOR) &&
(cb->m_vtxTrans.y + cb->m_fRadius) < (m_vtx.y + m_fSize*FACTOR) &&
(cb->m_vtxTrans.y - cb->m_fRadius) > (m_vtx.y - m_fSize*FACTOR) &&
(cb->m_vtxTrans.z + cb->m_fRadius) < (m_vtx.z + m_fSize*FACTOR) &&
(cb->m_vtxTrans.z - cb->m_fRadius) > (m_vtx.z - m_fSize*FACTOR)) {
return true;
}
#endif
return false;
}
bool OctTree::collide(CollisionBounds * cb) {
EmAssert(cb != NULL, "OctTree::surround() collisionbounds NULL");
// observe factor , loose octtrees if over 1.
#if EM_USE_QUADTREE
if ((cb->m_vtxTrans.x - cb->m_fRadius) < (m_vtx.x + m_fSize*FACTOR) &&
(cb->m_vtxTrans.x + cb->m_fRadius) > (m_vtx.x - m_fSize*FACTOR) &&
(cb->m_vtxTrans.z - cb->m_fRadius) < (m_vtx.z + m_fSize*FACTOR) &&
(cb->m_vtxTrans.z + cb->m_fRadius) > (m_vtx.z - m_fSize*FACTOR)) {
return true;
}
#else
if ((cb->m_vtxTrans.x - cb->m_fRadius) < (m_vtx.x + m_fSize*FACTOR) &&
(cb->m_vtxTrans.x + cb->m_fRadius) > (m_vtx.x - m_fSize*FACTOR) &&
(cb->m_vtxTrans.y - cb->m_fRadius) < (m_vtx.y + m_fSize*FACTOR) &&
(cb->m_vtxTrans.y + cb->m_fRadius) > (m_vtx.y - m_fSize*FACTOR) &&
(cb->m_vtxTrans.z - cb->m_fRadius) < (m_vtx.z + m_fSize*FACTOR) &&
(cb->m_vtxTrans.z + cb->m_fRadius) > (m_vtx.z - m_fSize*FACTOR)) {
return true;
}
#endif
#undef FACTOR
return false;
}
void OctTree::printTree(int depth) {
for (int a=0; a<depth; a++) {
cerr << " ";
}
cerr << "T: " << m_vGroup.size() << endl;
vector<OctTree*>::iterator iter = m_vOctTree.begin();
vector<OctTree*>::iterator end = m_vOctTree.end();
for (; iter != end; iter++) {
(*iter)->printTree(depth+1);
}
}
|
