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