src/SMESHUtils/SMESH_OctreeNode.cxx

   1 // Copyright (C) 2007-2015  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, or (at your option) any later version.
  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
  23 //  SMESH SMESH_OctreeNode : Octree with Nodes set
  24 //  inherites class SMESH_Octree
  25 //  File      : SMESH_OctreeNode.cxx
  26 //  Created   : Tue Jan 16 16:00:00 2007
  27 //  Author    : Nicolas Geimer & Aurelien Motteux (OCC)
  28 //  Module    : SMESH
  29 //
  30 #include "SMESH_OctreeNode.hxx"
  31
  32 #include "SMDS_SetIterator.hxx"
  33 #include "SMESH_TypeDefs.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
  48 SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel,
  49                                     const int maxNbNodes , const double minBoxSize )
  50   :SMESH_Octree( new Limit( maxLevel,minBoxSize,maxNbNodes)),
  51    myNodes(theNodes)
  52 {
  53   compute();
  54 }
  55
  56 //================================================================================
  57 /*!
  58  * \brief Constructor used to allocate a child
  59  */
  60 //================================================================================
  61
  62 SMESH_OctreeNode::SMESH_OctreeNode ():SMESH_Octree()
  63 {
  64 }
  65
  66 //================================================================================
  67 /*!
  68  * \brief Return max number of nodes in a tree leaf
  69  */
  70 //================================================================================
  71
  72 int SMESH_OctreeNode::getMaxNbNodes() const
  73 {
  74   return ((Limit*)myLimit)->myMaxNbNodes;
  75 }
  76
  77 //==================================================================================
  78 /*!
  79  * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
  80  */
  81 //==================================================================================
  82
  83 SMESH_Octree* SMESH_OctreeNode::newChild() const
  84 {
  85   return new SMESH_OctreeNode();
  86 }
  87
  88 //======================================
  89 /*!
  90  * \brief Compute the first bounding box
  91  *
  92  * We take the max/min coord of the nodes
  93  */
  94 //======================================
  95
  96 Bnd_B3d* SMESH_OctreeNode::buildRootBox()
  97 {
  98   Bnd_B3d* box = new Bnd_B3d;
  99   TIDSortedNodeSet::iterator it = myNodes.begin();
 100   for (; it != myNodes.end(); it++) {
 101     const SMDS_MeshNode* n1 = *it;
 102     gp_XYZ p1( n1->X(), n1->Y(), n1->Z() );
 103     box->Add(p1);
 104   }
 105   if ((int) myNodes.size() <= getMaxNbNodes() )
 106     myIsLeaf = true;
 107
 108   return box;
 109 }
 110
 111 //====================================================================================
 112 /*!
 113  * \brief Tells us if Node is inside the current box with the precision "precision"
 114  * \param Node - Node
 115  * \param precision - The box is enlarged with this precision
 116  * \retval bool - True if Node is in the box within precision
 117  */
 118 //====================================================================================
 119
 120 const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, const double precision)
 121 {
 122   if (precision <= 0.)
 123     return !(getBox()->IsOut(p));
 124   Bnd_B3d BoxWithPrecision = *getBox();
 125   BoxWithPrecision.Enlarge(precision);
 126   return ! BoxWithPrecision.IsOut(p);
 127 }
 128
 129 //================================================
 130 /*!
 131  * \brief Set the data of the children
 132  * Shares the father's data with each of his child
 133  */
 134 //================================================
 135 void SMESH_OctreeNode::buildChildrenData()
 136 {
 137   gp_XYZ min = getBox()->CornerMin();
 138   gp_XYZ max = getBox()->CornerMax();
 139   gp_XYZ mid = (min + max)/2.;
 140
 141   TIDSortedNodeSet::iterator it = myNodes.begin();
 142   while (it != myNodes.end())
 143   {
 144     const SMDS_MeshNode* n1 = *it;
 145     int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid );
 146     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
 147     myChild->myNodes.insert(myChild->myNodes.end(),n1);
 148     myNodes.erase( it );
 149     it = myNodes.begin();
 150   }
 151   for (int i = 0; i < 8; i++)
 152   {
 153     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 154     if ((int) myChild->myNodes.size() <= getMaxNbNodes() )
 155       myChild->myIsLeaf = true;
 156   }
 157 }
 158
 159 //===================================================================
 160 /*!
 161  * \brief Return in Result a list of Nodes potentials to be near Node
 162  * \param Node - Node
 163  * \param precision - precision used
 164  * \param Result - list of Nodes potentials to be near Node
 165  */
 166 //====================================================================
 167 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
 168                                     list<const SMDS_MeshNode*>* Result,
 169                                     const double precision)
 170 {
 171   SMESH_TNodeXYZ p(Node);
 172   if (isInside(p, precision))
 173   {
 174     if (isLeaf())
 175     {
 176       Result->insert(Result->end(), myNodes.begin(), myNodes.end());
 177     }
 178     else
 179     {
 180       for (int i = 0; i < 8; i++)
 181       {
 182         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 183         myChild->NodesAround(Node, Result, precision);
 184       }
 185     }
 186   }
 187 }
 188
 189 //================================================================================
 190 /*!
 191  * \brief Return in dist2Nodes nodes mapped to their square distance from Node
 192  *        Tries to find a closest node.
 193  *  \param node - node to find nodes closest to
 194  *  \param dist2Nodes - map of found nodes and their distances
 195  *  \param precision - radius of a sphere to check nodes inside
 196  *  \retval bool - true if an exact overlapping found !!!
 197  */
 198 //================================================================================
 199
 200 bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node,
 201                                    map<double, const SMDS_MeshNode*>& dist2Nodes,
 202                                    double                             precision)
 203 {
 204   if ( !dist2Nodes.empty() )
 205     precision = min ( precision, sqrt( dist2Nodes.begin()->first ));
 206   else if ( precision == 0. )
 207     precision = maxSize() / 2;
 208
 209   if (isInside(node, precision))
 210   {
 211     if (!isLeaf())
 212     {
 213       // first check a child containing node
 214       gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
 215       int nodeChild  = getChildIndex( node.X(), node.Y(), node.Z(), mid );
 216       if ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
 217         return true;
 218
 219       for (int i = 0; i < 8; i++)
 220         if ( i != nodeChild )
 221           if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
 222             return true;
 223     }
 224     else if ( NbNodes() > 0 )
 225     {
 226       double minDist = precision * precision;
 227       TIDSortedNodeSet::iterator nIt = myNodes.begin();
 228       for ( ; nIt != myNodes.end(); ++nIt )
 229       {
 230         SMESH_TNodeXYZ p2( *nIt );
 231         double dist2 = ( node - p2 ).SquareModulus();
 232         if ( dist2 < minDist )
 233           dist2Nodes.insert( make_pair( minDist = dist2, p2._node ));
 234       }
 235 //       if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
 236 //         dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
 237
 238       // true if an exact overlapping found
 239       return ( sqrt( minDist ) <= precision * 1e-12 );
 240     }
 241   }
 242   return false;
 243 }
 244
 245 //================================================================================
 246 /*!
 247  * \brief Return a list of nodes close to a point
 248  *  \param [in] point - point
 249  *  \param [out] nodes - found nodes
 250  *  \param [in] precision - allowed distance from \a point
 251  */
 252 //================================================================================
 253
 254 void SMESH_OctreeNode::NodesAround(const gp_XYZ&                      point,
 255                                    std::vector<const SMDS_MeshNode*>& nodes,
 256                                    double                             precision)
 257 {
 258   if ( isInside( point, precision ))
 259   {
 260     if ( isLeaf() && NbNodes() )
 261     {
 262       double minDist2 = precision * precision;
 263       TIDSortedNodeSet::iterator nIt = myNodes.begin();
 264       for ( ; nIt != myNodes.end(); ++nIt )
 265       {
 266         SMESH_TNodeXYZ p2( *nIt );
 267         double dist2 = ( point - p2 ).SquareModulus();
 268         if ( dist2 <= minDist2 )
 269           nodes.push_back( p2._node );
 270       }
 271     }
 272     else if ( myChildren )
 273     {
 274       for (int i = 0; i < 8; i++)
 275       {
 276         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 277         myChild->NodesAround( point, nodes, precision);
 278       }
 279     }
 280   }
 281 }
 282
 283 //=============================
 284 /*!
 285  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 286  * Search for all the nodes in theSetOfNodes
 287  * Static Method : no need to create an SMESH_OctreeNode
 288  * \param theSetOfNodes - set of nodes we look at, modified during research
 289  * \param theGroupsOfNodes - list of nodes closed to each other returned
 290  * \param theTolerance - Precision used, default value is 0.00001
 291  * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
 292  * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
 293  */
 294 //=============================
 295 void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
 296                                             list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
 297                                             const double theTolerance,
 298                                             const int maxLevel,
 299                                             const int maxNbNodes)
 300 {
 301   // VSR 14/10/2011: limit max number of the levels in order to avoid endless recursing
 302   const int MAX_LEVEL = 10;
 303   SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel < 0 ? MAX_LEVEL : maxLevel, maxNbNodes, theTolerance);
 304   theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
 305 }
 306
 307 //=============================
 308 /*!
 309  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 310  * Search for all the nodes in theSetOfNodes
 311  * \note  The Octree itself is also modified by this method
 312  * \param theSetOfNodes - set of nodes we look at, modified during research
 313  * \param theTolerance - Precision used
 314  * \param theGroupsOfNodes - list of nodes closed to each other returned
 315  */
 316 //=============================
 317 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet*                    theSetOfNodes,
 318                                              const double                         theTolerance,
 319                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
 320 {
 321   TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
 322   list<const SMDS_MeshNode*>::iterator it2;
 323
 324   list<const SMDS_MeshNode*> ListOfCoincidentNodes;
 325   TIDCompare idLess;
 326
 327   while (it1 != theSetOfNodes->end())
 328   {
 329     const SMDS_MeshNode * n1 = *it1;
 330
 331     // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
 332     // Found nodes are also erased from theSetOfNodes
 333     FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
 334
 335     if ( !ListOfCoincidentNodes.empty() )
 336     {
 337       // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
 338       if ( idLess( n1, ListOfCoincidentNodes.front() )) ListOfCoincidentNodes.push_front( n1 );
 339       else                                              ListOfCoincidentNodes.push_back ( n1 );
 340       ListOfCoincidentNodes.sort( idLess );
 341       theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
 342       theGroupsOfNodes->back().splice( theGroupsOfNodes->back().end(), ListOfCoincidentNodes );
 343     }
 344
 345     theSetOfNodes->erase(it1);
 346     it1 = theSetOfNodes->begin();
 347   }
 348 }
 349
 350 //======================================================================================
 351 /*!
 352  * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
 353  * \note  The Octree itself is also modified by this method
 354  * \param Node - We're searching the nodes next to him.
 355  * \param SetOfNodes - set of nodes in which we erase the found nodes
 356  * \param Result - list of nodes closed to Node
 357  * \param precision - Precision used
 358  */
 359 //======================================================================================
 360 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode *       Node,
 361                                             TIDSortedNodeSet*           SetOfNodes,
 362                                             list<const SMDS_MeshNode*>* Result,
 363                                             const double                precision)
 364 {
 365   gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
 366   bool isInsideBool = isInside( p1.XYZ(), precision );
 367
 368   if (isInsideBool)
 369   {
 370     // I'm only looking in the leaves, since all the nodes are stored there.
 371     if (isLeaf())
 372     {
 373       TIDSortedNodeSet::iterator it = myNodes.begin();
 374       const double tol2 = precision * precision;
 375       bool squareBool;
 376
 377       while (it != myNodes.end())
 378       {
 379         const SMDS_MeshNode* n2 = *it;
 380         squareBool = false;
 381         // We're only looking at nodes with a superior Id.
 382         // JFA: Why?
 383         //if (Node->GetID() < n2->GetID())
 384         if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
 385         {
 386           gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
 387           // Distance optimized computation
 388           squareBool = (p1.SquareDistance( p2 ) <= tol2);
 389
 390           // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
 391           if (squareBool)
 392           {
 393             Result->insert(Result->begin(), n2);
 394             SetOfNodes->erase( n2 );
 395             myNodes.erase( *it++ ); // it++ goes forward and returns it's previous position
 396           }
 397         }
 398         if ( !squareBool )
 399           it++;
 400       }
 401       if ( !Result->empty() )
 402         myNodes.erase(Node); // JFA: for bug 0020185
 403     }
 404     else
 405     {
 406       // If I'm not a leaf, I'm going to see my children !
 407       for (int i = 0; i < 8; i++)
 408       {
 409         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 410         myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
 411       }
 412     }
 413   }
 414 }
 415
 416 //================================================================================
 417 /*!
 418  * \brief Update data according to node movement
 419  */
 420 //================================================================================
 421
 422 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
 423 {
 424   if ( isLeaf() )
 425   {
 426     TIDSortedNodeSet::iterator pNode = myNodes.find( node );
 427     bool nodeInMe = ( pNode != myNodes.end() );
 428
 429     bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
 430
 431     if ( pointInMe != nodeInMe )
 432     {
 433       if ( pointInMe )
 434         myNodes.insert( node );
 435       else
 436         myNodes.erase( node );
 437     }
 438   }
 439   else if ( myChildren )
 440   {
 441     gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
 442     int nodeChild  = getChildIndex( node->X(), node->Y(), node->Z(), mid );
 443     int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
 444     if ( nodeChild != pointChild )
 445     {
 446       ((SMESH_OctreeNode*) myChildren[ nodeChild  ])->UpdateByMoveNode( node, toPnt );
 447       ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
 448     }
 449   }
 450 }
 451
 452 //================================================================================
 453 /*!
 454  * \brief Return iterator over children
 455  */
 456 //================================================================================
 457 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
 458 {
 459   return SMESH_OctreeNodeIteratorPtr
 460     ( new SMDS_SetIterator< SMESH_OctreeNode*, TBaseTree** >
 461       ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
 462 }
 463
 464 //================================================================================
 465 /*!
 466  * \brief Return nodes iterator
 467  */
 468 //================================================================================
 469 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
 470 {
 471   return SMDS_NodeIteratorPtr
 472     ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
 473       ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));
 474 }