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
52 const SMDS_MeshNode * myNode;
53 mutable std::vector< BEdge* > myLinkedEdges;
54 mutable std::vector< BEdge* > myCloseEdges;
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(); }
63 * \brief Edge of a free border
65 struct BEdge : public SMDS_LinearEdge
67 const BNode* myBNode1;
68 const BNode* myBNode2;
70 int myID; // within a border
73 const SMDS_MeshElement* myFace;
74 std::set< int > myCloseBorders;
77 BEdge():SMDS_LinearEdge( 0, 0 ), myBorderID(-1), myID(-1), myPrev(0), myNext(0), myInGroup(0) {}
79 void Set( const BNode * node1,
81 const SMDS_MeshElement* face,
86 myNodes[0] = node1->myNode;
87 myNodes[1] = node2->myNode;
89 setId( ID ); // mesh element ID
91 bool Contains( const BNode* n ) const
93 return ( n == myBNode1 || n == myBNode2 );
95 void AddLinked( BEdge* e )
97 if ( e->Contains( myBNode1 )) myPrev = e;
100 void RemoveLinked( BEdge* e )
102 if ( myPrev == e ) myPrev = 0;
103 if ( myNext == e ) myNext = 0;
107 std::swap( myBNode1, myBNode2 );
108 myNodes[0] = myBNode1->myNode;
109 myNodes[1] = myBNode2->myNode;
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();
125 myNext->SetID( id + 1 );
128 void FindRangeOfSameCloseBorders(BEdge* eRange[2])
131 while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == this->myCloseBorders )
133 if ( eRange[0]->myPrev == this /*|| eRange[0]->myPrev->myInGroup*/ )
135 eRange[0] = eRange[0]->myPrev;
138 if ( eRange[0]->myPrev != this ) // not closed range
139 while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == this->myCloseBorders )
141 if ( eRange[1]->myNext == this /*|| eRange[1]->myNext->myInGroup*/ )
143 eRange[1] = eRange[1]->myNext;
148 void BNode::AddLinked( BEdge* e ) const
150 myLinkedEdges.reserve(2);
151 myLinkedEdges.push_back( e );
152 if ( myLinkedEdges.size() < 2 ) return;
154 if ( myLinkedEdges.size() == 2 )
156 myLinkedEdges[0]->AddLinked( myLinkedEdges[1] );
157 myLinkedEdges[1]->AddLinked( myLinkedEdges[0] );
161 for ( size_t i = 0; i < myLinkedEdges.size(); ++i )
162 for ( size_t j = 0; j < myLinkedEdges.size(); ++j )
164 myLinkedEdges[i]->RemoveLinked( myLinkedEdges[j] );
167 void BNode::AddClose ( const BEdge* e ) const
169 if ( ! e->Contains( this ))
170 myCloseEdges.push_back( const_cast< BEdge* >( e ));
172 BEdge* BNode::FindCloseEdgeOfBorder( int borderID ) const
174 for ( size_t i = 0; i < myCloseEdges.size(); ++i )
175 if ( borderID == myCloseEdges[ i ]->myBorderID )
176 return myCloseEdges[ i ];
180 /// Accessor to SMDS_MeshElement* inherited by BEdge
183 static const SMDS_MeshElement* value( std::vector< BEdge >::const_iterator it)
188 /// Iterator over a vector of BEdge's
189 static SMDS_ElemIteratorPtr getElemIterator( const std::vector< BEdge > & bedges )
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() ));
198 // struct needed for NCollection_Map
201 static int HashCode(const SMESH_TLink& link, int aLimit)
203 return ::HashCode( link.node1()->GetID() + link.node2()->GetID(), aLimit );
205 static Standard_Boolean IsEqual(const SMESH_TLink& l1, const SMESH_TLink& l2)
207 return ( l1.node1() == l2.node1() && l1.node2() == l2.node2() );
211 //================================================================================
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.
217 //================================================================================
219 void SMESH_MeshAlgos::FindCoincidentFreeBorders(SMDS_Mesh& mesh,
221 CoincidentFreeBorders & foundFreeBordes)
224 typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, TLinkHasher > TLink2FaceMap;
225 TLink2FaceMap linkMap;
226 SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
227 while ( faceIt->more() )
229 const SMDS_MeshElement* face = faceIt->next();
230 if ( !face ) continue;
232 const SMDS_MeshNode* n0 = face->GetNode( face->NbNodes() - 1 );
233 SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
234 while ( nodeIt->more() )
236 const SMDS_MeshNode* n1 = nodeIt->next();
237 SMESH_TLink link( n0, n1 );
238 if ( !linkMap.Bind( link, face ))
239 linkMap.UnBind( link );
243 if ( linkMap.IsEmpty() )
247 std::set < BNode > bNodes;
248 std::vector< BEdge > bEdges( linkMap.Extent() );
250 TLink2FaceMap::Iterator linkIt( linkMap );
251 for ( int iEdge = 0; linkIt.More(); linkIt.Next(), ++iEdge )
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 ] );
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 )
267 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
269 if ( bn->myLinkedEdges[i]->myBorderID < 0 )
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 )
276 be->myBorderID = borderID;
279 bool isClosed = ( be == bn->myLinkedEdges[i] );
280 be = bn->myLinkedEdges[i]->myPrev;
281 for ( ; be && be->myBorderID < 0; be = be->myPrev )
283 be->myBorderID = borderID;
287 while ( borders.back()->myPrev )
288 borders.back() = borders.back()->myPrev;
290 borders.back()->SetID( 0 ); // set IDs to all edges of the border
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() )
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 )
304 double avgFaceSize = 0;
306 BEdge* be = borders[ i ];
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() )
313 gp_Pnt p1 = SMESH_TNodeXYZ( nodeIt->next() );
314 facePerimeter += p0.Distance( p1 );
317 avgFaceSize += ( facePerimeter / be->myFace->NbCornerNodes() );
322 while ( be && be != borders[i] );
324 bordToler[ i ] = 0.1 * avgFaceSize / nbFaces;
325 maxTolerance = Max( maxTolerance, bordToler[ i ]);
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 )
336 gp_Pnt point = SMESH_TNodeXYZ( bn->myNode );
337 searcher->FindElementsByPoint( point, SMDSAbs_Edge, candidateEdges );
338 if ( candidateEdges.size() <= bn->myLinkedEdges.size() )
342 for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
343 nodeTol = Max( nodeTol, bordToler[ bn->myLinkedEdges[ i ]->myBorderID ]);
345 for ( size_t i = 0; i < candidateEdges.size(); ++i )
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 ))
355 // for every border edge find close borders
357 std::vector< BEdge* > closeEdges;
358 for ( size_t i = 0; i < bEdges.size(); ++i )
360 BEdge& be = bEdges[i];
361 if ( be.myBNode1->myCloseEdges.empty() ||
362 be.myBNode2->myCloseEdges.empty() )
366 for ( size_t iE1 = 0; iE1 < be.myBNode1->myCloseEdges.size(); ++iE1 )
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 );
373 // check that edges connecting closeE1 and closeE2 (if any) are also close to 'be'
374 if ( closeE1 != closeE2 )
377 for ( int j = 0; j < 2; ++j ) // move closeE1 -> closeE2 or inversely
381 coincide = ( ce->myBNode2->FindCloseEdgeOfBorder( be.myBorderID ));
383 } while ( coincide && ce && ce != closeE2 );
385 if ( coincide && ce == closeE2 )
388 std::swap( closeE1, closeE2 );
393 closeEdges.push_back( closeE1 );
394 closeEdges.push_back( closeE2 );
398 closeEdges.push_back( closeE1 );
400 be.myCloseBorders.insert( closeE1->myBorderID );
402 if ( !closeEdges.empty() )
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() );
411 // Fill in CoincidentFreeBorders
413 // save nodes of free borders
414 foundFreeBordes._borders.resize( borders.size() );
415 for ( size_t i = 0; i < borders.size(); ++i )
417 BEdge* be = borders[i];
418 foundFreeBordes._borders[i].push_back( be->myBNode1->myNode );
420 foundFreeBordes._borders[i].push_back( be->myBNode2->myNode );
423 while ( be && be != borders[i] );
426 // form groups of coincident parts of free borders
428 TFreeBorderPart part;
429 TCoincidentGroup group;
430 for ( size_t i = 0; i < borders.size(); ++i )
432 BEdge* be = borders[i];
434 // look for an edge close to other borders
436 if ( !be->myInGroup && !be->myCloseBorders.empty() )
439 } while ( be && be != borders[i] );
441 if ( !be || be->myInGroup || be->myCloseBorders.empty() )
442 continue; // all edges of a border treated or are non-coincident
446 // look for the 1st and last edge of a coincident group
448 be->FindRangeOfSameCloseBorders( beRange );
449 BEdge* be1st = beRange[0];
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 );
459 be->myInGroup = true;
460 while ( be != beRange[1] )
462 be->myInGroup = true;
465 beRange[1]->myInGroup = true;
467 // add parts of other borders
468 std::set<int>::iterator closeBord = be1st->myCloseBorders.begin();
469 for ( ; closeBord != be1st->myCloseBorders.end(); ++closeBord )
471 be = be1st->myBNode2->FindCloseEdgeOfBorder( *closeBord );
474 be->FindRangeOfSameCloseBorders( beRange );
476 // find out mutual orientation of borders
477 bool reverse = ( beRange[0]->myBNode1->FindCloseEdgeOfBorder( i ) != be1st &&
478 beRange[0]->myBNode2->FindCloseEdgeOfBorder( i ) != be1st );
481 part._border = beRange[0]->myBorderID;
483 part._node1 = beRange[1]->myID + 1;
484 part._node2 = beRange[1]->myID;
485 part._nodeLast = beRange[0]->myID;
488 part._node1 = beRange[0]->myID;
489 part._node2 = beRange[0]->myID + 1;
490 part._nodeLast = beRange[1]->myID + 1;
492 group.push_back( part );
495 be->myInGroup = true;
496 while ( be != beRange[1] )
498 be->myInGroup = true;
501 beRange[1]->myInGroup = true;
504 foundFreeBordes._coincidentGroups.push_back( group );
506 } // loop on free borders