src/SMESHUtils/SMESH_OctreeNode.cxx

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