00001
00002
00003 #include "Octree.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 OctreeNode::OctreeNode(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 OctreeNode*[8];
00032
00033 for(i = 0; i < 8; i++) {
00034 m_nodes[i] = NULL;
00035 }
00036 }
00037
00038
00039
00040
00041
00042
00043
00044 OctreeNode::~OctreeNode(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 < 8; 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 OctreeNode::initRootNode(std::vector<Mesh*> *meshs) {
00073 if(meshs != NULL) {
00074 subdivide(*meshs);
00075 }
00076 }
00077
00078
00079
00080
00081
00082
00083
00084 int OctreeNode::getMeshNum(void) {
00085 return (int)m_meshs->size();
00086 }
00087
00088
00089
00090
00091
00092
00093
00094 void OctreeNode::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 < 8; 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 OctreeNode::renderWireframe(void) {
00145 int i;
00146
00147
00148 m_boundingBox->renderWireframe(Vector3f(1.0f, 0.0f, 0.0f));
00149
00150 for(i = 0; i < 8; i++) {
00151 if(m_nodes[i] != NULL) {
00152 m_nodes[i]->renderWireframe();
00153 }
00154 }
00155 }
00156
00157
00158
00159
00160
00161
00162
00163 void OctreeNode::subdivide(std::vector<Mesh*> meshs) {
00164 AABB boundingBoxes[8];
00165 std::vector<Mesh*> meshLists[8];
00166 float halfX;
00167 float halfY;
00168 float halfZ;
00169 int i;
00170 bool meshDone;
00171 std::vector<Mesh*>::iterator it;
00172
00173
00174 halfX = (m_boundingBox->m_maxX - m_boundingBox->m_minX) / 2.0f;
00175 halfY = (m_boundingBox->m_maxY - m_boundingBox->m_minY) / 2.0f;
00176 halfZ = (m_boundingBox->m_maxZ - m_boundingBox->m_minZ) / 2.0f;
00177
00178
00179
00180 boundingBoxes[OCTREE_NODE_MINX_MINY_MINZ] = AABB(m_boundingBox->m_minX,
00181 m_boundingBox->m_minY, m_boundingBox->m_minZ, m_boundingBox->m_minX + halfX,
00182 m_boundingBox->m_minY + halfY, m_boundingBox->m_minZ + halfZ);
00183
00184 boundingBoxes[OCTREE_NODE_MAXX_MINY_MINZ] = AABB(m_boundingBox->m_minX + halfX,
00185 m_boundingBox->m_minY, m_boundingBox->m_minZ, m_boundingBox->m_maxX,
00186 m_boundingBox->m_minY + halfY, m_boundingBox->m_minZ + halfZ);
00187
00188 boundingBoxes[OCTREE_NODE_MINX_MAXY_MINZ] = AABB(m_boundingBox->m_minX, m_boundingBox->m_minY
00189 + halfY, m_boundingBox->m_minZ, m_boundingBox->m_minX + halfX, m_boundingBox->m_maxY,
00190 m_boundingBox->m_minZ + halfZ);
00191
00192 boundingBoxes[OCTREE_NODE_MAXX_MAXY_MINZ] = AABB(m_boundingBox->m_minX + halfX,
00193 m_boundingBox->m_minY + halfY, m_boundingBox->m_minZ, m_boundingBox->m_maxX,
00194 m_boundingBox->m_maxY, m_boundingBox->m_minZ + halfZ);
00195
00196
00197 boundingBoxes[OCTREE_NODE_MINX_MINY_MAXZ] = AABB(m_boundingBox->m_minX,
00198 m_boundingBox->m_minY, m_boundingBox->m_minZ + halfZ, m_boundingBox->m_minX + halfX,
00199 m_boundingBox->m_minY + halfY, m_boundingBox->m_maxZ);
00200
00201 boundingBoxes[OCTREE_NODE_MAXX_MINY_MAXZ] = AABB(m_boundingBox->m_minX + halfX,
00202 m_boundingBox->m_minY, m_boundingBox->m_minZ + halfZ, m_boundingBox->m_maxX,
00203 m_boundingBox->m_minY + halfY, m_boundingBox->m_maxZ);
00204
00205 boundingBoxes[OCTREE_NODE_MINX_MAXY_MAXZ] = AABB(m_boundingBox->m_minX, m_boundingBox->m_minY
00206 + halfY, m_boundingBox->m_minZ + halfZ, m_boundingBox->m_minX + halfX,
00207 m_boundingBox->m_maxY, m_boundingBox->m_maxZ);
00208
00209 boundingBoxes[OCTREE_NODE_MAXX_MAXY_MAXZ] = AABB(m_boundingBox->m_minX + halfX,
00210 m_boundingBox->m_minY + halfY, m_boundingBox->m_minZ + halfZ, m_boundingBox->m_maxX,
00211 m_boundingBox->m_maxY, m_boundingBox->m_maxZ);
00212
00213
00214
00215
00216 for(it = meshs.begin(); it != meshs.end(); it++) {
00217
00218
00219 Mesh *mesh = *it;
00220
00221 meshDone = false;
00222
00223
00224 for(i = 0; (i < 8) && !meshDone; i++) {
00225
00226
00227 if(boundingBoxes[i].isAABBCompletelyInside(mesh->getBoundingBox())) {
00228
00229
00230 if(m_nodes[i] == NULL) {
00231
00232 m_nodes[i] = new OctreeNode(new AABB(boundingBoxes[i]), m_minMeshsPerNode, m_occlusionCulling);
00233
00234
00235
00236 }
00237
00238
00239
00240 meshLists[i].push_back(mesh);
00241
00242
00243 meshDone = true;
00244 }
00245 }
00246
00247
00248
00249 if(!meshDone) {
00250 addMesh(mesh);
00251 }
00252 }
00253
00254
00255 for(i = 0; i < 8; i++) {
00256 if(m_nodes[i] != NULL) {
00257 if(meshLists[i].size() >= m_minMeshsPerNode) {
00258
00259 m_nodes[i]->subdivide(meshLists[i]);
00260 } else {
00261
00262
00263 m_nodes[i]->addMeshs(&meshLists[i]);
00264 }
00265 }
00266 }
00267 }
00268
00269
00270
00271
00272
00273
00274
00275 void OctreeNode::addMesh(Mesh *mesh) {
00276 m_meshs->push_back(mesh);
00277 }
00278
00279
00280
00281
00282
00283
00284
00285 void OctreeNode::addMeshs(std::vector<Mesh*> *meshs) {
00286 std::vector<Mesh*>::iterator it;
00287
00288
00289 for(it = meshs->begin(); it != meshs->end(); it++) {
00290 addMesh(*it);
00291 }
00292 }
00293
00294
00295
00296
00297
00298
00299
00300 Octree::Octree(MeshModel *model, int minMeshsPerNode, bool occlusionCulling) {
00301 m_model = model;
00302 m_root = NULL;
00303 m_minMeshsPerNode = minMeshsPerNode;
00304 m_occlusionCulling = occlusionCulling;
00305 }
00306
00307
00308
00309
00310
00311
00312
00313 Octree::~Octree(void) {
00314 if(m_root != NULL) {
00315 delete m_root;
00316 m_root = NULL;
00317 }
00318 if(m_model != NULL) {
00319 delete m_model;
00320 m_model = NULL;
00321 }
00322 }
00323
00324
00325
00326
00327
00328
00329
00330 bool Octree::init(void) {
00331 if(m_model != NULL) {
00332 m_model->init();
00333 m_root = new OctreeNode(new AABB(*m_model->getBoundingBox()), m_minMeshsPerNode, m_occlusionCulling);
00334 m_root->initRootNode(m_model->getMeshs());
00335
00336 return true;
00337 }
00338 return false;
00339 }
00340
00341
00342
00343
00344
00345
00346
00347 void Octree::render(void) {
00348 m_root->render();
00349
00350 }
00351
00352
00353
00354
00355
00356
00357
00358 void Octree::timer(unsigned int delay) {
00359 m_model->timer(delay);
00360 }
00361 };