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