src/SMESH/SMESH_OctreeNode.cxx

   1 //  SMESH SMESH_OctreeNode : Octree with Nodes set
   2 //  inherites global class SMESH_Octree
   3 //
   4 //  Copyright (C) 2003  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   5 //  CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   6 //
   7 //  This library is free software; you can redistribute it and/or
   8 //  modify it under the terms of the GNU Lesser General Public
   9 //  License as published by the Free Software Foundation; either
  10 //  version 2.1 of the License.
  11 //
  12 //  This library is distributed in the hope that it will be useful,
  13 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 //  Lesser General Public License for more details.
  16 //
  17 //  You should have received a copy of the GNU Lesser General Public
  18 //  License along with this library; if not, write to the Free Software
  19 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  20 //
  21 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  22 //
  23 //
  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 #include <gp_Pnt.hxx>
  32 #include <SMDS_MeshNode.hxx>
  33
  34 using namespace std;
  35
  36 //===============================================================
  37 /*!
  38  * \brief Constructor : Build all the Octree using Compute()
  39  * \param theNodes - Set of nodes, the Octree is built from this nodes
  40  * \param maxLevel - Maximum level for the leaves
  41  * \param maxNbNodes - Maximum number of nodes, a leaf can contain
  42  * \param minBoxSize - Minimal size of the Octree Box
  43  */
  44 //================================================================
  45 SMESH_OctreeNode::SMESH_OctreeNode (set<const SMDS_MeshNode*> theNodes, const int maxLevel,
  46                                     const int maxNbNodes , const double minBoxSize )
  47   :SMESH_Octree(maxLevel,minBoxSize),
  48   myMaxNbNodes(maxNbNodes),
  49   myNodes(theNodes)
  50 {
  51   // We need to compute the first bounding box via a special method
  52   computeBoxForFather();
  53   myNbNodes = myNodes.size();
  54   myIsLeaf = (myLevel == myMaxLevel)||(myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myBox));
  55   // All the children (Boxes and Data) are computed in Compute()
  56   Compute();
  57 }
  58
  59 //==================================================================================
  60 /*!
  61  * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
  62  */
  63 //==================================================================================
  64 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
  65 {
  66   SMESH_OctreeNode * theOctree = new SMESH_OctreeNode();
  67   theOctree->myFather = this;
  68   theOctree->myLevel = myLevel + 1;
  69   theOctree->myMaxLevel = myMaxLevel;
  70   theOctree->myMaxNbNodes = myMaxNbNodes;
  71   theOctree->myMinBoxSize = myMinBoxSize;
  72   theOctree->myNbNodes = 0;
  73   return theOctree;
  74 }
  75
  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 void SMESH_OctreeNode::computeBoxForFather()
  86 {
  87   set<const SMDS_MeshNode*>::iterator it=myNodes.begin();
  88   for( ;it!=myNodes.end();it++){
  89     const SMDS_MeshNode* n1 = *it;
  90     gp_XYZ p1( n1->X(), n1->Y(), n1->Z() );
  91     myBox->Add(p1);
  92   }
  93 }
  94
  95 //====================================================================================
  96 /*!
  97  * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes)
  98  * \retval      - True if the Octree is a leaf
  99  */
 100 //====================================================================================
 101 const bool SMESH_OctreeNode::isLeaf()
 102 {
 103   return myIsLeaf;
 104 }
 105
 106 //====================================================================================
 107 /*!
 108  * \brief Tells us if Node is inside the current box with the precision "precision"
 109  * \param Node - Node
 110  * \param precision - The box is enlarged with this precision
 111  * \retval bool - True if Node is in the box within precision
 112  */
 113 //====================================================================================
 114 const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double precision )
 115 {
 116   double X=Node->X();
 117   double Y=Node->Y();
 118   double Z=Node->Z();
 119   bool Out = 1 ;
 120   if (precision<=0.)
 121      return !(myBox->IsOut(gp_XYZ(X,Y,Z)));
 122   Bnd_B3d * BoxWithPrecision = new Bnd_B3d();
 123   getBox(BoxWithPrecision);
 124   BoxWithPrecision->Enlarge(precision);
 125   Out=BoxWithPrecision->IsOut(gp_XYZ(X,Y,Z));
 126   delete BoxWithPrecision;
 127   return !(Out);
 128 }
 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)||(myChild->myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myChild->myBox));
 159   }
 160 }
 161
 162 //===================================================================
 163 /*!
 164  * \brief Return in Result a list of Nodes potentials to be near Node
 165  * \param Node - Node
 166  * \param precision - precision used
 167  * \param Result - list of Nodes potentials to be near Node
 168  */
 169 //====================================================================
 170 void SMESH_OctreeNode::NodesAround( const SMDS_MeshNode * Node,
 171                                     list<const SMDS_MeshNode*>* Result, const double precision)
 172 {
 173   if (isInside(Node,precision))
 174   {
 175     if (myIsLeaf)
 176     {
 177       Result->insert( Result->end(), myNodes.begin(), myNodes.end() );
 178     }
 179     else
 180     {
 181       for(int i=0;i<8;i++)
 182       {
 183         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 184         myChild->NodesAround( Node, Result, precision);
 185       }
 186     }
 187   }
 188 }
 189
 190
 191
 192 //=============================
 193 /*!
 194  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 195  * Search for all the nodes in nodes
 196  * Static Method : no need to create an SMESH_OctreeNode
 197  * \param nodes - set of nodes we look at, modified during research
 198  * \param theGroupsOfNodes - list of nodes closed to each other returned
 199  * \param theTolerance - Precision used, default value is 0.00001
 200  * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
 201  * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
 202  */
 203 //=============================
 204 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*> nodes,
 205                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
 206                                              const double theTolerance, const int maxLevel,
 207                                              const int maxNbNodes)
 208 {
 209   SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(nodes, maxLevel, maxNbNodes, theTolerance);
 210   theOctreeNode->FindCoincidentNodes (&nodes, theTolerance, theGroupsOfNodes);
 211   delete theOctreeNode;
 212 }
 213
 214
 215 //=============================
 216 /*!
 217  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
 218  * Search for all the nodes in nodes
 219  * \param nodes - set of nodes we look at, modified during research
 220  * \param theTolerance - Precision used
 221  * \param theGroupsOfNodes - list of nodes closed to each other returned
 222  */
 223 //=============================
 224 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* nodes,
 225                                              const double                theTolerance,
 226                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
 227 {
 228   set<const SMDS_MeshNode*>::iterator it1 = nodes->begin();
 229   list<const SMDS_MeshNode*>::iterator it2;
 230
 231   while (it1 != nodes->end())
 232   {
 233     const SMDS_MeshNode * n1 = *it1;
 234
 235     list<const SMDS_MeshNode*> ListofCoincidentNodes;// Initialize the lists via a declaration, it's enough
 236
 237     list<const SMDS_MeshNode*> * groupPtr = 0;
 238
 239     // Searching for Nodes around n1 and put them in ListofCoincidentNodes
 240     FindCoincidentNodes(n1, nodes, &ListofCoincidentNodes, theTolerance);
 241
 242     // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
 243     for (it2=ListofCoincidentNodes.begin();it2 != ListofCoincidentNodes.end(); it2++)
 244     {
 245       const SMDS_MeshNode* n2 = *it2;
 246       if ( !groupPtr )
 247       {
 248         theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
 249         groupPtr = & theGroupsOfNodes->back();
 250         groupPtr->push_back( n1 );
 251       }
 252       if(groupPtr->front()>n2)
 253         groupPtr->push_front( n2 );
 254       else
 255         groupPtr->push_back( n2 );
 256     }
 257     if(groupPtr != 0)
 258       groupPtr->sort();
 259
 260     nodes->erase(it1);
 261     it1=nodes->begin();
 262   }
 263 }
 264
 265 //======================================================================================
 266 /*!
 267  * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
 268  * \param Node - We're searching the nodes next to him.
 269  * \param SetOfNodes - set of nodes in which we erase the found nodes
 270  * \param Result - list of nodes closed to Node
 271  * \param precision - Precision used
 272  */
 273 //======================================================================================
 274 void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node,
 275                                             set<const SMDS_MeshNode*>* SetOfNodes,
 276                                             list<const SMDS_MeshNode*>* Result,
 277                                             const double precision)
 278 {
 279   bool isInsideBool = isInside(Node,precision);
 280
 281   if (isInsideBool)
 282   {
 283     // I'm only looking in the leaves, since all the nodes are stored there.
 284     if (myIsLeaf)
 285     {
 286       gp_Pnt p1( Node->X(), Node->Y(), Node->Z() );
 287
 288       set<const SMDS_MeshNode*> myNodesCopy = myNodes;
 289       set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
 290       double tol2 = precision * precision;
 291       bool squareBool;
 292
 293       while (it != myNodesCopy.end())
 294       {
 295         const SMDS_MeshNode* n2 = *it;
 296         // We're only looking at nodes with a superior Id.
 297         if(Node->GetID() < n2->GetID())
 298         {
 299           gp_Pnt p2( n2->X(), n2->Y(), n2->Z() );
 300           // Distance optimized computation
 301           squareBool = (p1.SquareDistance( p2 ) <= tol2);
 302
 303           // If n2 inside  the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
 304           if(squareBool)
 305           {
 306             Result->insert(Result->begin(), n2);
 307             SetOfNodes->erase( n2 );
 308             myNodes.erase( n2 );
 309           }
 310         }
 311         myNodesCopy.erase( it );
 312         it = myNodesCopy.begin();
 313       }
 314
 315     }
 316     else
 317     {
 318       // If I'm not a leaf, I'm going to see my children !
 319       for(int i = 0; i < 8; i++)
 320       {
 321         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
 322         myChild->FindCoincidentNodes(Node,  SetOfNodes, Result, precision);
 323       }
 324     }
 325   }
 326 }
 327