src/PARTITION/Partition_Loop2d.cxx

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