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