src/BOPAlgo/BOPAlgo_WireSplitter_1.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2012 OPEN CASCADE SAS
   3 //
   4 // The content of this file is subject to the Open CASCADE Technology Public
   5 // License Version 6.5 (the "License"). You may not use the content of this file
   6 // except in compliance with the License. Please obtain a copy of the License
   7 // at http://www.opencascade.org and read it completely before using this file.
   8 //
   9 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  10 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  11 //
  12 // The Original Code and all software distributed under the License is
  13 // distributed on an "AS IS" basis, without warranty of any kind, and the
  14 // Initial Developer hereby disclaims all such warranties, including without
  15 // limitation, any warranties of merchantability, fitness for a particular
  16 // purpose or non-infringement. Please see the License for the specific terms
  17 // and conditions governing the rights and limitations under the License.
  18
  19 #include <BOPAlgo_WireSplitter.ixx>
  20
  21 #include <Precision.hxx>
  22
  23 #include <gp_Pnt2d.hxx>
  24 #include <gp_Vec2d.hxx>
  25 #include <gp_Dir2d.hxx>
  26 #include <Geom2d_Curve.hxx>
  27 #include <GeomAdaptor_Surface.hxx>
  28
  29 #include <TopoDS_Edge.hxx>
  30 #include <TopoDS_Vertex.hxx>
  31 #include <TopoDS_Wire.hxx>
  32 #include <TopoDS_Iterator.hxx>
  33 #include <BRep_Tool.hxx>
  34 #include <BRepAdaptor_Surface.hxx>
  35
  36 #include <BOPCol_ListOfShape.hxx>
  37 #include <BOPCol_SequenceOfShape.hxx>
  38 #include <BOPCol_SequenceOfPnt2d.hxx>
  39 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
  40 //
  41 #include <Geom_Surface.hxx>
  42 #include <Geom_Plane.hxx>
  43 #include <Geom_RectangularTrimmedSurface.hxx>
  44 #include <Geom_RectangularTrimmedSurface.hxx>
  45 #include <BOPTools_AlgoTools2D.hxx>
  46 #include <TopLoc_Location.hxx>
  47 #include <BRep_Builder.hxx>
  48 #include <BOPCol_SequenceOfReal.hxx>
  49 #include <TopExp.hxx>
  50 #include <TopExp_Explorer.hxx>
  51 //
  52
  53 static
  54   Standard_Real Angle (const gp_Dir2d& aDir2D);
  55
  56 static
  57   Standard_Real Angle2D (const TopoDS_Vertex& aV,
  58                          const TopoDS_Edge& anEdge,
  59                          const TopoDS_Face& myFace,
  60                          const GeomAdaptor_Surface& aGAS,
  61                          const Standard_Boolean aFlag);
  62
  63 static
  64   void GetNextVertex(const TopoDS_Vertex& aV,
  65                      const TopoDS_Edge& aE,
  66                      TopoDS_Vertex& aV1);
  67
  68 static
  69   Standard_Real AngleIn(const TopoDS_Edge& aEIn,
  70                         const BOPAlgo_ListOfEdgeInfo& aLEInfo);
  71
  72 static
  73   Standard_Integer NbWaysOut(const BOPAlgo_ListOfEdgeInfo& aLEInfo);
  74
  75 static
  76   gp_Pnt2d Coord2dVf (const TopoDS_Edge& aE,
  77                       const TopoDS_Face& aF);
  78
  79 static
  80   gp_Pnt2d Coord2d (const TopoDS_Vertex& aV1,
  81                     const TopoDS_Edge& aE1,
  82                     const TopoDS_Face& aF);
  83
  84
  85 static
  86   Standard_Real ClockWiseAngle(const Standard_Real aAngleIn,
  87                                const Standard_Real aAngleOut);
  88
  89 static
  90   void Path (const GeomAdaptor_Surface& aGAS,
  91              const TopoDS_Face& myFace,
  92              const TopoDS_Vertex& aVa,
  93              const TopoDS_Edge& aEOuta,
  94              BOPAlgo_EdgeInfo& anEdgeInfo,
  95              BOPCol_SequenceOfShape& aLS,
  96              BOPCol_SequenceOfShape& aVertVa,
  97              BOPCol_SequenceOfPnt2d& aCoordVa,
  98              BOPTools_ConnexityBlock& aCB,
  99              BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap);
 100
 101 static
 102   Standard_Real Angle2D (const TopoDS_Vertex& aV,
 103                          const TopoDS_Edge& anEdge,
 104                          const TopoDS_Face& myFace,
 105                          const GeomAdaptor_Surface& aGAS,
 106                          const Standard_Boolean aFlag);
 107 static
 108   Standard_Real Angle (const gp_Dir2d& aDir2D);
 109
 110 static
 111   Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
 112                              const GeomAdaptor_Surface& aGAS);
 113
 114 static
 115   void BuildPCurveForPlane (const BOPCol_ListOfShape myEdges,
 116                             const TopoDS_Face& myFace);
 117
 118 static
 119   Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
 120                               const GeomAdaptor_Surface& aGAS);
 121 static
 122   Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
 123                               const GeomAdaptor_Surface& aGAS);
 124
 125 static
 126   Standard_Boolean RecomputeAngles(const BOPAlgo_ListOfEdgeInfo& aLEInfo,
 127                                    const TopoDS_Face&            theFace,
 128                                    const gp_Pnt2d&               thePb,
 129                                    const TopoDS_Vertex&          theVb,
 130                                    const GeomAdaptor_Surface&    theGAS,
 131                                    const TopoDS_Edge&            theEOuta,
 132                                    const Standard_Boolean&       bHasClosed,
 133                                    const Standard_Real&          theTol2D,
 134                                    BOPCol_SequenceOfReal&        theRecomputedAngles);
 135
 136 //=======================================================================
 137 //function : SplitBlock
 138 //purpose  :
 139 //=======================================================================
 140   void BOPAlgo_WireSplitter::SplitBlock(BOPTools_ConnexityBlock& aCB)
 141 {
 142   Standard_Boolean bNothingToDo;
 143   Standard_Integer aIx, aNb, i, aCntIn, aCntOut;
 144   Standard_Real aAngle;
 145   TopAbs_Orientation aOr;
 146   TopoDS_Iterator aItS;
 147   TopoDS_Vertex aVV;
 148   BOPCol_ListIteratorOfListOfShape aIt;
 149   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
 150   //
 151   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo mySmartMap(100, myAllocator);
 152   //
 153   const TopoDS_Face& myFace=myWES->Face();
 154   const BOPCol_ListOfShape& myEdges=aCB.Shapes();
 155   //
 156   // 1.Filling mySmartMap
 157   BuildPCurveForPlane(myEdges, myFace);
 158   aIt.Initialize(myEdges);
 159   for(; aIt.More(); aIt.Next()) {
 160     const TopoDS_Edge& aE=(*(TopoDS_Edge *)&aIt.Value());
 161     if (!BOPTools_AlgoTools2D::HasCurveOnSurface (aE, myFace)) {
 162       continue;
 163     }
 164     //
 165     aItS.Initialize(aE);
 166     for(; aItS.More(); aItS.Next()) {
 167       const TopoDS_Shape& aV=aItS.Value();
 168       aIx=mySmartMap.FindIndex(aV);
 169       if (!aIx) {
 170         BOPAlgo_ListOfEdgeInfo aLEIx(myAllocator);
 171         aIx=mySmartMap.Add(aV, aLEIx);
 172       }
 173       //
 174       BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(aIx);
 175       //
 176       BOPAlgo_EdgeInfo aEI;
 177       //
 178       aEI.SetEdge(aE);
 179       aOr=aV.Orientation();
 180       if (aOr==TopAbs_FORWARD) {
 181         aEI.SetInFlag(Standard_False);
 182       }
 183       else if (aOr==TopAbs_REVERSED) {
 184         aEI.SetInFlag(Standard_True);
 185       }
 186       aLEI.Append(aEI);
 187     }
 188   }
 189   //
 190   aNb=mySmartMap.Extent();
 191   //
 192   bNothingToDo=Standard_True;
 193   for (i=1; i<=aNb; i++) {
 194     aCntIn=0;
 195     aCntOut=0;
 196     const BOPAlgo_ListOfEdgeInfo& aLEInfo= mySmartMap(i);
 197     BOPAlgo_ListIteratorOfListOfEdgeInfo anIt(aLEInfo);
 198     for (; anIt.More(); anIt.Next()) {
 199       const BOPAlgo_EdgeInfo& aEI=anIt.Value();
 200       if (aEI.IsIn()) {
 201         aCntIn++;
 202       }
 203       else {
 204         aCntOut++;
 205       }
 206     }
 207     if (aCntIn!=1 || aCntOut!=1) {
 208       bNothingToDo=Standard_False;
 209       break;
 210     }
 211   }
 212   //
 213   // Each vertex has one edge In and one - Out. Good. But it is not enought
 214   // to consider that nothing to do with this. We must check edges on TShape
 215   // coinsidence. If there are such edges there is something to do with.
 216   if (bNothingToDo) {
 217     Standard_Integer aNbE, aNbMapEE;
 218     Standard_Boolean bFlag;
 219     //
 220     BOPCol_IndexedDataMapOfShapeListOfShape aMapEE(100, myAllocator);
 221     aNbE=myEdges.Extent();
 222     //
 223     aIt.Initialize(myEdges);
 224     for (; aIt.More(); aIt.Next()) {
 225       const TopoDS_Shape& aE = aIt.Value();
 226       if (!aMapEE.Contains(aE)) {
 227         BOPCol_ListOfShape aLEx(myAllocator);
 228         aLEx.Append(aE);
 229         aMapEE.Add(aE, aLEx);
 230       }
 231       else {
 232         BOPCol_ListOfShape& aLEx=aMapEE.ChangeFromKey(aE);
 233         aLEx.Append(aE);
 234       }
 235     }
 236     //
 237     bFlag=Standard_True;
 238     aNbMapEE=aMapEE.Extent();
 239     for (i=1; i<=aNbMapEE; ++i) {
 240       const BOPCol_ListOfShape& aLEx=aMapEE(i);
 241       aNbE=aLEx.Extent();
 242       if (aNbE==1) {// usual case
 243         continue;
 244       }
 245       else if (aNbE==2){
 246         const TopoDS_Shape& aE1=aLEx.First();
 247         const TopoDS_Shape& aE2=aLEx.Last();
 248         if (aE1.IsSame(aE2)) {
 249           bFlag=Standard_False;
 250           break;
 251         }
 252       }
 253       else {
 254         bFlag=Standard_False;
 255         break;
 256       }
 257     }
 258     bNothingToDo=bNothingToDo && bFlag;
 259   } // if (bNothingToDo) {
 260   if (bNothingToDo) {
 261     TopoDS_Wire aW;
 262     //
 263     BOPCol_ListOfShape& aLECB=aCB.ChangeShapes();
 264     BOPAlgo_WireSplitter::MakeWire(aLECB, aW);
 265     BOPCol_ListOfShape& aLoops=aCB.ChangeLoops();
 266     aLoops.Append(aW);
 267     //
 268     myErrorStatus=0;
 269     return;
 270   }
 271   //
 272   // 3. Angles in mySmartMap
 273   BRepAdaptor_Surface aBAS(myFace);
 274   const GeomAdaptor_Surface& aGAS=aBAS.Surface();
 275   //
 276   for (i=1; i<=aNb; i++) {
 277     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i)));
 278     const BOPAlgo_ListOfEdgeInfo& aLEI= mySmartMap(i);
 279
 280     aItLEI.Initialize(aLEI);
 281     for (; aItLEI.More(); aItLEI.Next()) {
 282       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 283       const TopoDS_Edge& aE=aEI.Edge();
 284       //
 285       aVV=aV;
 286       if (aEI.IsIn()) {
 287         aVV.Orientation(TopAbs_REVERSED);
 288         aAngle=Angle2D (aVV, aE, myFace, aGAS, Standard_True);
 289       }
 290       else { // OUT
 291         aVV.Orientation(TopAbs_FORWARD);
 292         aAngle=Angle2D (aVV, aE, myFace, aGAS, Standard_False);
 293       }
 294       aEI.SetAngle(aAngle);
 295     }
 296   }// for (i=1; i<=aNb; i++) {
 297   //
 298   // 4. Do
 299   //
 300   Standard_Boolean bIsOut, bIsNotPassed;
 301   BOPCol_SequenceOfShape aLS, aVertVa;
 302   BOPCol_SequenceOfPnt2d aCoordVa;
 303   //
 304   for (i=1; i<=aNb; ++i) {
 305     const TopoDS_Vertex& aVa=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i)));
 306     const BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
 307     aItLEI.Initialize(aLEI);
 308     for (; aItLEI.More(); aItLEI.Next()) {
 309       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
 310       const TopoDS_Edge& aEOuta=aEI.Edge();
 311       //
 312       bIsOut=!aEI.IsIn();
 313       bIsNotPassed=!aEI.Passed();
 314       if (bIsOut && bIsNotPassed) {
 315         //
 316         aLS.Clear();
 317         aVertVa.Clear();
 318         aCoordVa.Clear();
 319         //
 320         Path(aGAS, myFace, aVa, aEOuta, aEI, aLS,
 321              aVertVa, aCoordVa, aCB, mySmartMap);
 322       }
 323     }
 324   }// for (i=1; i<=aNb; ++i) {
 325 }
 326 //=======================================================================
 327 // function: Path
 328 // purpose:
 329 //=======================================================================
 330 void Path (const GeomAdaptor_Surface& aGAS,
 331            const TopoDS_Face& myFace,
 332            const TopoDS_Vertex& aVa,
 333            const TopoDS_Edge& aEOuta,
 334            BOPAlgo_EdgeInfo& anEdgeInfo,
 335            BOPCol_SequenceOfShape& aLS,
 336            BOPCol_SequenceOfShape& aVertVa,
 337            BOPCol_SequenceOfPnt2d& aCoordVa,
 338            BOPTools_ConnexityBlock& aCB,
 339            BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap)
 340
 341 {
 342   Standard_Integer i, j, aNb, aNbj;
 343   Standard_Real aTol, anAngleIn, anAngleOut, anAngle, aMinAngle;
 344   Standard_Real aTol2D, aTol2D2;
 345   Standard_Real aTol2, aD2;
 346   Standard_Boolean anIsSameV2d, anIsSameV, anIsFound, anIsOut, anIsNotPassed;
 347   TopoDS_Vertex aVb;
 348   TopoDS_Edge aEOutb;
 349   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
 350   //
 351   aTol=1.e-7;
 352   //
 353   // append block
 354   //
 355   // Do not escape through edge from which you enter
 356   aNb=aLS.Length();
 357   if (aNb==1) {
 358     const TopoDS_Shape& anEPrev=aLS(aNb);
 359     if (anEPrev.IsSame(aEOuta)) {
 360       return;
 361     }
 362   }
 363   //
 364   anEdgeInfo.SetPassed(Standard_True);
 365   aLS.Append(aEOuta);
 366   aVertVa.Append(aVa);
 367
 368   TopoDS_Vertex pVa=aVa;
 369   pVa.Orientation(TopAbs_FORWARD);
 370   gp_Pnt2d aPa=Coord2d(pVa, aEOuta, myFace);
 371   aCoordVa.Append(aPa);
 372
 373   GetNextVertex (pVa, aEOuta, aVb);
 374
 375   gp_Pnt2d aPb=Coord2d(aVb, aEOuta, myFace);
 376
 377   const BOPAlgo_ListOfEdgeInfo& aLEInfoVb=mySmartMap.FindFromKey(aVb);
 378   //
 379   aTol=2.*Tolerance2D(aVb, aGAS);
 380   aTol2=10.*aTol*aTol;
 381
 382   TopoDS_Vertex aV1, aV2;
 383   TopExp::Vertices(aEOuta, aV1, aV2);
 384   Standard_Boolean bIsClosedEdge = aV1.IsNull() || aV2.IsNull() || aV1.IsSame(aV2);
 385   Standard_Boolean bIsDegenerated = BRep_Tool::Degenerated(aEOuta);
 386   Standard_Boolean bIsSeam = BRep_Tool::IsClosed(aEOuta, myFace);
 387
 388   anIt.Initialize(aLEInfoVb);
 389   for (; anIt.More(); anIt.Next()) {
 390     const BOPAlgo_EdgeInfo& anEI = anIt.Value();
 391     const TopoDS_Edge& aE = anEI.Edge();
 392     bIsDegenerated = bIsDegenerated || BRep_Tool::Degenerated(aE);
 393     bIsSeam = bIsSeam || BRep_Tool::IsClosed(aE, myFace);
 394     aV1.Nullify();
 395     aV2.Nullify();
 396     TopExp::Vertices(aE, aV1, aV2);
 397     bIsClosedEdge = bIsClosedEdge || aV1.IsNull() || aV2.IsNull() || aV1.IsSame(aV2);
 398   }
 399   //
 400   aNb=aLS.Length();
 401   if (aNb>0) {
 402     //
 403     BOPCol_ListOfShape aBuf;
 404     //
 405     for (i=aNb; i>0; --i) {
 406       const TopoDS_Shape& aVPrev=aVertVa(i);
 407       const gp_Pnt2d& aPaPrev=aCoordVa(i);
 408       const TopoDS_Shape& aEPrev=aLS(i);
 409
 410       aBuf.Append(aEPrev);
 411
 412       anIsSameV=aVPrev.IsSame(aVb);
 413       anIsSameV2d=Standard_False;
 414
 415       if (anIsSameV) {
 416         anIsSameV2d = Standard_True;
 417         //
 418         aD2=aPaPrev.SquareDistance(aPb);
 419         anIsSameV2d =aD2<aTol2;
 420         if(anIsSameV2d &&
 421            (bIsDegenerated || bIsSeam || bIsClosedEdge)) {
 422           Standard_Real udist = fabs(aPaPrev.X() - aPb.X());
 423           Standard_Real vdist = fabs(aPaPrev.Y() - aPb.Y());
 424           Standard_Real aTolU = 2. * UTolerance2D(aVb, aGAS);
 425           Standard_Real aTolV = 2. * VTolerance2D(aVb, aGAS);
 426           //
 427           if((udist > aTolU) ||
 428              (vdist > aTolV)) {
 429             anIsSameV2d = Standard_False;
 430           }
 431         }
 432       }//if (anIsSameV) {
 433       //
 434       if (anIsSameV && anIsSameV2d) {
 435         Standard_Integer iPriz;
 436         iPriz=1;
 437         if (aBuf.Extent()==2) {
 438           if(aBuf.First().IsSame(aBuf.Last())) {
 439             iPriz=0;
 440           }
 441         }
 442         if (iPriz) {
 443           TopoDS_Wire aW;
 444           BOPAlgo_WireSplitter::MakeWire(aBuf, aW);
 445           aCB.ChangeLoops().Append(aW);
 446         }
 447         //
 448         aNbj=i-1;
 449         if (aNbj<1) {
 450           //
 451           aLS.Clear();
 452           aVertVa.Clear();
 453           aCoordVa.Clear();
 454           //
 455           return;
 456         }
 457         //
 458         BOPCol_SequenceOfShape aLSt, aVertVat;
 459         BOPCol_SequenceOfPnt2d aCoordVat;
 460         //
 461         aVb=(*(TopoDS_Vertex *)(&aVertVa(i)));
 462         //
 463         for (j=1; j<=aNbj; ++j) {
 464           aLSt.Append(aLS(j));
 465           aVertVat.Append(aVertVa(j));
 466           aCoordVat.Append(aCoordVa(j));
 467         }
 468         //
 469         aLS.Clear();
 470         aVertVa.Clear();
 471         aCoordVa.Clear();
 472
 473         aLS=aLSt;
 474         aVertVa=aVertVat;
 475         aCoordVa=aCoordVat;
 476         //
 477         break;
 478       }
 479     }
 480   }
 481   //
 482   aTol2D=2.*Tolerance2D(aVb, aGAS);
 483   aTol2D2=1000.*aTol2D*aTol2D;//100.*aTol2D*aTol2D;
 484   //
 485   // anAngleIn in Vb from edge aEOuta
 486   const BOPAlgo_ListOfEdgeInfo& aLEInfo=mySmartMap.FindFromKey(aVb);
 487   //
 488   anAngleIn=AngleIn(aEOuta, aLEInfo);
 489   BOPCol_SequenceOfReal aRecomputedAngles;
 490
 491   Standard_Boolean bRecomputeAngle =
 492     RecomputeAngles(aLEInfo, myFace, aPb, aVb, aGAS, aEOuta,
 493                     (bIsDegenerated || bIsSeam || bIsClosedEdge),
 494                     aTol2D, aRecomputedAngles);
 495
 496   //
 497   // aEOutb
 498   BOPAlgo_EdgeInfo *pEdgeInfo=NULL;
 499   //
 500   aMinAngle=100.;
 501   anIsFound=Standard_False;
 502   Standard_Integer aCurIndexE = 0;
 503   anIt.Initialize(aLEInfo);
 504   for (; anIt.More(); anIt.Next()) {
 505     BOPAlgo_EdgeInfo& anEI=anIt.ChangeValue();
 506     const TopoDS_Edge& aE=anEI.Edge();
 507     anIsOut=!anEI.IsIn();
 508     anIsNotPassed=!anEI.Passed();
 509
 510     if (anIsOut && anIsNotPassed) {
 511       aCurIndexE++;
 512       //
 513       // Is there one way to go out of the vertex
 514       // we have to use it only.
 515       Standard_Integer iCnt;
 516       iCnt=NbWaysOut (aLEInfo);
 517       //
 518       if (!iCnt) {
 519         // no way to go . (Error)
 520         return ;
 521       }
 522       //
 523       if (iCnt==1) {
 524         // the one and only way to go out .
 525         pEdgeInfo=&anEI;
 526         anIsFound=Standard_True;
 527         break;
 528       }
 529       //
 530       // Look for minimal angle and make the choice.
 531       gp_Pnt2d aP2Dx;
 532       //
 533       aP2Dx=Coord2dVf(aE, myFace);
 534       //
 535       aD2=aP2Dx.SquareDistance(aPb);
 536       if (aD2 > aTol2D2){
 537         continue;
 538       }
 539       //
 540       //
 541       anAngleOut=anEI.Angle();
 542       //
 543       if(bRecomputeAngle) {
 544         if(aCurIndexE <= aRecomputedAngles.Length()) {
 545           anAngleOut = aRecomputedAngles.Value(aCurIndexE);
 546         }
 547       }
 548
 549       anAngle=ClockWiseAngle(anAngleIn, anAngleOut);
 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   aEOutb=pEdgeInfo->Edge();
 564   //
 565   Path (aGAS, myFace, aVb, aEOutb, *pEdgeInfo, aLS,
 566         aVertVa, aCoordVa, aCB, mySmartMap);
 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 aFlag)
 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   if (fabs (aTV-aFirst) < fabs(aTV - aLast)) {
 753     aTV1=aTV + dt;
 754   }
 755   else {
 756     aTV1=aTV - dt;
 757   }
 758   //
 759   aC2D->D0 (aTV1, aPV1);
 760   aC2D->D0 (aTV, aPV);
 761   //
 762   if (aFlag) {//IN
 763     gp_Vec2d aV2DIn(aPV1, aPV);
 764     aV2D=aV2DIn;
 765   }
 766   else {
 767     gp_Vec2d aV2DOut(aPV, aPV1);
 768     aV2D=aV2DOut;
 769   }
 770   //
 771   gp_Dir2d aDir2D(aV2D);
 772   anAngle=Angle(aDir2D);
 773   //
 774   return anAngle;
 775 }
 776 //=======================================================================
 777 // function: Angle
 778 // purpose:
 779 //=======================================================================
 780 Standard_Real Angle (const gp_Dir2d& aDir2D)
 781 {
 782   gp_Dir2d aRefDir(1., 0.);
 783   Standard_Real anAngle;
 784
 785   anAngle = aRefDir.Angle(aDir2D);
 786   if (anAngle < 0.)
 787     anAngle += M_PI + M_PI;
 788   return anAngle;
 789 }
 790 //=======================================================================
 791 // function:  Tolerance2D
 792 // purpose:
 793 //=======================================================================
 794  Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
 795                             const GeomAdaptor_Surface& aGAS)
 796 {
 797   Standard_Real aTol2D, anUr, aVr, aTolV3D;
 798   GeomAbs_SurfaceType aType;
 799   //
 800   aType=aGAS.GetType();
 801   aTolV3D=BRep_Tool::Tolerance(aV);
 802
 803   anUr=aGAS.UResolution(aTolV3D);
 804   aVr =aGAS.VResolution(aTolV3D);
 805   aTol2D=(aVr>anUr) ? aVr : anUr;
 806   //
 807   if (aTol2D < aTolV3D) {
 808     aTol2D=aTolV3D;
 809   }
 810   if (aType==GeomAbs_BSplineSurface) {
 811     aTol2D=1.1*aTol2D;
 812   }
 813   //
 814   return aTol2D;
 815 }
 816 //=======================================================================
 817 // function: BuildPCurvesForPlane
 818 // purpose:
 819 //=======================================================================
 820   void BuildPCurveForPlane (const BOPCol_ListOfShape myEdges,
 821                             const TopoDS_Face& myFace)
 822 {
 823   TopLoc_Location aLoc;
 824   Handle(Geom2d_Curve) aC2D;
 825   Handle(Geom_Plane) aGP;
 826   Handle(Geom_RectangularTrimmedSurface) aGRTS;
 827   //
 828   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(myFace, aLoc);
 829   aGRTS=Handle(Geom_RectangularTrimmedSurface)::DownCast(aS);
 830   if(!aGRTS.IsNull()){
 831     aGP=Handle(Geom_Plane)::DownCast(aGRTS->BasisSurface());
 832     }
 833   else {
 834     aGP=Handle(Geom_Plane)::DownCast(aS);
 835   }
 836   //
 837   if (aGP.IsNull()) {
 838     return;
 839   }
 840   //
 841   Standard_Real aTolE;
 842   BOPCol_ListIteratorOfListOfShape aIt;
 843   BRep_Builder aBB;
 844   //
 845   aIt.Initialize(myEdges);
 846   for(; aIt.More(); aIt.Next()) {
 847     const TopoDS_Edge& aE=(*(TopoDS_Edge *)&aIt.Value());
 848     BOPTools_AlgoTools2D::CurveOnSurface(aE, myFace, aC2D, aTolE);
 849     aBB.UpdateEdge(aE, aC2D, myFace, aTolE);
 850   }
 851 }
 852 //=======================================================================
 853 //function : UTolerance2D
 854 //purpose  :
 855 //=======================================================================
 856 Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
 857                             const GeomAdaptor_Surface& aGAS)
 858 {
 859   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
 860   const Standard_Real anUr = aGAS.UResolution(aTolV3D);
 861   //
 862   return anUr;
 863 }
 864
 865 //=======================================================================
 866 //function : VTolerance2D
 867 //purpose  :
 868 //=======================================================================
 869 Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
 870                             const GeomAdaptor_Surface& aGAS)
 871 {
 872   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
 873   const Standard_Real anVr = aGAS.VResolution(aTolV3D);
 874   //
 875   return anVr;
 876 }
 877
 878 //=======================================================================
 879 // function: RecomputeAngles
 880 // purpose:
 881 //=======================================================================
 882 Standard_Boolean RecomputeAngles(const BOPAlgo_ListOfEdgeInfo& aLEInfo,
 883                                  const TopoDS_Face&            theFace,
 884                                  const gp_Pnt2d&               thePb,
 885                                  const TopoDS_Vertex&          theVb,
 886                                  const GeomAdaptor_Surface&    theGAS,
 887                                  const TopoDS_Edge&            theEOuta,
 888                                  const Standard_Boolean&       bIsClosed,
 889                                  const Standard_Real&          theTol2D,
 890                                  BOPCol_SequenceOfReal&        theRecomputedAngles)
 891 {
 892   Standard_Boolean bRecomputeAngle = Standard_False;
 893   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
 894   anIt.Initialize(aLEInfo);
 895
 896   for (; anIt.More(); anIt.Next()) {
 897     const BOPAlgo_EdgeInfo& anEI=anIt.Value();
 898     const TopoDS_Edge& aE=anEI.Edge();
 899     Standard_Boolean anIsOut=!anEI.IsIn();
 900     Standard_Boolean anIsNotPassed=!anEI.Passed();
 901
 902     if (anIsOut && anIsNotPassed) {
 903       theRecomputedAngles.Append(anEI.Angle());
 904       Standard_Integer acurindex = theRecomputedAngles.Length();
 905
 906       Standard_Boolean bRecomputeAngleLocal = Standard_False;
 907       TopExp_Explorer anExp1(aE, TopAbs_VERTEX);
 908
 909       for(; anExp1.More(); anExp1.Next()) {
 910         TopExp_Explorer anExp2(theEOuta, TopAbs_VERTEX);
 911         Standard_Boolean existsInEdge = Standard_False;
 912
 913         for(; anExp2.More(); anExp2.Next()) {
 914           if(anExp1.Current().IsSame(anExp2.Current())) {
 915             existsInEdge = Standard_True;
 916             break;
 917           }
 918         }
 919
 920         if(!existsInEdge) {
 921           bRecomputeAngleLocal = Standard_False;
 922           break;
 923         }
 924         bRecomputeAngleLocal = Standard_True;
 925       }
 926       bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
 927
 928       if(!bRecomputeAngle) {
 929         BOPAlgo_ListIteratorOfListOfEdgeInfo anIt2(aLEInfo);
 930
 931         for(; anIt2.More(); anIt2.Next()) {
 932           const BOPAlgo_EdgeInfo& anEI2=anIt2.Value();
 933           const TopoDS_Edge& aE2=anEI2.Edge();
 934
 935           if(aE2.IsSame(aE))
 936             continue;
 937           Standard_Boolean anIsOut2=!anEI2.IsIn();
 938           Standard_Boolean anIsNotPassed2=!anEI2.Passed();
 939
 940           if (anIsOut2 && anIsNotPassed2) {
 941             anExp1.Init(aE, TopAbs_VERTEX);
 942
 943             for(; anExp1.More(); anExp1.Next()) {
 944               TopExp_Explorer anExp2(aE2, TopAbs_VERTEX);
 945               Standard_Boolean existsInEdge = Standard_False;
 946
 947               for(; anExp2.More(); anExp2.Next()) {
 948                 if(anExp1.Current().IsSame(anExp2.Current())) {
 949                   existsInEdge = Standard_True;
 950                   break;
 951                 }
 952               }
 953
 954               if(!existsInEdge) {
 955                 bRecomputeAngleLocal = Standard_False;
 956                 break;
 957               }
 958               bRecomputeAngleLocal = Standard_True;
 959             }
 960             bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
 961           }
 962         }
 963       }
 964
 965       bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
 966
 967       if(bRecomputeAngle) {
 968         gp_Pnt2d aP2Dx;
 969         //
 970         aP2Dx=Coord2dVf(aE, theFace);
 971         Standard_Real aD = aP2Dx.Distance(thePb);
 972
 973         TopoDS_Vertex aVf;
 974         TopExp_Explorer anExp(aE, TopAbs_VERTEX);
 975
 976         for (; anExp.More(); anExp.Next()) {
 977           const TopoDS_Vertex& aVx=*(TopoDS_Vertex*)(&anExp.Current());
 978           if (aVx.Orientation()==TopAbs_FORWARD) {
 979             aVf = aVx;
 980           }
 981         }
 982         Standard_Boolean bIgnore = Standard_False;
 983
 984         if(bIsClosed || aVf.IsNull() || !aVf.IsSame(theVb)) {
 985           bIgnore = (aD > theTol2D);
 986         }
 987
 988         if(!bIgnore && (theTol2D > M_PI)) {
 989           Standard_Real udist = fabs(aP2Dx.X() - thePb.X());
 990           Standard_Real vdist = fabs(aP2Dx.Y() - thePb.Y());
 991           Standard_Real aTolU = 2. * UTolerance2D(theVb, theGAS);
 992           Standard_Real aTolV = 2. * VTolerance2D(theVb, theGAS);
 993
 994           if((udist > aTolU) ||
 995              (vdist > aTolV)) {
 996             bIgnore = Standard_True;
 997           }
 998         }
 999
1000         if((aD > Precision::Confusion()) && !bIgnore) {
1001           Standard_Real f1, l1;
1002           Handle(Geom2d_Curve) ac1 = BRep_Tool::CurveOnSurface(aE, theFace, f1, l1);
1003
1004           Standard_Real aTV1 = BRep_Tool::Parameter (aVf, aE, theFace);
1005           Standard_Real aTV12 = 0.;
1006           Standard_Real dt1 = (l1 - f1) * 0.5;
1007
1008           if (fabs (aTV1-f1) < fabs(aTV1 - l1)) {
1009             aTV12 = aTV1 + dt1;
1010           }
1011           else {
1012             aTV12 = aTV1 - dt1;
1013           }
1014
1015           gp_Pnt2d aPointNew = ac1->Value(aTV12);
1016           gp_Vec2d aV2DOut(thePb, aPointNew);
1017
1018           gp_Dir2d aDir2D(aV2DOut);
1019           Standard_Real anAngleOut = Angle(aDir2D);
1020           theRecomputedAngles.ChangeValue(acurindex) = anAngleOut;
1021         }
1022       }
1023     }
1024   }
1025   return bRecomputeAngle;
1026 }