1 // Copyright (C) 2007-2010 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 & Aurélien 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 SMDS_MeshNode * Node, const double precision)
111 gp_XYZ p (Node->X(),Node->Y(),Node->Z());
113 return !(getBox().IsOut(p));
114 Bnd_B3d BoxWithPrecision = getBox();
115 BoxWithPrecision.Enlarge(precision);
116 return ! BoxWithPrecision.IsOut(p);
119 //================================================
121 * \brief Set the data of the children
122 * Shares the father's data with each of his child
124 //================================================
125 void SMESH_OctreeNode::buildChildrenData()
127 gp_XYZ min = getBox().CornerMin();
128 gp_XYZ max = getBox().CornerMax();
129 gp_XYZ mid = (min + max)/2.;
131 TIDSortedNodeSet::iterator it = myNodes.begin();
132 while (it != myNodes.end())
134 const SMDS_MeshNode* n1 = *it;
135 int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid );
136 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
137 myChild->myNodes.insert(myChild->myNodes.end(),n1);
139 it = myNodes.begin();
141 for (int i = 0; i < 8; i++)
143 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
144 if ( myChild->myNodes.size() <= myMaxNbNodes )
145 myChild->myIsLeaf = true;
149 //===================================================================
151 * \brief Return in Result a list of Nodes potentials to be near Node
153 * \param precision - precision used
154 * \param Result - list of Nodes potentials to be near Node
156 //====================================================================
157 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
158 list<const SMDS_MeshNode*>* Result,
159 const double precision)
161 if (isInside(Node,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 SMDS_MeshNode * 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 if (isInside(node,precision))
201 // first check a child containing node
202 gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
203 int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid );
204 if ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
207 for (int i = 0; i < 8; i++)
208 if ( i != nodeChild )
209 if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
212 else if ( NbNodes() > 0 )
214 double minDist = precision * precision;
215 gp_Pnt p1 ( node->X(), node->Y(), node->Z() );
216 TIDSortedNodeSet::iterator nIt = myNodes.begin();
217 for ( ; nIt != myNodes.end(); ++nIt )
219 gp_Pnt p2 ( (*nIt)->X(), (*nIt)->Y(), (*nIt)->Z() );
220 double dist2 = p1.SquareDistance( p2 );
221 if ( dist2 < minDist )
222 dist2Nodes.insert( make_pair( minDist = dist2, *nIt ));
224 // if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
225 // dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
227 return ( sqrt( minDist) <= precision * 1e-12 );
233 //=============================
235 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
236 * Search for all the nodes in theSetOfNodes
237 * Static Method : no need to create an SMESH_OctreeNode
238 * \param theSetOfNodes - set of nodes we look at, modified during research
239 * \param theGroupsOfNodes - list of nodes closed to each other returned
240 * \param theTolerance - Precision used, default value is 0.00001
241 * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
242 * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
244 //=============================
245 void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
246 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
247 const double theTolerance,
249 const int maxNbNodes)
251 SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
252 theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
255 //=============================
257 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
258 * Search for all the nodes in theSetOfNodes
259 * \note The Octree itself is also modified by this method
260 * \param theSetOfNodes - set of nodes we look at, modified during research
261 * \param theTolerance - Precision used
262 * \param theGroupsOfNodes - list of nodes closed to each other returned
264 //=============================
265 void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
266 const double theTolerance,
267 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
269 TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
270 list<const SMDS_MeshNode*>::iterator it2;
272 while (it1 != theSetOfNodes->end())
274 const SMDS_MeshNode * n1 = *it1;
276 list<const SMDS_MeshNode*> ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough
278 list<const SMDS_MeshNode*> * groupPtr = 0;
280 // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
281 // Found nodes are also erased from theSetOfNodes
282 FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
284 // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
285 for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++)
287 const SMDS_MeshNode* n2 = *it2;
290 theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
291 groupPtr = & theGroupsOfNodes->back();
292 groupPtr->push_back( n1 );
294 if (groupPtr->front() > n2)
295 groupPtr->push_front( n2 );
297 groupPtr->push_back( n2 );
302 theSetOfNodes->erase(it1);
303 it1 = theSetOfNodes->begin();
307 //======================================================================================
309 * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
310 * \note The Octree itself is also modified by this method
311 * \param Node - We're searching the nodes next to him.
312 * \param SetOfNodes - set of nodes in which we erase the found nodes
313 * \param Result - list of nodes closed to Node
314 * \param precision - Precision used
316 //======================================================================================
317 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
318 TIDSortedNodeSet* SetOfNodes,
319 list<const SMDS_MeshNode*>* Result,
320 const double precision)
322 bool isInsideBool = isInside(Node,precision);
326 // I'm only looking in the leaves, since all the nodes are stored there.
329 gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
331 TIDSortedNodeSet myNodesCopy = myNodes;
332 TIDSortedNodeSet::iterator it = myNodesCopy.begin();
333 double tol2 = precision * precision;
336 while (it != myNodesCopy.end())
338 const SMDS_MeshNode* n2 = *it;
339 // We're only looking at nodes with a superior Id.
341 //if (Node->GetID() < n2->GetID())
342 if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
344 gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
345 // Distance optimized computation
346 squareBool = (p1.SquareDistance( p2 ) <= tol2);
348 // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
351 Result->insert(Result->begin(), n2);
352 SetOfNodes->erase( n2 );
356 //myNodesCopy.erase( it );
357 //it = myNodesCopy.begin();
360 if (Result->size() > 0)
361 myNodes.erase(Node); // JFA: for bug 0020185
365 // If I'm not a leaf, I'm going to see my children !
366 for (int i = 0; i < 8; i++)
368 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
369 myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
375 //================================================================================
377 * \brief Update data according to node movement
379 //================================================================================
381 void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
385 TIDSortedNodeSet::iterator pNode = myNodes.find( node );
386 bool nodeInMe = ( pNode != myNodes.end() );
388 SMDS_MeshNode pointNode( toPnt.X(), toPnt.Y(), toPnt.Z() );
389 bool pointInMe = isInside( &pointNode, 1e-10 );
391 if ( pointInMe != nodeInMe )
394 myNodes.insert( node );
396 myNodes.erase( node );
399 else if ( myChildren )
401 gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
402 int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid );
403 int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
404 if ( nodeChild != pointChild )
406 ((SMESH_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt );
407 ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
412 //================================================================================
414 * \brief Return iterator over children
416 //================================================================================
417 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
419 return SMESH_OctreeNodeIteratorPtr
420 ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
421 ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
424 //================================================================================
426 * \brief Return nodes iterator
428 //================================================================================
429 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
431 return SMDS_NodeIteratorPtr
432 ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
433 ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));