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/Octree.cpp

Go to the documentation of this file.
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                 // 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 < 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                 // Create the boxes.
00179                 // Boxes in the back (minZ).
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                 // Boxes in the front (maxZ).
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                 // Loop through the meshes of this node.
00215                 // These could be distributed to the new nodes.
00216                 for(it = meshs.begin(); it != meshs.end(); it++) {
00217                         // Get the current mesh. It may later be added
00218                         // to the new node's list.
00219                         Mesh *mesh = *it;
00220 
00221                         meshDone = false;
00222 
00223                         // Go through each of the AABBs of the new nodes.
00224                         for(i = 0; (i < 8) && !meshDone; i++) {
00225 
00226                                 // Check if the mesh is completely inside the boundingbox.
00227                                 if(boundingBoxes[i].isAABBCompletelyInside(mesh->getBoundingBox())) {
00228 
00229                                         // If the new node was not created before, do it now.
00230                                         if(m_nodes[i] == NULL) {
00231                                                 // Create the node.
00232                                                 m_nodes[i] = new OctreeNode(new AABB(boundingBoxes[i]), m_minMeshsPerNode, m_occlusionCulling);
00233 
00234                                                 // TODO
00235                                                 //SceneAnalyseGUI.getInstance().setNodeCount(SceneAnalyseGUI.getInstance().getNodeCount() + 1);
00236                                         }
00237 
00238                                         // If the mesh is inside of this box it can not be inside of any other
00239                                         // box. So add reference of the mesh to the new node's mesh list.
00240                                         meshLists[i].push_back(mesh);
00241 
00242                                         // The mesh was already handled, so set this to true.
00243                                         meshDone = true;
00244                                 }
00245                         }
00246 
00247                         // If the mesh was not completely inside of the new nodes,
00248                         // add it to this node.
00249                         if(!meshDone) {
00250                                 addMesh(mesh);
00251                         }
00252                 }
00253 
00254                 // Recursion for octree.
00255                 for(i = 0; i < 8; i++) {
00256                         if(m_nodes[i] != NULL) {
00257                                 if(meshLists[i].size() >= m_minMeshsPerNode) {
00258                                         // Subdivide the mesh, if there are enough meshs in the new node's list.
00259                                         m_nodes[i]->subdivide(meshLists[i]);
00260                                 } else {
00261                                         // When the node can't be subdivided, add all meshs of the node's list to the mesh.
00262                                         // The list here is just a temporary memory and will be deleted at the end of this function.
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                         //printf("INFO: [%s] Rootnode meshs: %d\n", __FILE__, m_root->getMeshNum());
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                 //m_root->renderWireframe();
00350         }
00351 
00352 
00353         //****************************************************************************
00354         //
00355         //
00356         //
00357         //****************************************************************************
00358         void Octree::timer(unsigned int delay) {
00359                 m_model->timer(delay);
00360         }
00361 };

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