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