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