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