src/BOPTools/BOPTools_AlgoTools.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
   3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
   4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
   5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   6 //
   7 // This file is part of Open CASCADE Technology software library.
   8 //
   9 // This library is free software; you can redistribute it and/or modify it under
  10 // the terms of the GNU Lesser General Public License version 2.1 as published
  11 // by the Free Software Foundation, with special exception defined in the file
  12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  13 // distribution for complete text of the license and disclaimer of any warranty.
  14 //
  15 // Alternatively, this file may be used under the terms of Open CASCADE
  16 // commercial license or contractual agreement.
  17
  18
  19 #include <BOPCol_IndexedMapOfShape.hxx>
  20 #include <BOPCol_MapOfShape.hxx>
  21 #include <BOPTools.hxx>
  22 #include <BOPTools_AlgoTools.hxx>
  23 #include <BOPTools_AlgoTools2D.hxx>
  24 #include <BOPTools_AlgoTools3D.hxx>
  25 #include <BOPTools_CoupleOfShape.hxx>
  26 #include <BOPTools_ListOfCoupleOfShape.hxx>
  27 #include <BRep_Builder.hxx>
  28 #include <BRep_Tool.hxx>
  29 #include <BRepAdaptor_Curve2d.hxx>
  30 #include <BRepAdaptor_Surface.hxx>
  31 #include <BRepClass3d_SolidClassifier.hxx>
  32 #include <BRepLib.hxx>
  33 #include <Geom2d_Curve.hxx>
  34 #include <Geom2dInt_Geom2dCurveTool.hxx>
  35 #include <Geom_Curve.hxx>
  36 #include <Geom_Plane.hxx>
  37 #include <Geom_Surface.hxx>
  38 #include <Geom_TrimmedCurve.hxx>
  39 #include <GeomAPI_ProjectPointOnSurf.hxx>
  40 #include <gp_Cone.hxx>
  41 #include <gp_Cylinder.hxx>
  42 #include <gp_Lin.hxx>
  43 #include <gp_Pnt.hxx>
  44 #include <gp_Pnt2d.hxx>
  45 #include <gp_Sphere.hxx>
  46 #include <gp_Torus.hxx>
  47 #include <gp_XYZ.hxx>
  48 #include <IntTools_Context.hxx>
  49 #include <IntTools_Curve.hxx>
  50 #include <IntTools_Range.hxx>
  51 #include <IntTools_ShrunkRange.hxx>
  52 #include <IntTools_Tools.hxx>
  53 #include <Precision.hxx>
  54 #include <TopAbs_Orientation.hxx>
  55 #include <TopExp.hxx>
  56 #include <TopExp_Explorer.hxx>
  57 #include <TopoDS_Compound.hxx>
  58 #include <TopoDS_CompSolid.hxx>
  59 #include <TopoDS_Edge.hxx>
  60 #include <TopoDS_Face.hxx>
  61 #include <TopoDS_Shape.hxx>
  62 #include <TopoDS_Shell.hxx>
  63 #include <TopoDS_Solid.hxx>
  64 #include <TopoDS_Vertex.hxx>
  65 #include <TopoDS_Wire.hxx>
  66 #include <NCollection_Array1.hxx>
  67 #include <algorithm>
  68
  69 //
  70 static
  71   Standard_Real AngleWithRef(const gp_Dir& theD1,
  72                              const gp_Dir& theD2,
  73                              const gp_Dir& theDRef);
  74
  75 static
  76   Standard_Boolean FindFacePairs (const TopoDS_Edge& theE,
  77                                   const BOPCol_ListOfShape& thLF,
  78                                   BOPTools_ListOfCoupleOfShape& theLCFF,
  79                                   Handle(IntTools_Context)& theContext);
  80 static
  81   TopAbs_Orientation Orientation(const TopoDS_Edge& anE,
  82                                  const TopoDS_Face& aF);
  83
  84 static
  85   void GetFaceDir(const TopoDS_Edge& aE,
  86                   const TopoDS_Face& aF,
  87                   const gp_Pnt& aP,
  88                   const Standard_Real aT,
  89                   const gp_Dir& aDTgt,
  90                   gp_Dir& aDN,
  91                   gp_Dir& aDB,
  92                   Handle(IntTools_Context)& theContext,
  93                   GeomAPI_ProjectPointOnSurf& aProjPL,
  94                   const Standard_Real aDt);
  95 static
  96   Standard_Boolean FindPointInFace(const TopoDS_Face& aF,
  97                                    const gp_Pnt& aP,
  98                                    gp_Dir& aDB,
  99                                    gp_Pnt& aPOut,
 100                                    Handle(IntTools_Context)& theContext,
 101                                    GeomAPI_ProjectPointOnSurf& aProjPL,
 102                                    const Standard_Real aDt,
 103                                    const Standard_Real aTolE);
 104 static
 105   Standard_Real MinStep3D(const TopoDS_Edge& theE1,
 106                           const TopoDS_Face& theF1,
 107                           const BOPTools_ListOfCoupleOfShape& theLCS,
 108                           const gp_Pnt& aP);
 109
 110
 111
 112 //=======================================================================
 113 // function: MakeConnexityBlocks
 114 // purpose:
 115 //=======================================================================
 116 void BOPTools_AlgoTools::MakeConnexityBlocks
 117   (const TopoDS_Shape& theS,
 118    const TopAbs_ShapeEnum theType1,
 119    const TopAbs_ShapeEnum theType2,
 120    BOPCol_ListOfShape& theLCB)
 121 {
 122   Standard_Integer  aNbF, aNbAdd, aNbAdd1, i;
 123   BRep_Builder aBB;
 124   TopoDS_Compound aC;
 125   TopoDS_Iterator aIt;
 126   TopExp_Explorer aExp;
 127   BOPCol_MapOfShape aMP;
 128   BOPCol_IndexedMapOfShape aMCB, aMAdd, aMAdd1;
 129   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
 130   BOPCol_ListIteratorOfListOfShape aItLF;
 131   //
 132   // 1. aMEF
 133   BOPTools::MapShapesAndAncestors(theS, theType1, theType2, aMEF);
 134   //
 135   // 2. aMCB
 136   aIt.Initialize(theS);
 137   for (; aIt.More(); aIt.Next()) {
 138     const TopoDS_Shape& aF1=aIt.Value();
 139     if (aMP.Contains(aF1)) {
 140       continue;
 141     }
 142     //
 143     aMCB.Clear();
 144     aMAdd.Clear();
 145     aMAdd.Add(aF1);
 146     //
 147     for(;;) {
 148       aMAdd1.Clear();
 149       //
 150       aNbAdd = aMAdd.Extent();
 151       for (i=1; i<=aNbAdd; ++i) {
 152         const TopoDS_Shape& aF=aMAdd(i);
 153         //
 154         aExp.Init(aF, theType1);
 155         for (; aExp.More(); aExp.Next()) {
 156           const TopoDS_Shape& aE=aExp.Current();
 157           //
 158           const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
 159           aItLF.Initialize(aLF);
 160           for (; aItLF.More(); aItLF.Next()) {
 161             const TopoDS_Shape& aFx=aItLF.Value();
 162             if (aFx.IsSame(aF)) {
 163               continue;
 164             }
 165             if (aMCB.Contains(aFx)) {
 166               continue;
 167             }
 168             aMAdd1.Add(aFx);
 169           }
 170         }//for (; aExp.More(); aExp.Next()){
 171         aMCB.Add(aF);
 172       }// for (i=1; i<=aNbAdd; ++i) {
 173       //
 174       aNbAdd1=aMAdd1.Extent();
 175       if (!aNbAdd1) {
 176         break;// ->make new CB from aMCB
 177       }
 178       //
 179       aMAdd.Clear();
 180       for (i=1; i<=aNbAdd1; ++i) {
 181         const TopoDS_Shape& aFAdd = aMAdd1(i);
 182         aMAdd.Add(aFAdd);
 183       }
 184     }//while(1) {
 185     //
 186     aNbF=aMCB.Extent();
 187     if (aNbF) {
 188       aBB.MakeCompound(aC);
 189       //
 190       for (i=1; i<=aNbF; ++i) {
 191         const TopoDS_Shape& aF=aMCB(i);
 192         aBB.Add(aC, aF);
 193         aMP.Add(aF);
 194       }
 195       theLCB.Append(aC);
 196     }
 197   }// for (; aIt.More(); aIt.Next())
 198 }
 199 //=======================================================================
 200 // function: OrientFacesOnShell
 201 // purpose:
 202 //=======================================================================
 203 void BOPTools_AlgoTools::OrientFacesOnShell (TopoDS_Shape& aShell)
 204 {
 205   Standard_Boolean bIsProcessed1, bIsProcessed2;
 206   Standard_Integer i, aNbE, aNbF, j;
 207   TopAbs_Orientation anOrE1, anOrE2;
 208   TopoDS_Face aF1x, aF2x;
 209   TopoDS_Shape aShellNew;
 210   BOPCol_IndexedDataMapOfShapeListOfShape aEFMap;
 211   BOPCol_IndexedMapOfShape aProcessedFaces;
 212   BRep_Builder aBB;
 213   //
 214   BOPTools_AlgoTools::MakeContainer(TopAbs_SHELL, aShellNew);
 215   //
 216   BOPTools::MapShapesAndAncestors(aShell,
 217                                   TopAbs_EDGE, TopAbs_FACE,
 218                                   aEFMap);
 219   aNbE=aEFMap.Extent();
 220   //
 221   // One seam edge  in aEFMap contains  2 equivalent faces.
 222   for (i=1; i<=aNbE; ++i) {
 223     BOPCol_ListOfShape& aLF=aEFMap.ChangeFromIndex(i);
 224     aNbF=aLF.Extent();
 225     if (aNbF>1) {
 226       BOPCol_ListOfShape aLFTmp;
 227       BOPCol_IndexedMapOfShape aFM;
 228       //
 229       BOPCol_ListIteratorOfListOfShape anIt(aLF);
 230       for (; anIt.More(); anIt.Next()) {
 231         const TopoDS_Shape& aF=anIt.Value();
 232         if (!aFM.Contains(aF)) {
 233           aFM.Add(aF);
 234           aLFTmp.Append(aF);
 235         }
 236       }
 237       aLF.Clear();
 238       aLF=aLFTmp;
 239     }
 240   }
 241   //
 242   // Do
 243   for (i=1; i<=aNbE; ++i) {
 244     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aEFMap.FindKey(i)));
 245     if (BRep_Tool::Degenerated(aE)) {
 246       continue;
 247     }
 248     //
 249     const BOPCol_ListOfShape& aLF=aEFMap.FindFromIndex(i);
 250     aNbF=aLF.Extent();
 251     if (aNbF!=2) {
 252       continue;
 253     }
 254     //
 255     TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
 256     TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
 257     //
 258     bIsProcessed1=aProcessedFaces.Contains(aF1);
 259     bIsProcessed2=aProcessedFaces.Contains(aF2);
 260     if (bIsProcessed1 && bIsProcessed2) {
 261       continue;
 262     }
 263
 264     if (!bIsProcessed1 && !bIsProcessed2) {
 265       aProcessedFaces.Add(aF1);
 266       aBB.Add(aShellNew, aF1);
 267       bIsProcessed1=!bIsProcessed1;
 268     }
 269     //
 270     aF1x=aF1;
 271     if (bIsProcessed1) {
 272       j=aProcessedFaces.FindIndex(aF1);
 273       aF1x=(*(TopoDS_Face*)(&aProcessedFaces.FindKey(j)));
 274     }
 275     //
 276     aF2x=aF2;
 277     if (bIsProcessed2) {
 278       j=aProcessedFaces.FindIndex(aF2);
 279       aF2x=(*(TopoDS_Face*)(&aProcessedFaces.FindKey(j)));
 280     }
 281     //
 282     anOrE1=Orientation(aE, aF1x);
 283     anOrE2=Orientation(aE, aF2x);
 284     //
 285     if (bIsProcessed1 && !bIsProcessed2) {
 286       if (anOrE1==anOrE2) {
 287         if (!BRep_Tool::IsClosed(aE, aF1) &&
 288             !BRep_Tool::IsClosed(aE, aF2)) {
 289           aF2.Reverse();
 290         }
 291       }
 292       aProcessedFaces.Add(aF2);
 293       aBB.Add(aShellNew, aF2);
 294     }
 295     else if (!bIsProcessed1 && bIsProcessed2) {
 296       if (anOrE1==anOrE2) {
 297         if (!BRep_Tool::IsClosed(aE, aF1) &&
 298             !BRep_Tool::IsClosed(aE, aF2)) {
 299           aF1.Reverse();
 300         }
 301       }
 302       aProcessedFaces.Add(aF1);
 303       aBB.Add(aShellNew, aF1);
 304     }
 305   }
 306   //
 307   //
 308   for (i=1; i<=aNbE; ++i) {
 309     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aEFMap.FindKey(i)));
 310     if (BRep_Tool::Degenerated(aE)) {
 311       continue;
 312     }
 313     //
 314     const BOPCol_ListOfShape& aLF=aEFMap.FindFromIndex(i);
 315     aNbF=aLF.Extent();
 316     if (aNbF!=2) {
 317       BOPCol_ListIteratorOfListOfShape anIt(aLF);
 318       for(; anIt.More(); anIt.Next()) {
 319         const TopoDS_Face& aF=(*(TopoDS_Face*)(&anIt.Value()));
 320         if (!aProcessedFaces.Contains(aF)) {
 321           aProcessedFaces.Add(aF);
 322           aBB.Add(aShellNew, aF);
 323         }
 324       }
 325     }
 326   }
 327   aShell=aShellNew;
 328 }
 329 //=======================================================================
 330 //function : Orientation
 331 //purpose  :
 332 //=======================================================================
 333 TopAbs_Orientation Orientation(const TopoDS_Edge& anE,
 334                                const TopoDS_Face& aF)
 335 {
 336   TopAbs_Orientation anOr=TopAbs_INTERNAL;
 337
 338   TopExp_Explorer anExp;
 339   anExp.Init(aF, TopAbs_EDGE);
 340   for (; anExp.More(); anExp.Next()) {
 341     const TopoDS_Edge& anEF1=(*(TopoDS_Edge*)(&anExp.Current()));
 342     if (anEF1.IsSame(anE)) {
 343       anOr=anEF1.Orientation();
 344       break;
 345     }
 346   }
 347   return anOr;
 348 }
 349 //=======================================================================
 350 // function: MakeConnexityBlock.
 351 // purpose:
 352 //=======================================================================
 353 void BOPTools_AlgoTools::MakeConnexityBlock
 354   (BOPCol_ListOfShape& theLFIn,
 355    BOPCol_IndexedMapOfShape& theMEAvoid,
 356    BOPCol_ListOfShape& theLCB,
 357    const Handle(NCollection_BaseAllocator)& theAllocator)
 358 {
 359   Standard_Integer  aNbF, aNbAdd1, aNbAdd, i;
 360   TopExp_Explorer aExp;
 361   BOPCol_ListIteratorOfListOfShape aIt;
 362   //
 363   BOPCol_IndexedMapOfShape aMCB(100, theAllocator);
 364   BOPCol_IndexedMapOfShape aMAdd(100, theAllocator);
 365   BOPCol_IndexedMapOfShape aMAdd1(100, theAllocator);
 366   BOPCol_IndexedDataMapOfShapeListOfShape aMEF(100, theAllocator);
 367   //
 368   // 1. aMEF
 369   aNbF=theLFIn.Extent();
 370   aIt.Initialize(theLFIn);
 371   for (; aIt.More(); aIt.Next()) {
 372     const TopoDS_Shape& aF=aIt.Value();
 373     BOPTools::MapShapesAndAncestors(aF, TopAbs_EDGE, TopAbs_FACE, aMEF);
 374   }
 375   //
 376   // 2. aMCB
 377   const TopoDS_Shape& aF1=theLFIn.First();
 378   aMAdd.Add(aF1);
 379   //
 380   for(;;) {
 381     aMAdd1.Clear();
 382     aNbAdd = aMAdd.Extent();
 383     for (i=1; i<=aNbAdd; ++i) {
 384       const TopoDS_Shape& aF=aMAdd(i);
 385       //
 386       //aMAdd1.Clear();
 387       aExp.Init(aF, TopAbs_EDGE);
 388       for (; aExp.More(); aExp.Next()) {
 389         const TopoDS_Shape& aE=aExp.Current();
 390         if (theMEAvoid.Contains(aE)){
 391           continue;
 392         }
 393         //
 394         const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
 395         aIt.Initialize(aLF);
 396         for (; aIt.More(); aIt.Next()) {
 397           const TopoDS_Shape& aFx=aIt.Value();
 398           if (aFx.IsSame(aF)) {
 399             continue;
 400           }
 401           if (aMCB.Contains(aFx)) {
 402             continue;
 403           }
 404           aMAdd1.Add(aFx);
 405         }
 406       }//for (; aExp.More(); aExp.Next()){
 407       aMCB.Add(aF);
 408     }// for (i=1; i<=aNbAdd; ++i) {
 409     //
 410     aNbAdd1=aMAdd1.Extent();
 411     if (!aNbAdd1) {
 412       break;
 413     }
 414     //
 415     aMAdd.Clear();
 416     for (i=1; i<=aNbAdd1; ++i) {
 417       const TopoDS_Shape& aFAdd=aMAdd1(i);
 418       aMAdd.Add(aFAdd);
 419     }
 420     //
 421   }//while(1) {
 422
 423   //
 424   aNbF=aMCB.Extent();
 425   for (i=1; i<=aNbF; ++i) {
 426     const TopoDS_Shape& aF=aMCB(i);
 427     theLCB.Append(aF);
 428   }
 429 }
 430 //=======================================================================
 431 // function:  ComputeStateByOnePoint
 432 // purpose:
 433 //=======================================================================
 434 TopAbs_State BOPTools_AlgoTools::ComputeStateByOnePoint
 435   (const TopoDS_Shape& theS,
 436    const TopoDS_Solid& theRef,
 437    const Standard_Real theTol,
 438    Handle(IntTools_Context)& theContext)
 439 {
 440   TopAbs_State aState;
 441   TopAbs_ShapeEnum aType;
 442   //
 443   aState=TopAbs_UNKNOWN;
 444   aType=theS.ShapeType();
 445   if (aType==TopAbs_VERTEX) {
 446     const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&theS));
 447     aState=BOPTools_AlgoTools::ComputeState(aV, theRef, theTol, theContext);
 448   }
 449   else if (aType==TopAbs_EDGE) {
 450     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&theS));
 451     aState=BOPTools_AlgoTools::ComputeState(aE, theRef, theTol, theContext);
 452   }
 453   return aState;
 454 }
 455
 456 //=======================================================================
 457 // function:  ComputeState
 458 // purpose:
 459 //=======================================================================
 460 TopAbs_State BOPTools_AlgoTools::ComputeState
 461   (const TopoDS_Face& theF,
 462    const TopoDS_Solid& theRef,
 463    const Standard_Real theTol,
 464    BOPCol_IndexedMapOfShape& theBounds,
 465    Handle(IntTools_Context)& theContext)
 466 {
 467   TopAbs_State aState;
 468   TopExp_Explorer aExp;
 469   TopoDS_Edge aE1;
 470   gp_Pnt2d aP2D;
 471   gp_Pnt aP3D;
 472   //
 473   aState=TopAbs_UNKNOWN;
 474   //
 475   aExp.Init(theF, TopAbs_EDGE);
 476   for (; aExp.More(); aExp.Next()) {
 477     const TopoDS_Edge& aSE=(*(TopoDS_Edge*)(&aExp.Current()));
 478     if (BRep_Tool::Degenerated(aSE)) {
 479       continue;
 480     }
 481     //
 482     if (!theBounds.Contains(aSE)) {
 483       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aSE));
 484       aState=BOPTools_AlgoTools::ComputeState(aE, theRef, theTol,
 485                                               theContext);
 486       return aState;
 487     }
 488     if (aE1.IsNull()) {
 489       aE1=(*(TopoDS_Edge*)(&aSE));
 490     }
 491   }
 492   // !!<- process edges that are all on theRef
 493   if (!aE1.IsNull()) {
 494     BOPTools_AlgoTools3D::PointNearEdge(aE1, theF,
 495                                         aP2D, aP3D, theContext);
 496     aState=BOPTools_AlgoTools::ComputeState(aP3D, theRef, theTol,
 497                                             theContext);
 498   }
 499   //
 500   return aState;
 501 }
 502 //=======================================================================
 503 // function:  ComputeState
 504 // purpose:
 505 //=======================================================================
 506 TopAbs_State BOPTools_AlgoTools::ComputeState
 507   (const TopoDS_Vertex& theV,
 508    const TopoDS_Solid& theRef,
 509    const Standard_Real theTol,
 510    Handle(IntTools_Context)& theContext)
 511 {
 512   TopAbs_State aState;
 513   gp_Pnt aP3D;
 514   //
 515   aP3D=BRep_Tool::Pnt(theV);
 516   aState=BOPTools_AlgoTools::ComputeState(aP3D, theRef, theTol,
 517                                           theContext);
 518   return aState;
 519 }
 520 //=======================================================================
 521 // function:  ComputeState
 522 // purpose:
 523 //=======================================================================
 524 TopAbs_State BOPTools_AlgoTools::ComputeState
 525   (const TopoDS_Edge& theE,
 526    const TopoDS_Solid& theRef,
 527    const Standard_Real theTol,
 528    Handle(IntTools_Context)& theContext)
 529 {
 530   Standard_Real aT1, aT2, aT = 0.;
 531   TopAbs_State aState;
 532   Handle(Geom_Curve) aC3D;
 533   gp_Pnt aP3D;
 534   //
 535   aC3D = BRep_Tool::Curve(theE, aT1, aT2);
 536   //
 537   if(aC3D.IsNull()) {
 538     //it means that we are in degenerated edge
 539     const TopoDS_Vertex& aV = TopExp::FirstVertex(theE);
 540     if(aV.IsNull()){
 541       return TopAbs_UNKNOWN;
 542     }
 543     aP3D=BRep_Tool::Pnt(aV);
 544   }
 545   else {//usual case
 546     Standard_Boolean bF2Inf, bL2Inf;
 547     Standard_Real dT=10.;
 548     //
 549     bF2Inf = Precision::IsNegativeInfinite(aT1);
 550     bL2Inf = Precision::IsPositiveInfinite(aT2);
 551     //
 552     if (bF2Inf && !bL2Inf) {
 553       aT=aT2-dT;
 554     }
 555     else if (!bF2Inf && bL2Inf) {
 556       aT=aT1+dT;
 557     }
 558     else if (bF2Inf && bL2Inf) {
 559       aT=0.;
 560     }
 561     else {
 562       aT=IntTools_Tools::IntermediatePoint(aT1, aT2);
 563     }
 564     aC3D->D0(aT, aP3D);
 565   }
 566   //
 567   aState=BOPTools_AlgoTools::ComputeState(aP3D, theRef, theTol,
 568                                           theContext);
 569   //
 570   return aState;
 571 }
 572 //=======================================================================
 573 // function:  ComputeState
 574 // purpose:
 575 //=======================================================================
 576 TopAbs_State BOPTools_AlgoTools::ComputeState
 577   (const gp_Pnt& theP,
 578    const TopoDS_Solid& theRef,
 579    const Standard_Real theTol,
 580    Handle(IntTools_Context)& theContext)
 581 {
 582   TopAbs_State aState;
 583   //
 584   BRepClass3d_SolidClassifier& aSC=theContext->SolidClassifier(theRef);
 585   aSC.Perform(theP, theTol);
 586   //
 587   aState=aSC.State();
 588   //
 589   return aState;
 590 }
 591 //=======================================================================
 592 //function : IsInternalFace
 593 //purpose  :
 594 //=======================================================================
 595 Standard_Boolean BOPTools_AlgoTools::IsInternalFace
 596   (const TopoDS_Face& theFace,
 597    const TopoDS_Solid& theSolid,
 598    BOPCol_IndexedDataMapOfShapeListOfShape& theMEF,
 599    const Standard_Real theTol,
 600    Handle(IntTools_Context)& theContext)
 601 {
 602   Standard_Boolean bDegenerated;
 603   Standard_Integer aNbF, iRet, iFound;
 604   TopAbs_Orientation aOr;
 605   TopoDS_Edge aE1;
 606   TopExp_Explorer aExp;
 607   BOPCol_ListIteratorOfListOfShape aItF;
 608   //
 609   // For all invoked functions: [::IsInternalFace(...)]
 610   // the returned value iRet means:
 611   // iRet=0;  - state is not IN
 612   // iRet=1;  - state is IN
 613   // iRet=2;  - state can not be found by the method of angles
 614   //
 615   // For this function the returned value iRet means:
 616   // iRet=0;  - state is not IN
 617   // iRet=1;  - state is IN
 618   //
 619   iRet=0;
 620   // 1 Try to find an edge from theFace in theMEF
 621   iFound=0;
 622   aExp.Init(theFace, TopAbs_EDGE);
 623   for(; aExp.More(); aExp.Next()) {
 624     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
 625     if (!theMEF.Contains(aE)) {
 626       continue;
 627     }
 628     //
 629     ++iFound;
 630     //
 631     aOr=aE.Orientation();
 632     if (aOr==TopAbs_INTERNAL) {
 633       continue;
 634     }
 635     bDegenerated=BRep_Tool::Degenerated(aE);
 636     if (bDegenerated){
 637       continue;
 638     }
 639     // aE
 640     BOPCol_ListOfShape& aLF=theMEF.ChangeFromKey(aE);
 641     aNbF=aLF.Extent();
 642     if (!aNbF) {
 643       return iRet != 0; // it can not be so
 644     }
 645     //
 646     else if (aNbF==1) {
 647       // aE is internal edge on aLF.First()
 648       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
 649       BOPTools_AlgoTools::GetEdgeOnFace(aE, aF1, aE1);
 650       if (aE1.Orientation()!=TopAbs_INTERNAL) {
 651         iRet=2;
 652         break;
 653       }
 654       //
 655       iRet=BOPTools_AlgoTools::IsInternalFace(theFace, aE, aF1, aF1,
 656                                               theContext);
 657       break;
 658     }
 659     //
 660     else if (aNbF==2) {
 661       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
 662       const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
 663       //
 664       if (aF2.IsSame(aF1) && BRep_Tool::IsClosed(aE, aF1)) {
 665         // treat as it was for 1 face
 666         iRet=BOPTools_AlgoTools::IsInternalFace(theFace, aE, aF1, aF2,
 667                                                 theContext);
 668         break;
 669       }
 670     }
 671     //
 672     if (aNbF%2) {
 673       return Standard_False; // it can not be so
 674     }
 675     else { // aNbF=2,4,6,8,...
 676       iRet=BOPTools_AlgoTools::IsInternalFace(theFace, aE, aLF,
 677                                               theContext);
 678       break;
 679     }
 680   }//for(; aExp.More(); aExp.Next()) {
 681   //
 682   if (!iFound) {
 683     // the face has no shared edges with the solid
 684     iRet=2;
 685   }
 686   //
 687   if (iRet!=2) {
 688     return iRet == 1;
 689   }
 690   //
 691   //========================================
 692   // 2. Classify face using classifier
 693   //
 694   TopAbs_State aState;
 695   BOPCol_IndexedMapOfShape aBounds;
 696   //
 697   BOPTools::MapShapes(theSolid, TopAbs_EDGE, aBounds);
 698   //
 699   aState=BOPTools_AlgoTools::ComputeState(theFace, theSolid,
 700                                           theTol, aBounds, theContext);
 701   return aState == TopAbs_IN;
 702 }
 703 //=======================================================================
 704 //function : IsInternalFace
 705 //purpose  :
 706 //=======================================================================
 707 Standard_Integer BOPTools_AlgoTools::IsInternalFace
 708   (const TopoDS_Face& theFace,
 709    const TopoDS_Edge& theEdge,
 710    BOPCol_ListOfShape& theLF,
 711    Handle(IntTools_Context)& theContext)
 712 {
 713   Standard_Integer aNbF, iRet;
 714   //
 715   iRet=0;
 716   //
 717   aNbF=theLF.Extent();
 718   if (aNbF==2) {
 719     const TopoDS_Face& aF1=(*(TopoDS_Face*)(&theLF.First()));
 720     const TopoDS_Face& aF2=(*(TopoDS_Face*)(&theLF.Last()));
 721     iRet=BOPTools_AlgoTools::IsInternalFace(theFace, theEdge, aF1, aF2,
 722                                             theContext);
 723     return iRet;
 724   }
 725   //
 726   else {
 727     BOPTools_ListOfCoupleOfShape aLCFF;
 728     BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
 729     //
 730     FindFacePairs(theEdge, theLF, aLCFF, theContext);
 731     //
 732     aIt.Initialize(aLCFF);
 733     for (; aIt.More(); aIt.Next()) {
 734       BOPTools_CoupleOfShape& aCSFF=aIt.ChangeValue();
 735       //
 736       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aCSFF.Shape1()));
 737       const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aCSFF.Shape2()));
 738       iRet=BOPTools_AlgoTools::IsInternalFace(theFace, theEdge, aF1, aF2,
 739                                               theContext);
 740       if (iRet) {
 741         return iRet;
 742       }
 743     }
 744   }
 745   return iRet;
 746 }
 747 //=======================================================================
 748 //function : IsInternalFace
 749 //purpose  :
 750 //=======================================================================
 751 Standard_Integer BOPTools_AlgoTools::IsInternalFace
 752   (const TopoDS_Face& theFace,
 753    const TopoDS_Edge& theEdge,
 754    const TopoDS_Face& theFace1,
 755    const TopoDS_Face& theFace2,
 756    Handle(IntTools_Context)& theContext)
 757 {
 758   Standard_Boolean bRet;
 759   Standard_Integer iRet;
 760   TopoDS_Edge aE1, aE2;
 761   TopoDS_Face aFOff;
 762   BOPTools_ListOfCoupleOfShape theLCSOff;
 763   BOPTools_CoupleOfShape aCS1, aCS2;
 764   //
 765   BOPTools_AlgoTools::GetEdgeOnFace(theEdge, theFace1, aE1);
 766   if (aE1.Orientation()==TopAbs_INTERNAL) {
 767     aE2=aE1;
 768     aE1.Orientation(TopAbs_FORWARD);
 769     aE2.Orientation(TopAbs_REVERSED);
 770   }
 771   else if (theFace1==theFace2) {
 772     aE2=aE1;
 773     aE1.Orientation(TopAbs_FORWARD);
 774     aE2.Orientation(TopAbs_REVERSED);
 775   }
 776   else {
 777     BOPTools_AlgoTools::GetEdgeOnFace(theEdge, theFace2, aE2);
 778   }
 779   //
 780   aCS1.SetShape1(theEdge);
 781   aCS1.SetShape2(theFace);
 782   theLCSOff.Append(aCS1);
 783   //
 784   aCS2.SetShape1(aE2);
 785   aCS2.SetShape2(theFace2);
 786   theLCSOff.Append(aCS2);
 787   //
 788   bRet=GetFaceOff(aE1, theFace1, theLCSOff, aFOff, theContext);
 789   //
 790   iRet=0; // theFace is not internal
 791   if (theFace.IsEqual(aFOff)) {
 792     // theFace is internal
 793     iRet=1;
 794     if (!bRet) {
 795       // theFace seems to be internal
 796       iRet=2;
 797     }
 798   }
 799   return iRet;
 800 }
 801 //=======================================================================
 802 //function : GetFaceOff
 803 //purpose  :
 804 //=======================================================================
 805 Standard_Boolean BOPTools_AlgoTools::GetFaceOff
 806   (const TopoDS_Edge& theE1,
 807    const TopoDS_Face& theF1,
 808    BOPTools_ListOfCoupleOfShape& theLCSOff,
 809    TopoDS_Face& theFOff,
 810    Handle(IntTools_Context)& theContext)
 811 {
 812   Standard_Boolean bRet;
 813   Standard_Real aT, aT1, aT2, aAngle, aTwoPI, aAngleMin, aDt3D;
 814   Standard_Real aUmin, aUsup, aVmin, aVsup, aPA;
 815   gp_Pnt aPn1, aPn2, aPx;
 816   gp_Dir aDN1, aDN2, aDBF, aDBF2, aDTF;
 817   gp_Vec aVTgt;
 818   TopAbs_Orientation aOr;
 819   Handle(Geom_Curve)aC3D;
 820   Handle(Geom_Plane) aPL;
 821   BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
 822   GeomAPI_ProjectPointOnSurf aProjPL;
 823   //
 824   aPA=Precision::Angular();
 825   aAngleMin=100.;
 826   aTwoPI=M_PI+M_PI;
 827   aC3D =BRep_Tool::Curve(theE1, aT1, aT2);
 828   aT=BOPTools_AlgoTools2D::IntermediatePoint(aT1, aT2);
 829   aC3D->D0(aT, aPx);
 830   //
 831   BOPTools_AlgoTools2D::EdgeTangent(theE1, aT, aVTgt);
 832   gp_Dir aDTgt(aVTgt), aDTgt2;
 833   aOr = theE1.Orientation();
 834   //
 835   aPL = new Geom_Plane(aPx, aDTgt);
 836   aPL->Bounds(aUmin, aUsup, aVmin, aVsup);
 837   aProjPL.Init(aPL, aUmin, aUsup, aVmin, aVsup);
 838   //
 839   aDt3D = MinStep3D(theE1, theF1, theLCSOff, aPx);
 840   GetFaceDir(theE1, theF1, aPx, aT, aDTgt, aDN1, aDBF, theContext,
 841              aProjPL, aDt3D);
 842   //
 843   aDTF=aDN1^aDBF;
 844   //
 845   bRet=Standard_True;
 846   aIt.Initialize(theLCSOff);
 847   for (; aIt.More(); aIt.Next()) {
 848     const BOPTools_CoupleOfShape& aCS=aIt.Value();
 849     const TopoDS_Edge& aE2=(*(TopoDS_Edge*)(&aCS.Shape1()));
 850     const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aCS.Shape2()));
 851     //
 852     aDTgt2 = (aE2.Orientation()==aOr) ? aDTgt : aDTgt.Reversed();
 853     GetFaceDir(aE2, aF2, aPx, aT, aDTgt2, aDN2, aDBF2, theContext,
 854                aProjPL, aDt3D);
 855     //Angle
 856     aAngle=AngleWithRef(aDBF, aDBF2, aDTF);
 857     //
 858     if(aAngle<0.) {
 859       aAngle=aTwoPI+aAngle;
 860     }
 861     //
 862     if (aAngle<aPA) {
 863       if (aF2==theF1) {
 864         aAngle=M_PI;
 865       }
 866       else if (aF2.IsSame(theF1)) {
 867         aAngle=aTwoPI;
 868       }
 869     }
 870     //
 871     if (fabs(aAngle-aAngleMin)<aPA) {
 872       // the minimal angle can not be found
 873       bRet=Standard_False;
 874     }
 875     //
 876     if (aAngle<aAngleMin){
 877       aAngleMin=aAngle;
 878       theFOff=aF2;
 879     }
 880     else if (aAngle==aAngleMin) {
 881       // the minimal angle can not be found
 882       bRet=Standard_False;
 883     }
 884   }
 885   return bRet;
 886 }
 887 //=======================================================================
 888 //function : GetEdgeOff
 889 //purpose  :
 890 //=======================================================================
 891 Standard_Boolean BOPTools_AlgoTools::GetEdgeOff(const TopoDS_Edge& theE1,
 892                                                 const TopoDS_Face& theF2,
 893                                                 TopoDS_Edge& theE2)
 894 {
 895   Standard_Boolean bFound;
 896   TopAbs_Orientation aOr1, aOr1C, aOr2;
 897   TopExp_Explorer anExp;
 898   //
 899   bFound=Standard_False;
 900   aOr1=theE1.Orientation();
 901   aOr1C=TopAbs::Reverse(aOr1);
 902   //
 903   anExp.Init(theF2, TopAbs_EDGE);
 904   for (; anExp.More(); anExp.Next()) {
 905     const TopoDS_Edge& aEF2=(*(TopoDS_Edge*)(&anExp.Current()));
 906     if (aEF2.IsSame(theE1)) {
 907       aOr2=aEF2.Orientation();
 908       if (aOr2==aOr1C) {
 909         theE2=aEF2;
 910         bFound=!bFound;
 911         return bFound;
 912       }
 913     }
 914   }
 915   return bFound;
 916 }
 917
 918 //=======================================================================
 919 //function : AreFacesSameDomain
 920 //purpose  :
 921 //=======================================================================
 922 Standard_Boolean BOPTools_AlgoTools::AreFacesSameDomain
 923   (const TopoDS_Face& theF1,
 924    const TopoDS_Face& theF2,
 925    Handle(IntTools_Context)& theContext,
 926    const Standard_Real theFuzz)
 927 {
 928   Standard_Boolean bFlag;
 929   Standard_Integer iErr;
 930   Standard_Real aTolF1, aTolF2, aTol;
 931   gp_Pnt2d aP2D;
 932   gp_Pnt aP;
 933   TopoDS_Face aF1, aF2;
 934   TopoDS_Edge aE1;
 935   TopExp_Explorer aExp;
 936   Standard_Real aFuzz1 = (theFuzz > Precision::Confusion() ? theFuzz : Precision::Confusion());
 937   //
 938   bFlag=Standard_False;
 939   //
 940   aF1=theF1;
 941   aF1.Orientation(TopAbs_FORWARD);
 942   aF2=theF2;
 943   aF2.Orientation(TopAbs_FORWARD);
 944   //
 945   aTolF1=BRep_Tool::Tolerance(aF1);
 946   // 1
 947   aExp.Init(aF1, TopAbs_EDGE);
 948   for (; aExp.More(); aExp.Next()) {
 949     aE1=(*(TopoDS_Edge*)(&aExp.Current()));
 950     if (!BRep_Tool::Degenerated(aE1)) {
 951       Standard_Real aTolE = BRep_Tool::Tolerance(aE1);
 952       if (aTolE > aTolF1) {
 953         aTolF1 = aTolE;
 954       }
 955     }
 956   }
 957   // 2
 958   aTolF2=BRep_Tool::Tolerance(aF2);
 959   aTol = aTolF1 + aTolF2 + aFuzz1;
 960   //
 961   iErr = BOPTools_AlgoTools3D::PointInFace(aF1, aP, aP2D,
 962                                            theContext);
 963   if (!iErr) {
 964     bFlag=theContext->IsValidPointForFace(aP, aF2, aTol);
 965   }
 966   //
 967   return bFlag;
 968 }
 969
 970 //=======================================================================
 971 //function : CheckSameGeom
 972 //purpose  :
 973 //=======================================================================
 974 Standard_Boolean BOPTools_AlgoTools::CheckSameGeom
 975   (const TopoDS_Face& theF1,
 976    const TopoDS_Face& theF2,
 977    Handle(IntTools_Context)& theContext)
 978 {
 979   Standard_Boolean bRet;
 980   Standard_Real aTolF1, aTolF2, aTol;
 981   gp_Pnt2d aP2D;
 982   gp_Pnt aP;
 983   TopExp_Explorer aExp;
 984   //
 985   bRet=Standard_False;
 986   aExp.Init(theF1, TopAbs_EDGE);
 987   for (; aExp.More(); aExp.Next()) {
 988     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
 989     if (!BRep_Tool::Degenerated(aE)) {
 990       aTolF1=BRep_Tool::Tolerance(theF1);
 991       aTolF2=BRep_Tool::Tolerance(theF2);
 992       aTol=aTolF1+aTolF2;
 993       BOPTools_AlgoTools3D::PointNearEdge(aE, theF1, aP2D, aP, theContext);
 994       bRet=theContext->IsValidPointForFace(aP, theF2, aTol);
 995       break;
 996     }
 997   }
 998   return bRet;
 999 }
1000 //=======================================================================
1001 // function: Sense
1002 // purpose:
1003 //=======================================================================
1004 Standard_Integer BOPTools_AlgoTools::Sense (const TopoDS_Face& theF1,
1005                                             const TopoDS_Face& theF2)
1006 {
1007   Standard_Integer iSense=0;
1008   gp_Dir aDNF1, aDNF2;
1009   TopoDS_Edge aE1, aE2;
1010   TopExp_Explorer aExp;
1011   //
1012   aExp.Init(theF1, TopAbs_EDGE);
1013   for (; aExp.More(); aExp.Next()) {
1014     aE1=(*(TopoDS_Edge*)(&aExp.Current()));
1015     if (!BRep_Tool::Degenerated(aE1)) {
1016       if (!BRep_Tool::IsClosed(aE1, theF1)) {
1017         break;
1018       }
1019     }
1020   }
1021   //
1022   aExp.Init(theF2, TopAbs_EDGE);
1023   for (; aExp.More(); aExp.Next()) {
1024     aE2=(*(TopoDS_Edge*)(&aExp.Current()));
1025     if (!BRep_Tool::Degenerated(aE2)) {
1026       if (!BRep_Tool::IsClosed(aE2, theF2)) {
1027         if (aE2.IsSame(aE1)) {
1028           iSense=1;
1029           break;
1030         }
1031       }
1032     }
1033   }
1034   //
1035   if (!iSense) {
1036     return iSense;
1037   }
1038   //
1039   BOPTools_AlgoTools3D::GetNormalToFaceOnEdge(aE1, theF1, aDNF1);
1040   BOPTools_AlgoTools3D::GetNormalToFaceOnEdge(aE2, theF2, aDNF2);
1041   //
1042   iSense=BOPTools_AlgoTools3D::SenseFlag(aDNF1, aDNF2);
1043   //
1044   return iSense;
1045 }
1046 //=======================================================================
1047 // function: IsSplitToReverse
1048 // purpose:
1049 //=======================================================================
1050 Standard_Boolean BOPTools_AlgoTools::IsSplitToReverse
1051   (const TopoDS_Shape& theSp,
1052    const TopoDS_Shape& theSr,
1053    Handle(IntTools_Context)& theContext)
1054 {
1055   Standard_Boolean bRet;
1056   TopAbs_ShapeEnum aType;
1057   //
1058   bRet=Standard_False;
1059   //
1060   aType=theSp.ShapeType();
1061   switch (aType) {
1062     case TopAbs_EDGE: {
1063       const TopoDS_Edge& aESp=(*(TopoDS_Edge*)(&theSp));
1064       const TopoDS_Edge& aESr=(*(TopoDS_Edge*)(&theSr));
1065       bRet=BOPTools_AlgoTools::IsSplitToReverse(aESp, aESr, theContext);
1066     }
1067       break;
1068       //
1069     case TopAbs_FACE: {
1070       const TopoDS_Face& aFSp=(*(TopoDS_Face*)(&theSp));
1071       const TopoDS_Face& aFSr=(*(TopoDS_Face*)(&theSr));
1072       bRet=BOPTools_AlgoTools::IsSplitToReverse(aFSp, aFSr, theContext);
1073     }
1074       break;
1075       //
1076     default:
1077       break;
1078   }
1079   return bRet;
1080 }
1081 //=======================================================================
1082 //function :IsSplitToReverse
1083 //purpose  :
1084 //=======================================================================
1085 Standard_Boolean BOPTools_AlgoTools::IsSplitToReverse
1086   (const TopoDS_Face& theFSp,
1087    const TopoDS_Face& theFSr,
1088    Handle(IntTools_Context)& theContext)
1089 {
1090   Standard_Boolean bRet, bFound, bInFace;
1091   Standard_Real aT1, aT2, aT, aU, aV, aScPr;
1092   gp_Pnt aPFSp, aPFSr;
1093   gp_Dir aDNFSp;
1094   gp_Vec aD1U, aD1V;
1095   Handle(Geom_Surface) aSr, aSp;
1096   TopAbs_Orientation aOrSr, aOrSp;
1097   TopExp_Explorer anExp;
1098   TopoDS_Edge aESp;
1099   //
1100   bRet=Standard_False;
1101   //
1102   aSr=BRep_Tool::Surface(theFSr);
1103   aSp=BRep_Tool::Surface(theFSp);
1104   if (aSr==aSp) {
1105     aOrSr=theFSr.Orientation();
1106     aOrSp=theFSp.Orientation();
1107     bRet=(aOrSr!=aOrSp);
1108     return bRet;
1109   }
1110   //
1111   bFound=Standard_False;
1112   anExp.Init(theFSp, TopAbs_EDGE);
1113   for (; anExp.More(); anExp.Next()) {
1114     aESp=(*(TopoDS_Edge*)(&anExp.Current()));
1115     if (!BRep_Tool::Degenerated(aESp)) {
1116       if (!BRep_Tool::IsClosed(aESp, theFSp)) {
1117         bFound=!bFound;
1118         break;
1119       }
1120     }
1121   }
1122   if (!bFound) {
1123     Standard_Boolean bFlag;
1124     Standard_Integer iErr;
1125     gp_Pnt2d aP2DFSp;
1126     //
1127     iErr=BOPTools_AlgoTools3D::PointInFace(theFSp, aPFSp, aP2DFSp,
1128                                            theContext);
1129     if (iErr) {
1130       return bRet;
1131     }
1132     //
1133     aP2DFSp.Coord(aU, aV);
1134     bFlag=BOPTools_AlgoTools3D::GetNormalToSurface(aSp, aU, aV, aDNFSp);
1135     if (!bFlag) {
1136       return bRet;
1137     }
1138     //
1139     if (theFSp.Orientation()==TopAbs_REVERSED){
1140       aDNFSp.Reverse();
1141     }
1142   }
1143   else {
1144     BRep_Tool::Range(aESp, aT1, aT2);
1145     aT=BOPTools_AlgoTools2D::IntermediatePoint(aT1, aT2);
1146     BOPTools_AlgoTools3D::GetApproxNormalToFaceOnEdge(aESp, theFSp, aT,
1147                                                       aPFSp, aDNFSp,
1148                                                       theContext);
1149   }
1150   //
1151   // Parts of theContext->ComputeVS(..)
1152   GeomAPI_ProjectPointOnSurf& aProjector=theContext->ProjPS(theFSr);
1153   aProjector.Perform(aPFSp);
1154   if (!aProjector.IsDone()) {
1155     return bRet;
1156   }
1157   //
1158   aProjector.LowerDistanceParameters(aU, aV);
1159   gp_Pnt2d aP2D(aU, aV);
1160   bInFace=theContext->IsPointInOnFace (theFSr, aP2D);
1161   if (!bInFace) {
1162     return bRet;
1163   }
1164   //
1165   aSr->D1(aU, aV, aPFSr, aD1U, aD1V);
1166   gp_Dir aDD1U(aD1U);
1167   gp_Dir aDD1V(aD1V);
1168   gp_Dir aDNFSr=aDD1U^aDD1V;
1169   if (theFSr.Orientation()==TopAbs_REVERSED){
1170     aDNFSr.Reverse();
1171   }
1172   //
1173   aScPr=aDNFSp*aDNFSr;
1174   bRet=(aScPr<0.);
1175   //
1176   return bRet;
1177 }
1178 //=======================================================================
1179 //function :IsSplitToReverse
1180 //purpose  :
1181 //=======================================================================
1182 Standard_Boolean BOPTools_AlgoTools::IsSplitToReverse
1183   (const TopoDS_Edge& aEF1,
1184    const TopoDS_Edge& aEF2,
1185    Handle(IntTools_Context)& theContext)
1186 {
1187   Standard_Boolean bRet, bIsDegenerated;
1188   //
1189   bRet=Standard_False;
1190   bIsDegenerated=(BRep_Tool::Degenerated(aEF1) ||
1191                   BRep_Tool::Degenerated(aEF2));
1192   if (bIsDegenerated) {
1193     return bRet;
1194   }
1195   //
1196   Standard_Real a, b;
1197   TopAbs_Orientation aOrE, aOrSp;
1198   Handle(Geom_Curve)aC1, aC2;
1199   //
1200   aC2=BRep_Tool::Curve(aEF2, a, b);
1201   aC1=BRep_Tool::Curve(aEF1, a, b);
1202   //
1203   if (aC1==aC2) {
1204     aOrE=aEF2.Orientation();
1205     aOrSp=aEF1.Orientation();
1206     bRet=(aOrE!=aOrSp);
1207     return bRet;
1208   }
1209   //
1210   Standard_Real aT1, aT2, aScPr;
1211   gp_Vec aV1, aV2;
1212   gp_Pnt aP;
1213   //
1214   aT1=BOPTools_AlgoTools2D::IntermediatePoint(a, b);
1215   aC1->D0(aT1, aP);
1216   BOPTools_AlgoTools2D::EdgeTangent(aEF1, aT1, aV1);
1217   gp_Dir aDT1(aV1);
1218   //
1219   theContext->ProjectPointOnEdge(aP, aEF2, aT2);
1220   //
1221   BOPTools_AlgoTools2D::EdgeTangent(aEF2, aT2, aV2);
1222   gp_Dir aDT2(aV2);
1223   //
1224   aScPr=aDT1*aDT2;
1225   bRet=(aScPr<0.);
1226   //
1227   return bRet;
1228 }
1229
1230 //=======================================================================
1231 //function : IsHole
1232 //purpose  :
1233 //=======================================================================
1234 Standard_Boolean BOPTools_AlgoTools::IsHole(const TopoDS_Shape& aW,
1235                                             const TopoDS_Shape& aFace)
1236 {
1237   Standard_Boolean bIsHole;
1238   Standard_Integer i, aNbS;
1239   Standard_Real aT1, aT2, aS;
1240   Standard_Real aU1, aU, dU;
1241   Standard_Real aX1, aY1, aX0, aY0;
1242   TopAbs_Orientation aOr;
1243
1244   gp_Pnt2d aP2D0, aP2D1;
1245   Handle(Geom2d_Curve) aC2D;
1246   TopoDS_Face aF, aFF;
1247   TopoDS_Iterator aItW;
1248   //
1249   bIsHole=Standard_False;
1250   //
1251   aF=(*(TopoDS_Face *)(&aFace));
1252   aFF=aF;
1253   aFF.Orientation(TopAbs_FORWARD);
1254   //
1255   aS=0.;
1256   aItW.Initialize(aW);
1257   for (; aItW.More(); aItW.Next()) {
1258     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
1259     aOr=aE.Orientation();
1260     if (!(aOr==TopAbs_FORWARD ||
1261           aOr==TopAbs_REVERSED)) {
1262       continue;
1263     }
1264     //
1265     aC2D=BRep_Tool::CurveOnSurface(aE, aFF, aT1, aT2);
1266     if (aC2D.IsNull()) {
1267       break; //xx
1268     }
1269     //
1270     BRepAdaptor_Curve2d aBAC2D(aE, aFF);
1271     aNbS=Geom2dInt_Geom2dCurveTool::NbSamples(aBAC2D);
1272     if (aNbS>2) {
1273       aNbS*=4;
1274     }
1275     //
1276     dU=(aT2-aT1)/(Standard_Real)(aNbS-1);
1277     aU =aT1;
1278     aU1=aT1;
1279     if (aOr==TopAbs_REVERSED) {
1280       aU =aT2;
1281       aU1=aT2;
1282       dU=-dU;
1283     }
1284     //
1285     aBAC2D.D0(aU, aP2D0);
1286     for(i=2; i<=aNbS; i++) {
1287       aU=aU1+(i-1)*dU;
1288       aBAC2D.D0(aU, aP2D1);
1289       aP2D0.Coord(aX0, aY0);
1290       aP2D1.Coord(aX1, aY1);
1291       //
1292       aS=aS+(aY0+aY1)*(aX1-aX0);
1293       //
1294       aP2D0=aP2D1;
1295     }
1296   }//for (; aItW.More(); aItW.Next()) {
1297   bIsHole=(aS>0.);
1298   return bIsHole;
1299 }
1300
1301 //=======================================================================
1302 // function: MakeContainer
1303 // purpose:
1304 //=======================================================================
1305 void BOPTools_AlgoTools::MakeContainer(const TopAbs_ShapeEnum theType,
1306                                        TopoDS_Shape& theC)
1307 {
1308   BRep_Builder aBB;
1309   //
1310   switch(theType) {
1311     case TopAbs_COMPOUND:{
1312       TopoDS_Compound aC;
1313       aBB.MakeCompound(aC);
1314       theC=aC;
1315     }
1316       break;
1317       //
1318     case TopAbs_COMPSOLID:{
1319       TopoDS_CompSolid aCS;
1320       aBB.MakeCompSolid(aCS);
1321       theC=aCS;
1322     }
1323       break;
1324       //
1325     case TopAbs_SOLID:{
1326       TopoDS_Solid aSolid;
1327       aBB.MakeSolid(aSolid);
1328       theC=aSolid;
1329     }
1330       break;
1331       //
1332       //
1333     case TopAbs_SHELL:{
1334       TopoDS_Shell aShell;
1335       aBB.MakeShell(aShell);
1336       theC=aShell;
1337     }
1338       break;
1339       //
1340     case TopAbs_WIRE: {
1341       TopoDS_Wire aWire;
1342       aBB.MakeWire(aWire);
1343       theC=aWire;
1344     }
1345       break;
1346       //
1347     default:
1348       break;
1349   }
1350 }
1351 //=======================================================================
1352 // function: MakePCurve
1353 // purpose:
1354 //=======================================================================
1355 void BOPTools_AlgoTools::MakePCurve(const TopoDS_Edge& aE,
1356                                     const TopoDS_Face& aF1,
1357                                     const TopoDS_Face& aF2,
1358                                     const IntTools_Curve& aIC,
1359                                     const Standard_Boolean bPC1,
1360                                     const Standard_Boolean bPC2)
1361
1362 {
1363   Standard_Integer i;
1364   Standard_Real aTolE, aT1, aT2, aOutFirst, aOutLast, aOutTol;
1365   Handle(Geom2d_Curve) aC2D, aC2DA, aC2Dx1;
1366   TopoDS_Face aFFWD;
1367   BRep_Builder aBB;
1368   Standard_Boolean bPC;
1369   //
1370   aTolE=BRep_Tool::Tolerance(aE);
1371   //
1372   const Handle(Geom_Curve)& aC3DE=BRep_Tool::Curve(aE, aT1, aT2);
1373   Handle(Geom_TrimmedCurve)aC3DETrim=
1374     new Geom_TrimmedCurve(aC3DE, aT1, aT2);
1375   //
1376   for (i=0; i<2; ++i) {
1377     bPC = !i ? bPC1 : bPC2;
1378     if (!bPC) {
1379       continue;
1380     }
1381     //
1382     if (!i) {
1383       aFFWD=aF1;
1384       aC2Dx1=aIC.FirstCurve2d();
1385     }
1386     else {
1387       aFFWD=aF2;
1388       aC2Dx1=aIC.SecondCurve2d();
1389     }
1390     //
1391     aFFWD.Orientation(TopAbs_FORWARD);
1392     //
1393     aC2D=aC2Dx1;
1394     if (aC2D.IsNull()) {
1395       BOPTools_AlgoTools2D::BuildPCurveForEdgeOnFace(aE, aFFWD);
1396       BOPTools_AlgoTools2D::CurveOnSurface(aE, aFFWD, aC2D,
1397                                        aOutFirst, aOutLast,
1398                                        aOutTol);
1399       }
1400     //
1401     if (aC3DE->IsPeriodic()) {
1402       BOPTools_AlgoTools2D::AdjustPCurveOnFace(aFFWD, aT1, aT2,  aC2D,
1403                                                aC2DA);
1404     }
1405     else {
1406       BOPTools_AlgoTools2D::AdjustPCurveOnFace(aFFWD, aC3DETrim, aC2D,
1407                                                aC2DA);
1408     }
1409     //
1410     aBB.UpdateEdge(aE, aC2DA, aFFWD, aTolE);
1411     //BRepLib::SameParameter(aE);
1412   }
1413   BRepLib::SameParameter(aE);
1414 }
1415 //=======================================================================
1416 // function: MakeEdge
1417 // purpose:
1418 //=======================================================================
1419 void BOPTools_AlgoTools::MakeEdge(const IntTools_Curve& theIC,
1420                                   const TopoDS_Vertex& theV1,
1421                                   const Standard_Real theT1,
1422                                   const TopoDS_Vertex& theV2,
1423                                   const Standard_Real theT2,
1424                                   const Standard_Real theTolR3D,
1425                                   TopoDS_Edge& theE)
1426 {
1427   BRep_Builder aBB;
1428   Standard_Real aNeedTol = theTolR3D + 1e-12;
1429   //
1430   aBB.UpdateVertex(theV1, aNeedTol);
1431   aBB.UpdateVertex(theV2, aNeedTol);
1432   //
1433   BOPTools_AlgoTools::MakeSectEdge (theIC, theV1, theT1, theV2, theT2,
1434                                     theE);
1435   //
1436   aBB.UpdateEdge(theE, theTolR3D);
1437 }
1438 //=======================================================================
1439 // function: ComputeVV
1440 // purpose:
1441 //=======================================================================
1442 Standard_Integer BOPTools_AlgoTools::ComputeVV(const TopoDS_Vertex& aV1,
1443                                                const gp_Pnt& aP2,
1444                                                const Standard_Real aTolP2)
1445 {
1446   Standard_Real aTolV1, aTolSum, aTolSum2, aD2;
1447   gp_Pnt aP1;
1448   //
1449   aTolV1=BRep_Tool::Tolerance(aV1);
1450
1451   aTolSum = aTolV1 + aTolP2 + Precision::Confusion();
1452   aTolSum2=aTolSum*aTolSum;
1453   //
1454   aP1=BRep_Tool::Pnt(aV1);
1455   //
1456   aD2=aP1.SquareDistance(aP2);
1457   if (aD2>aTolSum2) {
1458     return 1;
1459   }
1460   return 0;
1461 }
1462 //=======================================================================
1463 // function: ComputeVV
1464 // purpose:
1465 //=======================================================================
1466 Standard_Integer BOPTools_AlgoTools::ComputeVV(const TopoDS_Vertex& aV1,
1467                                                const TopoDS_Vertex& aV2,
1468                                                const Standard_Real aFuzz)
1469 {
1470   Standard_Real aTolV1, aTolV2, aTolSum, aTolSum2, aD2;
1471   gp_Pnt aP1, aP2;
1472   Standard_Real aFuzz1 = (aFuzz > Precision::Confusion() ? aFuzz : Precision::Confusion());
1473   //
1474   aTolV1=BRep_Tool::Tolerance(aV1);
1475   aTolV2=BRep_Tool::Tolerance(aV2);
1476   aTolSum=aTolV1+aTolV2+aFuzz1;
1477   aTolSum2=aTolSum*aTolSum;
1478   //
1479   aP1=BRep_Tool::Pnt(aV1);
1480   aP2=BRep_Tool::Pnt(aV2);
1481   //
1482   aD2=aP1.SquareDistance(aP2);
1483   if (aD2>aTolSum2) {
1484     return 1;
1485   }
1486   return 0;
1487 }
1488 //=======================================================================
1489 // function: MakeVertex
1490 // purpose :
1491 //=======================================================================
1492 void BOPTools_AlgoTools::MakeVertex(const BOPCol_ListOfShape& aLV,
1493                                     TopoDS_Vertex& aVnew)
1494 {
1495   Standard_Integer aNb = aLV.Extent();
1496   if (aNb == 1)
1497     aVnew=*((TopoDS_Vertex*)(&aLV.First()));
1498   else if (aNb > 1)
1499   {
1500     Standard_Real aNTol;
1501     gp_Pnt aNC;
1502     BRepLib::BoundingVertex(aLV, aNC, aNTol);
1503     BRep_Builder aBB;
1504     aBB.MakeVertex(aVnew, aNC, aNTol);
1505   }
1506 }
1507 //=======================================================================
1508 //function : GetEdgeOnFace
1509 //purpose  :
1510 //=======================================================================
1511 Standard_Boolean BOPTools_AlgoTools::GetEdgeOnFace
1512 (const TopoDS_Edge& theE1,
1513  const TopoDS_Face& theF2,
1514  TopoDS_Edge& theE2)
1515 {
1516   Standard_Boolean bFound;
1517   TopoDS_Iterator aItF, aItW;
1518   //
1519   bFound=Standard_False;
1520   //
1521   aItF.Initialize(theF2);
1522   for (; aItF.More(); aItF.Next()) {
1523     const TopoDS_Shape& aW=aItF.Value();
1524     aItW.Initialize(aW);
1525     for (; aItW.More(); aItW.Next()) {
1526       const TopoDS_Shape& aE=aItW.Value();
1527       if (aE.IsSame(theE1)) {
1528         theE2=(*(TopoDS_Edge*)(&aE));
1529         bFound=!bFound;
1530         return bFound;
1531       }
1532     }
1533   }
1534   return bFound;
1535 }
1536 //=======================================================================
1537 //function : FindFacePairs
1538 //purpose  :
1539 //=======================================================================
1540 Standard_Boolean FindFacePairs (const TopoDS_Edge& theE,
1541                                 const BOPCol_ListOfShape& thLF,
1542                                 BOPTools_ListOfCoupleOfShape& theLCFF,
1543                                 Handle(IntTools_Context)& theContext)
1544 {
1545   Standard_Boolean bFound;
1546   Standard_Integer i, aNbCEF;
1547   TopAbs_Orientation aOr, aOrC = TopAbs_FORWARD;
1548   BOPCol_MapOfShape aMFP;
1549   TopoDS_Face aF1, aF2;
1550   TopoDS_Edge aEL, aE1;
1551   BOPCol_ListIteratorOfListOfShape aItLF;
1552   BOPTools_CoupleOfShape aCEF, aCFF;
1553   BOPTools_ListOfCoupleOfShape aLCEF, aLCEFx;
1554   BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
1555   //
1556   bFound=Standard_True;
1557   //
1558   // Preface aLCEF
1559   aItLF.Initialize(thLF);
1560   for (; aItLF.More(); aItLF.Next()) {
1561     const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aItLF.Value()));
1562     //
1563     bFound=BOPTools_AlgoTools::GetEdgeOnFace(theE, aFL, aEL);
1564     if (!bFound) {
1565       return bFound; // it can not be so
1566     }
1567     //
1568     aCEF.SetShape1(aEL);
1569     aCEF.SetShape2(aFL);
1570     aLCEF.Append(aCEF);
1571   }
1572   //
1573   aNbCEF=aLCEF.Extent();
1574   while(aNbCEF) {
1575     //
1576     // aLCEFx
1577     aLCEFx.Clear();
1578     aIt.Initialize(aLCEF);
1579     for (i=0; aIt.More(); aIt.Next(), ++i) {
1580       const BOPTools_CoupleOfShape& aCSx=aIt.Value();
1581       const TopoDS_Shape& aEx=aCSx.Shape1();
1582       const TopoDS_Shape& aFx=aCSx.Shape2();
1583       //
1584       aOr=aEx.Orientation();
1585       //
1586       if (!i) {
1587         aOrC=TopAbs::Reverse(aOr);
1588         aE1=(*(TopoDS_Edge*)(&aEx));
1589         aF1=(*(TopoDS_Face*)(&aFx));
1590         aMFP.Add(aFx);
1591         continue;
1592       }
1593       //
1594       if (aOr==aOrC) {
1595         aLCEFx.Append(aCSx);
1596         aMFP.Add(aFx);
1597       }
1598     }
1599     //
1600     // F2
1601     BOPTools_AlgoTools::GetFaceOff(aE1, aF1, aLCEFx, aF2, theContext);
1602     //
1603     aCFF.SetShape1(aF1);
1604     aCFF.SetShape2(aF2);
1605     theLCFF.Append(aCFF);
1606     //
1607     aMFP.Add(aF1);
1608     aMFP.Add(aF2);
1609     //
1610     // refine aLCEF
1611     aLCEFx.Clear();
1612     aLCEFx=aLCEF;
1613     aLCEF.Clear();
1614     aIt.Initialize(aLCEFx);
1615     for (; aIt.More(); aIt.Next()) {
1616       const BOPTools_CoupleOfShape& aCSx=aIt.Value();
1617       const TopoDS_Shape& aFx=aCSx.Shape2();
1618       if (!aMFP.Contains(aFx)) {
1619         aLCEF.Append(aCSx);
1620       }
1621     }
1622     //
1623     aNbCEF=aLCEF.Extent();
1624   }//while(aNbCEF) {
1625   //
1626   return bFound;
1627 }
1628 //=======================================================================
1629 //function : AngleWithRef
1630 //purpose  :
1631 //=======================================================================
1632 Standard_Real AngleWithRef(const gp_Dir& theD1,
1633                            const gp_Dir& theD2,
1634                            const gp_Dir& theDRef)
1635 {
1636   Standard_Real aCosinus, aSinus, aBeta, aHalfPI, aScPr;
1637   gp_XYZ aXYZ;
1638   //
1639   aHalfPI=0.5*M_PI;
1640   //
1641   const gp_XYZ& aXYZ1=theD1.XYZ();
1642   const gp_XYZ& aXYZ2=theD2.XYZ();
1643   aXYZ=aXYZ1.Crossed(aXYZ2);
1644   aSinus=aXYZ.Modulus();
1645   aCosinus=theD1*theD2;
1646   //
1647   aBeta=0.;
1648   if (aSinus>=0.) {
1649     aBeta=aHalfPI*(1.-aCosinus);
1650   }
1651   else {
1652     aBeta=2.*M_PI-aHalfPI*(3.+aCosinus);
1653   }
1654   //
1655   aScPr=aXYZ.Dot(theDRef.XYZ());
1656   if (aScPr<0.) {
1657     aBeta=-aBeta;
1658   }
1659   return aBeta;
1660 }
1661 //=======================================================================
1662 // function: IsBlockInOnFace
1663 // purpose:
1664 //=======================================================================
1665 Standard_Boolean BOPTools_AlgoTools::IsBlockInOnFace
1666   (const IntTools_Range& aShrR,
1667    const TopoDS_Face& aF,
1668    const TopoDS_Edge& aE1,
1669    Handle(IntTools_Context)& aContext)
1670 {
1671   Standard_Boolean bFlag;
1672   Standard_Real f1, l1, ULD, VLD;
1673   gp_Pnt2d aP2D;
1674   gp_Pnt aP11, aP12;
1675   //
1676   aShrR.Range(f1, l1);
1677   Standard_Real dt=0.0075,  k;//dt=0.001,  k;
1678   k=dt*(l1-f1);
1679   f1=f1+k;
1680   l1=l1-k;
1681   //
1682   // Treatment P11
1683   BOPTools_AlgoTools::PointOnEdge(aE1, f1, aP11);
1684   //
1685   GeomAPI_ProjectPointOnSurf& aProjector=aContext->ProjPS(aF);
1686   aProjector.Perform(aP11);
1687   //
1688   bFlag=aProjector.IsDone();
1689   if (!bFlag) {
1690     return bFlag;
1691   }
1692
1693   aProjector.LowerDistanceParameters(ULD, VLD);
1694   aP2D.SetCoord(ULD, VLD);
1695   //
1696   bFlag=aContext->IsPointInOnFace (aF, aP2D);
1697   //
1698   if (!bFlag) {
1699     return bFlag;
1700   }
1701   //
1702   // Treatment P12
1703   BOPTools_AlgoTools::PointOnEdge(aE1, l1, aP12);
1704   //
1705   aProjector.Perform(aP12);
1706   //
1707   bFlag=aProjector.IsDone();
1708   if (!bFlag) {
1709     return bFlag;
1710   }
1711
1712   aProjector.LowerDistanceParameters(ULD, VLD);
1713   aP2D.SetCoord(ULD, VLD);
1714   //
1715   bFlag=aContext->IsPointInOnFace (aF, aP2D);
1716   //
1717   if (!bFlag) {
1718     return bFlag;
1719   }
1720   //
1721   // Treatment intemediate
1722   Standard_Real m1, aTolF, aTolE, aTol, aDist;
1723   m1=IntTools_Tools::IntermediatePoint(f1, l1);
1724   BOPTools_AlgoTools::PointOnEdge(aE1, m1, aP12);
1725   //
1726   aProjector.Perform(aP12);
1727   //
1728   bFlag=aProjector.IsDone();
1729   if (!bFlag) {
1730     return bFlag;
1731   }
1732   //
1733   aTolE=BRep_Tool::Tolerance(aE1);
1734   aTolF=BRep_Tool::Tolerance(aF);
1735   aTol=aTolE+aTolF;
1736   aDist=aProjector.LowerDistance();
1737   if (aDist > aTol){
1738    return Standard_False;
1739   }
1740
1741   aProjector.LowerDistanceParameters(ULD, VLD);
1742   aP2D.SetCoord(ULD, VLD);
1743   //
1744   bFlag=aContext->IsPointInOnFace (aF, aP2D);
1745   //
1746   if (!bFlag) {
1747     return bFlag;
1748   }
1749   return bFlag;
1750 }
1751
1752 //=======================================================================
1753 //function : IsMicroEdge
1754 //purpose  :
1755 //=======================================================================
1756 Standard_Boolean BOPTools_AlgoTools::IsMicroEdge
1757   (const TopoDS_Edge& aE,
1758    const Handle(IntTools_Context)& aCtx,
1759    const Standard_Boolean bCheckSplittable)
1760 {
1761   Standard_Boolean bRet;
1762   Standard_Real aT1, aT2, aTmp;
1763   Handle(Geom_Curve) aC3D;
1764   TopoDS_Vertex aV1, aV2;
1765   //
1766   bRet=(BRep_Tool::Degenerated(aE) ||
1767         !BRep_Tool::IsGeometric(aE));
1768   if (bRet) {
1769     return bRet;
1770   }
1771   //
1772   aC3D=BRep_Tool::Curve(aE, aT1, aT2);
1773   TopExp::Vertices(aE, aV1, aV2);
1774   aT1=BRep_Tool::Parameter(aV1, aE);
1775   aT2=BRep_Tool::Parameter(aV2, aE);
1776   if (aT2<aT1) {
1777     aTmp=aT1;
1778     aT1=aT2;
1779     aT2=aTmp;
1780   }
1781   //
1782   IntTools_ShrunkRange aSR;
1783   aSR.SetContext(aCtx);
1784   aSR.SetData(aE, aT1, aT2, aV1, aV2);
1785   aSR.Perform();
1786   bRet = !aSR.IsDone();
1787   if (!bRet && bCheckSplittable) {
1788     bRet = !aSR.IsSplittable();
1789   }
1790   //
1791   return bRet;
1792 }
1793
1794 //=======================================================================
1795 //function : GetFaceDir
1796 //purpose  : Get binormal direction for the face in the point aP
1797 //=======================================================================
1798 void GetFaceDir(const TopoDS_Edge& aE,
1799                 const TopoDS_Face& aF,
1800                 const gp_Pnt& aP,
1801                 const Standard_Real aT,
1802                 const gp_Dir& aDTgt,
1803                 gp_Dir& aDN,
1804                 gp_Dir& aDB,
1805                 Handle(IntTools_Context)& theContext,
1806                 GeomAPI_ProjectPointOnSurf& aProjPL,
1807                 const Standard_Real aDt)
1808 {
1809   Standard_Real aTolE;
1810   gp_Pnt aPx;
1811   //
1812   BOPTools_AlgoTools3D::GetNormalToFaceOnEdge(aE, aF, aT, aDN);
1813   if (aF.Orientation()==TopAbs_REVERSED){
1814     aDN.Reverse();
1815   }
1816   //
1817   aTolE=BRep_Tool::Tolerance(aE);
1818   aDB = aDN^aDTgt;
1819   //
1820   if (!FindPointInFace(aF, aP, aDB, aPx, theContext, aProjPL, aDt, aTolE)) {
1821     BOPTools_AlgoTools3D::GetApproxNormalToFaceOnEdge(aE, aF, aT, aPx,
1822                                                       aDN, theContext);
1823     aProjPL.Perform(aPx);
1824     aPx = aProjPL.NearestPoint();
1825     gp_Vec aVec(aP, aPx);
1826     aDB.SetXYZ(aVec.XYZ());
1827   }
1828 }
1829 //=======================================================================
1830 //function : FindPointInFace
1831 //purpose  : Find a point in the face in direction of <aDB>
1832 //=======================================================================
1833 Standard_Boolean FindPointInFace(const TopoDS_Face& aF,
1834                                  const gp_Pnt& aP,
1835                                  gp_Dir& aDB,
1836                                  gp_Pnt& aPOut,
1837                                  Handle(IntTools_Context)& theContext,
1838                                  GeomAPI_ProjectPointOnSurf& aProjPL,
1839                                  const Standard_Real aDt,
1840                                  const Standard_Real aTolE)
1841 {
1842   Standard_Integer aNbItMax;
1843   Standard_Real aDist, aDTol, aPM, anEps;
1844   Standard_Boolean bRet;
1845   gp_Pnt aP1, aPS;
1846   //
1847   aDTol = Precision::Angular();
1848   aPM = aP.XYZ().Modulus();
1849   if (aPM > 1000.) {
1850     aDTol = 5.e-16 * aPM;
1851   }
1852   bRet = Standard_False;
1853   aNbItMax = 15;
1854   anEps = Precision::SquareConfusion();
1855   //
1856   GeomAPI_ProjectPointOnSurf& aProj=theContext->ProjPS(aF);
1857   //
1858   aPS=aP;
1859   aProj.Perform(aPS);
1860   if (!aProj.IsDone()) {
1861     return bRet;
1862   }
1863   aPS=aProj.NearestPoint();
1864   aProjPL.Perform(aPS);
1865   aPS=aProjPL.NearestPoint();
1866   //
1867   aPS.SetXYZ(aPS.XYZ()+2.*aTolE*aDB.XYZ());
1868   aProj.Perform(aPS);
1869   if (!aProj.IsDone()) {
1870     return bRet;
1871   }
1872   aPS=aProj.NearestPoint();
1873   aProjPL.Perform(aPS);
1874   aPS=aProjPL.NearestPoint();
1875   //
1876   do {
1877     aP1.SetXYZ(aPS.XYZ()+aDt*aDB.XYZ());
1878     //
1879     aProj.Perform(aP1);
1880     if (!aProj.IsDone()) {
1881       return bRet;
1882     }
1883     aPOut = aProj.NearestPoint();
1884     aDist = aProj.LowerDistance();
1885     //
1886     aProjPL.Perform(aPOut);
1887     aPOut = aProjPL.NearestPoint();
1888     //
1889     gp_Vec aV(aPS, aPOut);
1890     if (aV.SquareMagnitude() < anEps) {
1891       return bRet;
1892     }
1893     aDB.SetXYZ(aV.XYZ());
1894   } while (aDist > aDTol && --aNbItMax);
1895   //
1896   bRet = aDist < aDTol;
1897   return bRet;
1898 }
1899 //=======================================================================
1900 //function : MinStep3D
1901 //purpose  :
1902 //=======================================================================
1903 Standard_Real MinStep3D(const TopoDS_Edge& theE1,
1904                         const TopoDS_Face& theF1,
1905                         const BOPTools_ListOfCoupleOfShape& theLCS,
1906                         const gp_Pnt& aP)
1907 {
1908   Standard_Real aDt, aTolE, aTolF, aDtMax, aDtMin, aR;
1909   BOPTools_CoupleOfShape aCS1;
1910   BOPTools_ListOfCoupleOfShape aLCS;
1911   BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
1912   BRepAdaptor_Surface aBAS;
1913   //
1914   aLCS = theLCS;
1915   aCS1.SetShape1(theE1);
1916   aCS1.SetShape2(theF1);
1917   aLCS.Append(aCS1);
1918   //
1919   aTolE = BRep_Tool::Tolerance(theE1);
1920   aDtMax = -1.;
1921   aDtMin = 5.e-6;
1922   //
1923   aIt.Initialize(aLCS);
1924   for (; aIt.More(); aIt.Next()) {
1925     const BOPTools_CoupleOfShape& aCS = aIt.Value();
1926     const TopoDS_Face& aF = (*(TopoDS_Face*)(&aCS.Shape2()));
1927     //
1928     aTolF = BRep_Tool::Tolerance(aF);
1929     aDt = 2*(aTolE + aTolF);
1930     //
1931     aR = 0.;
1932     aBAS.Initialize(aF, Standard_False);
1933     GeomAbs_SurfaceType aSType = aBAS.GetType();
1934     switch (aSType) {
1935     case GeomAbs_Cylinder: {
1936       aR = aBAS.Cylinder().Radius();
1937       break;
1938     }
1939     case GeomAbs_Cone: {
1940       gp_Lin aL(aBAS.Cone().Axis());
1941       aR = aL.Distance(aP);
1942       break;
1943     }
1944     case GeomAbs_Sphere: {
1945       aDtMin = Max(aDtMin, 5.e-4);
1946       aR = aBAS.Sphere().Radius();
1947       break;
1948     }
1949     case GeomAbs_Torus: {
1950       aR = aBAS.Torus().MajorRadius();
1951       break;
1952     }
1953     default:
1954       aDtMin = Max(aDtMin, 5.e-4);
1955       break;
1956     }
1957     //
1958     if (aR > 100.) {
1959       Standard_Real d = 10*Precision::PConfusion();
1960       aDtMin = Max(aDtMin, sqrt(d*d + 2*d*aR));
1961     }
1962     //
1963     if (aDt > aDtMax) {
1964       aDtMax = aDt;
1965     }
1966   }
1967   //
1968   if (aDtMax < aDtMin) {
1969     aDtMax = aDtMin;
1970   }
1971   //
1972   return aDtMax;
1973 }
1974 //=======================================================================
1975 //function : IsOpenShell
1976 //purpose  :
1977 //=======================================================================
1978 Standard_Boolean BOPTools_AlgoTools::IsOpenShell(const TopoDS_Shell& aSh)
1979 {
1980   Standard_Boolean bRet;
1981   Standard_Integer i, aNbE, aNbF;
1982   TopAbs_Orientation aOrF;
1983   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
1984   BOPCol_ListIteratorOfListOfShape aItLS;
1985   //
1986   bRet=Standard_False;
1987   //
1988   BOPTools::MapShapesAndAncestors(aSh, TopAbs_EDGE, TopAbs_FACE, aMEF);
1989   //
1990   aNbE=aMEF.Extent();
1991   for (i=1; i<=aNbE; ++i) {
1992     const TopoDS_Edge& aE=*((TopoDS_Edge*)&aMEF.FindKey(i));
1993     if (BRep_Tool::Degenerated(aE)) {
1994       continue;
1995     }
1996     //
1997     aNbF=0;
1998     const BOPCol_ListOfShape& aLF=aMEF(i);
1999     aItLS.Initialize(aLF);
2000     for (; aItLS.More(); aItLS.Next()) {
2001       const TopoDS_Shape& aF=aItLS.Value();
2002       aOrF=aF.Orientation();
2003       if (aOrF==TopAbs_INTERNAL || aOrF==TopAbs_EXTERNAL) {
2004         continue;
2005       }
2006       ++aNbF;
2007     }
2008     //
2009     if (aNbF==1) {
2010       bRet=!bRet; // True
2011       break;
2012     }
2013   }
2014   //
2015   return bRet;
2016 }
2017 //=======================================================================
2018 //function : IsInvertedSolid
2019 //purpose  :
2020 //=======================================================================
2021 Standard_Boolean BOPTools_AlgoTools::IsInvertedSolid
2022   (const TopoDS_Solid& aSolid)
2023 {
2024   Standard_Real aTolS;
2025   TopAbs_State aState;
2026   BRepClass3d_SolidClassifier aSC(aSolid);
2027   //
2028   aTolS=1.e-7;
2029   aSC.PerformInfinitePoint(aTolS);
2030   aState=aSC.State();
2031   return (aState==TopAbs_IN);
2032 }