1 // Copyright (C) 2007-2015 CEA/DEN, EDF R&D, OPEN CASCADE
3 // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
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.
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.
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
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
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)
30 #include "SMESH_OctreeNode.hxx"
32 #include "SMDS_SetIterator.hxx"
33 #include "SMESH_TypeDefs.hxx"
38 //===============================================================
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
46 //================================================================
48 SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel,
49 const int maxNbNodes , const double minBoxSize )
50 :SMESH_Octree( new Limit( maxLevel,minBoxSize,maxNbNodes)),
56 //================================================================================
58 * \brief Constructor used to allocate a child
60 //================================================================================
62 SMESH_OctreeNode::SMESH_OctreeNode ():SMESH_Octree()
66 //================================================================================
68 * \brief Return max number of nodes in a tree leaf
70 //================================================================================
72 int SMESH_OctreeNode::getMaxNbNodes() const
74 return ((Limit*)myLimit)->myMaxNbNodes;
77 //==================================================================================
79 * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
81 //==================================================================================
83 SMESH_Octree* SMESH_OctreeNode::newChild() const
85 return new SMESH_OctreeNode();
88 //======================================
90 * \brief Compute the first bounding box
92 * We take the max/min coord of the nodes
94 //======================================
96 Bnd_B3d* SMESH_OctreeNode::buildRootBox()
98 Bnd_B3d* box = new Bnd_B3d;
99 TIDSortedNodeSet::iterator it = myNodes.begin();
100 for (; it != myNodes.end(); it++) {
101 const SMDS_MeshNode* n1 = *it;
102 gp_XYZ p1( n1->X(), n1->Y(), n1->Z() );
105 if ((int) myNodes.size() <= getMaxNbNodes() )
111 //====================================================================================
113 * \brief Tells us if Node is inside the current box with the precision "precision"
115 * \param precision - The box is enlarged with this precision
116 * \retval bool - True if Node is in the box within precision
118 //====================================================================================
120 const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, const double precision)
123 return !(getBox()->IsOut(p));
124 Bnd_B3d BoxWithPrecision = *getBox();
125 BoxWithPrecision.Enlarge(precision);
126 return ! BoxWithPrecision.IsOut(p);
129 //================================================
131 * \brief Set the data of the children
132 * Shares the father's data with each of his child
134 //================================================
135 void SMESH_OctreeNode::buildChildrenData()
137 gp_XYZ min = getBox()->CornerMin();
138 gp_XYZ max = getBox()->CornerMax();
139 gp_XYZ mid = (min + max)/2.;
141 TIDSortedNodeSet::iterator it = myNodes.begin();
142 while (it != myNodes.end())
144 const SMDS_MeshNode* n1 = *it;
145 int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid );
146 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
147 myChild->myNodes.insert(myChild->myNodes.end(),n1);
149 it = myNodes.begin();
151 for (int i = 0; i < 8; i++)
153 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
154 if ((int) myChild->myNodes.size() <= getMaxNbNodes() )
155 myChild->myIsLeaf = true;
159 //===================================================================
161 * \brief Return in Result a list of Nodes potentials to be near Node
163 * \param precision - precision used
164 * \param Result - list of Nodes potentials to be near Node
166 //====================================================================
167 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
168 list<const SMDS_MeshNode*>* Result,
169 const double precision)
171 SMESH_TNodeXYZ p(Node);
172 if (isInside(p, precision))
176 Result->insert(Result->end(), myNodes.begin(), myNodes.end());
180 for (int i = 0; i < 8; i++)
182 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
183 myChild->NodesAround(Node, Result, precision);
189 //================================================================================
191 * \brief Return in dist2Nodes nodes mapped to their square distance from Node
192 * Tries to find a closest 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 !!!
198 //================================================================================
200 bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node,
201 map<double, const SMDS_MeshNode*>& dist2Nodes,
204 if ( !dist2Nodes.empty() )
205 precision = min ( precision, sqrt( dist2Nodes.begin()->first ));
206 else if ( precision == 0. )
207 precision = maxSize() / 2;
209 if (isInside(node, precision))
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 ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
219 for (int i = 0; i < 8; i++)
220 if ( i != nodeChild )
221 if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
224 else if ( NbNodes() > 0 )
226 double minDist = precision * precision;
227 TIDSortedNodeSet::iterator nIt = myNodes.begin();
228 for ( ; nIt != myNodes.end(); ++nIt )
230 SMESH_TNodeXYZ p2( *nIt );
231 double dist2 = ( node - p2 ).SquareModulus();
232 if ( dist2 < minDist )
233 dist2Nodes.insert( make_pair( minDist = dist2, p2._node ));
235 // if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
236 // dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
238 // true if an exact overlapping found
239 return ( sqrt( minDist ) <= precision * 1e-12 );
245 //================================================================================
247 * \brief Return a list of nodes close to a point
248 * \param [in] point - point
249 * \param [out] nodes - found nodes
250 * \param [in] precision - allowed distance from \a point
252 //================================================================================
254 void SMESH_OctreeNode::NodesAround(const gp_XYZ& point,
255 std::vector<const SMDS_MeshNode*>& nodes,
258 if ( isInside( point, precision ))
260 if ( isLeaf() && NbNodes() )
262 double minDist2 = precision * precision;
263 TIDSortedNodeSet::iterator nIt = myNodes.begin();
264 for ( ; nIt != myNodes.end(); ++nIt )
266 SMESH_TNodeXYZ p2( *nIt );
267 double dist2 = ( point - p2 ).SquareModulus();
268 if ( dist2 <= minDist2 )
269 nodes.push_back( p2._node );
272 else if ( myChildren )
274 for (int i = 0; i < 8; i++)
276 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
277 myChild->NodesAround( point, nodes, precision);
283 //=============================
285 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
286 * Search for all the nodes in theSetOfNodes
287 * Static Method : no need to create an SMESH_OctreeNode
288 * \param theSetOfNodes - set of nodes we look at, modified during research
289 * \param theGroupsOfNodes - list of nodes closed to each other returned
290 * \param theTolerance - Precision used, default value is 0.00001
291 * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
292 * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
294 //=============================
295 void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
296 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
297 const double theTolerance,
299 const int maxNbNodes)
301 // VSR 14/10/2011: limit max number of the levels in order to avoid endless recursing
302 const int MAX_LEVEL = 10;
303 SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel < 0 ? MAX_LEVEL : maxLevel, maxNbNodes, theTolerance);
304 theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
307 //=============================
309 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
310 * Search for all the nodes in theSetOfNodes
311 * \note The Octree itself is also modified by this method
312 * \param theSetOfNodes - set of nodes we look at, modified during research
313 * \param theTolerance - Precision used
314 * \param theGroupsOfNodes - list of nodes closed to each other returned
316 //=============================
317 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
318 const double theTolerance,
319 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
321 TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
322 list<const SMDS_MeshNode*>::iterator it2;
324 list<const SMDS_MeshNode*> ListOfCoincidentNodes;
327 while (it1 != theSetOfNodes->end())
329 const SMDS_MeshNode * n1 = *it1;
331 // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
332 // Found nodes are also erased from theSetOfNodes
333 FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
335 if ( !ListOfCoincidentNodes.empty() )
337 // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
338 if ( idLess( n1, ListOfCoincidentNodes.front() )) ListOfCoincidentNodes.push_front( n1 );
339 else ListOfCoincidentNodes.push_back ( n1 );
340 ListOfCoincidentNodes.sort( idLess );
341 theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
342 theGroupsOfNodes->back().splice( theGroupsOfNodes->back().end(), ListOfCoincidentNodes );
345 theSetOfNodes->erase(it1);
346 it1 = theSetOfNodes->begin();
350 //======================================================================================
352 * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
353 * \note The Octree itself is also modified by this method
354 * \param Node - We're searching the nodes next to him.
355 * \param SetOfNodes - set of nodes in which we erase the found nodes
356 * \param Result - list of nodes closed to Node
357 * \param precision - Precision used
359 //======================================================================================
360 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
361 TIDSortedNodeSet* SetOfNodes,
362 list<const SMDS_MeshNode*>* Result,
363 const double precision)
365 gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
366 bool isInsideBool = isInside( p1.XYZ(), precision );
370 // I'm only looking in the leaves, since all the nodes are stored there.
373 TIDSortedNodeSet::iterator it = myNodes.begin();
374 const double tol2 = precision * precision;
377 while (it != myNodes.end())
379 const SMDS_MeshNode* n2 = *it;
381 // We're only looking at nodes with a superior Id.
383 //if (Node->GetID() < n2->GetID())
384 if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
386 gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
387 // Distance optimized computation
388 squareBool = (p1.SquareDistance( p2 ) <= tol2);
390 // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
393 Result->insert(Result->begin(), n2);
394 SetOfNodes->erase( n2 );
395 myNodes.erase( *it++ ); // it++ goes forward and returns it's previous position
401 if ( !Result->empty() )
402 myNodes.erase(Node); // JFA: for bug 0020185
406 // If I'm not a leaf, I'm going to see my children !
407 for (int i = 0; i < 8; i++)
409 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
410 myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
416 //================================================================================
418 * \brief Update data according to node movement
420 //================================================================================
422 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
426 TIDSortedNodeSet::iterator pNode = myNodes.find( node );
427 bool nodeInMe = ( pNode != myNodes.end() );
429 bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
431 if ( pointInMe != nodeInMe )
434 myNodes.insert( node );
436 myNodes.erase( node );
439 else if ( myChildren )
441 gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
442 int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid );
443 int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
444 if ( nodeChild != pointChild )
446 ((SMESH_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt );
447 ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
452 //================================================================================
454 * \brief Return iterator over children
456 //================================================================================
457 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
459 return SMESH_OctreeNodeIteratorPtr
460 ( new SMDS_SetIterator< SMESH_OctreeNode*, TBaseTree** >
461 ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
464 //================================================================================
466 * \brief Return nodes iterator
468 //================================================================================
469 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
471 return SMDS_NodeIteratorPtr
472 ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
473 ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));