Main Page | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals

/Users/blackie/Documents/myRepository/phobosengine-vc2005/phobosengine/phobosengine/Quadtree.cpp

Go to the documentation of this file.
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                 // Perform frustum culling.
00101                 if(CoreEngine::getInstance()->getCurrentWorld()->getFrustum()->isAABBInside(m_boundingBox)) {
00102 
00103                         // Add one visible octree node count.
00104                         //SceneAnalyseGUI.getInstance().addVisibleNodeCount(1);
00105 
00106                         // Perform occlusion culling if enabled.
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                                         //SceneAnalyseGUI.getInstance().addOcclusionCulledNodeCount(1);
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                                                 //SceneAnalyseGUI.getInstance().addVisibleTriangleCount(mesh.getTriangleNum());
00125                                                 //SceneAnalyseGUI.getInstance().addVisibleMeshCount(1);
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                 // Create the boxes.
00177                 // Boxes in the back (minZ).
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                 // Boxes in the front (maxZ).
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                 // Loop through the meshes of this node.
00196                 // These could be distributed to the new nodes.
00197                 for(it = meshs.begin(); it != meshs.end(); it++) {
00198                         // Get the current mesh. It may later be added
00199                         // to the new node's list.
00200                         Mesh *mesh = *it;
00201 
00202                         meshDone = false;
00203 
00204                         // Go through each of the AABBs of the new nodes.
00205                         for(i = 0; (i < 4) && !meshDone; i++) {
00206 
00207                                 // Check if the mesh is completely inside the boundingbox.
00208                                 if(boundingBoxes[i].isAABBCompletelyInside(mesh->getBoundingBox())) {
00209 
00210                                         // If the new node was not created before, do it now.
00211                                         if(m_nodes[i] == NULL) {
00212                                                 // Create the node.
00213                                                 m_nodes[i] = new QuadtreeNode(new AABB(boundingBoxes[i]), m_minMeshsPerNode, m_occlusionCulling);
00214 
00215                                                 // TODO
00216                                                 //SceneAnalyseGUI.getInstance().setNodeCount(SceneAnalyseGUI.getInstance().getNodeCount() + 1);
00217                                         }
00218 
00219                                         // If the mesh is inside of this box it can not be inside of any other
00220                                         // box. So add reference of the mesh to the new node's mesh list.
00221                                         meshLists[i].push_back(mesh);
00222 
00223                                         // The mesh was already handled, so set this to true.
00224                                         meshDone = true;
00225                                 }
00226                         }
00227 
00228                         // If the mesh was not completely inside of the new nodes,
00229                         // add it to this node.
00230                         if(!meshDone) {
00231                                 addMesh(mesh);
00232                         }
00233                 }
00234 
00235                 // Recursion for quadtree.
00236                 for(i = 0; i < 4; i++) {
00237                         if(m_nodes[i] != NULL) {
00238                                 if(meshLists[i].size() >= m_minMeshsPerNode) {
00239                                         // Subdivide the mesh, if there are enough meshs in the new node's list.
00240                                         m_nodes[i]->subdivide(meshLists[i]);
00241                                 } else {
00242                                         // When the node can't be subdivided, add all meshs of the node's list to the mesh.
00243                                         // The list here is just a temporary memory and will be deleted at the end of this function.
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                         //printf("INFO: [%s] Rootnode meshs: %d\n", __FILE__, m_root->getMeshNum());
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                 //m_root->renderWireframe();
00331         }
00332 
00333 
00334         //****************************************************************************
00335         //
00336         //
00337         //
00338         //****************************************************************************
00339         void Quadtree::timer(unsigned int delay) {
00340                 m_model->timer(delay);
00341         }
00342 };

Generated on Mon Oct 16 12:08:10 2006 for Phobosengine by doxygen 1.3.4