Salome HOME
Update copyright
[modules/smesh.git] / src / SMESH / SMESH_OctreeNode.cxx
1 // Copyright (C) 2007-2011  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       set<const SMDS_MeshNode*>::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   SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
253   theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
254 }
255
256 //=============================
257 /*!
258  * \brief  Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
259  * Search for all the nodes in theSetOfNodes
260  * \note  The Octree itself is also modified by this method
261  * \param theSetOfNodes - set of nodes we look at, modified during research
262  * \param theTolerance - Precision used
263  * \param theGroupsOfNodes - list of nodes closed to each other returned
264  */
265 //=============================
266 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
267                                              const double               theTolerance,
268                                              list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
269 {
270   TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
271   list<const SMDS_MeshNode*>::iterator it2;
272
273   while (it1 != theSetOfNodes->end())
274   {
275     const SMDS_MeshNode * n1 = *it1;
276
277     list<const SMDS_MeshNode*> ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough
278
279     list<const SMDS_MeshNode*> * groupPtr = 0;
280
281     // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
282     // Found nodes are also erased from theSetOfNodes
283     FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
284
285     // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
286     for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++)
287     {
288       const SMDS_MeshNode* n2 = *it2;
289       if ( !groupPtr )
290       {
291         theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
292         groupPtr = & theGroupsOfNodes->back();
293         groupPtr->push_back( n1 );
294       }
295       if (groupPtr->front() > n2)
296         groupPtr->push_front( n2 );
297       else
298         groupPtr->push_back( n2 );
299     }
300     if (groupPtr != 0)
301       groupPtr->sort();
302
303     theSetOfNodes->erase(it1);
304     it1 = theSetOfNodes->begin();
305   }
306 }
307
308 //======================================================================================
309 /*!
310  * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
311  * \note  The Octree itself is also modified by this method
312  * \param Node - We're searching the nodes next to him.
313  * \param SetOfNodes - set of nodes in which we erase the found nodes
314  * \param Result - list of nodes closed to Node
315  * \param precision - Precision used
316  */
317 //======================================================================================
318 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
319                                             TIDSortedNodeSet* SetOfNodes,
320                                             list<const SMDS_MeshNode*>* Result,
321                                             const double precision)
322 {
323   gp_XYZ p(Node->X(), Node->Y(), Node->Z());
324   bool isInsideBool = isInside(p, precision);
325
326   if (isInsideBool)
327   {
328     // I'm only looking in the leaves, since all the nodes are stored there.
329     if (isLeaf())
330     {
331       gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
332
333       TIDSortedNodeSet myNodesCopy = myNodes;
334       TIDSortedNodeSet::iterator it = myNodesCopy.begin();
335       double tol2 = precision * precision;
336       bool squareBool;
337
338       while (it != myNodesCopy.end())
339       {
340         const SMDS_MeshNode* n2 = *it;
341         // We're only looking at nodes with a superior Id.
342         // JFA: Why?
343         //if (Node->GetID() < n2->GetID())
344         if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
345         {
346           gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
347           // Distance optimized computation
348           squareBool = (p1.SquareDistance( p2 ) <= tol2);
349
350           // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
351           if (squareBool)
352           {
353             Result->insert(Result->begin(), n2);
354             SetOfNodes->erase( n2 );
355             myNodes.erase( n2 );
356           }
357         }
358         //myNodesCopy.erase( it );
359         //it = myNodesCopy.begin();
360         it++;
361       }
362       if (Result->size() > 0)
363         myNodes.erase(Node); // JFA: for bug 0020185
364     }
365     else
366     {
367       // If I'm not a leaf, I'm going to see my children !
368       for (int i = 0; i < 8; i++)
369       {
370         SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
371         myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
372       }
373     }
374   }
375 }
376
377 //================================================================================
378 /*!
379  * \brief Update data according to node movement
380  */
381 //================================================================================
382
383 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
384 {
385   if ( isLeaf() )
386   {
387     TIDSortedNodeSet::iterator pNode = myNodes.find( node );
388     bool nodeInMe = ( pNode != myNodes.end() );
389
390     bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
391
392     if ( pointInMe != nodeInMe )
393     {
394       if ( pointInMe )
395         myNodes.insert( node );
396       else
397         myNodes.erase( node );
398     }
399   }
400   else if ( myChildren )
401   {
402     gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
403     int nodeChild  = getChildIndex( node->X(), node->Y(), node->Z(), mid );
404     int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
405     if ( nodeChild != pointChild )
406     {
407       ((SMESH_OctreeNode*) myChildren[ nodeChild  ])->UpdateByMoveNode( node, toPnt );
408       ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
409     }
410   }
411 }
412
413 //================================================================================
414 /*!
415  * \brief Return iterator over children
416  */
417 //================================================================================
418 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
419 {
420   return SMESH_OctreeNodeIteratorPtr
421     ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
422       ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
423 }
424
425 //================================================================================
426 /*!
427  * \brief Return nodes iterator
428  */
429 //================================================================================
430 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
431 {
432   return SMDS_NodeIteratorPtr
433     ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
434       ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));
435 }