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 <Bnd_Box2d.hxx>
  21 #include <BOPAlgo_BuilderFace.hxx>
  22 #include <BOPAlgo_WireEdgeSet.hxx>
  23 #include <BOPAlgo_WireSplitter.hxx>
  24 #include <BOPAlgo_Alerts.hxx>
  25 #include <BOPTools_AlgoTools.hxx>
  26 #include <BOPTools_AlgoTools2D.hxx>
  27 #include <BOPTools_BoxTree.hxx>
  28 #include <Bnd_Tools.hxx>
  29 #include <BRep_Builder.hxx>
  30 #include <BRep_Tool.hxx>
  31 #include <BRepBndLib.hxx>
  32 #include <BRepTools.hxx>
  33 #include <Geom_Surface.hxx>
  34 #include <gp_Dir.hxx>
  35 #include <gp_Pln.hxx>
  36 #include <gp_Pnt.hxx>
  37 #include <gp_Pnt2d.hxx>
  38 #include <gp_Vec.hxx>
  39 #include <IntTools_Context.hxx>
  40 #include <IntTools_FClass2d.hxx>
  41 #include <NCollection_DataMap.hxx>
  42 #include <TColStd_MapOfInteger.hxx>
  43 #include <TopAbs.hxx>
  44 #include <TopExp.hxx>
  45 #include <TopExp_Explorer.hxx>
  46 #include <TopLoc_Location.hxx>
  47 #include <TopoDS.hxx>
  48 #include <TopoDS_Edge.hxx>
  49 #include <TopoDS_Face.hxx>
  50 #include <TopoDS_Iterator.hxx>
  51 #include <TopoDS_Shape.hxx>
  52 #include <TopoDS_Vertex.hxx>
  53 #include <TopoDS_Wire.hxx>
  54 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  55 #include <TopTools_IndexedDataMapOfShapeShape.hxx>
  56 #include <TopTools_ListOfShape.hxx>
  57 #include <TopTools_MapOfShape.hxx>
  58 #include <TopTools_MapOfOrientedShape.hxx>
  59 //
  60 static
  61   Standard_Boolean IsGrowthWire(const TopoDS_Shape& ,
  62                                 const TopTools_IndexedMapOfShape& );
  63
  64 static
  65   Standard_Boolean IsInside(const TopoDS_Shape& ,
  66                             const TopoDS_Shape& ,
  67                             Handle(IntTools_Context)& );
  68 static
  69   void MakeInternalWires(const TopTools_IndexedMapOfShape& ,
  70                          TopTools_ListOfShape& );
  71
  72 //=======================================================================
  73 //function :
  74 //purpose  :
  75 //=======================================================================
  76 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace()
  77 :
  78   BOPAlgo_BuilderArea()
  79 {
  80   myOrientation=TopAbs_EXTERNAL;
  81 }
  82 //=======================================================================
  83 //function :
  84 //purpose  :
  85 //=======================================================================
  86 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace
  87   (const Handle(NCollection_BaseAllocator)& theAllocator)
  88 :
  89   BOPAlgo_BuilderArea(theAllocator)
  90 {
  91   myOrientation=TopAbs_EXTERNAL;
  92 }
  93 //=======================================================================
  94 //function : ~
  95 //purpose  :
  96 //=======================================================================
  97   BOPAlgo_BuilderFace::~BOPAlgo_BuilderFace()
  98 {
  99 }
 100 //=======================================================================
 101 //function : SetFace
 102 //purpose  :
 103 //=======================================================================
 104 void BOPAlgo_BuilderFace::SetFace(const TopoDS_Face& theFace)
 105 {
 106   myOrientation=theFace.Orientation();
 107   myFace=theFace;
 108   myFace.Orientation(TopAbs_FORWARD);
 109 }
 110 //=======================================================================
 111 //function : Orientation
 112 //purpose  :
 113 //=======================================================================
 114 TopAbs_Orientation BOPAlgo_BuilderFace::Orientation()const
 115 {
 116   return myOrientation;
 117 }
 118 //=======================================================================
 119 //function : Face
 120 //purpose  :
 121 //=======================================================================
 122 const TopoDS_Face& BOPAlgo_BuilderFace::Face()const
 123 {
 124   return myFace;
 125 }
 126 //=======================================================================
 127 //function : CheckData
 128 //purpose  :
 129 //=======================================================================
 130 void BOPAlgo_BuilderFace::CheckData()
 131 {
 132   if (myFace.IsNull()) {
 133     AddError (new BOPAlgo_AlertNullInputShapes);
 134     return;
 135   }
 136   if (myContext.IsNull()) {
 137     myContext = new IntTools_Context;
 138   }
 139 }
 140 //=======================================================================
 141 //function : Perform
 142 //purpose  :
 143 //=======================================================================
 144 void BOPAlgo_BuilderFace::Perform()
 145 {
 146   GetReport()->Clear();
 147   //
 148   CheckData();
 149   if (HasErrors()) {
 150     return;
 151   }
 152   //
 153   UserBreak();
 154   //
 155   PerformShapesToAvoid();
 156   if (HasErrors()) {
 157     return;
 158   }
 159   //
 160   UserBreak();
 161   //
 162   PerformLoops();
 163   if (HasErrors()) {
 164     return;
 165   }
 166   //
 167   UserBreak();
 168   //
 169   PerformAreas();
 170   if (HasErrors()) {
 171     return;
 172   }
 173   //
 174   UserBreak();
 175   //
 176   PerformInternalShapes();
 177   if (HasErrors()) {
 178     return;
 179   }
 180 }
 181 //=======================================================================
 182 //function :PerformShapesToAvoid
 183 //purpose  :
 184 //=======================================================================
 185 void BOPAlgo_BuilderFace::PerformShapesToAvoid()
 186 {
 187   Standard_Boolean bFound;
 188   Standard_Integer i, iCnt, aNbV, aNbE;
 189   TopTools_IndexedDataMapOfShapeListOfShape aMVE;
 190   TopTools_ListIteratorOfListOfShape aIt;
 191   //
 192   myShapesToAvoid.Clear();
 193   //
 194   iCnt=0;
 195   for(;;) {
 196     ++iCnt;
 197     bFound=Standard_False;
 198     //
 199     // 1. MEF
 200     aMVE.Clear();
 201     aIt.Initialize (myShapes);
 202     for (; aIt.More(); aIt.Next()) {
 203       const TopoDS_Shape& aE=aIt.Value();
 204       if (!myShapesToAvoid.Contains(aE)) {
 205         TopExp::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 206       }
 207     }
 208     aNbV=aMVE.Extent();
 209     //
 210     // 2. myEdgesToAvoid
 211     for (i=1; i<=aNbV; ++i) {
 212       const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aMVE.FindKey(i)));
 213       //
 214       TopTools_ListOfShape& aLE=aMVE.ChangeFromKey(aV);
 215       aNbE=aLE.Extent();
 216       if (!aNbE) {
 217         continue;
 218       }
 219       //
 220       const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aLE.First()));
 221       if (aNbE==1) {
 222         if (BRep_Tool::Degenerated(aE1)) {
 223           continue;
 224         }
 225         if (aV.Orientation()==TopAbs_INTERNAL) {
 226           continue;
 227         }
 228         bFound=Standard_True;
 229         myShapesToAvoid.Add(aE1);
 230       }
 231       else if (aNbE==2) {
 232         const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aLE.Last()));
 233         if (aE2.IsSame(aE1)) {
 234           TopoDS_Vertex aV1x, aV2x;
 235           //
 236           TopExp::Vertices(aE1, aV1x, aV2x);
 237           if (aV1x.IsSame(aV2x)) {
 238             continue;
 239           }
 240           bFound=Standard_True;
 241           myShapesToAvoid.Add(aE1);
 242           myShapesToAvoid.Add(aE2);
 243         }
 244       }
 245     }// for (i=1; i<=aNbE; ++i) {
 246     //
 247     if (!bFound) {
 248       break;
 249     }
 250     //
 251   }//while (1)
 252   //printf(" EdgesToAvoid=%d, iCnt=%d\n", EdgesToAvoid.Extent(), iCnt);
 253 }
 254 //=======================================================================
 255 //function : PerformLoops
 256 //purpose  :
 257 //=======================================================================
 258 void BOPAlgo_BuilderFace::PerformLoops()
 259 {
 260   Standard_Boolean bFlag;
 261   Standard_Integer i, aNbEA;
 262   TopTools_ListIteratorOfListOfShape aIt;
 263   TopTools_IndexedDataMapOfShapeListOfShape aVEMap;
 264   TopTools_MapOfOrientedShape aMAdded;
 265   TopoDS_Iterator aItW;
 266   BRep_Builder aBB;
 267   BOPAlgo_WireEdgeSet aWES(myAllocator);
 268   BOPAlgo_WireSplitter aWSp(myAllocator);
 269   //
 270   // 1.
 271   myLoops.Clear();
 272   aWES.SetFace(myFace);
 273   //
 274   aIt.Initialize(myShapes);
 275   for (; aIt.More(); aIt.Next()) {
 276     const TopoDS_Shape& aE=aIt.Value();
 277     if (!myShapesToAvoid.Contains(aE)) {
 278       aWES.AddStartElement(aE);
 279     }
 280   }
 281   //
 282   aWSp.SetWES(aWES);
 283   aWSp.SetRunParallel(myRunParallel);
 284   aWSp.SetContext(myContext);
 285   aWSp.Perform();
 286   if (aWSp.HasErrors()) {
 287     return;
 288   }
 289   //
 290   const TopTools_ListOfShape& aLW=aWES.Shapes();
 291   aIt.Initialize (aLW);
 292   for (; aIt.More(); aIt.Next()) {
 293     const TopoDS_Shape& aW=aIt.Value();
 294     myLoops.Append(aW);
 295   }
 296   // Post Treatment
 297   TopTools_MapOfOrientedShape aMEP;
 298   //
 299   // a. collect all edges that are in loops
 300   aIt.Initialize (myLoops);
 301   for (; aIt.More(); aIt.Next()) {
 302     const TopoDS_Shape& aW=aIt.Value();
 303     aItW.Initialize(aW);
 304     for (; aItW.More(); aItW.Next()) {
 305       const TopoDS_Shape& aE=aItW.Value();
 306       aMEP.Add(aE);
 307     }
 308   }
 309   //
 310   // b. collect all edges that are to avoid
 311   aNbEA = myShapesToAvoid.Extent();
 312   for (i = 1; i <= aNbEA; ++i) {
 313     const TopoDS_Shape& aE = myShapesToAvoid(i);
 314     aMEP.Add(aE);
 315   }
 316   //
 317   // c. add all edges that are not processed to myShapesToAvoid
 318   aIt.Initialize (myShapes);
 319   for (; aIt.More(); aIt.Next()) {
 320     const TopoDS_Shape& aE=aIt.Value();
 321     if (!aMEP.Contains(aE)) {
 322       myShapesToAvoid.Add(aE);
 323     }
 324   }
 325   //
 326   // 2. Internal Wires
 327   myLoopsInternal.Clear();
 328   //
 329   aNbEA = myShapesToAvoid.Extent();
 330   for (i = 1; i <= aNbEA; ++i) {
 331     const TopoDS_Shape& aEE = myShapesToAvoid(i);
 332     TopExp::MapShapesAndAncestors(aEE,
 333                                     TopAbs_VERTEX,
 334                                     TopAbs_EDGE,
 335                                     aVEMap);
 336   }
 337   //
 338   bFlag=Standard_True;
 339   for (i = 1; (i <= aNbEA) && bFlag; ++i) {
 340     const TopoDS_Shape& aEE = myShapesToAvoid(i);
 341     if (!aMAdded.Add(aEE)) {
 342       continue;
 343     }
 344     //
 345     // make new wire
 346     TopoDS_Wire aW;
 347     aBB.MakeWire(aW);
 348     aBB.Add(aW, aEE);
 349     //
 350     aItW.Initialize(aW);
 351     for (; aItW.More()&&bFlag; aItW.Next()) {
 352       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
 353       //
 354       TopoDS_Iterator aItE(aE);
 355       for (; aItE.More()&&bFlag; aItE.Next()) {
 356         const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aItE.Value()));
 357         const TopTools_ListOfShape& aLE=aVEMap.FindFromKey(aV);
 358         aIt.Initialize(aLE);
 359         for (; aIt.More()&&bFlag; aIt.Next()) {
 360           const TopoDS_Shape& aEx=aIt.Value();
 361           if (aMAdded.Add(aEx)) {
 362             aBB.Add(aW, aEx);
 363             if(aMAdded.Extent()==aNbEA) {
 364               bFlag=!bFlag;
 365             }
 366           }
 367         }//for (; aIt.More(); aIt.Next()) {
 368       }//for (; aItE.More(); aItE.Next()) {
 369     }//for (; aItW.More(); aItW.Next()) {
 370     aW.Closed(BRep_Tool::IsClosed(aW));
 371     myLoopsInternal.Append(aW);
 372   }//for (i = 1; (i <= aNbEA) && bFlag; ++i) {
 373 }
 374 //=======================================================================
 375 //function : PerformAreas
 376 //purpose  :
 377 //=======================================================================
 378 void BOPAlgo_BuilderFace::PerformAreas()
 379 {
 380   myAreas.Clear();
 381   BRep_Builder aBB;
 382   // Location of the myFace
 383   TopLoc_Location aLoc;
 384   // Get surface from myFace
 385   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(myFace, aLoc);
 386   // Get tolerance of myFace
 387   Standard_Real aTol = BRep_Tool::Tolerance(myFace);
 388
 389   // Check if there are no loops at all
 390   if (myLoops.IsEmpty())
 391   {
 392     if (myContext->IsInfiniteFace(myFace))
 393     {
 394       TopoDS_Face aFace;
 395       aBB.MakeFace(aFace, aS, aLoc, aTol);
 396       if (BRep_Tool::NaturalRestriction(myFace))
 397         aBB.NaturalRestriction(aFace, Standard_True);
 398       myAreas.Append(aFace);
 399     }
 400     return;
 401   }
 402
 403   // The new faces
 404   TopTools_ListOfShape aNewFaces;
 405   // The hole faces which has to be classified relatively new faces
 406   TopTools_IndexedMapOfShape aHoleFaces;
 407   // Map of the edges of the hole faces for quick check of the growths.
 408   // If the analyzed wire contains any of the edges from the hole faces
 409   // it is considered as growth.
 410   TopTools_IndexedMapOfShape aMHE;
 411
 412   // Analyze the new wires - classify them to be the holes and growths
 413   TopTools_ListIteratorOfListOfShape aItLL(myLoops);
 414   for (; aItLL.More(); aItLL.Next())
 415   {
 416     const TopoDS_Shape& aWire = aItLL.Value();
 417
 418     TopoDS_Face aFace;
 419     aBB.MakeFace(aFace, aS, aLoc, aTol);
 420     aBB.Add(aFace, aWire);
 421
 422     Standard_Boolean bIsGrowth = IsGrowthWire(aWire, aMHE);
 423     if (!bIsGrowth)
 424     {
 425       // Fast check did not give the result, run classification
 426       IntTools_FClass2d& aClsf = myContext->FClass2d(aFace);
 427       bIsGrowth = !aClsf.IsHole();
 428     }
 429
 430     // Save the face
 431     if (bIsGrowth)
 432     {
 433       aNewFaces.Append(aFace);
 434     }
 435     else
 436     {
 437       aHoleFaces.Add(aFace);
 438       TopExp::MapShapes(aWire, TopAbs_EDGE, aMHE);
 439     }
 440   }
 441
 442   if (aHoleFaces.IsEmpty())
 443   {
 444     // No holes, stop the analysis
 445     myAreas.Append(aNewFaces);
 446     return;
 447   }
 448
 449   // Classify holes relatively faces
 450
 451   // Prepare tree with the boxes of the hole faces
 452   BOPTools_Box2dTree aBoxTree;
 453   Standard_Integer i, aNbH = aHoleFaces.Extent();
 454   aBoxTree.SetSize (aNbH);
 455   for (i = 1; i <= aNbH; ++i)
 456   {
 457     const TopoDS_Face& aHFace = TopoDS::Face(aHoleFaces(i));
 458     //
 459     Bnd_Box2d aBox;
 460     BRepTools::AddUVBounds(aHFace, aBox);
 461     aBoxTree.Add(i, Bnd_Tools::Bnd2BVH (aBox));
 462   }
 463
 464   // Build BVH
 465   aBoxTree.Build();
 466
 467   // Find outer growth face that is most close to each hole face
 468   TopTools_IndexedDataMapOfShapeShape aHoleFaceMap;
 469
 470   // Selector
 471   BOPTools_Box2dTreeSelector aSelector;
 472   aSelector.SetBVHSet (&aBoxTree);
 473
 474   TopTools_ListIteratorOfListOfShape aItLS(aNewFaces);
 475   for (; aItLS.More(); aItLS.Next())
 476   {
 477     const TopoDS_Face& aFace = TopoDS::Face(aItLS.Value());
 478
 479     // Build box
 480     Bnd_Box2d aBox;
 481     BRepTools::AddUVBounds(aFace, aBox);
 482
 483     aSelector.Clear();
 484     aSelector.SetBox(Bnd_Tools::Bnd2BVH (aBox));
 485     aSelector.Select();
 486
 487     const TColStd_ListOfInteger& aLI = aSelector.Indices();
 488     TColStd_ListIteratorOfListOfInteger aItLI(aLI);
 489     for (; aItLI.More(); aItLI.Next())
 490     {
 491       Standard_Integer k = aItLI.Value();
 492       const TopoDS_Shape& aHole = aHoleFaces(k);
 493       // Check if it is inside
 494       if (!IsInside(aHole, aFace, myContext))
 495         continue;
 496
 497       // Save the relation
 498       TopoDS_Shape* pFaceWas = aHoleFaceMap.ChangeSeek(aHole);
 499       if (pFaceWas)
 500       {
 501         if (IsInside(aFace, *pFaceWas, myContext))
 502         {
 503           *pFaceWas = aFace;
 504         }
 505       }
 506       else
 507       {
 508         aHoleFaceMap.Add(aHole, aFace);
 509       }
 510     }
 511   }
 512
 513   // Make the back map from faces to holes
 514   TopTools_IndexedDataMapOfShapeListOfShape aFaceHolesMap;
 515
 516   aNbH = aHoleFaceMap.Extent();
 517   for (i = 1; i <= aNbH; ++i)
 518   {
 519     const TopoDS_Shape& aHole = aHoleFaceMap.FindKey(i);
 520     const TopoDS_Shape& aFace = aHoleFaceMap(i);
 521     //
 522     TopTools_ListOfShape* pLHoles = aFaceHolesMap.ChangeSeek(aFace);
 523     if (!pLHoles)
 524       pLHoles = &aFaceHolesMap(aFaceHolesMap.Add(aFace, TopTools_ListOfShape()));
 525     pLHoles->Append(aHole);
 526   }
 527
 528   // Add unused holes to the original face
 529   if (aHoleFaces.Extent() != aHoleFaceMap.Extent())
 530   {
 531     Bnd_Box aBoxF;
 532     BRepBndLib::Add(myFace, aBoxF);
 533     if (aBoxF.IsOpenXmin() || aBoxF.IsOpenXmax() ||
 534         aBoxF.IsOpenYmin() || aBoxF.IsOpenYmax() ||
 535         aBoxF.IsOpenZmin() || aBoxF.IsOpenZmax())
 536     {
 537       TopoDS_Face aFace;
 538       aBB.MakeFace(aFace, aS, aLoc, aTol);
 539       TopTools_ListOfShape& anUnUsedHoles = aFaceHolesMap(aFaceHolesMap.Add(aFace, TopTools_ListOfShape()));
 540       aNbH = aHoleFaces.Extent();
 541       for (i = 1; i <= aNbH; ++i)
 542       {
 543         const TopoDS_Shape& aHole = aHoleFaces(i);
 544         if (!aHoleFaceMap.Contains(aHole))
 545           anUnUsedHoles.Append(aHole);
 546       }
 547       // Save it
 548       aNewFaces.Append(aFace);
 549     }
 550   }
 551
 552   // Add Holes to Faces and add them to myAreas
 553   aItLS.Initialize(aNewFaces);
 554   for ( ; aItLS.More(); aItLS.Next())
 555   {
 556     TopoDS_Face& aFace = *(TopoDS_Face*)&aItLS.Value();
 557     const TopTools_ListOfShape* pLHoles = aFaceHolesMap.Seek(aFace);
 558     if (pLHoles)
 559     {
 560       // update faces with the holes
 561       TopTools_ListIteratorOfListOfShape aItLH(*pLHoles);
 562       for (; aItLH.More(); aItLH.Next())
 563       {
 564         const TopoDS_Shape& aFHole = aItLH.Value();
 565         // The hole face contains only one wire
 566         TopoDS_Iterator aItW(aFHole);
 567         aBB.Add(aFace, aItW.Value());
 568       }
 569
 570       // update classifier
 571       myContext->FClass2d(aFace).Init(aFace, aTol);
 572     }
 573
 574     // The face is just a draft that does not contain any internal shapes
 575     myAreas.Append(aFace);
 576   }
 577 }
 578 //=======================================================================
 579 //function : PerformInternalShapes
 580 //purpose  :
 581 //=======================================================================
 582 void BOPAlgo_BuilderFace::PerformInternalShapes()
 583 {
 584   if (myAvoidInternalShapes)
 585     // User-defined option to avoid internal edges
 586     // in the result is in force.
 587     return;
 588
 589   if (myLoopsInternal.IsEmpty())
 590     // No edges left for classification
 591     return;
 592
 593   // Prepare tree with the boxes of the edges to classify
 594   BOPTools_Box2dTree aBoxTree;
 595
 596   // Map of edges to classify
 597   TopTools_IndexedMapOfShape anEdgesMap;
 598
 599   // Fill the tree and the map
 600   TopTools_ListIteratorOfListOfShape itLE(myLoopsInternal);
 601   for (; itLE.More(); itLE.Next())
 602   {
 603     TopoDS_Iterator itE(itLE.Value());
 604     for (; itE.More(); itE.Next())
 605     {
 606       const TopoDS_Edge& aE = TopoDS::Edge(itE.Value());
 607       if (!anEdgesMap.Contains(aE))
 608       {
 609         Bnd_Box2d aBoxE;
 610         BRepTools::AddUVBounds(myFace, aE, aBoxE);
 611         // Make sure the index of edge in the map and
 612         // of the box in the tree is the same
 613         aBoxTree.Add(anEdgesMap.Add(aE), Bnd_Tools::Bnd2BVH (aBoxE));
 614       }
 615     }
 616   }
 617
 618   // Build BVH
 619   aBoxTree.Build();
 620
 621   // Fence map
 622   TColStd_MapOfInteger aMEDone;
 623
 624   // Classify edges relatively faces
 625   TopTools_ListIteratorOfListOfShape itLF(myAreas);
 626   for (; itLF.More(); itLF.Next())
 627   {
 628     TopoDS_Face& aF = *(TopoDS_Face*)&itLF.Value();
 629
 630     // Build box
 631     Bnd_Box2d aBoxF;
 632     BRepTools::AddUVBounds(aF, aBoxF);
 633
 634     // Select edges for the classification
 635     BOPTools_Box2dTreeSelector aSelector;
 636     aSelector.SetBVHSet (&aBoxTree);
 637     aSelector.SetBox(Bnd_Tools::Bnd2BVH (aBoxF));
 638     if (!aSelector.Select())
 639       continue;
 640
 641     // Collect edges inside the face
 642     TopTools_IndexedMapOfShape anEdgesInside;
 643
 644     const TColStd_ListOfInteger& aLI = aSelector.Indices();
 645     TColStd_ListIteratorOfListOfInteger itLI(aLI);
 646     for (; itLI.More(); itLI.Next())
 647     {
 648       const Standard_Integer nE = itLI.Value();
 649       if (aMEDone.Contains(nE))
 650         continue;
 651
 652       const TopoDS_Edge& aE = TopoDS::Edge(anEdgesMap(nE));
 653       if (IsInside(aE, aF, myContext))
 654       {
 655         anEdgesInside.Add(aE);
 656         aMEDone.Add(nE);
 657       }
 658     }
 659
 660     if (anEdgesInside.IsEmpty())
 661       continue;
 662
 663     // Make internal wires
 664     TopTools_ListOfShape aLSI;
 665     MakeInternalWires(anEdgesInside, aLSI);
 666
 667     // Add wires to a face
 668     TopTools_ListIteratorOfListOfShape itLSI(aLSI);
 669     for (; itLSI.More(); itLSI.Next())
 670     {
 671       const TopoDS_Shape& aWI = itLSI.Value();
 672       BRep_Builder().Add(aF, aWI);
 673     }
 674
 675     // Condition of early exit
 676     if (aMEDone.Extent() == anEdgesMap.Extent())
 677       // All edges are classified and added into the faces
 678       return;
 679   }
 680
 681   // Some edges are left unclassified - warn user about them
 682   TopTools_IndexedMapOfShape anEdgesUnUsed;
 683   for (Standard_Integer i = 1; i <= anEdgesMap.Extent(); ++i)
 684   {
 685     if (!aMEDone.Contains(i))
 686       anEdgesUnUsed.Add(anEdgesMap(i));
 687   }
 688
 689   // Make internal wires
 690   TopTools_ListOfShape aLSI;
 691   MakeInternalWires(anEdgesUnUsed, aLSI);
 692
 693   // Make compound
 694   TopoDS_Compound aWShape;
 695   BRep_Builder().MakeCompound(aWShape);
 696   BRep_Builder().Add(aWShape, myFace);
 697   if (aLSI.Extent() == 1)
 698     BRep_Builder().Add(aWShape, aLSI.First());
 699   else
 700   {
 701     TopoDS_Compound aCE;
 702     BRep_Builder().MakeCompound(aCE);
 703     for (TopTools_ListIteratorOfListOfShape it(aLSI); it.More(); it.Next())
 704       BRep_Builder().Add(aCE, it.Value());
 705     BRep_Builder().Add(aWShape, aCE);
 706   }
 707
 708   // Add warning
 709   AddWarning(new BOPAlgo_AlertFaceBuilderUnusedEdges(aWShape));
 710 }
 711 //=======================================================================
 712 //function : MakeInternalWires
 713 //purpose  :
 714 //=======================================================================
 715 void MakeInternalWires(const TopTools_IndexedMapOfShape& theME,
 716                        TopTools_ListOfShape& theWires)
 717 {
 718   Standard_Integer i, aNbE;
 719   TopTools_MapOfShape aAddedMap;
 720   TopTools_ListIteratorOfListOfShape aItE;
 721   TopTools_IndexedDataMapOfShapeListOfShape aMVE;
 722   BRep_Builder aBB;
 723   //
 724   aNbE = theME.Extent();
 725   for (i = 1; i <= aNbE; ++i) {
 726     const TopoDS_Shape& aE = theME(i);
 727     TopExp::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 728   }
 729   //
 730   for (i = 1; i <= aNbE; ++i) {
 731     TopoDS_Shape aEE = theME(i);
 732     if (!aAddedMap.Add(aEE)) {
 733       continue;
 734     }
 735     //
 736     // make a new shell
 737     TopoDS_Wire aW;
 738     aBB.MakeWire(aW);
 739     aEE.Orientation(TopAbs_INTERNAL);
 740     aBB.Add(aW, aEE);
 741     //
 742     TopoDS_Iterator aItAdded (aW);
 743     for (; aItAdded.More(); aItAdded.Next()) {
 744       const TopoDS_Shape& aE =aItAdded.Value();
 745       //
 746       TopExp_Explorer aExp(aE, TopAbs_VERTEX);
 747       for (; aExp.More(); aExp.Next()) {
 748         const TopoDS_Shape& aV =aExp.Current();
 749         const TopTools_ListOfShape& aLE=aMVE.FindFromKey(aV);
 750         aItE.Initialize(aLE);
 751         for (; aItE.More(); aItE.Next()) {
 752           TopoDS_Shape aEL=aItE.Value();
 753           if (aAddedMap.Add(aEL)){
 754             aEL.Orientation(TopAbs_INTERNAL);
 755             aBB.Add(aW, aEL);
 756           }
 757         }
 758       }
 759     }
 760     aW.Closed(BRep_Tool::IsClosed(aW));
 761     theWires.Append(aW);
 762   }
 763 }
 764 //=======================================================================
 765 //function : IsInside
 766 //purpose  :
 767 //=======================================================================
 768 Standard_Boolean IsInside(const TopoDS_Shape& theWire,
 769                           const TopoDS_Shape& theF,
 770                           Handle(IntTools_Context)& theContext)
 771 {
 772   // Check if the wire is located inside the face:
 773   // take unique point from the wire and classify it relatively the face
 774
 775   // Avoid edges of the face
 776   TopTools_IndexedMapOfShape aFaceEdgesMap;
 777   TopExp::MapShapes(theF, TopAbs_EDGE, aFaceEdgesMap);
 778
 779   // Get classification tool from the context
 780   const TopoDS_Face& aF = TopoDS::Face(theF);
 781   IntTools_FClass2d& aClassifier = theContext->FClass2d(aF);
 782
 783   Standard_Boolean isInside = Standard_False;
 784
 785   // Iterate on wire edges until first classification is performed
 786   TopExp_Explorer anExp(theWire, TopAbs_EDGE);
 787   for (; anExp.More(); anExp.Next())
 788   {
 789     const TopoDS_Edge& aE = TopoDS::Edge(anExp.Current());
 790     if (BRep_Tool::Degenerated(aE))
 791       // Avoid checking degenerated edges.
 792       continue;
 793
 794     if (aFaceEdgesMap.Contains(aE))
 795       // Face contains the edge from the wire, thus the wire cannot be
 796       // inside that face.
 797       return isInside;
 798
 799     // Get 2d curve of the edge on the face
 800     Standard_Real aT1, aT2;
 801     const Handle(Geom2d_Curve)& aC2D = BRep_Tool::CurveOnSurface(aE, aF, aT1, aT2);
 802     if (aC2D.IsNull())
 803       continue;
 804
 805     // Get middle point on the curve
 806     gp_Pnt2d aP2D = aC2D->Value((aT1 + aT2) / 2.);
 807
 808     // Classify the point
 809     TopAbs_State aState = aClassifier.Perform(aP2D);
 810     isInside = (aState == TopAbs_IN);
 811     break;
 812   }
 813   return isInside;
 814 }
 815 //=======================================================================
 816 //function : IsGrowthWire
 817 //purpose  :
 818 //=======================================================================
 819 Standard_Boolean IsGrowthWire(const TopoDS_Shape& theWire,
 820                               const TopTools_IndexedMapOfShape& theMHE)
 821 {
 822   if (theMHE.Extent())
 823   {
 824     TopoDS_Iterator aIt(theWire);
 825     for(; aIt.More(); aIt.Next())
 826     {
 827       if (theMHE.Contains(aIt.Value()))
 828         return Standard_True;
 829     }
 830   }
 831   return Standard_False;
 832 }