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