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