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
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) ||
57 (myNbNodes <= myMaxNbNodes) ||
58 (maxSize(myBox) <= myMinBoxSize));
59 // All the children (Boxes and Data) are computed in Compute()
63 //==================================================================================
65 * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
67 //==================================================================================
68 SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
70 SMESH_OctreeNode * theOctree = new SMESH_OctreeNode();
71 theOctree->myFather = this;
72 theOctree->myLevel = myLevel + 1;
73 theOctree->myMaxLevel = myMaxLevel;
74 theOctree->myMaxNbNodes = myMaxNbNodes;
75 theOctree->myMinBoxSize = myMinBoxSize;
76 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)
118 double X = Node->X();
119 double Y = Node->Y();
120 double Z = Node->Z();
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));
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);
152 it = myNodes.begin();
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) ||
159 (myChild->myNbNodes <= myMaxNbNodes) ||
160 (maxSize(myChild->myBox) <= myMinBoxSize));
164 //===================================================================
166 * \brief Return in Result a list of Nodes potentials to be near Node
168 * \param precision - precision used
169 * \param Result - list of Nodes potentials to be near Node
171 //====================================================================
172 void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node,
173 list<const SMDS_MeshNode*>* Result,
174 const double precision)
176 if (isInside(Node,precision))
180 Result->insert(Result->end(), myNodes.begin(), myNodes.end());
184 for (int i = 0; i < 8; i++)
186 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
187 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 theSetOfNodes
197 * Static Method : no need to create an SMESH_OctreeNode
198 * \param theSetOfNodes - 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*> theSetOfNodes,
206 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
207 const double theTolerance,
209 const int maxNbNodes)
211 SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
212 theOctreeNode->FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
213 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 theSetOfNodes
220 * \note The Octree itself is also modified by this method
221 * \param theSetOfNodes - set of nodes we look at, modified during research
222 * \param theTolerance - Precision used
223 * \param theGroupsOfNodes - list of nodes closed to each other returned
225 //=============================
226 void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* theSetOfNodes,
227 const double theTolerance,
228 list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
230 set<const SMDS_MeshNode*>::iterator it1 = theSetOfNodes->begin();
231 list<const SMDS_MeshNode*>::iterator it2;
233 while (it1 != theSetOfNodes->end())
235 const SMDS_MeshNode * n1 = *it1;
237 list<const SMDS_MeshNode*> ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough
239 list<const SMDS_MeshNode*> * groupPtr = 0;
241 // Searching for Nodes around n1 and put them in ListofCoincidentNodes.
242 // Found nodes are also erased from theSetOfNodes
243 FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance);
245 // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes
246 for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++)
248 const SMDS_MeshNode* n2 = *it2;
251 theGroupsOfNodes->push_back( list<const SMDS_MeshNode*>() );
252 groupPtr = & theGroupsOfNodes->back();
253 groupPtr->push_back( n1 );
255 if (groupPtr->front() > n2)
256 groupPtr->push_front( n2 );
258 groupPtr->push_back( n2 );
263 theSetOfNodes->erase(it1);
264 it1 = theSetOfNodes->begin();
268 //======================================================================================
270 * \brief Return a list of nodes closed to Node and remove it from SetOfNodes
271 * \note The Octree itself is also modified by this method
272 * \param Node - We're searching the nodes next to him.
273 * \param SetOfNodes - set of nodes in which we erase the found nodes
274 * \param Result - list of nodes closed to Node
275 * \param precision - Precision used
277 //======================================================================================
278 void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
279 set<const SMDS_MeshNode*>* SetOfNodes,
280 list<const SMDS_MeshNode*>* Result,
281 const double precision)
283 bool isInsideBool = isInside(Node,precision);
287 // I'm only looking in the leaves, since all the nodes are stored there.
290 gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
292 set<const SMDS_MeshNode*> myNodesCopy = myNodes;
293 set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
294 double tol2 = precision * precision;
297 while (it != myNodesCopy.end())
299 const SMDS_MeshNode* n2 = *it;
300 // We're only looking at nodes with a superior Id.
302 //if (Node->GetID() < n2->GetID())
303 if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185
305 gp_Pnt p2 (n2->X(), n2->Y(), n2->Z());
306 // Distance optimized computation
307 squareBool = (p1.SquareDistance( p2 ) <= tol2);
309 // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes
312 Result->insert(Result->begin(), n2);
313 SetOfNodes->erase( n2 );
317 //myNodesCopy.erase( it );
318 //it = myNodesCopy.begin();
321 if (Result->size() > 0)
322 myNodes.erase(Node); // JFA: for bug 0020185
326 // If I'm not a leaf, I'm going to see my children !
327 for (int i = 0; i < 8; i++)
329 SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
330 myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision);
336 //================================================================================
338 * \brief Return iterator over children
340 //================================================================================
341 SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator()
343 return SMESH_OctreeNodeIteratorPtr
344 ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
345 ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] )));
348 //================================================================================
350 * \brief Return nodes iterator
352 //================================================================================
353 SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
355 return SMDS_NodeIteratorPtr
356 ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator >
357 ( myNodes.begin(), myNodes.end() ));