src/SMESHUtils/SMESH_OctreeNode.cxx

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