X-Git-Url: http://git.salome-platform.org/gitweb/?p=modules%2Fsmesh.git;a=blobdiff_plain;f=src%2FSMESHUtils%2FSMESH_MeshAlgos.cxx;h=8464e245fe197e6765f100a08498d730211522bb;hp=a26695858025dd9644b6ab75b0fcb1ff47e2ff0f;hb=4fa5fdbd44a9567a62142d6abd80f663165f3ba2;hpb=831b40eb011a5f2ad1738518e86fdc6d924f891d diff --git a/src/SMESHUtils/SMESH_MeshAlgos.cxx b/src/SMESHUtils/SMESH_MeshAlgos.cxx index a26695858..8464e245f 100644 --- a/src/SMESHUtils/SMESH_MeshAlgos.cxx +++ b/src/SMESHUtils/SMESH_MeshAlgos.cxx @@ -228,15 +228,15 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() SMDSAbs_ElementType elemType, SMDS_ElemIteratorPtr theElemIt = SMDS_ElemIteratorPtr(), double tolerance = NodeRadius ); - void getElementsNearPoint( const gp_Pnt& point, TIDSortedElemSet& foundElems ); - void getElementsNearLine ( const gp_Ax1& line, TIDSortedElemSet& foundElems); - void getElementsInSphere ( const gp_XYZ& center, - const double radius, TIDSortedElemSet& foundElems); - size_t getSize() { return std::max( _size, _elements.size() ); } - virtual ~ElementBndBoxTree(); + void prepare(); // !!!call it before calling the following methods!!! + void getElementsNearPoint( const gp_Pnt& point, vector& foundElems ); + void getElementsNearLine ( const gp_Ax1& line, vector& foundElems); + void getElementsInSphere ( const gp_XYZ& center, + const double radius, + vector& foundElems); protected: - ElementBndBoxTree():_size(0) {} + ElementBndBoxTree() {} SMESH_Octree* newChild() const { return new ElementBndBoxTree; } void buildChildrenData(); Bnd_B3d* buildRootBox(); @@ -245,11 +245,25 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() struct ElementBox : public Bnd_B3d { const SMDS_MeshElement* _element; - int _refCount; // an ElementBox can be included in several tree branches - ElementBox(const SMDS_MeshElement* elem, double tolerance); + bool _isMarked; + void init(const SMDS_MeshElement* elem, double tolerance); }; vector< ElementBox* > _elements; - size_t _size; + + typedef ObjectPool< ElementBox > TElementBoxPool; + + //!< allocator of ElementBox's and SMESH_TreeLimit + struct LimitAndPool : public SMESH_TreeLimit + { + TElementBoxPool _elBoPool; + std::vector< ElementBox* > _markedElems; + LimitAndPool():SMESH_TreeLimit( MaxLevel, /*minSize=*/0. ) {} + }; + LimitAndPool* getLimitAndPool() const + { + SMESH_TreeLimit* limitAndPool = const_cast< SMESH_TreeLimit* >( myLimit ); + return static_cast< LimitAndPool* >( limitAndPool ); + } }; //================================================================================ @@ -258,32 +272,27 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() */ //================================================================================ - ElementBndBoxTree::ElementBndBoxTree(const SMDS_Mesh& mesh, SMDSAbs_ElementType elemType, SMDS_ElemIteratorPtr theElemIt, double tolerance) - :SMESH_Octree( new SMESH_TreeLimit( MaxLevel, /*minSize=*/0. )) + ElementBndBoxTree::ElementBndBoxTree(const SMDS_Mesh& mesh, + SMDSAbs_ElementType elemType, + SMDS_ElemIteratorPtr theElemIt, + double tolerance) + :SMESH_Octree( new LimitAndPool() ) { int nbElems = mesh.GetMeshInfo().NbElements( elemType ); _elements.reserve( nbElems ); + TElementBoxPool& elBoPool = getLimitAndPool()->_elBoPool; + SMDS_ElemIteratorPtr elemIt = theElemIt ? theElemIt : mesh.elementsIterator( elemType ); while ( elemIt->more() ) - _elements.push_back( new ElementBox( elemIt->next(),tolerance )); - + { + ElementBox* eb = elBoPool.getNew(); + eb->init( elemIt->next(), tolerance ); + _elements.push_back( eb ); + } compute(); } - //================================================================================ - /*! - * \brief Destructor - */ - //================================================================================ - - ElementBndBoxTree::~ElementBndBoxTree() - { - for ( size_t i = 0; i < _elements.size(); ++i ) - if ( --_elements[i]->_refCount <= 0 ) - delete _elements[i]; - } - //================================================================================ /*! * \brief Return the maximal box @@ -311,14 +320,10 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() for (int j = 0; j < 8; j++) { if ( !_elements[i]->IsOut( *myChildren[j]->getBox() )) - { - _elements[i]->_refCount++; ((ElementBndBoxTree*)myChildren[j])->_elements.push_back( _elements[i]); - } } - _elements[i]->_refCount--; } - _size = _elements.size(); + //_size = _elements.size(); SMESHUtils::FreeVector( _elements ); // = _elements.clear() + free memory for (int j = 0; j < 8; j++) @@ -327,33 +332,61 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() if ((int) child->_elements.size() <= MaxNbElemsInLeaf ) child->myIsLeaf = true; - if ( child->_elements.capacity() - child->_elements.size() > 1000 ) + if ( child->isLeaf() && child->_elements.capacity() > child->_elements.size() ) SMESHUtils::CompactVector( child->_elements ); } } + //================================================================================ + /*! + * \brief Un-mark all elements + */ + //================================================================================ + + void ElementBndBoxTree::prepare() + { + // TElementBoxPool& elBoPool = getElementBoxPool(); + // for ( size_t i = 0; i < elBoPool.nbElements(); ++i ) + // const_cast< ElementBox* >( elBoPool[ i ])->_isMarked = false; + } + //================================================================================ /*! * \brief Return elements which can include the point */ //================================================================================ - void ElementBndBoxTree::getElementsNearPoint( const gp_Pnt& point, - TIDSortedElemSet& foundElems) + void ElementBndBoxTree::getElementsNearPoint( const gp_Pnt& point, + vector& foundElems) { if ( getBox()->IsOut( point.XYZ() )) return; if ( isLeaf() ) { + LimitAndPool* pool = getLimitAndPool(); + for ( size_t i = 0; i < _elements.size(); ++i ) - if ( !_elements[i]->IsOut( point.XYZ() )) - foundElems.insert( _elements[i]->_element ); + if ( !_elements[i]->IsOut( point.XYZ() ) && + !_elements[i]->_isMarked ) + { + foundElems.push_back( _elements[i]->_element ); + _elements[i]->_isMarked = true; + pool->_markedElems.push_back( _elements[i] ); + } } else { for (int i = 0; i < 8; i++) ((ElementBndBoxTree*) myChildren[i])->getElementsNearPoint( point, foundElems ); + + if ( level() == 0 ) + { + LimitAndPool* pool = getLimitAndPool(); + for ( size_t i = 0; i < pool->_markedElems.size(); ++i ) + pool->_markedElems[i]->_isMarked = false; + pool->_markedElems.clear(); + } } } @@ -363,22 +396,37 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() */ //================================================================================ - void ElementBndBoxTree::getElementsNearLine( const gp_Ax1& line, - TIDSortedElemSet& foundElems) + void ElementBndBoxTree::getElementsNearLine( const gp_Ax1& line, + vector& foundElems) { if ( getBox()->IsOut( line )) return; if ( isLeaf() ) { + LimitAndPool* pool = getLimitAndPool(); + for ( size_t i = 0; i < _elements.size(); ++i ) - if ( !_elements[i]->IsOut( line )) - foundElems.insert( _elements[i]->_element ); + if ( !_elements[i]->IsOut( line ) && + !_elements[i]->_isMarked ) + { + foundElems.push_back( _elements[i]->_element ); + _elements[i]->_isMarked = true; + pool->_markedElems.push_back( _elements[i] ); + } } else { for (int i = 0; i < 8; i++) ((ElementBndBoxTree*) myChildren[i])->getElementsNearLine( line, foundElems ); + + if ( level() == 0 ) + { + LimitAndPool* pool = getLimitAndPool(); + for ( size_t i = 0; i < pool->_markedElems.size(); ++i ) + pool->_markedElems[i]->_isMarked = false; + pool->_markedElems.clear(); + } } } @@ -388,23 +436,38 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() */ //================================================================================ - void ElementBndBoxTree::getElementsInSphere ( const gp_XYZ& center, - const double radius, - TIDSortedElemSet& foundElems) + void ElementBndBoxTree::getElementsInSphere ( const gp_XYZ& center, + const double radius, + vector& foundElems) { if ( getBox()->IsOut( center, radius )) return; if ( isLeaf() ) { + LimitAndPool* pool = getLimitAndPool(); + for ( size_t i = 0; i < _elements.size(); ++i ) - if ( !_elements[i]->IsOut( center, radius )) - foundElems.insert( _elements[i]->_element ); + if ( !_elements[i]->IsOut( center, radius ) && + !_elements[i]->_isMarked ) + { + foundElems.push_back( _elements[i]->_element ); + _elements[i]->_isMarked = true; + pool->_markedElems.push_back( _elements[i] ); + } } else { for (int i = 0; i < 8; i++) ((ElementBndBoxTree*) myChildren[i])->getElementsInSphere( center, radius, foundElems ); + + if ( level() == 0 ) + { + LimitAndPool* pool = getLimitAndPool(); + for ( size_t i = 0; i < pool->_markedElems.size(); ++i ) + pool->_markedElems[i]->_isMarked = false; + pool->_markedElems.clear(); + } } } @@ -414,13 +477,13 @@ namespace // Utils used in SMESH_ElementSearcherImpl::FindElementsByPoint() */ //================================================================================ - ElementBndBoxTree::ElementBox::ElementBox(const SMDS_MeshElement* elem, double tolerance) + void ElementBndBoxTree::ElementBox::init(const SMDS_MeshElement* elem, double tolerance) { _element = elem; - _refCount = 1; + _isMarked = false; SMDS_ElemIteratorPtr nIt = elem->nodesIterator(); while ( nIt->more() ) - Add( SMESH_TNodeXYZ( nIt->next() )); + Add( SMESH_NodeXYZ( nIt->next() )); Enlarge( tolerance ); } @@ -441,8 +504,8 @@ struct SMESH_ElementSearcherImpl: public SMESH_ElementSearcher { SMDS_Mesh* _mesh; SMDS_ElemIteratorPtr _meshPartIt; - ElementBndBoxTree* _ebbTree; - int _ebbTreeHeight; + ElementBndBoxTree* _ebbTree [SMDSAbs_NbElementTypes]; + int _ebbTreeHeight[SMDSAbs_NbElementTypes]; SMESH_NodeSearcherImpl* _nodeSearcher; SMDSAbs_ElementType _elementType; double _tolerance; @@ -452,10 +515,21 @@ struct SMESH_ElementSearcherImpl: public SMESH_ElementSearcher SMESH_ElementSearcherImpl( SMDS_Mesh& mesh, double tol=-1, SMDS_ElemIteratorPtr elemIt=SMDS_ElemIteratorPtr()) - : _mesh(&mesh),_meshPartIt(elemIt),_ebbTree(0),_ebbTreeHeight(-1),_nodeSearcher(0),_tolerance(tol),_outerFacesFound(false) {} + : _mesh(&mesh),_meshPartIt(elemIt),_nodeSearcher(0),_tolerance(tol),_outerFacesFound(false) + { + for ( int i = 0; i < SMDSAbs_NbElementTypes; ++i ) + { + _ebbTree[i] = NULL; + _ebbTreeHeight[i] = -1; + } + _elementType = SMDSAbs_All; + } virtual ~SMESH_ElementSearcherImpl() { - if ( _ebbTree ) delete _ebbTree; _ebbTree = 0; + for ( int i = 0; i < SMDSAbs_NbElementTypes; ++i ) + { + delete _ebbTree[i]; _ebbTree[i] = NULL; + } if ( _nodeSearcher ) delete _nodeSearcher; _nodeSearcher = 0; } virtual int FindElementsByPoint(const gp_Pnt& point, @@ -482,9 +556,9 @@ struct SMESH_ElementSearcherImpl: public SMESH_ElementSearcher } int getTreeHeight() { - if ( _ebbTreeHeight < 0 ) - _ebbTreeHeight = _ebbTree->getHeight(); - return _ebbTreeHeight; + if ( _ebbTreeHeight[ _elementType ] < 0 ) + _ebbTreeHeight[ _elementType ] = _ebbTree[ _elementType ]->getHeight(); + return _ebbTreeHeight[ _elementType ]; } struct TInters //!< data of intersection of the line and the mesh face (used in GetPointState()) @@ -528,9 +602,9 @@ double SMESH_ElementSearcherImpl::getTolerance() double boxSize = _nodeSearcher->getTree()->maxSize(); _tolerance = 1e-8 * boxSize/* / meshInfo.NbNodes()*/; } - else if ( _ebbTree && meshInfo.NbElements() > 0 ) + else if ( _ebbTree[_elementType] && meshInfo.NbElements() > 0 ) { - double boxSize = _ebbTree->maxSize(); + double boxSize = _ebbTree[_elementType]->maxSize(); _tolerance = 1e-8 * boxSize/* / meshInfo.NbElements()*/; } if ( _tolerance == 0 ) @@ -551,10 +625,9 @@ double SMESH_ElementSearcherImpl::getTolerance() } else { - SMDS_ElemIteratorPtr elemIt = - _mesh->elementsIterator( SMDSAbs_ElementType( complexType )); + SMDS_ElemIteratorPtr elemIt = _mesh->elementsIterator( SMDSAbs_ElementType( complexType )); const SMDS_MeshElement* elem = elemIt->next(); - SMDS_ElemIteratorPtr nodeIt = elem->nodesIterator(); + SMDS_ElemIteratorPtr nodeIt = elem->nodesIterator(); SMESH_TNodeXYZ n1( nodeIt->next() ); elemSize = 0; while ( nodeIt->more() ) @@ -594,7 +667,7 @@ bool SMESH_ElementSearcherImpl::getIntersParamOnLine(const gp_Lin& lin anExtCC.Init( lineCurve, edge.Value() ); if ( anExtCC.NbExtrema() > 0 && anExtCC.LowerDistance() <= tol) { - Quantity_Parameter pl, pe; + Standard_Real pl, pe; anExtCC.LowerDistanceParameters( pl, pe ); param += pl; if ( ++nbInts == 2 ) @@ -679,7 +752,7 @@ void SMESH_ElementSearcherImpl::findOuterBoundary(const SMDS_MeshElement* outerF outerFace2 = angle2Face.begin()->second; } } - // store the found outer face and add its links to continue seaching from + // store the found outer face and add its links to continue searching from if ( outerFace2 ) { _outerFaces.insert( outerFace2 ); @@ -723,6 +796,7 @@ FindElementsByPoint(const gp_Pnt& point, vector< const SMDS_MeshElement* >& foundElements) { foundElements.clear(); + _elementType = type; double tolerance = getTolerance(); @@ -756,14 +830,17 @@ FindElementsByPoint(const gp_Pnt& point, // ================================================================================= else // elements more complex than 0D { - if ( !_ebbTree || _elementType != type ) + if ( !_ebbTree[type] ) + { + _ebbTree[_elementType] = new ElementBndBoxTree( *_mesh, type, _meshPartIt, tolerance ); + } + else { - if ( _ebbTree ) delete _ebbTree; - _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = type, _meshPartIt, tolerance ); + _ebbTree[ type ]->prepare(); } - TIDSortedElemSet suspectElems; - _ebbTree->getElementsNearPoint( point, suspectElems ); - TIDSortedElemSet::iterator elem = suspectElems.begin(); + vector< const SMDS_MeshElement* > suspectElems; + _ebbTree[ type ]->getElementsNearPoint( point, suspectElems ); + vector< const SMDS_MeshElement* >::iterator elem = suspectElems.begin(); for ( ; elem != suspectElems.end(); ++elem ) if ( !SMESH_MeshAlgos::IsOut( *elem, point, tolerance )) foundElements.push_back( *elem ); @@ -784,35 +861,38 @@ SMESH_ElementSearcherImpl::FindClosestTo( const gp_Pnt& point, SMDSAbs_ElementType type ) { const SMDS_MeshElement* closestElem = 0; + _elementType = type; if ( type == SMDSAbs_Face || type == SMDSAbs_Volume ) { - if ( !_ebbTree || _elementType != type ) - { - if ( _ebbTree ) delete _ebbTree; - _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = type, _meshPartIt ); - } - TIDSortedElemSet suspectElems; - _ebbTree->getElementsNearPoint( point, suspectElems ); + ElementBndBoxTree*& ebbTree = _ebbTree[ type ]; + if ( !ebbTree ) + ebbTree = new ElementBndBoxTree( *_mesh, type, _meshPartIt ); + else + ebbTree->prepare(); - if ( suspectElems.empty() && _ebbTree->maxSize() > 0 ) + vector suspectElems; + ebbTree->getElementsNearPoint( point, suspectElems ); + + if ( suspectElems.empty() && ebbTree->maxSize() > 0 ) { - gp_Pnt boxCenter = 0.5 * ( _ebbTree->getBox()->CornerMin() + - _ebbTree->getBox()->CornerMax() ); + gp_Pnt boxCenter = 0.5 * ( ebbTree->getBox()->CornerMin() + + ebbTree->getBox()->CornerMax() ); double radius = -1; - if ( _ebbTree->getBox()->IsOut( point.XYZ() )) - radius = point.Distance( boxCenter ) - 0.5 * _ebbTree->maxSize(); + if ( ebbTree->getBox()->IsOut( point.XYZ() )) + radius = point.Distance( boxCenter ) - 0.5 * ebbTree->maxSize(); if ( radius < 0 ) - radius = _ebbTree->maxSize() / pow( 2., getTreeHeight()) / 2; + radius = ebbTree->maxSize() / pow( 2., getTreeHeight()) / 2; while ( suspectElems.empty() ) { - _ebbTree->getElementsInSphere( point.XYZ(), radius, suspectElems ); + ebbTree->prepare(); + ebbTree->getElementsInSphere( point.XYZ(), radius, suspectElems ); radius *= 1.1; } } double minDist = std::numeric_limits::max(); multimap< double, const SMDS_MeshElement* > dist2face; - TIDSortedElemSet::iterator elem = suspectElems.begin(); + vector::iterator elem = suspectElems.begin(); for ( ; elem != suspectElems.end(); ++elem ) { double dist = SMESH_MeshAlgos::GetDistance( *elem, point ); @@ -869,12 +949,16 @@ SMESH_ElementSearcherImpl::FindClosestTo( const gp_Pnt& point, TopAbs_State SMESH_ElementSearcherImpl::GetPointState(const gp_Pnt& point) { + _elementType = SMDSAbs_Face; + double tolerance = getTolerance(); - if ( !_ebbTree || _elementType != SMDSAbs_Face ) - { - if ( _ebbTree ) delete _ebbTree; - _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = SMDSAbs_Face, _meshPartIt ); - } + + ElementBndBoxTree*& ebbTree = _ebbTree[ SMDSAbs_Face ]; + if ( !ebbTree ) + ebbTree = new ElementBndBoxTree( *_mesh, _elementType, _meshPartIt ); + else + ebbTree->prepare(); + // Algo: analyse transition of a line starting at the point through mesh boundary; // try three lines parallel to axis of the coordinate system and perform rough // analysis. If solution is not clear perform thorough analysis. @@ -889,13 +973,14 @@ TopAbs_State SMESH_ElementSearcherImpl::GetPointState(const gp_Pnt& point) gp_Ax1 lineAxis( point, axisDir[axis]); gp_Lin line ( lineAxis ); - TIDSortedElemSet suspectFaces; // faces possibly intersecting the line - _ebbTree->getElementsNearLine( lineAxis, suspectFaces ); + vector suspectFaces; // faces possibly intersecting the line + if ( axis > 0 ) ebbTree->prepare(); + ebbTree->getElementsNearLine( lineAxis, suspectFaces ); // Intersect faces with the line map< double, TInters > & u2inters = paramOnLine2TInters[ axis ]; - TIDSortedElemSet::iterator face = suspectFaces.begin(); + vector::iterator face = suspectFaces.begin(); for ( ; face != suspectFaces.end(); ++face ) { // get face plane @@ -1098,14 +1183,14 @@ void SMESH_ElementSearcherImpl::GetElementsNearLine( const gp_Ax1& SMDSAbs_ElementType type, vector< const SMDS_MeshElement* >& foundElems) { - if ( !_ebbTree || _elementType != type ) - { - if ( _ebbTree ) delete _ebbTree; - _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = type, _meshPartIt ); - } - TIDSortedElemSet suspectFaces; // elements possibly intersecting the line - _ebbTree->getElementsNearLine( line, suspectFaces ); - foundElems.assign( suspectFaces.begin(), suspectFaces.end()); + _elementType = type; + ElementBndBoxTree*& ebbTree = _ebbTree[ type ]; + if ( !ebbTree ) + ebbTree = new ElementBndBoxTree( *_mesh, _elementType, _meshPartIt ); + else + ebbTree->prepare(); + + ebbTree->getElementsNearLine( line, foundElems ); } //======================================================================= @@ -1119,14 +1204,14 @@ void SMESH_ElementSearcherImpl::GetElementsInSphere( const gp_XYZ& SMDSAbs_ElementType type, vector< const SMDS_MeshElement* >& foundElems) { - if ( !_ebbTree || _elementType != type ) - { - if ( _ebbTree ) delete _ebbTree; - _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = type, _meshPartIt ); - } - TIDSortedElemSet suspectFaces; // elements possibly intersecting the line - _ebbTree->getElementsInSphere( center, radius, suspectFaces ); - foundElems.assign( suspectFaces.begin(), suspectFaces.end() ); + _elementType = type; + ElementBndBoxTree*& ebbTree = _ebbTree[ type ]; + if ( !ebbTree ) + ebbTree = new ElementBndBoxTree( *_mesh, _elementType, _meshPartIt ); + else + ebbTree->prepare(); + + ebbTree->getElementsInSphere( center, radius, foundElems ); } //=======================================================================