1 // Copyright (C) 2007-2008 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
22 // SMESH SMESH_OctreeNode : Octree with Nodes set
23 // inherites global class SMESH_Octree
24 // File : SMESH_OctreeNode.cxx
25 // Created : Tue Jan 16 16:00:00 2007
26 // Author : Nicolas Geimer & Aurélien Motteux (OCC)
29 #include "SMESH_OctreeNode.hxx"
31 #include "SMDS_MeshNode.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 set<const SMDS_MeshNode*> & theNodes, const int maxLevel,
47 const int maxNbNodes , const double minBoxSize )
48 :SMESH_Octree(maxLevel,minBoxSize),
49 myMaxNbNodes(maxNbNodes),
52 // We need to compute the first bounding box via a special method
53 computeBoxForFather();
54 myNbNodes = myNodes.size();
55 myIsLeaf = (myLevel == myMaxLevel)||(myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myBox));
56 // All the children (Boxes and Data) are computed in Compute()
60 //==================================================================================
62 * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
64 //==================================================================================
65 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
67 SMESH_OctreeNode * theOctree = new SMESH_OctreeNode();
68 theOctree->myFather = this;
69 theOctree->myLevel = myLevel + 1;
70 theOctree->myMaxLevel = myMaxLevel;
71 theOctree->myMaxNbNodes = myMaxNbNodes;
72 theOctree->myMinBoxSize = myMinBoxSize;
73 theOctree->myNbNodes = 0;
79 //======================================
81 * \brief Compute the first bounding box
83 * We take the max/min coord of the nodes
85 //======================================
86 void SMESH_OctreeNode::computeBoxForFather()
88 set<const SMDS_MeshNode*>::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() );
96 //====================================================================================
98 * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes)
99 * \retval - True if the Octree is a leaf
101 //====================================================================================
102 const bool SMESH_OctreeNode::isLeaf()
107 //====================================================================================
109 * \brief Tells us if Node is inside the current box with the precision "precision"
111 * \param precision - The box is enlarged with this precision
112 * \retval bool - True if Node is in the box within precision
114 //====================================================================================
115 const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double precision )
122 return !(myBox->IsOut(gp_XYZ(X,Y,Z)));
123 Bnd_B3d BoxWithPrecision;
124 getBox(BoxWithPrecision);
125 BoxWithPrecision.Enlarge(precision);
126 Out=BoxWithPrecision.IsOut(gp_XYZ(X,Y,Z));
131 //================================================
133 * \brief Set the data of the children
134 * Shares the father's data with each of his child
136 //================================================
137 void SMESH_OctreeNode::buildChildrenData()
139 gp_XYZ min = myBox->CornerMin();
140 gp_XYZ max = myBox->CornerMax();
141 gp_XYZ mid = (min + max)/2.;
143 set<const SMDS_MeshNode*>::iterator it=myNodes.begin();
145 while( it!=myNodes.end())
147 const SMDS_MeshNode* n1 = *it;
148 ChildBoxNum= (n1->X()>mid.X()) + (n1->Y()>mid.Y())*2 + (n1->Z()>mid.Z())*4;
149 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
150 myChild->myNodes.insert(myChild->myNodes.end(),n1);
154 for (int i = 0; i<8; i++)
156 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
157 myChild->myNbNodes = (myChild->myNodes).size();
158 myChild->myIsLeaf = (myChild->myLevel == myMaxLevel)||(myChild->myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myChild->myBox));
162 //===================================================================
164 * \brief Return in Result a list of Nodes potentials to be near Node
166 * \param precision - precision used
167 * \param Result - list of Nodes potentials to be near Node
169 //====================================================================
170 void SMESH_OctreeNode::NodesAround( const SMDS_MeshNode * Node,
171 list<const SMDS_MeshNode*>* Result, const double precision)
173 if (isInside(Node,precision))
177 Result->insert( Result->end(), myNodes.begin(), myNodes.end() );
183 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
184 myChild->NodesAround( Node, Result, precision);
192 //=============================
194 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
195 * Search for all the nodes in nodes
196 * Static Method : no need to create an SMESH_OctreeNode
197 * \param nodes - set of nodes we look at, modified during research
198 * \param theGroupsOfNodes - list of nodes closed to each other returned
199 * \param theTolerance - Precision used, default value is 0.00001
200 * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
201 * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
203 //=============================
204 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*> nodes,
205 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
206 const double theTolerance, const int maxLevel,
207 const int maxNbNodes)
209 SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(nodes, maxLevel, maxNbNodes, theTolerance);
210 theOctreeNode->FindCoincidentNodes (&nodes, theTolerance, theGroupsOfNodes);
211 delete theOctreeNode;
215 //=============================
217 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
218 * Search for all the nodes in nodes
219 * \param nodes - set of nodes we look at, modified during research
220 * \param theTolerance - Precision used
221 * \param theGroupsOfNodes - list of nodes closed to each other returned
223 //=============================
224 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* nodes,
225 const double theTolerance,
226 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
228 set<const SMDS_MeshNode*>::iterator it1 = nodes->begin();
229 list<const SMDS_MeshNode*>::iterator it2;
231 while (it1 != nodes->end())
233 const SMDS_MeshNode * n1 = *it1;
235 list<const SMDS_MeshNode*> ListofCoincidentNodes;// Initialize the lists via a declaration, it's enough
237 list<const SMDS_MeshNode*> * groupPtr = 0;
239 // Searching for Nodes around n1 and put them in ListofCoincidentNodes
240 FindCoincidentNodes(n1, nodes, &ListofCoincidentNodes, theTolerance);
242 // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
243 for (it2=ListofCoincidentNodes.begin();it2 != ListofCoincidentNodes.end(); it2++)
245 const SMDS_MeshNode* n2 = *it2;
248 theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
249 groupPtr = & theGroupsOfNodes->back();
250 groupPtr->push_back( n1 );
252 if(groupPtr->front()>n2)
253 groupPtr->push_front( n2 );
255 groupPtr->push_back( n2 );
265 //======================================================================================
267 * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
268 * \param Node - We're searching the nodes next to him.
269 * \param SetOfNodes - set of nodes in which we erase the found nodes
270 * \param Result - list of nodes closed to Node
271 * \param precision - Precision used
273 //======================================================================================
274 void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node,
275 set<const SMDS_MeshNode*>* SetOfNodes,
276 list<const SMDS_MeshNode*>* Result,
277 const double precision)
279 bool isInsideBool = isInside(Node,precision);
283 // I'm only looking in the leaves, since all the nodes are stored there.
286 gp_Pnt p1( Node->X(), Node->Y(), Node->Z() );
288 set<const SMDS_MeshNode*> myNodesCopy = myNodes;
289 set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
290 double tol2 = precision * precision;
293 while (it != myNodesCopy.end())
295 const SMDS_MeshNode* n2 = *it;
296 // We're only looking at nodes with a superior Id.
297 if(Node->GetID() < n2->GetID())
299 gp_Pnt p2( n2->X(), n2->Y(), n2->Z() );
300 // Distance optimized computation
301 squareBool = (p1.SquareDistance( p2 ) <= tol2);
303 // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
306 Result->insert(Result->begin(), n2);
307 SetOfNodes->erase( n2 );
311 myNodesCopy.erase( it );
312 it = myNodesCopy.begin();
318 // If I'm not a leaf, I'm going to see my children !
319 for(int i = 0; i < 8; i++)
321 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
322 myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
328 //================================================================================
330 * \brief Return iterator over children
332 //================================================================================
334 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
336 return SMESH_OctreeNodeIteratorPtr
337 ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
338 ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] )));
341 //================================================================================
343 * \brief Return nodes iterator
345 //================================================================================
347 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
349 return SMDS_NodeIteratorPtr
350 ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator >
351 ( myNodes.begin(), myNodes.end() ));