glc_octreenode.cpp

Go to the documentation of this file.
00001 /****************************************************************************
00002 
00003  This file is part of the GLC-lib library.
00004  Copyright (C) 2005-2008 Laurent Ribon (laumaya@users.sourceforge.net)
00005  http://glc-lib.sourceforge.net
00006 
00007  GLC-lib is free software; you can redistribute it and/or modify
00008  it under the terms of the GNU Lesser General Public License as published by
00009  the Free Software Foundation; either version 3 of the License, or
00010  (at your option) any later version.
00011 
00012  GLC-lib is distributed in the hope that it will be useful,
00013  but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  GNU Lesser General Public License for more details.
00016 
00017  You should have received a copy of the GNU Lesser General Public License
00018  along with GLC-lib; if not, write to the Free Software
00019  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
00020 
00021  *****************************************************************************/
00023 
00024 #include "glc_octreenode.h"
00025 
00026 bool GLC_OctreeNode::m_useBoundingSphere= true;
00027 
00028 GLC_OctreeNode::GLC_OctreeNode(const GLC_BoundingBox& boundingBox, GLC_OctreeNode* pParent)
00029 : m_BoundingBox(boundingBox)
00030 , m_pParent(pParent)
00031 , m_Children()
00032 , m_3DViewInstanceSet()
00033 , m_Empty(true)
00034 {
00035 
00036 
00037 }
00038 
00039 GLC_OctreeNode::GLC_OctreeNode(const GLC_OctreeNode& octreeNode, GLC_OctreeNode* pParent)
00040 : m_BoundingBox(octreeNode.m_BoundingBox)
00041 , m_pParent(pParent)
00042 , m_Children()
00043 , m_3DViewInstanceSet(octreeNode.m_3DViewInstanceSet)
00044 , m_Empty(octreeNode.m_Empty)
00045 {
00046         if (!octreeNode.m_Children.isEmpty())
00047         {
00048                 const int size= octreeNode.m_Children.size();
00049                 for (int i= 0; i < size; ++i)
00050                 {
00051                         m_Children.append(new GLC_OctreeNode(*(octreeNode.m_Children.at(i)), this));
00052                 }
00053         }
00054 }
00055 
00056 GLC_OctreeNode::~GLC_OctreeNode()
00057 {
00058         const int size= m_Children.size();
00059         for (int i= 0; i < size; ++i)
00060         {
00061                 delete m_Children.at(i);
00062         }
00063 }
00064 
00065 bool GLC_OctreeNode::intersectionWithBoundingSphereUsed()
00066 {
00067         return m_useBoundingSphere;
00068 }
00069 
00070 QSet<GLC_3DViewInstance*> GLC_OctreeNode::setOfIntersectedInstances(const GLC_BoundingBox& bBox)
00071 {
00072         QSet<GLC_3DViewInstance*> instanceSet;
00073         if (intersect(bBox))
00074         {
00075                 QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
00076                 while (m_3DViewInstanceSet.constEnd() != iInstance)
00077                 {
00078                         if ((*iInstance)->boundingBox().intersect(bBox))
00079                         {
00080                                 instanceSet << *(iInstance);
00081                         }
00082                         ++iInstance;
00083                 }
00084                 const int childCount= m_Children.size();
00085                 for (int i= 0; i < childCount; ++i)
00086                 {
00087                         instanceSet.unite(m_Children[i]->setOfIntersectedInstances(bBox));
00088                 }
00089         }
00090 
00091         return instanceSet;
00092 }
00094 // Set Functions
00096 
00097 void GLC_OctreeNode::addChildren()
00098 {
00099         Q_ASSERT(m_Children.isEmpty());
00100         Q_ASSERT(!m_BoundingBox.isEmpty());
00101 
00102         const double xLower=  m_BoundingBox.lowerCorner().x();
00103         const double yLower=  m_BoundingBox.lowerCorner().y();
00104         const double zLower=  m_BoundingBox.lowerCorner().z();
00105 
00106         const double xUpper=  m_BoundingBox.upperCorner().x();
00107         const double dX= (xUpper - xLower) / 2.0;
00108         const double yUpper=  m_BoundingBox.upperCorner().y();
00109         const double dY= (yUpper - yLower) / 2.0;
00110         const double zUpper=  m_BoundingBox.upperCorner().z();
00111         const double dZ= (zUpper - zLower) / 2.0;
00112 
00113 
00114         // Add 8 Children
00115         GLC_Point3d lower;
00116         GLC_Point3d upper;
00117         GLC_OctreeNode* pOctreeNode= NULL;
00118 
00119         { // Child 1
00120                 lower.setVect(xLower, yLower, zLower);
00121                 upper.setVect(xLower + dX, yLower + dY, zLower + dZ);
00122                 GLC_BoundingBox box(lower, upper);
00123                 pOctreeNode= new GLC_OctreeNode(box, this);
00124                 m_Children.append(pOctreeNode);
00125         }
00126         { // Child 2
00127                 lower.setVect(xLower + dX, yLower, zLower);
00128                 upper.setVect(xUpper, yLower + dY, zLower + dZ);
00129                 GLC_BoundingBox box(lower, upper);
00130                 pOctreeNode= new GLC_OctreeNode(box, this);
00131                 m_Children.append(pOctreeNode);
00132         }
00133         { // Child 3
00134                 lower.setVect(xLower + dX, yLower + dY, zLower);
00135                 upper.setVect(xUpper, yUpper, zLower + dZ);
00136                 GLC_BoundingBox box(lower, upper);
00137                 pOctreeNode= new GLC_OctreeNode(box, this);
00138                 m_Children.append(pOctreeNode);
00139         }
00140         { // Child 4
00141                 lower.setVect(xLower, yLower + dY, zLower);
00142                 upper.setVect(xLower + dX, yUpper, zLower + dZ);
00143                 GLC_BoundingBox box(lower, upper);
00144                 pOctreeNode= new GLC_OctreeNode(box, this);
00145                 m_Children.append(pOctreeNode);
00146         }
00147         { // Child 5
00148                 lower.setVect(xLower, yLower, zLower + dZ);
00149                 upper.setVect(xLower + dX, yLower + dY, zUpper);
00150                 GLC_BoundingBox box(lower, upper);
00151                 pOctreeNode= new GLC_OctreeNode(box, this);
00152                 m_Children.append(pOctreeNode);
00153         }
00154         { // Child 6
00155                 lower.setVect(xLower + dX, yLower, zLower + dZ);
00156                 upper.setVect(xUpper, yLower + dY, zUpper);
00157                 GLC_BoundingBox box(lower, upper);
00158                 pOctreeNode= new GLC_OctreeNode(box, this);
00159                 m_Children.append(pOctreeNode);
00160         }
00161         { // Child 7
00162                 lower.setVect(xLower + dX, yLower + dY, zLower + dZ);
00163                 upper.setVect(xUpper, yUpper, zUpper);
00164                 GLC_BoundingBox box(lower, upper);
00165                 pOctreeNode= new GLC_OctreeNode(box, this);
00166                 m_Children.append(pOctreeNode);
00167         }
00168         { // Child 8
00169                 lower.setVect(xLower, yLower + dY, zLower + dZ);
00170                 upper.setVect(xLower + dX, yUpper, zUpper);
00171                 GLC_BoundingBox box(lower, upper);
00172                 pOctreeNode= new GLC_OctreeNode(box, this);
00173                 m_Children.append(pOctreeNode);
00174         }
00175 }
00176 
00177 
00178 void GLC_OctreeNode::addInstance(GLC_3DViewInstance* pInstance, int depth)
00179 {
00180         m_Empty= false;
00181         const GLC_BoundingBox instanceBox= pInstance->boundingBox();
00182         // Check if the instance's bounding box intersect this node bounding box
00183         if (!instanceBox.isEmpty() && intersect(instanceBox))
00184         {
00185                 if (0 == depth)
00186                 {
00187                         m_3DViewInstanceSet.insert(pInstance);
00188                 }
00189                 else
00190                 {
00191                         if (m_Children.isEmpty())
00192                         {
00193                                 // Create children
00194                                 addChildren();
00195                         }
00196                         QVector<bool> childIntersect(8);
00197                         bool allIntersect= true;
00198                         bool currentIntersect= false;
00199                         for (int i= 0; i < 8; ++i)
00200                         {
00201                                 currentIntersect= m_Children.at(i)->intersect(instanceBox);
00202                                 allIntersect= allIntersect && currentIntersect;
00203                                 childIntersect[i]= currentIntersect;
00204                         }
00205                         if (allIntersect)
00206                         {
00207                                 m_3DViewInstanceSet.insert(pInstance);
00208                         }
00209                         else
00210                         {
00211                                 for (int i= 0; i < 8; ++i)
00212                                 {
00213                                         if (childIntersect[i])
00214                                         {
00215                                                 m_Children[i]->addInstance(pInstance, depth - 1);
00216                                         }
00217                                 }
00218                         }
00219                 }
00220 
00221         }
00222 }
00223 
00224 
00225 void GLC_OctreeNode::updateViewableInstances(const GLC_Frustum& frustum, QSet<GLC_3DViewInstance*>* pInstanceSet)
00226 {
00227 
00228         bool firstCall= false;
00229         // Create the set of viewable instance if necessary
00230         if (NULL == pInstanceSet)
00231         {
00232                 pInstanceSet= new QSet<GLC_3DViewInstance*>();
00233                 firstCall= true;
00234         }
00235 
00236         // Test the localisation of current octree node
00237         GLC_Frustum::Localisation nodeLocalisation= frustum.localizeBoundingBox(m_BoundingBox);
00238         if (nodeLocalisation == GLC_Frustum::OutFrustum)
00239         {
00240                 disableViewFlag(pInstanceSet);
00241         }
00242         else if (nodeLocalisation == GLC_Frustum::InFrustum)
00243         {
00244                 unableViewFlag(pInstanceSet);
00245         }
00246         else // The current node intersect the frustum
00247         {
00248                 QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
00249                 while (m_3DViewInstanceSet.constEnd() != iInstance)
00250                 {
00251                         // Test if the instances is in the viewable set
00252                         if (!pInstanceSet->contains(*iInstance))
00253                         {
00254                                 GLC_3DViewInstance* pCurrentInstance= (*iInstance);
00255                                 // Test the localisation of the current instance
00256                                 GLC_Frustum::Localisation instanceLocalisation= frustum.localizeBoundingBox(pCurrentInstance->boundingBox());
00257 
00258                                 if (instanceLocalisation == GLC_Frustum::OutFrustum)
00259                                 {
00260                                         pCurrentInstance->setViewable(GLC_3DViewInstance::NoViewable);
00261                                 }
00262                                 else if (instanceLocalisation == GLC_Frustum::InFrustum)
00263                                 {
00264                                         pInstanceSet->insert(pCurrentInstance);
00265                                         pCurrentInstance->setViewable(GLC_3DViewInstance::FullViewable);
00266                                 }
00267                                 else
00268                                 {
00269                                         pInstanceSet->insert(pCurrentInstance);
00270                                         pCurrentInstance->setViewable(GLC_3DViewInstance::PartialViewable);
00271                                         //Update the geometries viewable property of the instance
00272                                         GLC_Matrix4x4 instanceMat= pCurrentInstance->matrix();
00273                                         const int size= pCurrentInstance->numberOfBody();
00274                                         for (int i= 0; i < size; ++i)
00275                                         {
00276                                                 // Get the geometry bounding box
00277                                                 GLC_BoundingBox geomBox= pCurrentInstance->geomAt(i)->boundingBox();
00278                                                 GLC_Point3d center(instanceMat * geomBox.center());
00279                                                 double radius= geomBox.boundingSphereRadius() * instanceMat.scalingX();
00280                                                 GLC_Frustum::Localisation geomLocalisation= frustum.localizeSphere(center, radius);
00281 
00282                                                 pCurrentInstance->setGeomViewable(i, geomLocalisation != GLC_Frustum::OutFrustum);
00283                                         }
00284                                 }
00285                         }
00286 
00287                         ++iInstance;
00288                 }
00289                 const int size= m_Children.size();
00290                 for (int i= 0; i < size; ++i)
00291                 {
00292                         m_Children.at(i)->updateViewableInstances(frustum, pInstanceSet);
00293                 }
00294         }
00295         if (firstCall) delete pInstanceSet;
00296 }
00297 
00298 
00299 void GLC_OctreeNode::removeEmptyChildren()
00300 {
00301         NodeList::iterator iList= m_Children.begin();
00302         while(m_Children.constEnd() != iList)
00303         {
00304                 GLC_OctreeNode* pCurrentChild= *iList;
00305                 if (pCurrentChild->isEmpty())
00306                 {
00307                         delete pCurrentChild;
00308                         iList= m_Children.erase(iList);
00309                 }
00310                 else
00311                 {
00312                         pCurrentChild->removeEmptyChildren();
00313                         if (pCurrentChild->isEmpty())
00314                         {
00315                                 delete pCurrentChild;
00316                                 iList= m_Children.erase(iList);
00317                         }
00318                         else ++iList;
00319                 }
00320         }
00321         // Update empty flag
00322         if (m_Children.isEmpty() && (NULL != m_pParent))
00323         {
00324                 if (1 == m_3DViewInstanceSet.size())
00325                 {
00326                         m_pParent->m_3DViewInstanceSet.insert(*(m_3DViewInstanceSet.begin()));
00327                         m_3DViewInstanceSet.clear();
00328                 }
00329                 m_Empty= m_3DViewInstanceSet.isEmpty();
00330         }
00331 }
00332 
00333 void GLC_OctreeNode::useBoundingSphereIntersection(bool use)
00334 {
00335         m_useBoundingSphere= use;
00336 }
00337 
00338 void GLC_OctreeNode::unableViewFlag(QSet<GLC_3DViewInstance*>* pInstanceSet)
00339 {
00340         QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
00341         while (m_3DViewInstanceSet.constEnd() != iInstance)
00342         {
00343                 if (!pInstanceSet->contains(*iInstance))
00344                 {
00345                         (*iInstance)->setViewable(GLC_3DViewInstance::FullViewable);
00346                         pInstanceSet->insert(*iInstance);
00347                 }
00348 
00349                 ++iInstance;
00350         }
00351         const int size= m_Children.size();
00352         for (int i= 0; i < size; ++i)
00353         {
00354                 m_Children.at(i)->unableViewFlag(pInstanceSet);
00355         }
00356 }
00357 
00358 
00359 void GLC_OctreeNode::disableViewFlag(QSet<GLC_3DViewInstance*>* pInstanceSet)
00360 {
00361         QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
00362         while (m_3DViewInstanceSet.constEnd() != iInstance)
00363         {
00364                 if (!pInstanceSet->contains(*iInstance))
00365                         (*iInstance)->setViewable(GLC_3DViewInstance::NoViewable);
00366 
00367                 ++iInstance;
00368         }
00369         const int size= m_Children.size();
00370         for (int i= 0; i < size; ++i)
00371         {
00372                 m_Children.at(i)->disableViewFlag(pInstanceSet);
00373         }
00374 }
00375 

SourceForge.net Logo

©2005-2011 Laurent Ribon