src/BOPTools/BOPTools_AlgoTools.cxx

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