X-Git-Url: http://git.salome-platform.org/gitweb/?a=blobdiff_plain;f=src%2FSMESH%2FSMESH_OctreeNode.cxx;h=ecff551844d54202b860c4a0a4d436a2b6cb5b6a;hb=062f1da5dde14e9ca8755c2eda44cbe8850f1d3a;hp=52f1e3071799bb048975583044fe08ad98c4b7b5;hpb=984c4ffdd7df62aeaedc544cd0b8e64ff8f53f1a;p=modules%2Fsmesh.git diff --git a/src/SMESH/SMESH_OctreeNode.cxx b/src/SMESH/SMESH_OctreeNode.cxx index 52f1e3071..ecff55184 100644 --- a/src/SMESH/SMESH_OctreeNode.cxx +++ b/src/SMESH/SMESH_OctreeNode.cxx @@ -1,7 +1,6 @@ -// SMESH SMESH_OctreeNode : Octree with Nodes set -// inherites global class SMESH_Octree +// Copyright (C) 2007-2011 CEA/DEN, EDF R&D, OPEN CASCADE // -// Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS // // This library is free software; you can redistribute it and/or @@ -18,18 +17,20 @@ // License along with this library; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA // -// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com -// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com // -// -// File : SMESH_OctreeNode.cxx -// Created : Tue Jan 16 16:00:00 2007 -// Author : Nicolas Geimer & Aurélien Motteux (OCC) -// Module : SMESH +// SMESH SMESH_OctreeNode : Octree with Nodes set +// inherites global class SMESH_Octree +// File : SMESH_OctreeNode.cxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : SMESH +// #include "SMESH_OctreeNode.hxx" + +#include "SMDS_SetIterator.hxx" #include -#include using namespace std; @@ -42,18 +43,24 @@ using namespace std; * \param minBoxSize - Minimal size of the Octree Box */ //================================================================ -SMESH_OctreeNode::SMESH_OctreeNode (set theNodes, const int maxLevel, +SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel, const int maxNbNodes , const double minBoxSize ) - :SMESH_Octree(maxLevel,minBoxSize), + :SMESH_Octree( new SMESH_Octree::Limit( maxLevel,minBoxSize)), myMaxNbNodes(maxNbNodes), myNodes(theNodes) { - // We need to compute the first bounding box via a special method - computeBoxForFather(); - myNbNodes = myNodes.size(); - myIsLeaf = (myLevel == myMaxLevel)||(myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myBox)); - // All the children (Boxes and Data) are computed in Compute() - Compute(); + compute(); +} + +//================================================================================ +/*! + * \brief Constructor used to allocate a child + */ +//================================================================================ + +SMESH_OctreeNode::SMESH_OctreeNode (int maxNbNodes): + SMESH_Octree(), myMaxNbNodes(maxNbNodes) +{ } //================================================================================== @@ -61,46 +68,33 @@ SMESH_OctreeNode::SMESH_OctreeNode (set theNodes, const in * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren() */ //================================================================================== -SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() + +SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() const { - SMESH_OctreeNode * theOctree = new SMESH_OctreeNode(); - theOctree->myFather = this; - theOctree->myLevel = myLevel + 1; - theOctree->myMaxLevel = myMaxLevel; - theOctree->myMaxNbNodes = myMaxNbNodes; - theOctree->myMinBoxSize = myMinBoxSize; - theOctree->myNbNodes = 0; - return theOctree; + return new SMESH_OctreeNode(myMaxNbNodes); } - - //====================================== /*! * \brief Compute the first bounding box * - * We take the max/min coord of the nodes + * We take the max/min coord of the nodes */ //====================================== -void SMESH_OctreeNode::computeBoxForFather() + +Bnd_B3d* SMESH_OctreeNode::buildRootBox() { - set::iterator it=myNodes.begin(); - for( ;it!=myNodes.end();it++){ + Bnd_B3d* box = new Bnd_B3d; + TIDSortedNodeSet::iterator it = myNodes.begin(); + for (; it != myNodes.end(); it++) { const SMDS_MeshNode* n1 = *it; gp_XYZ p1( n1->X(), n1->Y(), n1->Z() ); - myBox->Add(p1); + box->Add(p1); } -} + if ( myNodes.size() <= myMaxNbNodes ) + myIsLeaf = true; -//==================================================================================== -/*! - * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes) - * \retval - True if the Octree is a leaf - */ -//==================================================================================== -const bool SMESH_OctreeNode::isLeaf() -{ - return myIsLeaf; + return box; } //==================================================================================== @@ -111,23 +105,17 @@ const bool SMESH_OctreeNode::isLeaf() * \retval bool - True if Node is in the box within precision */ //==================================================================================== -const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double precision ) + +const bool SMESH_OctreeNode::isInside (const SMDS_MeshNode * Node, const double precision) { - double X=Node->X(); - double Y=Node->Y(); - double Z=Node->Z(); - bool Out = 1 ; - if (precision<=0.) - return !(myBox->IsOut(gp_XYZ(X,Y,Z))); - Bnd_B3d * BoxWithPrecision = new Bnd_B3d(); - getBox(BoxWithPrecision); - BoxWithPrecision->Enlarge(precision); - Out=BoxWithPrecision->IsOut(gp_XYZ(X,Y,Z)); - delete BoxWithPrecision; - return !(Out); + gp_XYZ p (Node->X(),Node->Y(),Node->Z()); + if (precision <= 0.) + return !(getBox().IsOut(p)); + Bnd_B3d BoxWithPrecision = getBox(); + BoxWithPrecision.Enlarge(precision); + return ! BoxWithPrecision.IsOut(p); } - //================================================ /*! * \brief Set the data of the children @@ -136,26 +124,25 @@ const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double p //================================================ void SMESH_OctreeNode::buildChildrenData() { - gp_XYZ min = myBox->CornerMin(); - gp_XYZ max = myBox->CornerMax(); + gp_XYZ min = getBox().CornerMin(); + gp_XYZ max = getBox().CornerMax(); gp_XYZ mid = (min + max)/2.; - set::iterator it=myNodes.begin(); - int ChildBoxNum; - while( it!=myNodes.end()) + TIDSortedNodeSet::iterator it = myNodes.begin(); + while (it != myNodes.end()) { const SMDS_MeshNode* n1 = *it; - ChildBoxNum= (n1->X()>mid.X()) + (n1->Y()>mid.Y())*2 + (n1->Z()>mid.Z())*4; + int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid ); SMESH_OctreeNode* myChild = dynamic_cast (myChildren[ChildBoxNum]); myChild->myNodes.insert(myChild->myNodes.end(),n1); myNodes.erase( it ); - it=myNodes.begin(); + it = myNodes.begin(); } - for (int i = 0; i<8; i++) + for (int i = 0; i < 8; i++) { SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); - myChild->myNbNodes = (myChild->myNodes).size(); - myChild->myIsLeaf = (myChild->myLevel == myMaxLevel)||(myChild->myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myChild->myBox)); + if ( myChild->myNodes.size() <= myMaxNbNodes ) + myChild->myIsLeaf = true; } } @@ -167,80 +154,135 @@ void SMESH_OctreeNode::buildChildrenData() * \param Result - list of Nodes potentials to be near Node */ //==================================================================== -void SMESH_OctreeNode::NodesAround( const SMDS_MeshNode * Node, - list* Result, const double precision) +void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node, + list* Result, + const double precision) { if (isInside(Node,precision)) { - if (myIsLeaf) + if (isLeaf()) { - Result->insert( Result->end(), myNodes.begin(), myNodes.end() ); + Result->insert(Result->end(), myNodes.begin(), myNodes.end()); } else { - for(int i=0;i<8;i++) + for (int i = 0; i < 8; i++) { SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); - myChild->NodesAround( Node, Result, precision); + myChild->NodesAround(Node, Result, precision); } } } } +//================================================================================ +/*! + * \brief Return in dist2Nodes nodes mapped to their square distance from Node + * \param node - node to find nodes closest to + * \param dist2Nodes - map of found nodes and their distances + * \param precision - radius of a sphere to check nodes inside + * \retval bool - true if an exact overlapping found + */ +//================================================================================ + +bool SMESH_OctreeNode::NodesAround(const SMDS_MeshNode * node, + map& dist2Nodes, + double precision) +{ + if ( !dist2Nodes.empty() ) + precision = min ( precision, sqrt( dist2Nodes.begin()->first )); + else if ( precision == 0. ) + precision = maxSize() / 2; + + if (isInside(node,precision)) + { + if (!isLeaf()) + { + // first check a child containing node + gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.; + int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid ); + if ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision)) + return true; + + for (int i = 0; i < 8; i++) + if ( i != nodeChild ) + if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision)) + return true; + } + else if ( NbNodes() > 0 ) + { + double minDist = precision * precision; + gp_Pnt p1 ( node->X(), node->Y(), node->Z() ); + TIDSortedNodeSet::iterator nIt = myNodes.begin(); + for ( ; nIt != myNodes.end(); ++nIt ) + { + gp_Pnt p2 ( (*nIt)->X(), (*nIt)->Y(), (*nIt)->Z() ); + double dist2 = p1.SquareDistance( p2 ); + if ( dist2 < minDist ) + dist2Nodes.insert( make_pair( minDist = dist2, *nIt )); + } +// if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes +// dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end()); + return ( sqrt( minDist) <= precision * 1e-12 ); + } + } + return false; +} //============================= /*! * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance - * Search for all the nodes in nodes + * Search for all the nodes in theSetOfNodes * Static Method : no need to create an SMESH_OctreeNode - * \param nodes - set of nodes we look at, modified during research + * \param theSetOfNodes - set of nodes we look at, modified during research * \param theGroupsOfNodes - list of nodes closed to each other returned * \param theTolerance - Precision used, default value is 0.00001 * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite) * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5 */ //============================= -void SMESH_OctreeNode::FindCoincidentNodes ( set nodes, - list< list< const SMDS_MeshNode*> >* theGroupsOfNodes, - const double theTolerance, const int maxLevel, - const int maxNbNodes) +void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes, + list< list< const SMDS_MeshNode*> >* theGroupsOfNodes, + const double theTolerance, + const int maxLevel, + const int maxNbNodes) { - SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(nodes, maxLevel, maxNbNodes, theTolerance); - theOctreeNode->FindCoincidentNodes (&nodes, theTolerance, theGroupsOfNodes); - delete theOctreeNode; + SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance); + theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes); } - //============================= /*! * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance - * Search for all the nodes in nodes - * \param nodes - set of nodes we look at, modified during research + * Search for all the nodes in theSetOfNodes + * \note The Octree itself is also modified by this method + * \param theSetOfNodes - set of nodes we look at, modified during research * \param theTolerance - Precision used * \param theGroupsOfNodes - list of nodes closed to each other returned */ //============================= -void SMESH_OctreeNode::FindCoincidentNodes ( set* nodes, - const double theTolerance, +void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes, + const double theTolerance, list< list< const SMDS_MeshNode*> >* theGroupsOfNodes) { - set::iterator it1 = nodes->begin(); + TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin(); list::iterator it2; - while (it1 != nodes->end()) + while (it1 != theSetOfNodes->end()) { const SMDS_MeshNode * n1 = *it1; - list ListofCoincidentNodes;// Initialize the lists via a declaration, it's enough + list ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough list * groupPtr = 0; - // Searching for Nodes around n1 and put them in ListofCoincidentNodes - FindCoincidentNodes(n1, nodes, &ListofCoincidentNodes, theTolerance); + // Searching for Nodes around n1 and put them in ListofCoincidentNodes. + // Found nodes are also erased from theSetOfNodes + FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance); // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes - for (it2=ListofCoincidentNodes.begin();it2 != ListofCoincidentNodes.end(); it2++) + for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++) { const SMDS_MeshNode* n2 = *it2; if ( !groupPtr ) @@ -249,30 +291,31 @@ void SMESH_OctreeNode::FindCoincidentNodes ( set* nodes, groupPtr = & theGroupsOfNodes->back(); groupPtr->push_back( n1 ); } - if(groupPtr->front()>n2) + if (groupPtr->front() > n2) groupPtr->push_front( n2 ); else groupPtr->push_back( n2 ); } - if(groupPtr != 0) + if (groupPtr != 0) groupPtr->sort(); - nodes->erase(it1); - it1=nodes->begin(); + theSetOfNodes->erase(it1); + it1 = theSetOfNodes->begin(); } } //====================================================================================== /*! * \brief Return a list of nodes closed to Node and remove it from SetOfNodes + * \note The Octree itself is also modified by this method * \param Node - We're searching the nodes next to him. * \param SetOfNodes - set of nodes in which we erase the found nodes * \param Result - list of nodes closed to Node * \param precision - Precision used */ //====================================================================================== -void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node, - set* SetOfNodes, +void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node, + TIDSortedNodeSet* SetOfNodes, list* Result, const double precision) { @@ -281,12 +324,12 @@ void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node, if (isInsideBool) { // I'm only looking in the leaves, since all the nodes are stored there. - if (myIsLeaf) + if (isLeaf()) { - gp_Pnt p1( Node->X(), Node->Y(), Node->Z() ); + gp_Pnt p1 (Node->X(), Node->Y(), Node->Z()); - set myNodesCopy = myNodes; - set::iterator it = myNodesCopy.begin(); + TIDSortedNodeSet myNodesCopy = myNodes; + TIDSortedNodeSet::iterator it = myNodesCopy.begin(); double tol2 = precision * precision; bool squareBool; @@ -294,34 +337,98 @@ void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node, { const SMDS_MeshNode* n2 = *it; // We're only looking at nodes with a superior Id. - if(Node->GetID() < n2->GetID()) + // JFA: Why? + //if (Node->GetID() < n2->GetID()) + if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185 { - gp_Pnt p2( n2->X(), n2->Y(), n2->Z() ); + gp_Pnt p2 (n2->X(), n2->Y(), n2->Z()); // Distance optimized computation squareBool = (p1.SquareDistance( p2 ) <= tol2); - // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes - if(squareBool) + // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes + if (squareBool) { Result->insert(Result->begin(), n2); SetOfNodes->erase( n2 ); myNodes.erase( n2 ); } } - myNodesCopy.erase( it ); - it = myNodesCopy.begin(); + //myNodesCopy.erase( it ); + //it = myNodesCopy.begin(); + it++; } - + if (Result->size() > 0) + myNodes.erase(Node); // JFA: for bug 0020185 } else { // If I'm not a leaf, I'm going to see my children ! - for(int i = 0; i < 8; i++) + for (int i = 0; i < 8; i++) { SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); - myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision); + myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision); } } } } +//================================================================================ +/*! + * \brief Update data according to node movement + */ +//================================================================================ + +void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt ) +{ + if ( isLeaf() ) + { + TIDSortedNodeSet::iterator pNode = myNodes.find( node ); + bool nodeInMe = ( pNode != myNodes.end() ); + + SMDS_MeshNode pointNode( toPnt.X(), toPnt.Y(), toPnt.Z() ); + bool pointInMe = isInside( &pointNode, 1e-10 ); + + if ( pointInMe != nodeInMe ) + { + if ( pointInMe ) + myNodes.insert( node ); + else + myNodes.erase( node ); + } + } + else if ( myChildren ) + { + gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.; + int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid ); + int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid ); + if ( nodeChild != pointChild ) + { + ((SMESH_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt ); + ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt ); + } + } +} + +//================================================================================ +/*! + * \brief Return iterator over children + */ +//================================================================================ +SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator() +{ + return SMESH_OctreeNodeIteratorPtr + ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** > + ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] ))); +} + +//================================================================================ +/*! + * \brief Return nodes iterator + */ +//================================================================================ +SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator() +{ + return SMDS_NodeIteratorPtr + ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator > + ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin())); +}