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