src/SMESHUtils/SMESH_FreeBorders.cxx

   1 // Copyright (C) 2007-2015  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19 // File      : SMESH_FreeBorders.cxx
  20 // Created   : Tue Sep  8 17:08:39 2015
  21 // Author    : Edward AGAPOV (eap)
  22
  23 //================================================================================
  24 // Implementation of SMESH_MeshAlgos::FindCoincidentFreeBorders()
  25 //================================================================================
  26
  27 #include "SMESH_MeshAlgos.hxx"
  28
  29 #include "SMDS_LinearEdge.hxx"
  30 #include "SMDS_Mesh.hxx"
  31 #include "SMDS_SetIterator.hxx"
  32
  33 #include <algorithm>
  34 #include <limits>
  35 #include <set>
  36 #include <vector>
  37
  38 #include <NCollection_DataMap.hxx>
  39 #include <gp_Pnt.hxx>
  40
  41 using namespace SMESH_MeshAlgos;
  42
  43 namespace
  44 {
  45   struct BEdge;
  46
  47   /*!
  48    * \brief Node on a free border
  49    */
  50   struct BNode : public SMESH_TNodeXYZ
  51   {
  52     mutable std::vector< BEdge* > myLinkedEdges;
  53     mutable std::vector< std::pair < BEdge*, double > > myCloseEdges; // edge & U
  54
  55     BNode(const SMDS_MeshNode * node): SMESH_TNodeXYZ( node ) {}
  56     const SMDS_MeshNode * Node() const { return _node; }
  57     void AddLinked( BEdge* e ) const;
  58     void AddClose ( const BEdge* e, double u ) const;
  59     BEdge* GetCloseEdge( size_t i ) const { return myCloseEdges[i].first; }
  60     double GetCloseU( size_t i ) const { return myCloseEdges[i].second; }
  61     BEdge* GetCloseEdgeOfBorder( int borderID, double * u = 0 ) const;
  62     bool IsCloseEdge( const BEdge* ) const;
  63     bool operator<(const BNode& other) const { return Node()->GetID() < other.Node()->GetID(); }
  64   };
  65   /*!
  66    * \brief Edge of a free border
  67    */
  68   struct BEdge : public SMDS_LinearEdge
  69   {
  70     const BNode*            myBNode1;
  71     const BNode*            myBNode2;
  72     int                     myBorderID;
  73     int                     myID; // within a border
  74     BEdge*                  myPrev;
  75     BEdge*                  myNext;
  76     const SMDS_MeshElement* myFace;
  77     std::set< int >         myCloseBorders;
  78     int                     myInGroup;
  79
  80     BEdge():SMDS_LinearEdge( 0, 0 ), myBorderID(-1), myID(-1), myPrev(0), myNext(0), myInGroup(-1) {}
  81
  82     void Set( const BNode *           node1,
  83               const BNode *           node2,
  84               const SMDS_MeshElement* face,
  85               const int               ID)
  86     {
  87       myBNode1   = node1;
  88       myBNode2   = node2;
  89       myNodes[0] = node1->Node();
  90       myNodes[1] = node2->Node();
  91       myFace     = face;
  92       setId( ID ); // mesh element ID
  93     }
  94     bool IsInGroup() const
  95     {
  96       return myInGroup >= 0;
  97     }
  98     bool Contains( const BNode* n ) const
  99     {
 100       return ( n == myBNode1 || n == myBNode2 );
 101     }
 102     void AddLinked( BEdge* e )
 103     {
 104       if ( e->Contains( myBNode1 )) myPrev = e;
 105       else                          myNext = e;
 106     }
 107     void RemoveLinked( BEdge* e )
 108     {
 109       if ( myPrev == e ) myPrev = 0;
 110       if ( myNext == e ) myNext = 0;
 111     }
 112     void Reverse()
 113     {
 114       std::swap( myBNode1, myBNode2 );
 115       myNodes[0] = myBNode1->Node();
 116       myNodes[1] = myBNode2->Node();
 117     }
 118     void Orient()
 119     {
 120       if (( myPrev && !myPrev->Contains( myBNode1 )) ||
 121           ( myNext && !myNext->Contains( myBNode2 )))
 122         std::swap( myPrev, myNext );
 123       if ( myPrev && myPrev->myBNode2 != myBNode1 ) myPrev->Reverse();
 124       if ( myNext && myNext->myBNode1 != myBNode2 ) myNext->Reverse();
 125     }
 126     void SetID( int id )
 127     {
 128       if ( myID < 0 )
 129       {
 130         myID = id;
 131         if ( myNext )
 132           myNext->SetID( id + 1 );
 133       }
 134     }
 135     bool IsOut( const gp_XYZ& point, const double tol, double& u ) const
 136     {
 137       gp_XYZ  me = *myBNode2 - *myBNode1;
 138       gp_XYZ n1p = point     - *myBNode1;
 139       u = ( me * n1p ) / me.SquareModulus(); // param [0,1] on this
 140       if ( u < 0. ) return ( n1p.SquareModulus() > tol * tol );
 141       if ( u > 1. ) return ( ( point - *myBNode2 ).SquareModulus() > tol * tol );
 142
 143       gp_XYZ  proj = ( 1. - u ) * *myBNode1 + u * *myBNode2; // projection of the point on this
 144       double dist2 = ( point - proj ).SquareModulus();
 145       return ( dist2 > tol * tol );
 146     }
 147     bool IsOverlappingProjection( const BEdge* toE, const double u, bool is1st ) const
 148     {
 149       // is1st shows which end of toE is projected on this at u
 150       double u2;
 151       const double eps = 0.1;
 152       if ( toE == myBNode1->GetCloseEdgeOfBorder( toE->myBorderID, &u2 ) ||
 153            toE == myBNode2->GetCloseEdgeOfBorder( toE->myBorderID, &u2 ))
 154         return (( 0 < u2 && u2 < 1 ) &&     // u2 is proj param of myBNode's on toE
 155                 ( Abs( u2 - int( !is1st )) > eps ));
 156
 157       const BNode* n = is1st ? toE->myBNode2 : toE->myBNode1;
 158       if ( this == n->GetCloseEdgeOfBorder( this->myBorderID, &u2 ))
 159         return Abs( u - u2 ) > eps;
 160       return false;
 161     }
 162     bool GetRangeOfSameCloseBorders(BEdge* eRange[2], const std::set< int >& bordIDs)
 163     {
 164       if ( this->myCloseBorders != bordIDs )
 165         return false;
 166
 167       eRange[0] = this;
 168       while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == bordIDs )
 169       {
 170         if ( eRange[0]->myPrev == this /*|| eRange[0]->myPrev->myInGroup*/ )
 171           break;
 172         eRange[0] = eRange[0]->myPrev;
 173       }
 174
 175       eRange[1] = this;
 176       if ( eRange[0]->myPrev != this ) // not closed range
 177         while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == bordIDs )
 178         {
 179           if ( eRange[1]->myNext == this /*|| eRange[1]->myNext->myInGroup*/ )
 180             break;
 181           eRange[1] = eRange[1]->myNext;
 182         }
 183
 184       return ( eRange[0] != eRange[1] );
 185     }
 186   }; // class BEdge
 187
 188   void extendPart( BEdge* & e1, BEdge* & e2, const std::set< int >& bordIDs, int groupID )
 189   {
 190     if (( e1->myPrev == e2 ) ||
 191         ( e1 == e2 && e1->myPrev && e1->myPrev->myInGroup == groupID ))
 192       return; // full free border already
 193
 194     double u;
 195     BEdge* be;
 196     std::set<int>::const_iterator bord;
 197     if ( e1->myPrev )
 198     {
 199       for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
 200         if ((  *bord != e1->myBorderID ) &&
 201             (( be = e1->myBNode1->GetCloseEdgeOfBorder( *bord, &u ))) &&
 202             (  be->myInGroup == groupID ) &&
 203             (  0 < u && u < 1 ) &&
 204             (  be->IsOverlappingProjection( e1->myPrev, u, false )))
 205         {
 206           e1 = e1->myPrev;
 207           break;
 208         }
 209     }
 210     if ( e2->myNext )
 211     {
 212       for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
 213         if ((  *bord != e2->myBorderID ) &&
 214             (( be = e2->myBNode2->GetCloseEdgeOfBorder( *bord, &u ))) &&
 215             (  be->myInGroup == groupID ) &&
 216             (  0 < u && u < 1 ) &&
 217             (  be->IsOverlappingProjection( e2->myNext, u, true )))
 218         {
 219           e2 = e2->myNext;
 220           break;
 221         }
 222     }
 223   }
 224
 225   void BNode::AddLinked( BEdge* e ) const
 226   {
 227     myLinkedEdges.reserve(2);
 228     myLinkedEdges.push_back( e );
 229     if ( myLinkedEdges.size() < 2 ) return;
 230
 231     if ( myLinkedEdges.size() == 2 )
 232     {
 233       myLinkedEdges[0]->AddLinked( myLinkedEdges[1] );
 234       myLinkedEdges[1]->AddLinked( myLinkedEdges[0] );
 235     }
 236     else
 237     {
 238       for ( size_t i = 0; i < myLinkedEdges.size(); ++i )
 239         for ( size_t j = 0; j < myLinkedEdges.size(); ++j )
 240           if ( i != j )
 241             myLinkedEdges[i]->RemoveLinked( myLinkedEdges[j] );
 242     }
 243   }
 244   void BNode::AddClose ( const BEdge* e, double u ) const
 245   {
 246     if ( ! e->Contains( this ))
 247       myCloseEdges.push_back( make_pair( const_cast< BEdge* >( e ), u ));
 248   }
 249   BEdge* BNode::GetCloseEdgeOfBorder( int borderID, double * uPtr ) const
 250   {
 251     BEdge* e = 0;
 252     double u = 0;
 253     for ( size_t i = 0; i < myCloseEdges.size(); ++i )
 254       if ( borderID == GetCloseEdge( i )->myBorderID )
 255       {
 256         if ( e && Abs( u - 0.5 ) < Abs( GetCloseU( i ) - 0.5 ))
 257           continue;
 258         u = GetCloseU( i );
 259         e = GetCloseEdge ( i );
 260       }
 261     if ( uPtr ) *uPtr = u;
 262     return e;
 263   }
 264   bool BNode::IsCloseEdge( const BEdge* e ) const
 265   {
 266     for ( size_t i = 0; i < myCloseEdges.size(); ++i )
 267       if ( e == GetCloseEdge( i ) )
 268         return true;
 269     return false;
 270   }
 271
 272   /// Accessor to SMDS_MeshElement* inherited by BEdge
 273   struct ElemAcess
 274   {
 275     static const SMDS_MeshElement* value( std::vector< BEdge >::const_iterator it)
 276     {
 277       return & (*it);
 278     }
 279   };
 280   /// Iterator over a vector of BEdge's
 281   static SMDS_ElemIteratorPtr getElemIterator( const std::vector< BEdge > & bedges )
 282   {
 283     typedef SMDS_SetIterator
 284       < const SMDS_MeshElement*, std::vector< BEdge >::const_iterator, ElemAcess > BEIter;
 285     return SMDS_ElemIteratorPtr( new BEIter( bedges.begin(), bedges.end() ));
 286   }
 287
 288 } // namespace
 289
 290 // struct needed for NCollection_Map
 291 struct TLinkHasher
 292 {
 293   static int HashCode(const SMESH_TLink& link, int aLimit)
 294   {
 295     return ::HashCode( link.node1()->GetID() + link.node2()->GetID(), aLimit );
 296   }
 297   static Standard_Boolean IsEqual(const SMESH_TLink& l1, const SMESH_TLink& l2)
 298   {
 299     return ( l1.node1() == l2.node1() && l1.node2() == l2.node2() );
 300   }
 301 };
 302
 303 //================================================================================
 304 /*
 305  * Returns groups of TFreeBorder's coincident within the given tolerance.
 306  * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
 307  * to free borders being compared is used.
 308  */
 309 //================================================================================
 310
 311 void SMESH_MeshAlgos::FindCoincidentFreeBorders(SMDS_Mesh&              mesh,
 312                                                 double                  tolerance,
 313                                                 CoincidentFreeBorders & foundFreeBordes)
 314 {
 315   // find free links
 316   typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, TLinkHasher > TLink2FaceMap;
 317   TLink2FaceMap linkMap;
 318   SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
 319   while ( faceIt->more() )
 320   {
 321     const SMDS_MeshElement* face = faceIt->next();
 322     if ( !face ) continue;
 323
 324     const SMDS_MeshNode*     n0 = face->GetNode( face->NbNodes() - 1 );
 325     SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
 326     while ( nodeIt->more() )
 327     {
 328       const SMDS_MeshNode* n1 = nodeIt->next();
 329       SMESH_TLink link( n0, n1 );
 330       if ( !linkMap.Bind( link, face ))
 331         linkMap.UnBind( link );
 332       n0 = n1;
 333     }
 334   }
 335   if ( linkMap.IsEmpty() )
 336     return;
 337
 338   // form free borders
 339   std::set   < BNode > bNodes;
 340   std::vector< BEdge > bEdges( linkMap.Extent() );
 341
 342   TLink2FaceMap::Iterator linkIt( linkMap );
 343   for ( int iEdge = 0; linkIt.More(); linkIt.Next(), ++iEdge )
 344   {
 345     const SMESH_TLink & link = linkIt.Key();
 346     std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
 347     std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
 348     bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
 349     n1->AddLinked( & bEdges[ iEdge ] );
 350     n2->AddLinked( & bEdges[ iEdge ] );
 351   }
 352   linkMap.Clear();
 353
 354   // assign IDs to borders
 355   std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
 356   std::set< BNode >::iterator bn = bNodes.begin();
 357   for ( ; bn != bNodes.end(); ++bn )
 358   {
 359     for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
 360     {
 361       if ( bn->myLinkedEdges[i]->myBorderID < 0 )
 362       {
 363         BEdge* be = bn->myLinkedEdges[i];
 364         int borderID = borders.size();
 365         borders.push_back( be );
 366         for ( ; be && be->myBorderID < 0; be = be->myNext )
 367         {
 368           be->myBorderID = borderID;
 369           be->Orient();
 370         }
 371         bool isClosed = ( be == bn->myLinkedEdges[i] );
 372         be = bn->myLinkedEdges[i]->myPrev;
 373         for ( ; be && be->myBorderID < 0; be = be->myPrev )
 374         {
 375           be->myBorderID = borderID;
 376           be->Orient();
 377         }
 378         if ( !isClosed )
 379           while ( borders.back()->myPrev )
 380             borders.back() = borders.back()->myPrev;
 381
 382         borders.back()->SetID( 0 ); // set IDs to all edges of the border
 383       }
 384     }
 385   }
 386
 387   // compute tolerance of each border
 388   double maxTolerance = tolerance;
 389   std::vector< double > bordToler( borders.size(), tolerance );
 390   if ( maxTolerance < std::numeric_limits< double >::min() )
 391   {
 392     // no tolerance provided by the user; compute tolerance of each border
 393     // as one tenth of an average size of faces adjacent to a border
 394     for ( size_t i = 0; i < borders.size(); ++i )
 395     {
 396       double avgFaceSize = 0;
 397       int    nbFaces     = 0;
 398       BEdge* be = borders[ i ];
 399       do {
 400         double facePerimeter = 0;
 401         gp_Pnt p0 = SMESH_TNodeXYZ( be->myFace->GetNode( be->myFace->NbNodes() - 1 ));
 402         SMDS_NodeIteratorPtr nodeIt = be->myFace->interlacedNodesIterator();
 403         while ( nodeIt->more() )
 404         {
 405           gp_Pnt p1 = SMESH_TNodeXYZ( nodeIt->next() );
 406           facePerimeter += p0.Distance( p1 );
 407           p0 = p1;
 408         }
 409         avgFaceSize += ( facePerimeter / be->myFace->NbCornerNodes() );
 410         nbFaces++;
 411
 412         be = be->myNext;
 413       }
 414       while ( be && be != borders[i] );
 415
 416       bordToler[ i ] = 0.1 * avgFaceSize / nbFaces;
 417       maxTolerance = Max( maxTolerance, bordToler[ i ]);
 418     }
 419   }
 420
 421   // for every border node find close border edges
 422   SMESH_ElementSearcher* searcher =
 423     GetElementSearcher( mesh, getElemIterator( bEdges ), maxTolerance );
 424   SMESHUtils::Deleter< SMESH_ElementSearcher > searcherDeleter( searcher );
 425   std::vector< const SMDS_MeshElement* > candidateEdges;
 426   for ( bn = bNodes.begin(); bn != bNodes.end(); ++bn )
 427   {
 428     searcher->FindElementsByPoint( *bn, SMDSAbs_Edge, candidateEdges );
 429     if ( candidateEdges.size() <= bn->myLinkedEdges.size() )
 430       continue;
 431
 432     double nodeTol = 0, u;
 433     for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
 434       nodeTol = Max( nodeTol, bordToler[ bn->myLinkedEdges[ i ]->myBorderID ]);
 435
 436     for ( size_t i = 0; i < candidateEdges.size(); ++i )
 437     {
 438       const BEdge* be = static_cast< const BEdge* >( candidateEdges[ i ]);
 439       double      tol = Max( nodeTol, bordToler[ be->myBorderID ]);
 440       if ( !be->IsOut( *bn, tol, u ))
 441         bn->AddClose( be, u );
 442     }
 443   }
 444
 445   // for every border edge find close borders
 446
 447   std::vector< BEdge* > closeEdges;
 448   for ( size_t i = 0; i < bEdges.size(); ++i )
 449   {
 450     BEdge& be = bEdges[i];
 451     if ( be.myBNode1->myCloseEdges.empty() ||
 452          be.myBNode2->myCloseEdges.empty() )
 453       continue;
 454
 455     closeEdges.clear();
 456     for ( size_t iE1 = 0; iE1 < be.myBNode1->myCloseEdges.size(); ++iE1 )
 457     {
 458       // find edges of the same border close to both nodes of the edge
 459       BEdge* closeE1 = be.myBNode1->GetCloseEdge( iE1 );
 460       BEdge* closeE2 = be.myBNode2->GetCloseEdgeOfBorder( closeE1->myBorderID );
 461       if ( !closeE2 )
 462         continue;
 463       // check that edges connecting closeE1 and closeE2 (if any) are also close to 'be'
 464       if ( closeE1 != closeE2 )
 465       {
 466         bool coincide;
 467         for ( int j = 0; j < 2; ++j ) // move closeE1 -> closeE2 or inversely
 468         {
 469           BEdge* ce = closeE1;
 470           do {
 471             coincide = ( ce->myBNode2->GetCloseEdgeOfBorder( be.myBorderID ));
 472             ce       = ce->myNext;
 473           } while ( coincide && ce && ce != closeE2 );
 474
 475           if ( coincide && ce == closeE2 )
 476             break;
 477           if ( j == 0 )
 478             std::swap( closeE1, closeE2 );
 479           coincide = false;
 480         }
 481         if ( !coincide )
 482           continue;
 483         closeEdges.push_back( closeE1 );
 484         closeEdges.push_back( closeE2 );
 485       }
 486       else
 487       {
 488         closeEdges.push_back( closeE1 );
 489       }
 490       be.myCloseBorders.insert( closeE1->myBorderID );
 491     }
 492     if ( !closeEdges.empty() )
 493     {
 494       be.myCloseBorders.insert( be.myBorderID );
 495       // for ( size_t iB = 0; iB < closeEdges.size(); ++iB )
 496       //   closeEdges[ iB ]->myCloseBorders.insert( be.myCloseBorders.begin(),
 497       //                                            be.myCloseBorders.end() );
 498     }
 499   }
 500
 501   // Fill in CoincidentFreeBorders
 502
 503   // save nodes of free borders
 504   foundFreeBordes._borders.resize( borders.size() );
 505   for ( size_t i = 0; i < borders.size(); ++i )
 506   {
 507     BEdge* be = borders[i];
 508     foundFreeBordes._borders[i].push_back( be->myBNode1->Node() );
 509     do {
 510       foundFreeBordes._borders[i].push_back( be->myBNode2->Node() );
 511       be = be->myNext;
 512     }
 513     while ( be && be != borders[i] );
 514   }
 515
 516   // form groups of coincident parts of free borders
 517
 518   TFreeBorderPart  part;
 519   TCoincidentGroup group;
 520   vector< BEdge* > ranges; // couples of edges delimiting parts
 521   BEdge* be = 0; // a current edge
 522   int skipGroup = bEdges.size(); // a group ID used to avoid repeating treatment of edges
 523
 524   for ( int i = 0, nbBords = borders.size(); i < nbBords; i += bool(!be) )
 525   {
 526     if ( !be )
 527       be = borders[i];
 528
 529     // look for an edge close to other borders
 530     do {
 531       if ( !be->IsInGroup() && !be->myCloseBorders.empty() )
 532         break;
 533       be = be->myNext;
 534     } while ( be && be != borders[i] );
 535
 536     if ( !be || be->IsInGroup() || be->myCloseBorders.empty() )
 537     {
 538       be = 0;
 539       continue; // all edges of a border are treated or non-coincident
 540     }
 541     group.clear();
 542     ranges.clear();
 543
 544     // look for the 1st and last edge of a coincident group
 545     BEdge* beRange[2];
 546     if ( !be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders ))
 547     {
 548       be->myInGroup = skipGroup;
 549       be = be->myNext;
 550       continue;
 551     }
 552
 553     ranges.push_back( beRange[0] );
 554     ranges.push_back( beRange[1] );
 555
 556     int groupID = foundFreeBordes._coincidentGroups.size();
 557     be = beRange[0];
 558     be->myInGroup = groupID;
 559     while ( be != beRange[1] )
 560     {
 561       be->myInGroup = groupID;
 562       be = be->myNext;
 563     }
 564     beRange[1]->myInGroup = groupID;
 565
 566     // add parts of other borders
 567
 568     BEdge* be1st = beRange[0];
 569     closeEdges.clear();
 570     std::set<int>::iterator closeBord = be1st->myCloseBorders.begin();
 571     for ( ; closeBord != be1st->myCloseBorders.end(); ++closeBord )
 572       closeEdges.push_back( be1st->myBNode2->GetCloseEdgeOfBorder( *closeBord ));
 573
 574     for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
 575     {
 576       be = closeEdges[ iE ];
 577       if ( !be ) continue;
 578
 579       bool ok = be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders );
 580       if ( !ok && be->myPrev )
 581         ok = be->myPrev->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
 582       if ( !ok && be->myNext )
 583         ok = be->myNext->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
 584       if ( !ok )
 585         continue;
 586
 587       be = beRange[0];
 588       if ( be->myCloseBorders != be1st->myCloseBorders )
 589       {
 590         //add missing edges to closeEdges
 591         closeBord = be->myCloseBorders.begin();
 592         for ( ; closeBord != be->myCloseBorders.end(); ++closeBord )
 593           if ( !be1st->myCloseBorders.count( *closeBord ))
 594             closeEdges.push_back( be->myBNode2->GetCloseEdgeOfBorder( *closeBord ));
 595       }
 596
 597       ranges.push_back( beRange[0] );
 598       ranges.push_back( beRange[1] );
 599
 600       be->myInGroup = groupID;
 601       while ( be != beRange[1] )
 602       {
 603         be->myInGroup = groupID;
 604         be = be->myNext;
 605       }
 606       beRange[1]->myInGroup = groupID;
 607     }
 608
 609     if ( ranges.size() > 2 )
 610     {
 611       for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
 612         extendPart( ranges[ iR-1 ], ranges[ iR ], be1st->myCloseBorders, groupID );
 613
 614       // fill in a group
 615       beRange[0] = ranges[0];
 616       beRange[1] = ranges[1];
 617
 618       part._border   = i;
 619       part._node1    = beRange[0]->myID;
 620       part._node2    = beRange[0]->myID + 1;
 621       part._nodeLast = beRange[1]->myID + 1;
 622       group.push_back( part );
 623
 624       be1st = beRange[0];
 625       for ( size_t iR = 3; iR < ranges.size(); iR += 2 )
 626       {
 627         beRange[0] = ranges[iR-1];
 628         beRange[1] = ranges[iR-0];
 629
 630         // find out mutual orientation of borders
 631         double u1, u2;
 632         be1st       ->IsOut( *beRange[ 0 ]->myBNode1, maxTolerance, u1 );
 633         beRange[ 0 ]->IsOut( *be1st->myBNode1,        maxTolerance, u2 );
 634         bool reverse = (( u1 < 0 || u1 > 1 ) && ( u2 < 0 || u2 > 1 ));
 635
 636         // fill in a group
 637         part._border   = beRange[0]->myBorderID;
 638         if ( reverse ) {
 639           part._node1    = beRange[1]->myID + 1;
 640           part._node2    = beRange[1]->myID;
 641           part._nodeLast = beRange[0]->myID;
 642         }
 643         else  {
 644           part._node1    = beRange[0]->myID;
 645           part._node2    = beRange[0]->myID + 1;
 646           part._nodeLast = beRange[1]->myID + 1;
 647         }
 648         group.push_back( part );
 649       }
 650       foundFreeBordes._coincidentGroups.push_back( group );
 651     }
 652     else
 653     {
 654       beRange[0] = ranges[0];
 655       beRange[1] = ranges[1];
 656
 657       be = beRange[0];
 658       be->myInGroup = skipGroup;
 659       while ( be != beRange[1] )
 660       {
 661         be->myInGroup = skipGroup;
 662         be = be->myNext;
 663       }
 664       beRange[1]->myInGroup = skipGroup;
 665     }
 666
 667     be = ranges[1];
 668
 669   } // loop on free borders
 670
 671   return;
 672
 673 } // SMESH_MeshAlgos::FindCoincidentFreeBorders()
 674