X-Git-Url: http://git.salome-platform.org/gitweb/?a=blobdiff_plain;f=src%2FSMESHUtils%2FSMESH_OctreeNode.cxx;h=03e99b50f99d2b207ba40008698350284c3deb68;hb=e2ed82ab76826fe71cb635add1926e389c2fff9f;hp=d14a50a2465106b190ee8ad57afc373a14ab16b5;hpb=bd4e115a78b52e3fbc016e5e30bb0e19b2a9e7d6;p=modules%2Fsmesh.git diff --git a/src/SMESHUtils/SMESH_OctreeNode.cxx b/src/SMESHUtils/SMESH_OctreeNode.cxx index d14a50a24..03e99b50f 100644 --- a/src/SMESHUtils/SMESH_OctreeNode.cxx +++ b/src/SMESHUtils/SMESH_OctreeNode.cxx @@ -1,4 +1,4 @@ -// Copyright (C) 2007-2012 CEA/DEN, EDF R&D, OPEN CASCADE +// Copyright (C) 2007-2016 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 @@ -6,7 +6,7 @@ // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either -// version 2.1 of the License. +// version 2.1 of the License, or (at your option) any later version. // // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -21,7 +21,7 @@ // // SMESH SMESH_OctreeNode : Octree with Nodes set -// inherites global class SMESH_Octree +// inherites class SMESH_Octree // File : SMESH_OctreeNode.cxx // Created : Tue Jan 16 16:00:00 2007 // Author : Nicolas Geimer & Aurelien Motteux (OCC) @@ -30,6 +30,7 @@ #include "SMESH_OctreeNode.hxx" #include "SMDS_SetIterator.hxx" +#include "SMESH_TypeDefs.hxx" #include using namespace std; @@ -43,11 +44,11 @@ using namespace std; * \param minBoxSize - Minimal size of the Octree Box */ //================================================================ + SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel, const int maxNbNodes , const double minBoxSize ) - :SMESH_Octree( new SMESH_Octree::Limit( maxLevel,minBoxSize)), - myMaxNbNodes(maxNbNodes), - myNodes(theNodes) + :SMESH_Octree( new Limit( maxLevel,minBoxSize,maxNbNodes)), + myNodes(theNodes) { compute(); } @@ -58,9 +59,19 @@ SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int */ //================================================================================ -SMESH_OctreeNode::SMESH_OctreeNode (int maxNbNodes): - SMESH_Octree(), myMaxNbNodes(maxNbNodes) +SMESH_OctreeNode::SMESH_OctreeNode ():SMESH_Octree() +{ +} + +//================================================================================ +/*! + * \brief Return max number of nodes in a tree leaf + */ +//================================================================================ + +int SMESH_OctreeNode::getMaxNbNodes() const { + return ((Limit*)myLimit)->myMaxNbNodes; } //================================================================================== @@ -69,9 +80,9 @@ SMESH_OctreeNode::SMESH_OctreeNode (int maxNbNodes): */ //================================================================================== -SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() const +SMESH_Octree* SMESH_OctreeNode::newChild() const { - return new SMESH_OctreeNode(myMaxNbNodes); + return new SMESH_OctreeNode(); } //====================================== @@ -91,7 +102,7 @@ Bnd_B3d* SMESH_OctreeNode::buildRootBox() gp_XYZ p1( n1->X(), n1->Y(), n1->Z() ); box->Add(p1); } - if ( myNodes.size() <= myMaxNbNodes ) + if ((int) myNodes.size() <= getMaxNbNodes() ) myIsLeaf = true; return box; @@ -109,8 +120,8 @@ Bnd_B3d* SMESH_OctreeNode::buildRootBox() const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, const double precision) { if (precision <= 0.) - return !(getBox().IsOut(p)); - Bnd_B3d BoxWithPrecision = getBox(); + return !(getBox()->IsOut(p)); + Bnd_B3d BoxWithPrecision = *getBox(); BoxWithPrecision.Enlarge(precision); return ! BoxWithPrecision.IsOut(p); } @@ -123,8 +134,8 @@ const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, const double precision) //================================================ void SMESH_OctreeNode::buildChildrenData() { - gp_XYZ min = getBox().CornerMin(); - gp_XYZ max = getBox().CornerMax(); + gp_XYZ min = getBox()->CornerMin(); + gp_XYZ max = getBox()->CornerMax(); gp_XYZ mid = (min + max)/2.; TIDSortedNodeSet::iterator it = myNodes.begin(); @@ -140,7 +151,7 @@ void SMESH_OctreeNode::buildChildrenData() for (int i = 0; i < 8; i++) { SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); - if ( myChild->myNodes.size() <= myMaxNbNodes ) + if ((int) myChild->myNodes.size() <= getMaxNbNodes() ) myChild->myIsLeaf = true; } } @@ -157,7 +168,7 @@ void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node, list* Result, const double precision) { - gp_XYZ p(Node->X(), Node->Y(), Node->Z()); + SMESH_TNodeXYZ p(Node); if (isInside(p, precision)) { if (isLeaf()) @@ -178,10 +189,11 @@ void SMESH_OctreeNode::NodesAround (const SMDS_MeshNode * Node, //================================================================================ /*! * \brief Return in dist2Nodes nodes mapped to their square distance from Node + * Tries to find a closest 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 + * \retval bool - true if an exact overlapping found !!! */ //================================================================================ @@ -194,13 +206,12 @@ bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node, else if ( precision == 0. ) precision = maxSize() / 2; - //gp_XYZ p(node->X(), node->Y(), node->Z()); if (isInside(node, precision)) { if (!isLeaf()) { // first check a child containing node - gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.; + 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; @@ -213,24 +224,62 @@ bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node, 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 ); + SMESH_TNodeXYZ p2( *nIt ); + double dist2 = ( node - p2 ).SquareModulus(); if ( dist2 < minDist ) - dist2Nodes.insert( make_pair( minDist = dist2, *nIt )); + dist2Nodes.insert( make_pair( minDist = dist2, p2._node )); } // if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes // dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end()); - return ( sqrt( minDist) <= precision * 1e-12 ); + // true if an exact overlapping found + return ( sqrt( minDist ) <= precision * 1e-12 ); } } return false; } +//================================================================================ +/*! + * \brief Return a list of nodes close to a point + * \param [in] point - point + * \param [out] nodes - found nodes + * \param [in] precision - allowed distance from \a point + */ +//================================================================================ + +void SMESH_OctreeNode::NodesAround(const gp_XYZ& point, + std::vector& nodes, + double precision) +{ + if ( isInside( point, precision )) + { + if ( isLeaf() && NbNodes() ) + { + double minDist2 = precision * precision; + TIDSortedNodeSet::iterator nIt = myNodes.begin(); + for ( ; nIt != myNodes.end(); ++nIt ) + { + SMESH_TNodeXYZ p2( *nIt ); + double dist2 = ( point - p2 ).SquareModulus(); + if ( dist2 <= minDist2 ) + nodes.push_back( p2._node ); + } + } + else if ( myChildren ) + { + for (int i = 0; i < 8; i++) + { + SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); + myChild->NodesAround( point, nodes, precision); + } + } + } +} + //============================= /*! * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance @@ -265,42 +314,33 @@ void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes, * \param theGroupsOfNodes - list of nodes closed to each other returned */ //============================= -void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes, - const double theTolerance, +void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes, + const double theTolerance, list< list< const SMDS_MeshNode*> >* theGroupsOfNodes) { TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin(); list::iterator it2; + list ListOfCoincidentNodes; + TIDCompare idLess; + while (it1 != theSetOfNodes->end()) { const SMDS_MeshNode * n1 = *it1; - list ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough - - list * groupPtr = 0; - // 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++) + if ( !ListOfCoincidentNodes.empty() ) { - const SMDS_MeshNode* n2 = *it2; - if ( !groupPtr ) - { - theGroupsOfNodes->push_back( list() ); - groupPtr = & theGroupsOfNodes->back(); - groupPtr->push_back( n1 ); - } - if (groupPtr->front() > n2) - groupPtr->push_front( n2 ); - else - groupPtr->push_back( n2 ); + // We build a list {n1 + his neighbors} and add this list in theGroupsOfNodes + if ( idLess( n1, ListOfCoincidentNodes.front() )) ListOfCoincidentNodes.push_front( n1 ); + else ListOfCoincidentNodes.push_back ( n1 ); + ListOfCoincidentNodes.sort( idLess ); + theGroupsOfNodes->push_back( list() ); + theGroupsOfNodes->back().splice( theGroupsOfNodes->back().end(), ListOfCoincidentNodes ); } - if (groupPtr != 0) - groupPtr->sort(); theSetOfNodes->erase(it1); it1 = theSetOfNodes->begin(); @@ -317,29 +357,27 @@ void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes, * \param precision - Precision used */ //====================================================================================== -void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node, - TIDSortedNodeSet* SetOfNodes, +void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node, + TIDSortedNodeSet* SetOfNodes, list* Result, - const double precision) + const double precision) { - gp_XYZ p(Node->X(), Node->Y(), Node->Z()); - bool isInsideBool = isInside(p, precision); + gp_Pnt p1 (Node->X(), Node->Y(), Node->Z()); + bool isInsideBool = isInside( p1.XYZ(), precision ); if (isInsideBool) { // I'm only looking in the leaves, since all the nodes are stored there. if (isLeaf()) { - gp_Pnt p1 (Node->X(), Node->Y(), Node->Z()); - - TIDSortedNodeSet myNodesCopy = myNodes; - TIDSortedNodeSet::iterator it = myNodesCopy.begin(); - double tol2 = precision * precision; + TIDSortedNodeSet::iterator it = myNodes.begin(); + const double tol2 = precision * precision; bool squareBool; - while (it != myNodesCopy.end()) + while (it != myNodes.end()) { const SMDS_MeshNode* n2 = *it; + squareBool = false; // We're only looking at nodes with a superior Id. // JFA: Why? //if (Node->GetID() < n2->GetID()) @@ -354,14 +392,13 @@ void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node, { Result->insert(Result->begin(), n2); SetOfNodes->erase( n2 ); - myNodes.erase( n2 ); + myNodes.erase( *it++ ); // it++ goes forward and returns it's previous position } } - //myNodesCopy.erase( it ); - //it = myNodesCopy.begin(); - it++; + if ( !squareBool ) + it++; } - if (Result->size() > 0) + if ( !Result->empty() ) myNodes.erase(Node); // JFA: for bug 0020185 } else @@ -401,7 +438,7 @@ void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt } else if ( myChildren ) { - gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.; + 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 ) @@ -420,7 +457,7 @@ void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt SMESH_OctreeNodeIteratorPtr SMESH_OctreeNode::GetChildrenIterator() { return SMESH_OctreeNodeIteratorPtr - ( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** > + ( new SMDS_SetIterator< SMESH_OctreeNode*, TBaseTree** > ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] ))); }