1 // Copyright (C) 2007-2015 CEA/DEN, EDF R&D, OPEN CASCADE
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.
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.
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
17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
19 // File : SMESH_FreeBorders.cxx
20 // Created : Tue Sep 8 17:08:39 2015
21 // Author : Edward AGAPOV (eap)
23 //================================================================================
24 // Implementation of SMESH_MeshAlgos::FindCoincidentFreeBorders()
25 //================================================================================
27 #include "SMESH_MeshAlgos.hxx"
29 #include "SMDS_LinearEdge.hxx"
30 #include "SMDS_Mesh.hxx"
31 #include "SMDS_SetIterator.hxx"
38 #include <NCollection_DataMap.hxx>
41 using namespace SMESH_MeshAlgos;
48 * \brief Node on a free border
50 struct BNode : public SMESH_TNodeXYZ
52 mutable std::vector< BEdge* > myLinkedEdges;
53 mutable std::vector< std::pair < BEdge*, double > > myCloseEdges; // edge & U
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 HasCloseEdgeWithNode( const BNode* n ) const;
63 bool IsCloseEdge( const BEdge*, double * u = 0 ) const;
64 bool operator<(const BNode& other) const { return Node()->GetID() < other.Node()->GetID(); }
67 * \brief Edge of a free border
69 struct BEdge : public SMDS_LinearEdge
71 const BNode* myBNode1;
72 const BNode* myBNode2;
74 int myID; // within a border
77 const SMDS_MeshElement* myFace;
78 std::set< int > myCloseBorders;
81 BEdge():SMDS_LinearEdge( 0, 0 ), myBorderID(-1), myID(-1), myPrev(0), myNext(0), myInGroup(-1) {}
83 void Set( const BNode * node1,
85 const SMDS_MeshElement* face,
90 myNodes[0] = node1->Node();
91 myNodes[1] = node2->Node();
93 setId( ID ); // mesh element ID
95 bool IsInGroup() const
97 return myInGroup >= 0;
99 bool Contains( const BNode* n ) const
101 return ( n == myBNode1 || n == myBNode2 );
103 void AddLinked( BEdge* e )
105 if ( e->Contains( myBNode1 )) myPrev = e;
108 void RemoveLinked( BEdge* e )
110 if ( myPrev == e ) myPrev = 0;
111 if ( myNext == e ) myNext = 0;
115 std::swap( myBNode1, myBNode2 );
116 myNodes[0] = myBNode1->Node();
117 myNodes[1] = myBNode2->Node();
121 if (( myPrev && !myPrev->Contains( myBNode1 )) ||
122 ( myNext && !myNext->Contains( myBNode2 )))
123 std::swap( myPrev, myNext );
124 if ( myPrev && myPrev->myBNode2 != myBNode1 ) myPrev->Reverse();
125 if ( myNext && myNext->myBNode1 != myBNode2 ) myNext->Reverse();
133 myNext->SetID( id + 1 );
136 bool IsOut( const gp_XYZ& point, const double tol, double& u ) const
138 gp_XYZ me = *myBNode2 - *myBNode1;
139 gp_XYZ n1p = point - *myBNode1;
140 u = ( me * n1p ) / me.SquareModulus(); // param [0,1] on this
141 if ( u < 0. ) return ( n1p.SquareModulus() > tol * tol );
142 if ( u > 1. ) return ( ( point - *myBNode2 ).SquareModulus() > tol * tol );
144 gp_XYZ proj = ( 1. - u ) * *myBNode1 + u * *myBNode2; // projection of the point on this
145 double dist2 = ( point - proj ).SquareModulus();
146 return ( dist2 > tol * tol );
148 bool IsOverlappingProjection( const BEdge* toE, const double u, bool is1st ) const
150 // is1st shows which end of toE is projected on this at u
152 const double eps = 0.1;
153 if ( myBNode1->IsCloseEdge( toE, &u2 ) ||
154 myBNode2->IsCloseEdge( toE, &u2 ))
155 return (( 0 < u2 && u2 < 1 ) && // u2 is proj param of myBNode's on toE
156 ( Abs( u2 - int( !is1st )) > eps ));
158 const BNode* n = is1st ? toE->myBNode2 : toE->myBNode1;
159 if ( this == n->GetCloseEdgeOfBorder( this->myBorderID, &u2 ))
160 return Abs( u - u2 ) > eps;
163 bool GetRangeOfSameCloseBorders(BEdge* eRange[2], const std::set< int >& bordIDs)
165 if ( this->myCloseBorders != bordIDs )
168 if ( bordIDs.size() == 1 && bordIDs.count( myBorderID )) // border close to self
172 while ( eRange[0]->myBNode1->GetCloseEdgeOfBorder( myBorderID, &u ))
174 if ( eRange[0]->myPrev == this || u < 0 || u > 1 )
176 eRange[0] = eRange[0]->myPrev;
179 while ( eRange[1]->myBNode2->GetCloseEdgeOfBorder( myBorderID, &u ))
181 if ( eRange[1]->myNext == this || u < 0 || u > 1 )
183 eRange[1] = eRange[1]->myNext;
189 while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == bordIDs )
191 if ( eRange[0]->myPrev == this )
193 eRange[0] = eRange[0]->myPrev;
197 if ( eRange[0]->myPrev != this ) // not closed border
198 while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == bordIDs )
200 if ( eRange[1]->myNext == this )
202 eRange[1] = eRange[1]->myNext;
206 if ( eRange[0] == eRange[1] )
208 std::set<int>::iterator closeBord = eRange[0]->myCloseBorders.begin();
209 for ( ; closeBord != eRange[0]->myCloseBorders.end(); ++closeBord )
211 if ( BEdge* be = eRange[0]->myBNode1->GetCloseEdgeOfBorder( *closeBord ))
212 if ( be->myCloseBorders == eRange[0]->myCloseBorders )
214 if ( BEdge* be = eRange[0]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
215 if ( be->myCloseBorders == eRange[0]->myCloseBorders )
224 void extendPart( BEdge* & e1, BEdge* & e2, const std::set< int >& bordIDs, int groupID )
226 if (( e1->myPrev == e2 ) ||
227 ( e1 == e2 && e1->myPrev && e1->myPrev->myInGroup == groupID ))
228 return; // full free border already
232 std::set<int>::const_iterator bord;
235 for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
236 if ((( be = e1->myBNode1->GetCloseEdgeOfBorder( *bord, &u ))) &&
237 ( be->myInGroup == groupID ) &&
238 ( 0 < u && u < 1 ) &&
239 ( be->IsOverlappingProjection( e1->myPrev, u, false )))
244 if ( bord == bordIDs.end() && // not extended
245 e1->myBNode1->HasCloseEdgeWithNode( e1->myPrev->myBNode1 ))
249 e1->myInGroup = groupID;
253 for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
254 if ((( be = e2->myBNode2->GetCloseEdgeOfBorder( *bord, &u ))) &&
255 ( be->myInGroup == groupID ) &&
256 ( 0 < u && u < 1 ) &&
257 ( be->IsOverlappingProjection( e2->myNext, u, true )))
262 if ( bord == bordIDs.end() && // not extended
263 e2->myBNode2->HasCloseEdgeWithNode( e2->myNext->myBNode2 ))
267 e2->myInGroup = groupID;
271 void BNode::AddLinked( BEdge* e ) const
273 myLinkedEdges.reserve(2);
274 myLinkedEdges.push_back( e );
275 if ( myLinkedEdges.size() < 2 ) return;
277 if ( myLinkedEdges.size() == 2 )
279 myLinkedEdges[0]->AddLinked( myLinkedEdges[1] );
280 myLinkedEdges[1]->AddLinked( myLinkedEdges[0] );
284 for ( size_t i = 0; i < myLinkedEdges.size(); ++i )
285 for ( size_t j = 0; j < myLinkedEdges.size(); ++j )
287 myLinkedEdges[i]->RemoveLinked( myLinkedEdges[j] );
290 void BNode::AddClose ( const BEdge* e, double u ) const
292 if ( ! e->Contains( this ))
293 myCloseEdges.push_back( make_pair( const_cast< BEdge* >( e ), u ));
295 BEdge* BNode::GetCloseEdgeOfBorder( int borderID, double * uPtr ) const
299 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
300 if ( borderID == GetCloseEdge( i )->myBorderID )
302 if ( e && Abs( u - 0.5 ) < Abs( GetCloseU( i ) - 0.5 ))
305 e = GetCloseEdge ( i );
307 if ( uPtr ) *uPtr = u;
310 bool BNode::HasCloseEdgeWithNode( const BNode* n ) const
312 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
313 if ( GetCloseEdge( i )->Contains( n ) &&
314 0 < GetCloseU( i ) && GetCloseU( i ) < 1 )
318 bool BNode::IsCloseEdge( const BEdge* e, double * uPtr ) const
320 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
321 if ( e == GetCloseEdge( i ) )
323 if ( uPtr ) *uPtr = GetCloseU( i );
329 /// Accessor to SMDS_MeshElement* inherited by BEdge
332 static const SMDS_MeshElement* value( std::vector< BEdge >::const_iterator it)
337 /// Iterator over a vector of BEdge's
338 static SMDS_ElemIteratorPtr getElemIterator( const std::vector< BEdge > & bedges )
340 typedef SMDS_SetIterator
341 < const SMDS_MeshElement*, std::vector< BEdge >::const_iterator, ElemAcess > BEIter;
342 return SMDS_ElemIteratorPtr( new BEIter( bedges.begin(), bedges.end() ));
347 // struct needed for NCollection_Map
350 static int HashCode(const SMESH_TLink& link, int aLimit)
352 return ::HashCode( link.node1()->GetID() + link.node2()->GetID(), aLimit );
354 static Standard_Boolean IsEqual(const SMESH_TLink& l1, const SMESH_TLink& l2)
356 return ( l1.node1() == l2.node1() && l1.node2() == l2.node2() );
360 //================================================================================
362 * Returns groups of TFreeBorder's coincident within the given tolerance.
363 * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
364 * to free borders being compared is used.
366 //================================================================================
368 void SMESH_MeshAlgos::FindCoincidentFreeBorders(SMDS_Mesh& mesh,
370 CoincidentFreeBorders & foundFreeBordes)
373 typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, TLinkHasher > TLink2FaceMap;
374 TLink2FaceMap linkMap;
375 int nbSharedLinks = 0;
376 SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
377 while ( faceIt->more() )
379 const SMDS_MeshElement* face = faceIt->next();
380 if ( !face ) continue;
382 const SMDS_MeshNode* n0 = face->GetNode( face->NbNodes() - 1 );
383 SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
384 while ( nodeIt->more() )
386 const SMDS_MeshNode* n1 = nodeIt->next();
387 SMESH_TLink link( n0, n1 );
388 if ( const SMDS_MeshElement** faceInMap = linkMap.ChangeSeek( link ))
390 nbSharedLinks += bool( *faceInMap );
395 linkMap.Bind( link, face );
400 if ( linkMap.Extent() == nbSharedLinks )
404 std::set < BNode > bNodes;
405 std::vector< BEdge > bEdges( linkMap.Extent() - nbSharedLinks );
407 TLink2FaceMap::Iterator linkIt( linkMap );
408 for ( int iEdge = 0; linkIt.More(); linkIt.Next() )
410 if ( !linkIt.Value() ) continue;
411 const SMESH_TLink & link = linkIt.Key();
412 std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
413 std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
414 bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
415 n1->AddLinked( & bEdges[ iEdge ] );
416 n2->AddLinked( & bEdges[ iEdge ] );
421 // assign IDs to borders
422 std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
423 std::set< BNode >::iterator bn = bNodes.begin();
424 for ( ; bn != bNodes.end(); ++bn )
426 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
428 if ( bn->myLinkedEdges[i]->myBorderID < 0 )
430 BEdge* be = bn->myLinkedEdges[i];
431 int borderID = borders.size();
432 borders.push_back( be );
433 for ( ; be && be->myBorderID < 0; be = be->myNext )
435 be->myBorderID = borderID;
438 bool isClosed = ( be == bn->myLinkedEdges[i] );
439 be = bn->myLinkedEdges[i]->myPrev;
440 for ( ; be && be->myBorderID < 0; be = be->myPrev )
442 be->myBorderID = borderID;
446 while ( borders.back()->myPrev )
447 borders.back() = borders.back()->myPrev;
449 borders.back()->SetID( 0 ); // set IDs to all edges of the border
454 // compute tolerance of each border
455 double maxTolerance = tolerance;
456 std::vector< double > bordToler( borders.size(), tolerance );
457 if ( maxTolerance < std::numeric_limits< double >::min() )
459 // no tolerance provided by the user; compute tolerance of each border
460 // as one tenth of an average size of faces adjacent to a border
461 for ( size_t i = 0; i < borders.size(); ++i )
463 double avgFaceSize = 0;
465 BEdge* be = borders[ i ];
467 double facePerimeter = 0;
468 gp_Pnt p0 = SMESH_TNodeXYZ( be->myFace->GetNode( be->myFace->NbNodes() - 1 ));
469 SMDS_NodeIteratorPtr nodeIt = be->myFace->interlacedNodesIterator();
470 while ( nodeIt->more() )
472 gp_Pnt p1 = SMESH_TNodeXYZ( nodeIt->next() );
473 facePerimeter += p0.Distance( p1 );
476 avgFaceSize += ( facePerimeter / be->myFace->NbCornerNodes() );
481 while ( be && be != borders[i] );
483 bordToler[ i ] = 0.1 * avgFaceSize / nbFaces;
484 maxTolerance = Max( maxTolerance, bordToler[ i ]);
488 // for every border node find close border edges
489 SMESH_ElementSearcher* searcher =
490 GetElementSearcher( mesh, getElemIterator( bEdges ), maxTolerance );
491 SMESHUtils::Deleter< SMESH_ElementSearcher > searcherDeleter( searcher );
492 std::vector< const SMDS_MeshElement* > candidateEdges;
493 for ( bn = bNodes.begin(); bn != bNodes.end(); ++bn )
495 searcher->FindElementsByPoint( *bn, SMDSAbs_Edge, candidateEdges );
496 if ( candidateEdges.size() <= bn->myLinkedEdges.size() )
499 double nodeTol = 0, u;
500 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
501 nodeTol = Max( nodeTol, bordToler[ bn->myLinkedEdges[ i ]->myBorderID ]);
503 for ( size_t i = 0; i < candidateEdges.size(); ++i )
505 const BEdge* be = static_cast< const BEdge* >( candidateEdges[ i ]);
506 double tol = Max( nodeTol, bordToler[ be->myBorderID ]);
507 if ( !be->IsOut( *bn, tol, u ))
508 bn->AddClose( be, u );
512 // for every border edge find close borders
514 std::vector< BEdge* > closeEdges;
515 for ( size_t i = 0; i < bEdges.size(); ++i )
517 BEdge& be = bEdges[i];
518 if ( be.myBNode1->myCloseEdges.empty() ||
519 be.myBNode2->myCloseEdges.empty() )
523 for ( size_t iE1 = 0; iE1 < be.myBNode1->myCloseEdges.size(); ++iE1 )
525 // find edges of the same border close to both nodes of the edge
526 BEdge* closeE1 = be.myBNode1->GetCloseEdge( iE1 );
527 BEdge* closeE2 = be.myBNode2->GetCloseEdgeOfBorder( closeE1->myBorderID );
530 // check that edges connecting closeE1 and closeE2 (if any) are also close to 'be'
531 if ( closeE1 != closeE2 )
534 for ( int j = 0; j < 2; ++j ) // move closeE1 -> closeE2 or inversely
538 coincide = ( ce->myBNode2->GetCloseEdgeOfBorder( be.myBorderID ));
540 } while ( coincide && ce && ce != closeE2 );
542 if ( coincide && ce == closeE2 )
545 std::swap( closeE1, closeE2 );
550 closeEdges.push_back( closeE1 );
551 closeEdges.push_back( closeE2 );
555 closeEdges.push_back( closeE1 );
557 be.myCloseBorders.insert( closeE1->myBorderID );
559 if ( !closeEdges.empty() )
561 be.myCloseBorders.insert( be.myBorderID );
562 // for ( size_t iB = 0; iB < closeEdges.size(); ++iB )
563 // closeEdges[ iB ]->myCloseBorders.insert( be.myCloseBorders.begin(),
564 // be.myCloseBorders.end() );
568 // Fill in CoincidentFreeBorders
570 // save nodes of free borders
571 foundFreeBordes._borders.resize( borders.size() );
572 for ( size_t i = 0; i < borders.size(); ++i )
574 BEdge* be = borders[i];
575 foundFreeBordes._borders[i].push_back( be->myBNode1->Node() );
577 foundFreeBordes._borders[i].push_back( be->myBNode2->Node() );
580 while ( be && be != borders[i] );
583 // form groups of coincident parts of free borders
585 TFreeBorderPart part;
586 TCoincidentGroup group;
587 vector< BEdge* > ranges; // couples of edges delimiting parts
588 BEdge* be = 0; // a current edge
589 int skipGroup = bEdges.size(); // a group ID used to avoid repeating treatment of edges
591 for ( int i = 0, nbBords = borders.size(); i < nbBords; i += bool(!be) )
596 // look for an edge close to other borders
598 if ( !be->IsInGroup() && !be->myCloseBorders.empty() )
601 } while ( be && be != borders[i] );
603 if ( !be || be->IsInGroup() || be->myCloseBorders.empty() )
606 continue; // all edges of a border are treated or non-coincident
611 // look for the 1st and last edge of a coincident group
613 if ( !be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders ))
615 be->myInGroup = skipGroup;
620 ranges.push_back( beRange[0] );
621 ranges.push_back( beRange[1] );
623 int groupID = foundFreeBordes._coincidentGroups.size();
625 be->myInGroup = groupID;
626 while ( be != beRange[1] )
628 be->myInGroup = groupID;
631 beRange[1]->myInGroup = groupID;
633 // get starting edge of each close border
636 if ( be->myCloseBorders.empty() )
637 be = beRange[0]->myNext;
638 std::set<int>::iterator closeBord = be->myCloseBorders.begin();
639 for ( ; closeBord != be->myCloseBorders.end(); ++closeBord )
640 if ( BEdge* e = be->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
641 closeEdges.push_back( e );
643 for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
644 if ( be->myCloseBorders != closeEdges[iE]->myCloseBorders )
646 closeBord = closeEdges[iE]->myCloseBorders.begin();
647 for ( ; closeBord != closeEdges[iE]->myCloseBorders.end(); ++closeBord )
648 if ( !be->myCloseBorders.count( *closeBord ))
649 if ( BEdge* e = closeEdges[iE]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
650 if ( std::find( closeEdges.begin(), closeEdges.end(), e ) == closeEdges.end() )
651 closeEdges.push_back( e );
654 // add parts of other borders
656 BEdge* be1st = beRange[0];
657 for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
659 be = closeEdges[ iE ];
662 bool ok = be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders );
663 // if ( !ok && be->myPrev )
664 // ok = be->myPrev->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
665 // if ( !ok && be->myNext )
666 // ok = be->myNext->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
672 ranges.push_back( beRange[0] );
673 ranges.push_back( beRange[1] );
675 be->myInGroup = groupID;
676 while ( be != beRange[1] )
678 be->myInGroup = groupID;
681 beRange[1]->myInGroup = groupID;
684 if ( ranges.size() > 2 )
686 for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
687 extendPart( ranges[ iR-1 ], ranges[ iR ], be1st->myCloseBorders, groupID );
690 beRange[0] = ranges[0];
691 beRange[1] = ranges[1];
694 part._node1 = beRange[0]->myID;
695 part._node2 = beRange[0]->myID + 1;
696 part._nodeLast = beRange[1]->myID + 1;
697 group.push_back( part );
700 for ( size_t iR = 3; iR < ranges.size(); iR += 2 )
702 beRange[0] = ranges[iR-1];
703 beRange[1] = ranges[iR-0];
705 // find out mutual orientation of borders
707 be1st ->IsOut( *beRange[ 0 ]->myBNode1, maxTolerance, u1 );
708 beRange[ 0 ]->IsOut( *be1st->myBNode1, maxTolerance, u2 );
709 bool reverse = (( u1 < 0 || u1 > 1 ) && ( u2 < 0 || u2 > 1 ));
712 part._border = beRange[0]->myBorderID;
714 part._node1 = beRange[1]->myID + 1;
715 part._node2 = beRange[1]->myID;
716 part._nodeLast = beRange[0]->myID;
719 part._node1 = beRange[0]->myID;
720 part._node2 = beRange[0]->myID + 1;
721 part._nodeLast = beRange[1]->myID + 1;
723 // if ( group[0]._node2 != part._node2 )
724 group.push_back( part );
726 //if ( group.size() > 1 )
727 foundFreeBordes._coincidentGroups.push_back( group );
731 beRange[0] = ranges[0];
732 beRange[1] = ranges[1];
735 be->myInGroup = skipGroup;
736 while ( be != beRange[1] )
738 be->myInGroup = skipGroup;
741 beRange[1]->myInGroup = skipGroup;
746 } // loop on free borders
750 } // SMESH_MeshAlgos::FindCoincidentFreeBorders()