src/PARTITION/Partition_Loop2d.cxx

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