1 // Copyright (C) 2007-2011 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.
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 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)
30 #include "SMESH_OctreeNode.hxx"
32 #include "SMDS_SetIterator.hxx"
37 //===============================================================
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
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),
55 //================================================================================
57 * \brief Constructor used to allocate a child
59 //================================================================================
61 SMESH_OctreeNode::SMESH_OctreeNode (int maxNbNodes):
62 SMESH_Octree(), myMaxNbNodes(maxNbNodes)
66 //==================================================================================
68 * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
70 //==================================================================================
72 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() const
74 return new SMESH_OctreeNode(myMaxNbNodes);
77 //======================================
79 * \brief Compute the first bounding box
81 * We take the max/min coord of the nodes
83 //======================================
85 Bnd_B3d* SMESH_OctreeNode::buildRootBox()
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() );
94 if ( myNodes.size() <= myMaxNbNodes )
100 //====================================================================================
102 * \brief Tells us if Node is inside the current box with the precision "precision"
104 * \param precision - The box is enlarged with this precision
105 * \retval bool - True if Node is in the box within precision
107 //====================================================================================
109 const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, const double precision)
112 return !(getBox().IsOut(p));
113 Bnd_B3d BoxWithPrecision = getBox();
114 BoxWithPrecision.Enlarge(precision);
115 return ! BoxWithPrecision.IsOut(p);
118 //================================================
120 * \brief Set the data of the children
121 * Shares the father's data with each of his child
123 //================================================
124 void SMESH_OctreeNode::buildChildrenData()
126 gp_XYZ min = getBox().CornerMin();
127 gp_XYZ max = getBox().CornerMax();
128 gp_XYZ mid = (min + max)/2.;
130 TIDSortedNodeSet::iterator it = myNodes.begin();
131 while (it != myNodes.end())
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);
138 it = myNodes.begin();
140 for (int i = 0; i < 8; i++)
142 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
143 if ( myChild->myNodes.size() <= myMaxNbNodes )
144 myChild->myIsLeaf = true;
148 //===================================================================
150 * \brief Return in Result a list of Nodes potentials to be near Node
152 * \param precision - precision used
153 * \param Result - list of Nodes potentials to be near Node
155 //====================================================================
156 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
157 list<const SMDS_MeshNode*>* Result,
158 const double precision)
160 gp_XYZ p(Node->X(), Node->Y(), Node->Z());
161 if (isInside(p, precision))
165 Result->insert(Result->end(), myNodes.begin(), myNodes.end());
169 for (int i = 0; i < 8; i++)
171 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
172 myChild->NodesAround(Node, Result, precision);
178 //================================================================================
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
186 //================================================================================
188 bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node,
189 map<double, const SMDS_MeshNode*>& dist2Nodes,
192 if ( !dist2Nodes.empty() )
193 precision = min ( precision, sqrt( dist2Nodes.begin()->first ));
194 else if ( precision == 0. )
195 precision = maxSize() / 2;
197 //gp_XYZ p(node->X(), node->Y(), node->Z());
198 if (isInside(node, precision))
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))
208 for (int i = 0; i < 8; i++)
209 if ( i != nodeChild )
210 if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
213 else if ( NbNodes() > 0 )
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 )
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 ));
225 // if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
226 // dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
228 return ( sqrt( minDist) <= precision * 1e-12 );
234 //=============================
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
245 //=============================
246 void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
247 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
248 const double theTolerance,
250 const int maxNbNodes)
252 SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
253 theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
256 //=============================
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
265 //=============================
266 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
267 const double theTolerance,
268 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
270 TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
271 list<const SMDS_MeshNode*>::iterator it2;
273 while (it1 != theSetOfNodes->end())
275 const SMDS_MeshNode * n1 = *it1;
277 list<const SMDS_MeshNode*> ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough
279 list<const SMDS_MeshNode*> * groupPtr = 0;
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);
285 // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
286 for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++)
288 const SMDS_MeshNode* n2 = *it2;
291 theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
292 groupPtr = & theGroupsOfNodes->back();
293 groupPtr->push_back( n1 );
295 if (groupPtr->front() > n2)
296 groupPtr->push_front( n2 );
298 groupPtr->push_back( n2 );
303 theSetOfNodes->erase(it1);
304 it1 = theSetOfNodes->begin();
308 //======================================================================================
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
317 //======================================================================================
318 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
319 TIDSortedNodeSet* SetOfNodes,
320 list<const SMDS_MeshNode*>* Result,
321 const double precision)
323 gp_XYZ p(Node->X(), Node->Y(), Node->Z());
324 bool isInsideBool = isInside(p, precision);
328 // I'm only looking in the leaves, since all the nodes are stored there.
331 gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
333 TIDSortedNodeSet myNodesCopy = myNodes;
334 TIDSortedNodeSet::iterator it = myNodesCopy.begin();
335 double tol2 = precision * precision;
338 while (it != myNodesCopy.end())
340 const SMDS_MeshNode* n2 = *it;
341 // We're only looking at nodes with a superior Id.
343 //if (Node->GetID() < n2->GetID())
344 if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
346 gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
347 // Distance optimized computation
348 squareBool = (p1.SquareDistance( p2 ) <= tol2);
350 // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
353 Result->insert(Result->begin(), n2);
354 SetOfNodes->erase( n2 );
358 //myNodesCopy.erase( it );
359 //it = myNodesCopy.begin();
362 if (Result->size() > 0)
363 myNodes.erase(Node); // JFA: for bug 0020185
367 // If I'm not a leaf, I'm going to see my children !
368 for (int i = 0; i < 8; i++)
370 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
371 myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
377 //================================================================================
379 * \brief Update data according to node movement
381 //================================================================================
383 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
387 TIDSortedNodeSet::iterator pNode = myNodes.find( node );
388 bool nodeInMe = ( pNode != myNodes.end() );
390 bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
392 if ( pointInMe != nodeInMe )
395 myNodes.insert( node );
397 myNodes.erase( node );
400 else if ( myChildren )
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 )
407 ((SMESH_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt );
408 ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
413 //================================================================================
415 * \brief Return iterator over children
417 //================================================================================
418 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
420 return SMESH_OctreeNodeIteratorPtr
421 ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
422 ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
425 //================================================================================
427 * \brief Return nodes iterator
429 //================================================================================
430 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
432 return SMDS_NodeIteratorPtr
433 ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
434 ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));