1 // Copyright (C) 2007-2021 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_MeshAlgos.hxx"
34 #include "SMESH_TypeDefs.hxx"
40 //===============================================================
42 * \brief Constructor : Build all the Octree using Compute()
43 * \param theNodes - Set of nodes, the Octree is built from this nodes
44 * \param maxLevel - Maximum level for the leaves
45 * \param maxNbNodes - Maximum number of nodes, a leaf can contain
46 * \param minBoxSize - Minimal size of the Octree Box
48 //================================================================
50 SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel,
51 const int maxNbNodes , const double minBoxSize )
52 :SMESH_Octree( new Limit( maxLevel,minBoxSize,maxNbNodes)),
53 myNodes( theNodes.begin(), theNodes.end() )
58 //================================================================================
60 * \brief Constructor used to allocate a child
62 //================================================================================
64 SMESH_OctreeNode::SMESH_OctreeNode ():SMESH_Octree()
68 //================================================================================
70 * \brief Return max number of nodes in a tree leaf
72 //================================================================================
74 int SMESH_OctreeNode::getMaxNbNodes() const
76 return ((Limit*)myLimit)->myMaxNbNodes;
79 //==================================================================================
81 * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
83 //==================================================================================
85 SMESH_Octree* SMESH_OctreeNode::newChild() const
87 return new SMESH_OctreeNode();
90 //======================================
92 * \brief Compute the first bounding box
94 * We take the max/min coord of the nodes
96 //======================================
98 Bnd_B3d* SMESH_OctreeNode::buildRootBox()
100 Bnd_B3d* box = new Bnd_B3d;
101 for ( size_t i = 0; i < myNodes.size(); ++i )
102 box->Add( SMESH_NodeXYZ( myNodes[ i ]));
104 if ((int) myNodes.size() <= getMaxNbNodes() )
110 //====================================================================================
112 * \brief Tells us if Node is inside the current box with the precision "precision"
114 * \param precision - The box is enlarged with this precision
115 * \retval bool - True if Node is in the box within precision
117 //====================================================================================
119 bool SMESH_OctreeNode::isInside ( const gp_XYZ& p, const double precision )
121 if ( precision <= 0.)
122 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 //================================================
136 void SMESH_OctreeNode::buildChildrenData()
138 gp_XYZ min = getBox()->CornerMin();
139 gp_XYZ max = getBox()->CornerMax();
140 gp_XYZ mid = (min + max)/2.;
142 for ( int i = 0; i < 8; i++ )
144 SMESH_OctreeNode* myChild = static_cast<SMESH_OctreeNode*>( myChildren[ i ]);
145 myChild->myNodes.reserve( myNodes.size() / 8 );
148 for ( size_t i = 0; i < myNodes.size(); ++i )
150 SMESH_NodeXYZ n = myNodes[ i ];
151 int ChildBoxNum = getChildIndex( n.X(), n.Y(), n.Z(), mid );
152 SMESH_OctreeNode* myChild = static_cast<SMESH_OctreeNode*>( myChildren[ ChildBoxNum ]);
153 myChild->myNodes.push_back( myNodes[ i ]);
155 SMESHUtils::FreeVector( myNodes );
157 for ( int i = 0; i < 8; i++ )
159 SMESH_OctreeNode* myChild = static_cast<SMESH_OctreeNode*>( myChildren[ i ]);
160 if ((int) myChild->myNodes.size() <= getMaxNbNodes() )
162 myChild->myIsLeaf = true;
163 if ( myChild->myNodes.empty() )
164 SMESHUtils::FreeVector( myChild->myNodes );
169 //===================================================================
171 * \brief Return in Result a list of Nodes potentials to be near Node
173 * \param precision - precision used
174 * \param Result - list of Nodes potentials to be near Node
176 //====================================================================
178 void SMESH_OctreeNode::AllNodesAround (const SMDS_MeshNode * Node,
179 std::vector<const SMDS_MeshNode*>* Result,
180 const double precision)
182 SMESH_NodeXYZ p = Node;
183 if ( isInside( p, precision ))
187 Result->insert( Result->end(), myNodes.begin(), myNodes.end() );
191 for ( int i = 0; i < 8; i++ )
193 SMESH_OctreeNode* myChild = static_cast<SMESH_OctreeNode*> (myChildren[i]);
194 myChild->AllNodesAround( Node, Result, precision );
200 //================================================================================
202 * \brief Return in dist2Nodes nodes mapped to their square distance from Node
203 * Tries to find a closest node.
204 * \param node - node to find nodes closest to
205 * \param dist2Nodes - map of found nodes and their distances
206 * \param precision - radius of a sphere to check nodes inside
207 * \retval bool - true if an exact overlapping found !!!
209 //================================================================================
211 bool SMESH_OctreeNode::NodesAround(const gp_XYZ & node,
212 map<double, const SMDS_MeshNode*>& dist2Nodes,
215 if ( !dist2Nodes.empty() )
216 precision = min ( precision, sqrt( dist2Nodes.begin()->first ));
217 else if ( precision == 0. )
218 precision = maxSize() / 2;
220 if ( isInside( node, precision ))
224 // first check a child containing node
225 gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
226 int nodeChild = getChildIndex( node.X(), node.Y(), node.Z(), mid );
227 if ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
230 for (int i = 0; i < 8; i++)
231 if ( i != nodeChild )
232 if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
235 else if ( NbNodes() > 0 )
237 double minDist = precision * precision;
238 for ( size_t i = 0; i < myNodes.size(); ++i )
240 SMESH_NodeXYZ p2 = myNodes[ i ];
241 double dist2 = ( node - p2 ).SquareModulus();
242 if ( dist2 < minDist )
243 dist2Nodes.insert( std::make_pair( minDist = dist2, myNodes[ i ] ));
245 // if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
246 // dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
248 // true if an exact overlapping found
249 return ( sqrt( minDist ) <= precision * 1e-12 );
255 //================================================================================
257 * \brief Return a list of nodes close to a point
258 * \param [in] point - point
259 * \param [out] nodes - found nodes
260 * \param [in] precision - allowed distance from \a point
262 //================================================================================
264 void SMESH_OctreeNode::NodesAround(const gp_XYZ& point,
265 std::vector<const SMDS_MeshNode*>& nodes,
268 if ( isInside( point, precision ))
270 if ( isLeaf() && NbNodes() )
272 double minDist2 = precision * precision;
273 for ( size_t i = 0; i < myNodes.size(); ++i )
275 SMESH_NodeXYZ p2 = myNodes[ i ];
276 double dist2 = ( point - p2 ).SquareModulus();
277 if ( dist2 <= minDist2 )
278 nodes.push_back( myNodes[ i ] );
281 else if ( myChildren )
283 for (int i = 0; i < 8; i++)
285 SMESH_OctreeNode* myChild = static_cast<SMESH_OctreeNode*>( myChildren[ i ]);
286 myChild->NodesAround( point, nodes, precision );
292 //=============================
294 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
295 * Search for all the nodes in theSetOfNodes
296 * Static Method : no need to create an SMESH_OctreeNode
297 * \param theSetOfNodes - set of nodes we look at, modified during research
298 * \param theGroupsOfNodes - list of nodes closed to each other returned
299 * \param theTolerance - Precision used, default value is 0.00001
300 * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
301 * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
303 //=============================
305 void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
306 TListOfNodeLists* theGroupsOfNodes,
307 const double theTolerance,
309 const int maxNbNodes)
311 // VSR 14/10/2011: limit max number of the levels in order to avoid endless recursion
312 const int MAX_LEVEL = 10;
313 SMESH_OctreeNode theOctreeNode(theSetOfNodes,
314 maxLevel < 0 ? MAX_LEVEL : maxLevel,
317 theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
320 //=============================
322 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
323 * Search for all the nodes in theSetOfNodes
324 * \note The Octree itself is also modified by this method
325 * \param theSetOfNodes - set of nodes we look at, modified during research
326 * \param theTolerance - Precision used
327 * \param theGroupsOfNodes - list of nodes closed to each other returned
329 //=============================
331 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
332 const double theTolerance,
333 TListOfNodeLists* theGroupsOfNodes )
335 // un-mark all nodes; we mark nodes added to theGroupsOfNodes
336 SMESH_MeshAlgos::MarkElems( SMESHUtils::elemSetIterator( *theSetOfNodes ), false );
338 vector<const SMDS_MeshNode*> coincidentNodes;
341 TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
342 for ( ; it1 != theSetOfNodes->end(); ++it1 )
344 const SMDS_MeshNode * n1 = *it1;
345 if ( n1->isMarked() )
347 n1->setIsMarked( true );
349 // Searching for Nodes around n1 and put them in coincidentNodes.
350 // Found nodes are also erased from theSetOfNodes
351 coincidentNodes.clear();
352 findCoincidentNodes( n1, theSetOfNodes, &coincidentNodes, theTolerance );
354 if ( !coincidentNodes.empty() )
356 // We build a list {n1 + his neighbors} and add this list in theGroupsOfNodes
357 std::sort( coincidentNodes.begin(), coincidentNodes.end(), idLess );
358 list<const SMDS_MeshNode*> newGroup;
359 newGroup.push_back( n1 );
360 newGroup.insert( newGroup.end(), coincidentNodes.begin(), coincidentNodes.end() );
362 theGroupsOfNodes->emplace_back( newGroup );
367 //======================================================================================
369 * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
370 * \note The Octree itself is also modified by this method
371 * \param Node - We're searching the nodes next to him.
372 * \param SetOfNodes - set of nodes in which we erase the found nodes
373 * \param Result - list of nodes closed to Node
374 * \param precision - Precision used
376 //======================================================================================
378 void SMESH_OctreeNode::findCoincidentNodes (const SMDS_MeshNode * Node,
379 TIDSortedNodeSet* SetOfNodes,
380 std::vector<const SMDS_MeshNode*>* Result,
381 const double precision)
383 SMESH_NodeXYZ p1 = Node;
385 if ( isInside( p1, precision ))
387 // I'm only looking in the leaves, since all the nodes are stored there.
390 const double tol2 = precision * precision;
392 for ( size_t i = 0; i < myNodes.size(); ++i )
394 if ( myNodes[ i ]->isMarked() ) // coincident node already found
397 //if ( Node != myNodes[ i ]) // JFA: for bug 0020185
399 // If n2 inside the SquareDistance, we add it in Result
400 bool coincide = ( p1.SquareDistance( myNodes[ i ]) <= tol2 );
403 Result->push_back ( myNodes[ i ]);
404 myNodes[ i ]->setIsMarked( true );
411 // If I'm not a leaf, I'm going to see my children !
412 for ( int i = 0; i < 8; i++ )
414 SMESH_OctreeNode* myChild = static_cast<SMESH_OctreeNode*> (myChildren[i]);
415 myChild->findCoincidentNodes( Node, SetOfNodes, Result, precision );
421 //================================================================================
423 * \brief Update data according to node movement
425 //================================================================================
427 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
431 std::vector< const SMDS_MeshNode* >::iterator pNode =
432 std::find( myNodes.begin(), myNodes.end(), node );
434 bool nodeInMe = ( pNode != myNodes.end() );
435 bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
437 if ( pointInMe != nodeInMe )
440 myNodes.push_back( node );
442 myNodes.erase( pNode );
445 else if ( myChildren )
447 gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
448 int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid );
449 int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
450 if ( nodeChild != pointChild )
452 ((SMESH_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt );
453 ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
458 //================================================================================
460 * \brief Return iterator over children
462 //================================================================================
464 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
466 return SMESH_OctreeNodeIteratorPtr
467 ( new SMDS_SetIterator< SMESH_OctreeNode*, TBaseTree** >
468 ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
471 //================================================================================
473 * \brief Return nodes iterator
475 //================================================================================
477 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
479 return boost::make_shared< SMDS_NodeVectorIterator >( myNodes.begin(), myNodes.end());