src/BOPAlgo/BOPAlgo_BuilderFace.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 2010-2012 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 //
   8 // This file is part of Open CASCADE Technology software library.
   9 //
  10 // This library is free software; you can redistribute it and/or modify it under
  11 // the terms of the GNU Lesser General Public License version 2.1 as published
  12 // by the Free Software Foundation, with special exception defined in the file
  13 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  14 // distribution for complete text of the license and disclaimer of any warranty.
  15 //
  16 // Alternatively, this file may be used under the terms of Open CASCADE
  17 // commercial license or contractual agreement.
  18
  19 #include <Bnd_Box.hxx>
  20 #include <BOPAlgo_BuilderFace.hxx>
  21 #include <BOPAlgo_WireEdgeSet.hxx>
  22 #include <BOPAlgo_WireSplitter.hxx>
  23 #include <BOPAlgo_Alerts.hxx>
  24 #include <BOPCol_Box2DBndTree.hxx>
  25 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
  26 #include <BOPCol_DataMapOfShapeShape.hxx>
  27 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
  28 #include <BOPCol_ListOfShape.hxx>
  29 #include <BOPCol_MapOfShape.hxx>
  30 #include <BOPCol_MapOfOrientedShape.hxx>
  31 #include <BOPTools.hxx>
  32 #include <BOPTools_AlgoTools.hxx>
  33 #include <BOPTools_AlgoTools2D.hxx>
  34 #include <BRep_Builder.hxx>
  35 #include <BRep_Tool.hxx>
  36 #include <BRepBndLib.hxx>
  37 #include <BRepTools.hxx>
  38 #include <Geom_Surface.hxx>
  39 #include <gp_Dir.hxx>
  40 #include <gp_Pln.hxx>
  41 #include <gp_Pnt.hxx>
  42 #include <gp_Pnt2d.hxx>
  43 #include <gp_Vec.hxx>
  44 #include <IntTools_Context.hxx>
  45 #include <IntTools_FClass2d.hxx>
  46 #include <NCollection_DataMap.hxx>
  47 #include <NCollection_UBTreeFiller.hxx>
  48 #include <TColStd_MapIntegerHasher.hxx>
  49 #include <TopAbs.hxx>
  50 #include <TopExp.hxx>
  51 #include <TopExp_Explorer.hxx>
  52 #include <TopLoc_Location.hxx>
  53 #include <TopoDS_Edge.hxx>
  54 #include <TopoDS_Face.hxx>
  55 #include <TopoDS_Iterator.hxx>
  56 #include <TopoDS_Shape.hxx>
  57 #include <TopoDS_Vertex.hxx>
  58 #include <TopoDS_Wire.hxx>
  59
  60 //
  61 static
  62   Standard_Boolean IsGrowthWire(const TopoDS_Shape& ,
  63                                 const BOPCol_IndexedMapOfShape& );
  64
  65 static
  66   Standard_Boolean IsInside(const TopoDS_Shape& ,
  67                             const TopoDS_Shape& ,
  68                             Handle(IntTools_Context)& );
  69 static
  70   void MakeInternalWires(const BOPCol_IndexedMapOfShape& ,
  71                          BOPCol_ListOfShape& );
  72 static
  73   void GetWire(const TopoDS_Shape& ,
  74         TopoDS_Shape& );
  75 //
  76
  77 //
  78 //=======================================================================
  79 //class     : BOPAlgo_ShapeBox2D
  80 //purpose   : Auxiliary class
  81 //=======================================================================
  82 class BOPAlgo_ShapeBox2D {
  83  public:
  84   BOPAlgo_ShapeBox2D() {
  85     myIsHole=Standard_False;
  86   };
  87   //
  88   ~BOPAlgo_ShapeBox2D() {
  89   };
  90   //
  91   void SetShape(const TopoDS_Shape& aS) {
  92     myShape=aS;
  93   };
  94   //
  95   const TopoDS_Shape& Shape()const {
  96     return myShape;
  97   };
  98   //
  99   void SetBox2D(const Bnd_Box2d& aBox2D) {
 100     myBox2D=aBox2D;
 101   };
 102   //
 103   const Bnd_Box2d& Box2D()const {
 104     return myBox2D;
 105   };
 106   //
 107   void SetIsHole(const Standard_Boolean bFlag) {
 108     myIsHole=bFlag;
 109   };
 110   //
 111   Standard_Boolean IsHole()const {
 112     return myIsHole;
 113   };
 114   //
 115  protected:
 116   Standard_Boolean myIsHole;
 117   TopoDS_Shape myShape;
 118   Bnd_Box2d myBox2D;
 119 };
 120 //
 121 typedef NCollection_IndexedDataMap
 122   <Standard_Integer,
 123   BOPAlgo_ShapeBox2D,
 124   TColStd_MapIntegerHasher>  BOPAlgo_IndexedDataMapOfIntegerShapeBox2D;
 125
 126 typedef NCollection_IndexedDataMap
 127   <TopoDS_Shape,
 128   TopoDS_Shape,
 129   TopTools_ShapeMapHasher> BOPCol_IndexedDataMapOfShapeShape;
 130 //
 131 //=======================================================================
 132 //function :
 133 //purpose  :
 134 //=======================================================================
 135 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace()
 136 :
 137   BOPAlgo_BuilderArea()
 138 {
 139   myOrientation=TopAbs_EXTERNAL;
 140 }
 141 //=======================================================================
 142 //function :
 143 //purpose  :
 144 //=======================================================================
 145 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace
 146   (const Handle(NCollection_BaseAllocator)& theAllocator)
 147 :
 148   BOPAlgo_BuilderArea(theAllocator)
 149 {
 150   myOrientation=TopAbs_EXTERNAL;
 151 }
 152 //=======================================================================
 153 //function : ~
 154 //purpose  :
 155 //=======================================================================
 156   BOPAlgo_BuilderFace::~BOPAlgo_BuilderFace()
 157 {
 158 }
 159 //=======================================================================
 160 //function : SetFace
 161 //purpose  :
 162 //=======================================================================
 163 void BOPAlgo_BuilderFace::SetFace(const TopoDS_Face& theFace)
 164 {
 165   myOrientation=theFace.Orientation();
 166   myFace=theFace;
 167   myFace.Orientation(TopAbs_FORWARD);
 168 }
 169 //=======================================================================
 170 //function : Orientation
 171 //purpose  :
 172 //=======================================================================
 173 TopAbs_Orientation BOPAlgo_BuilderFace::Orientation()const
 174 {
 175   return myOrientation;
 176 }
 177 //=======================================================================
 178 //function : Face
 179 //purpose  :
 180 //=======================================================================
 181 const TopoDS_Face& BOPAlgo_BuilderFace::Face()const
 182 {
 183   return myFace;
 184 }
 185 //=======================================================================
 186 //function : CheckData
 187 //purpose  :
 188 //=======================================================================
 189 void BOPAlgo_BuilderFace::CheckData()
 190 {
 191   if (myFace.IsNull()) {
 192     AddError (new BOPAlgo_AlertNullInputShapes);
 193     return;
 194   }
 195   if (myContext.IsNull()) {
 196     myContext = new IntTools_Context;
 197   }
 198 }
 199 //=======================================================================
 200 //function : Perform
 201 //purpose  :
 202 //=======================================================================
 203 void BOPAlgo_BuilderFace::Perform()
 204 {
 205   GetReport()->Clear();
 206   //
 207   CheckData();
 208   if (HasErrors()) {
 209     return;
 210   }
 211   //
 212   UserBreak();
 213   //
 214   PerformShapesToAvoid();
 215   if (HasErrors()) {
 216     return;
 217   }
 218   //
 219   UserBreak();
 220   //
 221   PerformLoops();
 222   if (HasErrors()) {
 223     return;
 224   }
 225   //
 226   UserBreak();
 227   //
 228   PerformAreas();
 229   if (HasErrors()) {
 230     return;
 231   }
 232   //
 233   UserBreak();
 234   //
 235   PerformInternalShapes();
 236   if (HasErrors()) {
 237     return;
 238   }
 239 }
 240 //=======================================================================
 241 //function :PerformShapesToAvoid
 242 //purpose  :
 243 //=======================================================================
 244 void BOPAlgo_BuilderFace::PerformShapesToAvoid()
 245 {
 246   Standard_Boolean bFound;
 247   Standard_Integer i, iCnt, aNbV, aNbE;
 248   BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
 249   BOPCol_ListIteratorOfListOfShape aIt;
 250   //
 251   myShapesToAvoid.Clear();
 252   //
 253   iCnt=0;
 254   for(;;) {
 255     ++iCnt;
 256     bFound=Standard_False;
 257     //
 258     // 1. MEF
 259     aMVE.Clear();
 260     aIt.Initialize (myShapes);
 261     for (; aIt.More(); aIt.Next()) {
 262       const TopoDS_Shape& aE=aIt.Value();
 263       if (!myShapesToAvoid.Contains(aE)) {
 264         BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 265       }
 266     }
 267     aNbV=aMVE.Extent();
 268     //
 269     // 2. myEdgesToAvoid
 270     for (i=1; i<=aNbV; ++i) {
 271       const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aMVE.FindKey(i)));
 272       //
 273       BOPCol_ListOfShape& aLE=aMVE.ChangeFromKey(aV);
 274       aNbE=aLE.Extent();
 275       if (!aNbE) {
 276         continue;
 277       }
 278       //
 279       const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aLE.First()));
 280       if (aNbE==1) {
 281         if (BRep_Tool::Degenerated(aE1)) {
 282           continue;
 283         }
 284         if (aV.Orientation()==TopAbs_INTERNAL) {
 285           continue;
 286         }
 287         bFound=Standard_True;
 288         myShapesToAvoid.Add(aE1);
 289       }
 290       else if (aNbE==2) {
 291         const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aLE.Last()));
 292         if (aE2.IsSame(aE1)) {
 293           TopoDS_Vertex aV1x, aV2x;
 294           //
 295           TopExp::Vertices(aE1, aV1x, aV2x);
 296           if (aV1x.IsSame(aV2x)) {
 297             continue;
 298           }
 299           bFound=Standard_True;
 300           myShapesToAvoid.Add(aE1);
 301           myShapesToAvoid.Add(aE2);
 302         }
 303       }
 304     }// for (i=1; i<=aNbE; ++i) {
 305     //
 306     if (!bFound) {
 307       break;
 308     }
 309     //
 310   }//while (1)
 311   //printf(" EdgesToAvoid=%d, iCnt=%d\n", EdgesToAvoid.Extent(), iCnt);
 312 }
 313 //=======================================================================
 314 //function : PerformLoops
 315 //purpose  :
 316 //=======================================================================
 317 void BOPAlgo_BuilderFace::PerformLoops()
 318 {
 319   Standard_Boolean bFlag;
 320   Standard_Integer i, aNbEA;
 321   BOPCol_ListIteratorOfListOfShape aIt;
 322   BOPCol_IndexedDataMapOfShapeListOfShape aVEMap;
 323   BOPCol_MapOfOrientedShape aMAdded;
 324   TopoDS_Iterator aItW;
 325   BRep_Builder aBB;
 326   BOPAlgo_WireEdgeSet aWES(myAllocator);
 327   BOPAlgo_WireSplitter aWSp(myAllocator);
 328   //
 329   // 1.
 330   myLoops.Clear();
 331   aWES.SetFace(myFace);
 332   //
 333   aIt.Initialize(myShapes);
 334   for (; aIt.More(); aIt.Next()) {
 335     const TopoDS_Shape& aE=aIt.Value();
 336     if (!myShapesToAvoid.Contains(aE)) {
 337       aWES.AddStartElement(aE);
 338     }
 339   }
 340   //
 341   aWSp.SetWES(aWES);
 342   aWSp.SetRunParallel(myRunParallel);
 343   aWSp.SetContext(myContext);
 344   aWSp.Perform();
 345   if (aWSp.HasErrors()) {
 346     return;
 347   }
 348   //
 349   const BOPCol_ListOfShape& aLW=aWES.Shapes();
 350   aIt.Initialize (aLW);
 351   for (; aIt.More(); aIt.Next()) {
 352     const TopoDS_Shape& aW=aIt.Value();
 353     myLoops.Append(aW);
 354   }
 355   // Post Treatment
 356   BOPCol_MapOfOrientedShape aMEP;
 357   //
 358   // a. collect all edges that are in loops
 359   aIt.Initialize (myLoops);
 360   for (; aIt.More(); aIt.Next()) {
 361     const TopoDS_Shape& aW=aIt.Value();
 362     aItW.Initialize(aW);
 363     for (; aItW.More(); aItW.Next()) {
 364       const TopoDS_Shape& aE=aItW.Value();
 365       aMEP.Add(aE);
 366     }
 367   }
 368   //
 369   // b. collect all edges that are to avoid
 370   aNbEA = myShapesToAvoid.Extent();
 371   for (i = 1; i <= aNbEA; ++i) {
 372     const TopoDS_Shape& aE = myShapesToAvoid(i);
 373     aMEP.Add(aE);
 374   }
 375   //
 376   // c. add all edges that are not processed to myShapesToAvoid
 377   aIt.Initialize (myShapes);
 378   for (; aIt.More(); aIt.Next()) {
 379     const TopoDS_Shape& aE=aIt.Value();
 380     if (!aMEP.Contains(aE)) {
 381       myShapesToAvoid.Add(aE);
 382     }
 383   }
 384   //
 385   // 2. Internal Wires
 386   myLoopsInternal.Clear();
 387   //
 388   aNbEA = myShapesToAvoid.Extent();
 389   for (i = 1; i <= aNbEA; ++i) {
 390     const TopoDS_Shape& aEE = myShapesToAvoid(i);
 391     BOPTools::MapShapesAndAncestors(aEE,
 392                                     TopAbs_VERTEX,
 393                                     TopAbs_EDGE,
 394                                     aVEMap);
 395   }
 396   //
 397   bFlag=Standard_True;
 398   for (i = 1; (i <= aNbEA) && bFlag; ++i) {
 399     const TopoDS_Shape& aEE = myShapesToAvoid(i);
 400     if (!aMAdded.Add(aEE)) {
 401       continue;
 402     }
 403     //
 404     // make new wire
 405     TopoDS_Wire aW;
 406     aBB.MakeWire(aW);
 407     aBB.Add(aW, aEE);
 408     //
 409     aItW.Initialize(aW);
 410     for (; aItW.More()&&bFlag; aItW.Next()) {
 411       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
 412       //
 413       TopoDS_Iterator aItE(aE);
 414       for (; aItE.More()&&bFlag; aItE.Next()) {
 415         const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aItE.Value()));
 416         const BOPCol_ListOfShape& aLE=aVEMap.FindFromKey(aV);
 417         aIt.Initialize(aLE);
 418         for (; aIt.More()&&bFlag; aIt.Next()) {
 419           const TopoDS_Shape& aEx=aIt.Value();
 420           if (aMAdded.Add(aEx)) {
 421             aBB.Add(aW, aEx);
 422             if(aMAdded.Extent()==aNbEA) {
 423               bFlag=!bFlag;
 424             }
 425           }
 426         }//for (; aIt.More(); aIt.Next()) {
 427       }//for (; aItE.More(); aItE.Next()) {
 428     }//for (; aItW.More(); aItW.Next()) {
 429     aW.Closed(BRep_Tool::IsClosed(aW));
 430     myLoopsInternal.Append(aW);
 431   }//for (i = 1; (i <= aNbEA) && bFlag; ++i) {
 432 }
 433 //=======================================================================
 434 //function : PerformAreas
 435 //purpose  :
 436 //=======================================================================
 437 void BOPAlgo_BuilderFace::PerformAreas()
 438 {
 439   Standard_Boolean bIsGrowth, bIsHole;
 440   Standard_Integer k, aNbS, aNbHoles, aNbDMISB, m, aNbMSH, aNbInOutMap;
 441   Standard_Real aTol;
 442   TopLoc_Location aLoc;
 443   Handle(Geom_Surface) aS;
 444   BRep_Builder aBB;
 445   TopoDS_Face aFace;
 446   BOPCol_ListIteratorOfListOfInteger aItLI;
 447   BOPCol_IndexedMapOfShape aMHE;
 448   BOPCol_ListIteratorOfListOfShape aIt1;
 449   BOPCol_IndexedDataMapOfShapeListOfShape aMSH;
 450   BOPCol_IndexedDataMapOfShapeShape aInOutMap;
 451   BOPAlgo_IndexedDataMapOfIntegerShapeBox2D aDMISB(100);
 452   //
 453   BOPCol_Box2DBndTreeSelector aSelector;
 454   BOPCol_Box2DBndTree aBBTree;
 455   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box2d> aTreeFiller(aBBTree);
 456   //
 457   aNbHoles=0;
 458   //
 459   aTol=BRep_Tool::Tolerance(myFace);
 460   aS=BRep_Tool::Surface(myFace, aLoc);
 461   //
 462   myAreas.Clear();
 463   //
 464   if (myLoops.IsEmpty()) {
 465     if (myContext->IsInfiniteFace(myFace)) {
 466       aBB.MakeFace(aFace, aS, aLoc, aTol);
 467       if (BRep_Tool::NaturalRestriction(myFace)) {
 468         aBB.NaturalRestriction(aFace, Standard_True);
 469       }
 470       myAreas.Append(aFace);
 471     }
 472     return;
 473   }
 474   //
 475   // 1. Growthes and Holes -> aDMISB: [Index/ShapeBox2D]
 476   aIt1.Initialize(myLoops);
 477   for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
 478     Bnd_Box2d aBox2D;
 479     //
 480     const TopoDS_Shape& aWire=aIt1.Value();
 481     //
 482     aBB.MakeFace(aFace, aS, aLoc, aTol);
 483     aBB.Add (aFace, aWire);
 484     BRepTools::AddUVBounds(aFace, aBox2D);
 485     //
 486     bIsGrowth=IsGrowthWire(aWire, aMHE);
 487     if (bIsGrowth) {
 488       bIsHole=Standard_False;
 489     }
 490     else{
 491       // check if a wire is a hole
 492       IntTools_FClass2d& aClsf=myContext->FClass2d(aFace);
 493       aClsf.Init(aFace, aTol);
 494       //
 495       bIsHole=aClsf.IsHole();
 496       if (bIsHole) {
 497         BOPTools::MapShapes(aWire, TopAbs_EDGE, aMHE);
 498         //
 499         bIsHole=Standard_True;
 500       }
 501       else {
 502         bIsHole=Standard_False;
 503       }
 504     }
 505     //
 506     BOPAlgo_ShapeBox2D aSB2D;
 507     //
 508     aSB2D.SetShape(aFace);
 509     aSB2D.SetBox2D(aBox2D);
 510     aSB2D.SetIsHole(bIsHole);
 511     //
 512     aDMISB.Add(k, aSB2D);
 513   }// for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
 514   //
 515   // 2. Prepare TreeFiller
 516   aNbDMISB=aDMISB.Extent();
 517   for (m=1; m<=aNbDMISB; ++m) {
 518     k=aDMISB.FindKey(m);
 519     const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
 520     //
 521     bIsHole=aSB2D.IsHole();
 522     if (bIsHole) {
 523       const Bnd_Box2d& aBox2D=aSB2D.Box2D();
 524       aTreeFiller.Add(k, aBox2D);
 525       ++aNbHoles;
 526     }
 527   }
 528   //
 529   // 3. Shake TreeFiller
 530   aTreeFiller.Fill();
 531   //
 532   // 4. Find outer growth shell that is most close
 533   //    to each hole shell
 534   for (m=1; m<=aNbDMISB; ++m) {
 535     const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
 536     bIsHole=aSB2D.IsHole();
 537     if (bIsHole) {
 538       continue;
 539     }
 540     //
 541     const Bnd_Box2d& aBox2DF=aSB2D.Box2D();
 542     const TopoDS_Shape aF=aSB2D.Shape();
 543     //
 544     aSelector.Clear();
 545     aSelector.SetBox(aBox2DF);
 546     //
 547     aNbS = aBBTree.Select(aSelector);
 548     if (!aNbS) {
 549       continue;
 550     }
 551     //
 552     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
 553     //
 554     aItLI.Initialize(aLI);
 555     for (; aItLI.More(); aItLI.Next()) {
 556       k=aItLI.Value();
 557       const BOPAlgo_ShapeBox2D& aSB2Dk=aDMISB.FindFromKey(k);
 558       const TopoDS_Shape& aHole=aSB2Dk.Shape();
 559       //
 560       if (!IsInside(aHole, aF, myContext)){
 561         continue;
 562       }
 563       //
 564       if (aInOutMap.Contains(aHole)){
 565         TopoDS_Shape& aF2=aInOutMap.ChangeFromKey(aHole);
 566         if (IsInside(aF, aF2, myContext)) {
 567           aF2=aF;
 568         }
 569       }
 570       else{
 571         aInOutMap.Add(aHole, aF);
 572       }
 573     }
 574   }// for (m=1; m<=aNbDMISB; ++m)
 575   //
 576   // 5.1 Map [Face/Holes] -> aMSH
 577   aNbInOutMap=aInOutMap.Extent();
 578   for (m=1; m<=aNbInOutMap; ++m) {
 579     const TopoDS_Shape& aHole=aInOutMap.FindKey(m);
 580     const TopoDS_Shape& aF=aInOutMap.FindFromIndex(m);
 581     //
 582     if (aMSH.Contains(aF)) {
 583       BOPCol_ListOfShape& aLH=aMSH.ChangeFromKey(aF);
 584       aLH.Append(aHole);
 585     }
 586     else {
 587       BOPCol_ListOfShape aLH;
 588       aLH.Append(aHole);
 589       aMSH.Add(aF, aLH);
 590     }
 591   }
 592   //
 593   // 5.2. Add unused holes to the original face
 594   if (aNbHoles != aNbInOutMap) {
 595     Bnd_Box aBoxF;
 596     BRepBndLib::Add(myFace, aBoxF);
 597     if (aBoxF.IsOpenXmin() || aBoxF.IsOpenXmax() ||
 598         aBoxF.IsOpenYmin() || aBoxF.IsOpenYmax() ||
 599         aBoxF.IsOpenZmin() || aBoxF.IsOpenZmax()) {
 600       //
 601       BOPCol_ListOfShape anUnUsedHoles;
 602       for (m = 1; m <= aNbDMISB; ++m) {
 603         const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
 604         if (aSB2D.IsHole()) {
 605           const TopoDS_Shape& aHole = aSB2D.Shape();
 606           if (!aInOutMap.Contains(aHole)) {
 607             anUnUsedHoles.Append(aHole);
 608           }
 609         }
 610       }
 611       //
 612       if (anUnUsedHoles.Extent()) {
 613         aBB.MakeFace(aFace, aS, aLoc, aTol);
 614         aMSH.Add(aFace, anUnUsedHoles);
 615         //
 616         BOPAlgo_ShapeBox2D aSB2D;
 617         //
 618         aSB2D.SetShape(aFace);
 619         aSB2D.SetIsHole(Standard_False);
 620         //
 621         aDMISB.Add(aNbDMISB, aSB2D);
 622         ++aNbDMISB;
 623       }
 624     }
 625   }
 626   //
 627   // 6. Add aHoles to Faces
 628   aNbMSH=aMSH.Extent();
 629   for (m=1; m<=aNbMSH; ++m) {
 630     TopoDS_Face aF=(*(TopoDS_Face *)(&aMSH.FindKey(m)));
 631     const BOPCol_ListOfShape& aLH=aMSH.FindFromIndex(m);
 632     //
 633     aIt1.Initialize(aLH);
 634     for (; aIt1.More(); aIt1.Next()) {
 635       TopoDS_Shape aWHole;
 636       //
 637       const TopoDS_Shape& aFHole=aIt1.Value();
 638       GetWire(aFHole, aWHole);
 639       aBB.Add (aF, aWHole);
 640     }
 641     //
 642     // update classifier
 643     aTol=BRep_Tool::Tolerance(aF);
 644     IntTools_FClass2d& aClsf=myContext->FClass2d(aF);
 645     aClsf.Init(aF, aTol);
 646   }
 647   //
 648   // 7. Fill myAreas
 649   //    NB:These aNewFaces are draft faces that
 650   //    do not contain any internal shapes
 651   for (m=1; m<=aNbDMISB; ++m) {
 652     const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
 653     bIsHole=aSB2D.IsHole();
 654     if (!bIsHole) {
 655       const TopoDS_Shape aF=aSB2D.Shape();
 656       myAreas.Append(aF);
 657     }
 658   }
 659 }
 660 //=======================================================================
 661 //function : GetWire
 662 //purpose  :
 663 //=======================================================================
 664 void GetWire(const TopoDS_Shape& aF, TopoDS_Shape& aW)
 665 {
 666   TopoDS_Shape aWx;
 667   TopoDS_Iterator aIt;
 668   //
 669   aIt.Initialize(aF);
 670   for (; aIt.More(); aIt.Next()) {
 671     aW=aIt.Value();
 672   }
 673 }
 674 //=======================================================================
 675 //function : PerformInternalShapes
 676 //purpose  :
 677 //=======================================================================
 678 void BOPAlgo_BuilderFace::PerformInternalShapes()
 679 {
 680   if (myAvoidInternalShapes) {
 681     return;
 682   }
 683   //
 684   Standard_Integer aNbWI=myLoopsInternal.Extent();
 685   if (!aNbWI) {// nothing to do
 686     return;
 687   }
 688   //
 689   //Standard_Real aTol;
 690   Standard_Integer i;
 691   BRep_Builder aBB;
 692   BOPCol_ListIteratorOfListOfShape aIt1, aIt2;
 693   TopoDS_Iterator aIt;
 694   BOPCol_IndexedMapOfShape aME1, aME2, aMEP;
 695   BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
 696   BOPCol_ListOfShape aLSI;
 697   //
 698   // 1. All internal edges
 699   aIt1.Initialize(myLoopsInternal);
 700   for (; aIt1.More(); aIt1.Next()) {
 701     const TopoDS_Shape& aWire=aIt1.Value();
 702     aIt.Initialize(aWire);
 703     for (; aIt.More(); aIt.Next()) {
 704       const TopoDS_Shape& aE=aIt.Value();
 705       aME1.Add(aE);
 706     }
 707   }
 708   //
 709   // 2 Process faces
 710   aIt2.Initialize(myAreas);
 711   for ( ; aIt2.More(); aIt2.Next()) {
 712     TopoDS_Face& aF=(*(TopoDS_Face *)(&aIt2.Value()));
 713     //
 714     aMVE.Clear();
 715     BOPTools::MapShapesAndAncestors(aF, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 716     //
 717     // 2.1 Separate faces to process aMEP
 718     aME2.Clear();
 719     aMEP.Clear();
 720     aNbWI = aME1.Extent();
 721     for (i = 1; i <= aNbWI; ++i) {
 722       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aME1(i)));
 723       if (IsInside(aE, aF, myContext)) {
 724         aMEP.Add(aE);
 725       }
 726       else {
 727         aME2.Add(aE);
 728       }
 729     }
 730     //
 731     // 2.2 Make Internal Wires
 732     aLSI.Clear();
 733     MakeInternalWires(aMEP, aLSI);
 734     //
 735     // 2.3 Add them to aF
 736     aIt1.Initialize(aLSI);
 737     for (; aIt1.More(); aIt1.Next()) {
 738       const TopoDS_Shape& aSI=aIt1.Value();
 739       aBB.Add (aF, aSI);
 740     }
 741     //
 742     // 2.4 Remove faces aMFP from aMF
 743     aME1 = aME2;
 744     //
 745     aNbWI = aME1.Extent();
 746     if (!aNbWI) {
 747       break;
 748     }
 749   } //for ( ; aIt2.More(); aIt2.Next()) {
 750 }
 751 //=======================================================================
 752 //function : MakeInternalWires
 753 //purpose  :
 754 //=======================================================================
 755 void MakeInternalWires(const BOPCol_IndexedMapOfShape& theME,
 756                        BOPCol_ListOfShape& theWires)
 757 {
 758   Standard_Integer i, aNbE;
 759   BOPCol_MapOfShape aAddedMap;
 760   BOPCol_ListIteratorOfListOfShape aItE;
 761   BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
 762   BRep_Builder aBB;
 763   //
 764   aNbE = theME.Extent();
 765   for (i = 1; i <= aNbE; ++i) {
 766     const TopoDS_Shape& aE = theME(i);
 767     BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 768   }
 769   //
 770   for (i = 1; i <= aNbE; ++i) {
 771     TopoDS_Shape aEE = theME(i);
 772     if (!aAddedMap.Add(aEE)) {
 773       continue;
 774     }
 775     //
 776     // make a new shell
 777     TopoDS_Wire aW;
 778     aBB.MakeWire(aW);
 779     aEE.Orientation(TopAbs_INTERNAL);
 780     aBB.Add(aW, aEE);
 781     //
 782     TopoDS_Iterator aItAdded (aW);
 783     for (; aItAdded.More(); aItAdded.Next()) {
 784       const TopoDS_Shape& aE =aItAdded.Value();
 785       //
 786       TopExp_Explorer aExp(aE, TopAbs_VERTEX);
 787       for (; aExp.More(); aExp.Next()) {
 788         const TopoDS_Shape& aV =aExp.Current();
 789         const BOPCol_ListOfShape& aLE=aMVE.FindFromKey(aV);
 790         aItE.Initialize(aLE);
 791         for (; aItE.More(); aItE.Next()) {
 792           TopoDS_Shape aEL=aItE.Value();
 793           if (aAddedMap.Add(aEL)){
 794             aEL.Orientation(TopAbs_INTERNAL);
 795             aBB.Add(aW, aEL);
 796           }
 797         }
 798       }
 799     }
 800     aW.Closed(BRep_Tool::IsClosed(aW));
 801     theWires.Append(aW);
 802   }
 803 }
 804 //=======================================================================
 805 //function : IsInside
 806 //purpose  :
 807 //=======================================================================
 808 Standard_Boolean IsInside(const TopoDS_Shape& theHole,
 809                           const TopoDS_Shape& theF2,
 810                           Handle(IntTools_Context)& theContext)
 811 {
 812   Standard_Boolean bRet;
 813   Standard_Real aT, aU, aV;
 814
 815   TopAbs_State aState;
 816   TopExp_Explorer aExp;
 817   BOPCol_IndexedMapOfShape aME2;
 818   gp_Pnt2d aP2D;
 819   //
 820   bRet=Standard_False;
 821   aState=TopAbs_UNKNOWN;
 822   const TopoDS_Face& aF2=(*(TopoDS_Face *)(&theF2));
 823   //
 824   BOPTools::MapShapes(aF2, TopAbs_EDGE, aME2);//AA
 825   //
 826   aExp.Init(theHole, TopAbs_EDGE);
 827   if (aExp.More()) {
 828     const TopoDS_Edge& aE =(*(TopoDS_Edge *)(&aExp.Current()));
 829     if (aME2.Contains(aE)) {
 830       return bRet;
 831     }
 832     if (!BRep_Tool::Degenerated(aE)) {
 833       //
 834       aT=BOPTools_AlgoTools2D::IntermediatePoint(aE);
 835       BOPTools_AlgoTools2D::PointOnSurface(aE, aF2, aT, aU, aV, theContext);
 836       aP2D.SetCoord(aU, aV);
 837       //
 838       IntTools_FClass2d& aClsf=theContext->FClass2d(aF2);
 839       aState=aClsf.Perform(aP2D);
 840       bRet=(aState==TopAbs_IN);
 841     }
 842   }
 843   //
 844   return bRet;
 845 }
 846
 847 //=======================================================================
 848 //function : IsGrowthWire
 849 //purpose  :
 850 //=======================================================================
 851 Standard_Boolean IsGrowthWire(const TopoDS_Shape& theWire,
 852                               const BOPCol_IndexedMapOfShape& theMHE)
 853 {
 854   Standard_Boolean bRet;
 855   TopoDS_Iterator aIt;
 856   //
 857   bRet=Standard_False;
 858   if (theMHE.Extent()) {
 859     aIt.Initialize(theWire);
 860     for(; aIt.More(); aIt.Next()) {
 861       const TopoDS_Shape& aE=aIt.Value();
 862       if (theMHE.Contains(aE)) {
 863         return !bRet;
 864       }
 865     }
 866   }
 867   return bRet;
 868 }