src/BOPAlgo/BOPAlgo_WireSplitter_1.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15 #include <BOPAlgo_WireEdgeSet.hxx>
  16 #include <BOPAlgo_WireSplitter.hxx>
  17 #include <BOPCol_IndexedDataMapOfShapeInteger.hxx>
  18 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
  19 #include <BOPCol_ListOfShape.hxx>
  20 #include <BOPCol_MapOfShape.hxx>
  21 #include <BOPCol_SequenceOfPnt2d.hxx>
  22 #include <BOPCol_SequenceOfReal.hxx>
  23 #include <BOPCol_SequenceOfShape.hxx>
  24 #include <BOPTools_AlgoTools2D.hxx>
  25 #include <BRep_Builder.hxx>
  26 #include <BRep_Tool.hxx>
  27 #include <BRepAdaptor_Surface.hxx>
  28 #include <Geom2d_Curve.hxx>
  29 #include <Geom2d_Line.hxx>
  30 #include <Geom2dAdaptor_Curve.hxx>
  31 #include <Geom2dInt_GInter.hxx>
  32 #include <Geom_Plane.hxx>
  33 #include <Geom_RectangularTrimmedSurface.hxx>
  34 #include <Geom_Surface.hxx>
  35 #include <GeomAdaptor_Surface.hxx>
  36 #include <gp_Dir2d.hxx>
  37 #include <gp_Pnt2d.hxx>
  38 #include <gp_Vec2d.hxx>
  39 #include <IntRes2d_Domain.hxx>
  40 #include <IntRes2d_IntersectionPoint.hxx>
  41 #include <Precision.hxx>
  42 #include <TopExp.hxx>
  43 #include <TopExp_Explorer.hxx>
  44 #include <TopLoc_Location.hxx>
  45 #include <TopoDS_Edge.hxx>
  46 #include <TopoDS_Face.hxx>
  47 #include <TopoDS_Iterator.hxx>
  48 #include <TopoDS_Vertex.hxx>
  49 #include <TopoDS_Wire.hxx>
  50 #include <TopTools_ShapeMapHasher.hxx>
  51 typedef NCollection_DataMap \
  52   <TopoDS_Shape, Standard_Boolean, TopTools_ShapeMapHasher> \
  53   BOPCol_DataMapOfShapeBoolean;
  54 //
  55
  56 static
  57   Standard_Real Angle (const gp_Dir2d& aDir2D);
  58
  59 static
  60   Standard_Real Angle2D (const TopoDS_Vertex& aV,
  61                          const TopoDS_Edge& anEdge,
  62                          const TopoDS_Face& myFace,
  63                          const GeomAdaptor_Surface& aGAS,
  64                          const Standard_Boolean aFlag);
  65
  66 static
  67   void GetNextVertex(const TopoDS_Vertex& aV,
  68                      const TopoDS_Edge& aE,
  69                      TopoDS_Vertex& aV1);
  70
  71 static
  72   Standard_Real AngleIn(const TopoDS_Edge& aEIn,
  73                         const BOPAlgo_ListOfEdgeInfo& aLEInfo);
  74
  75 static
  76   Standard_Integer NbWaysOut(const BOPAlgo_ListOfEdgeInfo& aLEInfo);
  77
  78 static
  79   gp_Pnt2d Coord2dVf (const TopoDS_Edge& aE,
  80                       const TopoDS_Face& aF);
  81
  82 static
  83   gp_Pnt2d Coord2d (const TopoDS_Vertex& aV1,
  84                     const TopoDS_Edge& aE1,
  85                     const TopoDS_Face& aF);
  86
  87 static
  88   Standard_Real ClockWiseAngle(const Standard_Real aAngleIn,
  89                                const Standard_Real aAngleOut);
  90
  91 static
  92   void Path (const GeomAdaptor_Surface& aGAS,
  93              const TopoDS_Face& myFace,
  94              const TopoDS_Vertex& aVa,
  95              const TopoDS_Edge& aEOuta,
  96              BOPAlgo_EdgeInfo& anEdgeInfo,
  97              BOPCol_SequenceOfShape& aLS,
  98              BOPCol_SequenceOfShape& aVertVa,
  99              BOPCol_SequenceOfPnt2d& aCoordVa,
 100              BOPTools_ConnexityBlock& aCB,
 101              BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap,
 102              BOPCol_DataMapOfShapeBoolean aVertMap);
 103
 104 static
 105   Standard_Real Angle (const gp_Dir2d& aDir2D);
 106
 107 static
 108   Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
 109                              const GeomAdaptor_Surface& aGAS);
 110
 111
 112
 113 static
 114   Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
 115                               const GeomAdaptor_Surface& aGAS);
 116 static
 117   Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
 118                               const GeomAdaptor_Surface& aGAS);
 119
 120 static
 121   void RefineAngles(const TopoDS_Face& myFace,
 122                     const BOPCol_ListOfShape&,
 123                     BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo&);
 124
 125
 126 static
 127   void RefineAngles(const TopoDS_Vertex& ,
 128                   const TopoDS_Face& ,
 129                   const BOPCol_MapOfShape& ,
 130                   BOPAlgo_ListOfEdgeInfo& );
 131
 132 static
 133   Standard_Boolean RefineAngle2D(const TopoDS_Vertex& ,
 134                                  const TopoDS_Edge& ,
 135                                  const TopoDS_Face& ,
 136                                  const Standard_Real ,
 137                                  const Standard_Real ,
 138                                  Standard_Real& );
 139
 140 //=======================================================================
 141 //function : SplitBlock
 142 //purpose  :
 143 //=======================================================================
 144 void BOPAlgo_WireSplitter::SplitBlock(const TopoDS_Face& myFace,
 145                                       BOPTools_ConnexityBlock& aCB)
 146 {
 147   Standard_Boolean bNothingToDo, bIsClosed, bIsIN;
 148   Standard_Integer aIx, aNb, i, aCntIn, aCntOut;
 149   Standard_Real aAngle;
 150   TopAbs_Orientation aOr;
 151   TopoDS_Iterator aItS;
 152   TopoDS_Vertex aVV;
 153   TopoDS_Shape aV1;
 154   BOPCol_ListIteratorOfListOfShape aIt;
 155   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
 156   //
 157   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo mySmartMap(100);
 158   BOPCol_DataMapOfShapeBoolean aVertMap;
 159   //
 160   const BOPCol_ListOfShape& myEdges=aCB.Shapes();
 161   //
 162   // 1.Filling mySmartMap
 163   BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane(myEdges, myFace);
 164   //
 165   aIt.Initialize(myEdges);
 166   for(; aIt.More(); aIt.Next()) {
 167     const TopoDS_Edge& aE=(*(TopoDS_Edge *)&aIt.Value());
 168     if (!BOPTools_AlgoTools2D::HasCurveOnSurface (aE, myFace)) {
 169       continue;
 170     }
 171     //
 172     bIsClosed = BRep_Tool::Degenerated(aE) ||
 173                 BRep_Tool::IsClosed(aE, myFace);
 174     //
 175     aItS.Initialize(aE);
 176     for(i = 0; aItS.More(); aItS.Next(), ++i) {
 177       const TopoDS_Shape& aV = aItS.Value();
 178       aIx = mySmartMap.FindIndex(aV);
 179       if (!aIx) {
 180         BOPAlgo_ListOfEdgeInfo aLEIx;
 181         aIx = mySmartMap.Add(aV, aLEIx);
 182       }
 183       //
 184       BOPAlgo_ListOfEdgeInfo& aLEI = mySmartMap(aIx);
 185       BOPAlgo_EdgeInfo aEI;
 186       //
 187       aEI.SetEdge(aE);
 188       aOr = aV.Orientation();
 189       bIsIN = (aOr == TopAbs_REVERSED);
 190       aEI.SetInFlag(bIsIN);
 191       aLEI.Append(aEI);
 192       //
 193       if (!i) {
 194         aV1 = aV;
 195       } else {
 196         bIsClosed = bIsClosed || aV1.IsSame(aV);
 197       }
 198       //
 199       if (aVertMap.IsBound(aV)) {
 200         if (bIsClosed) {
 201           aVertMap.ChangeFind(aV) = bIsClosed;
 202         }
 203       } else {
 204         aVertMap.Bind(aV, bIsClosed);
 205       }
 206     }
 207   }
 208   //
 209   aNb=mySmartMap.Extent();
 210   //
 211   bNothingToDo=Standard_True;
 212   for (i=1; i<=aNb; i++) {
 213     aCntIn=0;
 214     aCntOut=0;
 215     const BOPAlgo_ListOfEdgeInfo& aLEInfo= mySmartMap(i);
 216     BOPAlgo_ListIteratorOfListOfEdgeInfo anIt(aLEInfo);
 217     for (; anIt.More(); anIt.Next()) {
 218       const BOPAlgo_EdgeInfo& aEI=anIt.Value();
 219       if (aEI.IsIn()) {
 220         aCntIn++;
 221       }
 222       else {
 223         aCntOut++;
 224       }
 225     }
 226     if (aCntIn!=1 || aCntOut!=1) {
 227       bNothingToDo=Standard_False;
 228       break;
 229     }
 230   }
 231   //
 232   // Each vertex has one edge In and one - Out. Good. But it is not enought
 233   // to consider that nothing to do with this. We must check edges on TShape
 234   // coinsidence. If there are such edges there is something to do with.
 235   if (bNothingToDo) {
 236     Standard_Integer aNbE, aNbMapEE;
 237     Standard_Boolean bFlag;
 238     //
 239     BOPCol_IndexedDataMapOfShapeListOfShape aMapEE(100);
 240     aNbE=myEdges.Extent();
 241     //
 242     aIt.Initialize(myEdges);
 243     for (; aIt.More(); aIt.Next()) {
 244       const TopoDS_Shape& aE = aIt.Value();
 245       if (!aMapEE.Contains(aE)) {
 246         BOPCol_ListOfShape aLEx;
 247         aLEx.Append(aE);
 248         aMapEE.Add(aE, aLEx);
 249       }
 250       else {
 251         BOPCol_ListOfShape& aLEx=aMapEE.ChangeFromKey(aE);
 252         aLEx.Append(aE);
 253       }
 254     }
 255     //
 256     bFlag=Standard_True;
 257     aNbMapEE=aMapEE.Extent();
 258     for (i=1; i<=aNbMapEE; ++i) {
 259       const BOPCol_ListOfShape& aLEx=aMapEE(i);
 260       aNbE=aLEx.Extent();
 261       if (aNbE==1) {// usual case
 262         continue;
 263       }
 264       else if (aNbE==2){
 265         const TopoDS_Shape& aE1=aLEx.First();
 266         const TopoDS_Shape& aE2=aLEx.Last();
 267         if (aE1.IsSame(aE2)) {
 268           bFlag=Standard_False;
 269           break;
 270         }
 271       }
 272       else {
 273         bFlag=Standard_False;
 274         break;
 275       }
 276     }
 277     bNothingToDo=bNothingToDo && bFlag;
 278   } // if (bNothingToDo) {
 279   if (bNothingToDo) {
 280     TopoDS_Wire aW;
 281     //
 282     BOPCol_ListOfShape& aLECB=aCB.ChangeShapes();
 283     BOPAlgo_WireSplitter::MakeWire(aLECB, aW);
 284     BOPCol_ListOfShape& aLoops=aCB.ChangeLoops();
 285     aLoops.Append(aW);
 286     //
 287     return;
 288   }
 289   //
 290   // 3. Angles in mySmartMap
 291   BRepAdaptor_Surface aBAS(myFace);
 292   const GeomAdaptor_Surface& aGAS=aBAS.Surface();
 293   //
 294   for (i=1; i<=aNb; i++) {
 295     const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&mySmartMap.FindKey(i)));
 296     const BOPAlgo_ListOfEdgeInfo& aLEI= mySmartMap(i);
 297
 298     aItLEI.Initialize(aLEI);
 299     for (; aItLEI.More(); aItLEI.Next()) {
 300       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 301       const TopoDS_Edge& aE=aEI.Edge();
 302       //
 303       aVV = aV;
 304       bIsIN = aEI.IsIn();
 305       aOr = bIsIN ? TopAbs_REVERSED : TopAbs_FORWARD;
 306       aVV.Orientation(aOr);
 307       aAngle = Angle2D(aVV, aE, myFace, aGAS, bIsIN);
 308       aEI.SetAngle(aAngle);
 309     }
 310   }// for (i=1; i<=aNb; i++) {
 311   //
 312   //Theme: The treatment p-curves convergent in node.
 313   //The refining the angles of p-curves taking into account
 314   //bounging curves if exist.
 315   RefineAngles(myFace, myEdges, mySmartMap);
 316   //
 317   // 4. Do
 318   //
 319   Standard_Boolean bIsOut, bIsNotPassed;
 320   BOPCol_SequenceOfShape aLS, aVertVa;
 321   BOPCol_SequenceOfPnt2d aCoordVa;
 322   //
 323   for (i=1; i<=aNb; ++i) {
 324     const TopoDS_Vertex& aVa=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i)));
 325     const BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
 326     aItLEI.Initialize(aLEI);
 327     for (; aItLEI.More(); aItLEI.Next()) {
 328       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 329       const TopoDS_Edge& aEOuta=aEI.Edge();
 330       //
 331       bIsOut=!aEI.IsIn();
 332       bIsNotPassed=!aEI.Passed();
 333       if (bIsOut && bIsNotPassed) {
 334         //
 335         aLS.Clear();
 336         aVertVa.Clear();
 337         aCoordVa.Clear();
 338         //
 339         Path(aGAS, myFace, aVa, aEOuta, aEI, aLS,
 340              aVertVa, aCoordVa, aCB, mySmartMap, aVertMap);
 341       }
 342     }
 343   }// for (i=1; i<=aNb; ++i) {
 344 }
 345 //=======================================================================
 346 // function: Path
 347 // purpose:
 348 //=======================================================================
 349 void Path (const GeomAdaptor_Surface& aGAS,
 350            const TopoDS_Face& myFace,
 351            const TopoDS_Vertex& aVFirst,
 352            const TopoDS_Edge& aEFirst,
 353            BOPAlgo_EdgeInfo& aEIFirst,
 354            BOPCol_SequenceOfShape& aLS,
 355            BOPCol_SequenceOfShape& aVertVa,
 356            BOPCol_SequenceOfPnt2d& aCoordVa,
 357            BOPTools_ConnexityBlock& aCB,
 358            BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap,
 359            BOPCol_DataMapOfShapeBoolean aVertMap)
 360
 361 {
 362   Standard_Integer i, j, aNb, aNbj;
 363   Standard_Real anAngleIn, anAngleOut, anAngle, aMinAngle;
 364   Standard_Real aTol2D, aTol2D2, aD2, aTwoPI;
 365   Standard_Boolean anIsSameV2d, anIsSameV, anIsFound, anIsOut, anIsNotPassed;
 366   Standard_Boolean bIsClosed;
 367   TopoDS_Vertex aVa, aVb;
 368   TopoDS_Edge aEOuta;
 369   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
 370   //
 371   aVa = aVFirst;
 372   aEOuta = aEFirst;
 373   BOPAlgo_EdgeInfo* anEdgeInfo = &aEIFirst;
 374   //
 375   aTwoPI = M_PI + M_PI;
 376   //
 377   // append block
 378   //
 379   for (;;) {
 380     // Do not escape through edge from which you enter
 381     aNb=aLS.Length();
 382     if (aNb==1) {
 383       const TopoDS_Shape& anEPrev=aLS(aNb);
 384       if (anEPrev.IsSame(aEOuta)) {
 385         return;
 386       }
 387     }
 388     //
 389     anEdgeInfo->SetPassed(Standard_True);
 390     aLS.Append(aEOuta);
 391     aVertVa.Append(aVa);
 392
 393     TopoDS_Vertex pVa=aVa;
 394     pVa.Orientation(TopAbs_FORWARD);
 395     gp_Pnt2d aPa=Coord2d(pVa, aEOuta, myFace);
 396     aCoordVa.Append(aPa);
 397
 398     GetNextVertex (pVa, aEOuta, aVb);
 399
 400     gp_Pnt2d aPb=Coord2d(aVb, aEOuta, myFace);
 401
 402     const BOPAlgo_ListOfEdgeInfo& aLEInfo=mySmartMap.FindFromKey(aVb);
 403     //
 404     aTol2D = 2.*Tolerance2D(aVb, aGAS);
 405     aTol2D2 = aTol2D * aTol2D;
 406     //
 407     bIsClosed = aVertMap.Find(aVb);
 408     //
 409     aNb=aLS.Length();
 410     if (aNb>0) {
 411       //
 412       BOPCol_ListOfShape aBuf;
 413       //
 414       for (i=aNb; i>0; --i) {
 415         const TopoDS_Shape& aVPrev=aVertVa(i);
 416         const gp_Pnt2d& aPaPrev=aCoordVa(i);
 417         const TopoDS_Shape& aEPrev=aLS(i);
 418
 419         aBuf.Append(aEPrev);
 420
 421         anIsSameV = aVPrev.IsSame(aVb);
 422         anIsSameV2d = anIsSameV;
 423         if (anIsSameV) {
 424           if(bIsClosed) {
 425             aD2 = aPaPrev.SquareDistance(aPb);
 426             anIsSameV2d = aD2 < aTol2D2;
 427             if (anIsSameV2d) {
 428               Standard_Real udist = fabs(aPaPrev.X() - aPb.X());
 429               Standard_Real vdist = fabs(aPaPrev.Y() - aPb.Y());
 430               Standard_Real aTolU = 2.*UTolerance2D(aVb, aGAS);
 431               Standard_Real aTolV = 2.*VTolerance2D(aVb, aGAS);
 432               //
 433               if((udist > aTolU) || (vdist > aTolV)) {
 434                 anIsSameV2d = Standard_False;
 435               }
 436             }
 437           }
 438         }//if (anIsSameV) {
 439         //
 440         if (anIsSameV && anIsSameV2d) {
 441           Standard_Integer iPriz;
 442           iPriz=1;
 443           if (aBuf.Extent()==2) {
 444             if(aBuf.First().IsSame(aBuf.Last())) {
 445               iPriz=0;
 446             }
 447           }
 448           if (iPriz) {
 449             TopoDS_Wire aW;
 450             BOPAlgo_WireSplitter::MakeWire(aBuf, aW);
 451             aCB.ChangeLoops().Append(aW);
 452           }
 453           //
 454           aNbj=i-1;
 455           if (aNbj<1) {
 456             //
 457             aLS.Clear();
 458             aVertVa.Clear();
 459             aCoordVa.Clear();
 460             //
 461             return;
 462           }
 463           //
 464           BOPCol_SequenceOfShape aLSt, aVertVat;
 465           BOPCol_SequenceOfPnt2d aCoordVat;
 466           //
 467           aVb=(*(TopoDS_Vertex *)(&aVertVa(i)));
 468           //
 469           for (j=1; j<=aNbj; ++j) {
 470             aLSt.Append(aLS(j));
 471             aVertVat.Append(aVertVa(j));
 472             aCoordVat.Append(aCoordVa(j));
 473           }
 474           //
 475           aLS.Clear();
 476           aVertVa.Clear();
 477           aCoordVa.Clear();
 478
 479           aLS=aLSt;
 480           aVertVa=aVertVat;
 481           aCoordVa=aCoordVat;
 482           //
 483           break;
 484         }
 485       }
 486     }
 487     //
 488     // aEOutb
 489     BOPAlgo_EdgeInfo *pEdgeInfo=NULL;
 490     //
 491     anAngleIn = AngleIn(aEOuta, aLEInfo);
 492     aMinAngle = 100.;
 493     anIsFound = Standard_False;
 494     Standard_Integer aCurIndexE = 0;
 495     anIt.Initialize(aLEInfo);
 496     for (; anIt.More(); anIt.Next()) {
 497       BOPAlgo_EdgeInfo& anEI=anIt.ChangeValue();
 498       const TopoDS_Edge& aE=anEI.Edge();
 499       anIsOut=!anEI.IsIn();
 500       anIsNotPassed=!anEI.Passed();
 501       //
 502       if (anIsOut && anIsNotPassed) {
 503         aCurIndexE++;
 504         //
 505         // Is there one way to go out of the vertex
 506         // we have to use it only.
 507         Standard_Integer iCnt;
 508         iCnt=NbWaysOut (aLEInfo);
 509         //
 510         if (!iCnt) {
 511           // no way to go . (Error)
 512           return;
 513         }
 514         //
 515         if (iCnt==1) {
 516           // the one and only way to go out .
 517           pEdgeInfo=&anEI;
 518           anIsFound=Standard_True;
 519           break;
 520         }
 521         //
 522         if (aE.IsSame(aEOuta)) {
 523           anAngle = aTwoPI;
 524         } else {
 525           //check 2d distance
 526           if (bIsClosed) {
 527             gp_Pnt2d aP2Dx;
 528             //
 529             aP2Dx = Coord2dVf(aE, myFace);
 530             //
 531             aD2 = aP2Dx.SquareDistance(aPb);
 532             if (aD2 > aTol2D2){
 533               continue;
 534             }
 535           }
 536           //
 537           // Look for minimal angle and make the choice.
 538           anAngleOut=anEI.Angle();
 539           anAngle=ClockWiseAngle(anAngleIn, anAngleOut);
 540         }
 541         if (anAngle < aMinAngle) {
 542           aMinAngle=anAngle;
 543           pEdgeInfo=&anEI;
 544           anIsFound=Standard_True;
 545         }
 546       }
 547     } // for (; anIt.More(); anIt.Next())
 548     //
 549     if (!anIsFound) {
 550       // no way to go . (Error)
 551       return;
 552     }
 553     //
 554     aVa = aVb;
 555     aEOuta = pEdgeInfo->Edge();
 556     anEdgeInfo = pEdgeInfo;
 557   }
 558 }
 559 //=======================================================================
 560 // function:  ClockWiseAngle
 561 // purpose:
 562 //=======================================================================
 563  Standard_Real ClockWiseAngle(const Standard_Real aAngleIn,
 564                               const Standard_Real aAngleOut)
 565 {
 566   Standard_Real aTwoPi=M_PI+M_PI;
 567   Standard_Real dA, A1, A2, AIn, AOut ;
 568
 569   AIn=aAngleIn;
 570   AOut=aAngleOut;
 571   if (AIn >= aTwoPi) {
 572     AIn=AIn-aTwoPi;
 573   }
 574
 575   if (AOut >= aTwoPi) {
 576     AOut=AOut-aTwoPi;
 577   }
 578
 579   A1=AIn+M_PI;
 580
 581   if (A1 >= aTwoPi) {
 582     A1=A1-aTwoPi;
 583   }
 584
 585   A2=AOut;
 586
 587   dA=A1-A2;
 588   if (dA <= 0.) {
 589     dA=aTwoPi+dA;
 590   }
 591   //xx
 592   //else if (dA <= 1.e-15) {
 593   else if (dA <= 1.e-14) {
 594     dA=aTwoPi;
 595   }
 596   return dA;
 597 }
 598 //=======================================================================
 599 // function:  Coord2d
 600 // purpose:
 601 //=======================================================================
 602  gp_Pnt2d Coord2d (const TopoDS_Vertex& aV1,
 603                    const TopoDS_Edge& aE1,
 604                    const TopoDS_Face& aF)
 605 {
 606   Standard_Real aT, aFirst, aLast;
 607   Handle(Geom2d_Curve) aC2D;
 608   gp_Pnt2d aP2D1;
 609   //
 610   aT=BRep_Tool::Parameter (aV1, aE1, aF);
 611   aC2D=BRep_Tool::CurveOnSurface(aE1, aF, aFirst, aLast);
 612   aC2D->D0 (aT, aP2D1);
 613   //
 614   return aP2D1;
 615 }
 616 //=======================================================================
 617 // function:  Coord2dVf
 618 // purpose:
 619 //=======================================================================
 620  gp_Pnt2d Coord2dVf (const TopoDS_Edge& aE,
 621                      const TopoDS_Face& aF)
 622 {
 623   Standard_Real aCoord=99.;
 624   gp_Pnt2d aP2D1(aCoord, aCoord);
 625   TopoDS_Iterator aIt;
 626   //
 627   aIt.Initialize(aE);
 628   for (; aIt.More(); aIt.Next()) {
 629     const TopoDS_Shape& aVx=aIt.Value();
 630     if (aVx.Orientation()==TopAbs_FORWARD) {
 631
 632       const TopoDS_Vertex& aVxx=(*(TopoDS_Vertex *)(&aVx));// TopoDS::Vertex(aVx);
 633       aP2D1=Coord2d(aVxx, aE, aF);
 634       return aP2D1;
 635     }
 636   }
 637   return aP2D1;
 638 }
 639
 640 //=======================================================================
 641 // function: NbWaysOut
 642 // purpose:
 643 //=======================================================================
 644 Standard_Integer NbWaysOut(const BOPAlgo_ListOfEdgeInfo& aLEInfo)
 645 {
 646   Standard_Boolean bIsOut, bIsNotPassed;
 647   Standard_Integer iCnt=0;
 648   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
 649   //
 650   anIt.Initialize(aLEInfo);
 651   for (; anIt.More(); anIt.Next()) {
 652     const BOPAlgo_EdgeInfo& anEI=anIt.Value();
 653     //
 654     bIsOut=!anEI.IsIn();
 655     bIsNotPassed=!anEI.Passed();
 656     if (bIsOut && bIsNotPassed) {
 657       iCnt++;
 658     }
 659   }
 660   return iCnt;
 661 }
 662
 663 //=======================================================================
 664 // function:  AngleIn
 665 // purpose:
 666 //=======================================================================
 667  Standard_Real AngleIn(const TopoDS_Edge& aEIn,
 668                        const BOPAlgo_ListOfEdgeInfo& aLEInfo)
 669 {
 670   Standard_Real anAngleIn;
 671   Standard_Boolean anIsIn;
 672   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
 673
 674   anIt.Initialize(aLEInfo);
 675   for (; anIt.More(); anIt.Next()) {
 676     const BOPAlgo_EdgeInfo& anEdgeInfo=anIt.Value();
 677     const TopoDS_Edge& aE=anEdgeInfo.Edge();
 678     anIsIn=anEdgeInfo.IsIn();
 679     //
 680     if (anIsIn && aE==aEIn) {
 681       anAngleIn=anEdgeInfo.Angle();
 682       return anAngleIn;
 683     }
 684   }
 685   anAngleIn=0.;
 686   return anAngleIn;
 687 }
 688 //=======================================================================
 689 // function: GetNextVertex
 690 // purpose:
 691 //=======================================================================
 692  void GetNextVertex(const TopoDS_Vertex& aV,
 693                     const TopoDS_Edge& aE,
 694                     TopoDS_Vertex& aV1)
 695 {
 696   TopoDS_Iterator aIt;
 697   //
 698   aIt.Initialize(aE);
 699   for (; aIt.More(); aIt.Next()) {
 700     const TopoDS_Shape& aVx=aIt.Value();
 701     if (!aVx.IsEqual(aV)) {
 702       aV1=(*(TopoDS_Vertex *)(&aVx));
 703       return ;
 704     }
 705   }
 706   aV1=aV;
 707 }
 708 //=======================================================================
 709 // function: Angle2D
 710 // purpose:
 711 //=======================================================================
 712   Standard_Real Angle2D (const TopoDS_Vertex& aV,
 713                          const TopoDS_Edge& anEdge,
 714                          const TopoDS_Face& myFace,
 715                          const GeomAdaptor_Surface& aGAS,
 716                          const Standard_Boolean bIsIN)
 717 {
 718   Standard_Real aFirst, aLast, aToler, dt, aTV, aTV1, anAngle, aTX;
 719   gp_Pnt2d aPV, aPV1;
 720   gp_Vec2d aV2D;
 721   Handle(Geom2d_Curve) aC2D;
 722   //
 723   aTV=BRep_Tool::Parameter (aV, anEdge, myFace);
 724   if (Precision::IsInfinite(aTV)) {
 725     return 0.;
 726   }
 727   //
 728   BOPTools_AlgoTools2D::CurveOnSurface (anEdge, myFace, aC2D,
 729                                         aFirst, aLast, aToler);
 730   dt=2.*Tolerance2D(aV, aGAS);
 731   //
 732   //for case chl/927/r9
 733   aTX=0.05*(aLast - aFirst);//aTX=0.25*(aLast - aFirst);
 734   if (aTX < 5.e-5) {
 735     aTX = 5.e-5;
 736   }
 737   if(dt > aTX) {
 738     // to save direction of the curve as much as it possible
 739     // in the case of big tolerances
 740     dt = aTX;
 741   }
 742   //
 743   GeomAbs_CurveType aType;
 744   Geom2dAdaptor_Curve aGAC2D(aC2D);
 745   aType=aGAC2D.GetType();
 746   if (aType==GeomAbs_BSplineCurve ||
 747       aType==GeomAbs_BezierCurve) {
 748     dt=1.1*dt;
 749   }
 750   if (fabs (aTV-aFirst) < fabs(aTV - aLast)) {
 751     aTV1=aTV + dt;
 752   }
 753   else {
 754     aTV1=aTV - dt;
 755   }
 756   //
 757   if (aType==GeomAbs_Circle) {
 758     Standard_Real aTM;
 759     TopAbs_Orientation aOrE;
 760     gp_Pnt2d aPM;
 761     //
 762     aTM=0.5*(aTV1+aTV);
 763     //
 764     aGAC2D.D1(aTM, aPM, aV2D);
 765     aOrE=anEdge.Orientation();
 766     if (aOrE==TopAbs_REVERSED) {
 767       aV2D.Reverse();
 768     }
 769   }
 770   else {
 771     aGAC2D.D0 (aTV1, aPV1);
 772     aGAC2D.D0 (aTV, aPV);
 773     //
 774     aV2D = bIsIN ? gp_Vec2d(aPV1, aPV) : gp_Vec2d(aPV, aPV1);
 775   }
 776   //
 777   gp_Dir2d aDir2D(aV2D);
 778   anAngle=Angle(aDir2D);
 779   //
 780   return anAngle;
 781 }
 782 //=======================================================================
 783 // function: Angle
 784 // purpose:
 785 //=======================================================================
 786 Standard_Real Angle (const gp_Dir2d& aDir2D)
 787 {
 788   gp_Dir2d aRefDir(1., 0.);
 789   Standard_Real anAngle;
 790
 791   anAngle = aRefDir.Angle(aDir2D);
 792   if (anAngle < 0.)
 793     anAngle += M_PI + M_PI;
 794   return anAngle;
 795 }
 796 //=======================================================================
 797 // function:  Tolerance2D
 798 // purpose:
 799 //=======================================================================
 800  Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
 801                             const GeomAdaptor_Surface& aGAS)
 802 {
 803   Standard_Real aTol2D, anUr, aVr, aTolV3D;
 804   GeomAbs_SurfaceType aType;
 805   //
 806   aType=aGAS.GetType();
 807   aTolV3D=BRep_Tool::Tolerance(aV);
 808
 809   anUr=aGAS.UResolution(aTolV3D);
 810   aVr =aGAS.VResolution(aTolV3D);
 811   aTol2D=(aVr>anUr) ? aVr : anUr;
 812   //
 813   if (aTol2D < aTolV3D) {
 814     aTol2D=aTolV3D;
 815   }
 816   if (aType==GeomAbs_BSplineSurface) {
 817     aTol2D=1.1*aTol2D;
 818   }
 819   //
 820   return aTol2D;
 821 }
 822
 823 //=======================================================================
 824 //function : UTolerance2D
 825 //purpose  :
 826 //=======================================================================
 827 Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
 828                             const GeomAdaptor_Surface& aGAS)
 829 {
 830   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
 831   const Standard_Real anUr = aGAS.UResolution(aTolV3D);
 832   //
 833   return anUr;
 834 }
 835
 836 //=======================================================================
 837 //function : VTolerance2D
 838 //purpose  :
 839 //=======================================================================
 840 Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
 841                             const GeomAdaptor_Surface& aGAS)
 842 {
 843   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
 844   const Standard_Real anVr = aGAS.VResolution(aTolV3D);
 845   //
 846   return anVr;
 847 }
 848
 849 //=======================================================================
 850 //function : RefineAngles
 851 //purpose  :
 852 //=======================================================================
 853 void RefineAngles(const TopoDS_Face& myFace,
 854                   const BOPCol_ListOfShape& myEdges,
 855                   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap)
 856 {
 857   Standard_Integer aNb, i;
 858   BOPCol_IndexedDataMapOfShapeInteger aMSI;
 859   BOPCol_MapOfShape aMBE;
 860   BOPCol_ListIteratorOfListOfShape aIt;
 861   //
 862   // 1. Boundary Edges
 863   aIt.Initialize(myEdges);
 864   for(; aIt.More(); aIt.Next()) {
 865     const TopoDS_Shape& aE=aIt.Value();
 866     if(aMSI.Contains(aE)) {
 867       Standard_Integer& iCnt = aMSI.ChangeFromKey(aE);
 868       ++iCnt;
 869     }
 870     else {
 871       Standard_Integer iCnt = 1;
 872       aMSI.Add(aE, iCnt);
 873     }
 874   }
 875   //
 876   aNb = aMSI.Extent();
 877   for (i = 1; i <= aNb; ++i) {
 878     Standard_Integer iCnt = aMSI(i);
 879     if (iCnt == 1) {
 880       const TopoDS_Shape& aE = aMSI.FindKey(i);
 881       aMBE.Add(aE);
 882     }
 883   }
 884   //
 885   aMSI.Clear();
 886   //
 887   aNb = mySmartMap.Extent();
 888   for (i = 1; i <= aNb; ++i) {
 889     const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&mySmartMap.FindKey(i));
 890     BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
 891     //
 892     RefineAngles(aV, myFace, aMBE, aLEI);
 893   }
 894 }
 895 //=======================================================================
 896 typedef NCollection_DataMap \
 897   <TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> \
 898    BOPCol_DataMapOfShapeReal;
 899 typedef BOPCol_DataMapOfShapeReal::Iterator \
 900   BOPCol_DataMapIteratorOfDataMapOfShapeReal;
 901 //
 902 //=======================================================================
 903 //function : RefineAngles
 904 //purpose  :
 905 //=======================================================================
 906 void RefineAngles(const TopoDS_Vertex& aV,
 907                   const TopoDS_Face& myFace,
 908                   const BOPCol_MapOfShape& aMBE,
 909                   BOPAlgo_ListOfEdgeInfo& aLEI)
 910 {
 911   Standard_Boolean bIsIn, bIsBoundary, bRefined;
 912   Standard_Integer iCntBnd, iCntInt;
 913   Standard_Real aA, aA1, aA2;
 914   BOPCol_DataMapOfShapeReal aDMSR;
 915   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
 916   //
 917   aA1=0.;
 918   aA2=0.;
 919   iCntBnd=0;
 920   iCntInt=0;
 921   aItLEI.Initialize(aLEI);
 922   for (; aItLEI.More(); aItLEI.Next()) {
 923     BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 924     const TopoDS_Edge& aE=aEI.Edge();
 925     bIsIn=aEI.IsIn();
 926     aA=aEI.Angle();
 927     //
 928     if (aMBE.Contains(aE)) {
 929       ++iCntBnd;
 930       if (!bIsIn) {
 931         aA1=aA;
 932       }
 933       else {
 934         aA2=aA+M_PI;
 935       }
 936     }
 937     else {
 938       ++iCntInt;
 939     }
 940   }
 941   //
 942   if (iCntBnd!=2) {
 943     return;
 944   }
 945   //
 946   aItLEI.Initialize(aLEI);
 947   for (; aItLEI.More(); aItLEI.Next()) {
 948     BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 949     const TopoDS_Edge& aE=aEI.Edge();
 950     //
 951     bIsBoundary=aMBE.Contains(aE);
 952     bIsIn=aEI.IsIn();
 953     if (bIsBoundary || bIsIn) {
 954       continue;
 955     }
 956     //
 957     aA=aEI.Angle();
 958     if (aA>aA1 && aA<aA2) {
 959       continue;
 960     }
 961     //
 962     bRefined=RefineAngle2D(aV, aE, myFace, aA1, aA2, aA);
 963     if (bRefined) {
 964       aDMSR.Bind(aE, aA);
 965     }
 966     else if (iCntInt == 2) {
 967       aA = (aA <= aA1) ? (aA1 + Precision::Angular()) :
 968                          (aA2 - Precision::Angular());
 969       aDMSR.Bind(aE, aA);
 970     }
 971   }
 972
 973   if (aDMSR.IsEmpty()) {
 974     return;
 975   }
 976   //
 977   // update Angles
 978   aItLEI.Initialize(aLEI);
 979   for (; aItLEI.More(); aItLEI.Next()) {
 980     BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 981     const TopoDS_Edge& aE=aEI.Edge();
 982     //
 983     bIsIn=aEI.IsIn();
 984     if (!aDMSR.IsBound(aE)) {
 985       continue;
 986     }
 987     //
 988     aA=aDMSR.Find(aE);
 989     if (bIsIn) {
 990       aA=aA+M_PI;
 991     }
 992     //
 993     aEI.SetAngle(aA);
 994   }
 995 }
 996 //=======================================================================
 997 //function : RefineAngle2D
 998 //purpose  :
 999 //=======================================================================
1000 Standard_Boolean RefineAngle2D(const TopoDS_Vertex& aV,
1001                                const TopoDS_Edge& aE,
1002                                const TopoDS_Face& myFace,
1003                                const Standard_Real aA1,
1004                                const Standard_Real aA2,
1005                                Standard_Real& aA)
1006 {
1007   Standard_Boolean bRet;
1008   Standard_Integer i, j, aNbP;
1009   Standard_Real aTV, aTol, aT1, aT2, dT, aAngle, aT, aTOp;
1010   Standard_Real aTolInt, aAi, aXi, aYi, aT1j, aT2j, aT1max, aT2max, aCf;
1011   gp_Pnt2d aPV, aP, aP1, aP2;
1012   Handle(Geom2d_Curve) aC2D;
1013   Handle(Geom2d_Line) aLi;
1014   Geom2dAdaptor_Curve aGAC1, aGAC2;
1015   Geom2dInt_GInter aGInter;
1016   IntRes2d_Domain aDomain1, aDomain2;
1017   //
1018   bRet=Standard_True;
1019   aCf=0.01;
1020   aTolInt=1.e-10;
1021   //
1022   BOPTools_AlgoTools2D::CurveOnSurface(aE, myFace, aC2D, aT1, aT2, aTol);
1023   aGAC1.Load(aC2D, aT1, aT2);
1024   //
1025   aTV=BRep_Tool::Parameter (aV, aE, myFace);
1026   aGAC1.D0(aTV, aPV);
1027   //
1028   aTOp = (fabs(aTV-aT1) < fabs(aTV-aT2)) ? aT2 : aT1;
1029   //
1030   aGAC1.D0(aT1, aP1);
1031   aGAC1.D0(aT2, aP2);
1032   aDomain1.SetValues(aP1, aT1, aTolInt, aP2, aT2, aTolInt);
1033   //
1034   for (i=0; i<2; ++i) {
1035     aAi=(!i) ? aA1 : aA2;
1036     aXi=cos(aAi);
1037     aYi=sin(aAi);
1038     gp_Dir2d aDiri(aXi, aYi);
1039     aLi=new Geom2d_Line(aPV, aDiri);
1040     //
1041     aGAC2.Load(aLi);
1042     //
1043     aGInter.Perform(aGAC1, aDomain1, aGAC2, aDomain2, aTolInt, aTolInt);
1044     if (!aGInter.IsDone()) {
1045       continue;
1046     }
1047     //
1048     aNbP=aGInter.NbPoints();
1049     if (aNbP<2) {
1050       continue;
1051     }
1052     //
1053     aT1max=aTV;
1054     aT2max=-1.;
1055     for (j=1; j<=aNbP; ++j) {
1056       const IntRes2d_IntersectionPoint& aIPj=aGInter.Point(j);
1057       aT1j=aIPj.ParamOnFirst();
1058       aT2j=aIPj.ParamOnSecond();
1059       //
1060       if (aT2j > aT2max) {
1061         aT2max=aT2j;
1062         aT1max=aT1j;
1063       }
1064     }
1065     //
1066     dT = aTOp - aT1max;
1067     if (Abs(dT) < aTolInt) {
1068       continue;
1069     }
1070     //
1071     aT=aT1max + aCf*dT;
1072     aGAC1.D0(aT, aP);
1073     gp_Vec2d aV2D(aPV, aP);
1074     gp_Dir2d aDir2D(aV2D);
1075     //
1076     aAngle=Angle(aDir2D);
1077     if (aAngle>aA1 && aAngle<aA2) {
1078       aA=aAngle;
1079       return bRet;
1080     }
1081   }// for (i=0; i<2; ++i) {
1082   return !bRet;
1083 }