1 // Copyright (C) 2007-2021 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>
39 #include <Precision.hxx>
42 using namespace SMESH_MeshAlgos;
49 * \brief Node on a free border
51 struct BNode : public SMESH_TNodeXYZ
53 mutable std::vector< BEdge* > myLinkedEdges;
54 mutable std::vector< std::pair < BEdge*, double > > myCloseEdges; // edge & U
56 BNode(const SMDS_MeshNode * node): SMESH_TNodeXYZ( node ) {}
57 const SMDS_MeshNode * Node() const { return _node; }
58 void AddLinked( BEdge* e ) const;
59 void AddClose ( const BEdge* e, double u ) const;
60 BEdge* GetCloseEdge( size_t i ) const { return myCloseEdges[i].first; }
61 double GetCloseU( size_t i ) const { return myCloseEdges[i].second; }
62 BEdge* GetCloseEdgeOfBorder( int borderID, double * u = 0 ) const;
63 bool HasCloseEdgeWithNode( const BNode* n ) const;
64 bool IsCloseEdge( const BEdge*, double * u = 0 ) const;
65 bool operator<(const BNode& other) const { return Node()->GetID() < other.Node()->GetID(); }
66 double SquareDistance(const BNode& e2) const { return ( e2 - *this ).SquareModulus(); }
69 * \brief Edge of a free border
71 struct BEdge : public SMDS_LinearEdge
73 const BNode* myBNode1;
74 const BNode* myBNode2;
76 int myID; // within a border
79 const SMDS_MeshElement* myFace;
80 std::set< int > myCloseBorders;
83 BEdge():SMDS_LinearEdge( 0, 0 ), myBorderID(-1), myID(-1), myPrev(0), myNext(0), myInGroup(-1) {}
85 void Set( const BNode * node1,
87 const SMDS_MeshElement* face,
92 myNodes[0] = node1->Node();
93 myNodes[1] = node2->Node();
95 setID( ID ); // mesh element ID
97 bool IsInGroup() const
99 return myInGroup >= 0;
101 bool Contains( const BNode* n ) const
103 return ( n == myBNode1 || n == myBNode2 );
105 void AddLinked( BEdge* e )
107 if ( e->Contains( myBNode1 )) myPrev = e;
110 void RemoveLinked( BEdge* e )
112 if ( myPrev == e ) myPrev = 0;
113 if ( myNext == e ) myNext = 0;
117 std::swap( myBNode1, myBNode2 );
118 myNodes[0] = myBNode1->Node();
119 myNodes[1] = myBNode2->Node();
123 if (( myPrev && !myPrev->Contains( myBNode1 )) ||
124 ( myNext && !myNext->Contains( myBNode2 )))
125 std::swap( myPrev, myNext );
126 if ( myPrev && myPrev->myBNode2 != myBNode1 ) myPrev->Reverse();
127 if ( myNext && myNext->myBNode1 != myBNode2 ) myNext->Reverse();
135 for ( BEdge* be = myNext; be && be->myID < 0; be = be->myNext )
141 //================================================================================
143 * \brief Checks if a point is closer to this BEdge than tol
145 //================================================================================
147 bool IsOut( const gp_XYZ& point, const double tol, double& u ) const
149 gp_XYZ me = *myBNode2 - *myBNode1;
150 gp_XYZ n1p = point - *myBNode1;
151 u = ( me * n1p ) / me.SquareModulus(); // param [0,1] on this
152 if ( u < 0. ) return ( n1p.SquareModulus() > tol * tol );
153 if ( u > 1. ) return ( ( point - *myBNode2 ).SquareModulus() > tol * tol );
155 gp_XYZ proj = ( 1. - u ) * *myBNode1 + u * *myBNode2; // projection of the point on this
156 double dist2 = ( point - proj ).SquareModulus();
157 return ( dist2 > tol * tol );
159 //================================================================================
161 * \brief Checks if two BEdges can be considered as overlapping
163 //================================================================================
165 bool IsOverlappingProjection( const BEdge* toE, const double u, bool is1st ) const
167 // is1st shows which end of toE is projected on this at u
169 const double eps = 0.1;
170 if ( myBNode1->IsCloseEdge( toE, &u2 ) ||
171 myBNode2->IsCloseEdge( toE, &u2 ))
172 return (( 0 < u2 && u2 < 1 ) && // u2 is proj param of myBNode's on toE
173 ( Abs( u2 - int( !is1st )) > eps ));
175 const BNode* n = is1st ? toE->myBNode2 : toE->myBNode1;
176 if ( this == n->GetCloseEdgeOfBorder( this->myBorderID, &u2 ))
177 return Abs( u - u2 ) > eps;
180 //================================================================================
182 * \brief Finds all neighbor BEdge's having the same close borders
184 //================================================================================
186 bool GetRangeOfSameCloseBorders(BEdge* eRange[2], const std::set< int >& bordIDs)
188 if ( this->myCloseBorders != bordIDs )
191 if ( bordIDs.size() == 1 && bordIDs.count( myBorderID )) // border close to self
195 while ( eRange[0]->myBNode1->GetCloseEdgeOfBorder( myBorderID, &u ))
197 if ( eRange[0]->myPrev == this || u < 0 || u > 1 )
199 eRange[0] = eRange[0]->myPrev;
202 while ( eRange[1]->myBNode2->GetCloseEdgeOfBorder( myBorderID, &u ))
204 if ( eRange[1]->myNext == this || u < 0 || u > 1 )
206 eRange[1] = eRange[1]->myNext;
212 while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == bordIDs )
214 if ( eRange[0]->myPrev == this )
216 eRange[0] = eRange[0]->myPrev;
220 if ( eRange[0]->myPrev != this ) // not closed border
221 while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == bordIDs )
223 if ( eRange[1]->myNext == this )
225 eRange[1] = eRange[1]->myNext;
229 if ( eRange[0] == eRange[1] )
231 std::set<int>::iterator closeBord = eRange[0]->myCloseBorders.begin();
232 for ( ; closeBord != eRange[0]->myCloseBorders.end(); ++closeBord )
234 if ( BEdge* be = eRange[0]->myBNode1->GetCloseEdgeOfBorder( *closeBord ))
235 if ( be->myCloseBorders == eRange[0]->myCloseBorders )
237 if ( BEdge* be = eRange[0]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
238 if ( be->myCloseBorders == eRange[0]->myCloseBorders )
247 //================================================================================
249 * \brief Checks if all border parts include the whole closed border, and if so
250 * returns \c true and choose starting BEdge's with most coincident nodes
252 //================================================================================
254 bool chooseStartOfClosedBorders( std::vector< BEdge* >& ranges ) // PAL23078#c21002
256 bool allClosed = true;
257 for ( size_t iR = 1; iR < ranges.size() && allClosed; iR += 2 )
258 allClosed = ( ranges[ iR-1 ]->myPrev == ranges[ iR ] );
262 double u, minDiff = Precision::Infinite();
263 std::vector< BEdge* > start( ranges.size() / 2 );
264 BEdge* range0 = start[0] = ranges[0];
269 for ( size_t iR = 3; iR < ranges.size(); iR += 2 )
271 int borderID = ranges[iR]->myBorderID;
272 if ( BEdge* e = start[0]->myBNode1->GetCloseEdgeOfBorder( borderID, & u ))
275 double diffU = Min( Abs( u ), Abs( 1.-u ));
276 double diff = e->myBNode1->SquareDistance( *e->myBNode2 ) * diffU * diffU;
277 maxDiffU = Max( diffU, maxDiffU );
278 maxDiff = Max( diff, maxDiff );
281 if ( maxDiff < minDiff )
284 for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
286 ranges[ iR-1 ] = start[ iR/2 ];
287 ranges[ iR ] = ranges[ iR-1]->myPrev;
290 if ( maxDiffU < 1e-6 )
292 start[0] = start[0]->myNext;
294 while ( start[0] != range0 );
299 //================================================================================
301 * \brief Tries to include neighbor BEdge's into a border part
303 //================================================================================
305 void extendPart( BEdge* & e1, BEdge* & e2, const std::set< int >& bordIDs, int groupID )
307 if (( e1->myPrev == e2 ) ||
308 ( e1 == e2 && e1->myPrev && e1->myPrev->myInGroup == groupID ))
309 return; // full free border already
313 std::set<int>::const_iterator bord;
316 for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
317 if ((( be = e1->myBNode1->GetCloseEdgeOfBorder( *bord, &u ))) &&
318 ( be->myInGroup == groupID ) &&
319 ( 0 < u && u < 1 ) &&
320 ( be->IsOverlappingProjection( e1->myPrev, u, false )))
325 if ( bord == bordIDs.end() && // not extended
326 e1->myBNode1->HasCloseEdgeWithNode( e1->myPrev->myBNode1 ))
330 e1->myInGroup = groupID;
334 for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
335 if ((( be = e2->myBNode2->GetCloseEdgeOfBorder( *bord, &u ))) &&
336 ( be->myInGroup == groupID ) &&
337 ( 0 < u && u < 1 ) &&
338 ( be->IsOverlappingProjection( e2->myNext, u, true )))
343 if ( bord == bordIDs.end() && // not extended
344 e2->myBNode2->HasCloseEdgeWithNode( e2->myNext->myBNode2 ))
348 e2->myInGroup = groupID;
352 //================================================================================
354 * \brief Connect BEdge's incident at this node
356 //================================================================================
358 void BNode::AddLinked( BEdge* e ) const
360 myLinkedEdges.reserve(2);
361 myLinkedEdges.push_back( e );
362 if ( myLinkedEdges.size() < 2 ) return;
364 if ( myLinkedEdges.size() == 2 )
366 myLinkedEdges[0]->AddLinked( myLinkedEdges[1] );
367 myLinkedEdges[1]->AddLinked( myLinkedEdges[0] );
371 for ( size_t i = 0; i < myLinkedEdges.size(); ++i )
372 for ( size_t j = 0; j < myLinkedEdges.size(); ++j )
374 myLinkedEdges[i]->RemoveLinked( myLinkedEdges[j] );
377 void BNode::AddClose ( const BEdge* e, double u ) const
379 if ( ! e->Contains( this ))
380 myCloseEdges.push_back( std::make_pair( const_cast< BEdge* >( e ), u ));
382 BEdge* BNode::GetCloseEdgeOfBorder( int borderID, double * uPtr ) const
386 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
387 if ( borderID == GetCloseEdge( i )->myBorderID )
389 if ( e && Abs( u - 0.5 ) < Abs( GetCloseU( i ) - 0.5 ))
392 e = GetCloseEdge ( i );
394 if ( uPtr ) *uPtr = u;
397 bool BNode::HasCloseEdgeWithNode( const BNode* n ) const
399 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
400 if ( GetCloseEdge( i )->Contains( n ) &&
401 0 < GetCloseU( i ) && GetCloseU( i ) < 1 )
405 bool BNode::IsCloseEdge( const BEdge* e, double * uPtr ) const
407 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
408 if ( e == GetCloseEdge( i ) )
410 if ( uPtr ) *uPtr = GetCloseU( i );
416 /// Accessor to SMDS_MeshElement* inherited by BEdge
419 static const SMDS_MeshElement* value( std::vector< BEdge >::const_iterator it)
424 /// Iterator over a vector of BEdge's
425 static SMDS_ElemIteratorPtr getElemIterator( const std::vector< BEdge > & bedges )
427 typedef SMDS_SetIterator
428 < const SMDS_MeshElement*, std::vector< BEdge >::const_iterator, ElemAcess > BEIter;
429 return SMDS_ElemIteratorPtr( new BEIter( bedges.begin(), bedges.end() ));
434 //================================================================================
436 * Returns groups of TFreeBorder's coincident within the given tolerance.
437 * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
438 * to free borders being compared is used.
440 //================================================================================
442 void SMESH_MeshAlgos::FindCoincidentFreeBorders(SMDS_Mesh& mesh,
444 CoincidentFreeBorders & foundFreeBordes)
447 typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, SMESH_TLink > TLink2FaceMap;
448 TLink2FaceMap linkMap;
449 int nbSharedLinks = 0;
450 SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
451 while ( faceIt->more() )
453 const SMDS_MeshElement* face = faceIt->next();
454 if ( !face ) continue;
456 const SMDS_MeshNode* n0 = face->GetNode( face->NbNodes() - 1 );
457 SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
458 while ( nodeIt->more() )
460 const SMDS_MeshNode* n1 = nodeIt->next();
461 SMESH_TLink link( n0, n1 );
462 if ( const SMDS_MeshElement** faceInMap = linkMap.ChangeSeek( link ))
464 nbSharedLinks += bool( *faceInMap );
469 linkMap.Bind( link, face );
474 if ( linkMap.Extent() == nbSharedLinks )
478 std::set < BNode > bNodes;
479 std::vector< BEdge > bEdges( linkMap.Extent() - nbSharedLinks );
481 TLink2FaceMap::Iterator linkIt( linkMap );
482 for ( int iEdge = 0; linkIt.More(); linkIt.Next() )
484 if ( !linkIt.Value() ) continue;
485 const SMESH_TLink & link = linkIt.Key();
486 std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
487 std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
488 bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
489 n1->AddLinked( & bEdges[ iEdge ] );
490 n2->AddLinked( & bEdges[ iEdge ] );
495 // assign IDs to borders
496 std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
497 std::set< BNode >::iterator bn = bNodes.begin();
498 for ( ; bn != bNodes.end(); ++bn )
500 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
502 if ( bn->myLinkedEdges[i]->myBorderID < 0 )
504 BEdge* be = bn->myLinkedEdges[i];
505 int borderID = borders.size();
506 borders.push_back( be );
507 for ( ; be && be->myBorderID < 0; be = be->myNext )
509 be->myBorderID = borderID;
512 bool isClosed = ( be == bn->myLinkedEdges[i] );
513 be = bn->myLinkedEdges[i]->myPrev;
514 for ( ; be && be->myBorderID < 0; be = be->myPrev )
516 be->myBorderID = borderID;
520 while ( borders.back()->myPrev )
521 borders.back() = borders.back()->myPrev;
523 borders.back()->SetID( 0 ); // set IDs to all edges of the border
528 // compute tolerance of each border
529 double maxTolerance = tolerance;
530 std::vector< double > bordToler( borders.size(), tolerance );
531 if ( maxTolerance < std::numeric_limits< double >::min() )
533 // no tolerance provided by the user; compute tolerance of each border
534 // as one tenth of an average size of faces adjacent to a border
535 for ( size_t i = 0; i < borders.size(); ++i )
537 double avgFaceSize = 0;
539 BEdge* be = borders[ i ];
541 double facePerimeter = 0;
542 gp_Pnt p0 = SMESH_TNodeXYZ( be->myFace->GetNode( be->myFace->NbNodes() - 1 ));
543 SMDS_NodeIteratorPtr nodeIt = be->myFace->interlacedNodesIterator();
544 while ( nodeIt->more() )
546 gp_Pnt p1 = SMESH_TNodeXYZ( nodeIt->next() );
547 facePerimeter += p0.Distance( p1 );
550 avgFaceSize += ( facePerimeter / be->myFace->NbCornerNodes() );
555 while ( be && be != borders[i] );
557 bordToler[ i ] = 0.1 * avgFaceSize / nbFaces;
558 maxTolerance = Max( maxTolerance, bordToler[ i ]);
562 // for every border node find close border edges
563 SMESH_ElementSearcher* searcher =
564 GetElementSearcher( mesh, getElemIterator( bEdges ), maxTolerance );
565 SMESHUtils::Deleter< SMESH_ElementSearcher > searcherDeleter( searcher );
566 std::vector< const SMDS_MeshElement* > candidateEdges;
567 for ( bn = bNodes.begin(); bn != bNodes.end(); ++bn )
569 searcher->FindElementsByPoint( *bn, SMDSAbs_Edge, candidateEdges );
570 if ( candidateEdges.size() <= bn->myLinkedEdges.size() )
573 double nodeTol = 0, u;
574 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
575 nodeTol = Max( nodeTol, bordToler[ bn->myLinkedEdges[ i ]->myBorderID ]);
577 for ( size_t i = 0; i < candidateEdges.size(); ++i )
579 const BEdge* be = static_cast< const BEdge* >( candidateEdges[ i ]);
580 double tol = Max( nodeTol, bordToler[ be->myBorderID ]);
581 if ( !be->IsOut( *bn, tol, u ))
582 bn->AddClose( be, u );
586 // for every border edge find close borders
588 std::vector< BEdge* > closeEdges;
589 for ( size_t i = 0; i < bEdges.size(); ++i )
591 BEdge& be = bEdges[i];
592 if ( be.myBNode1->myCloseEdges.empty() ||
593 be.myBNode2->myCloseEdges.empty() )
597 for ( size_t iE1 = 0; iE1 < be.myBNode1->myCloseEdges.size(); ++iE1 )
599 // find edges of the same border close to both nodes of the edge
600 BEdge* closeE1 = be.myBNode1->GetCloseEdge( iE1 );
601 BEdge* closeE2 = be.myBNode2->GetCloseEdgeOfBorder( closeE1->myBorderID );
604 // check that edges connecting closeE1 and closeE2 (if any) are also close to 'be'
605 if ( closeE1 != closeE2 )
608 for ( int j = 0; j < 2; ++j ) // move closeE1 -> closeE2 or inversely
612 coincide = ( ce->myBNode2->GetCloseEdgeOfBorder( be.myBorderID ));
614 } while ( coincide && ce && ce != closeE2 );
616 if ( coincide && ce == closeE2 )
619 std::swap( closeE1, closeE2 );
624 closeEdges.push_back( closeE1 );
625 closeEdges.push_back( closeE2 );
629 closeEdges.push_back( closeE1 );
631 be.myCloseBorders.insert( closeE1->myBorderID );
633 if ( !closeEdges.empty() )
635 be.myCloseBorders.insert( be.myBorderID );
636 // for ( size_t iB = 0; iB < closeEdges.size(); ++iB )
637 // closeEdges[ iB ]->myCloseBorders.insert( be.myCloseBorders.begin(),
638 // be.myCloseBorders.end() );
642 // Fill in CoincidentFreeBorders
644 // save nodes of free borders
645 foundFreeBordes._borders.resize( borders.size() );
646 for ( size_t i = 0; i < borders.size(); ++i )
648 BEdge* be = borders[i];
649 foundFreeBordes._borders[i].push_back( be->myBNode1->Node() );
651 foundFreeBordes._borders[i].push_back( be->myBNode2->Node() );
654 while ( be && be != borders[i] );
657 // form groups of coincident parts of free borders
659 TFreeBorderPart part;
660 TCoincidentGroup group;
661 std::vector< BEdge* > ranges; // couples of edges delimiting parts
662 BEdge* be = 0; // a current edge
663 int skipGroup = bEdges.size(); // a group ID used to avoid repeating treatment of edges
665 for ( int i = 0, nbBords = borders.size(); i < nbBords; i += bool(!be) )
670 // look for an edge close to other borders
672 if ( !be->IsInGroup() && !be->myCloseBorders.empty() )
675 } while ( be && be != borders[i] );
677 if ( !be || be->IsInGroup() || be->myCloseBorders.empty() )
680 continue; // all edges of a border are treated or non-coincident
685 // look for the 1st and last edge of a coincident group
687 if ( !be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders ))
689 be->myInGroup = skipGroup;
694 ranges.push_back( beRange[0] );
695 ranges.push_back( beRange[1] );
697 int groupID = foundFreeBordes._coincidentGroups.size();
699 be->myInGroup = groupID;
700 while ( be != beRange[1] )
702 be->myInGroup = groupID;
705 beRange[1]->myInGroup = groupID;
707 // get starting edge of each close border
710 if ( be->myCloseBorders.empty() )
711 be = beRange[0]->myNext;
712 std::set<int>::iterator closeBord = be->myCloseBorders.begin();
713 for ( ; closeBord != be->myCloseBorders.end(); ++closeBord )
714 if ( BEdge* e = be->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
715 closeEdges.push_back( e );
717 for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
718 if ( be->myCloseBorders != closeEdges[iE]->myCloseBorders )
720 closeBord = closeEdges[iE]->myCloseBorders.begin();
721 for ( ; closeBord != closeEdges[iE]->myCloseBorders.end(); ++closeBord )
722 if ( !be->myCloseBorders.count( *closeBord ))
723 if ( BEdge* e = closeEdges[iE]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
724 if ( std::find( closeEdges.begin(), closeEdges.end(), e ) == closeEdges.end() )
725 closeEdges.push_back( e );
728 // add parts of other borders
730 BEdge* be1st = beRange[0];
731 for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
733 be = closeEdges[ iE ];
736 bool ok = be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders );
737 // if ( !ok && be->myPrev )
738 // ok = be->myPrev->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
739 // if ( !ok && be->myNext )
740 // ok = be->myNext->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
746 ranges.push_back( beRange[0] );
747 ranges.push_back( beRange[1] );
749 be->myInGroup = groupID;
750 while ( be != beRange[1] )
752 be->myInGroup = groupID;
755 beRange[1]->myInGroup = groupID;
758 if ( ranges.size() > 2 )
760 if ( !chooseStartOfClosedBorders( ranges ))
761 for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
762 extendPart( ranges[ iR-1 ], ranges[ iR ], be1st->myCloseBorders, groupID );
765 beRange[0] = ranges[0];
766 beRange[1] = ranges[1];
769 part._node1 = beRange[0]->myID;
770 part._node2 = beRange[0]->myID + 1;
771 part._nodeLast = beRange[1]->myID + 1;
772 group.push_back( part );
775 for ( size_t iR = 3; iR < ranges.size(); iR += 2 )
777 beRange[0] = ranges[iR-1];
778 beRange[1] = ranges[iR-0];
780 // find out mutual orientation of borders
782 be1st ->IsOut( *beRange[ 0 ]->myBNode1, maxTolerance, u1 );
783 beRange[ 0 ]->IsOut( *be1st->myBNode1, maxTolerance, u2 );
784 bool reverse = (( u1 < 0 || u1 > 1 ) && ( u2 < 0 || u2 > 1 ));
787 part._border = beRange[0]->myBorderID;
789 part._node1 = beRange[1]->myID + 1;
790 part._node2 = beRange[1]->myID;
791 part._nodeLast = beRange[0]->myID;
794 part._node1 = beRange[0]->myID;
795 part._node2 = beRange[0]->myID + 1;
796 part._nodeLast = beRange[1]->myID + 1;
798 // if ( group[0]._node2 != part._node2 )
799 group.push_back( part );
801 //if ( group.size() > 1 )
802 foundFreeBordes._coincidentGroups.push_back( group );
806 beRange[0] = ranges[0];
807 beRange[1] = ranges[1];
810 be->myInGroup = skipGroup;
811 while ( be != beRange[1] )
813 be->myInGroup = skipGroup;
816 beRange[1]->myInGroup = skipGroup;
821 } // loop on free borders
825 } // SMESH_MeshAlgos::FindCoincidentFreeBorders()
827 //================================================================================
829 * Returns all TFreeBorder's. Optionally check if the mesh is manifold
830 * and if faces are correctly oriented.
832 //================================================================================
834 void SMESH_MeshAlgos::FindFreeBorders(SMDS_Mesh& theMesh,
835 TFreeBorderVec & theFoundFreeBordes,
836 const bool theClosedOnly,
840 bool isManifold = true;
843 typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, SMESH_TLink > TLink2FaceMap;
844 TLink2FaceMap linkMap;
845 int nbSharedLinks = 0;
846 SMDS_FaceIteratorPtr faceIt = theMesh.facesIterator();
847 while ( faceIt->more() )
849 const SMDS_MeshElement* face = faceIt->next();
850 if ( !face ) continue;
852 const SMDS_MeshNode* n0 = face->GetNode( face->NbNodes() - 1 );
853 SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
854 while ( nodeIt->more() )
856 const SMDS_MeshNode* n1 = nodeIt->next();
857 SMESH_TLink link( n0, n1 );
858 if ( const SMDS_MeshElement** faceInMap = linkMap.ChangeSeek( link ))
862 if ( theIsGoodOri && *theIsGoodOri && !IsRightOrder( *faceInMap, n1, n0 ))
863 *theIsGoodOri = false;
869 nbSharedLinks += bool( *faceInMap );
874 linkMap.Bind( link, face );
880 *theIsManifold = isManifold;
882 if ( linkMap.Extent() == nbSharedLinks )
886 std::set < BNode > bNodes;
887 std::vector< BEdge > bEdges( linkMap.Extent() - nbSharedLinks );
889 TLink2FaceMap::Iterator linkIt( linkMap );
890 for ( int iEdge = 0; linkIt.More(); linkIt.Next() )
892 if ( !linkIt.Value() ) continue;
893 const SMESH_TLink & link = linkIt.Key();
894 std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
895 std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
896 bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
897 n1->AddLinked( & bEdges[ iEdge ] );
898 n2->AddLinked( & bEdges[ iEdge ] );
903 // assign IDs to borders
904 std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
905 std::set< BNode >::iterator bn = bNodes.begin();
906 for ( ; bn != bNodes.end(); ++bn )
908 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
910 if ( bn->myLinkedEdges[i]->myBorderID < 0 )
912 BEdge* be = bn->myLinkedEdges[i];
913 int borderID = borders.size();
914 borders.push_back( be );
915 for ( ; be && be->myBorderID < 0; be = be->myNext )
917 be->myBorderID = borderID;
920 bool isClosed = ( be == bn->myLinkedEdges[i] );
921 if ( !isClosed && theClosedOnly )
926 be = bn->myLinkedEdges[i]->myPrev;
927 for ( ; be && be->myBorderID < 0; be = be->myPrev )
929 be->myBorderID = borderID;
933 while ( borders.back()->myPrev )
934 borders.back() = borders.back()->myPrev;
938 theFoundFreeBordes.resize( borders.size() );
939 for ( size_t i = 0; i < borders.size(); ++i )
941 TFreeBorder & bordNodes = theFoundFreeBordes[ i ];
942 BEdge* be = borders[i];
945 for ( be = be->myNext; be && be != borders[i]; be = be->myNext )
947 bordNodes.resize( cnt + 1 );
950 for ( be = borders[i], cnt = 0;
951 be && cnt < bordNodes.size()-1;
952 be = be->myNext, ++cnt )
954 bordNodes[ cnt ] = be->myBNode1->Node();
958 bordNodes.back() = beLast->myBNode2->Node();