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