src/SMESH/SMESH_OctreeNode.cxx

   1 //  Copyright (C) 2007-2008  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 //  SMESH SMESH_OctreeNode : Octree with Nodes set
  23 //  inherites global class SMESH_Octree
  24 //
  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(maxLevel,minBoxSize),
  50   myMaxNbNodes(maxNbNodes),
  51   myNodes(theNodes)
  52 {
  53   // We need to compute the first bounding box via a special method
  54   computeBoxForFather();
  55   myNbNodes = myNodes.size();
  56   myIsLeaf = ((myLevel == myMaxLevel) ||
  57               (myNbNodes <= myMaxNbNodes) ||
  58               (maxSize(myBox) <= myMinBoxSize));
  59   // All the children (Boxes and Data) are computed in Compute()
  60   Compute();
  61 }
  62
  63 //==================================================================================
  64 /*!
  65  * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
  66  */
  67 //==================================================================================
  68 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
  69 {
  70   SMESH_OctreeNode * theOctree = new SMESH_OctreeNode();
  71   theOctree->myFather = this;
  72   theOctree->myLevel = myLevel + 1;
  73   theOctree->myMaxLevel = myMaxLevel;
  74   theOctree->myMaxNbNodes = myMaxNbNodes;
  75   theOctree->myMinBoxSize = myMinBoxSize;
  76   theOctree->myNbNodes = 0;
  77   return theOctree;
  78 }
  79
  80 //======================================
  81 /*!
  82  * \brief Compute the first bounding box
  83  *
  84  * We take the max/min coord of the nodes
  85  */
  86 //======================================
  87 void SMESH_OctreeNode::computeBoxForFather()
  88 {
  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     myBox->Add(p1);
  94   }
  95 }
  96
  97 //====================================================================================
  98 /*!
  99  * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes)
 100  * \retval      - True if the Octree is a leaf
 101  */
 102 //====================================================================================
 103 const bool SMESH_OctreeNode::isLeaf()
 104 {
 105   return myIsLeaf;
 106 }
 107
 108 //====================================================================================
 109 /*!
 110  * \brief Tells us if Node is inside the current box with the precision "precision"
 111  * \param Node - Node
 112  * \param precision - The box is enlarged with this precision
 113  * \retval bool - True if Node is in the box within precision
 114  */
 115 //====================================================================================
 116 const bool SMESH_OctreeNode::isInside (const SMDS_MeshNode * Node, const double precision)
 117 {
 118   double X = Node->X();
 119   double Y = Node->Y();
 120   double Z = Node->Z();
 121   bool Out = 1 ;
 122   if (precision <= 0.)
 123     return !(myBox->IsOut(gp_XYZ(X,Y,Z)));
 124   Bnd_B3d BoxWithPrecision;
 125   getBox(BoxWithPrecision);
 126   BoxWithPrecision.Enlarge(precision);
 127   Out = BoxWithPrecision.IsOut(gp_XYZ(X,Y,Z));
 128   return !(Out);
 129 }
 130
 131 //================================================
 132 /*!
 133  * \brief Set the data of the children
 134  * Shares the father's data with each of his child
 135  */
 136 //================================================
 137 void SMESH_OctreeNode::buildChildrenData()
 138 {
 139   gp_XYZ min = myBox->CornerMin();
 140   gp_XYZ max = myBox->CornerMax();
 141   gp_XYZ mid = (min + max)/2.;
 142
 143   set<const SMDS_MeshNode*>::iterator it = myNodes.begin();
 144   int ChildBoxNum;
 145   while (it != myNodes.end())
 146   {
 147     const SMDS_MeshNode* n1 = *it;
 148     ChildBoxNum = (n1->X() > mid.X()) + (n1->Y() > mid.Y())*2 + (n1->Z() > mid.Z())*4;
 149     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
 150     myChild->myNodes.insert(myChild->myNodes.end(),n1);
 151     myNodes.erase( it );
 152     it = myNodes.begin();
 153   }
 154   for (int i = 0; i < 8; i++)
 155   {
 156     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 157     myChild->myNbNodes = (myChild->myNodes).size();
 158     myChild->myIsLeaf = ((myChild->myLevel == myMaxLevel) ||
 159                          (myChild->myNbNodes <= myMaxNbNodes) ||
 160                          (maxSize(myChild->myBox) <= myMinBoxSize));
 161   }
 162 }
 163
 164 //===================================================================
 165 /*!
 166  * \brief Return in Result a list of Nodes potentials to be near Node
 167  * \param Node - Node
 168  * \param precision - precision used
 169  * \param Result - list of Nodes potentials to be near Node
 170  */
 171 //====================================================================
 172 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
 173                                     list<const SMDS_MeshNode*>* Result,
 174                                     const double precision)
 175 {
 176   if (isInside(Node,precision))
 177   {
 178     if (myIsLeaf)
 179     {
 180       Result->insert(Result->end(), myNodes.begin(), myNodes.end());
 181     }
 182     else
 183     {
 184       for (int i = 0; i < 8; i++)
 185       {
 186         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 187         myChild->NodesAround(Node, Result, precision);
 188       }
 189     }
 190   }
 191 }
 192
 193 //=============================
 194 /*!
 195  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 196  * Search for all the nodes in theSetOfNodes
 197  * Static Method : no need to create an SMESH_OctreeNode
 198  * \param theSetOfNodes - set of nodes we look at, modified during research
 199  * \param theGroupsOfNodes - list of nodes closed to each other returned
 200  * \param theTolerance - Precision used, default value is 0.00001
 201  * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
 202  * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
 203  */
 204 //=============================
 205 void SMESH_OctreeNode::FindCoincidentNodes (set<const SMDS_MeshNode*> theSetOfNodes,
 206                                             list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
 207                                             const double theTolerance,
 208                                             const int maxLevel,
 209                                             const int maxNbNodes)
 210 {
 211   SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
 212   theOctreeNode->FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
 213   delete theOctreeNode;
 214 }
 215
 216 //=============================
 217 /*!
 218  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 219  * Search for all the nodes in theSetOfNodes
 220  * \note  The Octree itself is also modified by this method
 221  * \param theSetOfNodes - set of nodes we look at, modified during research
 222  * \param theTolerance - Precision used
 223  * \param theGroupsOfNodes - list of nodes closed to each other returned
 224  */
 225 //=============================
 226 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* theSetOfNodes,
 227                                              const double               theTolerance,
 228                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
 229 {
 230   set<const SMDS_MeshNode*>::iterator it1 = theSetOfNodes->begin();
 231   list<const SMDS_MeshNode*>::iterator it2;
 232
 233   while (it1 != theSetOfNodes->end())
 234   {
 235     const SMDS_MeshNode * n1 = *it1;
 236
 237     list<const SMDS_MeshNode*> ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough
 238
 239     list<const SMDS_MeshNode*> * groupPtr = 0;
 240
 241     // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
 242     // Found nodes are also erased from theSetOfNodes
 243     FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
 244
 245     // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
 246     for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++)
 247     {
 248       const SMDS_MeshNode* n2 = *it2;
 249       if ( !groupPtr )
 250       {
 251         theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
 252         groupPtr = & theGroupsOfNodes->back();
 253         groupPtr->push_back( n1 );
 254       }
 255       if (groupPtr->front() > n2)
 256         groupPtr->push_front( n2 );
 257       else
 258         groupPtr->push_back( n2 );
 259     }
 260     if (groupPtr != 0)
 261       groupPtr->sort();
 262
 263     theSetOfNodes->erase(it1);
 264     it1 = theSetOfNodes->begin();
 265   }
 266 }
 267
 268 //======================================================================================
 269 /*!
 270  * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
 271  * \note  The Octree itself is also modified by this method
 272  * \param Node - We're searching the nodes next to him.
 273  * \param SetOfNodes - set of nodes in which we erase the found nodes
 274  * \param Result - list of nodes closed to Node
 275  * \param precision - Precision used
 276  */
 277 //======================================================================================
 278 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
 279                                             set<const SMDS_MeshNode*>* SetOfNodes,
 280                                             list<const SMDS_MeshNode*>* Result,
 281                                             const double precision)
 282 {
 283   bool isInsideBool = isInside(Node,precision);
 284
 285   if (isInsideBool)
 286   {
 287     // I'm only looking in the leaves, since all the nodes are stored there.
 288     if (myIsLeaf)
 289     {
 290       gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
 291
 292       set<const SMDS_MeshNode*> myNodesCopy = myNodes;
 293       set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
 294       double tol2 = precision * precision;
 295       bool squareBool;
 296
 297       while (it != myNodesCopy.end())
 298       {
 299         const SMDS_MeshNode* n2 = *it;
 300         // We're only looking at nodes with a superior Id.
 301         // JFA: Why?
 302         //if (Node->GetID() < n2->GetID())
 303         if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
 304         {
 305           gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
 306           // Distance optimized computation
 307           squareBool = (p1.SquareDistance( p2 ) <= tol2);
 308
 309           // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
 310           if (squareBool)
 311           {
 312             Result->insert(Result->begin(), n2);
 313             SetOfNodes->erase( n2 );
 314             myNodes.erase( n2 );
 315           }
 316         }
 317         //myNodesCopy.erase( it );
 318         //it = myNodesCopy.begin();
 319         it++;
 320       }
 321       if (Result->size() > 0)
 322         myNodes.erase(Node); // JFA: for bug 0020185
 323     }
 324     else
 325     {
 326       // If I'm not a leaf, I'm going to see my children !
 327       for (int i = 0; i < 8; i++)
 328       {
 329         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 330         myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
 331       }
 332     }
 333   }
 334 }
 335
 336 //================================================================================
 337 /*!
 338  * \brief Return iterator over children
 339  */
 340 //================================================================================
 341 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
 342 {
 343   return SMESH_OctreeNodeIteratorPtr
 344     ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
 345       ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] )));
 346 }
 347
 348 //================================================================================
 349 /*!
 350  * \brief Return nodes iterator
 351  */
 352 //================================================================================
 353 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
 354 {
 355   return SMDS_NodeIteratorPtr
 356     ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator >
 357       ( myNodes.begin(), myNodes.end() ));
 358 }