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