Back to index

salome-smesh  6.5.0
Classes | Public Member Functions | Public Attributes
SMESH_ElementSearcherImpl Struct Reference

Implementation of search for the elements by point and of classification of point in 2D mesh. More...

Inheritance diagram for SMESH_ElementSearcherImpl:
Inheritance graph
[legend]
Collaboration diagram for SMESH_ElementSearcherImpl:
Collaboration graph
[legend]

List of all members.

Classes

struct  TFaceLink
 < link and faces sharing it (used in findOuterBoundary()) More...
struct  TInters
 < data of intersection of the line and the mesh face (used in GetPointState()) More...

Public Member Functions

 SMESH_ElementSearcherImpl (SMESHDS_Mesh &mesh, SMDS_ElemIteratorPtr elemIt=SMDS_ElemIteratorPtr())
 ~SMESH_ElementSearcherImpl ()
virtual int FindElementsByPoint (const gp_Pnt &point, SMDSAbs_ElementType type, vector< const SMDS_MeshElement * > &foundElements)
 Find elements of given type where the given point is IN or ON.
virtual TopAbs_State GetPointState (const gp_Pnt &point)
 Classify the given point in the closed 2D mesh.
void GetElementsNearLine (const gp_Ax1 &line, SMDSAbs_ElementType type, vector< const SMDS_MeshElement * > &foundElems)
 Return elements possibly intersecting the line.
double getTolerance ()
 define tolerance for search
bool getIntersParamOnLine (const gp_Lin &line, const SMDS_MeshElement *face, const double tolerance, double &param)
 Find intersection of the line and an edge of face and return parameter on line.
void findOuterBoundary (const SMDS_MeshElement *anyOuterFace)
 Find all faces belonging to the outer boundary of mesh.
bool isOuterBoundary (const SMDS_MeshElement *face) const

Public Attributes

SMESHDS_Mesh * _mesh
SMDS_ElemIteratorPtr _meshPartIt
ElementBndBoxTree * _ebbTree
SMESH_NodeSearcherImpl_nodeSearcher
SMDSAbs_ElementType _elementType
double _tolerance
bool _outerFacesFound
set< const SMDS_MeshElement * > _outerFaces

Detailed Description

Implementation of search for the elements by point and of classification of point in 2D mesh.

Definition at line 6246 of file SMESH_MeshEditor.cxx.


Constructor & Destructor Documentation

Definition at line 6257 of file SMESH_MeshEditor.cxx.

Definition at line 6259 of file SMESH_MeshEditor.cxx.

  {
    if ( _ebbTree )      delete _ebbTree;      _ebbTree      = 0;
    if ( _nodeSearcher ) delete _nodeSearcher; _nodeSearcher = 0;
  }

Member Function Documentation

int SMESH_ElementSearcherImpl::FindElementsByPoint ( const gp_Pnt &  point,
SMDSAbs_ElementType  type,
vector< const SMDS_MeshElement * > &  foundElements 
) [virtual]

Find elements of given type where the given point is IN or ON.

   Returns nb of found elements and elements them-selves.

'ALL' type means elements of any type excluding nodes and 0D elements

Implements SMESH_ElementSearcher.

Definition at line 6510 of file SMESH_MeshEditor.cxx.

{
  foundElements.clear();

  double tolerance = getTolerance();

  // =================================================================================
  if ( type == SMDSAbs_Node || type == SMDSAbs_0DElement )
  {
    if ( !_nodeSearcher )
      _nodeSearcher = new SMESH_NodeSearcherImpl( _mesh );

    const SMDS_MeshNode* closeNode = _nodeSearcher->FindClosestTo( point );
    if ( !closeNode ) return foundElements.size();

    if ( point.Distance( SMESH_TNodeXYZ( closeNode )) > tolerance )
      return foundElements.size(); // to far from any node

    if ( type == SMDSAbs_Node )
    {
      foundElements.push_back( closeNode );
    }
    else
    {
      SMDS_ElemIteratorPtr elemIt = closeNode->GetInverseElementIterator( SMDSAbs_0DElement );
      while ( elemIt->more() )
        foundElements.push_back( elemIt->next() );
    }
  }
  // =================================================================================
  else // elements more complex than 0D
  {
    if ( !_ebbTree || _elementType != type )
    {
      if ( _ebbTree ) delete _ebbTree;
      _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = type, _meshPartIt, tolerance );
    }
    TIDSortedElemSet suspectElems;
    _ebbTree->getElementsNearPoint( point, suspectElems );
    TIDSortedElemSet::iterator elem = suspectElems.begin();
    for ( ; elem != suspectElems.end(); ++elem )
      if ( !SMESH_MeshEditor::isOut( *elem, point, tolerance ))
        foundElements.push_back( *elem );
  }
  return foundElements.size();
}

Here is the call graph for this function:

void SMESH_ElementSearcherImpl::findOuterBoundary ( const SMDS_MeshElement *  anyOuterFace)

Find all faces belonging to the outer boundary of mesh.

Definition at line 6403 of file SMESH_MeshEditor.cxx.

{
  if ( _outerFacesFound ) return;

  // Collect all outer faces by passing from one outer face to another via their links
  // and BTW find out if there are internal faces at all.

  // checked links and links where outer boundary meets internal one
  set< SMESH_TLink > visitedLinks, seamLinks;

  // links to treat with already visited faces sharing them
  list < TFaceLink > startLinks;

  // load startLinks with the first outerFace
  startLinks.push_back( TFaceLink( outerFace->GetNode(0), outerFace->GetNode(1), outerFace));
  _outerFaces.insert( outerFace );

  TIDSortedElemSet emptySet;
  while ( !startLinks.empty() )
  {
    const SMESH_TLink& link  = startLinks.front()._link;
    TIDSortedElemSet&  faces = startLinks.front()._faces;

    outerFace = *faces.begin();
    // find other faces sharing the link
    const SMDS_MeshElement* f;
    while (( f = SMESH_MeshEditor::FindFaceInSet(link.node1(), link.node2(), emptySet, faces )))
      faces.insert( f );

    // select another outer face among the found 
    const SMDS_MeshElement* outerFace2 = 0;
    if ( faces.size() == 2 )
    {
      outerFace2 = (outerFace == *faces.begin() ? *faces.rbegin() : *faces.begin());
    }
    else if ( faces.size() > 2 )
    {
      seamLinks.insert( link );

      // link direction within the outerFace
      gp_Vec n1n2( SMESH_TNodeXYZ( link.node1()),
                   SMESH_TNodeXYZ( link.node2()));
      int i1 = outerFace->GetNodeIndex( link.node1() );
      int i2 = outerFace->GetNodeIndex( link.node2() );
      bool rev = ( abs(i2-i1) == 1 ? i1 > i2 : i2 > i1 );
      if ( rev ) n1n2.Reverse();
      // outerFace normal
      gp_XYZ ofNorm, fNorm;
      if ( SMESH_Algo::FaceNormal( outerFace, ofNorm, /*normalized=*/false ))
      {
        // direction from the link inside outerFace
        gp_Vec dirInOF = gp_Vec( ofNorm ) ^ n1n2;
        // sort all other faces by angle with the dirInOF
        map< double, const SMDS_MeshElement* > angle2Face;
        set< const SMDS_MeshElement*, TIDCompare >::const_iterator face = faces.begin();
        for ( ; face != faces.end(); ++face )
        {
          if ( !SMESH_Algo::FaceNormal( *face, fNorm, /*normalized=*/false ))
            continue;
          gp_Vec dirInF = gp_Vec( fNorm ) ^ n1n2;
          double angle = dirInOF.AngleWithRef( dirInF, n1n2 );
          if ( angle < 0 ) angle += 2. * M_PI;
          angle2Face.insert( make_pair( angle, *face ));
        }
        if ( !angle2Face.empty() )
          outerFace2 = angle2Face.begin()->second;
      }
    }
    // store the found outer face and add its links to continue seaching from
    if ( outerFace2 )
    {
      _outerFaces.insert( outerFace );
      int nbNodes = outerFace2->NbNodes()/( outerFace2->IsQuadratic() ? 2 : 1 );
      for ( int i = 0; i < nbNodes; ++i )
      {
        SMESH_TLink link2( outerFace2->GetNode(i), outerFace2->GetNode((i+1)%nbNodes));
        if ( visitedLinks.insert( link2 ).second )
          startLinks.push_back( TFaceLink( link2.node1(), link2.node2(), outerFace2 ));
      }
    }
    startLinks.pop_front();
  }
  _outerFacesFound = true;

  if ( !seamLinks.empty() )
  {
    // There are internal boundaries touching the outher one,
    // find all faces of internal boundaries in order to find
    // faces of boundaries of holes, if any.
    
  }
  else
  {
    _outerFaces.clear();
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void SMESH_ElementSearcherImpl::GetElementsNearLine ( const gp_Ax1 &  line,
SMDSAbs_ElementType  type,
vector< const SMDS_MeshElement * > &  foundElems 
) [virtual]

Return elements possibly intersecting the line.

Implements SMESH_ElementSearcher.

Definition at line 6788 of file SMESH_MeshEditor.cxx.

{
  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());
}
bool SMESH_ElementSearcherImpl::getIntersParamOnLine ( const gp_Lin &  line,
const SMDS_MeshElement *  face,
const double  tolerance,
double &  param 
)

Find intersection of the line and an edge of face and return parameter on line.

Definition at line 6368 of file SMESH_MeshEditor.cxx.

{
  int nbInts = 0;
  param = 0;

  GeomAPI_ExtremaCurveCurve anExtCC;
  Handle(Geom_Curve) lineCurve = new Geom_Line( line );
  
  int nbNodes = face->IsQuadratic() ? face->NbNodes()/2 : face->NbNodes();
  for ( int i = 0; i < nbNodes && nbInts < 2; ++i )
  {
    GC_MakeSegment edge( SMESH_TNodeXYZ( face->GetNode( i )),
                         SMESH_TNodeXYZ( face->GetNode( (i+1)%nbNodes) )); 
    anExtCC.Init( lineCurve, edge);
    if ( anExtCC.NbExtrema() > 0 && anExtCC.LowerDistance() <= tol)
    {
      Quantity_Parameter pl, pe;
      anExtCC.LowerDistanceParameters( pl, pe );
      param += pl;
      if ( ++nbInts == 2 )
        break;
    }
  }
  if ( nbInts > 0 ) param /= nbInts;
  return nbInts > 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

TopAbs_State SMESH_ElementSearcherImpl::GetPointState ( const gp_Pnt &  point) [virtual]

Classify the given point in the closed 2D mesh.

Implements SMESH_ElementSearcher.

Definition at line 6565 of file SMESH_MeshEditor.cxx.

{
  double tolerance = getTolerance();
  if ( !_ebbTree || _elementType != SMDSAbs_Face )
  {
    if ( _ebbTree ) delete _ebbTree;
    _ebbTree = new ElementBndBoxTree( *_mesh, _elementType = SMDSAbs_Face, _meshPartIt );
  }
  // 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.

  const int nbAxes = 3;
  gp_Dir axisDir[ nbAxes ] = { gp::DX(), gp::DY(), gp::DZ() };
  map< double, TInters >   paramOnLine2TInters[ nbAxes ];
  list< TInters > tangentInters[ nbAxes ]; // of faces whose plane includes the line
  multimap< int, int > nbInt2Axis; // to find the simplest case
  for ( int axis = 0; axis < nbAxes; ++axis )
  {
    gp_Ax1 lineAxis( point, axisDir[axis]);
    gp_Lin line    ( lineAxis );

    TIDSortedElemSet suspectFaces; // faces possibly intersecting the line
    _ebbTree->getElementsNearLine( lineAxis, suspectFaces );

    // Intersect faces with the line

    map< double, TInters > & u2inters = paramOnLine2TInters[ axis ];
    TIDSortedElemSet::iterator face = suspectFaces.begin();
    for ( ; face != suspectFaces.end(); ++face )
    {
      // get face plane
      gp_XYZ fNorm;
      if ( !SMESH_Algo::FaceNormal( *face, fNorm, /*normalized=*/false)) continue;
      gp_Pln facePlane( SMESH_TNodeXYZ( (*face)->GetNode(0)), fNorm );

      // perform intersection
      IntAna_IntConicQuad intersection( line, IntAna_Quadric( facePlane ));
      if ( !intersection.IsDone() )
        continue;
      if ( intersection.IsInQuadric() )
      {
        tangentInters[ axis ].push_back( TInters( *face, fNorm, true ));
      }
      else if ( ! intersection.IsParallel() && intersection.NbPoints() > 0 )
      {
        gp_Pnt intersectionPoint = intersection.Point(1);
        if ( !SMESH_MeshEditor::isOut( *face, intersectionPoint, tolerance ))
          u2inters.insert(make_pair( intersection.ParamOnConic(1), TInters( *face, fNorm )));
      }
    }
    // Analyse intersections roughly

    int nbInter = u2inters.size();
    if ( nbInter == 0 )
      return TopAbs_OUT; 

    double f = u2inters.begin()->first, l = u2inters.rbegin()->first;
    if ( nbInter == 1 ) // not closed mesh
      return fabs( f ) < tolerance ? TopAbs_ON : TopAbs_UNKNOWN;

    if ( fabs( f ) < tolerance || fabs( l ) < tolerance )
      return TopAbs_ON;

    if ( (f<0) == (l<0) )
      return TopAbs_OUT;

    int nbIntBeforePoint = std::distance( u2inters.begin(), u2inters.lower_bound(0));
    int nbIntAfterPoint  = nbInter - nbIntBeforePoint;
    if ( nbIntBeforePoint == 1 || nbIntAfterPoint == 1 )
      return TopAbs_IN;

    nbInt2Axis.insert( make_pair( min( nbIntBeforePoint, nbIntAfterPoint ), axis ));

    if ( _outerFacesFound ) break; // pass to thorough analysis

  } // three attempts - loop on CS axes

  // Analyse intersections thoroughly.
  // We make two loops maximum, on the first one we only exclude touching intersections,
  // on the second, if situation is still unclear, we gather and use information on
  // position of faces (internal or outer). If faces position is already gathered,
  // we make the second loop right away.

  for ( int hasPositionInfo = _outerFacesFound; hasPositionInfo < 2; ++hasPositionInfo )
  {
    multimap< int, int >::const_iterator nb_axis = nbInt2Axis.begin();
    for ( ; nb_axis != nbInt2Axis.end(); ++nb_axis )
    {
      int axis = nb_axis->second;
      map< double, TInters > & u2inters = paramOnLine2TInters[ axis ];

      gp_Ax1 lineAxis( point, axisDir[axis]);
      gp_Lin line    ( lineAxis );

      // add tangent intersections to u2inters
      double param;
      list< TInters >::const_iterator tgtInt = tangentInters[ axis ].begin();
      for ( ; tgtInt != tangentInters[ axis ].end(); ++tgtInt )
        if ( getIntersParamOnLine( line, tgtInt->_face, tolerance, param ))
          u2inters.insert(make_pair( param, *tgtInt ));
      tangentInters[ axis ].clear();

      // Count intersections before and after the point excluding touching ones.
      // If hasPositionInfo we count intersections of outer boundary only

      int nbIntBeforePoint = 0, nbIntAfterPoint = 0;
      double f = numeric_limits<double>::max(), l = -numeric_limits<double>::max();
      map< double, TInters >::iterator u_int1 = u2inters.begin(), u_int2 = u_int1;
      bool ok = ! u_int1->second._coincides;
      while ( ok && u_int1 != u2inters.end() )
      {
        double u = u_int1->first;
        bool touchingInt = false;
        if ( ++u_int2 != u2inters.end() )
        {
          // skip intersections at the same point (if the line passes through edge or node)
          int nbSamePnt = 0;
          while ( u_int2 != u2inters.end() && fabs( u_int2->first - u ) < tolerance )
          {
            ++nbSamePnt;
            ++u_int2;
          }

          // skip tangent intersections
          int nbTgt = 0;
          const SMDS_MeshElement* prevFace = u_int1->second._face;
          while ( ok && u_int2->second._coincides )
          {
            if ( SMESH_Algo::GetCommonNodes(prevFace , u_int2->second._face).empty() )
              ok = false;
            else
            {
              nbTgt++;
              u_int2++;
              ok = ( u_int2 != u2inters.end() );
            }
          }
          if ( !ok ) break;

          // skip intersections at the same point after tangent intersections
          if ( nbTgt > 0 )
          {
            double u2 = u_int2->first;
            ++u_int2;
            while ( u_int2 != u2inters.end() && fabs( u_int2->first - u2 ) < tolerance )
            {
              ++nbSamePnt;
              ++u_int2;
            }
          }
          // decide if we skipped a touching intersection
          if ( nbSamePnt + nbTgt > 0 )
          {
            double minDot = numeric_limits<double>::max(), maxDot = -numeric_limits<double>::max();
            map< double, TInters >::iterator u_int = u_int1;
            for ( ; u_int != u_int2; ++u_int )
            {
              if ( u_int->second._coincides ) continue;
              double dot = u_int->second._faceNorm * line.Direction();
              if ( dot > maxDot ) maxDot = dot;
              if ( dot < minDot ) minDot = dot;
            }
            touchingInt = ( minDot*maxDot < 0 );
          }
        }
        if ( !touchingInt )
        {
          if ( !hasPositionInfo || isOuterBoundary( u_int1->second._face ))
          {
            if ( u < 0 )
              ++nbIntBeforePoint;
            else
              ++nbIntAfterPoint;
          }
          if ( u < f ) f = u;
          if ( u > l ) l = u;
        }

        u_int1 = u_int2; // to next intersection

      } // loop on intersections with one line

      if ( ok )
      {
        if ( fabs( f ) < tolerance || fabs( l ) < tolerance )
          return TopAbs_ON;

        if ( nbIntBeforePoint == 0  || nbIntAfterPoint == 0)
          return TopAbs_OUT; 

        if ( nbIntBeforePoint + nbIntAfterPoint == 1 ) // not closed mesh
          return fabs( f ) < tolerance ? TopAbs_ON : TopAbs_UNKNOWN;

        if ( nbIntBeforePoint == 1 || nbIntAfterPoint == 1 )
          return TopAbs_IN;

        if ( (f<0) == (l<0) )
          return TopAbs_OUT;

        if ( hasPositionInfo )
          return nbIntBeforePoint % 2 ? TopAbs_IN : TopAbs_OUT;
      }
    } // loop on intersections of the tree lines - thorough analysis

    if ( !hasPositionInfo )
    {
      // gather info on faces position - is face in the outer boundary or not
      map< double, TInters > & u2inters = paramOnLine2TInters[ 0 ];
      findOuterBoundary( u2inters.begin()->second._face );
    }

  } // two attempts - with and w/o faces position info in the mesh

  return TopAbs_UNKNOWN;
}

Here is the call graph for this function:

define tolerance for search

Definition at line 6309 of file SMESH_MeshEditor.cxx.

{
  if ( _tolerance < 0 )
  {
    const SMDS_MeshInfo& meshInfo = _mesh->GetMeshInfo();

    _tolerance = 0;
    if ( _nodeSearcher && meshInfo.NbNodes() > 1 )
    {
      double boxSize = _nodeSearcher->getTree()->maxSize();
      _tolerance = 1e-8 * boxSize/* / meshInfo.NbNodes()*/;
    }
    else if ( _ebbTree && meshInfo.NbElements() > 0 )
    {
      double boxSize = _ebbTree->maxSize();
      _tolerance = 1e-8 * boxSize/* / meshInfo.NbElements()*/;
    }
    if ( _tolerance == 0 )
    {
      // define tolerance by size of a most complex element
      int complexType = SMDSAbs_Volume;
      while ( complexType > SMDSAbs_All &&
              meshInfo.NbElements( SMDSAbs_ElementType( complexType )) < 1 )
        --complexType;
      if ( complexType == SMDSAbs_All ) return 0; // empty mesh
      double elemSize;
      if ( complexType == int( SMDSAbs_Node ))
      {
        SMDS_NodeIteratorPtr nodeIt = _mesh->nodesIterator();
        elemSize = 1;
        if ( meshInfo.NbNodes() > 2 )
          elemSize = SMESH_TNodeXYZ( nodeIt->next() ).Distance( nodeIt->next() );
      }
      else
      {
        SMDS_ElemIteratorPtr elemIt =
            _mesh->elementsIterator( SMDSAbs_ElementType( complexType ));
        const SMDS_MeshElement* elem = elemIt->next();
        SMDS_ElemIteratorPtr nodeIt = elem->nodesIterator();
        SMESH_TNodeXYZ n1( cast2Node( nodeIt->next() ));
        elemSize = 0;
        while ( nodeIt->more() )
        {
          double dist = n1.Distance( cast2Node( nodeIt->next() ));
          elemSize = max( dist, elemSize );
        }
      }
      _tolerance = 1e-4 * elemSize;
    }
  }
  return _tolerance;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool SMESH_ElementSearcherImpl::isOuterBoundary ( const SMDS_MeshElement *  face) const [inline]

Definition at line 6276 of file SMESH_MeshEditor.cxx.

  {
    return _outerFaces.empty() || _outerFaces.count(face);
  }

Here is the caller graph for this function:


Member Data Documentation

Definition at line 6250 of file SMESH_MeshEditor.cxx.

Definition at line 6252 of file SMESH_MeshEditor.cxx.

Definition at line 6248 of file SMESH_MeshEditor.cxx.

Definition at line 6249 of file SMESH_MeshEditor.cxx.

Definition at line 6251 of file SMESH_MeshEditor.cxx.

set<const SMDS_MeshElement*> SMESH_ElementSearcherImpl::_outerFaces

Definition at line 6255 of file SMESH_MeshEditor.cxx.

Definition at line 6254 of file SMESH_MeshEditor.cxx.

Definition at line 6253 of file SMESH_MeshEditor.cxx.


The documentation for this struct was generated from the following file: