src/SMESH/SMESH_OctreeNode.cxx

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