Back to index

salome-smesh  6.5.0
SMESH_OctreeNode.cxx
Go to the documentation of this file.
00001 // Copyright (C) 2007-2012  CEA/DEN, EDF R&D, OPEN CASCADE
00002 //
00003 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
00004 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
00005 //
00006 // This library is free software; you can redistribute it and/or
00007 // modify it under the terms of the GNU Lesser General Public
00008 // License as published by the Free Software Foundation; either
00009 // version 2.1 of the License.
00010 //
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // Lesser General Public License for more details.
00015 //
00016 // You should have received a copy of the GNU Lesser General Public
00017 // License along with this library; if not, write to the Free Software
00018 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
00019 //
00020 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
00021 //
00022 
00023 //  SMESH SMESH_OctreeNode : Octree with Nodes set
00024 //  inherites global class SMESH_Octree
00025 //  File      : SMESH_OctreeNode.cxx
00026 //  Created   : Tue Jan 16 16:00:00 2007
00027 //  Author    : Nicolas Geimer & Aurelien Motteux (OCC)
00028 //  Module    : SMESH
00029 //
00030 #include "SMESH_OctreeNode.hxx"
00031 
00032 #include "SMDS_SetIterator.hxx"
00033 #include <gp_Pnt.hxx>
00034 
00035 using namespace std;
00036 
00037 //===============================================================
00045 //================================================================
00046 SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel,
00047                                     const int maxNbNodes , const double minBoxSize )
00048   :SMESH_Octree( new SMESH_Octree::Limit( maxLevel,minBoxSize)),
00049   myMaxNbNodes(maxNbNodes),
00050   myNodes(theNodes)
00051 {
00052   compute();
00053 }
00054 
00055 //================================================================================
00059 //================================================================================
00060 
00061 SMESH_OctreeNode::SMESH_OctreeNode (int maxNbNodes):
00062   SMESH_Octree(), myMaxNbNodes(maxNbNodes)
00063 {
00064 }
00065 
00066 //==================================================================================
00070 //==================================================================================
00071 
00072 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() const
00073 {
00074   return new SMESH_OctreeNode(myMaxNbNodes);
00075 }
00076 
00077 //======================================
00083 //======================================
00084 
00085 Bnd_B3d* SMESH_OctreeNode::buildRootBox()
00086 {
00087   Bnd_B3d* box = new Bnd_B3d;
00088   TIDSortedNodeSet::iterator it = myNodes.begin();
00089   for (; it != myNodes.end(); it++) {
00090     const SMDS_MeshNode* n1 = *it;
00091     gp_XYZ p1( n1->X(), n1->Y(), n1->Z() );
00092     box->Add(p1);
00093   }
00094   if ( myNodes.size() <= myMaxNbNodes )
00095     myIsLeaf = true;
00096 
00097   return box;
00098 }
00099 
00100 //====================================================================================
00107 //====================================================================================
00108 
00109 const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, const double precision)
00110 {
00111   if (precision <= 0.)
00112     return !(getBox().IsOut(p));
00113   Bnd_B3d BoxWithPrecision = getBox();
00114   BoxWithPrecision.Enlarge(precision);
00115   return ! BoxWithPrecision.IsOut(p);
00116 }
00117 
00118 //================================================
00123 //================================================
00124 void SMESH_OctreeNode::buildChildrenData()
00125 {
00126   gp_XYZ min = getBox().CornerMin();
00127   gp_XYZ max = getBox().CornerMax();
00128   gp_XYZ mid = (min + max)/2.;
00129 
00130   TIDSortedNodeSet::iterator it = myNodes.begin();
00131   while (it != myNodes.end())
00132   {
00133     const SMDS_MeshNode* n1 = *it;
00134     int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid );
00135     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
00136     myChild->myNodes.insert(myChild->myNodes.end(),n1);
00137     myNodes.erase( it );
00138     it = myNodes.begin();
00139   }
00140   for (int i = 0; i < 8; i++)
00141   {
00142     SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
00143     if ( myChild->myNodes.size() <= myMaxNbNodes )
00144       myChild->myIsLeaf = true;
00145   }
00146 }
00147 
00148 //===================================================================
00155 //====================================================================
00156 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
00157                                     list<const SMDS_MeshNode*>* Result,
00158                                     const double precision)
00159 {
00160   gp_XYZ p(Node->X(), Node->Y(), Node->Z());
00161   if (isInside(p, precision))
00162   {
00163     if (isLeaf())
00164     {
00165       Result->insert(Result->end(), myNodes.begin(), myNodes.end());
00166     }
00167     else
00168     {
00169       for (int i = 0; i < 8; i++)
00170       {
00171         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
00172         myChild->NodesAround(Node, Result, precision);
00173       }
00174     }
00175   }
00176 }
00177 
00178 //================================================================================
00186 //================================================================================
00187 
00188 bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node,
00189                                    map<double, const SMDS_MeshNode*>& dist2Nodes,
00190                                    double                             precision)
00191 {
00192   if ( !dist2Nodes.empty() )
00193     precision = min ( precision, sqrt( dist2Nodes.begin()->first ));
00194   else if ( precision == 0. )
00195     precision = maxSize() / 2;
00196 
00197   //gp_XYZ p(node->X(), node->Y(), node->Z());
00198   if (isInside(node, precision))
00199   {
00200     if (!isLeaf())
00201     {
00202       // first check a child containing node
00203       gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
00204       int nodeChild  = getChildIndex( node.X(), node.Y(), node.Z(), mid );
00205       if ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
00206         return true;
00207       
00208       for (int i = 0; i < 8; i++)
00209         if ( i != nodeChild )
00210           if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
00211             return true;
00212     }
00213     else if ( NbNodes() > 0 )
00214     {
00215       double minDist = precision * precision;
00216       gp_Pnt p1 ( node.X(), node.Y(), node.Z() );
00217       TIDSortedNodeSet::iterator nIt = myNodes.begin();
00218       for ( ; nIt != myNodes.end(); ++nIt )
00219       {
00220         gp_Pnt p2 ( (*nIt)->X(), (*nIt)->Y(), (*nIt)->Z() );
00221         double dist2 = p1.SquareDistance( p2 );
00222         if ( dist2 < minDist )
00223           dist2Nodes.insert( make_pair( minDist = dist2, *nIt ));
00224       }
00225 //       if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
00226 //         dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
00227 
00228       return ( sqrt( minDist) <= precision * 1e-12 );
00229     }
00230   }
00231   return false;
00232 }
00233 
00234 //=============================
00245 //=============================
00246 void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
00247                                             list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
00248                                             const double theTolerance,
00249                                             const int maxLevel,
00250                                             const int maxNbNodes)
00251 {
00252   // VSR 14/10/2011: limit max number of the levels in order to avoid endless recursing
00253   const int MAX_LEVEL = 10;
00254   SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel < 0 ? MAX_LEVEL : maxLevel, maxNbNodes, theTolerance);
00255   theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
00256 }
00257 
00258 //=============================
00267 //=============================
00268 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
00269                                              const double               theTolerance,
00270                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
00271 {
00272   TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
00273   list<const SMDS_MeshNode*>::iterator it2;
00274 
00275   while (it1 != theSetOfNodes->end())
00276   {
00277     const SMDS_MeshNode * n1 = *it1;
00278 
00279     list<const SMDS_MeshNode*> ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough
00280 
00281     list<const SMDS_MeshNode*> * groupPtr = 0;
00282 
00283     // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
00284     // Found nodes are also erased from theSetOfNodes
00285     FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
00286 
00287     // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
00288     for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++)
00289     {
00290       const SMDS_MeshNode* n2 = *it2;
00291       if ( !groupPtr )
00292       {
00293         theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
00294         groupPtr = & theGroupsOfNodes->back();
00295         groupPtr->push_back( n1 );
00296       }
00297       if (groupPtr->front() > n2)
00298         groupPtr->push_front( n2 );
00299       else
00300         groupPtr->push_back( n2 );
00301     }
00302     if (groupPtr != 0)
00303       groupPtr->sort();
00304 
00305     theSetOfNodes->erase(it1);
00306     it1 = theSetOfNodes->begin();
00307   }
00308 }
00309 
00310 //======================================================================================
00319 //======================================================================================
00320 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
00321                                             TIDSortedNodeSet* SetOfNodes,
00322                                             list<const SMDS_MeshNode*>* Result,
00323                                             const double precision)
00324 {
00325   gp_XYZ p(Node->X(), Node->Y(), Node->Z());
00326   bool isInsideBool = isInside(p, precision);
00327 
00328   if (isInsideBool)
00329   {
00330     // I'm only looking in the leaves, since all the nodes are stored there.
00331     if (isLeaf())
00332     {
00333       gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
00334 
00335       TIDSortedNodeSet myNodesCopy = myNodes;
00336       TIDSortedNodeSet::iterator it = myNodesCopy.begin();
00337       double tol2 = precision * precision;
00338       bool squareBool;
00339 
00340       while (it != myNodesCopy.end())
00341       {
00342         const SMDS_MeshNode* n2 = *it;
00343         // We're only looking at nodes with a superior Id.
00344         // JFA: Why?
00345         //if (Node->GetID() < n2->GetID())
00346         if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
00347         {
00348           gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
00349           // Distance optimized computation
00350           squareBool = (p1.SquareDistance( p2 ) <= tol2);
00351 
00352           // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
00353           if (squareBool)
00354           {
00355             Result->insert(Result->begin(), n2);
00356             SetOfNodes->erase( n2 );
00357             myNodes.erase( n2 );
00358           }
00359         }
00360         //myNodesCopy.erase( it );
00361         //it = myNodesCopy.begin();
00362         it++;
00363       }
00364       if (Result->size() > 0)
00365         myNodes.erase(Node); // JFA: for bug 0020185
00366     }
00367     else
00368     {
00369       // If I'm not a leaf, I'm going to see my children !
00370       for (int i = 0; i < 8; i++)
00371       {
00372         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
00373         myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
00374       }
00375     }
00376   }
00377 }
00378 
00379 //================================================================================
00383 //================================================================================
00384 
00385 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
00386 {
00387   if ( isLeaf() )
00388   {
00389     TIDSortedNodeSet::iterator pNode = myNodes.find( node );
00390     bool nodeInMe = ( pNode != myNodes.end() );
00391 
00392     bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
00393 
00394     if ( pointInMe != nodeInMe )
00395     {
00396       if ( pointInMe )
00397         myNodes.insert( node );
00398       else
00399         myNodes.erase( node );
00400     }
00401   }
00402   else if ( myChildren )
00403   {
00404     gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
00405     int nodeChild  = getChildIndex( node->X(), node->Y(), node->Z(), mid );
00406     int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
00407     if ( nodeChild != pointChild )
00408     {
00409       ((SMESH_OctreeNode*) myChildren[ nodeChild  ])->UpdateByMoveNode( node, toPnt );
00410       ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
00411     }
00412   }
00413 }
00414 
00415 //================================================================================
00419 //================================================================================
00420 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
00421 {
00422   return SMESH_OctreeNodeIteratorPtr
00423     ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
00424       ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
00425 }
00426 
00427 //================================================================================
00431 //================================================================================
00432 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
00433 {
00434   return SMDS_NodeIteratorPtr
00435     ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
00436       ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));
00437 }