src/BOPAlgo/BOPAlgo_BuilderSolid.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
   3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
   4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
   5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   6 //
   7 // This file is part of Open CASCADE Technology software library.
   8 //
   9 // This library is free software; you can redistribute it and/or modify it under
  10 // the terms of the GNU Lesser General Public License version 2.1 as published
  11 // by the Free Software Foundation, with special exception defined in the file
  12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  13 // distribution for complete text of the license and disclaimer of any warranty.
  14 //
  15 // Alternatively, this file may be used under the terms of Open CASCADE
  16 // commercial license or contractual agreement.
  17 //
  18 #include <BOPAlgo_BuilderSolid.hxx>
  19 #include <BOPAlgo_ShellSplitter.hxx>
  20 #include <BOPCol_BoxBndTree.hxx>
  21 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
  22 #include <BOPCol_DataMapOfShapeShape.hxx>
  23 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
  24 #include <BOPCol_IndexedDataMapOfShapeShape.hxx>
  25 #include <BOPCol_ListOfInteger.hxx>
  26 #include <BOPCol_ListOfShape.hxx>
  27 #include <BOPCol_MapOfOrientedShape.hxx>
  28 #include <BOPCol_MapOfShape.hxx>
  29 #include <BOPCol_NCVector.hxx>
  30 #include <BOPCol_Parallel.hxx>
  31 #include <BOPTools.hxx>
  32 #include <BOPTools_AlgoTools.hxx>
  33 #include <BOPTools_AlgoTools3D.hxx>
  34 #include <BOPTools_CoupleOfShape.hxx>
  35 #include <BRep_Builder.hxx>
  36 #include <BRep_Tool.hxx>
  37 #include <BRepBndLib.hxx>
  38 #include <BRepClass3d_SolidClassifier.hxx>
  39 #include <Geom2d_Curve.hxx>
  40 #include <Geom_Curve.hxx>
  41 #include <Geom_Surface.hxx>
  42 #include <gp_Dir.hxx>
  43 #include <gp_Pln.hxx>
  44 #include <gp_Pnt.hxx>
  45 #include <gp_Pnt2d.hxx>
  46 #include <gp_Vec.hxx>
  47 #include <IntTools_Context.hxx>
  48 #include <NCollection_DataMap.hxx>
  49 #include <NCollection_List.hxx>
  50 #include <NCollection_UBTreeFiller.hxx>
  51 #include <TColStd_MapIntegerHasher.hxx>
  52 #include <TopAbs.hxx>
  53 #include <TopExp.hxx>
  54 #include <TopExp_Explorer.hxx>
  55 #include <TopoDS_Compound.hxx>
  56 #include <TopoDS_Edge.hxx>
  57 #include <TopoDS_Face.hxx>
  58 #include <TopoDS_Iterator.hxx>
  59 #include <TopoDS_Shape.hxx>
  60 #include <TopoDS_Shell.hxx>
  61 #include <TopoDS_Solid.hxx>
  62 #include <TopoDS_Vertex.hxx>
  63
  64 //
  65 static
  66   Standard_Boolean IsGrowthShell(const TopoDS_Shape& ,
  67                                  const BOPCol_IndexedMapOfShape& );
  68 static
  69   Standard_Boolean IsHole(const TopoDS_Shape& ,
  70                           Handle(IntTools_Context)& );
  71 static
  72   Standard_Boolean IsInside(const TopoDS_Shape& ,
  73                             const TopoDS_Shape& ,
  74                             Handle(IntTools_Context)& );
  75 static
  76   void MakeInternalShells(const BOPCol_IndexedMapOfShape& ,
  77                           BOPCol_ListOfShape& );
  78
  79 //=======================================================================
  80 //class     : BOPAlgo_BuilderSolid_ShapeBox
  81 //purpose   : Auxiliary class
  82 //=======================================================================
  83 class BOPAlgo_BuilderSolid_ShapeBox {
  84  public:
  85   BOPAlgo_BuilderSolid_ShapeBox() {
  86     myIsHole=Standard_False;
  87   };
  88   //
  89   ~BOPAlgo_BuilderSolid_ShapeBox() {
  90   };
  91   //
  92   void SetShape(const TopoDS_Shape& aS) {
  93     myShape=aS;
  94   };
  95   //
  96   const TopoDS_Shape& Shape()const {
  97     return myShape;
  98   };
  99   //
 100   void SetBox(const Bnd_Box& aBox) {
 101     myBox=aBox;
 102   };
 103   //
 104   const Bnd_Box& Box()const {
 105     return myBox;
 106   };
 107   //
 108   void SetIsHole(const Standard_Boolean bFlag) {
 109     myIsHole=bFlag;
 110   };
 111   //
 112   Standard_Boolean IsHole()const {
 113     return myIsHole;
 114   };
 115   //
 116  protected:
 117   Standard_Boolean myIsHole;
 118   TopoDS_Shape myShape;
 119   Bnd_Box myBox;
 120 };
 121 //
 122 typedef NCollection_DataMap
 123   <Standard_Integer,
 124   BOPAlgo_BuilderSolid_ShapeBox,
 125   TColStd_MapIntegerHasher> BOPAlgo_DataMapOfIntegerBSSB;
 126 //
 127 typedef BOPAlgo_DataMapOfIntegerBSSB::Iterator
 128   BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB;
 129 //
 130 //=======================================================================
 131 //function : BOPAlgo_FacePnt
 132 //purpose  :
 133 //=======================================================================
 134 class BOPAlgo_FacePnt {
 135  public:
 136   BOPAlgo_FacePnt() {
 137   }
 138   //
 139   virtual ~BOPAlgo_FacePnt() {
 140   }
 141   //
 142   void SetFace(const TopoDS_Face& aFace) {
 143     myFace=aFace;
 144   }
 145   //
 146   const TopoDS_Face& Face()const {
 147     return myFace;
 148   }
 149   //
 150   void SetPnt(const gp_Pnt& aPnt) {
 151     myPnt=aPnt;
 152   }
 153   //
 154   const gp_Pnt& Pnt()const {
 155     return myPnt;
 156   }
 157   //
 158  protected:
 159   gp_Pnt myPnt;
 160   TopoDS_Face myFace;
 161 };
 162 //
 163 typedef BOPCol_NCVector
 164   <BOPAlgo_FacePnt> BOPAlgo_VectorOfFacePnt;
 165 //
 166 //=======================================================================
 167 //function : BOPAlgo_FaceSolid
 168 //purpose  :
 169 //=======================================================================
 170 class BOPAlgo_FaceSolid : public BOPAlgo_Algo {
 171  public:
 172   DEFINE_STANDARD_ALLOC
 173
 174   BOPAlgo_FaceSolid() :
 175     myIsInternalFace(Standard_False) {
 176   }
 177   //
 178   virtual ~BOPAlgo_FaceSolid() {
 179   }
 180   //
 181   void SetFace(const TopoDS_Face& aFace) {
 182     myFace=aFace;
 183   }
 184   //
 185   const TopoDS_Face& Face()const {
 186     return myFace;
 187   }
 188   //
 189   void SetSolid(const TopoDS_Solid& aSolid) {
 190     mySolid=aSolid;
 191   }
 192   //
 193   const TopoDS_Solid& Solid()const {
 194     return mySolid;
 195   }
 196   //
 197   void SetPnt(const gp_Pnt& aPnt) {
 198     myPnt=aPnt;
 199   }
 200   //
 201   const gp_Pnt& Pnt()const {
 202     return myPnt;
 203   }
 204   void SetContext(const Handle(IntTools_Context)& aContext) {
 205     myContext=aContext;
 206   }
 207   //
 208   const Handle(IntTools_Context)& Context()const {
 209     return myContext;
 210   }
 211   //
 212   Standard_Boolean IsInternalFace() const {
 213     return myIsInternalFace;
 214   }
 215   //
 216   virtual void Perform () {
 217     TopAbs_State aState;
 218     //
 219     BOPAlgo_Algo::UserBreak();
 220     //
 221     aState=BOPTools_AlgoTools::ComputeState(myPnt, mySolid,
 222                                             Precision::Confusion(),
 223                                             myContext);
 224     //
 225     myIsInternalFace=(aState==TopAbs_IN);
 226   }
 227   //
 228  protected:
 229   Standard_Boolean myIsInternalFace;
 230   gp_Pnt myPnt;
 231   TopoDS_Face myFace;
 232   TopoDS_Solid mySolid;
 233   Handle(IntTools_Context) myContext;
 234 };
 235 //=======================================================================
 236 typedef BOPCol_NCVector
 237   <BOPAlgo_FaceSolid> BOPAlgo_VectorOfFaceSolid;
 238 //
 239 typedef BOPCol_ContextFunctor
 240   <BOPAlgo_FaceSolid,
 241   BOPAlgo_VectorOfFaceSolid,
 242   Handle(IntTools_Context),
 243   IntTools_Context> BOPAlgo_FaceSolidFunctor;
 244 //
 245 typedef BOPCol_ContextCnt
 246   <BOPAlgo_FaceSolidFunctor,
 247   BOPAlgo_VectorOfFaceSolid,
 248   Handle(IntTools_Context)> BOPAlgo_FaceSolidCnt;
 249 //
 250 //=======================================================================
 251
 252 //=======================================================================
 253 //function :
 254 //purpose  :
 255 //=======================================================================
 256 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid()
 257 :
 258   BOPAlgo_BuilderArea()
 259 {
 260 }
 261 //=======================================================================
 262 //function :
 263 //purpose  :
 264 //=======================================================================
 265 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid
 266   (const Handle(NCollection_BaseAllocator)& theAllocator)
 267 :
 268   BOPAlgo_BuilderArea(theAllocator)
 269 {
 270 }
 271 //=======================================================================
 272 //function : ~
 273 //purpose  :
 274 //=======================================================================
 275 BOPAlgo_BuilderSolid::~BOPAlgo_BuilderSolid()
 276 {
 277 }
 278 //=======================================================================
 279 //function : SetSolid
 280 //purpose  :
 281 //=======================================================================
 282 void BOPAlgo_BuilderSolid::SetSolid(const TopoDS_Solid& aS)
 283 {
 284   mySolid=aS;
 285 }
 286 //=======================================================================
 287 //function : Solid
 288 //purpose  :
 289 //=======================================================================
 290 const TopoDS_Solid& BOPAlgo_BuilderSolid::Solid()const
 291 {
 292   return mySolid;
 293 }
 294 //=======================================================================
 295 //function : Perform
 296 //purpose  :
 297 //=======================================================================
 298 void BOPAlgo_BuilderSolid::Perform()
 299 {
 300   myErrorStatus=0;
 301   //
 302   if (myContext.IsNull()) {
 303     myContext=new IntTools_Context;
 304   }
 305   //
 306   TopoDS_Compound aC;
 307   BRep_Builder aBB;
 308   BOPCol_ListIteratorOfListOfShape aIt;
 309   //
 310   aBB.MakeCompound(aC);
 311   aIt.Initialize(myShapes);
 312   for(; aIt.More(); aIt.Next()) {
 313     const TopoDS_Shape& aF=aIt.Value();
 314     aBB.Add(aC, aF);
 315   }
 316   //
 317   UserBreak();
 318   //
 319   PerformShapesToAvoid();
 320   if (myErrorStatus) {
 321     return;
 322   }
 323   //
 324   UserBreak();
 325   //
 326   PerformLoops();
 327   if (myErrorStatus) {
 328     return;
 329   }
 330   //
 331   UserBreak();
 332   //
 333   PerformAreas();
 334   if (myErrorStatus) {
 335     return;
 336   }
 337   //
 338   UserBreak();
 339   //
 340   PerformInternalShapes();
 341   if (myErrorStatus) {
 342     return;
 343   }
 344 }
 345 //=======================================================================
 346 //function :PerformShapesToAvoid
 347 //purpose  :
 348 //=======================================================================
 349 void BOPAlgo_BuilderSolid::PerformShapesToAvoid()
 350 {
 351   Standard_Boolean bFound;
 352   Standard_Integer i, iCnt, aNbE, aNbF;
 353   TopAbs_Orientation aOrE;
 354   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
 355   BOPCol_ListIteratorOfListOfShape aIt;
 356   //
 357   myShapesToAvoid.Clear();
 358   //
 359   iCnt=0;
 360   for(;;) {
 361     ++iCnt;
 362     bFound=Standard_False;
 363     //
 364     // 1. MEF
 365     aMEF.Clear();
 366     aIt.Initialize (myShapes);
 367     for (; aIt.More(); aIt.Next()) {
 368       const TopoDS_Shape& aF=aIt.Value();
 369       if (!myShapesToAvoid.Contains(aF)) {
 370         BOPTools::MapShapesAndAncestors(aF,
 371                                         TopAbs_EDGE,
 372                                         TopAbs_FACE,
 373                                         aMEF);
 374       }
 375     }
 376     aNbE=aMEF.Extent();
 377     //
 378     // 2. myFacesToAvoid
 379     for (i=1; i<=aNbE; ++i) {
 380       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aMEF.FindKey(i)));
 381       if (BRep_Tool::Degenerated(aE)) {
 382         continue;
 383       }
 384       //
 385       BOPCol_ListOfShape& aLF=aMEF.ChangeFromKey(aE);
 386       aNbF=aLF.Extent();
 387       if (!aNbF) {
 388         continue;
 389       }
 390       //
 391       aOrE=aE.Orientation();
 392       //
 393       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
 394       if (aNbF==1) {
 395         if (aOrE==TopAbs_INTERNAL) {
 396           continue;
 397         }
 398         bFound=Standard_True;
 399         myShapesToAvoid.Add(aF1);
 400       }
 401       else if (aNbF==2) {
 402         const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
 403         if (aF2.IsSame(aF1)) {
 404           if (BRep_Tool::IsClosed(aE, aF1)) {
 405             continue;
 406           }
 407           //
 408           if (aOrE==TopAbs_INTERNAL) {
 409             continue;
 410           }
 411           //
 412           bFound=Standard_True;
 413           myShapesToAvoid.Add(aF1);
 414           myShapesToAvoid.Add(aF2);
 415         }
 416       }
 417     }// for (i=1; i<=aNbE; ++i) {
 418     //
 419     if (!bFound) {
 420       break;
 421     }
 422     //
 423   }//for(;;) {
 424 }
 425 //=======================================================================
 426 //function : PerformLoops
 427 //purpose  :
 428 //=======================================================================
 429 void BOPAlgo_BuilderSolid::PerformLoops()
 430 {
 431   Standard_Integer iErr, i, aNbSh;
 432   BOPCol_ListIteratorOfListOfShape aIt;
 433   TopoDS_Iterator aItS;
 434   Handle(NCollection_BaseAllocator) aAlr;
 435   //
 436   myErrorStatus=0;
 437   myLoops.Clear();
 438   //
 439   aAlr=
 440     NCollection_BaseAllocator::CommonBaseAllocator();
 441   BOPAlgo_ShellSplitter aSSp(aAlr);
 442   //
 443   // 1. Shells Usual
 444   aIt.Initialize (myShapes);
 445   for (; aIt.More(); aIt.Next()) {
 446     const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
 447     if (myContext->IsInfiniteFace(aF)) {
 448       TopoDS_Shell aSh;
 449       BRep_Builder aBB;
 450       //
 451       aBB.MakeShell(aSh);
 452       aBB.Add(aSh, aF);
 453       myLoops.Append(aSh);
 454       continue;
 455     }
 456     //
 457     if (!myShapesToAvoid.Contains(aF)) {
 458       aSSp.AddStartElement(aF);
 459     }
 460   }
 461   //
 462   aSSp.SetRunParallel(myRunParallel);
 463   aSSp.Perform();
 464   iErr=aSSp.ErrorStatus();
 465   if (iErr) {
 466     return;
 467   }
 468   //
 469   const BOPCol_ListOfShape& aLSh=aSSp.Shells();
 470   aIt.Initialize (aLSh);
 471   for (; aIt.More(); aIt.Next()) {
 472     const TopoDS_Shape& aSh=aIt.Value();
 473     myLoops.Append(aSh);
 474   }
 475   //=================================================
 476   //
 477   // 2. Post Treatment
 478   BRep_Builder aBB;
 479   BOPCol_MapOfOrientedShape AddedFacesMap;
 480   BOPCol_IndexedDataMapOfShapeListOfShape aEFMap;
 481   BOPCol_MapOfOrientedShape aMP;
 482   //
 483   // a. collect all edges that are in loops
 484   aIt.Initialize (myLoops);
 485   for (; aIt.More(); aIt.Next()) {
 486     const TopoDS_Shape& aS=aIt.Value();
 487     aItS.Initialize(aS);
 488     for (; aItS.More(); aItS.Next()) {
 489       const TopoDS_Shape& aF=aItS.Value();
 490       aMP.Add(aF);
 491     }
 492   }
 493   //
 494   // b. collect all edges that are to avoid
 495   aNbSh = myShapesToAvoid.Extent();
 496   for (i = 1; i <= aNbSh; ++i) {
 497     const TopoDS_Shape& aF = myShapesToAvoid(i);
 498     aMP.Add(aF);
 499   }
 500   //
 501   // c. add all edges that are not processed to myShapesToAvoid
 502   aIt.Initialize (myShapes);
 503   for (; aIt.More(); aIt.Next()) {
 504     const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
 505     if (!myContext->IsInfiniteFace(aF)) {
 506       if (!aMP.Contains(aF)) {
 507         myShapesToAvoid.Add(aF);
 508       }
 509     }
 510   }
 511   //=================================================
 512   //
 513   // 3.Internal Shells
 514   myLoopsInternal.Clear();
 515   //
 516   aEFMap.Clear();
 517   AddedFacesMap.Clear();
 518   //
 519   aNbSh = myShapesToAvoid.Extent();
 520   for (i = 1; i <= aNbSh; ++i) {
 521     const TopoDS_Shape& aFF = myShapesToAvoid(i);
 522     BOPTools::MapShapesAndAncestors(aFF,
 523         TopAbs_EDGE, TopAbs_FACE,
 524         aEFMap);
 525   }
 526   //
 527   for (i = 1; i <= aNbSh; ++i) {
 528     const TopoDS_Shape& aFF = myShapesToAvoid(i);
 529     if (!AddedFacesMap.Add(aFF)) {
 530       continue;
 531     }
 532     //
 533     // make a new shell
 534     TopExp_Explorer aExp;
 535     TopoDS_Shell aShell;
 536     aBB.MakeShell(aShell);
 537     aBB.Add(aShell, aFF);
 538     //
 539     aItS.Initialize(aShell);
 540     for (; aItS.More(); aItS.Next()) {
 541       const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItS.Value()));
 542       //
 543       aExp.Init(aF, TopAbs_EDGE);
 544       for (; aExp.More(); aExp.Next()) {
 545         const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
 546         const BOPCol_ListOfShape& aLF=aEFMap.FindFromKey(aE);
 547         aIt.Initialize(aLF);
 548         for (; aIt.More(); aIt.Next()) {
 549           const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aIt.Value()));
 550           if (AddedFacesMap.Add(aFL)){
 551             aBB.Add(aShell, aFL);
 552           }
 553         }
 554       }
 555     }
 556     aShell.Closed (BRep_Tool::IsClosed (aShell));
 557     myLoopsInternal.Append(aShell);
 558   }
 559 }
 560 //=======================================================================
 561 //function : PerformAreas
 562 //purpose  :
 563 //=======================================================================
 564 void BOPAlgo_BuilderSolid::PerformAreas()
 565 {
 566   Standard_Boolean bIsGrowth, bIsHole;
 567   Standard_Integer i, k, aNbInOut, aNbMSH;
 568   BRep_Builder aBB;
 569   BOPCol_ListIteratorOfListOfShape aItLS;
 570   BOPCol_ListOfShape aNewSolids, aHoleShells;
 571   BOPCol_IndexedDataMapOfShapeShape aInOutMap;
 572   BOPCol_IndexedMapOfShape aMHF;
 573   BOPCol_ListIteratorOfListOfInteger aItLI;
 574   BOPCol_BoxBndTreeSelector aSelector;
 575   BOPCol_BoxBndTree aBBTree;
 576   NCollection_UBTreeFiller
 577     <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
 578   BOPAlgo_DataMapOfIntegerBSSB aDMISB(100);
 579   BOPCol_IndexedDataMapOfShapeListOfShape aMSH;
 580   BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB aItDMISB;
 581   //
 582   myErrorStatus=0;
 583   //
 584   myAreas.Clear();
 585   //
 586   //  Draft solids [aNewSolids]
 587   aItLS.Initialize(myLoops);
 588   for (k=0; aItLS.More(); aItLS.Next(), ++k) {
 589     TopoDS_Solid aSolid;
 590     Bnd_Box aBox;
 591     BOPAlgo_BuilderSolid_ShapeBox aSB;
 592     //
 593     const TopoDS_Shape& aShell = aItLS.Value();
 594     aSB.SetShape(aShell);
 595     //
 596     BRepBndLib::Add(aShell, aBox);
 597     bIsHole=Standard_False;
 598     //
 599     bIsGrowth=IsGrowthShell(aShell, aMHF);
 600     if (bIsGrowth) {
 601       // make a growth solid from a shell
 602       aBB.MakeSolid(aSolid);
 603       aBB.Add (aSolid, aShell);
 604       //
 605       aNewSolids.Append (aSolid);
 606       aSB.SetShape(aSolid);
 607     }
 608     else{
 609       // check if a shell is a hole
 610       bIsHole=IsHole(aShell, myContext);
 611       if (bIsHole) {
 612         aHoleShells.Append(aShell);
 613         BOPTools::MapShapes(aShell, TopAbs_FACE, aMHF);
 614         aSB.SetShape(aShell);
 615       }
 616       else {
 617         // make a growth solid from a shell
 618         aBB.MakeSolid(aSolid);
 619         aBB.Add (aSolid, aShell);
 620         //
 621         aNewSolids.Append (aSolid);
 622         aSB.SetShape(aSolid);
 623       }
 624     }
 625     //
 626     aSB.SetBox(aBox);
 627     aSB.SetIsHole(bIsHole);
 628     aDMISB.Bind(k, aSB);
 629   }
 630   //
 631   // 2. Prepare TreeFiller
 632   aItDMISB.Initialize(aDMISB);
 633   for (; aItDMISB.More(); aItDMISB.Next()) {
 634     k=aItDMISB.Key();
 635     const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
 636     //
 637     bIsHole=aSB.IsHole();
 638     if (bIsHole) {
 639       const Bnd_Box& aBox=aSB.Box();
 640       aTreeFiller.Add(k, aBox);
 641     }
 642   }
 643   //
 644   // 3. Shake TreeFiller
 645   aTreeFiller.Fill();
 646   //
 647   // 4. Find outer growth shell that is most close
 648   //    to each hole shell
 649   aItDMISB.Initialize(aDMISB);
 650   for (; aItDMISB.More(); aItDMISB.Next()) {
 651     k=aItDMISB.Key();
 652     const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
 653     bIsHole=aSB.IsHole();
 654     if (bIsHole) {
 655       continue;
 656     }
 657     //
 658     const TopoDS_Shape aSolid=aSB.Shape();
 659     const Bnd_Box& aBoxSolid=aSB.Box();
 660     //
 661     aSelector.Clear();
 662     aSelector.SetBox(aBoxSolid);
 663     //
 664     aBBTree.Select(aSelector);
 665     //
 666     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
 667     //
 668     aItLI.Initialize(aLI);
 669     for (; aItLI.More(); aItLI.Next()) {
 670       k=aItLI.Value();
 671       const BOPAlgo_BuilderSolid_ShapeBox& aSBk=aDMISB.Find(k);
 672       const TopoDS_Shape& aHole=aSBk.Shape();
 673       //
 674       if (!IsInside(aHole, aSolid, myContext)){
 675         continue;
 676       }
 677       //
 678       if (aInOutMap.Contains (aHole)){
 679         const TopoDS_Shape& aSolidWas = aInOutMap.FindFromKey(aHole);
 680         if (IsInside(aSolid, aSolidWas, myContext)) {
 681           aInOutMap.ChangeFromKey(aHole) = aSolid;
 682         }
 683       }
 684       else{
 685         aInOutMap.Add(aHole, aSolid);
 686       }
 687     }
 688   }//for (i = 1; i <= aNbDMISB; ++i) {
 689   //
 690   // 5. Map [Solid/Holes] -> aMSH
 691   aNbInOut = aInOutMap.Extent();
 692   for (i = 1; i <= aNbInOut; ++i) {
 693     const TopoDS_Shape& aHole = aInOutMap.FindKey(i);
 694     const TopoDS_Shape& aSolid = aInOutMap(i);
 695     //
 696     if (aMSH.Contains(aSolid)) {
 697       BOPCol_ListOfShape& aLH = aMSH.ChangeFromKey(aSolid);
 698       aLH.Append(aHole);
 699     }
 700     else {
 701       BOPCol_ListOfShape aLH;
 702       aLH.Append(aHole);
 703       aMSH.Add(aSolid, aLH);
 704     }
 705   }
 706   //
 707   // 6. Add aHoles to Solids
 708   aNbMSH = aMSH.Extent();
 709   for (i = 1; i <= aNbMSH; ++i) {
 710     TopoDS_Solid aSolid=(*(TopoDS_Solid*)(&(aMSH.FindKey(i))));
 711     const BOPCol_ListOfShape& aLH = aMSH(i);
 712     //
 713     aItLS.Initialize(aLH);
 714     for (; aItLS.More(); aItLS.Next()) {
 715       const TopoDS_Shape& aHole = aItLS.Value();
 716       aBB.Add (aSolid, aHole);
 717     }
 718     //
 719     // update classifier
 720     BRepClass3d_SolidClassifier& aSC=
 721       myContext->SolidClassifier(aSolid);
 722     aSC.Load(aSolid);
 723     //
 724   }
 725   //
 726   // 7. These aNewSolids are draft solids that
 727   // do not contain any internal shapes
 728   aItLS.Initialize(aNewSolids);
 729   for ( ; aItLS.More(); aItLS.Next()) {
 730     const TopoDS_Shape& aSx=aItLS.Value();
 731     myAreas.Append(aSx);
 732   }
 733   // Add holes that outside the solids to myAreas
 734   aItLS.Initialize(aHoleShells);
 735   for (; aItLS.More(); aItLS.Next()) {
 736     const TopoDS_Shape& aHole = aItLS.Value();
 737     if (!aInOutMap.Contains(aHole)){
 738       TopoDS_Solid aSolid;
 739       //
 740       aBB.MakeSolid(aSolid);
 741       aBB.Add (aSolid, aHole);
 742       //
 743       myAreas.Append(aSolid);
 744     }
 745   }
 746 }
 747 //=======================================================================
 748 //function : PerformInternalShapes
 749 //purpose  :
 750 //=======================================================================
 751 void BOPAlgo_BuilderSolid::PerformInternalShapes()
 752 {
 753   myErrorStatus=0;
 754   if (myAvoidInternalShapes) {
 755     return;
 756   }
 757   //
 758   Standard_Integer aNbFI=myLoopsInternal.Extent();
 759   if (!aNbFI) {// nothing to do
 760     return;
 761   }
 762   //
 763   Standard_Boolean bIsInternalFace;
 764   Standard_Integer k, aNbVFS, aNbSLF, aNbVFP, aNbA;
 765   BRep_Builder aBB;
 766   TopoDS_Iterator aIt;
 767   TopExp_Explorer aExp;
 768   BOPCol_ListIteratorOfListOfShape  aItLS;
 769   BOPCol_IndexedMapOfShape aMFs;
 770   BOPCol_ListOfShape aLSI;
 771   BOPAlgo_VectorOfFaceSolid aVFS;
 772   BOPAlgo_VectorOfFacePnt aVFP;
 773   BOPCol_ListIteratorOfListOfInteger aItLI;
 774   BOPCol_BoxBndTreeSelector aSelector;
 775   BOPCol_BoxBndTree aBBTree;
 776   NCollection_UBTreeFiller
 777     <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
 778   //
 779   aNbA=myAreas.Extent();
 780   //
 781   // 1. aVFP
 782   aItLS.Initialize(myLoopsInternal);
 783   for (; aItLS.More(); aItLS.Next()) {
 784     const TopoDS_Shape& aShell=aItLS.Value();
 785     aIt.Initialize(aShell);
 786     for (; aIt.More(); aIt.Next()) {
 787       const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
 788       //
 789       if (!aMFs.Contains(aF)) {
 790         aMFs.Add(aF);
 791         //
 792         gp_Pnt aP;
 793         gp_Pnt2d aP2D;
 794         //
 795         if (aNbA) {
 796           BOPTools_AlgoTools3D::PointInFace(aF, aP, aP2D, myContext);
 797         }
 798         //
 799         BOPAlgo_FacePnt& aFP=aVFP.Append1();
 800         aFP.SetFace(aF);
 801         aFP.SetPnt(aP);
 802       }
 803     }
 804   }
 805   //
 806   if (!aNbA) {
 807     // 7b. "Rest" faces treatment
 808     TopoDS_Solid aSolid;
 809     aBB.MakeSolid(aSolid);
 810     //
 811     MakeInternalShells(aMFs, aLSI);
 812     //
 813     aItLS.Initialize(aLSI);
 814     for (; aItLS.More(); aItLS.Next()) {
 815       const TopoDS_Shape& aSI=aItLS.Value();
 816        aBB.Add (aSolid, aSI);
 817     }
 818     myAreas.Append(aSolid);
 819     //
 820     return; // =>
 821   }//if (!aNbA) {
 822   //
 823   // 2. Prepare TreeFiller
 824   aNbVFP=aVFP.Extent();
 825   for(k=0; k<aNbVFP; ++k) {
 826     Bnd_Box aBox;
 827     //
 828     const BOPAlgo_FacePnt& aFP=aVFP(k);
 829     const TopoDS_Face& aF=aFP.Face();
 830     //
 831     BRepBndLib::Add(aF, aBox);
 832     aTreeFiller.Add(k, aBox);
 833   }
 834   //
 835   aTreeFiller.Fill();
 836   //
 837   // 3. Face/Solid candidates: aVFS
 838   aItLS.Initialize(myAreas);
 839   for (; aItLS.More(); aItLS.Next()) {
 840     Bnd_Box aBox;
 841     //
 842     TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aItLS.Value()));
 843     BRepBndLib::Add(aSolid, aBox);
 844     //
 845     aMFs.Clear();
 846     aExp.Init(aSolid, TopAbs_FACE);
 847     for (; aExp.More(); aExp.Next()) {
 848       const TopoDS_Shape& aFs=aExp.Current();
 849       aMFs.Add(aFs);
 850     }
 851     //
 852     aSelector.Clear();
 853     aSelector.SetBox(aBox);
 854     //
 855     aBBTree.Select(aSelector);
 856     //
 857     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
 858     aItLI.Initialize(aLI);
 859     for (; aItLI.More(); aItLI.Next()) {
 860       k=aItLI.Value();
 861       const BOPAlgo_FacePnt& aFP=aVFP(k);
 862       const TopoDS_Face& aF=aFP.Face();
 863       if (aMFs.Contains(aF)) {
 864         continue;
 865       }
 866       //
 867       const gp_Pnt& aP=aFP.Pnt();
 868       //
 869       BOPAlgo_FaceSolid& aFS=aVFS.Append1();
 870       aFS.SetPnt(aP);
 871       aFS.SetFace(aF);
 872       aFS.SetSolid(aSolid);
 873     }
 874   }
 875   //
 876   aNbVFS=aVFS.Extent();
 877   if (!aNbVFS) {
 878     return;
 879   }
 880   // 4. Refine candidares
 881   //=============================================================
 882   BOPAlgo_FaceSolidCnt::Perform(myRunParallel, aVFS, myContext);
 883   //=============================================================
 884   //
 885   // 5. Solid/Faces:  aMSLF
 886   BOPCol_IndexedDataMapOfShapeListOfShape aMSLF;
 887   BOPCol_MapOfShape aMFProcessed;
 888   //
 889   for (k=0; k < aNbVFS; ++k) {
 890     const BOPAlgo_FaceSolid& aFS=aVFS(k);
 891     //
 892     const TopoDS_Solid& aSolid=aFS.Solid();
 893     const TopoDS_Face& aF=aFS.Face();
 894     //
 895     bIsInternalFace=aFS.IsInternalFace();
 896     if (!bIsInternalFace) {
 897       continue;
 898     }
 899     //
 900     if (aMSLF.Contains(aSolid)) {
 901       BOPCol_ListOfShape& aLF=aMSLF.ChangeFromKey(aSolid);
 902       aLF.Append(aF);
 903     }
 904     else {
 905       BOPCol_ListOfShape aLF;
 906       //
 907       aLF.Append(aF);
 908       aMSLF.Add(aSolid, aLF);
 909     }
 910   }// for (k=0; k < aNbVE; ++k) {
 911   //
 912   // 6. Update Solids by internal Faces
 913   aNbSLF=aMSLF.Extent();
 914   for (k=1; k <= aNbSLF; ++k) {
 915     const TopoDS_Shape& aSolid=aMSLF.FindKey(k);
 916     TopoDS_Shape *pSolid=(TopoDS_Shape*)&aSolid;
 917     //
 918     const BOPCol_ListOfShape& aLF=aMSLF(k);
 919     //
 920     aMFs.Clear();
 921     aItLS.Initialize(aLF);
 922     for (; aItLS.More(); aItLS.Next()) {
 923       const TopoDS_Shape& aF=aItLS.Value();
 924       aMFs.Add(aF);
 925       aMFProcessed.Add(aF);
 926     }
 927     //
 928     aLSI.Clear();
 929     MakeInternalShells(aMFs, aLSI);
 930     //
 931     aItLS.Initialize(aLSI);
 932     for (; aItLS.More(); aItLS.Next()) {
 933       const TopoDS_Shape& aSI=aItLS.Value();
 934       aBB.Add (*pSolid, aSI);
 935     }
 936   }
 937   //
 938   // 7. "Rest" faces treatment (if there are)
 939   aMFs.Clear();
 940   for (k=0; k < aNbVFS; ++k) {
 941     const BOPAlgo_FaceSolid& aFS=aVFS(k);
 942     //
 943     const TopoDS_Face& aF=aFS.Face();
 944     if (!aMFProcessed.Contains(aF)) {
 945       aMFs.Add(aF);
 946     }
 947   }
 948   //
 949   aNbFI=aMFs.Extent();
 950   if (aNbFI) {
 951     TopoDS_Solid aSolid;
 952     aBB.MakeSolid(aSolid);
 953     //
 954     aLSI.Clear();
 955     MakeInternalShells(aMFs, aLSI);
 956     //
 957     aItLS.Initialize(aLSI);
 958     for (; aItLS.More(); aItLS.Next()) {
 959       const TopoDS_Shape& aSI=aItLS.Value();
 960       aBB.Add (aSolid, aSI);
 961     }
 962     myAreas.Append(aSolid);
 963   }
 964 }
 965 //=======================================================================
 966 //function : MakeInternalShells
 967 //purpose  :
 968 //=======================================================================
 969 void MakeInternalShells(const BOPCol_IndexedMapOfShape& theMF,
 970                         BOPCol_ListOfShape& theShells)
 971 {
 972   Standard_Integer i, aNbF;
 973   BRep_Builder aBB;
 974   BOPCol_ListIteratorOfListOfShape aItF;
 975   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
 976   BOPCol_MapOfShape aAddedFacesMap;
 977   //
 978   aNbF = theMF.Extent();
 979   for (i = 1; i <= aNbF; ++i) {
 980     TopoDS_Shape aF = theMF(i);
 981     BOPTools::MapShapesAndAncestors(aF,
 982         TopAbs_EDGE, TopAbs_FACE,
 983         aMEF);
 984   }
 985   //
 986   for (i = 1; i <= aNbF; ++i) {
 987     TopoDS_Shape aFF = theMF(i);
 988     if (!aAddedFacesMap.Add(aFF)) {
 989       continue;
 990     }
 991     //
 992     // make a new shell
 993     TopoDS_Shell aShell;
 994     aBB.MakeShell(aShell);
 995     aFF.Orientation(TopAbs_INTERNAL);
 996     aBB.Add(aShell, aFF);
 997     //
 998     TopoDS_Iterator aItAddedF (aShell);
 999     for (; aItAddedF.More(); aItAddedF.Next()) {
1000       const TopoDS_Shape& aF =aItAddedF.Value();
1001       //
1002       TopExp_Explorer aEdgeExp(aF, TopAbs_EDGE);
1003       for (; aEdgeExp.More(); aEdgeExp.Next()) {
1004         const TopoDS_Shape& aE =aEdgeExp.Current();
1005         const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
1006         aItF.Initialize(aLF);
1007         for (; aItF.More(); aItF.Next()) {
1008           TopoDS_Shape aFL=aItF.Value();
1009           if (aAddedFacesMap.Add(aFL)){
1010             aFL.Orientation(TopAbs_INTERNAL);
1011             aBB.Add(aShell, aFL);
1012           }
1013         }
1014       }
1015     }
1016     aShell.Closed (BRep_Tool::IsClosed (aShell));
1017     theShells.Append(aShell);
1018   }
1019 }
1020 //=======================================================================
1021 //function : IsHole
1022 //purpose  :
1023 //=======================================================================
1024 Standard_Boolean IsHole(const TopoDS_Shape& theS2,
1025                         Handle(IntTools_Context)& theContext)
1026 {
1027   TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
1028   BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
1029   //
1030   aClsf.PerformInfinitePoint(::RealSmall());
1031   //
1032   return (aClsf.State()==TopAbs_IN);
1033 }
1034 //=======================================================================
1035 //function : IsInside
1036 //purpose  :
1037 //=======================================================================
1038 Standard_Boolean IsInside(const TopoDS_Shape& theS1,
1039                           const TopoDS_Shape& theS2,
1040                           Handle(IntTools_Context)& theContext)
1041 {
1042   TopExp_Explorer aExp;
1043   TopAbs_State aState;
1044   //
1045   TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
1046   //
1047   aExp.Init(theS1, TopAbs_FACE);
1048   if (!aExp.More()){
1049     BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
1050     aClsf.PerformInfinitePoint(::RealSmall());
1051     aState=aClsf.State();
1052   }
1053   else {
1054     BOPCol_IndexedMapOfShape aBounds;
1055     BOPTools::MapShapes(*pS2, TopAbs_EDGE, aBounds);
1056     const TopoDS_Face& aF = (*(TopoDS_Face*)(&aExp.Current()));
1057     aState=BOPTools_AlgoTools::ComputeState(aF, *pS2,
1058                                             Precision::Confusion(),
1059                                             aBounds, theContext);
1060   }
1061   return (aState==TopAbs_IN);
1062 }
1063 //=======================================================================
1064 //function : IsGrowthShell
1065 //purpose  :
1066 //=======================================================================
1067 Standard_Boolean IsGrowthShell(const TopoDS_Shape& theShell,
1068                                const BOPCol_IndexedMapOfShape& theMHF)
1069 {
1070   Standard_Boolean bRet;
1071   TopoDS_Iterator aIt;
1072   //
1073   bRet=Standard_False;
1074   if (theMHF.Extent()) {
1075     aIt.Initialize(theShell);
1076     for(; aIt.More(); aIt.Next()) {
1077       const TopoDS_Shape& aF=aIt.Value();
1078       if (theMHF.Contains(aF)) {
1079         return !bRet;
1080       }
1081     }
1082   }
1083   return bRet;
1084 }