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