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