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