00001
00002
00003 #include "Quadtree.h"
00004
00005 #include "AABB.h"
00006 #include "CoreEngine.h"
00007 #include "Frustum.h"
00008 #include "Mesh.h"
00009 #include "MeshModel.h"
00010 #include "OcclusionQuery.h"
00011 #include "World.h"
00012
00013
00014 namespace pge {
00015
00016
00017
00018
00019
00020
00021 QuadtreeNode::QuadtreeNode(AABB *boundingBox, int minMeshsPerNode, bool occlusionCulling) {
00022 int i;
00023
00024
00025 m_boundingBox = boundingBox;
00026 m_minMeshsPerNode = minMeshsPerNode;
00027 m_occlusionCulling = occlusionCulling;
00028
00029 m_meshs = new std::vector<Mesh*>();
00030
00031 m_nodes = new QuadtreeNode*[4];
00032
00033 for(i = 0; i < 4; i++) {
00034 m_nodes[i] = NULL;
00035 }
00036 }
00037
00038
00039
00040
00041
00042
00043
00044 QuadtreeNode::~QuadtreeNode(void) {
00045 int i;
00046
00047
00048 if(m_boundingBox != NULL) {
00049 delete m_boundingBox;
00050 m_boundingBox = NULL;
00051 }
00052
00053 if(m_meshs != NULL) {
00054 delete m_meshs;
00055 m_meshs = NULL;
00056 }
00057
00058 for(i = 0; i < 4; i++) {
00059 if(m_nodes[i] != NULL) {
00060 delete m_nodes[i];
00061 m_nodes[i] = NULL;
00062 }
00063 }
00064 }
00065
00066
00067
00068
00069
00070
00071
00072 void QuadtreeNode::initRootNode(std::vector<Mesh*> *meshs) {
00073 if(meshs != NULL) {
00074 subdivide(*meshs);
00075 }
00076 }
00077
00078
00079
00080
00081
00082
00083
00084 int QuadtreeNode::getMeshNum(void) {
00085 return (int)m_meshs->size();
00086 }
00087
00088
00089
00090
00091
00092
00093
00094 void QuadtreeNode::render(void) {
00095 int i;
00096 bool visible = true;
00097 std::vector<Mesh*>::iterator it;
00098
00099
00100
00101 if(CoreEngine::getInstance()->getCurrentWorld()->getFrustum()->isAABBInside(m_boundingBox)) {
00102
00103
00104
00105
00106
00107 if(!m_occlusionCulling) {
00108 visible = true;
00109 } else {
00110 if(occlusionquery::occlusionQuery(m_boundingBox) > 0) {
00111 visible = true;
00112 } else {
00113 visible = false;
00114
00115 }
00116 }
00117
00118 if(visible) {
00119 for(it = m_meshs->begin(); it != m_meshs->end(); it++) {
00120 Mesh *mesh = *it;
00121
00122 if(CoreEngine::getInstance()->getCurrentWorld()->getFrustum()->isAABBInside(mesh->getBoundingBox())) {
00123 mesh->render();
00124
00125
00126 }
00127 }
00128
00129 for(i = 0; i < 4; i++) {
00130 if(m_nodes[i] != NULL) {
00131 m_nodes[i]->render();
00132 }
00133 }
00134 }
00135 }
00136 }
00137
00138
00139
00140
00141
00142
00143
00144 void QuadtreeNode::renderWireframe(void) {
00145 int i;
00146
00147
00148 m_boundingBox->renderWireframe(Vector3f(1.0f, 0.0f, 0.0f));
00149
00150 for(i = 0; i < 4; i++) {
00151 if(m_nodes[i] != NULL) {
00152 m_nodes[i]->renderWireframe();
00153 }
00154 }
00155 }
00156
00157
00158
00159
00160
00161
00162
00163 void QuadtreeNode::subdivide(std::vector<Mesh*> meshs) {
00164 AABB boundingBoxes[4];
00165 std::vector<Mesh*> meshLists[4];
00166 float halfX;
00167 float halfZ;
00168 int i;
00169 bool meshDone;
00170 std::vector<Mesh*>::iterator it;
00171
00172
00173 halfX = (m_boundingBox->m_maxX - m_boundingBox->m_minX) / 2.0f;
00174 halfZ = (m_boundingBox->m_maxZ - m_boundingBox->m_minZ) / 2.0f;
00175
00176
00177
00178 boundingBoxes[QUADTREE_NODE_MINX_MINZ] = AABB(m_boundingBox->m_minX, m_boundingBox->m_minY,
00179 m_boundingBox->m_minZ, m_boundingBox->m_minX + halfX, m_boundingBox->m_maxY,
00180 m_boundingBox->m_minZ + halfZ);
00181
00182 boundingBoxes[QUADTREE_NODE_MAXX_MINZ] = AABB(m_boundingBox->m_minX + halfX,
00183 m_boundingBox->m_minY, m_boundingBox->m_minZ, m_boundingBox->m_maxX,
00184 m_boundingBox->m_maxY, m_boundingBox->m_minZ + halfZ);
00185
00186
00187 boundingBoxes[QUADTREE_NODE_MINX_MAXZ] = AABB(m_boundingBox->m_minX, m_boundingBox->m_minY,
00188 m_boundingBox->m_minZ + halfZ, m_boundingBox->m_minX + halfX, m_boundingBox->m_maxY,
00189 m_boundingBox->m_maxZ);
00190
00191 boundingBoxes[QUADTREE_NODE_MAXX_MAXZ] = AABB(m_boundingBox->m_minX + halfX,
00192 m_boundingBox->m_minY, m_boundingBox->m_minZ + halfZ, m_boundingBox->m_maxX,
00193 m_boundingBox->m_maxY, m_boundingBox->m_maxZ);
00194
00195
00196
00197 for(it = meshs.begin(); it != meshs.end(); it++) {
00198
00199
00200 Mesh *mesh = *it;
00201
00202 meshDone = false;
00203
00204
00205 for(i = 0; (i < 4) && !meshDone; i++) {
00206
00207
00208 if(boundingBoxes[i].isAABBCompletelyInside(mesh->getBoundingBox())) {
00209
00210
00211 if(m_nodes[i] == NULL) {
00212
00213 m_nodes[i] = new QuadtreeNode(new AABB(boundingBoxes[i]), m_minMeshsPerNode, m_occlusionCulling);
00214
00215
00216
00217 }
00218
00219
00220
00221 meshLists[i].push_back(mesh);
00222
00223
00224 meshDone = true;
00225 }
00226 }
00227
00228
00229
00230 if(!meshDone) {
00231 addMesh(mesh);
00232 }
00233 }
00234
00235
00236 for(i = 0; i < 4; i++) {
00237 if(m_nodes[i] != NULL) {
00238 if(meshLists[i].size() >= m_minMeshsPerNode) {
00239
00240 m_nodes[i]->subdivide(meshLists[i]);
00241 } else {
00242
00243
00244 m_nodes[i]->addMeshs(&meshLists[i]);
00245 }
00246 }
00247 }
00248 }
00249
00250
00251
00252
00253
00254
00255
00256 void QuadtreeNode::addMesh(Mesh *mesh) {
00257 m_meshs->push_back(mesh);
00258 }
00259
00260
00261
00262
00263
00264
00265
00266 void QuadtreeNode::addMeshs(std::vector<Mesh*> *meshs) {
00267 std::vector<Mesh*>::iterator it;
00268
00269
00270 for(it = meshs->begin(); it != meshs->end(); it++) {
00271 addMesh(*it);
00272 }
00273 }
00274
00275
00276
00277
00278
00279
00280
00281 Quadtree::Quadtree(MeshModel *model, int minMeshsPerNode, bool occlusionCulling) {
00282 m_model = model;
00283 m_root = NULL;
00284 m_minMeshsPerNode = minMeshsPerNode;
00285 m_occlusionCulling = occlusionCulling;
00286 }
00287
00288
00289
00290
00291
00292
00293
00294 Quadtree::~Quadtree(void) {
00295 if(m_root != NULL) {
00296 delete m_root;
00297 m_root = NULL;
00298 }
00299 if(m_model != NULL) {
00300 delete m_model;
00301 m_model = NULL;
00302 }
00303 }
00304
00305
00306
00307
00308
00309
00310
00311 bool Quadtree::init(void) {
00312 if(m_model != NULL) {
00313 m_model->init();
00314 m_root = new QuadtreeNode(new AABB(*m_model->getBoundingBox()), m_minMeshsPerNode, m_occlusionCulling);
00315 m_root->initRootNode(m_model->getMeshs());
00316
00317 return true;
00318 }
00319 return false;
00320 }
00321
00322
00323
00324
00325
00326
00327
00328 void Quadtree::render(void) {
00329 m_root->render();
00330
00331 }
00332
00333
00334
00335
00336
00337
00338
00339 void Quadtree::timer(unsigned int delay) {
00340 m_model->timer(delay);
00341 }
00342 };