src/BOPAlgo/BOPAlgo_Tools.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15
  16 #include <BOPAlgo_Tools.hxx>
  17
  18 #include <BOPAlgo_Builder.hxx>
  19 #include <BOPAlgo_BuilderFace.hxx>
  20 #include <BOPDS_CommonBlock.hxx>
  21 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
  22 #include <BOPDS_DS.hxx>
  23 #include <BOPDS_IndexedMapOfPaveBlock.hxx>
  24 #include <BOPDS_MapOfPaveBlock.hxx>
  25 #include <BOPDS_PaveBlock.hxx>
  26 #include <BOPTools_AlgoTools.hxx>
  27 #include <BOPTools_AlgoTools2D.hxx>
  28 #include <BOPTools_BoxBndTree.hxx>
  29 #include <BOPTools_Parallel.hxx>
  30 #include <BRep_Builder.hxx>
  31 #include <BRep_Tool.hxx>
  32 #include <BRepAdaptor_Curve.hxx>
  33 #include <BRepBndLib.hxx>
  34 #include <BRepBuilderAPI_MakeFace.hxx>
  35 #include <BRepLib.hxx>
  36 #include <GeomAPI_ProjectPointOnCurve.hxx>
  37 #include <GeomAPI_ProjectPointOnSurf.hxx>
  38 #include <gp_Circ.hxx>
  39 #include <gp_Dir.hxx>
  40 #include <gp_Elips.hxx>
  41 #include <gp_Hypr.hxx>
  42 #include <gp_Parab.hxx>
  43 #include <gp_Pln.hxx>
  44 #include <gp_Pnt.hxx>
  45 #include <gp_Vec.hxx>
  46 #include <IntTools_Context.hxx>
  47 #include <NCollection_IncAllocator.hxx>
  48 #include <NCollection_UBTreeFiller.hxx>
  49 #include <NCollection_Vector.hxx>
  50 #include <Standard_ErrorHandler.hxx>
  51 #include <Standard_Failure.hxx>
  52 #include <TColStd_IndexedMapOfInteger.hxx>
  53 #include <TopExp.hxx>
  54 #include <TopExp_Explorer.hxx>
  55 #include <TopoDS.hxx>
  56 #include <TopoDS_Edge.hxx>
  57 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  58 #include <TopTools_IndexedMapOfShape.hxx>
  59 #include <TopTools_MapOfShape.hxx>
  60
  61 #include <algorithm>
  62
  63 typedef NCollection_IndexedDataMap
  64   <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
  65 typedef NCollection_IndexedDataMap
  66   <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
  67
  68 static
  69   void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
  70                  TopoDS_Compound& theWires,
  71                  const Standard_Boolean theCheckUniquePlane,
  72                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
  73                  TopTools_MapOfShape& theMEdgesNoUniquePlane);
  74
  75 static
  76   Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
  77                              gp_Pln& thePlane);
  78
  79 static
  80   Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
  81                              gp_Pln& thePlane,
  82                              BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
  83                              TopTools_MapOfShape& theMEdgesNoUniquePlane);
  84
  85 static
  86   Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
  87                                    BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
  88                                    gp_Dir& theTgt);
  89
  90 static
  91   Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
  92                                    gp_Vec& theTangent);
  93
  94 //=======================================================================
  95 //function : FillMap
  96 //purpose  :
  97 //=======================================================================
  98 void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
  99                             const Standard_Integer nF,
 100                             BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
 101                             const Handle(NCollection_BaseAllocator)& aAllocator)
 102 {
 103   TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
 104   if (!pLI) {
 105     pLI = &aMPBLI(aMPBLI.Add(aPB, TColStd_ListOfInteger(aAllocator)));
 106   }
 107   pLI->Append(nF);
 108 }
 109 //=======================================================================
 110 //function : PerformCommonBlocks
 111 //purpose  :
 112 //=======================================================================
 113 void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
 114                                         const Handle(NCollection_BaseAllocator)& aAllocator,
 115                                         BOPDS_PDS& pDS,
 116                                         const Handle(IntTools_Context)& theContext)
 117 {
 118   Standard_Integer aNbCB;
 119   //
 120   aNbCB=aMPBLPB.Extent();
 121   if (!aNbCB) {
 122     return;
 123   }
 124   // Make Blocks of the pave blocks
 125   NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
 126   BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
 127
 128   // Use temporary allocator for the local fence map
 129   Handle(NCollection_IncAllocator) anAllocTmp = new NCollection_IncAllocator;
 130
 131   NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
 132   for (; aItB.More(); aItB.Next()) {
 133     const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
 134     Standard_Integer aNbPB = aLPB.Extent();
 135     if (aNbPB < 2)
 136       continue;
 137
 138     // Reset the allocator
 139     anAllocTmp->Reset();
 140     // New common block
 141     Handle(BOPDS_CommonBlock) aCB;
 142     // Faces of the common block
 143     TColStd_ListOfInteger aLFaces;
 144     // Fence map to avoid duplicates in the list of faces of the common block
 145     TColStd_MapOfInteger aMFaces(1, anAllocTmp);
 146
 147     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
 148     for (; aItLPB.More(); aItLPB.Next())
 149     {
 150       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
 151       if (pDS->IsCommonBlock(aPB))
 152       {
 153         const Handle(BOPDS_CommonBlock)& aCBx = pDS->CommonBlock(aPB);
 154         // Move all faces to the new common block
 155         TColStd_ListIteratorOfListOfInteger aItLF(aCBx->Faces());
 156         for (; aItLF.More(); aItLF.Next())
 157         {
 158           const Standard_Integer nF = aItLF.Value();
 159           // Append to common list avoiding duplicates
 160           if (aMFaces.Add(nF))
 161             aLFaces.Append(nF);
 162         }
 163         if (aCB.IsNull())
 164           aCB = aCBx;
 165       }
 166     }
 167
 168     if (aCB.IsNull())
 169       aCB = new BOPDS_CommonBlock;
 170
 171     aCB->SetPaveBlocks(aLPB);
 172     aCB->SetFaces(aLFaces);
 173     for (aItLPB.Initialize(aLPB); aItLPB.More(); aItLPB.Next())
 174       pDS->SetCommonBlock(aItLPB.Value(), aCB);
 175
 176     // Compute tolerance for Common Block
 177     Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
 178     aCB->SetTolerance(aTolCB);
 179   }
 180 }
 181 //=======================================================================
 182 //function : PerformCommonBlocks
 183 //purpose  :
 184 //=======================================================================
 185 void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
 186                                         const Handle(NCollection_BaseAllocator)& ,//aAllocator
 187                                         BOPDS_PDS& pDS,
 188                                         const Handle(IntTools_Context)& theContext)
 189 {
 190   Standard_Integer nF, i, aNb;
 191   TColStd_ListIteratorOfListOfInteger aItLI;
 192   Handle(BOPDS_PaveBlock) aPB;
 193   Handle(BOPDS_CommonBlock) aCB;
 194   //
 195   aNb=aMPBLI.Extent();
 196   for (i=1; i<=aNb; ++i) {
 197     aPB=aMPBLI.FindKey(i);
 198     if (pDS->IsCommonBlock(aPB)) {
 199       aCB=pDS->CommonBlock(aPB);
 200     }
 201     else {
 202       aCB=new BOPDS_CommonBlock;
 203       aCB->AddPaveBlock(aPB);
 204     }
 205     //
 206     const TColStd_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
 207     TColStd_ListOfInteger aNewFaces;
 208     const TColStd_ListOfInteger& anOldFaces = aCB->Faces();
 209     aItLI.Initialize(aLI);
 210     for (; aItLI.More(); aItLI.Next()) {
 211       nF=aItLI.Value();
 212       // the both lists aLI and anOldFaces are expected to be short,
 213       // so we can allow to run nested loop here
 214       TColStd_ListIteratorOfListOfInteger it(anOldFaces);
 215       for (; it.More(); it.Next()) {
 216         if (it.Value() == nF)
 217           break;
 218       }
 219       if (!it.More()) {
 220         aNewFaces.Append(nF);
 221       }
 222     }
 223     aCB->AppendFaces(aNewFaces);
 224     pDS->SetCommonBlock(aPB, aCB);
 225     // Compute tolerance for Common Block
 226     Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
 227     aCB->SetTolerance(aTolCB);
 228   }
 229 }
 230 //=======================================================================
 231 //function : ComputeToleranceOfCB
 232 //purpose  :
 233 //=======================================================================
 234 Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
 235                    (const Handle(BOPDS_CommonBlock)& theCB,
 236                     const BOPDS_PDS theDS,
 237                     const Handle(IntTools_Context)& theContext)
 238 {
 239   Standard_Real aTolMax = 0.;
 240   if (theCB.IsNull()) {
 241     return aTolMax;
 242   }
 243   //
 244   const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
 245   Standard_Integer nE = aPBR->OriginalEdge();
 246   const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
 247   aTolMax = BRep_Tool::Tolerance(aEOr);
 248   //
 249   const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
 250   const TColStd_ListOfInteger& aLFI = theCB->Faces();
 251   //
 252   if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
 253     return aTolMax;
 254   }
 255   //
 256   const Standard_Integer aNbPnt = 11;
 257   Standard_Real aTol, aT, aT1, aT2, aDt;
 258   gp_Pnt aP;
 259   //
 260   const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
 261   //
 262   aPBR->Range(aT1, aT2);
 263   aDt = (aT2 - aT1) / (aNbPnt + 1);
 264   //
 265   Handle(IntTools_Context) aCtx = theContext;
 266   if (aCtx.IsNull())
 267     aCtx = new IntTools_Context();
 268
 269   // compute max tolerance for common blocks on edges
 270   if (aLPB.Extent() > 1) {
 271     // compute max distance between edges
 272     BOPDS_ListIteratorOfListOfPaveBlock aItPB;
 273     GeomAPI_ProjectPointOnCurve aProjPC;
 274     //
 275     aItPB.Initialize(aLPB);
 276     for (; aItPB.More(); aItPB.Next()) {
 277       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
 278       if (aPB == aPBR) {
 279         continue;
 280       }
 281       //
 282       nE = aPB->OriginalEdge();
 283       const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
 284       aTol = BRep_Tool::Tolerance(aE);
 285       //
 286       aProjPC = aCtx->ProjPC(aE);
 287       //
 288       aT = aT1;
 289       for (Standard_Integer i=1; i <= aNbPnt; i++) {
 290         aT += aDt;
 291         aC3D->D0(aT, aP);
 292         aProjPC.Perform(aP);
 293         if (aProjPC.NbPoints()) {
 294           Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
 295           if (aTolNew > aTolMax) {
 296             aTolMax = aTolNew;
 297           }
 298         }
 299       }
 300     }
 301   }
 302   //
 303   // compute max tolerance for common blocks on faces
 304   if (aLFI.Extent()) {
 305     Standard_Integer nF;
 306     GeomAPI_ProjectPointOnSurf aProjPS;
 307     TColStd_ListIteratorOfListOfInteger aItLI;
 308     //
 309     aItLI.Initialize(aLFI);
 310     for (; aItLI.More(); aItLI.Next()) {
 311       nF = aItLI.Value();
 312       const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
 313       aTol = BRep_Tool::Tolerance(aF);
 314       //
 315       aProjPS = aCtx->ProjPS(aF);
 316       //
 317       aT = aT1;
 318       for (Standard_Integer i=1; i <= aNbPnt; i++) {
 319         aT += aDt;
 320         aC3D->D0(aT, aP);
 321         aProjPS.Perform(aP);
 322         if (aProjPS.NbPoints()) {
 323           Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
 324           if (aTolNew > aTolMax) {
 325             aTolMax = aTolNew;
 326           }
 327         }
 328       }
 329     }
 330   }
 331   //
 332   return aTolMax;
 333 }
 334
 335 //=======================================================================
 336 //function : EdgesToWires
 337 //purpose  :
 338 //=======================================================================
 339 Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
 340                                              TopoDS_Shape& theWires,
 341                                              const Standard_Boolean theShared,
 342                                              const Standard_Real theAngTol)
 343 {
 344   Standard_Integer iErr = 0;
 345   //
 346   // 1. Check the input edges
 347   //
 348   // List of edges to process
 349   TopTools_ListOfShape aLE;
 350   //
 351   TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
 352   for (; aExp.More(); aExp.Next()) {
 353     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
 354     if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
 355       aLE.Append(aExp.Current());
 356     }
 357   }
 358   //
 359   if (aLE.IsEmpty()) {
 360     // no edges to process
 361     iErr = 1;
 362     return iErr;
 363   }
 364   //
 365   BRep_Builder aBB;
 366   TopoDS_Compound aRWires;
 367   aBB.MakeCompound(aRWires);
 368   //
 369   if (aLE.Extent() == 1) {
 370     TopoDS_Wire aWire;
 371     aBB.MakeWire(aWire);
 372     aBB.Add(aWire, aLE.First());
 373     aBB.Add(aRWires, aWire);
 374     theWires = aRWires;
 375     return iErr;
 376   }
 377   //
 378   // 2. Make compound of shared edges
 379   TopoDS_Shape aSEdges;
 380   //
 381   if (!theShared) {
 382     // intersect the edges if necessary
 383     BOPAlgo_Builder aGF;
 384     aGF.SetArguments(aLE);
 385     aGF.Perform();
 386     if (aGF.HasErrors()) {
 387       // unable to share the edges
 388       iErr = 2;
 389       return iErr;
 390     }
 391     //
 392     aSEdges = aGF.Shape();
 393   }
 394   else {
 395     aBB.MakeCompound(TopoDS::Compound(aSEdges));
 396     TopTools_ListIteratorOfListOfShape aItLE(aLE);
 397     for (; aItLE.More(); aItLE.Next()) {
 398       aBB.Add(aSEdges, aItLE.Value());
 399     }
 400   }
 401   //
 402   // 3. Find edges located in the same planes and make wires from them.
 403   // If the plane cannot be found for a single edge, then it is necessary
 404   // to find all pairs of connected edges with the same cross product.
 405
 406   // Try to compute the plane in which the edge is located
 407   BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
 408   // Compute the tangent direction for the edges for which the plane is not defined
 409   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
 410   //
 411   // edges for which the plane is not found
 412   TopTools_MapOfShape aMEdgesNoUniquePlane;
 413   //
 414   // edges for which the plane cannot be found on a single edge
 415   TopoDS_Compound aLEdges;
 416   aBB.MakeCompound(aLEdges);
 417   //
 418   aExp.Init(aSEdges, TopAbs_EDGE);
 419   for (; aExp.More(); aExp.Next()) {
 420     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
 421     BRepAdaptor_Curve aBAC(aE);
 422     //
 423     gp_Pln aPln;
 424     if (FindPlane(aBAC, aPln)) {
 425       aDMEdgePln.Add(aE, aPln);
 426     }
 427     else {
 428       gp_Vec aVT;
 429       if (FindEdgeTangent(aBAC, aVT)) {
 430         aDMEdgeTgt.Add(aE, gp_Dir(aVT));
 431         aBB.Add(aLEdges, aE);
 432         aMEdgesNoUniquePlane.Add(aE);
 433       }
 434     }
 435   }
 436   //
 437   typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
 438   //
 439   // to avoid processing of the same edges in the same plane store
 440   // the processed planes into a list and use it as a fence map
 441   BOPAlgo_ListOfDir aLPFence;
 442   //
 443   // used edges
 444   TopTools_MapOfShape aMEFence;
 445   //
 446   // look for a planes on the single edges
 447   Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
 448   for (i = 1; i <= aNbPlanes; ++i) {
 449     const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
 450     if (!aMEFence.Add(aEI)) {
 451       continue;
 452     }
 453     //
 454     const gp_Pln& aPlnI = aDMEdgePln(i);
 455     const gp_Dir& aDI = aPlnI.Position().Direction();
 456     //
 457     aLPFence.Append(aDI);
 458     //
 459     TopTools_IndexedMapOfShape aMEPln;
 460     aMEPln.Add(aEI);
 461     //
 462     TopTools_IndexedMapOfShape aMV;
 463     TopExp::MapShapes(aEI, TopAbs_VERTEX, aMV);
 464     //
 465     // look for other edges with the plane parallel to current one
 466     for (j = i + 1; j <= aNbPlanes; ++j) {
 467       const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
 468       if (aDI.IsParallel(aDJ, theAngTol)) {
 469         const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
 470         aMEPln.Add(aEJ);
 471         aMEFence.Add(aEJ);
 472         TopExp::MapShapes(aEJ, TopAbs_VERTEX, aMV);
 473       }
 474     }
 475     //
 476     // look for all other edges located in the plane parallel to current one
 477     TopoDS_Compound aCEPln;
 478     aBB.MakeCompound(aCEPln);
 479     //
 480     for (j = 1; j <= aNbEdges; ++j) {
 481       const gp_Dir& aDJ = aDMEdgeTgt(j);
 482       if (aDI.IsNormal(aDJ, theAngTol)) {
 483         aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
 484       }
 485     }
 486     //
 487     // make blocks of these edges and check blocks to be connected
 488     // to any of the already added edges or forming a wire themselves
 489     TopTools_ListOfShape aLCBE;
 490     BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
 491     //
 492     // make wire from each block
 493     TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
 494     for (; aItLCB.More(); aItLCB.Next()) {
 495       const TopoDS_Shape& aCBE = aItLCB.Value();
 496       //
 497       // check connectivity
 498       TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
 499       for (; aExpV.More(); aExpV.Next()) {
 500         if (aMV.Contains(aExpV.Current())) {
 501           break;
 502         }
 503       }
 504       //
 505       Standard_Boolean bAddBlock = aExpV.More();
 506       if (!bAddBlock) {
 507         // check if the edges are forming a wire
 508         gp_Pln aPln;
 509         bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
 510       }
 511       //
 512       if (bAddBlock) {
 513         // add edges
 514         for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
 515           aMEPln.Add(aItE.Value());
 516         }
 517       }
 518     }
 519     //
 520     MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
 521   }
 522   //
 523   // make connection map from vertices to edges to find the connected pairs
 524   TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
 525   TopExp::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
 526   //
 527   // find planes for connected edges
 528   Standard_Integer aNbV = aDMVE.Extent();
 529   for (i = 1; i <= aNbV; ++i) {
 530     const TopTools_ListOfShape& aLEI = aDMVE(i);
 531     if (aLEI.Extent() < 2) {
 532       continue;
 533     }
 534     //
 535     TopTools_ListIteratorOfListOfShape aItLEI1(aLEI);
 536     for (; aItLEI1.More(); aItLEI1.Next()) {
 537       const TopoDS_Shape& aEI1 = aItLEI1.Value();
 538       const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
 539       //
 540       TopTools_ListIteratorOfListOfShape aItLEI2(aLEI);
 541       for (; aItLEI2.More(); aItLEI2.Next()) {
 542         const TopoDS_Shape& aEI2 = aItLEI2.Value();
 543         if (aEI2.IsSame(aEI1)) {
 544           continue;
 545         }
 546         //
 547         const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
 548         //
 549         if (aDI1.IsParallel(aDI2, theAngTol)) {
 550           continue;
 551         }
 552         //
 553         gp_Dir aDNI = aDI1^aDI2;
 554         //
 555         // check if this normal direction has not been checked yet
 556         BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
 557         for (; aItLPln.More(); aItLPln.Next()) {
 558           if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
 559             break;
 560           }
 561         }
 562         if (aItLPln.More()) {
 563           continue;
 564         }
 565         //
 566         aLPFence.Append(aDNI);
 567         //
 568         // find all other edges in the plane parallel to current one
 569         TopTools_IndexedMapOfShape aMEPln;
 570         aMEPln.Add(aEI1);
 571         aMEPln.Add(aEI2);
 572         //
 573         // iterate on all other edges to find all edges lying in the plane parallel to current one
 574         for (j = 1; j <= aNbEdges; ++j) {
 575           const gp_Dir& aDJ = aDMEdgeTgt(j);
 576           if (aDNI.IsNormal(aDJ, theAngTol)) {
 577             aMEPln.Add(aDMEdgeTgt.FindKey(j));
 578           }
 579         }
 580         //
 581         MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
 582       } // for (; aItLEI2.More(); aItLEI2.Next()) {
 583     } // for (; aItLEI1.More(); aItLEI1.Next()) {
 584   } // for (i = 1; i < aNb; ++i) {
 585   //
 586   // 4. Find unused edges and make wires from them
 587   TopTools_IndexedMapOfShape aMEAlone, aMEUsed;
 588   TopExp::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
 589   //
 590   for (i = 1; i <= aNbEdges; ++i) {
 591     const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
 592     if (!aMEUsed.Contains(aE)) {
 593       aMEAlone.Add(aE);
 594     }
 595   }
 596   //
 597   MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
 598   //
 599   theWires = aRWires;
 600   //
 601   return iErr;
 602 }
 603
 604 //=======================================================================
 605 //function : WiresToFaces
 606 //purpose  :
 607 //=======================================================================
 608 Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
 609                                              TopoDS_Shape& theFaces,
 610                                              const Standard_Real theAngTol)
 611 {
 612   BRep_Builder aBB;
 613   TopTools_MapOfShape aMFence;
 614   TopoDS_Compound aRFaces;
 615   aBB.MakeCompound(aRFaces);
 616   //
 617   const Standard_Real aMax = 1.e+8;
 618   //
 619   // map to store the tangent vectors for the edges
 620   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
 621   // maps to store the planes found for the wires
 622   BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
 623   // map to store the tolerance for the wire
 624   NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
 625   // edges for which the plane is not found
 626   TopTools_MapOfShape aMEdgesNoUniquePlane;
 627   //
 628   // Find planes for the wires
 629   TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
 630   for (; aExpW.More(); aExpW.Next()) {
 631     const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
 632     gp_Pln aPlane;
 633     if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
 634       aDMWirePln.Add(aWire, aPlane);
 635       // find tolerance for the wire - max tolerance of its edges
 636       aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
 637     }
 638   }
 639   //
 640   Standard_Integer i, j, aNb = aDMWirePln.Extent();
 641   for (i = 1; i <= aNb; ++i) {
 642     const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
 643     if (aMFence.Contains(aWireI)) {
 644       continue;
 645     }
 646     //
 647     const gp_Pln& aPlnI = aDMWirePln(i);
 648     //
 649     TopTools_ListOfShape aLW;
 650     aLW.Append(aWireI);
 651     aMFence.Add(aWireI);
 652     //
 653     Standard_Real aTolI = aDMWireTol.Find(aWireI);
 654     //
 655     // Find other wires in the same plane
 656     for (j = i + 1; j <= aNb; ++j) {
 657       const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
 658       if (aMFence.Contains(aWireJ)) {
 659         continue;
 660       }
 661       //
 662       // check if the planes are the same
 663       const gp_Pln& aPlnJ = aDMWirePln(j);
 664       // check direction of the planes
 665       if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
 666         continue;
 667       }
 668       // check distance between the planes
 669       Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
 670       Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
 671       if (aDist > (aTolI + aTolJ)) {
 672         continue;
 673       }
 674       //
 675       aLW.Append(aWireJ);
 676       aMFence.Add(aWireJ);
 677     }
 678     //
 679     // Take the edges to build the face
 680     TopTools_ListOfShape aLE;
 681     TopTools_ListIteratorOfListOfShape aItLW(aLW);
 682     for (; aItLW.More(); aItLW.Next()) {
 683       TopoDS_Iterator aItE(aItLW.Value());
 684       for (; aItE.More(); aItE.Next()) {
 685         aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
 686         aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
 687       }
 688     }
 689     //
 690     // build planar face
 691     TopoDS_Face aFF = BRepBuilderAPI_MakeFace
 692       (aPlnI, -aMax, aMax, -aMax, aMax).Face();
 693     aFF.Orientation(TopAbs_FORWARD);
 694     //
 695     try {
 696       OCC_CATCH_SIGNALS
 697       //
 698       // build pcurves for edges on this face
 699       BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
 700       //
 701       // split the face with the edges
 702       BOPAlgo_BuilderFace aBF;
 703       aBF.SetShapes(aLE);
 704       aBF.SetFace(aFF);
 705       aBF.Perform();
 706       if (aBF.HasErrors()) {
 707         continue;
 708       }
 709       //
 710       const TopTools_ListOfShape& aLFSp = aBF.Areas();
 711       TopTools_ListIteratorOfListOfShape aItLF(aLFSp);
 712       for (; aItLF.More(); aItLF.Next()) {
 713         const TopoDS_Shape& aFSp = aItLF.ChangeValue();
 714         aBB.Add(aRFaces, aFSp);
 715       }
 716     }
 717     catch (Standard_Failure const&) {
 718       continue;
 719     }
 720   }
 721   //
 722   // fix tolerances of the resulting faces
 723   TopTools_IndexedMapOfShape aMEmpty;
 724   BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
 725   BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
 726   //
 727   theFaces = aRFaces;
 728   return theFaces.NbChildren() > 0;
 729 }
 730
 731 //=======================================================================
 732 //function : MakeWires
 733 //purpose  : Makes wires from the separate blocks of the given edges
 734 //=======================================================================
 735 void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
 736                TopoDS_Compound& theWires,
 737                const Standard_Boolean theCheckUniquePlane,
 738                BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
 739                TopTools_MapOfShape& theMEdgesNoUniquePlane)
 740 {
 741   TopoDS_Compound aCE;
 742   BRep_Builder().MakeCompound(aCE);
 743   Standard_Integer i, aNbE = theEdges.Extent();
 744   for (i = 1; i <= aNbE; ++i) {
 745     BRep_Builder().Add(aCE, theEdges(i));
 746   }
 747   //
 748   TopTools_ListOfShape aLCBE;
 749   BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
 750   //
 751   // make wire from each block
 752   TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
 753   for (; aItLCB.More(); aItLCB.Next()) {
 754     const TopoDS_Shape& aCBE = aItLCB.Value();
 755     //
 756     if (theCheckUniquePlane) {
 757       gp_Pln aPln;
 758       if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
 759         continue;
 760       }
 761     }
 762     //
 763     TopoDS_Wire aWire;
 764     BRep_Builder().MakeWire(aWire);
 765     for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
 766       BRep_Builder().Add(aWire, aItE.Value());
 767     }
 768     //
 769     BRep_Builder().Add(theWires, aWire);
 770   }
 771 }
 772
 773 //=======================================================================
 774 //function : FindEdgeTangent
 775 //purpose  : Finds the tangent for the edge using the map
 776 //=======================================================================
 777 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
 778                                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
 779                                  gp_Dir& theTgt)
 780 {
 781   gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
 782   if (!pDTE) {
 783     gp_Vec aVTE;
 784     BRepAdaptor_Curve aBAC(theEdge);
 785     if (!FindEdgeTangent(aBAC, aVTE)) {
 786       return Standard_False;
 787     }
 788     pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
 789   }
 790   theTgt = *pDTE;
 791   return Standard_True;
 792 }
 793
 794 //=======================================================================
 795 //function : FindEdgeTangent
 796 //purpose  : Finds the tangent for the edge
 797 //=======================================================================
 798 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
 799                                  gp_Vec& theTangent)
 800 {
 801   if (!theCurve.Is3DCurve()) {
 802     return Standard_False;
 803   }
 804   // for the line the tangent is defined by the direction
 805   if (theCurve.GetType() == GeomAbs_Line) {
 806     theTangent = theCurve.Line().Position().Direction();
 807     return Standard_True;
 808   }
 809   //
 810   // for other curves take D1 and check for its length
 811   Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
 812   const Standard_Integer aNbP = 11;
 813   const Standard_Real aDt = (aT2 - aT1) / aNbP;
 814   //
 815   for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
 816     gp_Pnt aP;
 817     theCurve.D1(aT, aP, theTangent);
 818     if (theTangent.Magnitude() > Precision::Confusion()) {
 819       return Standard_True;
 820     }
 821   }
 822   //
 823   return Standard_False;
 824 }
 825
 826 //=======================================================================
 827 //function : FindPlane
 828 //purpose  : Finds the plane in which the edge is located
 829 //=======================================================================
 830 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
 831                            gp_Pln& thePlane)
 832 {
 833   if (!theCurve.Is3DCurve()) {
 834     return Standard_False;
 835   }
 836   //
 837   Standard_Boolean bFound = Standard_True;
 838   gp_Vec aVN;
 839   switch (theCurve.GetType()) {
 840     case GeomAbs_Line:
 841       return Standard_False;
 842     case GeomAbs_Circle:
 843       aVN = theCurve.Circle().Position().Direction();
 844       break;
 845     case GeomAbs_Ellipse:
 846       aVN = theCurve.Ellipse().Position().Direction();
 847       break;
 848     case GeomAbs_Hyperbola:
 849       aVN = theCurve.Hyperbola().Position().Direction();
 850       break;
 851     case GeomAbs_Parabola:
 852       aVN = theCurve.Parabola().Position().Direction();
 853       break;
 854     default: {
 855       // for all other types of curve compute two tangent vectors
 856       // on the curve and cross them
 857       bFound = Standard_False;
 858       Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
 859       const Standard_Integer aNbP = 11;
 860       const Standard_Real aDt = (aT2 - aT1) / aNbP;
 861       //
 862       aT = aT1;
 863       gp_Pnt aP1;
 864       gp_Vec aV1;
 865       theCurve.D1(aT, aP1, aV1);
 866       //
 867       for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
 868         gp_Pnt aP2;
 869         gp_Vec aV2;
 870         theCurve.D1(aT, aP2, aV2);
 871         //
 872         aVN = aV1^aV2;
 873         if (aVN.Magnitude() > Precision::Confusion()) {
 874           bFound = Standard_True;
 875           break;
 876         }
 877       }
 878       break;
 879     }
 880   }
 881   //
 882   if (bFound) {
 883     thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
 884   }
 885   return bFound;
 886 }
 887
 888 //=======================================================================
 889 //function : FindPlane
 890 //purpose  : Finds the plane in which the wire is located
 891 //=======================================================================
 892 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
 893                            gp_Pln& thePlane,
 894                            BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
 895                            TopTools_MapOfShape& theMEdgesNoUniquePlane)
 896 {
 897   TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
 898   if (!aExpE1.More()) {
 899     return Standard_False;
 900   }
 901   //
 902   // try to find two not parallel edges in wire to get normal of the plane
 903   for (; aExpE1.More(); aExpE1.Next()) {
 904     // get the first edge in the wire
 905     const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
 906     //
 907     // find tangent for the first edge
 908     gp_Dir aDTE1;
 909     if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
 910       continue;
 911     }
 912     //
 913     // find the other edge not parallel to the first one
 914     TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
 915     for (; aExpE2.More(); aExpE2.Next()) {
 916       const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
 917       if (aE1.IsSame(aE2)) {
 918         continue;
 919       }
 920       //
 921       // find tangent for the second edge
 922       gp_Dir aDTE2;
 923       if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
 924         continue;
 925       }
 926       //
 927       if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
 928         continue;
 929       }
 930       //
 931       gp_Dir aDN = aDTE1^aDTE2;
 932       //
 933       TopoDS_Iterator aItV(aE1);
 934       thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
 935       return Standard_True;
 936     }
 937   }
 938   //
 939   // try to compute normal on the single edge
 940   aExpE1.Init(theWire, TopAbs_EDGE);
 941   for (; aExpE1.More(); aExpE1.Next()) {
 942     const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
 943     if (theMEdgesNoUniquePlane.Contains(aE)) {
 944       continue;
 945     }
 946     BRepAdaptor_Curve aBAC(aE);
 947     if (FindPlane(aBAC, thePlane)) {
 948       return Standard_True;
 949     }
 950     theMEdgesNoUniquePlane.Add(aE);
 951   }
 952   return Standard_False;
 953 }
 954
 955 /////////////////////////////////////////////////////////////////////////
 956 //=======================================================================
 957 //class    : BOPAlgo_TNV
 958 //purpose  :
 959 //=======================================================================
 960 class BOPAlgo_TNV;
 961 typedef NCollection_Vector
 962   <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
 963 //
 964 typedef BOPTools_Functor
 965   <BOPAlgo_TNV,
 966   BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
 967 //
 968 typedef BOPTools_Cnt
 969   <BOPAlgo_TNVFunctor,
 970   BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
 971 //=======================================================================
 972 class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
 973  public:
 974   BOPAlgo_TNV()
 975     : BOPTools_BoxBndTreeSelector(),
 976       myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
 977   };
 978   //
 979   ~BOPAlgo_TNV(){
 980   };
 981   //
 982   void SetVertex(const TopoDS_Vertex& aV) {
 983     myV=aV;
 984     myPnt = BRep_Tool::Pnt(myV);
 985   }
 986   //
 987   const TopoDS_Vertex& Vertex()const {
 988     return myV;
 989   }
 990   //
 991   void SetTree(BOPTools_BoxBndTree& aTree) {
 992     myTree=&aTree;
 993   }
 994   //
 995   void SetTolerance(const Standard_Real theTol) {
 996     myTol = theTol;
 997   }
 998   //
 999   Standard_Real Tolerance() const {
1000     return myTol;
1001   }
1002   //
1003   const gp_Pnt& Pnt() const {
1004     return myPnt;
1005   }
1006   //
1007   void SetFuzzyValue(const Standard_Real theFuzzyValue) {
1008     myFuzzyValue = theFuzzyValue;
1009   }
1010   //
1011   void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
1012     myVecTNV = &theVec;
1013   }
1014   //
1015   virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
1016   {
1017     const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
1018     Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
1019     aTolSum2 *= aTolSum2;
1020     Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
1021     if (aD2 < aTolSum2)
1022       return BOPTools_BoxBndTreeSelector::Accept(theIndex);
1023     return Standard_False;
1024   }
1025   //
1026   void Perform() {
1027     myTree->Select(*this);
1028   }
1029   //
1030  protected:
1031   Standard_Real myTol;
1032   Standard_Real myFuzzyValue;
1033   gp_Pnt        myPnt;
1034   TopoDS_Vertex myV;
1035   BOPTools_BoxBndTree *myTree;
1036   const BOPAlgo_VectorOfTNV *myVecTNV;
1037 };
1038 //
1039 /////////////////////////////////////////////////////////////////////////
1040
1041 //=======================================================================
1042 //function : IntersectVertices
1043 //purpose  : Builds the chains of intersecting vertices
1044 //=======================================================================
1045 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
1046                                       const Standard_Boolean theRunParallel,
1047                                       const Standard_Real theFuzzyValue,
1048                                       TopTools_ListOfListOfShape& theChains)
1049 {
1050   Standard_Integer i, j, aNbV = theVertices.Extent();
1051   if (aNbV <= 1) {
1052     if (aNbV == 1) {
1053       theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
1054     }
1055     return;
1056   }
1057   //
1058   // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
1059   BOPTools_BoxBndTree aBBTree;
1060   NCollection_UBTreeFiller <Standard_Integer,
1061                             Bnd_Box> aTreeFiller(aBBTree);
1062   // Perform intersection of the vertices
1063   BOPAlgo_VectorOfTNV aVTNV;
1064   //
1065   // Use additional tolerance for intersection
1066   Standard_Real aTolAdd = theFuzzyValue / 2.;
1067   // Prepare the tree
1068   for (i = 1; i <= aNbV; ++i) {
1069     const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1070     Standard_Real aTol = BRep_Tool::Tolerance(aV);
1071     if (aTol < theVertices(i)) {
1072       aTol = theVertices(i);
1073     }
1074     // Build bnd box for vertex
1075     Bnd_Box aBox;
1076     aBox.Add(BRep_Tool::Pnt(aV));
1077     aBox.SetGap(aTol + aTolAdd);
1078     //
1079     aTreeFiller.Add(i, aBox);
1080     //
1081     BOPAlgo_TNV& aTNV=aVTNV.Appended();
1082     aTNV.SetTree(aBBTree);
1083     aTNV.SetBox(aBox);
1084     aTNV.SetVertex(aV);
1085     aTNV.SetTolerance(aTol);
1086     aTNV.SetFuzzyValue(theFuzzyValue);
1087     aTNV.SetVectorOfTNV(aVTNV);
1088   }
1089   // Shake the tree
1090   aTreeFiller.Fill();
1091   //
1092   // Perform intersection
1093   BOPAlgo_TNVCnt::Perform(theRunParallel, aVTNV);
1094   //
1095   // Fence map
1096   TColStd_MapOfInteger aMFence;
1097   // Build chains of intersecting vertices
1098   for (i = 1; i <= aNbV; ++i) {
1099     if (!aMFence.Add(i)) {
1100       continue;
1101     }
1102     // Start the chain
1103     TColStd_IndexedMapOfInteger aMChain;
1104     aMChain.Add(i);
1105     //
1106     for (j = 1; j <= aMChain.Extent(); ++j) {
1107       BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
1108       const TColStd_ListOfInteger& aLI = aTNV.Indices();
1109       // Add these vertices into the chain
1110       for (TColStd_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
1111         if (aMFence.Add(aItLI.Value())) {
1112           aMChain.Add(aItLI.Value());
1113         }
1114       }
1115     }
1116     //
1117     // Put vertices of the chain into the list
1118     TopTools_ListOfShape& aChain = theChains.Append(TopTools_ListOfShape());
1119     //
1120     Standard_Integer aNbVChain = aMChain.Extent();
1121     for (j = 1; j <= aNbVChain; ++j) {
1122       const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
1123       aChain.Append(aVP);
1124     }
1125   }
1126 }
1127
1128 //=======================================================================
1129 //function : TreatCompound
1130 //purpose  :
1131 //=======================================================================
1132 void BOPAlgo_Tools::TreatCompound(const TopoDS_Shape& theS,
1133                                   TopTools_MapOfShape& aMFence,
1134                                   TopTools_ListOfShape& theLS)
1135 {
1136   TopAbs_ShapeEnum aType = theS.ShapeType();
1137   if (aType != TopAbs_COMPOUND)
1138   {
1139     if (aMFence.Add(theS))
1140       theLS.Append(theS);
1141     return;
1142   }
1143   TopoDS_Iterator aIt(theS);
1144   for (; aIt.More(); aIt.Next())
1145   {
1146     const TopoDS_Shape& aS = aIt.Value();
1147     TreatCompound(aS, aMFence, theLS);
1148   }
1149 }
1150
1151 //=======================================================================
1152 // Classification of the faces relatively solids
1153 //=======================================================================
1154
1155 //=======================================================================
1156 //class     : BOPAlgo_ShapeBox
1157 //purpose   : Auxiliary class defining ShapeBox structure
1158 //=======================================================================
1159 class BOPAlgo_ShapeBox
1160 {
1161 public:
1162   //! Empty constructor
1163   BOPAlgo_ShapeBox() {};
1164   //! Sets the shape
1165   void SetShape(const TopoDS_Shape& theS)
1166   {
1167     myShape = theS;
1168   };
1169   //! Returns the shape
1170   const TopoDS_Shape& Shape() const
1171   {
1172     return myShape;
1173   };
1174   //! Sets the bounding box
1175   void SetBox(const Bnd_Box& theBox)
1176   {
1177     myBox = theBox;
1178   };
1179   //! Returns the bounding box
1180   const Bnd_Box& Box() const
1181   {
1182     return myBox;
1183   };
1184 private:
1185   TopoDS_Shape myShape;
1186   Bnd_Box myBox;
1187 };
1188 // Vector of ShapeBox
1189 typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
1190
1191 //=======================================================================
1192 //class : BOPAlgo_FillIn3DParts
1193 //purpose : Auxiliary class for faces classification in parallel mode
1194 //=======================================================================
1195 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1196 {
1197 public:
1198   DEFINE_STANDARD_ALLOC
1199
1200   //! Constructor
1201   BOPAlgo_FillIn3DParts()
1202   {
1203     myBBTree = NULL;
1204     myVShapeBox = NULL;
1205   };
1206
1207   //! Destructor
1208   virtual ~BOPAlgo_FillIn3DParts() {};
1209
1210   //! Sets the solid
1211   void SetSolid(const TopoDS_Solid& theSolid)
1212   {
1213     mySolid = theSolid;
1214   };
1215
1216   //! Returns the solid
1217   const TopoDS_Solid& Solid() const
1218   {
1219     return mySolid;
1220   };
1221
1222   //! Sets the box for the solid
1223   void SetBoxS(const Bnd_Box& theBox)
1224   {
1225     myBoxS = theBox;
1226   };
1227
1228   //! Returns the solid's box
1229   const Bnd_Box& BoxS() const
1230   {
1231     return myBoxS;
1232   };
1233
1234   //! Sets own INTERNAL faces of the solid
1235   void SetOwnIF(const TopTools_ListOfShape& theLIF)
1236   {
1237     myOwnIF = theLIF;
1238   };
1239
1240   //! Returns own INTERNAL faces of the solid
1241   const TopTools_ListOfShape& OwnIF() const
1242   {
1243     return myOwnIF;
1244   };
1245
1246   //! Sets the Bounding Box tree
1247   void SetBBTree(const BOPTools_BoxBndTree& theBBTree)
1248   {
1249     myBBTree = (BOPTools_BoxBndTree*)&theBBTree;
1250   };
1251
1252   //! Sets the ShapeBox structure
1253   void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1254   {
1255     myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1256   };
1257
1258   //! Sets the context
1259   void SetContext(const Handle(IntTools_Context)& theContext)
1260   {
1261     myContext = theContext;
1262   }
1263
1264   //! Returns the context
1265   const Handle(IntTools_Context)& Context() const
1266   {
1267     return myContext;
1268   }
1269
1270   //! Performs the classification
1271   virtual void Perform();
1272
1273   //! Returns the faces classified as IN for solid
1274   const TopTools_ListOfShape& InFaces() const
1275   {
1276     return myInFaces;
1277   };
1278
1279 private:
1280
1281   //! Prepares Edge-Face connection map of the given shape
1282   void MapEdgesAndFaces(const TopoDS_Shape& theF,
1283                         TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1284                         const Handle(NCollection_BaseAllocator)& theAlloc);
1285
1286   //! Makes the connexity block of faces using the connection map
1287   void MakeConnexityBlock(const TopoDS_Face& theF,
1288                           const TopTools_IndexedMapOfShape& theMEToAvoid,
1289                           const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1290                           TopTools_MapOfShape& theMFDone,
1291                           TopTools_ListOfShape& theLCB,
1292                           TopoDS_Face& theFaceToClassify);
1293
1294   TopoDS_Solid mySolid; //! Solid
1295   Bnd_Box myBoxS; // Bounding box of the solid
1296   TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1297   TopTools_ListOfShape myInFaces; //! Faces classified as IN
1298
1299   BOPTools_BoxBndTree* myBBTree; //! UB tree of bounding boxes
1300   BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1301
1302   TopoDS_Iterator myItF; //! Iterators
1303   TopoDS_Iterator myItW;
1304
1305   Handle(IntTools_Context) myContext; //! Context
1306 };
1307
1308 //=======================================================================
1309 //function : BOPAlgo_FillIn3DParts::Perform
1310 //purpose  :
1311 //=======================================================================
1312 void BOPAlgo_FillIn3DParts::Perform()
1313 {
1314   BOPAlgo_Algo::UserBreak();
1315
1316   myInFaces.Clear();
1317
1318   // 1. Select boxes of faces that are not out of aBoxS
1319   BOPTools_BoxBndTreeSelector aSelector;
1320   aSelector.SetBox(myBoxS);
1321   //
1322   if (!myBBTree->Select(aSelector))
1323     return;
1324
1325   const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
1326
1327   // 2. Fill maps of edges and faces of the solid
1328
1329   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1330
1331   BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1332
1333   TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1334   TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1335   TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
1336
1337   // Check if the Solid contains any faces
1338   Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1339
1340   // Add own internal faces of the solid into aMSF
1341   TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
1342   for (; aItLS.More(); aItLS.Next())
1343     aMSF.Add(aItLS.Value());
1344
1345   // 3. aIVec - faces to process.
1346   //    Filter the selected faces with faces of the solid.
1347   NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
1348
1349   TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
1350   for (; aItLI.More(); aItLI.Next()) {
1351     Standard_Integer nFP = aItLI.Value();
1352     const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1353     if (!aMSF.Contains(aFP))
1354       aIVec.Appended() = nFP;
1355   }
1356
1357   // 4. Classify faces relatively solid.
1358   //    Store faces that are IN mySolid into <myInFaces>
1359
1360   Standard_Integer k, aNbFP = aIVec.Length();
1361   // Sort indices if necessary
1362   if (aNbFP > 1)
1363     std::sort(aIVec.begin(), aIVec.end());
1364
1365   if (bIsEmpty)
1366   {
1367     // The solid is empty as it does not contain any faces.
1368     // It could happen when the input solid consists of INTERNAL faces only.
1369     // Classification of any point relatively empty solid would always give IN status.
1370     // Thus, we consider all selected faces as IN without real classification.
1371     for (k = 0; k < aNbFP; ++k)
1372       myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1373
1374     return;
1375   }
1376
1377   // Prepare EF map of faces to process for building connexity blocks
1378   TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
1379   if (aNbFP > 1)
1380   {
1381     for (k = 0; k < aNbFP; ++k)
1382       MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1383   }
1384
1385   // Map of Edge-Face connection, necessary for solid classification.
1386   // It will be filled when first classification is performed.
1387   TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
1388
1389   // Fence map to avoid processing of the same faces twice
1390   TopTools_MapOfShape aMFDone(1, anAlloc);
1391
1392   for (k = 0; k < aNbFP; ++k)
1393   {
1394     Standard_Integer nFP = aIVec(k);
1395     const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1396     if (!aMFDone.Add(aFP))
1397       continue;
1398
1399     // Make connexity blocks of faces, avoiding passing through the
1400     // borders of the solid. It helps to reduce significantly the
1401     // number of classified faces.
1402     TopTools_ListOfShape aLCBF(anAlloc);
1403     // The most appropriate face for classification
1404     TopoDS_Face aFaceToClassify;
1405     MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1406
1407     if (!myBoxS.IsWhole())
1408     {
1409       // First, try fast classification of the whole block by additional
1410       // check on bounding boxes - check that bounding boxes of all vertices
1411       // of the block interfere with the box of the solid.
1412       // If not, the faces are out.
1413       Standard_Boolean bOut = Standard_False;
1414       aItLS.Initialize(aLCBF);
1415       for (; aItLS.More() && !bOut; aItLS.Next())
1416       {
1417         TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1418         for (; anExpV.More() && !bOut; anExpV.Next())
1419         {
1420           const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1421           Bnd_Box aBBV;
1422           aBBV.Add(BRep_Tool::Pnt(aV));
1423           aBBV.SetGap(BRep_Tool::Tolerance(aV));
1424           bOut = myBoxS.IsOut(aBBV);
1425         }
1426       }
1427       if (bOut)
1428         continue;
1429     }
1430
1431     if (aFaceToClassify.IsNull())
1432       aFaceToClassify = aFP;
1433
1434     if (aMEFDS.IsEmpty())
1435       // Fill EF map for Solid
1436       TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
1437
1438     // All vertices are interfere with the solids box, run classification.
1439     Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1440       (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1441     if (bIsIN)
1442     {
1443       aItLS.Initialize(aLCBF);
1444       for (; aItLS.More(); aItLS.Next())
1445         myInFaces.Append(aItLS.Value());
1446     }
1447   }
1448 }
1449 //=======================================================================
1450 // function: MapEdgesAndFaces
1451 // purpose:
1452 //=======================================================================
1453 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1454                                              TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1455                                              const Handle(NCollection_BaseAllocator)& theAllocator)
1456 {
1457   myItF.Initialize(theF);
1458   for (; myItF.More(); myItF.Next())
1459   {
1460     const TopoDS_Shape& aW = myItF.Value();
1461     if (aW.ShapeType() != TopAbs_WIRE)
1462       continue;
1463
1464     myItW.Initialize(aW);
1465     for (; myItW.More(); myItW.Next())
1466     {
1467       const TopoDS_Shape& aE = myItW.Value();
1468
1469       TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
1470       if (!pLF)
1471         pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
1472       pLF->Append(theF);
1473     }
1474   }
1475 }
1476 //=======================================================================
1477 // function: MakeConnexityBlock
1478 // purpose:
1479 //=======================================================================
1480 void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1481                                                const TopTools_IndexedMapOfShape& theMEAvoid,
1482                                                const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1483                                                TopTools_MapOfShape& theMFDone,
1484                                                TopTools_ListOfShape& theLCB,
1485                                                TopoDS_Face& theFaceToClassify)
1486 {
1487   // Add start element
1488   theLCB.Append(theFStart);
1489   if (theEFMap.IsEmpty())
1490     return;
1491
1492   TopTools_ListIteratorOfListOfShape aItCB(theLCB);
1493   for (; aItCB.More(); aItCB.Next())
1494   {
1495     const TopoDS_Shape& aF = aItCB.Value();
1496     myItF.Initialize(aF);
1497     for (; myItF.More(); myItF.Next())
1498     {
1499       const TopoDS_Shape& aW = myItF.Value();
1500       if (aW.ShapeType() != TopAbs_WIRE)
1501         continue;
1502
1503       myItW.Initialize(aW);
1504       for (; myItW.More(); myItW.Next())
1505       {
1506         const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1507         if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
1508         {
1509           if (theFaceToClassify.IsNull())
1510             theFaceToClassify = TopoDS::Face(aF);
1511           continue;
1512         }
1513
1514         const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
1515         if (!pLF)
1516           continue;
1517         TopTools_ListIteratorOfListOfShape aItLF(*pLF);
1518         for (; aItLF.More(); aItLF.Next())
1519         {
1520           const TopoDS_Shape& aFToAdd = aItLF.Value();
1521           if (theMFDone.Add(aFToAdd))
1522             theLCB.Append(aFToAdd);
1523         }
1524       }
1525     }
1526   }
1527 }
1528
1529 // Vector of solid classifiers
1530 typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
1531
1532 // Functors to perform classification
1533 typedef BOPTools_ContextFunctor<BOPAlgo_FillIn3DParts,
1534                                 BOPAlgo_VectorOfFillIn3DParts,
1535                                 Handle(IntTools_Context),
1536                                 IntTools_Context> BOPAlgo_FillIn3DPartsFunctor;
1537
1538 typedef BOPTools_ContextCnt<BOPAlgo_FillIn3DPartsFunctor,
1539                             BOPAlgo_VectorOfFillIn3DParts,
1540                             Handle(IntTools_Context)> BOPAlgo_FillIn3DPartsCnt;
1541
1542 //=======================================================================
1543 //function : ClassifyFaces
1544 //purpose  :
1545 //=======================================================================
1546 void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1547                                   const TopTools_ListOfShape& theSolids,
1548                                   const Standard_Boolean theRunParallel,
1549                                   Handle(IntTools_Context)& theContext,
1550                                   TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1551                                   const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1552                                   const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
1553 {
1554   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1555
1556   // Fill the vector of shape box with faces and its bounding boxes
1557   BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1558
1559   TopTools_ListIteratorOfListOfShape aItLF(theFaces);
1560   for (; aItLF.More(); aItLF.Next())
1561   {
1562     const TopoDS_Shape& aF = aItLF.Value();
1563     // Append face to the vector of shape box
1564     BOPAlgo_ShapeBox& aSB = aVSB.Appended();
1565     aSB.SetShape(aF);
1566
1567     // Get bounding box for the face
1568     const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1569     if (pBox)
1570       aSB.SetBox(*pBox);
1571     else
1572     {
1573       // Build the bounding box
1574       Bnd_Box aBox;
1575       BRepBndLib::Add(aF, aBox);
1576       aSB.SetBox(aBox);
1577     }
1578   }
1579
1580   // Prepare UB tree of bounding boxes of the faces to classify
1581   // taking the bounding boxes from the just prepared vector
1582   BOPTools_BoxBndTree aBBTree;
1583   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
1584
1585   Standard_Integer aNbF = aVSB.Length();
1586   for (Standard_Integer i = 0; i < aNbF; ++i)
1587   {
1588     aTreeFiller.Add(i, aVSB(i).Box());
1589   }
1590
1591   // Shake tree filler
1592   aTreeFiller.Fill();
1593
1594   // Prepare vector of solids to classify
1595   BOPAlgo_VectorOfFillIn3DParts aVFIP;
1596
1597   TopTools_ListIteratorOfListOfShape aItLS(theSolids);
1598   for (; aItLS.More(); aItLS.Next())
1599   {
1600     const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1601     // Append solid to the vector
1602     BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
1603     aFIP.SetSolid(aSolid);
1604
1605     // Get bounding box for the solid
1606     const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1607     if (pBox)
1608       aFIP.SetBoxS(*pBox);
1609     else
1610     {
1611       // Build the bounding box
1612       Bnd_Box aBox;
1613       BRepBndLib::Add(aSolid, aBox);
1614       if (!aBox.IsWhole())
1615       {
1616         if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1617           aBox.SetWhole();
1618       }
1619       aFIP.SetBoxS(aBox);
1620     }
1621
1622     const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
1623     if (pLIF)
1624       aFIP.SetOwnIF(*pLIF);
1625
1626     aFIP.SetBBTree(aBBTree);
1627     aFIP.SetShapeBoxVector(aVSB);
1628   }
1629
1630   // Perform classification
1631   //================================================================
1632   BOPAlgo_FillIn3DPartsCnt::Perform(theRunParallel, aVFIP, theContext);
1633   //================================================================
1634
1635   // Analyze the results and fill the resulting map
1636
1637   Standard_Integer aNbS = aVFIP.Length();
1638   for (Standard_Integer i = 0; i < aNbS; ++i)
1639   {
1640     BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1641     const TopoDS_Shape& aS = aFIP.Solid();
1642     const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
1643     theInParts.Add(aS, aLFIn);
1644   }
1645 }
1646
1647 //=======================================================================
1648 //function : FillInternals
1649 //purpose  :
1650 //=======================================================================
1651 void BOPAlgo_Tools::FillInternals(const TopTools_ListOfShape& theSolids,
1652                                   const TopTools_ListOfShape& theParts,
1653                                   const TopTools_DataMapOfShapeListOfShape& theImages,
1654                                   const Handle(IntTools_Context)& theContext)
1655 {
1656   if (theSolids.IsEmpty() || theParts.IsEmpty())
1657     return;
1658
1659   // Map the solids to avoid classification of the own shapes of the solids
1660   TopTools_IndexedMapOfShape aMSSolids;
1661   TopTools_ListOfShape::Iterator itLS(theSolids);
1662   for (; itLS.More(); itLS.Next())
1663   {
1664     const TopoDS_Shape& aSolid = itLS.Value();
1665     if (aSolid.ShapeType() == TopAbs_SOLID)
1666     {
1667       TopExp::MapShapes(aSolid, TopAbs_VERTEX, aMSSolids);
1668       TopExp::MapShapes(aSolid, TopAbs_EDGE,   aMSSolids);
1669       TopExp::MapShapes(aSolid, TopAbs_FACE,   aMSSolids);
1670     }
1671   }
1672
1673   // Extract BRep elements from the given parts and
1674   // check them for possible splits
1675   TopTools_ListOfShape aLPartsInput = theParts, aLParts;
1676   TopTools_ListOfShape::Iterator itLP(aLPartsInput);
1677   for (; itLP.More(); itLP.Next())
1678   {
1679     const TopoDS_Shape& aPart = itLP.Value();
1680     switch (aPart.ShapeType())
1681     {
1682       case TopAbs_VERTEX:
1683       case TopAbs_EDGE:
1684       case TopAbs_FACE:
1685       {
1686         const TopTools_ListOfShape* pIm = theImages.Seek(aPart);
1687         if (pIm)
1688         {
1689           TopTools_ListOfShape::Iterator itIm(*pIm);
1690           for (; itIm.More(); itIm.Next())
1691           {
1692             const TopoDS_Shape& aPartIm = itIm.Value();
1693             if (!aMSSolids.Contains(aPartIm))
1694               aLParts.Append(aPartIm);
1695           }
1696         }
1697         else if (!aMSSolids.Contains(aPart))
1698           aLParts.Append(aPart);
1699
1700         break;
1701       }
1702       default:
1703       {
1704         for (TopoDS_Iterator it(aPart); it.More(); it.Next())
1705           aLPartsInput.Append(it.Value());
1706         break;
1707       }
1708     }
1709   }
1710
1711   // Classify the given parts relatively solids.
1712   // Add edges and vertices classified as IN into solids instantly,
1713   // and collect faces classified as IN into a list for further shell creation
1714
1715   TopTools_DataMapOfShapeListOfShape anINFaces;
1716   itLS.Initialize(theSolids);
1717   for (; itLS.More(); itLS.Next())
1718   {
1719     const TopoDS_Shape& aSolid = itLS.Value();
1720     if (aSolid.ShapeType() != TopAbs_SOLID)
1721       continue;
1722
1723     TopoDS_Solid aSd = *(TopoDS_Solid*)&aSolid;
1724
1725     itLP.Initialize(aLParts);
1726     for (; itLP.More();)
1727     {
1728       TopoDS_Shape aPart = itLP.Value();
1729       TopAbs_State aState =
1730         BOPTools_AlgoTools::ComputeStateByOnePoint(aPart, aSd, Precision::Confusion(), theContext);
1731       if (aState == TopAbs_IN)
1732       {
1733         if (aPart.ShapeType() == TopAbs_FACE)
1734         {
1735           TopTools_ListOfShape *pFaces = anINFaces.ChangeSeek(aSd);
1736           if (!pFaces)
1737             pFaces = anINFaces.Bound(aSd, TopTools_ListOfShape());
1738           pFaces->Append(aPart);
1739         }
1740         else
1741         {
1742           aPart.Orientation(TopAbs_INTERNAL);
1743           BRep_Builder().Add(aSd, aPart);
1744         }
1745         aLParts.Remove(itLP);
1746       }
1747       else
1748         itLP.Next();
1749     }
1750   }
1751
1752   // Make shells from faces and put them into solids
1753   TopTools_DataMapOfShapeListOfShape::Iterator itM(anINFaces);
1754   for (; itM.More(); itM.Next())
1755   {
1756     TopoDS_Solid aSd = *(TopoDS_Solid*)&itM.Key();
1757     const TopTools_ListOfShape& aFaces = itM.Value();
1758
1759     TopoDS_Compound aCF;
1760     BRep_Builder().MakeCompound(aCF);
1761
1762     TopTools_ListOfShape::Iterator itLF(aFaces);
1763     for (; itLF.More(); itLF.Next())
1764       BRep_Builder().Add(aCF, itLF.Value());
1765
1766     // Build blocks from the faces
1767     TopTools_ListOfShape aLCB;
1768     BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
1769
1770     // Build shell from each block
1771     TopTools_ListOfShape::Iterator itCB(aLCB);
1772     for (; itCB.More(); itCB.Next())
1773     {
1774       const TopoDS_Shape& aCB = itCB.Value();
1775
1776       TopoDS_Shell aShell;
1777       BRep_Builder().MakeShell(aShell);
1778       // Add faces of the block to the shell
1779       TopExp_Explorer expF(aCB, TopAbs_FACE);
1780       for (; expF.More(); expF.Next())
1781       {
1782         TopoDS_Face aFInt = TopoDS::Face(expF.Current());
1783         aFInt.Orientation(TopAbs_INTERNAL);
1784         BRep_Builder().Add(aShell, aFInt);
1785       }
1786
1787       BRep_Builder().Add(aSd, aShell);
1788     }
1789   }
1790 }