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