src/PARTITION/Partition_Loop2d.cxx

   1 //  GEOM PARTITION : partition algorithm
   2 //
   3 //  Copyright (C) 2003  CEA/DEN, EDF R&D
   4 //
   5 //
   6 //
   7 //  File   : Partition_Loop2d.cxx
   8 //  Author : Benedicte MARTIN
   9 //  Module : GEOM
  10 //  $Header$
  11
  12 using namespace std;
  13 #include "Partition_Loop2d.ixx"
  14
  15 #include "utilities.h"
  16 #include <stdio.h>
  17
  18 #include <BRepAdaptor_Curve2d.hxx>
  19 #include <BRepAdaptor_Surface.hxx>
  20 #include <BRepAlgo_AsDes.hxx>
  21 #include <BRepOffset_DataMapOfShapeReal.hxx>
  22 #include <BRepTopAdaptor_FClass2d.hxx>
  23 #include <BRep_Builder.hxx>
  24 #include <BRep_Tool.hxx>
  25 #include <Geom2dInt_GInter.hxx>
  26 #include <Geom2d_Curve.hxx>
  27 #include <IntRes2d_IntersectionPoint.hxx>
  28 #include <Precision.hxx>
  29 #include <TColStd_MapOfInteger.hxx>
  30 #include <TColStd_SequenceOfReal.hxx>
  31 #include <TopExp.hxx>
  32 #include <TopExp_Explorer.hxx>
  33 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  34 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
  35 #include <TopTools_DataMapOfShapeInteger.hxx>
  36 #include <TopTools_DataMapOfShapeShape.hxx>
  37 #include <TopTools_IndexedMapOfShape.hxx>
  38 #include <TopTools_ListIteratorOfListOfShape.hxx>
  39 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  40 #include <TopTools_MapOfOrientedShape.hxx>
  41 #include <TopTools_MapOfShape.hxx>
  42 #include <TopTools_SequenceOfShape.hxx>
  43 #include <TopoDS.hxx>
  44 #include <TopoDS_Iterator.hxx>
  45 #include <TopoDS_Vertex.hxx>
  46 #include <TopoDS_Wire.hxx>
  47 #include <gp_Pnt.hxx>
  48 #include <gp_Pnt2d.hxx>
  49
  50 //=======================================================================
  51 //function : Partition_Loop2d
  52 //purpose  :
  53 //=======================================================================
  54
  55 Partition_Loop2d::Partition_Loop2d()
  56 {
  57 }
  58
  59 //=======================================================================
  60 //function : Init
  61 //purpose  : Init with <F> the set of edges must have
  62 //           pcurves on <F>.
  63 //=======================================================================
  64
  65 void Partition_Loop2d::Init(const TopoDS_Face& F)
  66 {
  67   myConstEdges.Clear();
  68   myNewWires  .Clear();
  69   myNewFaces  .Clear();
  70   myFace = F;
  71   myFaceOri = myFace.Orientation();
  72   myFace.Orientation( TopAbs_FORWARD );
  73 }
  74
  75 //=======================================================================
  76 //function : AddConstEdge
  77 //purpose  : Add <E> as unique edge in the result.
  78 //=======================================================================
  79
  80 void Partition_Loop2d::AddConstEdge (const TopoDS_Edge& E)
  81 {
  82 #ifdef DEB
  83   Standard_Real f,l;
  84   Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
  85   if (pc.IsNull()) {
  86     INFOS( "AddConstEdge(): EDGE W/O PCURVE on FACE");
  87   } else
  88 #endif
  89   {
  90     myConstEdges.Append(E);
  91   }
  92 }
  93
  94 void Partition_Loop2d::AddSectionEdge (const TopoDS_Edge& E)
  95 {
  96 #ifdef DEB
  97   Standard_Real f,l;
  98   Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
  99   if (pc.IsNull())
 100     pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
 101   gp_Vec2d Tg1;
 102   gp_Pnt2d PC;
 103   pc->D1(0.5*(f+l), PC, Tg1);
 104   if (Tg1.Magnitude()  <= gp::Resolution()) {
 105     MESSAGE ("");
 106   }
 107   if (pc.IsNull()) {
 108     INFOS( "AddConstEdge(): EDGE W/O PCURVE on FACE");
 109   } else
 110 #endif
 111   {
 112     myConstEdges.Append(E);
 113     myConstEdges.Append(E.Reversed());
 114     mySectionEdges.Add( E );
 115   }
 116 }
 117
 118 //=======================================================================
 119 //function : SelectEdge
 120 //purpose  : Find the edge <NE> connected <CE> by the vertex <CV> in the list <LE>.
 121 //           <NE> Is erased  of the list. If <CE> is too in the list <LE>
 122 //           with the same orientation, it's erased of the list
 123 //=======================================================================
 124
 125 static Standard_Boolean  SelectEdge(const BRepAdaptor_Surface& Surf,
 126                                     const TopoDS_Edge&    CE,
 127                                     const TopoDS_Vertex&  CV,
 128                                     TopoDS_Edge&          NE,
 129                                     const TopTools_ListOfShape& LE)
 130 {
 131   NE.Nullify();
 132
 133   if (LE.Extent() > 1) {
 134     //--------------------------------------------------------------
 135     // Several possible edges.
 136     // - Test the edges differents of CE
 137     //--------------------------------------------------------------
 138     TopoDS_Face FForward = Surf.Face();
 139
 140     Standard_Real   cf, cl, f, l;
 141     Handle(Geom2d_Curve) Cc, C;
 142     Cc = BRep_Tool::CurveOnSurface(CE,FForward,cf,cl);
 143
 144 //    Standard_Real tolV, tol2d2;
 145     Standard_Real tolV = BRep_Tool::Tolerance(CV);
 146 //     tol2d2 = Max ( Surf.UResolution(tolV) , Surf.VResolution(tolV) );
 147 //     tol2d2 = 2 * Max ( tol2d2, Precision::PConfusion() );
 148 //     tol2d2 *= tol2d2;
 149
 150     Standard_Real uc,u, du = Precision::PConfusion();
 151     if (CE.Orientation () == TopAbs_FORWARD) uc = cl + du;
 152     else                                     uc = cf - du;
 153
 154     gp_Vec2d CTg1, Tg1;
 155     gp_Pnt2d PC, P;
 156     gp_Pnt P3d;
 157
 158     Cc->D1(uc, PC, CTg1);
 159     if (CE.Orientation () == TopAbs_REVERSED) CTg1.Reverse();
 160
 161     Standard_Real anglemin = 3 * PI;
 162 //    Standard_Real sqdist, sqdistmin = 1.0e50;
 163
 164     TopTools_ListIteratorOfListOfShape itl;
 165     for ( itl.Initialize(LE); itl.More(); itl.Next()) {
 166       const TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 167       if (E.IsSame(CE))
 168         continue;
 169       if (! CV.IsSame( TopExp::FirstVertex( E, Standard_True )))
 170         continue;
 171
 172       C = BRep_Tool::CurveOnSurface(E,FForward,f,l);
 173       if (E.Orientation () == TopAbs_FORWARD) u = f + du;
 174       else                                    u = l - du;
 175
 176       C->D1(u, P, Tg1);
 177 //       if (P.SquareDistance(PC); > tol2d2)
 178 //        continue;
 179
 180       if (E.Orientation () == TopAbs_REVERSED) Tg1.Reverse();
 181
 182       Standard_Real angle = Tg1.Angle(CTg1);
 183
 184       if (angle <= anglemin) {
 185         anglemin = angle ;
 186         NE = E;
 187 #ifdef DEB
 188 //      sqdist = P.SquareDistance(PC);
 189 //      if (sqdist < sqdistmin)
 190 //        sqdistmin = sqdist;
 191         P3d = Surf.Value (PC.X(), PC.Y());
 192 #endif
 193       }
 194     }
 195 #ifdef DEB
 196     if (!NE.IsNull() && P3d.Distance( BRep_Tool::Pnt(CV)) > tolV) {
 197       MESSAGE( "DISTANCE MORE THAN VERTEX TOL (" << tolV << ")" );
 198       cout << "point p " << P3d.X() << " " << P3d.Y() << " " << P3d.Z() << endl;
 199     }
 200 #endif
 201   }
 202   else if (LE.Extent() == 1) {
 203     NE = TopoDS::Edge(LE.First());
 204   }
 205   else {
 206     return Standard_False;
 207   }
 208   return !NE.IsNull();
 209 }
 210
 211 //=======================================================================
 212 //function : SamePnt2d
 213 //purpose  :
 214 //=======================================================================
 215
 216 static Standard_Boolean  SamePnt2d(const TopoDS_Vertex& V1,
 217                                    const TopoDS_Edge&   E1,
 218                                    const TopoDS_Vertex& V2,
 219                                    const TopoDS_Edge&   E2,
 220                                    const TopoDS_Face&   F)
 221 {
 222   Standard_Real   f1,f2,l1,l2;
 223   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1,F,f1,l1);
 224   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E2,F,f2,l2);
 225
 226   gp_Pnt2d P1 = C1->Value( BRep_Tool::Parameter(V1,E1));
 227   gp_Pnt2d P2 = C2->Value( BRep_Tool::Parameter(V2,E2));
 228
 229   Standard_Real Tol  = 100 * BRep_Tool::Tolerance(V1);
 230   Standard_Real Dist = P1.Distance(P2);
 231   return Dist < Tol;
 232 }
 233
 234
 235 //=======================================================================
 236 //function : StoreInMVE
 237 //purpose  :
 238 //=======================================================================
 239
 240 static void StoreInMVE (const TopoDS_Face& /*F*/,
 241                         TopoDS_Edge& E,
 242                         TopTools_DataMapOfShapeListOfShape& MVE )
 243
 244 {
 245   TopoDS_Vertex V1, V2;
 246   TopTools_ListOfShape Empty;
 247
 248   TopExp::Vertices(E,V1,V2);
 249   if (!MVE.IsBound(V1)) {
 250     MVE.Bind(V1,Empty);
 251   }
 252   MVE(V1).Append(E);
 253
 254   if (!MVE.IsBound(V2)) {
 255     MVE.Bind(V2,Empty);
 256   }
 257   MVE(V2).Append(E);
 258 }
 259
 260 //=======================================================================
 261 //function : RemoveFromMVE
 262 //purpose  :
 263 //=======================================================================
 264
 265 static void RemoveFromMVE(const TopoDS_Edge& E,
 266                           TopTools_DataMapOfShapeListOfShape& MVE)
 267 {
 268   TopTools_ListIteratorOfListOfShape itl;
 269   TopoDS_Vertex  V1,V2;
 270   TopExp::Vertices (E,V1,V2);
 271   if (MVE.IsBound(V1))
 272     for ( itl.Initialize(MVE(V1)); itl.More(); itl.Next()) {
 273       if (itl.Value().IsEqual(E)) {
 274         MVE(V1).Remove(itl);
 275         break;
 276       }
 277     }
 278   if (MVE.IsBound(V2))
 279     for ( itl.Initialize(MVE(V2)); itl.More(); itl.Next()) {
 280       if (itl.Value().IsEqual(E)) {
 281         MVE(V2).Remove(itl);
 282         break;
 283       }
 284     }
 285 }
 286 //=======================================================================
 287 //function : addConnected
 288 //purpose  : add to <EM> all edges reachable from <E>
 289 //=======================================================================
 290
 291 static void addConnected(const TopoDS_Shape& E,
 292                          TopTools_MapOfShape& EM,
 293                          TopTools_MapOfShape& VM,
 294                          const TopTools_DataMapOfShapeListOfShape& MVE)
 295 {
 296   // Loop on vertices of E
 297   TopoDS_Iterator itV ( E );
 298   for ( ; itV.More(); itV.Next()) {
 299
 300     if ( ! VM.Add ( itV.Value() )) continue;
 301
 302     // Loop on edges sharing V
 303     TopTools_ListIteratorOfListOfShape itE( MVE( itV.Value() ) );
 304     for (; itE.More(); itE.Next()) {
 305       if ( EM.Add( itE.Value() ))
 306         addConnected ( itE.Value(), EM, VM, MVE );
 307     }
 308   }
 309 }
 310 //=======================================================================
 311 //function : canPassToOld
 312 //purpose  :
 313 //=======================================================================
 314
 315 static Standard_Boolean canPassToOld (const TopoDS_Shape& V,
 316                                       TopTools_MapOfShape& UsedShapesMap,
 317                                       const TopTools_DataMapOfShapeListOfShape& MVE,
 318                                       const TopTools_MapOfShape& SectionEdgesMap)
 319 {
 320   TopTools_ListIteratorOfListOfShape itE( MVE(V) );
 321   // Loop on edges sharing V
 322   for (; itE.More(); itE.Next()) {
 323     if ( !UsedShapesMap.Add( itE.Value() ))
 324       continue; // already checked
 325
 326     if ( !SectionEdgesMap.Contains( itE.Value() ))
 327       return Standard_True; // WE PASSED
 328
 329     TopoDS_Iterator itV( itE.Value() );
 330     // Loop on vertices of an edge
 331     for (; itV.More(); itV.Next()) {
 332       if ( !UsedShapesMap.Add( itV.Value() ))
 333         continue; // already checked
 334       else
 335         return canPassToOld( itV.Value(), UsedShapesMap, MVE, SectionEdgesMap);
 336     }
 337   }
 338   return Standard_False;
 339 }
 340
 341 //=======================================================================
 342 //function : MakeDegenAndSelect
 343 //purpose  : Find parameter of intersection of <CE> with <DE> and
 344 //           select an edge with its parameter closest to found one.
 345 //           Return new degenerated edge trimming <DE> by found parameters
 346 //=======================================================================
 347
 348 static TopoDS_Edge MakeDegenAndSelect(const TopoDS_Edge& CE,
 349                                       const TopoDS_Vertex& CV,
 350                                       TopoDS_Edge& NE,
 351                                       TopTools_SequenceOfShape& EdgesSeq,
 352                                       TColStd_SequenceOfReal& USeq,
 353                                       const TopoDS_Edge& DE)
 354 {
 355   if (EdgesSeq.Length() < 3) {
 356     if (CE == EdgesSeq.First())
 357       NE = TopoDS::Edge( EdgesSeq.Last() );
 358     else
 359       NE = TopoDS::Edge( EdgesSeq.First() );
 360     return DE;
 361   }
 362
 363   // find parameter on DE where it intersects CE
 364
 365   Standard_Real U1;
 366   Standard_Integer i, nb = EdgesSeq.Length();
 367   for (i=1; i<= nb; ++i) {
 368     if (CE == EdgesSeq(i)) {
 369       U1 = USeq(i);
 370       break;
 371     }
 372   }
 373
 374   // select NE with param closest to U1 thus finding U2 for a new degen edge
 375
 376   Standard_Real U2, dU, dUmin = 1.e100;
 377   Standard_Boolean isReversed = ( DE.Orientation() == TopAbs_REVERSED );
 378   for (i=1; i<= nb; ++i) {
 379     dU = USeq(i) - U1;
 380     if (isReversed ? (dU > 0) : (dU < 0))
 381         continue;
 382     dU = Abs( dU );
 383     if ( dU  > dUmin || IsEqual( dU, 0.))
 384       continue;
 385     const TopoDS_Edge& E = TopoDS::Edge ( EdgesSeq(i) );
 386     if ( ! CV.IsSame( TopExp::FirstVertex( E , Standard_True )))
 387       continue;
 388     NE = E;
 389     dUmin = dU + Epsilon(dU);
 390     U2 = USeq(i);
 391   }
 392
 393   // make a new degenerated edge
 394   TopoDS_Edge NewDegen = TopoDS::Edge ( DE.EmptyCopied() );
 395
 396   Standard_Real Tol = BRep_Tool::Tolerance( CV );
 397   TopoDS_Vertex V = CV;
 398
 399   BRep_Builder B;
 400   V.Orientation( NewDegen.Orientation() );
 401   B.UpdateVertex( V, U1, NewDegen, Tol);
 402   B.Add ( NewDegen , V );
 403
 404   V.Reverse();
 405   B.UpdateVertex( V, U2, NewDegen, Tol);
 406   B.Add ( NewDegen , V );
 407
 408   return NewDegen;
 409 }
 410
 411 //=======================================================================
 412 //function : prepareDegen
 413 //purpose  : Intersect <DegEdge> with edges bound to its vertex in <MVE>
 414 //           and store intersection parameter on <DegEdge> in
 415 //           <USeq> as well as the edges them-self in <EdgesSeq>.
 416 //           Bind <DegEdgeIndex> to vertex of <DegEdge> in <MVDEI>
 417 //=======================================================================
 418
 419 static void prepareDegen (const TopoDS_Edge&                        DegEdge,
 420                           const TopoDS_Face&                        F,
 421                           const TopTools_DataMapOfShapeListOfShape& MVE,
 422                           TopTools_SequenceOfShape&                 EdgesSeq,
 423                           TColStd_SequenceOfReal&                   USeq,
 424                           TopTools_DataMapOfShapeInteger&           MVDEI,
 425                           const Standard_Integer                    DegEdgeIndex)
 426 {
 427   const TopoDS_Vertex& V = TopExp::FirstVertex ( DegEdge );
 428   MVDEI.Bind ( V, DegEdgeIndex );
 429
 430   const TopTools_ListOfShape& EdgesList = MVE ( V );
 431   // if only 2 edges come to degenerated one, no pb in selection and
 432   // no need to intersect them, just simulate asked data
 433   Standard_Boolean doIntersect =  ( EdgesList.Extent() > 2 );
 434
 435   BRepAdaptor_Curve2d DC, C;
 436   Geom2dInt_GInter InterCC;
 437   Standard_Real Tol = Precision::PConfusion();
 438   if ( doIntersect )
 439     DC.Initialize( DegEdge, F );
 440
 441   // avoid intersecting twice the same edge
 442   BRepOffset_DataMapOfShapeReal EUMap ( EdgesList.Extent() );
 443
 444   Standard_Real U, f, l;
 445   BRep_Tool::Range (DegEdge, f, l);
 446
 447   TopTools_ListIteratorOfListOfShape itE (EdgesList);
 448   for (; itE.More(); itE.Next()) {
 449
 450     const TopoDS_Edge& E = TopoDS::Edge ( itE.Value() );
 451
 452     if ( !doIntersect) {
 453       U = 0.; // it won't be used
 454     }
 455     else if ( BRep_Tool::IsClosed( E, F )) {
 456       // seam edge: select U among f and l
 457       Standard_Boolean first = Standard_True;
 458       if ( V.IsSame ( TopExp::FirstVertex( E, Standard_True ) ))
 459         first = Standard_False;
 460       if ( DegEdge.Orientation() == TopAbs_REVERSED )
 461         first = !first;
 462       U = first ? f : l;
 463     }
 464     else if ( EUMap.IsBound( E ) ) {
 465       // same edge already bound
 466       U = EUMap( E );
 467     }
 468     else {
 469       // intersect 2d curves
 470       C.Initialize( E, F );
 471       InterCC.Perform ( DC, C , Tol, Tol );
 472       if (! InterCC.IsDone() || InterCC.NbPoints() == 0) {
 473         MESSAGE ( "NO 2d INTERSECTION ON DEGENERATED EDGE" );
 474         continue;
 475       }
 476       // hope there is only one point of intersection
 477       U = InterCC.Point( 1 ).ParamOnFirst();
 478     }
 479     USeq.Append ( U );
 480     EdgesSeq.Append ( E );
 481   }
 482 }
 483 //=======================================================================
 484 //function : Perform
 485 //purpose  : Make loops.
 486 //=======================================================================
 487
 488 void Partition_Loop2d::Perform()
 489 {
 490
 491   Standard_Integer NbConstEdges = myConstEdges.Extent();
 492   TopTools_DataMapOfShapeListOfShape MVE(NbConstEdges) , MVE2(NbConstEdges);
 493   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 494   TopTools_ListIteratorOfListOfShape itl;
 495   TopoDS_Vertex V1,V2;
 496   BRepAdaptor_Surface Surface ( myFace, Standard_False );
 497
 498   // degenerated edges and parameters of their 2d intersection with other edges
 499   TopoDS_Edge                    DE [2];
 500   TopTools_SequenceOfShape       SEID [2]; // seq of edges intersecting degenerated
 501   TColStd_SequenceOfReal         SeqU [2]; // n-th U corresponds to n-th edge in SEID
 502   TopTools_DataMapOfShapeInteger MVDEI(2); // map vertex - degenerated edge index
 503   Standard_Integer               iDeg = 0; // index of degenerated edge [0,1]
 504
 505   //---------------------------------------------------------
 506   // Construction map vertex => edges, find degenerated edges
 507   //---------------------------------------------------------
 508   for (itl.Initialize(myConstEdges); itl.More(); itl.Next()) {
 509     TopoDS_Edge& E = TopoDS::Edge(itl.Value());
 510     if ( BRep_Tool::Degenerated( E )) {
 511       if (DE[0].IsNull()) DE[0] = E;
 512       else                DE[1] = E;
 513     }
 514     else
 515       StoreInMVE(myFace,E,MVE);
 516   }
 517
 518   // fill data for degenerated edges
 519   if ( ! DE[0].IsNull() )
 520     prepareDegen ( DE[0], myFace, MVE, SEID[0], SeqU[0], MVDEI, 0);
 521   if ( ! DE[1].IsNull() )
 522     prepareDegen ( DE[1], myFace, MVE, SEID[1], SeqU[1], MVDEI, 1);
 523
 524
 525   // to detect internal wires
 526   Standard_Boolean isInternCW = 0;
 527   MVE2 = MVE;
 528
 529
 530   //------------------------------
 531   // Construction of all the wires
 532   //------------------------------
 533   // first, we collect wire edges in WEL list looking for same edges that
 534   // will be then removed possibly exploding a wire into parts;
 535   // second, build wire(s)
 536
 537   while (!MVE.IsEmpty()) {
 538
 539     TopoDS_Vertex    VF,CV;
 540     TopoDS_Edge      CE,NE,EF;
 541     TopoDS_Wire      NW;
 542     BRep_Builder     B;
 543     Standard_Boolean End = Standard_False;
 544     TopTools_ListOfShape WEL;
 545
 546     Mapit.Initialize(MVE);
 547     if (Mapit.Value().IsEmpty()) {
 548       MVE.UnBind(Mapit.Key());
 549       continue;
 550     }
 551
 552     // EF first edge.
 553     EF = CE = TopoDS::Edge(Mapit.Value().First());
 554     // VF first vertex
 555     VF = TopExp::FirstVertex( CE, Standard_True);
 556
 557     isInternCW = Standard_True;
 558
 559     TopTools_MapOfShape addedEM  (NbConstEdges); // map of edges added to WEL
 560     TopTools_MapOfShape doubleEM (NbConstEdges); // edges encountered twice in WEL
 561
 562     //-------------------------------
 563     // Construction of a wire.
 564     //-------------------------------
 565     while (!End) {
 566
 567       // only a seam is allowed twice in a wire, the others should be removed
 568       if (addedEM.Add ( CE ) || BRep_Tool::IsClosed( CE, myFace ) )
 569         WEL.Append( CE );
 570       else {
 571         doubleEM.Add( CE );
 572         RemoveFromMVE (CE,MVE2);
 573         TopoDS_Edge CERev = CE;
 574         CERev.Reverse();
 575         RemoveFromMVE (CERev,MVE2);
 576       }
 577
 578       RemoveFromMVE (CE,MVE);
 579
 580       CV = TopExp::LastVertex( CE, Standard_True);
 581
 582       if (isInternCW && !mySectionEdges.Contains(CE))
 583         // wire is internal if all edges are section ones
 584         isInternCW = Standard_False;
 585
 586       if (MVDEI.IsBound( CV )) { // CE comes to the degeneration
 587         iDeg = MVDEI( CV );
 588         TopoDS_Edge NewDegen;
 589         NewDegen = MakeDegenAndSelect( CE, CV, NE, SEID[iDeg], SeqU[iDeg], DE[iDeg]);
 590         WEL.Append( NewDegen );
 591         CE = NE;
 592         End = CV.IsSame( VF );
 593         continue;
 594       }
 595
 596       //--------------
 597       // stop test
 598       //--------------
 599       if (MVE(CV).IsEmpty()) {
 600         End=Standard_True;
 601         MVE.UnBind(CV);
 602       }
 603       else if (CV.IsSame(VF) && SamePnt2d(CV,CE, VF,EF, myFace) ) {
 604         End = Standard_True;
 605       }
 606       else {
 607         //----------------------------
 608         // select new current edge
 609         //----------------------------
 610         if (! SelectEdge (Surface,CE,CV,NE,MVE(CV))) {
 611           MESSAGE ( " NOT CLOSED WIRE " );
 612           End=Standard_True;
 613         }
 614         else
 615           CE = NE;
 616       }
 617     } // while ( !End )
 618
 619
 620     // WEL is built, built wire(s)
 621
 622
 623     itl.Initialize( WEL );
 624     if ( doubleEM.IsEmpty()) { // no double edges
 625       B.MakeWire( NW );
 626       for (; itl.More(); itl.Next())
 627         B.Add ( NW, itl.Value());
 628       if (isInternCW) myInternalWL.Append(NW);
 629       else            myNewWires.Append  (NW);
 630     }
 631
 632     else {
 633       // remove double and degenerated edges from WEL
 634       while (itl.More()) {
 635         const TopoDS_Edge& E = TopoDS::Edge ( itl.Value() );
 636         if ( doubleEM.Contains( E ) || BRep_Tool::Degenerated( E ))
 637           WEL.Remove( itl );
 638         else
 639            itl.Next();
 640       }
 641       if ( WEL.IsEmpty())
 642         continue;
 643       // remove double edges from SEID and SeqU
 644       Standard_Integer i,j;
 645       for (j=0; j<2; ++j) {
 646         for (i=1; i<=SEID[j].Length(); ++i) {
 647           if (doubleEM.Contains( SEID[j].Value(i))) {
 648             SEID[j].Remove( i );
 649             SeqU[j].Remove( i-- );
 650           }
 651         }
 652       }
 653       // removal of doulbe edges can explode a wire into parts,
 654       // make new wires of them.
 655       // A Loop like previous one but without 2d check
 656       while ( !WEL.IsEmpty() ) {
 657         CE = TopoDS::Edge( WEL.First() );
 658         WEL.RemoveFirst();
 659         B.MakeWire( NW );
 660         VF = TopExp::FirstVertex ( EF, Standard_True);
 661
 662         End = Standard_False;
 663         while ( !End) {
 664           B.Add( NW, CE );
 665           CV = TopExp::LastVertex  ( CE, Standard_True);
 666
 667           if (MVDEI.IsBound( CV )) {   // CE comes to the degeneration
 668             iDeg = MVDEI( CV );
 669             TopoDS_Edge NewDegen;
 670             NewDegen = MakeDegenAndSelect( CE, CV, NE, SEID[iDeg], SeqU[iDeg], DE[iDeg]);
 671             B.Add( NW, NewDegen );
 672             End = CV.IsSame( VF );
 673             CE = NE;
 674             if (!NE.IsNull()) { // remove NE from WEL
 675               for (itl.Initialize( WEL ); itl.More(); itl.Next())
 676                 if ( NE == itl.Value()) {
 677                   WEL.Remove( itl );
 678                   break;
 679                 }
 680             }
 681           }  // end degeneration
 682
 683           else {
 684             if (CV.IsSame( VF )) {
 685               End = Standard_True;
 686               continue;
 687             }
 688             // edges in WEL most often are well ordered
 689             // so try to iterate until the End
 690             Standard_Boolean add = Standard_False;
 691             itl.Initialize(WEL);
 692             while ( itl.More() && !End) {
 693               NE = TopoDS::Edge( itl.Value() );
 694               if ( CV.IsSame( TopExp::FirstVertex( NE, Standard_True ))) {
 695                 WEL.Remove( itl );
 696                 if (add)
 697                   B.Add( NW, CE );
 698                 CE = NE;
 699                 add = Standard_True;
 700                 CV = TopExp::LastVertex( CE, Standard_True);
 701                 if (MVDEI.IsBound( CV ) || CV.IsSame( VF ))
 702                   break;
 703               }
 704               else
 705                 itl.Next();
 706             }
 707             if (!add)
 708               End = Standard_True;
 709           }
 710         } // !End
 711
 712         myInternalWL.Append( NW );
 713       }
 714     } // end building new wire(s) from WEL
 715
 716   } // end Loop on MVE
 717
 718   // all wires are built
 719
 720
 721   // ============================================================
 722   // select really internal wires i.e. those from which we can`t
 723   // pass to an old (not section) edge
 724   // ============================================================
 725
 726   Standard_Integer nbIW = myInternalWL.Extent();
 727   if ( nbIW == 1 ) {
 728     TopTools_MapOfShape UsedShapes( 2*NbConstEdges );
 729     TopExp_Explorer expV (myInternalWL.First(), TopAbs_VERTEX);
 730     if (canPassToOld (expV.Current(), UsedShapes, MVE2, mySectionEdges))
 731       myNewWires.Append ( myInternalWL );
 732   }
 733   else if ( nbIW > 1 ) {
 734     TopTools_MapOfShape outerEM (NbConstEdges); // edges connected to non-section ones
 735     TopTools_MapOfShape visitedVM (NbConstEdges);
 736     for ( itl.Initialize( myConstEdges ); itl.More(); itl.Next()) {
 737       if ( ! mySectionEdges.Contains( itl.Value() ))
 738         addConnected (itl.Value(), outerEM, visitedVM, MVE2);
 739     }
 740     // if an edge of a wire is in <outerEM>, the wire is not internal
 741     TopExp_Explorer expIWE;
 742     TopTools_ListIteratorOfListOfShape itIW ( myInternalWL );
 743     while (itIW.More()) {
 744       expIWE.Init ( itIW.Value() , TopAbs_EDGE );
 745       if ( outerEM.Contains( expIWE.Current() )) {
 746         myNewWires.Append ( itIW.Value() );
 747         myInternalWL.Remove( itIW ); // == itIW.Next()
 748       }
 749       else
 750         itIW.Next();
 751     }
 752   }
 753 }
 754 //=======================================================================
 755 //function : isHole
 756 //purpose  :
 757 //=======================================================================
 758
 759 static Standard_Boolean isHole (const TopoDS_Wire& W,
 760                                 const TopoDS_Face& F)
 761 {
 762   BRep_Builder B;
 763   TopoDS_Shape newFace = F.EmptyCopied();
 764   B.Add(newFace,W.Oriented(TopAbs_FORWARD));
 765   BRepTopAdaptor_FClass2d classif (TopoDS::Face(newFace),
 766                                    Precision::PConfusion());
 767   return (classif.PerformInfinitePoint() == TopAbs_IN);
 768 }
 769
 770 //=======================================================================
 771 //function : IsInside
 772 //purpose  : check if W1 is inside W2. Suppose W2 is not a hole !!!!
 773 //=======================================================================
 774
 775 static Standard_Boolean isInside(const TopoDS_Face& F,
 776                                  const TopoDS_Wire& W1,
 777                                  const TopoDS_Wire& W2)
 778 {
 779   // make a face with wire W2
 780   BRep_Builder B;
 781   TopoDS_Shape aLocalShape = F.EmptyCopied();
 782   TopoDS_Face newFace = TopoDS::Face(aLocalShape);
 783   B.Add(newFace,W2);
 784
 785   // get any 2d point of W1
 786   TopExp_Explorer exp(W1,TopAbs_EDGE);
 787   const TopoDS_Edge& edg = TopoDS::Edge(exp.Current());
 788   Standard_Real f,l;
 789   Handle(Geom2d_Curve) C2d = BRep_Tool::CurveOnSurface(edg,F,f,l);
 790   gp_Pnt2d pt2d(C2d->Value(f));
 791
 792   BRepTopAdaptor_FClass2d classif(newFace,Precision::PConfusion());
 793   return (classif.Perform(pt2d) == TopAbs_IN);
 794 }
 795
 796 //=======================================================================
 797 //function : NewWires
 798 //purpose  : Returns the list of wires performed.
 799 //           can be an empty list.
 800 //=======================================================================
 801
 802 const TopTools_ListOfShape&  Partition_Loop2d::NewWires() const
 803 {
 804   return myNewWires;
 805 }
 806
 807 //=======================================================================
 808 //function : NewFaces
 809 //purpose  : Returns the list of faces.
 810 //Warning  : The method <WiresToFaces> as to be called before.
 811 //           can be an empty list.
 812 //=======================================================================
 813
 814 const TopTools_ListOfShape&  Partition_Loop2d::NewFaces() const
 815 {
 816   return myNewFaces;
 817 }
 818
 819 //=======================================================================
 820 //function : findEqual
 821 //purpose  : move wires form <WL> to <EqWL> pairs of wires build of the same edges
 822 //=======================================================================
 823
 824 static void findEqual (TopTools_ListOfShape& WL,
 825                        TopTools_DataMapOfShapeShape& EqWM,
 826                        const TopoDS_Face& F)
 827 {
 828   TopTools_ListIteratorOfListOfShape it1, it2;
 829   Standard_Integer i,j;
 830   TColStd_MapOfInteger IndMap;
 831   for (it1.Initialize(WL), i=1;  it1.More();  it1.Next(), i++) {
 832
 833     if (IndMap.Contains(i)) continue;
 834     const TopoDS_Wire& Wire1 = TopoDS::Wire( it1.Value());
 835
 836     for (it2.Initialize(WL), j=1;  it2.More();  it2.Next(), j++) {
 837
 838       if (j <= i || IndMap.Contains(j)) continue;
 839
 840       TopTools_IndexedMapOfShape EdgesMap;
 841       TopExp::MapShapes (Wire1, TopAbs_EDGE, EdgesMap);
 842
 843       const TopoDS_Shape& Wire2 = it2.Value();
 844       TopoDS_Iterator itE ( Wire2);
 845       for (; itE.More(); itE.Next()) {
 846         if ( !EdgesMap.Contains( itE.Value()) )
 847           break;
 848       }
 849       if (!itE.More()) { // all edges are same
 850         if (isHole( Wire1, F)) {
 851           EqWM.Bind ( Wire1, Wire2 );
 852         }
 853         else {
 854           EqWM.Bind ( Wire2, Wire1 );
 855         }
 856         IndMap.Add(i);
 857         IndMap.Add(j);
 858         break;
 859       }
 860     }
 861   }
 862   // clear WL
 863   it1.Initialize(WL);
 864   i=1;
 865   while (it1.More()) {
 866     if (IndMap.Contains(i))
 867       WL.Remove(it1); // next node becomes current and with Next() we would miss it
 868     else
 869       it1.Next();
 870     i++;
 871   }
 872 }
 873
 874 //=======================================================================
 875 //function : classify
 876 //purpose  : bind to a wire a list of internal wires
 877 //=======================================================================
 878
 879 static void classify(const TopTools_DataMapOfShapeShape& EqWM,
 880                      BRepAlgo_AsDes& OuterInner,
 881                      const TopoDS_Face& F)
 882 {
 883   TopTools_DataMapIteratorOfDataMapOfShapeShape it1, it2;
 884
 885   for (it1.Initialize(EqWM);  it1.More();  it1.Next()) {
 886     for (it2.Initialize(EqWM);  it2.More();  it2.Next()) {
 887       if (it1.Value().IsSame( it2.Value() )) continue;
 888       const TopoDS_Wire& Wire1 = TopoDS::Wire( it1.Value() );
 889       const TopoDS_Wire& Wire2 = TopoDS::Wire( it2.Value() );
 890       if (isInside(F, Wire1, Wire2))
 891         OuterInner.Add (Wire2, Wire1);
 892       else if (isInside(F, Wire2, Wire1))
 893         OuterInner.Add (Wire1, Wire2);
 894     }
 895   }
 896 }
 897 //=======================================================================
 898 //function : WiresToFaces
 899 //purpose  : Build faces from the wires result.
 900 //           <EdgeImage> serves to  find  original edge by new
 901 //           one. <Section> contains edges resulting from face
 902 //           intersections
 903 //=======================================================================
 904
 905 //#define USE_BREPFEAT_SPLITSHAPE
 906
 907 #ifdef USE_BREPFEAT_SPLITSHAPE
 908
 909 # include <BRepFeat_SplitShape.hxx>
 910 void  Partition_Loop2d::WiresToFaces(const BRepAlgo_Image& EdgeImage)
 911 #else
 912
 913 # include <BRepAlgo_FaceRestrictor.hxx>
 914 void  Partition_Loop2d::WiresToFaces(const BRepAlgo_Image& )
 915 #endif
 916 {
 917   Standard_Integer nbW = myNewWires.Extent() + myInternalWL.Extent();
 918   if (nbW==0)
 919     return;
 920
 921 #ifndef USE_BREPFEAT_SPLITSHAPE
 922
 923   // ============================================================
 924   // use BRepAlgo_FaceRestrictor to make faces
 925   // ============================================================
 926
 927   BRepAlgo_FaceRestrictor FR;
 928   FR.Init (myFace,Standard_False);
 929
 930   // FaceRestrictor is instable in rather simple cases
 931   // (ex. a single face of bellecoque.brep splited by 10 planes:
 932   // sometimes 1-2 faces are missing ).
 933   // So we use it as less as possible: no holes -> make faces by hands
 934
 935
 936   // are there holes in myFace ?
 937   Standard_Boolean hasOldHoles = Standard_False;
 938   TopoDS_Iterator itOldW (myFace);
 939   if ( itOldW.More()) {
 940     const TopoDS_Wire& FirstOldWire = TopoDS::Wire( itOldW.Value() );
 941     itOldW.Next();
 942     hasOldHoles = itOldW.More() || isHole( FirstOldWire, myFace);
 943   }
 944   if (myInternalWL.IsEmpty() && !hasOldHoles) {
 945     // each wire bounds one face
 946     BRep_Builder B;
 947     TopTools_ListIteratorOfListOfShape itNW (myNewWires);
 948     for (; itNW.More(); itNW.Next()) {
 949       TopoDS_Face NF = TopoDS::Face ( myFace.EmptyCopied() );
 950       B.Add ( NF, itNW.Value() );
 951       NF.Orientation( myFaceOri);
 952       myNewFaces.Append ( NF );
 953     }
 954     return;
 955   }
 956
 957   // FaceRestrictor can't classify wires build on all the same edges
 958   // and gives incorrect result in such cases (ex. a plane cut into 2 parts by cylinder)
 959   // We must make faces of equal wires separately. One of equal wires makes a
 960   // hole in a face and should come together with outer wires of face.
 961   // The other of a wires pair bounds a face that may have holes in turn.
 962
 963   // Find equal wires among internal wires
 964   TopTools_DataMapOfShapeShape EqWM; // key is a hole part of a pair of equal wires
 965   findEqual (myInternalWL, EqWM, myFace);
 966
 967   if (!EqWM.IsEmpty()) { // there are equal wires
 968
 969     if (hasOldHoles)
 970       myInternalWL.Append( myNewWires ); // an old wire can be inside an equal wire
 971
 972     // classify equal wire pairs
 973     BRepAlgo_AsDes OuterInner;
 974     classify (EqWM,OuterInner,myFace);
 975
 976     // make face of most internal of equal wires and its inner wires
 977     while ( !EqWM.IsEmpty()) {
 978
 979       TopTools_ListOfShape prevHolesL; // list of hole-part of previous most internal equal wires
 980
 981       // find most internal wires among pairs (key - hole, value - outer part)
 982       TopTools_DataMapIteratorOfDataMapOfShapeShape it(EqWM);
 983       for ( ; it.More(); it.Next()) {
 984
 985         TopoDS_Wire outerW = TopoDS::Wire ( it.Value() );
 986         if (  OuterInner.HasDescendant( outerW ) && // has internal
 987              ! OuterInner.Descendant( outerW ).IsEmpty() )
 988           continue;
 989
 990         FR.Add( outerW );
 991
 992         // add internal wires that are inside of outerW
 993         TopTools_ListIteratorOfListOfShape itIW (myInternalWL);
 994         while ( itIW.More()) {
 995           TopoDS_Wire IW = TopoDS::Wire ( itIW.Value() );
 996           if ( isInside (myFace, IW, outerW)) {
 997             FR.Add (IW);
 998             myInternalWL.Remove( itIW ); // == itIW.Next() !!!
 999           }
1000           else
1001             itIW.Next();
1002         }
1003
1004         // the hole-part of current pair of equal wires will be in the next new face
1005         prevHolesL.Append ( it.Key() );
1006
1007       } // Loop on map of equal pairs searching for innermost wires
1008
1009       // make faces
1010       FR.Perform();
1011       if (FR.IsDone()) {
1012         for (; FR.More(); FR.Next())
1013           myNewFaces.Append(FR.Current());
1014       }
1015
1016       FR.Clear();
1017
1018       // add hole-parts to FaceRestrictor,
1019       // remove themfrom the EqWM,
1020       // remove found wires as internal of resting classified wires
1021       Standard_Boolean clearOuterInner =  ( prevHolesL.Extent() < EqWM.Extent() );
1022       TopTools_ListIteratorOfListOfShape itPrev (prevHolesL);
1023       for (; itPrev.More(); itPrev.Next()) {
1024         TopoDS_Wire& Hole = TopoDS::Wire ( itPrev.Value() );
1025         FR.Add ( Hole );
1026         if (clearOuterInner) {
1027           const TopoDS_Wire& outerW = TopoDS::Wire ( EqWM.Find( Hole ) );
1028           // Loop on wires including outerW
1029           TopTools_ListIteratorOfListOfShape itO( OuterInner.Ascendant( outerW ));
1030           for (; itO.More(); itO.Next()) {
1031             TopTools_ListOfShape& innerL = OuterInner.ChangeDescendant( itO.Value() );
1032             TopTools_ListIteratorOfListOfShape itI (innerL);
1033             // Loop on internal wires of current including wire
1034             for (; itI.More(); itI.Next())
1035               if ( outerW.IsSame( itI.Value() )) {
1036                 innerL.Remove( itI );   break;
1037               }
1038           }
1039         }
1040         EqWM.UnBind ( Hole );
1041       }
1042
1043     } // while (!EqWM.IsEmpty)
1044
1045   } //  !EqWM.IsEmpty()
1046
1047   myNewWires.Append ( myInternalWL );
1048
1049   TopTools_ListIteratorOfListOfShape itW (myNewWires);
1050   for (; itW.More(); itW.Next()) {
1051     TopoDS_Wire& W = TopoDS::Wire ( itW.Value() );
1052     FR.Add(W);
1053   }
1054   FR.Perform();
1055   for (; FR.IsDone() && FR.More(); FR.Next())
1056     myNewFaces.Append(FR.Current());
1057
1058
1059
1060 #else // ifndef USE_BREPFEAT_SPLITSHAPE
1061
1062   // ============================================================
1063   // use BRepFeat_SplitShape to make faces
1064   // ============================================================
1065
1066   BRepFeat_SplitShape Split(myFace);
1067   TopTools_MapOfShape AddedSectionEdgesMap;
1068
1069   myNewWires.Append(myInternalWL);
1070
1071   TopTools_ListIteratorOfListOfShape it(myNewWires);
1072   for (; it.More(); it.Next()) {
1073     TopoDS_Iterator itE(it.Value());
1074     for (; itE.More(); itE.Next()) {
1075       const TopoDS_Edge& newE = TopoDS::Edge( itE.Value() );
1076       if (AddedSectionEdgesMap.Add(newE)) {
1077         if (mySectionEdges.Contains(newE))
1078           Split.Add(newE,F); // new edge on face
1079         else {
1080           const TopoDS_Edge& oldE = TopoDS::Edge( EdgeImage.ImageFrom(newE) );
1081           Split.Add(newE, oldE); // splited edge
1082         }
1083       }
1084     }
1085   }
1086   Split.Build();
1087
1088   if (Split.IsDone())
1089     myNewFaces = Split.Modified(F);
1090
1091 #endif  // ifndef USE_BREPFEAT_SPLITSHAPE
1092
1093
1094
1095 #ifdef DEB
1096   Standard_Integer nbF = myNewFaces.Extent();
1097   if (nbW != nbF)
1098     cout << "WiresToFaces(): " << nbW << " wires --> " << myNewFaces.Extent() << " faces "
1099       << endl;
1100 #endif
1101
1102   TopTools_ListIteratorOfListOfShape itNF (myNewFaces);
1103   for (; itNF.More(); itNF.Next())
1104     itNF.Value().Orientation( myFaceOri );
1105 }