src/SMESH/SMESH_OctreeNode.cxx

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