src/PARTITION/Partition_Loop2d.cxx

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