Salome HOME
23156: EDF 9626 SMESH: Dump study produces a non-working script
[modules/smesh.git] / 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