src/SMESH/SMESH_OctreeNode.cxx

   1 //  Copyright (C) 2007-2008  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 //  Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 //  CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 //  This library is free software; you can redistribute it and/or
   7 //  modify it under the terms of the GNU Lesser General Public
   8 //  License as published by the Free Software Foundation; either
   9 //  version 2.1 of the License.
  10 //
  11 //  This library is distributed in the hope that it will be useful,
  12 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 //  Lesser General Public License for more details.
  15 //
  16 //  You should have received a copy of the GNU Lesser General Public
  17 //  License along with this library; if not, write to the Free Software
  18 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 //  See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22 //  SMESH SMESH_OctreeNode : Octree with Nodes set
  23 //  inherites global class SMESH_Octree
  24 // File      : SMESH_OctreeNode.cxx
  25 // Created   : Tue Jan 16 16:00:00 2007
  26 // Author    : Nicolas Geimer & Aurélien Motteux (OCC)
  27 // Module    : SMESH
  28 //
  29 #include "SMESH_OctreeNode.hxx"
  30
  31 #include "SMDS_MeshNode.hxx"
  32 #include "SMDS_SetIterator.hxx"
  33 #include <gp_Pnt.hxx>
  34
  35 using namespace std;
  36
  37 //===============================================================
  38 /*!
  39  * \brief Constructor : Build all the Octree using Compute()
  40  * \param theNodes - Set of nodes, the Octree is built from this nodes
  41  * \param maxLevel - Maximum level for the leaves
  42  * \param maxNbNodes - Maximum number of nodes, a leaf can contain
  43  * \param minBoxSize - Minimal size of the Octree Box
  44  */
  45 //================================================================
  46 SMESH_OctreeNode::SMESH_OctreeNode (const set<const SMDS_MeshNode*> & theNodes, const int maxLevel,
  47                                     const int maxNbNodes , const double minBoxSize )
  48   :SMESH_Octree(maxLevel,minBoxSize),
  49   myMaxNbNodes(maxNbNodes),
  50   myNodes(theNodes)
  51 {
  52   // We need to compute the first bounding box via a special method
  53   computeBoxForFather();
  54   myNbNodes = myNodes.size();
  55   myIsLeaf = (myLevel == myMaxLevel)||(myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myBox));
  56   // All the children (Boxes and Data) are computed in Compute()
  57   Compute();
  58 }
  59
  60 //==================================================================================
  61 /*!
  62  * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
  63  */
  64 //==================================================================================
  65 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
  66 {
  67   SMESH_OctreeNode * theOctree = new SMESH_OctreeNode();
  68   theOctree->myFather = this;
  69   theOctree->myLevel = myLevel + 1;
  70   theOctree->myMaxLevel = myMaxLevel;
  71   theOctree->myMaxNbNodes = myMaxNbNodes;
  72   theOctree->myMinBoxSize = myMinBoxSize;
  73   theOctree->myNbNodes = 0;
  74   return theOctree;
  75 }
  76
  77
  78
  79 //======================================
  80 /*!
  81  * \brief Compute the first bounding box
  82  *
  83  * We take the max/min coord of  the nodes
  84  */
  85 //======================================
  86 void SMESH_OctreeNode::computeBoxForFather()
  87 {
  88   set<const SMDS_MeshNode*>::iterator it=myNodes.begin();
  89   for( ;it!=myNodes.end();it++){
  90     const SMDS_MeshNode* n1 = *it;
  91     gp_XYZ p1( n1->X(), n1->Y(), n1->Z() );
  92     myBox->Add(p1);
  93   }
  94 }
  95
  96 //====================================================================================
  97 /*!
  98  * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes)
  99  * \retval      - True if the Octree is a leaf
 100  */
 101 //====================================================================================
 102 const bool SMESH_OctreeNode::isLeaf()
 103 {
 104   return myIsLeaf;
 105 }
 106
 107 //====================================================================================
 108 /*!
 109  * \brief Tells us if Node is inside the current box with the precision "precision"
 110  * \param Node - Node
 111  * \param precision - The box is enlarged with this precision
 112  * \retval bool - True if Node is in the box within precision
 113  */
 114 //====================================================================================
 115 const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double precision )
 116 {
 117   double X=Node->X();
 118   double Y=Node->Y();
 119   double Z=Node->Z();
 120   bool Out = 1 ;
 121   if (precision<=0.)
 122      return !(myBox->IsOut(gp_XYZ(X,Y,Z)));
 123   Bnd_B3d BoxWithPrecision;
 124   getBox(BoxWithPrecision);
 125   BoxWithPrecision.Enlarge(precision);
 126   Out=BoxWithPrecision.IsOut(gp_XYZ(X,Y,Z));
 127   return !(Out);
 128 }
 129
 130
 131 //================================================
 132 /*!
 133  * \brief Set the data of the children
 134  * Shares the father's data with each of his child
 135  */
 136 //================================================
 137 void SMESH_OctreeNode::buildChildrenData()
 138 {
 139   gp_XYZ min = myBox->CornerMin();
 140   gp_XYZ max = myBox->CornerMax();
 141   gp_XYZ mid = (min + max)/2.;
 142
 143   set<const SMDS_MeshNode*>::iterator it=myNodes.begin();
 144   int ChildBoxNum;
 145   while( it!=myNodes.end())
 146   {
 147     const SMDS_MeshNode* n1 = *it;
 148     ChildBoxNum= (n1->X()>mid.X()) + (n1->Y()>mid.Y())*2 + (n1->Z()>mid.Z())*4;
 149     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
 150     myChild->myNodes.insert(myChild->myNodes.end(),n1);
 151     myNodes.erase( it );
 152     it=myNodes.begin();
 153   }
 154   for (int i = 0; i<8; i++)
 155   {
 156     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 157     myChild->myNbNodes = (myChild->myNodes).size();
 158     myChild->myIsLeaf = (myChild->myLevel == myMaxLevel)||(myChild->myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myChild->myBox));
 159   }
 160 }
 161
 162 //===================================================================
 163 /*!
 164  * \brief Return in Result a list of Nodes potentials to be near Node
 165  * \param Node - Node
 166  * \param precision - precision used
 167  * \param Result - list of Nodes potentials to be near Node
 168  */
 169 //====================================================================
 170 void SMESH_OctreeNode::NodesAround( const SMDS_MeshNode * Node,
 171                                     list<const SMDS_MeshNode*>* Result, const double precision)
 172 {
 173   if (isInside(Node,precision))
 174   {
 175     if (myIsLeaf)
 176     {
 177       Result->insert( Result->end(), myNodes.begin(), myNodes.end() );
 178     }
 179     else
 180     {
 181       for(int i=0;i<8;i++)
 182       {
 183         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 184         myChild->NodesAround( Node, Result, precision);
 185       }
 186     }
 187   }
 188 }
 189
 190
 191
 192 //=============================
 193 /*!
 194  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 195  * Search for all the nodes in nodes
 196  * Static Method : no need to create an SMESH_OctreeNode
 197  * \param nodes - set of nodes we look at, modified during research
 198  * \param theGroupsOfNodes - list of nodes closed to each other returned
 199  * \param theTolerance - Precision used, default value is 0.00001
 200  * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
 201  * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
 202  */
 203 //=============================
 204 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*> nodes,
 205                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
 206                                              const double theTolerance, const int maxLevel,
 207                                              const int maxNbNodes)
 208 {
 209   SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(nodes, maxLevel, maxNbNodes, theTolerance);
 210   theOctreeNode->FindCoincidentNodes (&nodes, theTolerance, theGroupsOfNodes);
 211   delete theOctreeNode;
 212 }
 213
 214
 215 //=============================
 216 /*!
 217  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 218  * Search for all the nodes in nodes
 219  * \param nodes - set of nodes we look at, modified during research
 220  * \param theTolerance - Precision used
 221  * \param theGroupsOfNodes - list of nodes closed to each other returned
 222  */
 223 //=============================
 224 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* nodes,
 225                                              const double                theTolerance,
 226                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
 227 {
 228   set<const SMDS_MeshNode*>::iterator it1 = nodes->begin();
 229   list<const SMDS_MeshNode*>::iterator it2;
 230
 231   while (it1 != nodes->end())
 232   {
 233     const SMDS_MeshNode * n1 = *it1;
 234
 235     list<const SMDS_MeshNode*> ListofCoincidentNodes;// Initialize the lists via a declaration, it's enough
 236
 237     list<const SMDS_MeshNode*> * groupPtr = 0;
 238
 239     // Searching for Nodes around n1 and put them in ListofCoincidentNodes
 240     FindCoincidentNodes(n1, nodes, &ListofCoincidentNodes, theTolerance);
 241
 242     // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
 243     for (it2=ListofCoincidentNodes.begin();it2 != ListofCoincidentNodes.end(); it2++)
 244     {
 245       const SMDS_MeshNode* n2 = *it2;
 246       if ( !groupPtr )
 247       {
 248         theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
 249         groupPtr = & theGroupsOfNodes->back();
 250         groupPtr->push_back( n1 );
 251       }
 252       if(groupPtr->front()>n2)
 253         groupPtr->push_front( n2 );
 254       else
 255         groupPtr->push_back( n2 );
 256     }
 257     if(groupPtr != 0)
 258       groupPtr->sort();
 259
 260     nodes->erase(it1);
 261     it1=nodes->begin();
 262   }
 263 }
 264
 265 //======================================================================================
 266 /*!
 267  * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
 268  * \param Node - We're searching the nodes next to him.
 269  * \param SetOfNodes - set of nodes in which we erase the found nodes
 270  * \param Result - list of nodes closed to Node
 271  * \param precision - Precision used
 272  */
 273 //======================================================================================
 274 void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node,
 275                                             set<const SMDS_MeshNode*>* SetOfNodes,
 276                                             list<const SMDS_MeshNode*>* Result,
 277                                             const double precision)
 278 {
 279   bool isInsideBool = isInside(Node,precision);
 280
 281   if (isInsideBool)
 282   {
 283     // I'm only looking in the leaves, since all the nodes are stored there.
 284     if (myIsLeaf)
 285     {
 286       gp_Pnt p1( Node->X(), Node->Y(), Node->Z() );
 287
 288       set<const SMDS_MeshNode*> myNodesCopy = myNodes;
 289       set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
 290       double tol2 = precision * precision;
 291       bool squareBool;
 292
 293       while (it != myNodesCopy.end())
 294       {
 295         const SMDS_MeshNode* n2 = *it;
 296         // We're only looking at nodes with a superior Id.
 297         if(Node->GetID() < n2->GetID())
 298         {
 299           gp_Pnt p2( n2->X(), n2->Y(), n2->Z() );
 300           // Distance optimized computation
 301           squareBool = (p1.SquareDistance( p2 ) <= tol2);
 302
 303           // If n2 inside  the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
 304           if(squareBool)
 305           {
 306             Result->insert(Result->begin(), n2);
 307             SetOfNodes->erase( n2 );
 308             myNodes.erase( n2 );
 309           }
 310         }
 311         myNodesCopy.erase( it );
 312         it = myNodesCopy.begin();
 313       }
 314
 315     }
 316     else
 317     {
 318       // If I'm not a leaf, I'm going to see my children !
 319       for(int i = 0; i < 8; i++)
 320       {
 321         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 322         myChild->FindCoincidentNodes(Node,  SetOfNodes, Result, precision);
 323       }
 324     }
 325   }
 326 }
 327
 328 //================================================================================
 329 /*!
 330  * \brief Return iterator over children
 331  */
 332 //================================================================================
 333
 334 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
 335 {
 336   return SMESH_OctreeNodeIteratorPtr
 337     ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
 338       ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] )));
 339 }
 340
 341 //================================================================================
 342 /*!
 343  * \brief Return nodes iterator
 344  */
 345 //================================================================================
 346
 347 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
 348 {
 349   return SMDS_NodeIteratorPtr
 350     ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator >
 351       ( myNodes.begin(), myNodes.end() ));
 352 }