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<BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
 962
 963 //=======================================================================
 964 class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
 965  public:
 966   BOPAlgo_TNV()
 967     : BOPTools_BoxBndTreeSelector(),
 968       myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
 969   };
 970   //
 971   ~BOPAlgo_TNV(){
 972   };
 973   //
 974   void SetVertex(const TopoDS_Vertex& aV) {
 975     myV=aV;
 976     myPnt = BRep_Tool::Pnt(myV);
 977   }
 978   //
 979   const TopoDS_Vertex& Vertex()const {
 980     return myV;
 981   }
 982   //
 983   void SetTree(BOPTools_BoxBndTree& aTree) {
 984     myTree=&aTree;
 985   }
 986   //
 987   void SetTolerance(const Standard_Real theTol) {
 988     myTol = theTol;
 989   }
 990   //
 991   Standard_Real Tolerance() const {
 992     return myTol;
 993   }
 994   //
 995   const gp_Pnt& Pnt() const {
 996     return myPnt;
 997   }
 998   //
 999   void SetFuzzyValue(const Standard_Real theFuzzyValue) {
1000     myFuzzyValue = theFuzzyValue;
1001   }
1002   //
1003   void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
1004     myVecTNV = &theVec;
1005   }
1006   //
1007   virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
1008   {
1009     const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
1010     Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
1011     aTolSum2 *= aTolSum2;
1012     Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
1013     if (aD2 < aTolSum2)
1014       return BOPTools_BoxBndTreeSelector::Accept(theIndex);
1015     return Standard_False;
1016   }
1017   //
1018   void Perform() {
1019     myTree->Select(*this);
1020   }
1021   //
1022  protected:
1023   Standard_Real myTol;
1024   Standard_Real myFuzzyValue;
1025   gp_Pnt        myPnt;
1026   TopoDS_Vertex myV;
1027   BOPTools_BoxBndTree *myTree;
1028   const BOPAlgo_VectorOfTNV *myVecTNV;
1029 };
1030 //
1031 /////////////////////////////////////////////////////////////////////////
1032
1033 //=======================================================================
1034 //function : IntersectVertices
1035 //purpose  : Builds the chains of intersecting vertices
1036 //=======================================================================
1037 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
1038                                       const Standard_Boolean theRunParallel,
1039                                       const Standard_Real theFuzzyValue,
1040                                       TopTools_ListOfListOfShape& theChains)
1041 {
1042   Standard_Integer i, j, aNbV = theVertices.Extent();
1043   if (aNbV <= 1) {
1044     if (aNbV == 1) {
1045       theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
1046     }
1047     return;
1048   }
1049   //
1050   // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
1051   BOPTools_BoxBndTree aBBTree;
1052   NCollection_UBTreeFiller <Standard_Integer,
1053                             Bnd_Box> aTreeFiller(aBBTree);
1054   // Perform intersection of the vertices
1055   BOPAlgo_VectorOfTNV aVTNV;
1056   //
1057   // Use additional tolerance for intersection
1058   Standard_Real aTolAdd = theFuzzyValue / 2.;
1059   // Prepare the tree
1060   for (i = 1; i <= aNbV; ++i) {
1061     const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1062     Standard_Real aTol = BRep_Tool::Tolerance(aV);
1063     if (aTol < theVertices(i)) {
1064       aTol = theVertices(i);
1065     }
1066     // Build bnd box for vertex
1067     Bnd_Box aBox;
1068     aBox.Add(BRep_Tool::Pnt(aV));
1069     aBox.SetGap(aTol + aTolAdd);
1070     //
1071     aTreeFiller.Add(i, aBox);
1072     //
1073     BOPAlgo_TNV& aTNV=aVTNV.Appended();
1074     aTNV.SetTree(aBBTree);
1075     aTNV.SetBox(aBox);
1076     aTNV.SetVertex(aV);
1077     aTNV.SetTolerance(aTol);
1078     aTNV.SetFuzzyValue(theFuzzyValue);
1079     aTNV.SetVectorOfTNV(aVTNV);
1080   }
1081   // Shake the tree
1082   aTreeFiller.Fill();
1083   //
1084   // Perform intersection
1085   BOPTools_Parallel::Perform (theRunParallel, aVTNV);
1086   //
1087   // Fence map
1088   TColStd_MapOfInteger aMFence;
1089   // Build chains of intersecting vertices
1090   for (i = 1; i <= aNbV; ++i) {
1091     if (!aMFence.Add(i)) {
1092       continue;
1093     }
1094     // Start the chain
1095     TColStd_IndexedMapOfInteger aMChain;
1096     aMChain.Add(i);
1097     //
1098     for (j = 1; j <= aMChain.Extent(); ++j) {
1099       BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
1100       const TColStd_ListOfInteger& aLI = aTNV.Indices();
1101       // Add these vertices into the chain
1102       for (TColStd_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
1103         if (aMFence.Add(aItLI.Value())) {
1104           aMChain.Add(aItLI.Value());
1105         }
1106       }
1107     }
1108     //
1109     // Put vertices of the chain into the list
1110     TopTools_ListOfShape& aChain = theChains.Append(TopTools_ListOfShape());
1111     //
1112     Standard_Integer aNbVChain = aMChain.Extent();
1113     for (j = 1; j <= aNbVChain; ++j) {
1114       const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
1115       aChain.Append(aVP);
1116     }
1117   }
1118 }
1119
1120 //=======================================================================
1121 //function : TreatCompound
1122 //purpose  :
1123 //=======================================================================
1124 void BOPAlgo_Tools::TreatCompound(const TopoDS_Shape& theS,
1125                                   TopTools_MapOfShape& aMFence,
1126                                   TopTools_ListOfShape& theLS)
1127 {
1128   TopAbs_ShapeEnum aType = theS.ShapeType();
1129   if (aType != TopAbs_COMPOUND)
1130   {
1131     if (aMFence.Add(theS))
1132       theLS.Append(theS);
1133     return;
1134   }
1135   TopoDS_Iterator aIt(theS);
1136   for (; aIt.More(); aIt.Next())
1137   {
1138     const TopoDS_Shape& aS = aIt.Value();
1139     TreatCompound(aS, aMFence, theLS);
1140   }
1141 }
1142
1143 //=======================================================================
1144 // Classification of the faces relatively solids
1145 //=======================================================================
1146
1147 //=======================================================================
1148 //class     : BOPAlgo_ShapeBox
1149 //purpose   : Auxiliary class defining ShapeBox structure
1150 //=======================================================================
1151 class BOPAlgo_ShapeBox
1152 {
1153 public:
1154   //! Empty constructor
1155   BOPAlgo_ShapeBox() {};
1156   //! Sets the shape
1157   void SetShape(const TopoDS_Shape& theS)
1158   {
1159     myShape = theS;
1160   };
1161   //! Returns the shape
1162   const TopoDS_Shape& Shape() const
1163   {
1164     return myShape;
1165   };
1166   //! Sets the bounding box
1167   void SetBox(const Bnd_Box& theBox)
1168   {
1169     myBox = theBox;
1170   };
1171   //! Returns the bounding box
1172   const Bnd_Box& Box() const
1173   {
1174     return myBox;
1175   };
1176 private:
1177   TopoDS_Shape myShape;
1178   Bnd_Box myBox;
1179 };
1180 // Vector of ShapeBox
1181 typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
1182
1183 //=======================================================================
1184 //class : BOPAlgo_FillIn3DParts
1185 //purpose : Auxiliary class for faces classification in parallel mode
1186 //=======================================================================
1187 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1188 {
1189 public:
1190   DEFINE_STANDARD_ALLOC
1191
1192   //! Constructor
1193   BOPAlgo_FillIn3DParts()
1194   {
1195     myBBTree = NULL;
1196     myVShapeBox = NULL;
1197   };
1198
1199   //! Destructor
1200   virtual ~BOPAlgo_FillIn3DParts() {};
1201
1202   //! Sets the solid
1203   void SetSolid(const TopoDS_Solid& theSolid)
1204   {
1205     mySolid = theSolid;
1206   };
1207
1208   //! Returns the solid
1209   const TopoDS_Solid& Solid() const
1210   {
1211     return mySolid;
1212   };
1213
1214   //! Sets the box for the solid
1215   void SetBoxS(const Bnd_Box& theBox)
1216   {
1217     myBoxS = theBox;
1218   };
1219
1220   //! Returns the solid's box
1221   const Bnd_Box& BoxS() const
1222   {
1223     return myBoxS;
1224   };
1225
1226   //! Sets own INTERNAL faces of the solid
1227   void SetOwnIF(const TopTools_ListOfShape& theLIF)
1228   {
1229     myOwnIF = theLIF;
1230   };
1231
1232   //! Returns own INTERNAL faces of the solid
1233   const TopTools_ListOfShape& OwnIF() const
1234   {
1235     return myOwnIF;
1236   };
1237
1238   //! Sets the Bounding Box tree
1239   void SetBBTree(const BOPTools_BoxBndTree& theBBTree)
1240   {
1241     myBBTree = (BOPTools_BoxBndTree*)&theBBTree;
1242   };
1243
1244   //! Sets the ShapeBox structure
1245   void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1246   {
1247     myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1248   };
1249
1250   //! Sets the context
1251   void SetContext(const Handle(IntTools_Context)& theContext)
1252   {
1253     myContext = theContext;
1254   }
1255
1256   //! Returns the context
1257   const Handle(IntTools_Context)& Context() const
1258   {
1259     return myContext;
1260   }
1261
1262   //! Performs the classification
1263   virtual void Perform();
1264
1265   //! Returns the faces classified as IN for solid
1266   const TopTools_ListOfShape& InFaces() const
1267   {
1268     return myInFaces;
1269   };
1270
1271 private:
1272
1273   //! Prepares Edge-Face connection map of the given shape
1274   void MapEdgesAndFaces(const TopoDS_Shape& theF,
1275                         TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1276                         const Handle(NCollection_BaseAllocator)& theAlloc);
1277
1278   //! Makes the connexity block of faces using the connection map
1279   void MakeConnexityBlock(const TopoDS_Face& theF,
1280                           const TopTools_IndexedMapOfShape& theMEToAvoid,
1281                           const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1282                           TopTools_MapOfShape& theMFDone,
1283                           TopTools_ListOfShape& theLCB,
1284                           TopoDS_Face& theFaceToClassify);
1285
1286   TopoDS_Solid mySolid; //! Solid
1287   Bnd_Box myBoxS; // Bounding box of the solid
1288   TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1289   TopTools_ListOfShape myInFaces; //! Faces classified as IN
1290
1291   BOPTools_BoxBndTree* myBBTree; //! UB tree of bounding boxes
1292   BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1293
1294   TopoDS_Iterator myItF; //! Iterators
1295   TopoDS_Iterator myItW;
1296
1297   Handle(IntTools_Context) myContext; //! Context
1298 };
1299
1300 //=======================================================================
1301 //function : BOPAlgo_FillIn3DParts::Perform
1302 //purpose  :
1303 //=======================================================================
1304 void BOPAlgo_FillIn3DParts::Perform()
1305 {
1306   BOPAlgo_Algo::UserBreak();
1307
1308   myInFaces.Clear();
1309
1310   // 1. Select boxes of faces that are not out of aBoxS
1311   BOPTools_BoxBndTreeSelector aSelector;
1312   aSelector.SetBox(myBoxS);
1313   //
1314   if (!myBBTree->Select(aSelector))
1315     return;
1316
1317   const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
1318
1319   // 2. Fill maps of edges and faces of the solid
1320
1321   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1322
1323   BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1324
1325   TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1326   TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1327   TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
1328
1329   // Check if the Solid contains any faces
1330   Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1331
1332   // Add own internal faces of the solid into aMSF
1333   TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
1334   for (; aItLS.More(); aItLS.Next())
1335     aMSF.Add(aItLS.Value());
1336
1337   // 3. aIVec - faces to process.
1338   //    Filter the selected faces with faces of the solid.
1339   NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
1340
1341   TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
1342   for (; aItLI.More(); aItLI.Next()) {
1343     Standard_Integer nFP = aItLI.Value();
1344     const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1345     if (!aMSF.Contains(aFP))
1346       aIVec.Appended() = nFP;
1347   }
1348
1349   // 4. Classify faces relatively solid.
1350   //    Store faces that are IN mySolid into <myInFaces>
1351
1352   Standard_Integer k, aNbFP = aIVec.Length();
1353   // Sort indices if necessary
1354   if (aNbFP > 1)
1355     std::sort(aIVec.begin(), aIVec.end());
1356
1357   if (bIsEmpty)
1358   {
1359     // The solid is empty as it does not contain any faces.
1360     // It could happen when the input solid consists of INTERNAL faces only.
1361     // Classification of any point relatively empty solid would always give IN status.
1362     // Thus, we consider all selected faces as IN without real classification.
1363     for (k = 0; k < aNbFP; ++k)
1364       myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1365
1366     return;
1367   }
1368
1369   // Prepare EF map of faces to process for building connexity blocks
1370   TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
1371   if (aNbFP > 1)
1372   {
1373     for (k = 0; k < aNbFP; ++k)
1374       MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1375   }
1376
1377   // Map of Edge-Face connection, necessary for solid classification.
1378   // It will be filled when first classification is performed.
1379   TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
1380
1381   // Fence map to avoid processing of the same faces twice
1382   TopTools_MapOfShape aMFDone(1, anAlloc);
1383
1384   for (k = 0; k < aNbFP; ++k)
1385   {
1386     Standard_Integer nFP = aIVec(k);
1387     const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1388     if (!aMFDone.Add(aFP))
1389       continue;
1390
1391     // Make connexity blocks of faces, avoiding passing through the
1392     // borders of the solid. It helps to reduce significantly the
1393     // number of classified faces.
1394     TopTools_ListOfShape aLCBF(anAlloc);
1395     // The most appropriate face for classification
1396     TopoDS_Face aFaceToClassify;
1397     MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1398
1399     if (!myBoxS.IsWhole())
1400     {
1401       // First, try fast classification of the whole block by additional
1402       // check on bounding boxes - check that bounding boxes of all vertices
1403       // of the block interfere with the box of the solid.
1404       // If not, the faces are out.
1405       Standard_Boolean bOut = Standard_False;
1406       aItLS.Initialize(aLCBF);
1407       for (; aItLS.More() && !bOut; aItLS.Next())
1408       {
1409         TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1410         for (; anExpV.More() && !bOut; anExpV.Next())
1411         {
1412           const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1413           Bnd_Box aBBV;
1414           aBBV.Add(BRep_Tool::Pnt(aV));
1415           aBBV.SetGap(BRep_Tool::Tolerance(aV));
1416           bOut = myBoxS.IsOut(aBBV);
1417         }
1418       }
1419       if (bOut)
1420         continue;
1421     }
1422
1423     if (aFaceToClassify.IsNull())
1424       aFaceToClassify = aFP;
1425
1426     if (aMEFDS.IsEmpty())
1427       // Fill EF map for Solid
1428       TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
1429
1430     // All vertices are interfere with the solids box, run classification.
1431     Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1432       (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1433     if (bIsIN)
1434     {
1435       aItLS.Initialize(aLCBF);
1436       for (; aItLS.More(); aItLS.Next())
1437         myInFaces.Append(aItLS.Value());
1438     }
1439   }
1440 }
1441 //=======================================================================
1442 // function: MapEdgesAndFaces
1443 // purpose:
1444 //=======================================================================
1445 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1446                                              TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1447                                              const Handle(NCollection_BaseAllocator)& theAllocator)
1448 {
1449   myItF.Initialize(theF);
1450   for (; myItF.More(); myItF.Next())
1451   {
1452     const TopoDS_Shape& aW = myItF.Value();
1453     if (aW.ShapeType() != TopAbs_WIRE)
1454       continue;
1455
1456     myItW.Initialize(aW);
1457     for (; myItW.More(); myItW.Next())
1458     {
1459       const TopoDS_Shape& aE = myItW.Value();
1460
1461       TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
1462       if (!pLF)
1463         pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
1464       pLF->Append(theF);
1465     }
1466   }
1467 }
1468 //=======================================================================
1469 // function: MakeConnexityBlock
1470 // purpose:
1471 //=======================================================================
1472 void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1473                                                const TopTools_IndexedMapOfShape& theMEAvoid,
1474                                                const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1475                                                TopTools_MapOfShape& theMFDone,
1476                                                TopTools_ListOfShape& theLCB,
1477                                                TopoDS_Face& theFaceToClassify)
1478 {
1479   // Add start element
1480   theLCB.Append(theFStart);
1481   if (theEFMap.IsEmpty())
1482     return;
1483
1484   TopTools_ListIteratorOfListOfShape aItCB(theLCB);
1485   for (; aItCB.More(); aItCB.Next())
1486   {
1487     const TopoDS_Shape& aF = aItCB.Value();
1488     myItF.Initialize(aF);
1489     for (; myItF.More(); myItF.Next())
1490     {
1491       const TopoDS_Shape& aW = myItF.Value();
1492       if (aW.ShapeType() != TopAbs_WIRE)
1493         continue;
1494
1495       myItW.Initialize(aW);
1496       for (; myItW.More(); myItW.Next())
1497       {
1498         const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1499         if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
1500         {
1501           if (theFaceToClassify.IsNull())
1502             theFaceToClassify = TopoDS::Face(aF);
1503           continue;
1504         }
1505
1506         const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
1507         if (!pLF)
1508           continue;
1509         TopTools_ListIteratorOfListOfShape aItLF(*pLF);
1510         for (; aItLF.More(); aItLF.Next())
1511         {
1512           const TopoDS_Shape& aFToAdd = aItLF.Value();
1513           if (theMFDone.Add(aFToAdd))
1514             theLCB.Append(aFToAdd);
1515         }
1516       }
1517     }
1518   }
1519 }
1520
1521 // Vector of solid classifiers
1522 typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
1523
1524 //=======================================================================
1525 //function : ClassifyFaces
1526 //purpose  :
1527 //=======================================================================
1528 void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1529                                   const TopTools_ListOfShape& theSolids,
1530                                   const Standard_Boolean theRunParallel,
1531                                   Handle(IntTools_Context)& theContext,
1532                                   TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1533                                   const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1534                                   const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
1535 {
1536   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1537
1538   // Fill the vector of shape box with faces and its bounding boxes
1539   BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1540
1541   TopTools_ListIteratorOfListOfShape aItLF(theFaces);
1542   for (; aItLF.More(); aItLF.Next())
1543   {
1544     const TopoDS_Shape& aF = aItLF.Value();
1545     // Append face to the vector of shape box
1546     BOPAlgo_ShapeBox& aSB = aVSB.Appended();
1547     aSB.SetShape(aF);
1548
1549     // Get bounding box for the face
1550     const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1551     if (pBox)
1552       aSB.SetBox(*pBox);
1553     else
1554     {
1555       // Build the bounding box
1556       Bnd_Box aBox;
1557       BRepBndLib::Add(aF, aBox);
1558       aSB.SetBox(aBox);
1559     }
1560   }
1561
1562   // Prepare UB tree of bounding boxes of the faces to classify
1563   // taking the bounding boxes from the just prepared vector
1564   BOPTools_BoxBndTree aBBTree;
1565   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
1566
1567   Standard_Integer aNbF = aVSB.Length();
1568   for (Standard_Integer i = 0; i < aNbF; ++i)
1569   {
1570     aTreeFiller.Add(i, aVSB(i).Box());
1571   }
1572
1573   // Shake tree filler
1574   aTreeFiller.Fill();
1575
1576   // Prepare vector of solids to classify
1577   BOPAlgo_VectorOfFillIn3DParts aVFIP;
1578
1579   TopTools_ListIteratorOfListOfShape aItLS(theSolids);
1580   for (; aItLS.More(); aItLS.Next())
1581   {
1582     const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1583     // Append solid to the vector
1584     BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
1585     aFIP.SetSolid(aSolid);
1586
1587     // Get bounding box for the solid
1588     const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1589     if (pBox)
1590       aFIP.SetBoxS(*pBox);
1591     else
1592     {
1593       // Build the bounding box
1594       Bnd_Box aBox;
1595       BRepBndLib::Add(aSolid, aBox);
1596       if (!aBox.IsWhole())
1597       {
1598         if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1599           aBox.SetWhole();
1600       }
1601       aFIP.SetBoxS(aBox);
1602     }
1603
1604     const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
1605     if (pLIF)
1606       aFIP.SetOwnIF(*pLIF);
1607
1608     aFIP.SetBBTree(aBBTree);
1609     aFIP.SetShapeBoxVector(aVSB);
1610   }
1611
1612   // Perform classification
1613   //================================================================
1614   BOPTools_Parallel::Perform (theRunParallel, aVFIP, theContext);
1615   //================================================================
1616
1617   // Analyze the results and fill the resulting map
1618
1619   Standard_Integer aNbS = aVFIP.Length();
1620   for (Standard_Integer i = 0; i < aNbS; ++i)
1621   {
1622     BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1623     const TopoDS_Shape& aS = aFIP.Solid();
1624     const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
1625     theInParts.Add(aS, aLFIn);
1626   }
1627 }
1628
1629 //=======================================================================
1630 //function : FillInternals
1631 //purpose  :
1632 //=======================================================================
1633 void BOPAlgo_Tools::FillInternals(const TopTools_ListOfShape& theSolids,
1634                                   const TopTools_ListOfShape& theParts,
1635                                   const TopTools_DataMapOfShapeListOfShape& theImages,
1636                                   const Handle(IntTools_Context)& theContext)
1637 {
1638   if (theSolids.IsEmpty() || theParts.IsEmpty())
1639     return;
1640
1641   // Map the solids to avoid classification of the own shapes of the solids
1642   TopTools_IndexedMapOfShape aMSSolids;
1643   TopTools_ListOfShape::Iterator itLS(theSolids);
1644   for (; itLS.More(); itLS.Next())
1645   {
1646     const TopoDS_Shape& aSolid = itLS.Value();
1647     if (aSolid.ShapeType() == TopAbs_SOLID)
1648     {
1649       TopExp::MapShapes(aSolid, TopAbs_VERTEX, aMSSolids);
1650       TopExp::MapShapes(aSolid, TopAbs_EDGE,   aMSSolids);
1651       TopExp::MapShapes(aSolid, TopAbs_FACE,   aMSSolids);
1652     }
1653   }
1654
1655   // Extract BRep elements from the given parts and
1656   // check them for possible splits
1657   TopTools_ListOfShape aLPartsInput = theParts, aLParts;
1658   TopTools_ListOfShape::Iterator itLP(aLPartsInput);
1659   for (; itLP.More(); itLP.Next())
1660   {
1661     const TopoDS_Shape& aPart = itLP.Value();
1662     switch (aPart.ShapeType())
1663     {
1664       case TopAbs_VERTEX:
1665       case TopAbs_EDGE:
1666       case TopAbs_FACE:
1667       {
1668         const TopTools_ListOfShape* pIm = theImages.Seek(aPart);
1669         if (pIm)
1670         {
1671           TopTools_ListOfShape::Iterator itIm(*pIm);
1672           for (; itIm.More(); itIm.Next())
1673           {
1674             const TopoDS_Shape& aPartIm = itIm.Value();
1675             if (!aMSSolids.Contains(aPartIm))
1676               aLParts.Append(aPartIm);
1677           }
1678         }
1679         else if (!aMSSolids.Contains(aPart))
1680           aLParts.Append(aPart);
1681
1682         break;
1683       }
1684       default:
1685       {
1686         for (TopoDS_Iterator it(aPart); it.More(); it.Next())
1687           aLPartsInput.Append(it.Value());
1688         break;
1689       }
1690     }
1691   }
1692
1693   // Classify the given parts relatively solids.
1694   // Add edges and vertices classified as IN into solids instantly,
1695   // and collect faces classified as IN into a list for further shell creation
1696
1697   TopTools_DataMapOfShapeListOfShape anINFaces;
1698   itLS.Initialize(theSolids);
1699   for (; itLS.More(); itLS.Next())
1700   {
1701     const TopoDS_Shape& aSolid = itLS.Value();
1702     if (aSolid.ShapeType() != TopAbs_SOLID)
1703       continue;
1704
1705     TopoDS_Solid aSd = *(TopoDS_Solid*)&aSolid;
1706
1707     itLP.Initialize(aLParts);
1708     for (; itLP.More();)
1709     {
1710       TopoDS_Shape aPart = itLP.Value();
1711       TopAbs_State aState =
1712         BOPTools_AlgoTools::ComputeStateByOnePoint(aPart, aSd, Precision::Confusion(), theContext);
1713       if (aState == TopAbs_IN)
1714       {
1715         if (aPart.ShapeType() == TopAbs_FACE)
1716         {
1717           TopTools_ListOfShape *pFaces = anINFaces.ChangeSeek(aSd);
1718           if (!pFaces)
1719             pFaces = anINFaces.Bound(aSd, TopTools_ListOfShape());
1720           pFaces->Append(aPart);
1721         }
1722         else
1723         {
1724           aPart.Orientation(TopAbs_INTERNAL);
1725           BRep_Builder().Add(aSd, aPart);
1726         }
1727         aLParts.Remove(itLP);
1728       }
1729       else
1730         itLP.Next();
1731     }
1732   }
1733
1734   // Make shells from faces and put them into solids
1735   TopTools_DataMapOfShapeListOfShape::Iterator itM(anINFaces);
1736   for (; itM.More(); itM.Next())
1737   {
1738     TopoDS_Solid aSd = *(TopoDS_Solid*)&itM.Key();
1739     const TopTools_ListOfShape& aFaces = itM.Value();
1740
1741     TopoDS_Compound aCF;
1742     BRep_Builder().MakeCompound(aCF);
1743
1744     TopTools_ListOfShape::Iterator itLF(aFaces);
1745     for (; itLF.More(); itLF.Next())
1746       BRep_Builder().Add(aCF, itLF.Value());
1747
1748     // Build blocks from the faces
1749     TopTools_ListOfShape aLCB;
1750     BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
1751
1752     // Build shell from each block
1753     TopTools_ListOfShape::Iterator itCB(aLCB);
1754     for (; itCB.More(); itCB.Next())
1755     {
1756       const TopoDS_Shape& aCB = itCB.Value();
1757
1758       TopoDS_Shell aShell;
1759       BRep_Builder().MakeShell(aShell);
1760       // Add faces of the block to the shell
1761       TopExp_Explorer expF(aCB, TopAbs_FACE);
1762       for (; expF.More(); expF.Next())
1763       {
1764         TopoDS_Face aFInt = TopoDS::Face(expF.Current());
1765         aFInt.Orientation(TopAbs_INTERNAL);
1766         BRep_Builder().Add(aShell, aFInt);
1767       }
1768
1769       BRep_Builder().Add(aSd, aShell);
1770     }
1771   }
1772 }