1 // SMESH SMESH_OctreeNode : Octree with Nodes set
2 // inherites global class SMESH_Octree
4 // Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
5 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
7 // This library is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU Lesser General Public
9 // License as published by the Free Software Foundation; either
10 // version 2.1 of the License.
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 // Lesser General Public License for more details.
17 // You should have received a copy of the GNU Lesser General Public
18 // License along with this library; if not, write to the Free Software
19 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
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_MeshNode.hxx"
33 #include "SMDS_SetIterator.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 //================================================================
47 SMESH_OctreeNode::SMESH_OctreeNode (const set<const SMDS_MeshNode*> & theNodes, const int maxLevel,
48 const int maxNbNodes , const double minBoxSize )
49 :SMESH_Octree(maxLevel,minBoxSize),
50 myMaxNbNodes(maxNbNodes),
53 // We need to compute the first bounding box via a special method
54 computeBoxForFather();
55 myNbNodes = myNodes.size();
56 myIsLeaf = (myLevel == myMaxLevel)||(myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myBox));
57 // All the children (Boxes and Data) are computed in Compute()
61 //==================================================================================
63 * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
65 //==================================================================================
66 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
68 SMESH_OctreeNode * theOctree = new SMESH_OctreeNode();
69 theOctree->myFather = this;
70 theOctree->myLevel = myLevel + 1;
71 theOctree->myMaxLevel = myMaxLevel;
72 theOctree->myMaxNbNodes = myMaxNbNodes;
73 theOctree->myMinBoxSize = myMinBoxSize;
74 theOctree->myNbNodes = 0;
80 //======================================
82 * \brief Compute the first bounding box
84 * We take the max/min coord of the nodes
86 //======================================
87 void SMESH_OctreeNode::computeBoxForFather()
89 set<const SMDS_MeshNode*>::iterator it=myNodes.begin();
90 for( ;it!=myNodes.end();it++){
91 const SMDS_MeshNode* n1 = *it;
92 gp_XYZ p1( n1->X(), n1->Y(), n1->Z() );
97 //====================================================================================
99 * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes)
100 * \retval - True if the Octree is a leaf
102 //====================================================================================
103 const bool SMESH_OctreeNode::isLeaf()
108 //====================================================================================
110 * \brief Tells us if Node is inside the current box with the precision "precision"
112 * \param precision - The box is enlarged with this precision
113 * \retval bool - True if Node is in the box within precision
115 //====================================================================================
116 const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double precision )
123 return !(myBox->IsOut(gp_XYZ(X,Y,Z)));
124 Bnd_B3d BoxWithPrecision;
125 getBox(BoxWithPrecision);
126 BoxWithPrecision.Enlarge(precision);
127 Out=BoxWithPrecision.IsOut(gp_XYZ(X,Y,Z));
132 //================================================
134 * \brief Set the data of the children
135 * Shares the father's data with each of his child
137 //================================================
138 void SMESH_OctreeNode::buildChildrenData()
140 gp_XYZ min = myBox->CornerMin();
141 gp_XYZ max = myBox->CornerMax();
142 gp_XYZ mid = (min + max)/2.;
144 set<const SMDS_MeshNode*>::iterator it=myNodes.begin();
146 while( it!=myNodes.end())
148 const SMDS_MeshNode* n1 = *it;
149 ChildBoxNum= (n1->X()>mid.X()) + (n1->Y()>mid.Y())*2 + (n1->Z()>mid.Z())*4;
150 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
151 myChild->myNodes.insert(myChild->myNodes.end(),n1);
155 for (int i = 0; i<8; i++)
157 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
158 myChild->myNbNodes = (myChild->myNodes).size();
159 myChild->myIsLeaf = (myChild->myLevel == myMaxLevel)||(myChild->myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myChild->myBox));
163 //===================================================================
165 * \brief Return in Result a list of Nodes potentials to be near Node
167 * \param precision - precision used
168 * \param Result - list of Nodes potentials to be near Node
170 //====================================================================
171 void SMESH_OctreeNode::NodesAround( const SMDS_MeshNode * Node,
172 list<const SMDS_MeshNode*>* Result, const double precision)
174 if (isInside(Node,precision))
178 Result->insert( Result->end(), myNodes.begin(), myNodes.end() );
184 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
185 myChild->NodesAround( Node, Result, precision);
193 //=============================
195 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
196 * Search for all the nodes in nodes
197 * Static Method : no need to create an SMESH_OctreeNode
198 * \param nodes - set of nodes we look at, modified during research
199 * \param theGroupsOfNodes - list of nodes closed to each other returned
200 * \param theTolerance - Precision used, default value is 0.00001
201 * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite)
202 * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
204 //=============================
205 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*> nodes,
206 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
207 const double theTolerance, const int maxLevel,
208 const int maxNbNodes)
210 SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(nodes, maxLevel, maxNbNodes, theTolerance);
211 theOctreeNode->FindCoincidentNodes (&nodes, theTolerance, theGroupsOfNodes);
212 delete theOctreeNode;
216 //=============================
218 * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
219 * Search for all the nodes in nodes
220 * \param nodes - set of nodes we look at, modified during research
221 * \param theTolerance - Precision used
222 * \param theGroupsOfNodes - list of nodes closed to each other returned
224 //=============================
225 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* nodes,
226 const double theTolerance,
227 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
229 set<const SMDS_MeshNode*>::iterator it1 = nodes->begin();
230 list<const SMDS_MeshNode*>::iterator it2;
232 while (it1 != nodes->end())
234 const SMDS_MeshNode * n1 = *it1;
236 list<const SMDS_MeshNode*> ListofCoincidentNodes;// Initialize the lists via a declaration, it's enough
238 list<const SMDS_MeshNode*> * groupPtr = 0;
240 // Searching for Nodes around n1 and put them in ListofCoincidentNodes
241 FindCoincidentNodes(n1, nodes, &ListofCoincidentNodes, theTolerance);
243 // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
244 for (it2=ListofCoincidentNodes.begin();it2 != ListofCoincidentNodes.end(); it2++)
246 const SMDS_MeshNode* n2 = *it2;
249 theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
250 groupPtr = & theGroupsOfNodes->back();
251 groupPtr->push_back( n1 );
253 if(groupPtr->front()>n2)
254 groupPtr->push_front( n2 );
256 groupPtr->push_back( n2 );
266 //======================================================================================
268 * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
269 * \param Node - We're searching the nodes next to him.
270 * \param SetOfNodes - set of nodes in which we erase the found nodes
271 * \param Result - list of nodes closed to Node
272 * \param precision - Precision used
274 //======================================================================================
275 void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node,
276 set<const SMDS_MeshNode*>* SetOfNodes,
277 list<const SMDS_MeshNode*>* Result,
278 const double precision)
280 bool isInsideBool = isInside(Node,precision);
284 // I'm only looking in the leaves, since all the nodes are stored there.
287 gp_Pnt p1( Node->X(), Node->Y(), Node->Z() );
289 set<const SMDS_MeshNode*> myNodesCopy = myNodes;
290 set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
291 double tol2 = precision * precision;
294 while (it != myNodesCopy.end())
296 const SMDS_MeshNode* n2 = *it;
297 // We're only looking at nodes with a superior Id.
298 if(Node->GetID() < n2->GetID())
300 gp_Pnt p2( n2->X(), n2->Y(), n2->Z() );
301 // Distance optimized computation
302 squareBool = (p1.SquareDistance( p2 ) <= tol2);
304 // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
307 Result->insert(Result->begin(), n2);
308 SetOfNodes->erase( n2 );
312 myNodesCopy.erase( it );
313 it = myNodesCopy.begin();
319 // If I'm not a leaf, I'm going to see my children !
320 for(int i = 0; i < 8; i++)
322 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
323 myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
329 //================================================================================
331 * \brief Return iterator over children
333 //================================================================================
335 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
337 return SMESH_OctreeNodeIteratorPtr
338 ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
339 ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] )));
342 //================================================================================
344 * \brief Return nodes iterator
346 //================================================================================
348 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
350 return SMDS_NodeIteratorPtr
351 ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator >
352 ( myNodes.begin(), myNodes.end() ));