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
  51   {
  52     const SMDS_MeshNode *         myNode;
  53     mutable std::vector< BEdge* > myLinkedEdges;
  54     mutable std::vector< BEdge* > myCloseEdges;
  55
  56     BNode(const SMDS_MeshNode * node): myNode( node ) {}
  57     void AddLinked( BEdge* e ) const;
  58     void AddClose ( const BEdge* e ) const;
  59     BEdge* FindCloseEdgeOfBorder( int borderID ) const;
  60     bool operator<(const BNode& other) const { return myNode->GetID() < other.myNode->GetID(); }
  61   };
  62   /*!
  63    * \brief Edge of a free border
  64    */
  65   struct BEdge : public SMDS_LinearEdge
  66   {
  67     const BNode*            myBNode1;
  68     const BNode*            myBNode2;
  69     int                     myBorderID;
  70     int                     myID; // within a border
  71     BEdge*                  myPrev;
  72     BEdge*                  myNext;
  73     const SMDS_MeshElement* myFace;
  74     std::set< int >         myCloseBorders;
  75     bool                    myInGroup;
  76
  77     BEdge():SMDS_LinearEdge( 0, 0 ), myBorderID(-1), myID(-1), myPrev(0), myNext(0), myInGroup(0) {}
  78
  79     void Set( const BNode *           node1,
  80               const BNode *           node2,
  81               const SMDS_MeshElement* face,
  82               const int               ID)
  83     {
  84       myBNode1   = node1;
  85       myBNode2   = node2;
  86       myNodes[0] = node1->myNode;
  87       myNodes[1] = node2->myNode;
  88       myFace     = face;
  89       setId( ID ); // mesh element ID
  90     }
  91     bool Contains( const BNode* n ) const
  92     {
  93       return ( n == myBNode1 || n == myBNode2 );
  94     }
  95     void AddLinked( BEdge* e )
  96     {
  97       if ( e->Contains( myBNode1 )) myPrev = e;
  98       else                          myNext = e;
  99     }
 100     void RemoveLinked( BEdge* e )
 101     {
 102       if ( myPrev == e ) myPrev = 0;
 103       if ( myNext == e ) myNext = 0;
 104     }
 105     void Reverse()
 106     {
 107       std::swap( myBNode1, myBNode2 );
 108       myNodes[0] = myBNode1->myNode;
 109       myNodes[1] = myBNode2->myNode;
 110     }
 111     void Orient()
 112     {
 113       if (( myPrev && !myPrev->Contains( myBNode1 )) ||
 114           ( myNext && !myNext->Contains( myBNode2 )))
 115         std::swap( myPrev, myNext );
 116       if ( myPrev && myPrev->myBNode2 != myBNode1 ) myPrev->Reverse();
 117       if ( myNext && myNext->myBNode1 != myBNode2 ) myNext->Reverse();
 118     }
 119     void SetID( int id )
 120     {
 121       if ( myID < 0 )
 122       {
 123         myID = id;
 124         if ( myNext )
 125           myNext->SetID( id + 1 );
 126       }
 127     }
 128     void FindRangeOfSameCloseBorders(BEdge* eRange[2])
 129     {
 130       eRange[0] = this;
 131       while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == this->myCloseBorders )
 132       {
 133         if ( eRange[0]->myPrev == this /*|| eRange[0]->myPrev->myInGroup*/ )
 134           break;
 135         eRange[0] = eRange[0]->myPrev;
 136       }
 137       eRange[1] = this;
 138       if ( eRange[0]->myPrev != this ) // not closed range
 139         while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == this->myCloseBorders )
 140         {
 141           if ( eRange[1]->myNext == this /*|| eRange[1]->myNext->myInGroup*/ )
 142             break;
 143           eRange[1] = eRange[1]->myNext;
 144         }
 145     }
 146   };
 147
 148   void BNode::AddLinked( BEdge* e ) const
 149   {
 150     myLinkedEdges.reserve(2);
 151     myLinkedEdges.push_back( e );
 152     if ( myLinkedEdges.size() < 2 ) return;
 153
 154     if ( myLinkedEdges.size() == 2 )
 155     {
 156       myLinkedEdges[0]->AddLinked( myLinkedEdges[1] );
 157       myLinkedEdges[1]->AddLinked( myLinkedEdges[0] );
 158     }
 159     else
 160     {
 161       for ( size_t i = 0; i < myLinkedEdges.size(); ++i )
 162         for ( size_t j = 0; j < myLinkedEdges.size(); ++j )
 163           if ( i != j )
 164             myLinkedEdges[i]->RemoveLinked( myLinkedEdges[j] );
 165     }
 166   }
 167   void BNode::AddClose ( const BEdge* e ) const
 168   {
 169     if ( ! e->Contains( this ))
 170       myCloseEdges.push_back( const_cast< BEdge* >( e ));
 171   }
 172   BEdge* BNode::FindCloseEdgeOfBorder( int borderID ) const
 173   {
 174     for ( size_t i = 0; i < myCloseEdges.size(); ++i )
 175       if ( borderID == myCloseEdges[ i ]->myBorderID )
 176         return myCloseEdges[ i ];
 177     return 0;
 178   }
 179
 180   /// Accessor to SMDS_MeshElement* inherited by BEdge
 181   struct ElemAcess
 182   {
 183     static const SMDS_MeshElement* value( std::vector< BEdge >::const_iterator it)
 184     {
 185       return & (*it);
 186     }
 187   };
 188   /// Iterator over a vector of BEdge's
 189   static SMDS_ElemIteratorPtr getElemIterator( const std::vector< BEdge > & bedges )
 190   {
 191     typedef SMDS_SetIterator
 192       < const SMDS_MeshElement*, std::vector< BEdge >::const_iterator, ElemAcess > BEIter;
 193     return SMDS_ElemIteratorPtr( new BEIter( bedges.begin(), bedges.end() ));
 194   }
 195
 196 } // namespace
 197
 198 // struct needed for NCollection_Map
 199 struct TLinkHasher
 200 {
 201   static int HashCode(const SMESH_TLink& link, int aLimit)
 202   {
 203     return ::HashCode( link.node1()->GetID() + link.node2()->GetID(), aLimit );
 204   }
 205   static Standard_Boolean IsEqual(const SMESH_TLink& l1, const SMESH_TLink& l2)
 206   {
 207     return ( l1.node1() == l2.node1() && l1.node2() == l2.node2() );
 208   }
 209 };
 210
 211 //================================================================================
 212 /*
 213  * Returns groups of TFreeBorder's coincident within the given tolerance.
 214  * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
 215  * to free borders being compared is used.
 216  */
 217 //================================================================================
 218
 219 void SMESH_MeshAlgos::FindCoincidentFreeBorders(SMDS_Mesh&              mesh,
 220                                                 double                  tolerance,
 221                                                 CoincidentFreeBorders & foundFreeBordes)
 222 {
 223   // find free links
 224   typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, TLinkHasher > TLink2FaceMap;
 225   TLink2FaceMap linkMap;
 226   SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
 227   while ( faceIt->more() )
 228   {
 229     const SMDS_MeshElement* face = faceIt->next();
 230     if ( !face ) continue;
 231
 232     const SMDS_MeshNode*     n0 = face->GetNode( face->NbNodes() - 1 );
 233     SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
 234     while ( nodeIt->more() )
 235     {
 236       const SMDS_MeshNode* n1 = nodeIt->next();
 237       SMESH_TLink link( n0, n1 );
 238       if ( !linkMap.Bind( link, face ))
 239         linkMap.UnBind( link );
 240       n0 = n1;
 241     }
 242   }
 243   if ( linkMap.IsEmpty() )
 244     return;
 245
 246   // form free borders
 247   std::set   < BNode > bNodes;
 248   std::vector< BEdge > bEdges( linkMap.Extent() );
 249
 250   TLink2FaceMap::Iterator linkIt( linkMap );
 251   for ( int iEdge = 0; linkIt.More(); linkIt.Next(), ++iEdge )
 252   {
 253     const SMESH_TLink & link = linkIt.Key();
 254     std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
 255     std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
 256     bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
 257     n1->AddLinked( & bEdges[ iEdge ] );
 258     n2->AddLinked( & bEdges[ iEdge ] );
 259   }
 260   linkMap.Clear();
 261
 262   // assign IDs to borders
 263   std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
 264   std::set< BNode >::iterator bn = bNodes.begin();
 265   for ( ; bn != bNodes.end(); ++bn )
 266   {
 267     for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
 268     {
 269       if ( bn->myLinkedEdges[i]->myBorderID < 0 )
 270       {
 271         BEdge* be = bn->myLinkedEdges[i];
 272         int borderID = borders.size();
 273         borders.push_back( be );
 274         for ( ; be && be->myBorderID < 0; be = be->myNext )
 275         {
 276           be->myBorderID = borderID;
 277           be->Orient();
 278         }
 279         bool isClosed = ( be == bn->myLinkedEdges[i] );
 280         be = bn->myLinkedEdges[i]->myPrev;
 281         for ( ; be && be->myBorderID < 0; be = be->myPrev )
 282         {
 283           be->myBorderID = borderID;
 284           be->Orient();
 285         }
 286         if ( !isClosed )
 287           while ( borders.back()->myPrev )
 288             borders.back() = borders.back()->myPrev;
 289
 290         borders.back()->SetID( 0 ); // set IDs to all edges of the border
 291       }
 292     }
 293   }
 294
 295   // compute tolerance of each border
 296   double maxTolerance = tolerance;
 297   std::vector< double > bordToler( borders.size(), tolerance );
 298   if ( maxTolerance < std::numeric_limits< double >::min() )
 299   {
 300     // no tolerance provided by the user; compute tolerance of each border
 301     // as one tenth of an average size of faces adjacent to a border
 302     for ( size_t i = 0; i < borders.size(); ++i )
 303     {
 304       double avgFaceSize = 0;
 305       int    nbFaces     = 0;
 306       BEdge* be = borders[ i ];
 307       do {
 308         double facePerimeter = 0;
 309         gp_Pnt p0 = SMESH_TNodeXYZ( be->myFace->GetNode( be->myFace->NbNodes() - 1 ));
 310         SMDS_NodeIteratorPtr nodeIt = be->myFace->interlacedNodesIterator();
 311         while ( nodeIt->more() )
 312         {
 313           gp_Pnt p1 = SMESH_TNodeXYZ( nodeIt->next() );
 314           facePerimeter += p0.Distance( p1 );
 315           p0 = p1;
 316         }
 317         avgFaceSize += ( facePerimeter / be->myFace->NbCornerNodes() );
 318         nbFaces++;
 319
 320         be = be->myNext;
 321       }
 322       while ( be && be != borders[i] );
 323
 324       bordToler[ i ] = 0.1 * avgFaceSize / nbFaces;
 325       maxTolerance = Max( maxTolerance, bordToler[ i ]);
 326     }
 327   }
 328
 329   // for every border node find close border edges
 330   SMESH_ElementSearcher* searcher =
 331     GetElementSearcher( mesh, getElemIterator( bEdges ), maxTolerance );
 332   SMESHUtils::Deleter< SMESH_ElementSearcher > searcherDeleter( searcher );
 333   std::vector< const SMDS_MeshElement* > candidateEdges;
 334   for ( bn = bNodes.begin(); bn != bNodes.end(); ++bn )
 335   {
 336     gp_Pnt point = SMESH_TNodeXYZ( bn->myNode );
 337     searcher->FindElementsByPoint( point, SMDSAbs_Edge, candidateEdges );
 338     if ( candidateEdges.size() <= bn->myLinkedEdges.size() )
 339       continue;
 340
 341     double nodeTol = 0;
 342     for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
 343       nodeTol = Max( nodeTol, bordToler[ bn->myLinkedEdges[ i ]->myBorderID ]);
 344
 345     for ( size_t i = 0; i < candidateEdges.size(); ++i )
 346     {
 347       const BEdge* be = static_cast< const BEdge* >( candidateEdges[ i ]);
 348       double      tol = Max( nodeTol, bordToler[ be->myBorderID ]);
 349       if ( maxTolerance - tol < 1e-12 ||
 350            !SMESH_MeshAlgos::IsOut( be, point, tol ))
 351         bn->AddClose( be );
 352     }
 353   }
 354
 355   // for every border edge find close borders
 356
 357   std::vector< BEdge* > closeEdges;
 358   for ( size_t i = 0; i < bEdges.size(); ++i )
 359   {
 360     BEdge& be = bEdges[i];
 361     if ( be.myBNode1->myCloseEdges.empty() ||
 362          be.myBNode2->myCloseEdges.empty() )
 363       continue;
 364
 365     closeEdges.clear();
 366     for ( size_t iE1 = 0; iE1 < be.myBNode1->myCloseEdges.size(); ++iE1 )
 367     {
 368       // find edges of the same border close to both nodes of the edge
 369       BEdge* closeE1 = be.myBNode1->myCloseEdges[ iE1 ];
 370       BEdge* closeE2 = be.myBNode2->FindCloseEdgeOfBorder( closeE1->myBorderID );
 371       if ( !closeE2 )
 372         continue;
 373       // check that edges connecting closeE1 and closeE2 (if any) are also close to 'be'
 374       if ( closeE1 != closeE2 )
 375       {
 376         bool coincide;
 377         for ( int j = 0; j < 2; ++j ) // move closeE1 -> closeE2 or inversely
 378         {
 379           BEdge* ce = closeE1;
 380           do {
 381             coincide = ( ce->myBNode2->FindCloseEdgeOfBorder( be.myBorderID ));
 382             ce       = ce->myNext;
 383           } while ( coincide && ce && ce != closeE2 );
 384
 385           if ( coincide && ce == closeE2 )
 386             break;
 387           if ( j == 0 )
 388             std::swap( closeE1, closeE2 );
 389           coincide = false;
 390         }
 391         if ( !coincide )
 392           continue;
 393         closeEdges.push_back( closeE1 );
 394         closeEdges.push_back( closeE2 );
 395       }
 396       else
 397       {
 398         closeEdges.push_back( closeE1 );
 399       }
 400       be.myCloseBorders.insert( closeE1->myBorderID );
 401     }
 402     if ( !closeEdges.empty() )
 403     {
 404       be.myCloseBorders.insert( be.myBorderID );
 405       // for ( size_t iB = 0; iB < closeEdges.size(); ++iB )
 406       //   closeEdges[ iB ]->myCloseBorders.insert( be.myCloseBorders.begin(),
 407       //                                            be.myCloseBorders.end() );
 408     }
 409   }
 410
 411   // Fill in CoincidentFreeBorders
 412
 413   // save nodes of free borders
 414   foundFreeBordes._borders.resize( borders.size() );
 415   for ( size_t i = 0; i < borders.size(); ++i )
 416   {
 417     BEdge* be = borders[i];
 418     foundFreeBordes._borders[i].push_back( be->myBNode1->myNode );
 419     do {
 420       foundFreeBordes._borders[i].push_back( be->myBNode2->myNode );
 421       be = be->myNext;
 422     }
 423     while ( be && be != borders[i] );
 424   }
 425
 426   // form groups of coincident parts of free borders
 427
 428   TFreeBorderPart  part;
 429   TCoincidentGroup group;
 430   for ( size_t i = 0; i < borders.size(); ++i )
 431   {
 432     BEdge* be = borders[i];
 433
 434     // look for an edge close to other borders
 435     do {
 436       if ( !be->myInGroup && !be->myCloseBorders.empty() )
 437         break;
 438       be = be->myNext;
 439     } while ( be && be != borders[i] );
 440
 441     if ( !be || be->myInGroup || be->myCloseBorders.empty() )
 442       continue; // all edges of a border treated or are non-coincident
 443
 444     group.clear();
 445
 446     // look for the 1st and last edge of a coincident group
 447     BEdge* beRange[2];
 448     be->FindRangeOfSameCloseBorders( beRange );
 449     BEdge* be1st = beRange[0];
 450
 451     // fill in a group
 452     part._border   = i;
 453     part._node1    = beRange[0]->myID;
 454     part._node2    = beRange[0]->myID + 1;
 455     part._nodeLast = beRange[1]->myID + 1;
 456     group.push_back( part );
 457
 458     be = beRange[0];
 459     be->myInGroup = true;
 460     while ( be != beRange[1] )
 461     {
 462       be->myInGroup = true;
 463       be = be->myNext;
 464     }
 465     beRange[1]->myInGroup = true;
 466
 467     // add parts of other borders
 468     std::set<int>::iterator closeBord = be1st->myCloseBorders.begin();
 469     for ( ; closeBord != be1st->myCloseBorders.end(); ++closeBord )
 470     {
 471       be = be1st->myBNode2->FindCloseEdgeOfBorder( *closeBord );
 472       if ( !be ) continue;
 473
 474       be->FindRangeOfSameCloseBorders( beRange );
 475
 476       // find out mutual orientation of borders
 477       bool reverse = ( beRange[0]->myBNode1->FindCloseEdgeOfBorder( i ) != be1st &&
 478                        beRange[0]->myBNode2->FindCloseEdgeOfBorder( i ) != be1st );
 479
 480       // fill in a group
 481       part._border   = beRange[0]->myBorderID;
 482       if ( reverse ) {
 483         part._node1    = beRange[1]->myID + 1;
 484         part._node2    = beRange[1]->myID;
 485         part._nodeLast = beRange[0]->myID;
 486       }
 487       else  {
 488         part._node1    = beRange[0]->myID;
 489         part._node2    = beRange[0]->myID + 1;
 490         part._nodeLast = beRange[1]->myID + 1;
 491       }
 492       group.push_back( part );
 493
 494       be = beRange[0];
 495       be->myInGroup = true;
 496       while ( be != beRange[1] )
 497       {
 498         be->myInGroup = true;
 499         be = be->myNext;
 500       }
 501       beRange[1]->myInGroup = true;
 502     }
 503
 504     foundFreeBordes._coincidentGroups.push_back( group );
 505
 506   } // loop on free borders
 507 }