X-Git-Url: http://git.salome-platform.org/gitweb/?p=modules%2Fsmesh.git;a=blobdiff_plain;f=src%2FSMESH%2FSMESH_OctreeNode.cxx;h=37a7d4f1bac9505bd33cf0f45a3f2a08f1ea8a9a;hp=9a74d71bd7048db96817b792dad1b6ae5b703d54;hb=9357f5c87098aff2b95b754d69f66c76d2df9c24;hpb=c113b9f92eda39a04caed33d839213a3fefc00af diff --git a/src/SMESH/SMESH_OctreeNode.cxx b/src/SMESH/SMESH_OctreeNode.cxx index 9a74d71bd..37a7d4f1b 100644 --- a/src/SMESH/SMESH_OctreeNode.cxx +++ b/src/SMESH/SMESH_OctreeNode.cxx @@ -1,4 +1,4 @@ -// Copyright (C) 2007-2008 CEA/DEN, EDF R&D, OPEN CASCADE +// Copyright (C) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE // // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS @@ -19,14 +19,14 @@ // // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com // + // 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_MeshNode.hxx" @@ -46,18 +46,22 @@ using namespace std; //================================================================ SMESH_OctreeNode::SMESH_OctreeNode (const set & 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) || - (maxSize(myBox) <= myMinBoxSize)); - // 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) +{ } //================================================================================== @@ -65,16 +69,10 @@ SMESH_OctreeNode::SMESH_OctreeNode (const set & theNodes, * \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); } //====================================== @@ -84,25 +82,20 @@ SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() * We take the max/min coord of the nodes */ //====================================== -void SMESH_OctreeNode::computeBoxForFather() + +Bnd_B3d* SMESH_OctreeNode::buildRootBox() { + Bnd_B3d* box = new Bnd_B3d; set::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; } //==================================================================================== @@ -113,19 +106,15 @@ 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) { - double X = Node->X(); - double Y = Node->Y(); - double Z = Node->Z(); - bool Out = 1 ; + gp_XYZ p (Node->X(),Node->Y(),Node->Z()); if (precision <= 0.) - return !(myBox->IsOut(gp_XYZ(X,Y,Z))); - Bnd_B3d BoxWithPrecision; - getBox(BoxWithPrecision); + return !(getBox().IsOut(p)); + Bnd_B3d BoxWithPrecision = getBox(); BoxWithPrecision.Enlarge(precision); - Out = BoxWithPrecision.IsOut(gp_XYZ(X,Y,Z)); - return !(Out); + return ! BoxWithPrecision.IsOut(p); } //================================================ @@ -136,16 +125,15 @@ const bool SMESH_OctreeNode::isInside (const SMDS_MeshNode * Node, const double //================================================ 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()) { 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 ); @@ -154,10 +142,8 @@ void SMESH_OctreeNode::buildChildrenData() 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) || - (maxSize(myChild->myBox) <= myMinBoxSize)); + if ( myChild->myNodes.size() <= myMaxNbNodes ) + myChild->myIsLeaf = true; } } @@ -175,7 +161,7 @@ void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node, { if (isInside(Node,precision)) { - if (myIsLeaf) + if (isLeaf()) { Result->insert(Result->end(), myNodes.begin(), myNodes.end()); } @@ -190,6 +176,61 @@ void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node, } } +//================================================================================ +/*! + * \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() ); + set::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 @@ -202,15 +243,14 @@ void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node, * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5 */ //============================= -void SMESH_OctreeNode::FindCoincidentNodes (set theSetOfNodes, +void SMESH_OctreeNode::FindCoincidentNodes (set& theSetOfNodes, list< list< const SMDS_MeshNode*> >* theGroupsOfNodes, const double theTolerance, const int maxLevel, const int maxNbNodes) { - SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance); - theOctreeNode->FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes); - delete theOctreeNode; + SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance); + theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes); } //============================= @@ -285,7 +325,7 @@ 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()); @@ -333,6 +373,43 @@ void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node, } } +//================================================================================ +/*! + * \brief Update data according to node movement + */ +//================================================================================ + +void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt ) +{ + if ( isLeaf() ) + { + set::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 @@ -342,7 +419,7 @@ SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator() { return SMESH_OctreeNodeIteratorPtr ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** > - ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] ))); + ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] ))); } //================================================================================ @@ -354,5 +431,5 @@ SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator() { return SMDS_NodeIteratorPtr ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator > - ( myNodes.begin(), myNodes.end() )); + ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin())); }