src/BRepAlgo/BRepAlgo_Loop.cxx

   1 // Created on: 1995-11-10
   2 // Created by: Yves FRICAUD
   3 // Copyright (c) 1995-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and / or modify it
   9 // under the terms of the GNU Lesser General Public version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <stdio.h>
  18
  19 #include <BRepAlgo_Loop.ixx>
  20
  21 #include <BRep_Builder.hxx>
  22 #include <BRepAlgo_FaceRestrictor.hxx>
  23 #include <BRep_Tool.hxx>
  24
  25 #include <Geom2d_Curve.hxx>
  26 #include <Geom_Surface.hxx>
  27 #include <TopExp.hxx>
  28 #include <TopTools_SequenceOfShape.hxx>
  29 #include <TopTools_MapOfShape.hxx>
  30 #include <TopTools_ListIteratorOfListOfShape.hxx>
  31 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  32
  33 #include <TopoDS.hxx>
  34 #include <TopoDS_Vertex.hxx>
  35 #include <TopoDS_Wire.hxx>
  36 #include <gp_Pnt.hxx>
  37 #include <gp_Pnt2d.hxx>
  38 #include <Precision.hxx>
  39 #include <BRep_TVertex.hxx>
  40 #include <BRep_TEdge.hxx>
  41 #include <TopExp_Explorer.hxx>
  42 #include <TopoDS_Iterator.hxx>
  43 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
  44
  45 #ifdef DRAW
  46 #include <DBRep.hxx>
  47 #endif
  48 #ifdef DEBUG_ALGO
  49 Standard_Boolean AffichLoop  = Standard_False;
  50 Standard_Integer NbLoops     = 0;
  51 Standard_Integer NbWires     = 1;
  52 static char* name = new char[100];
  53 #endif
  54
  55 //=======================================================================
  56 //function : BRepAlgo_Loop
  57 //purpose  :
  58 //=======================================================================
  59
  60 BRepAlgo_Loop::BRepAlgo_Loop()
  61 {
  62 }
  63
  64
  65 //=======================================================================
  66 //function : Init
  67 //purpose  :
  68 //=======================================================================
  69
  70 void BRepAlgo_Loop::Init(const TopoDS_Face& F)
  71 {
  72   myConstEdges.Clear();
  73   myVerOnEdges.Clear();
  74   myNewWires  .Clear();
  75   myNewFaces  .Clear();
  76   myNewEdges  .Clear();
  77   myFace = F;
  78 }
  79
  80
  81 //=======================================================================
  82 //function : Bubble
  83 //purpose  : Orders the sequence of vertices by increasing parameter.
  84 //=======================================================================
  85
  86 static void Bubble(const TopoDS_Edge&        E,
  87                    TopTools_SequenceOfShape& Seq)
  88 {
  89   Standard_Boolean Invert   = Standard_True;
  90   Standard_Integer NbPoints = Seq.Length();
  91   Standard_Real    U1,U2;
  92   TopoDS_Vertex    V1,V2;
  93
  94   while (Invert) {
  95     Invert = Standard_False;
  96     for ( Standard_Integer i = 1; i < NbPoints; i++) {
  97       TopoDS_Shape aLocalV = Seq.Value(i)  .Oriented(TopAbs_INTERNAL);
  98       V1 = TopoDS::Vertex(aLocalV);
  99       aLocalV = Seq.Value(i+1).Oriented(TopAbs_INTERNAL);
 100       V2 = TopoDS::Vertex(aLocalV);
 101 //      V1 = TopoDS::Vertex(Seq.Value(i)  .Oriented(TopAbs_INTERNAL));
 102 //      V2 = TopoDS::Vertex(Seq.Value(i+1).Oriented(TopAbs_INTERNAL));
 103
 104       U1 = BRep_Tool::Parameter(V1,E);
 105       U2 = BRep_Tool::Parameter(V2,E);
 106       if (U2 < U1) {
 107         Seq.Exchange(i,i+1);
 108         Invert = Standard_True;
 109       }
 110     }
 111   }
 112 }
 113
 114
 115
 116 //=======================================================================
 117 //function : AddEdges
 118 //purpose  :
 119 //=======================================================================
 120
 121 void BRepAlgo_Loop::AddEdge (TopoDS_Edge&                E,
 122                              const TopTools_ListOfShape& LV)
 123 {
 124   myVerOnEdges.Bind(E,LV);
 125 }
 126
 127
 128 //=======================================================================
 129 //function : AddConstEdges
 130 //purpose  :
 131 //=======================================================================
 132
 133 void BRepAlgo_Loop::AddConstEdge (const TopoDS_Edge& E)
 134 {
 135   myConstEdges.Append(E);
 136 }
 137
 138 //=======================================================================
 139 //function : AddConstEdges
 140 //purpose  :
 141 //=======================================================================
 142
 143 void BRepAlgo_Loop::AddConstEdges(const TopTools_ListOfShape& LE)
 144 {
 145   TopTools_ListIteratorOfListOfShape itl(LE);
 146   for (; itl.More(); itl.Next()) {
 147     myConstEdges.Append(itl.Value());
 148   }
 149 }
 150
 151
 152 //=======================================================================
 153 //function : UpdateClosedEdge
 154 //purpose  : If the first or the last vertex of intersection
 155 //           coincides with the closing vertex, it is removed from SV.
 156 //           it will be added at the beginning and the end of SV by the caller.
 157 //=======================================================================
 158
 159 static TopoDS_Vertex  UpdateClosedEdge(const TopoDS_Edge&         E,
 160                                        TopTools_SequenceOfShape&  SV)
 161 {
 162   TopoDS_Vertex    VB [2], V1, V2, VRes;
 163   gp_Pnt           P,PC;
 164   Standard_Boolean OnStart = 0, OnEnd = 0;
 165   //// modified by jgv, 13.04.04 for OCC5634 ////
 166   TopExp::Vertices (E,V1,V2);
 167   //Standard_Real    Tol = Precision::Confusion();
 168   Standard_Real    Tol = BRep_Tool::Tolerance( V1 );
 169   ///////////////////////////////////////////////
 170
 171   if (SV.IsEmpty()) return VRes;
 172
 173   VB[0] = TopoDS::Vertex(SV.First());
 174   VB[1] = TopoDS::Vertex(SV.Last ());
 175   PC = BRep_Tool::Pnt(V1);
 176
 177   for ( Standard_Integer i = 0 ; i < 2 ; i++) {
 178     P = BRep_Tool::Pnt(VB [i]);
 179     if (P.IsEqual(PC,Tol)) {
 180       VRes = VB [i];
 181       if (i == 0) OnStart = Standard_True;
 182       else        OnEnd   = Standard_True;
 183     }
 184   }
 185   if (OnStart && OnEnd) {
 186     if (!VB[0].IsSame(VB[1])) {
 187 #ifdef DEBUG_ALGO
 188       if (AffichLoop)
 189         cout <<"Two different vertices on the closing vertex"<<endl;
 190 #endif
 191     }
 192     else {
 193       SV.Remove(1);
 194       if (!SV.IsEmpty()) SV.Remove(SV.Length());
 195     }
 196   }
 197   else if (OnStart) SV.Remove(1);
 198   else if (OnEnd  ) SV.Remove(SV.Length());
 199
 200   return VRes;
 201 }
 202
 203
 204
 205 //=======================================================================
 206 //function : RemovePendingEdges
 207 //purpose  :
 208 //=======================================================================
 209
 210 static void RemovePendingEdges(TopTools_DataMapOfShapeListOfShape& MVE)
 211 {
 212   //--------------------------------
 213   // Remove hanging edges.
 214   //--------------------------------
 215   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 216   TopTools_ListOfShape                     ToRemove;
 217   TopTools_ListIteratorOfListOfShape       itl;
 218   Standard_Boolean                         YaSupress = Standard_True;
 219   TopoDS_Vertex                            V1,V2;
 220
 221   while (YaSupress) {
 222     YaSupress = Standard_False;
 223     TopTools_ListOfShape VToRemove;
 224     TopTools_MapOfShape  EToRemove;
 225
 226     for (Mapit.Initialize(MVE); Mapit.More(); Mapit.Next()) {
 227
 228       if (Mapit.Value().IsEmpty()) {
 229         VToRemove.Append(Mapit.Key());
 230       }
 231       if (Mapit.Value().Extent() == 1) {
 232         const TopoDS_Edge& E = TopoDS::Edge(Mapit.Value().First());
 233         TopExp::Vertices(E,V1,V2) ;
 234         if (!V1.IsSame(V2)) {
 235           VToRemove.Append(Mapit.Key());
 236           EToRemove.Add(Mapit.Value().First());
 237         }
 238       }
 239     }
 240
 241     if (!VToRemove.IsEmpty()) {
 242       YaSupress = Standard_True;
 243       for (itl.Initialize(VToRemove); itl.More(); itl.Next()) {
 244         MVE.UnBind(itl.Value());
 245       }
 246       if (!EToRemove.IsEmpty()) {
 247         for (Mapit.Initialize(MVE); Mapit.More(); Mapit.Next()) {
 248           TopTools_ListOfShape& LE = MVE.ChangeFind(Mapit.Key());
 249           itl.Initialize(LE);
 250           while (itl.More()) {
 251             if (EToRemove.Contains(itl.Value())) {
 252               LE.Remove(itl);
 253             }
 254             else itl.Next();
 255           }
 256         }
 257       }
 258     }
 259   }
 260 }
 261 //=======================================================================
 262 //function : SamePnt2d
 263 //purpose  :
 264 //=======================================================================
 265
 266 static Standard_Boolean  SamePnt2d(TopoDS_Vertex  V,
 267                                    TopoDS_Edge&   E1,
 268                                    TopoDS_Edge&   E2,
 269                                    TopoDS_Face&   F)
 270 {
 271   Standard_Real   f1,f2,l1,l2;
 272   gp_Pnt2d        P1,P2;
 273   TopoDS_Shape aLocalF = F.Oriented(TopAbs_FORWARD);
 274   TopoDS_Face FF = TopoDS::Face(aLocalF);
 275 //  TopoDS_Face FF = TopoDS::Face(F.Oriented(TopAbs_FORWARD));
 276   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1,FF,f1,l1);
 277   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E2,FF,f2,l2);
 278   if (E1.Orientation () == TopAbs_FORWARD) P1 = C1->Value(f1);
 279   else                                     P1 = C1->Value(l1);
 280
 281   if (E2.Orientation () == TopAbs_FORWARD) P2 = C2->Value(l2);
 282   else                                     P2 = C2->Value(f2);
 283   Standard_Real Tol  = 100*BRep_Tool::Tolerance(V);
 284   Standard_Real Dist = P1.Distance(P2);
 285   return Dist < Tol;
 286 }
 287
 288 //=======================================================================
 289 //function : SelectEdge
 290 //purpose  : Find edge <NE> connected to <CE> by vertex <CV> in the
 291 //           list <LE>. <NE> is removed from the list. If <CE> is
 292 //           also in the list <LE> with the same orientation, it is
 293 //           removed from the list.
 294 //=======================================================================
 295
 296 static Standard_Boolean  SelectEdge(const TopoDS_Face&    F,
 297                                     const TopoDS_Edge&    CE,
 298                                     const TopoDS_Vertex&  CV,
 299                                     TopoDS_Edge&          NE,
 300                                     TopTools_ListOfShape& LE)
 301 {
 302   TopTools_ListIteratorOfListOfShape itl;
 303   NE.Nullify();
 304 #ifdef DEBUG_ALGO
 305   if (AffichLoop) {
 306     if ( LE.Extent() > 2) {
 307       cout <<"vertex on more than 2 edges in a face."<<endl;
 308     }
 309   }
 310 #endif
 311   for ( itl.Initialize(LE); itl.More(); itl.Next()) {
 312     if (itl.Value().IsEqual(CE)) {
 313       LE.Remove(itl);
 314       break;
 315     }
 316   }
 317   if (LE.Extent() > 1) {
 318     //--------------------------------------------------------------
 319     // Several edges possible.
 320     // - Test edges different from CE , Selection of edge
 321     // for which CV has U,V closer to the face
 322     // than corresponding to CE.
 323     // - If several edges give representation less than the tolerance.
 324     // discrimination on tangents.
 325     //--------------------------------------------------------------
 326     TopLoc_Location L;
 327     Standard_Real   f,l;
 328     TopoDS_Face FForward = F;
 329     FForward.Orientation(TopAbs_FORWARD);
 330
 331     Handle(Geom2d_Curve) C = BRep_Tool::CurveOnSurface(CE,FForward,f,l);
 332     Standard_Integer k = 1, kmin = 0;
 333     Standard_Real    dist,distmin  = 100*BRep_Tool::Tolerance(CV);
 334     Standard_Real    u ;
 335     if (CE.Orientation () == TopAbs_FORWARD) u = l;
 336     else                                     u = f;
 337
 338     gp_Pnt2d         P2,PV = C->Value(u);
 339
 340     for ( itl.Initialize(LE); itl.More(); itl.Next()) {
 341       const TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 342       if (!E.IsSame(CE)) {
 343         C    = BRep_Tool::CurveOnSurface(E,FForward,f,l);
 344         if (E.Orientation () == TopAbs_FORWARD) u = f;
 345         else                                    u = l;
 346         P2   = C->Value(u);
 347         dist = PV.Distance(P2);
 348         if ( dist <= distmin) {
 349           kmin    = k;
 350           distmin = dist;
 351         }
 352       }
 353       k++;
 354     }
 355     if (kmin == 0) return Standard_False;
 356
 357     k = 1; itl.Initialize(LE);
 358     while (k < kmin) {k++; itl.Next();}
 359     NE = TopoDS::Edge(itl.Value());
 360     LE.Remove(itl);
 361   }
 362   else if (LE.Extent() == 1) {
 363     NE = TopoDS::Edge(LE.First());
 364     LE.RemoveFirst();
 365   }
 366   else {
 367     return Standard_False;
 368   }
 369 #ifdef DRAW
 370   if (AffichLoop) {
 371     DBRep::Set("Selected",NE);
 372   }
 373
 374 #endif
 375   return Standard_True;
 376 }
 377 //=======================================================================
 378 //function : Store
 379 //purpose  :
 380 //=======================================================================
 381
 382 static void  PurgeNewEdges(TopTools_DataMapOfShapeListOfShape& NewEdges,
 383                            const TopTools_MapOfShape&          UsedEdges)
 384 {
 385   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape it(NewEdges);
 386   for (; it.More(); it.Next()) {
 387     TopTools_ListOfShape& LNE = NewEdges.ChangeFind(it.Key());
 388     TopTools_ListIteratorOfListOfShape itL(LNE);
 389     while (itL.More()) {
 390       const TopoDS_Shape& NE = itL.Value();
 391       if (!UsedEdges.Contains(NE)) {
 392         LNE.Remove(itL);
 393       }
 394       else {
 395         itL.Next();
 396       }
 397     }
 398   }
 399
 400 }
 401
 402 //=======================================================================
 403 //function : Store
 404 //purpose  :
 405 //=======================================================================
 406
 407 static void StoreInMVE (const TopoDS_Face&                  F,
 408                         TopoDS_Edge&                  E,
 409                         TopTools_DataMapOfShapeListOfShape& MVE,
 410                         Standard_Boolean&                   YaCouture,
 411                         TopTools_DataMapOfShapeShape& VerticesForSubstitute )
 412 {
 413   TopoDS_Vertex V1, V2, V;
 414   TopTools_ListOfShape Empty;
 415
 416   Standard_Real Tol = 0.001; //5.e-05; //5.e-07;
 417 //  gp_Pnt P1, P2, P;
 418   gp_Pnt P1, P;
 419   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 420   BRep_Builder BB;
 421   for (Mapit.Initialize( MVE ); Mapit.More(); Mapit.Next())
 422     {
 423       V = TopoDS::Vertex( Mapit.Key() );
 424       P = BRep_Tool::Pnt( V );
 425       TopTools_ListOfShape VList;
 426       TopoDS_Iterator VerExp( E );
 427       for (; VerExp.More(); VerExp.Next())
 428         VList.Append( VerExp.Value() );
 429       TopTools_ListIteratorOfListOfShape itl( VList );
 430       for (; itl.More(); itl.Next())
 431         {
 432           V1 = TopoDS::Vertex( itl.Value() );
 433           P1 = BRep_Tool::Pnt( V1 );
 434           if (P.IsEqual( P1, Tol ) && !V.IsSame(V1))
 435             {
 436               V.Orientation( V1.Orientation() );
 437               if (VerticesForSubstitute.IsBound( V1 ))
 438                 {
 439                   TopoDS_Shape OldNewV = VerticesForSubstitute( V1 );
 440                   if (! OldNewV.IsSame( V ))
 441                     {
 442                       VerticesForSubstitute.Bind( OldNewV, V );
 443                       VerticesForSubstitute( V1 ) = V;
 444                     }
 445                 }
 446               else
 447                 {
 448                   if (VerticesForSubstitute.IsBound( V ))
 449                     {
 450                       TopoDS_Shape NewNewV = VerticesForSubstitute( V );
 451                       if (! NewNewV.IsSame( V1 ))
 452                         VerticesForSubstitute.Bind( V1, NewNewV );
 453                     }
 454                   else
 455                     {
 456                       VerticesForSubstitute.Bind( V1, V );
 457                       TopTools_DataMapIteratorOfDataMapOfShapeShape mapit( VerticesForSubstitute );
 458                       for (; mapit.More(); mapit.Next())
 459                         if (mapit.Value().IsSame( V1 ))
 460                           VerticesForSubstitute( mapit.Key() ) = V;
 461                     }
 462                 }
 463               E.Free( Standard_True );
 464               BB.Remove( E, V1 );
 465               BB.Add( E, V );
 466             }
 467         }
 468     }
 469
 470   TopExp::Vertices(E,V1,V2);
 471   if( V1.IsNull() && V2.IsNull() ){ YaCouture = Standard_False; return; }
 472   if (!MVE.IsBound(V1)) {
 473     MVE.Bind(V1,Empty);
 474   }
 475   MVE(V1).Append(E);
 476   if (!V1.IsSame(V2)) {
 477      if (!MVE.IsBound(V2)) {
 478       MVE.Bind(V2,Empty);
 479     }
 480     MVE(V2).Append(E);
 481   }
 482   TopLoc_Location L ;
 483   Handle(Geom_Surface) S = BRep_Tool::Surface(F,L);
 484   if (BRep_Tool::IsClosed(E,S,L)) {
 485     MVE(V2).Append(E.Reversed());
 486     if (!V1.IsSame(V2)) {
 487       MVE(V1).Append(E.Reversed());
 488     }
 489     YaCouture = Standard_True;
 490   }
 491 }
 492
 493 //=======================================================================
 494 //function : Perform
 495 //purpose  :
 496 //=======================================================================
 497
 498 void BRepAlgo_Loop::Perform()
 499 {
 500   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 501   TopTools_ListIteratorOfListOfShape                  itl;
 502   TopoDS_Vertex                                       V1,V2;
 503   Standard_Boolean                                    YaCouture = Standard_False;
 504
 505 #ifdef DEBUG_ALGO
 506   if (AffichLoop) {
 507     cout <<"NewLoop"<<endl;
 508     NbLoops++;
 509 #ifdef DRAW
 510     sprintf(name,"FLoop_%d",NbLoops);
 511     DBRep::Set(name,myFace);
 512     Standard_Integer NbEdges = 1;
 513 #endif
 514     for (Mapit.Initialize(myVerOnEdges); Mapit.More(); Mapit.Next()) {
 515       const TopoDS_Edge& E = TopoDS::Edge(Mapit.Key());
 516 #ifdef DRAW
 517       sprintf(name,"EEE_%d_%d",NbLoops,NbEdges++);
 518       DBRep::Set(name,E);
 519 #endif
 520     }
 521     for (itl.Initialize(myConstEdges); itl.More(); itl.Next()) {
 522       const TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 523 #ifdef DRAW
 524       sprintf(name,"EEE_%d_%d",NbLoops,NbEdges++);
 525       DBRep::Set(name,E);
 526 #endif
 527     }
 528   }
 529 #endif
 530   //------------------------------------------------
 531   // Cut edges
 532   //------------------------------------------------
 533   for (Mapit.Initialize(myVerOnEdges); Mapit.More(); Mapit.Next()) {
 534     TopTools_ListOfShape LCE;
 535
 536     CutEdge (TopoDS::Edge(Mapit.Key()),Mapit.Value(), LCE);
 537
 538     myNewEdges.Bind(Mapit.Key(),LCE);
 539   }
 540   //-----------------------------------
 541   // Construction map vertex => edges
 542   //-----------------------------------
 543   TopTools_DataMapOfShapeListOfShape MVE;
 544
 545   // add cut edges.
 546   for (Mapit.Initialize(myNewEdges); Mapit.More(); Mapit.Next()) {
 547     for (itl.Initialize(myNewEdges(Mapit.Key())); itl.More(); itl.Next()) {
 548       TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 549       StoreInMVE(myFace,E,MVE,YaCouture,myVerticesForSubstitute);
 550     }
 551   }
 552
 553   // add const edges
 554   // Sewn edges can be doubled or not in myConstEdges
 555   // => call only once StoreInMVE which should double them
 556   TopTools_MapOfShape DejaVu;
 557   for (itl.Initialize(myConstEdges); itl.More(); itl.Next()) {
 558     TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 559     if (DejaVu.Add(E))
 560       StoreInMVE(myFace,E,MVE,YaCouture,myVerticesForSubstitute);
 561   }
 562
 563 #ifdef DRAW
 564   if (AffichLoop) {
 565     cout <<"NewLoop"<<endl;
 566     Standard_Integer NbEdges = 1;
 567     TopTools_MapOfShape Done;
 568     for (Mapit.Initialize(MVE); Mapit.More();Mapit.Next()) {
 569       for (itl.Initialize(Mapit.Value()); itl.More(); itl.Next()) {
 570         TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 571         if (Done.Add(E)) {
 572           sprintf(name,"EEC_%d_%d",NbLoops,NbEdges++);
 573           DBRep::Set(name,E);
 574         }
 575       }
 576     }
 577   }
 578 #endif
 579
 580   //-----------------------------------------------
 581   // Construction of wires and new faces.
 582   //----------------------------------------------
 583   TopoDS_Vertex    VF,VL,CV;
 584   TopoDS_Edge      CE,NE,EF;
 585   BRep_Builder     B;
 586   TopoDS_Wire      NW;
 587   Standard_Boolean End;
 588
 589   TopTools_MapOfShape UsedEdges;
 590
 591   while (!MVE.IsEmpty()) {
 592     B.MakeWire(NW);
 593     //--------------------------------
 594     // Removal of hanging edges.
 595     //--------------------------------
 596     RemovePendingEdges(MVE);
 597
 598     if (MVE.IsEmpty()) break;
 599     //--------------------------------
 600     // Start edge.
 601     //--------------------------------
 602     Mapit.Initialize(MVE);
 603     EF = CE = TopoDS::Edge(Mapit.Value().First());
 604     TopExp::Vertices(CE,V1,V2);
 605     //--------------------------------
 606     // VF vertex start of new wire
 607     //--------------------------------
 608     if (CE.Orientation() == TopAbs_FORWARD) { CV = VF = V1;}
 609     else                                    { CV = VF = V2;}
 610     if (!MVE.IsBound(CV)) continue;
 611     for ( itl.Initialize(MVE(CV)); itl.More(); itl.Next()) {
 612       if (itl.Value().IsEqual(CE)) {
 613         MVE(CV).Remove(itl);
 614         break;
 615       }
 616     }
 617     End  = Standard_False;
 618
 619     while (!End) {
 620       //-------------------------------
 621       // Construction of a wire.
 622       //-------------------------------
 623       TopExp::Vertices(CE,V1,V2);
 624       if (!CV.IsSame(V1)) CV = V1; else CV = V2;
 625
 626       B.Add (NW,CE);
 627       UsedEdges.Add(CE);
 628
 629       if (!MVE.IsBound(CV) || MVE(CV).IsEmpty()) {
 630         End = Standard_True;
 631       }
 632       else {
 633         End = !SelectEdge(myFace,CE,CV,NE,MVE(CV));
 634         if (!End) {
 635           CE = NE;
 636           if (MVE(CV).IsEmpty()) MVE.UnBind(CV);
 637         }
 638       }
 639     }
 640     //--------------------------------------------------
 641     // Add new wire to the set of wires
 642     //------------------------------------------------
 643     Standard_Real Tol = 0.001; //5.e-05; //5.e-07;
 644     TopExp_Explorer explo( NW, TopAbs_VERTEX );
 645     for (; explo.More(); explo.Next())
 646       {
 647       const TopoDS_Vertex& aV = TopoDS::Vertex( explo.Current() );
 648       Handle(BRep_TVertex)& TV = *((Handle(BRep_TVertex)*) &(aV).TShape());
 649       TV->Tolerance( Tol );
 650       TV->Modified( Standard_True );
 651       }
 652     for (explo.Init( NW, TopAbs_EDGE ); explo.More(); explo.Next())
 653       {
 654       const TopoDS_Edge& aE = TopoDS::Edge( explo.Current() );
 655       Handle(BRep_TEdge)& TE = *((Handle(BRep_TEdge)*) &(aE).TShape());
 656       TE->Tolerance( Tol );
 657       TE->Modified( Standard_True );
 658       }
 659
 660     if (VF.IsSame(CV) && SamePnt2d(VF,EF,CE,myFace))
 661       myNewWires.Append (NW);
 662 #ifdef DEBUG_ALGO
 663     else {
 664       cout <<"BRepAlgo_Loop: Open Wire"<<endl;
 665       if (AffichLoop)
 666         cout << "OpenWire is : NW_"<<NbLoops<<"_"<<NbWires<<endl;
 667       }
 668 #endif
 669 #ifdef DRAW
 670     if (AffichLoop) {
 671       sprintf(name,"NW_%d_%d",NbLoops,NbWires++);
 672       DBRep::Set(name,NW);
 673     }
 674 #endif
 675   }
 676
 677   PurgeNewEdges(myNewEdges,UsedEdges);
 678 }
 679
 680 //=======================================================================
 681 //function : CutEdges
 682 //purpose  :
 683 //=======================================================================
 684
 685 void BRepAlgo_Loop::CutEdge (const TopoDS_Edge&          E,
 686                              const TopTools_ListOfShape& VOnE,
 687                                      TopTools_ListOfShape& NE   ) const
 688 {
 689   TopoDS_Shape aLocalE  = E.Oriented(TopAbs_FORWARD);
 690   TopoDS_Edge WE = TopoDS::Edge(aLocalE);
 691
 692   Standard_Real                      U1,U2;
 693   TopoDS_Vertex                      V1,V2;
 694   TopTools_SequenceOfShape           SV;
 695   TopTools_ListIteratorOfListOfShape it(VOnE);
 696   BRep_Builder                       B;
 697
 698   for ( ; it.More(); it.Next()) {
 699     SV.Append(it.Value());
 700   }
 701   //--------------------------------
 702   // Parse vertices on the edge.
 703   //--------------------------------
 704   Bubble (WE,SV);
 705
 706   Standard_Integer NbVer = SV.Length();
 707   //----------------------------------------------------------------
 708   // Construction of new edges.
 709   // Note :  vertices at the extremities of edges are not
 710   //         onligatorily in the list of vertices
 711   //----------------------------------------------------------------
 712   if (SV.IsEmpty()) {
 713     NE.Append(E);
 714     return;
 715   }
 716   TopoDS_Vertex    VF,VL;
 717   Standard_Real    f,l;
 718   BRep_Tool::Range(WE,f,l);
 719   TopExp::Vertices(WE,VF,VL);
 720
 721   if (NbVer == 2) {
 722     if (SV(1).IsEqual(VF) && SV(2).IsEqual(VL)) {
 723       NE.Append(E);
 724 #ifdef DRAW
 725       if (AffichLoop) {
 726       DBRep::Set("ECOpied",E);
 727     }
 728 #endif
 729       return;
 730     }
 731   }
 732   //----------------------------------------------------
 733   // Processing of closed edges
 734   // If a vertex of intersection is on the common vertex
 735   // it should appear at the beginning and end of SV.
 736   //----------------------------------------------------
 737   TopoDS_Vertex VCEI;
 738   if (!VF.IsNull() && VF.IsSame(VL)) {
 739     VCEI = UpdateClosedEdge(WE,SV);
 740     if (!VCEI.IsNull()) {
 741       TopoDS_Shape aLocalV = VCEI.Oriented(TopAbs_FORWARD);
 742       VF = TopoDS::Vertex(aLocalV);
 743       aLocalV = VCEI.Oriented(TopAbs_REVERSED);
 744       VL = TopoDS::Vertex(aLocalV);
 745 //      VF = TopoDS::Vertex(VCEI.Oriented(TopAbs_FORWARD));
 746 //      VL = TopoDS::Vertex(VCEI.Oriented(TopAbs_REVERSED));
 747     }
 748     SV.Prepend(VF);
 749     SV.Append(VL);
 750   }
 751   else {
 752     //-----------------------------------------
 753     // Eventually all extremities of the edge.
 754     //-----------------------------------------
 755     if (!VF.IsNull() && !VF.IsSame(SV.First())) SV.Prepend(VF);
 756     if (!VL.IsNull() && !VL.IsSame(SV.Last ())) SV.Append (VL);
 757   }
 758
 759   while (!SV.IsEmpty()) {
 760     while (!SV.IsEmpty() &&
 761            SV.First().Orientation() != TopAbs_FORWARD) {
 762       SV.Remove(1);
 763     }
 764     if (SV.IsEmpty())
 765       break;
 766     V1  = TopoDS::Vertex(SV.First());
 767     SV.Remove(1);
 768     if (SV.IsEmpty())
 769       break;
 770     if (SV.First().Orientation() == TopAbs_REVERSED) {
 771       V2  = TopoDS::Vertex(SV.First());
 772       SV.Remove(1);
 773       //-------------------------------------------
 774       // Copy the edge and restriction by V1 V2.
 775       //-------------------------------------------
 776       TopoDS_Shape NewEdge = WE.EmptyCopied();
 777       TopoDS_Shape aLocalEdge = V1.Oriented(TopAbs_FORWARD);
 778       B.Add  (NewEdge,aLocalEdge);
 779       aLocalEdge = V2.Oriented(TopAbs_REVERSED);
 780       B.Add  (TopoDS::Edge(NewEdge),aLocalEdge);
 781 //      B.Add  (NewEdge,V1.Oriented(TopAbs_FORWARD));
 782 //      B.Add  (NewEdge,V2.Oriented(TopAbs_REVERSED));
 783       if (V1.IsSame(VF))
 784         U1 = f;
 785       else
 786 //      U1=BRep_Tool::Parameter
 787 //        (TopoDS::Vertex(V1.Oriented(TopAbs_INTERNAL)),WE);
 788         {
 789           TopoDS_Shape aLocalV = V1.Oriented(TopAbs_INTERNAL);
 790           U1=BRep_Tool::Parameter(TopoDS::Vertex(aLocalV),WE);
 791         }
 792       if (V2.IsSame(VL))
 793         U2 = l;
 794       else
 795         {
 796           TopoDS_Shape aLocalV = V2.Oriented(TopAbs_INTERNAL);
 797           U2=BRep_Tool::Parameter(TopoDS::Vertex(aLocalV),WE);
 798 //      U2=BRep_Tool::Parameter
 799 //        (TopoDS::Vertex(V2.Oriented(TopAbs_INTERNAL)),WE);
 800         }
 801       B.Range (TopoDS::Edge(NewEdge),U1,U2);
 802 #ifdef DRAW
 803     if (AffichLoop) {
 804       DBRep::Set("Cut",NewEdge);
 805     }
 806 #endif
 807       NE.Append(NewEdge.Oriented(E.Orientation()));
 808     }
 809   }
 810
 811   //Remove edges with size <= tolerance
 812   Standard_Real Tol = 0.001; //5.e-05; //5.e-07;
 813   it.Initialize(NE);
 814   while (it.More())
 815     {
 816       // skl : I change "E" to "EE"
 817       TopoDS_Edge EE = TopoDS::Edge( it.Value() );
 818       Standard_Real fpar, lpar;
 819       BRep_Tool::Range( EE, fpar, lpar );
 820       if (lpar - fpar <= Precision::Confusion())
 821         NE.Remove(it);
 822       else
 823         {
 824           gp_Pnt2d pf, pl;
 825           BRep_Tool::UVPoints( EE, myFace, pf, pl );
 826           if (pf.Distance(pl) <= Tol && !EE.Closed())
 827             NE.Remove(it);
 828           else
 829             it.Next();
 830         }
 831     }
 832 }
 833
 834 //=======================================================================
 835 //function : NewWires
 836 //purpose  :
 837 //=======================================================================
 838
 839 const TopTools_ListOfShape&  BRepAlgo_Loop::NewWires() const
 840 {
 841   return myNewWires;
 842 }
 843
 844 //=======================================================================
 845 //function : NewFaces
 846 //purpose  :
 847 //=======================================================================
 848
 849 const TopTools_ListOfShape&  BRepAlgo_Loop::NewFaces() const
 850 {
 851   return myNewFaces;
 852 }
 853
 854 //=======================================================================
 855 //function : WiresToFaces
 856 //purpose  :
 857 //=======================================================================
 858
 859 void  BRepAlgo_Loop::WiresToFaces()
 860 {
 861   if (!myNewWires.IsEmpty()) {
 862     BRepAlgo_FaceRestrictor FR;
 863     TopoDS_Shape aLocalS = myFace.Oriented(TopAbs_FORWARD);
 864     FR.Init (TopoDS::Face(aLocalS),Standard_False);
 865 //    FR.Init (TopoDS::Face(myFace.Oriented(TopAbs_FORWARD)),
 866 //           Standard_False);
 867     TopTools_ListIteratorOfListOfShape it(myNewWires);
 868     for (; it.More(); it.Next()) {
 869       FR.Add(TopoDS::Wire(it.Value()));
 870     }
 871
 872     FR.Perform();
 873
 874     if (FR.IsDone()) {
 875       TopAbs_Orientation OriF = myFace.Orientation();
 876       for (; FR.More(); FR.Next()) {
 877         myNewFaces.Append(FR.Current().Oriented(OriF));
 878       }
 879     }
 880   }
 881 }
 882
 883
 884 //=======================================================================
 885 //function : NewEdges
 886 //purpose  :
 887 //=======================================================================
 888
 889 const TopTools_ListOfShape&  BRepAlgo_Loop::NewEdges(const TopoDS_Edge& E) const
 890 {
 891   return myNewEdges(E);
 892 }
 893
 894 //=======================================================================
 895 //function : GetVerticesForSubstitute
 896 //purpose  :
 897 //=======================================================================
 898
 899 void  BRepAlgo_Loop::GetVerticesForSubstitute( TopTools_DataMapOfShapeShape& VerVerMap ) const
 900 {
 901   VerVerMap = myVerticesForSubstitute;
 902 }
 903 //=======================================================================
 904 //function : VerticesForSubstitute
 905 //purpose  :
 906 //=======================================================================
 907
 908 void  BRepAlgo_Loop::VerticesForSubstitute( TopTools_DataMapOfShapeShape& VerVerMap )
 909 {
 910   myVerticesForSubstitute = VerVerMap;
 911 }