src/BOPAlgo/BOPAlgo_RemoveFeatures.cxx

   1 // Created by: Eugeny MALTCHIKOV
   2 // Copyright (c) 2018 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15 #include <BOPAlgo_RemoveFeatures.hxx>
  16
  17 #include <BOPAlgo_Alerts.hxx>
  18 #include <BOPAlgo_BOP.hxx>
  19 #include <BOPAlgo_Builder.hxx>
  20 #include <BOPAlgo_BuilderSolid.hxx>
  21 #include <BOPAlgo_MakerVolume.hxx>
  22 #include <BOPAlgo_Tools.hxx>
  23
  24 #include <BOPTools_AlgoTools.hxx>
  25 #include <BOPTools_Parallel.hxx>
  26 #include <BOPTools_Set.hxx>
  27
  28 #include <Bnd_Box.hxx>
  29
  30 #include <BRep_Builder.hxx>
  31
  32 #include <BRepBndLib.hxx>
  33
  34 #include <BRepLib.hxx>
  35
  36 #include <NCollection_Vector.hxx>
  37
  38 #include <ShapeUpgrade_UnifySameDomain.hxx>
  39
  40 #include <TopAbs_ShapeEnum.hxx>
  41
  42 #include <TopExp.hxx>
  43 #include <TopExp_Explorer.hxx>
  44
  45 #include <TopoDS.hxx>
  46 #include <TopoDS_Compound.hxx>
  47 #include <TopoDS_Edge.hxx>
  48 #include <TopoDS_Face.hxx>
  49
  50 #include <TopTools_IndexedDataMapOfShapeShape.hxx>
  51
  52
  53 //=======================================================================
  54 // static methods declaration
  55 //=======================================================================
  56
  57 static void MakeRemoved(const TopTools_ListOfShape& theShapes,
  58                         BRepTools_History& theHistory,
  59                         const TopTools_IndexedMapOfShape& theKeepShapes = TopTools_IndexedMapOfShape());
  60
  61 static void FindInternals(const TopoDS_Shape& theS,
  62                           TopTools_ListOfShape& theLInt);
  63
  64 static void RemoveInternalWires(const TopTools_ListOfShape& theShapes,
  65                                 TopTools_ListOfShape* theRemoved = NULL);
  66
  67 static void GetOriginalFaces(const TopoDS_Shape& theShape,
  68                              const TopTools_IndexedMapOfShape& theSolids,
  69                              const TopTools_MapOfShape& theFeatureFacesMap,
  70                              const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
  71                              const Handle(BRepTools_History)& theHistory,
  72                              TopTools_IndexedMapOfShape& theFacesToBeKept,
  73                              TopTools_ListOfShape& theInternalShapes,
  74                              TopTools_MapOfShape& theFacesToCheckOri,
  75                              TopTools_IndexedMapOfShape& theSolidsToRebuild,
  76                              TopTools_ListOfShape& theSharedFaces,
  77                              TopTools_ListOfShape& theUnTouchedSolids);
  78
  79 static void FindShape(const TopoDS_Shape& theSWhat,
  80                       const TopoDS_Shape& theSWhere,
  81                       TopoDS_Shape& theSFound);
  82
  83 static void GetValidSolids(BOPAlgo_MakerVolume& theMV,
  84                            const TopTools_MapOfShape& theFacesToCheckOri,
  85                            const TopTools_ListOfShape& aSharedFaces,
  86                            const TopoDS_Shape& theOrigFaces,
  87                            const Standard_Integer theNbSol,
  88                            TopTools_ListOfShape& theLSRes,
  89                            TopTools_ListOfShape& theRemovedShapes);
  90
  91 static void FindExtraShapes(const TopTools_IndexedDataMapOfShapeListOfShape& theConnectionMap,
  92                             const TopTools_MapOfShape& theShapesToCheckOri,
  93                             BOPAlgo_Builder& theBuilder,
  94                             TopTools_MapOfShape& theShapesToAvoid,
  95                             TopTools_MapOfShape* theValidShapes = NULL);
  96
  97 static void AvoidExtraSharedFaces(TopTools_ListOfShape& theLSolids,
  98                                   const TopTools_ListOfShape& theLFSharedToAvoid,
  99                                   BOPAlgo_Builder& theBuilder,
 100                                   TopTools_ListOfShape& theExtraFaces);
 101
 102 static void FillSolidsHistory(const TopTools_IndexedMapOfShape& theSolIn,
 103                               TopTools_ListOfShape& theSolidsRes,
 104                               const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
 105                               BOPAlgo_Builder& theBuilder,
 106                               BRepTools_History& theSolidsHistory);
 107
 108 static void TakeModified(const TopoDS_Shape& theS,
 109                          BOPAlgo_Builder& theBuilder,
 110                          TopTools_ListOfShape& theList);
 111
 112 static void TakeModified(const TopoDS_Shape& theS,
 113                          BOPAlgo_Builder& theBuilder,
 114                          TopTools_MapOfShape& theMap);
 115
 116 static void FindSolid(const TopoDS_Shape& theSolIn,
 117                       const TopTools_ListOfShape& theSolidsRes,
 118                       const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
 119                       BOPAlgo_Builder& theBuilder,
 120                       TopoDS_Shape& theSolOut);
 121
 122
 123 //=======================================================================
 124 // function: Perform
 125 // purpose: Performs the removal of the requested faces from the input shape
 126 //=======================================================================
 127 void BOPAlgo_RemoveFeatures::Perform()
 128 {
 129   try
 130   {
 131     OCC_CATCH_SIGNALS
 132
 133     if (HasHistory())
 134       myHistory = new BRepTools_History();
 135
 136     // Check the input data
 137     CheckData();
 138     if (HasErrors())
 139       return;
 140
 141     // Prepare the faces to remove.
 142     PrepareFeatures();
 143     if (HasErrors())
 144       return;
 145
 146     // Remove the features and fill the created gaps
 147     RemoveFeatures();
 148
 149     // Update history with the removed features
 150     UpdateHistory();
 151
 152     // Simplify the result
 153     SimplifyResult();
 154
 155     // Post treatment
 156     PostTreat();
 157   }
 158   catch (Standard_Failure const&)
 159   {
 160     AddError(new BOPAlgo_AlertRemoveFeaturesFailed());
 161   }
 162 }
 163
 164 //=======================================================================
 165 // function: CheckData
 166 // purpose: Checks the input data on validity for the algorithm
 167 //=======================================================================
 168 void BOPAlgo_RemoveFeatures::CheckData()
 169 {
 170   // Prepare the shape to work with
 171   myShape = myInputShape;
 172
 173   // Check the type of input shape
 174   const TopAbs_ShapeEnum aType = myInputShape.ShapeType();
 175
 176   if (aType == TopAbs_SOLID || aType == TopAbs_COMPSOLID)
 177     return; // OK
 178
 179   if (aType == TopAbs_COMPOUND)
 180   {
 181     TopTools_ListOfShape aShapes;
 182     TopTools_MapOfShape aMFence;
 183     // Extract all shapes from the compound
 184     BOPTools_AlgoTools::TreatCompound(myInputShape, aShapes, &aMFence);
 185     if (aShapes.IsEmpty())
 186     {
 187       // Add error of empty input shape
 188       AddError(new BOPAlgo_AlertEmptyShape(myInputShape));
 189       return;
 190     }
 191
 192     // Find all solids in the list of shapes
 193     TopTools_ListOfShape aSolids;
 194     TopTools_ListOfShape anOtherShapes;
 195     TopTools_ListIteratorOfListOfShape aIt(aShapes);
 196     for (; aIt.More(); aIt.Next())
 197     {
 198       const TopoDS_Shape& aS = aIt.Value();
 199       if (aS.ShapeType() == TopAbs_SOLID || aS.ShapeType() == TopAbs_COMPSOLID)
 200         aSolids.Append(aS);
 201       else
 202         anOtherShapes.Append(aS);
 203     }
 204
 205     if (aSolids.IsEmpty())
 206     {
 207       // No solids have been found for processing.
 208       // Add error of unsupported type of input shape
 209       AddError(new BOPAlgo_AlertTooFewArguments());
 210     }
 211     else if (anOtherShapes.Extent() > 0)
 212     {
 213       // Add warning of unsupported type of input shape for all
 214       // non-solid shapes, contained in the input shape
 215       for (aIt.Initialize(anOtherShapes); aIt.More(); aIt.Next())
 216       {
 217         AddWarning(new BOPAlgo_AlertUnsupportedType(aIt.Value()));
 218       }
 219
 220       // Collect all solids into compound and overwrite the shape to rebuild
 221       TopoDS_Compound aCS;
 222       BRep_Builder().MakeCompound(aCS);
 223       for (aIt.Initialize(aSolids); aIt.More(); aIt.Next())
 224         BRep_Builder().Add(aCS, aIt.Value());
 225
 226       myShape = aCS;
 227
 228       if (HasHistory())
 229       {
 230         // Make non solid shapes removed in the history
 231         MakeRemoved(anOtherShapes, *myHistory.get());
 232       }
 233     }
 234   }
 235   else
 236   {
 237     // Add error of unsupported type of input shape
 238     AddError(new BOPAlgo_AlertTooFewArguments());
 239   }
 240 }
 241
 242 //=======================================================================
 243 // function: PrepareFeatures
 244 // purpose: Prepares the features to remove
 245 //=======================================================================
 246 void BOPAlgo_RemoveFeatures::PrepareFeatures()
 247 {
 248   // Map all sub-shapes of the input solids
 249   TopExp::MapShapes(myInputShape, myInputsMap);
 250
 251   // Collect all faces of the input shape requested for removal
 252   TopTools_ListOfShape aFacesToRemove;
 253   TopTools_ListIteratorOfListOfShape aIt(myFacesToRemove);
 254   for (; aIt.More(); aIt.Next())
 255   {
 256     const TopoDS_Shape& aS = aIt.Value();
 257     TopExp_Explorer anExpF(aS, TopAbs_FACE);
 258     for (; anExpF.More(); anExpF.Next())
 259     {
 260       const TopoDS_Shape& aF = anExpF.Current();
 261       if (myInputsMap.Contains(aF))
 262         aFacesToRemove.Append(aF);
 263     }
 264   }
 265
 266   if (aFacesToRemove.IsEmpty())
 267   {
 268     // Add error, that no features to remove have been found
 269     AddError(new BOPAlgo_AlertNoFacesToRemove());
 270     return;
 271   }
 272
 273   // Build connexity blocks of the faces to remove
 274   TopoDS_Compound aCFToRemove;
 275   BRep_Builder().MakeCompound(aCFToRemove);
 276   for (aIt.Initialize(aFacesToRemove); aIt.More(); aIt.Next())
 277     BRep_Builder().Add(aCFToRemove, aIt.Value());
 278
 279   // Fill the list of features with connexity blocks of faces
 280   BOPTools_AlgoTools::MakeConnexityBlocks(aCFToRemove, TopAbs_EDGE, TopAbs_FACE, myFeatures);
 281 }
 282
 283 //=======================================================================
 284 // Adjacent faces extension block
 285
 286 //=======================================================================
 287 // class: FillGaps
 288 // purpose: Auxiliary class for creation of the faces for filling the gap
 289 //          created by removal of the single feature
 290 //=======================================================================
 291 class FillGap
 292 {
 293 public: //! @name Constructors
 294
 295   //! Empty constructor
 296   FillGap() :
 297     myRunParallel(Standard_False),
 298     myHasAdjacentFaces(Standard_False)
 299   {}
 300
 301 public: //! @name Setters/Getters
 302
 303   //! Sets the feature to remove
 304   void SetFeature(const TopoDS_Shape& theFeature) { myFeature = theFeature; }
 305
 306   //! Returns the feature
 307   const TopoDS_Shape& Feature() const { return myFeature; }
 308
 309   //! Sets the EF connection map
 310   void SetEFConnectionMap(const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap)
 311   {
 312     myEFMap = (TopTools_IndexedDataMapOfShapeListOfShape*)&theEFMap;
 313   }
 314
 315   //! Sets the FS connection map
 316   void SetFSConnectionMap(const TopTools_IndexedDataMapOfShapeListOfShape& theFSMap)
 317   {
 318     myFSMap = (TopTools_IndexedDataMapOfShapeListOfShape*)&theFSMap;
 319   }
 320
 321   //! Defines the parallel processing mode
 322   void SetRunParallel(const Standard_Boolean bRunParallel) { myRunParallel = bRunParallel; }
 323
 324   //! Gets the History object
 325   const Handle(BRepTools_History)& History()
 326   {
 327     return myHistory;
 328   }
 329
 330 public: //! @name Perform the operation
 331
 332   //! Performs the extension of the adjacent faces and
 333   //! then trims the extended faces to fill the gaps
 334   void Perform()
 335   {
 336     OCC_CATCH_SIGNALS
 337
 338     try
 339     {
 340       myHistory = new BRepTools_History();
 341
 342       // Find the faces adjacent to the faces of the feature
 343       TopTools_IndexedMapOfShape aMFAdjacent;
 344       FindAdjacentFaces(aMFAdjacent);
 345
 346       myHasAdjacentFaces = (aMFAdjacent.Extent() > 0);
 347       if (!myHasAdjacentFaces)
 348         return;
 349
 350       // Extend the adjacent faces keeping the connection to the original faces
 351       TopTools_IndexedDataMapOfShapeShape aFaceExtFaceMap;
 352       ExtendAdjacentFaces(aMFAdjacent, aFaceExtFaceMap);
 353
 354       // Trim the extended faces
 355       TrimExtendedFaces(aFaceExtFaceMap);
 356     }
 357     catch (Standard_Failure const&)
 358     {
 359       // Make sure the warning will be given on the higher level
 360       myHasAdjacentFaces = Standard_True;
 361       myFaces.Clear();
 362     }
 363   }
 364
 365 public: //! @name Obtain the result
 366
 367   //! Returns the map of faces of the feature
 368   const TopTools_MapOfShape& FeatureFacesMap() const { return myFeatureFacesMap; }
 369
 370   //! Shows whether the adjacent faces have been found for the feature
 371   Standard_Boolean HasAdjacentFaces() const { return myHasAdjacentFaces; }
 372
 373   //! Returns the Images map of the adjacent faces
 374   const TopTools_IndexedDataMapOfShapeListOfShape& Faces() const { return myFaces; }
 375
 376   //! Returns the initial solids participating in the feature removal
 377   const TopTools_IndexedMapOfShape& Solids() const { return mySolids; }
 378
 379
 380 private: //! @name Private methods performing the operation
 381
 382   //! Finds the faces adjacent to the feature and stores them into outgoing map.
 383   void FindAdjacentFaces(TopTools_IndexedMapOfShape& theMFAdjacent)
 384   {
 385     // Map the faces of the feature to avoid them in the map of adjacent faces
 386     TopoDS_Iterator aIt(myFeature);
 387     for (; aIt.More(); aIt.Next())
 388       myFeatureFacesMap.Add(aIt.Value());
 389
 390     // Find faces adjacent to the feature using the connection map
 391     aIt.Initialize(myFeature);
 392     for (; aIt.More(); aIt.Next())
 393     {
 394       const TopoDS_Shape& aF = aIt.Value();
 395       TopExp_Explorer anExpE(aF, TopAbs_EDGE);
 396       for (; anExpE.More(); anExpE.Next())
 397       {
 398         const TopoDS_Shape& aE = anExpE.Current();
 399         const TopTools_ListOfShape* pAdjacentFaces = myEFMap->Seek(aE);
 400         if (pAdjacentFaces)
 401         {
 402           TopTools_ListIteratorOfListOfShape itLFA(*pAdjacentFaces);
 403           for (; itLFA.More(); itLFA.Next())
 404           {
 405             const TopoDS_Shape& anAF = itLFA.Value();
 406             if (!myFeatureFacesMap.Contains(anAF))
 407               theMFAdjacent.Add(anAF);
 408           }
 409         }
 410       }
 411       // Find solids containing the feature face
 412       const TopTools_ListOfShape* pLS = myFSMap->Seek(aF);
 413       if (pLS)
 414       {
 415         TopTools_ListIteratorOfListOfShape itLS(*pLS);
 416         for (; itLS.More(); itLS.Next())
 417           mySolids.Add(itLS.Value());
 418       }
 419     }
 420
 421     // Find solids containing the edges of adjacent faces
 422     const Standard_Integer aNbFA = theMFAdjacent.Extent();
 423     for (Standard_Integer i = 1; i <= aNbFA; ++i)
 424     {
 425       TopExp_Explorer anExpEA(theMFAdjacent(i), TopAbs_EDGE);
 426       for (; anExpEA.More(); anExpEA.Next())
 427       {
 428         // Faces adjacent to the face adjacent to the feature
 429         const TopTools_ListOfShape* pLFAA = myEFMap->Seek(anExpEA.Current());
 430         if (pLFAA)
 431         {
 432           TopTools_ListIteratorOfListOfShape itLFAA(*pLFAA);
 433           for (; itLFAA.More(); itLFAA.Next())
 434           {
 435             // Solids containing the faces
 436             const TopTools_ListOfShape* pLS = myFSMap->Seek(itLFAA.Value());
 437             if (pLS)
 438             {
 439               TopTools_ListIteratorOfListOfShape itLS(*pLS);
 440               for (; itLS.More(); itLS.Next())
 441                 mySolids.Add(itLS.Value());
 442             }
 443           }
 444         }
 445       }
 446     }
 447   }
 448
 449   //! Extends the found adjacent faces and binds them to the original faces.
 450   void ExtendAdjacentFaces(const TopTools_IndexedMapOfShape& theMFAdjacent,
 451                            TopTools_IndexedDataMapOfShapeShape& theFaceExtFaceMap)
 452   {
 453     // Get the extension value for the faces - half of the diagonal of bounding box of the feature
 454     Bnd_Box aFeatureBox;
 455     BRepBndLib::Add(myFeature, aFeatureBox);
 456
 457     const Standard_Real anExtLength = sqrt(aFeatureBox.SquareExtent());
 458
 459     const Standard_Integer aNbFA = theMFAdjacent.Extent();
 460     for (Standard_Integer i = 1; i <= aNbFA; ++i)
 461     {
 462       const TopoDS_Face& aF = TopoDS::Face(theMFAdjacent(i));
 463       // Extend the face
 464       TopoDS_Face aFExt;
 465       BRepLib::ExtendFace(aF, anExtLength,
 466                           Standard_True, Standard_True,
 467                           Standard_True, Standard_True,
 468                           aFExt);
 469       theFaceExtFaceMap.Add(aF, aFExt);
 470       myHistory->AddModified(aF, aFExt);
 471     }
 472   }
 473
 474   //! Trims the extended adjacent faces by intersection with each other
 475   //! and following intersection with the bounds of original faces.
 476   void TrimExtendedFaces(const TopTools_IndexedDataMapOfShapeShape& theFaceExtFaceMap)
 477   {
 478     // Intersect the extended faces first
 479     BOPAlgo_Builder aGFInter;
 480     // Add faces for intersection
 481     const Standard_Integer aNbF = theFaceExtFaceMap.Extent();
 482     for (Standard_Integer i = 1; i <= aNbF; ++i)
 483       aGFInter.AddArgument(theFaceExtFaceMap(i));
 484
 485     aGFInter.SetRunParallel(myRunParallel);
 486
 487     // Intersection result
 488     TopoDS_Shape anIntResult;
 489     if (aGFInter.Arguments().Extent() > 1)
 490     {
 491       aGFInter.Perform();
 492       if (aGFInter.HasErrors())
 493         return;
 494
 495       anIntResult = aGFInter.Shape();
 496
 497       myHistory->Merge(aGFInter.History());
 498     }
 499     else
 500       anIntResult = aGFInter.Arguments().First();
 501
 502     // Prepare the EF map of the extended faces after intersection
 503     // to select from them only boundary edges
 504     TopTools_IndexedDataMapOfShapeListOfShape anEFExtMap;
 505     TopExp::MapShapesAndAncestors(anIntResult, TopAbs_EDGE, TopAbs_FACE, anEFExtMap);
 506
 507     // Get the splits of the extended faces after intersection
 508     // and trim them by the edges of the original faces
 509
 510     // Map the edges of the Feature to avoid them during the trim
 511     TopTools_IndexedMapOfShape aFeatureEdgesMap;
 512     TopExp::MapShapes(myFeature, TopAbs_EDGE, aFeatureEdgesMap);
 513
 514     for (Standard_Integer i = 1; i <= aNbF; ++i)
 515     {
 516       const TopoDS_Face& aFOriginal = TopoDS::Face(theFaceExtFaceMap.FindKey(i));
 517       const TopoDS_Face& aFExt = TopoDS::Face(theFaceExtFaceMap(i));
 518       TrimFace(aFExt, aFOriginal, aFeatureEdgesMap, anEFExtMap, aGFInter);
 519     }
 520   }
 521
 522   //! Trim the extended faces by the bounds of the original face,
 523   //! except those contained in the feature to remove.
 524   void TrimFace(const TopoDS_Face& theFExt,
 525                 const TopoDS_Face& theFOriginal,
 526                 const TopTools_IndexedMapOfShape& theFeatureEdgesMap,
 527                 const TopTools_IndexedDataMapOfShapeListOfShape& theEFExtMap,
 528                 BOPAlgo_Builder& theGFInter)
 529   {
 530     // Map all edges of the extended face, to filter the result of trim
 531     // from the faces containing these edges
 532     TopTools_MapOfShape aMExtEdges;
 533     TopExp_Explorer anExpE(theFExt, TopAbs_EDGE);
 534     for (; anExpE.More(); anExpE.Next())
 535     {
 536       const TopoDS_Edge& aE = TopoDS::Edge(anExpE.Current());
 537       // skip degenerated and seam edges
 538       if (BRep_Tool::Degenerated(aE) || BRep_Tool::IsClosed(aE, theFExt))
 539         continue;
 540       TopTools_ListOfShape aLEIm;
 541       TakeModified(aE, theGFInter, aLEIm);
 542       TopTools_ListIteratorOfListOfShape itLEIm(aLEIm);
 543       for (; itLEIm.More(); itLEIm.Next())
 544       {
 545         const TopoDS_Shape& aEIm = itLEIm.Value();
 546         if (theEFExtMap.FindFromKey(aEIm).Extent() == 1)
 547           aMExtEdges.Add(aEIm);
 548       }
 549     }
 550
 551     // Trimming tool
 552     BOPAlgo_Builder aGFTrim;
 553
 554     // Get the splits of the face and add them for trimming
 555     TopTools_ListOfShape anExtSplits;
 556     TakeModified(theFExt, theGFInter, anExtSplits);
 557     aGFTrim.SetArguments(anExtSplits);
 558
 559     // Add edges of the original faces
 560     TopTools_MapOfShape aMEdgesToCheckOri;
 561     anExpE.Init(theFOriginal, TopAbs_EDGE);
 562     for (; anExpE.More(); anExpE.Next())
 563     {
 564       const TopoDS_Edge& aE = TopoDS::Edge(anExpE.Current());
 565       if (!theFeatureEdgesMap.Contains(aE))
 566       {
 567         aGFTrim.AddArgument(aE);
 568         if (!BRep_Tool::Degenerated(aE) &&
 569             !BRep_Tool::IsClosed(aE, theFOriginal))
 570         {
 571           if (!aMEdgesToCheckOri.Add(aE))
 572             aMEdgesToCheckOri.Remove(aE);
 573         }
 574       }
 575     }
 576
 577     // Avoid faces intersection
 578     aGFTrim.SetGlue(BOPAlgo_GlueShift);
 579     aGFTrim.SetRunParallel(myRunParallel);
 580     aGFTrim.SetNonDestructive(Standard_True);
 581
 582     aGFTrim.Perform();
 583     if (aGFTrim.HasErrors())
 584       return;
 585
 586     // Get all splits
 587     const TopoDS_Shape& aSplits = aGFTrim.Shape();
 588     // Filter the trimmed faces and save the valid ones into result map
 589     TopTools_ListOfShape aLFTrimmed;
 590
 591     TopExp_Explorer anExpF(aSplits, TopAbs_FACE);
 592     for (; anExpF.More(); anExpF.Next())
 593     {
 594       const TopoDS_Shape& aSp = anExpF.Current();
 595       anExpE.Init(aSp, TopAbs_EDGE);
 596       for (; anExpE.More(); anExpE.Next())
 597       {
 598         if (aMExtEdges.Contains(anExpE.Current()))
 599           break;
 600       }
 601       if (!anExpE.More())
 602         aLFTrimmed.Append(aSp);
 603     }
 604
 605     if (aLFTrimmed.Extent() > 1)
 606     {
 607       // Chose the correct faces - the ones that contains edges with proper
 608       // bi-normal direction
 609       TopTools_IndexedDataMapOfShapeListOfShape anEFMap;
 610       TopTools_ListIteratorOfListOfShape itLF(aLFTrimmed);
 611       for (; itLF.More(); itLF.Next())
 612         TopExp::MapShapesAndAncestors(itLF.Value(), TopAbs_EDGE, TopAbs_FACE, anEFMap);
 613
 614       // Check edges orientations
 615       TopTools_MapOfShape aFacesToAvoid, aValidFaces;
 616       FindExtraShapes(anEFMap, aMEdgesToCheckOri, aGFTrim, aFacesToAvoid, &aValidFaces);
 617
 618       if (aLFTrimmed.Extent() - aFacesToAvoid.Extent() > 1)
 619       {
 620         // It is possible that the splits are forming the different blocks.
 621         // Take only those containing the valid faces.
 622         TopoDS_Compound aCF;
 623         BRep_Builder().MakeCompound(aCF);
 624         itLF.Initialize(aLFTrimmed);
 625         for (; itLF.More(); itLF.Next())
 626         {
 627           if (!aFacesToAvoid.Contains(itLF.Value()))
 628             BRep_Builder().Add(aCF, itLF.Value());
 629         }
 630
 631         TopTools_ListOfShape aLCB;
 632         BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
 633         if (aLCB.Extent() > 1)
 634         {
 635           TopTools_ListIteratorOfListOfShape itLCB(aLCB);
 636           for (; itLCB.More(); itLCB.Next())
 637           {
 638             // Check if the block contains any valid faces
 639             const TopoDS_Shape& aCB = itLCB.Value();
 640             TopoDS_Iterator itF(aCB);
 641             for (; itF.More(); itF.Next())
 642             {
 643               if (aValidFaces.Contains(itF.Value()))
 644                 break;
 645             }
 646             if (!itF.More())
 647             {
 648               // Invalid block
 649               for (itF.Initialize(aCB); itF.More(); itF.Next())
 650                 aFacesToAvoid.Add(itF.Value());
 651             }
 652           }
 653         }
 654       }
 655
 656       itLF.Initialize(aLFTrimmed);
 657       for (; itLF.More();)
 658       {
 659         if (aFacesToAvoid.Contains(itLF.Value()))
 660           aLFTrimmed.Remove(itLF);
 661         else
 662           itLF.Next();
 663       }
 664     }
 665     else if (aLFTrimmed.IsEmpty())
 666     {
 667       // Use all splits, including those having the bounds of extended face
 668       anExpF.ReInit();
 669       for (; anExpF.More(); anExpF.Next())
 670         aLFTrimmed.Append(anExpF.Current());
 671     }
 672
 673     if (aLFTrimmed.Extent())
 674     {
 675       // Remove the internal edges and vertices from the faces
 676       RemoveInternalWires(aLFTrimmed);
 677
 678       myFaces.Add(theFOriginal, aLFTrimmed);
 679     }
 680
 681     // Update history after intersection of the extended face with bounds
 682     myHistory->Merge(aGFTrim.History());
 683
 684     // Update history with all removed shapes
 685     BRepTools_History aHistRem;
 686
 687     // Map of the result splits
 688     TopTools_IndexedMapOfShape aResMap;
 689     TopTools_ListIteratorOfListOfShape itLF(aLFTrimmed);
 690     for (; itLF.More(); itLF.Next())
 691       TopExp::MapShapes(itLF.Value(), aResMap);
 692
 693     TopTools_ListOfShape aLSplits;
 694     aLSplits.Append(aSplits);
 695
 696     // Update the history with removed shapes
 697     MakeRemoved(aLSplits, aHistRem, aResMap);
 698     myHistory->Merge(aHistRem);
 699   }
 700
 701 private: //! @name Fields
 702
 703   // Inputs
 704   Standard_Boolean myRunParallel;                     //!< Defines the mode of processing of the single feature
 705   TopoDS_Shape myFeature;                             //!< Feature to remove
 706   TopTools_IndexedDataMapOfShapeListOfShape* myEFMap; //!< EF Connection map to find adjacent faces
 707   TopTools_IndexedDataMapOfShapeListOfShape* myFSMap; //!< FS Connection map to find solids participating in the feature removal
 708
 709   // Results
 710   TopTools_MapOfShape myFeatureFacesMap;              //!< Faces of the feature
 711   Standard_Boolean myHasAdjacentFaces;                //!< Flag to show whether the adjacent faces have been found or not
 712   TopTools_IndexedMapOfShape mySolids;                //!< Solids participating in the feature removal
 713   TopTools_IndexedDataMapOfShapeListOfShape myFaces;  //!< Reconstructed adjacent faces
 714   Handle(BRepTools_History) myHistory;                //!< History of the adjacent faces reconstruction
 715 };
 716
 717 typedef NCollection_Vector<FillGap> VectorOfFillGap;
 718
 719 //=======================================================================
 720 // function: RemoveFeatures
 721 // purpose: Remove features by filling the gaps by extension of the
 722 //          adjacent faces
 723 //=======================================================================
 724 void BOPAlgo_RemoveFeatures::RemoveFeatures()
 725 {
 726   // For each feature:
 727   // - Find the faces adjacent to the feature;
 728   // - Extend the adjacent faces;
 729   // - Trim the extended faces to fill the gap;
 730   // - Rebuild the solids with reconstructed adjacent faces
 731   //   and avoiding the feature faces.
 732
 733   // Make Edge-Face connection map of the input
 734   // shape to find faces adjacent to the feature
 735   TopTools_IndexedDataMapOfShapeListOfShape anEFMap;
 736   TopExp::MapShapesAndAncestors(myInputShape, TopAbs_EDGE, TopAbs_FACE, anEFMap);
 737
 738   // Make Face-Solid connection map to find the solids
 739   // participating in the removal of each feature
 740   TopTools_IndexedDataMapOfShapeListOfShape anFSMap;
 741   TopExp::MapShapesAndAncestors(myInputShape, TopAbs_FACE, TopAbs_SOLID, anFSMap);
 742
 743   // Tool for reconstruction of the faces adjacent to the feature
 744   // in parallel threads if necessary.
 745   VectorOfFillGap aVFG;
 746   // Fill the vector
 747   TopTools_ListIteratorOfListOfShape itF(myFeatures);
 748   for (; itF.More(); itF.Next())
 749   {
 750     const TopoDS_Shape& aFeature = itF.Value();
 751     FillGap& aFG = aVFG.Appended();
 752     aFG.SetFeature(aFeature);
 753     aFG.SetEFConnectionMap(anEFMap);
 754     aFG.SetFSConnectionMap(anFSMap);
 755     aFG.SetRunParallel(myRunParallel);
 756   }
 757
 758   // Perform the reconstruction of the adjacent faces
 759   BOPTools_Parallel::Perform (myRunParallel, aVFG);
 760
 761   // Even if the history is not requested, it is necessary to track:
 762   // - The solids modification after each feature removal to find
 763   //   the necessary solids to rebuild on the next step.
 764   // - The faces modification after each feature removal to find the
 765   //   splits of the adjacent and feature faces for the next steps.
 766   if (myHistory.IsNull())
 767     myHistory = new BRepTools_History();
 768
 769   // Remove the features one by one.
 770   // It will allow removing the features even if there were
 771   // some problems with removal of the previous features.
 772   const Standard_Integer aNbF = aVFG.Length();
 773   for (Standard_Integer i = 0; i < aNbF; ++i)
 774   {
 775     FillGap& aFG = aVFG(i);
 776
 777     // No need to fill the history for solids if the history is not
 778     // requested and the current feature is the last one.
 779     Standard_Boolean isSolidsHistoryNeeded = HasHistory() || (i < (aNbF - 1));
 780
 781     // Perform removal of the single feature
 782     RemoveFeature(aFG.Feature(), aFG.Solids(), aFG.FeatureFacesMap(),
 783                   aFG.HasAdjacentFaces(), aFG.Faces(), aFG.History(),
 784                   isSolidsHistoryNeeded);
 785   }
 786 }
 787
 788 //=======================================================================
 789 // function: RemoveFeature
 790 // purpose: Remove the single feature
 791 //=======================================================================
 792 void BOPAlgo_RemoveFeatures::RemoveFeature
 793   (const TopoDS_Shape& theFeature,
 794    const TopTools_IndexedMapOfShape& theSolids,
 795    const TopTools_MapOfShape& theFeatureFacesMap,
 796    const Standard_Boolean theHasAdjacentFaces,
 797    const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
 798    const Handle(BRepTools_History)& theAdjFacesHistory,
 799    const Standard_Boolean theSolidsHistoryNeeded)
 800 {
 801   Standard_Boolean bFuseShapes = Standard_True;
 802   const Standard_Integer aNbAF = theAdjFaces.Extent();
 803   if (aNbAF == 0)
 804   {
 805     if (theHasAdjacentFaces)
 806     {
 807       // The adjacent faces have been found for the feature,
 808       // but something went wrong during their rebuilding.
 809       // Add error
 810       AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 811       return;
 812     }
 813
 814     // No adjacent faces have been found for the feature.
 815     // Most likely, the intention is to remove some internal part of the shape.
 816     // We just have to rebuild the shape without the feature, no fuse is necessary.
 817     bFuseShapes = Standard_False;
 818   }
 819
 820   // Rebuild the shape using MakerVolume algorithm avoiding the faces of the
 821   // feature and replacing the adjacent faces with their images
 822
 823   BRep_Builder aBB;
 824
 825   // From the faces of input shape build map of faces with which the result will be validated:
 826   // - all non-internal faces of the input shape (except for adjacent and feature faces)
 827   //   must have some trace in the result solids;
 828   // - all adjacent faces (if any) must have some trace in the result solids.
 829   TopTools_IndexedMapOfShape aFacesToBeKept;
 830   // Build also the map of faces to compare orientation of the original and result faces
 831   TopTools_MapOfShape aFacesToCheckOri;
 832
 833   // Collect list of internal entities of the input shape to be avoided in result
 834   // and to make them removed in the history.
 835   TopTools_ListOfShape anInternalShapes;
 836
 837   // In the feature removal will participate only the solids connected to the feature
 838   // or the faces adjacent to the feature.
 839
 840   // Solids to be rebuilt  after the feature removal
 841   TopTools_IndexedMapOfShape aSolidsToRebuild;
 842   // Find faces shared between solids
 843   TopTools_ListOfShape aSharedFaces;
 844   // Solids to be avoided in the feature removal and added into result directly
 845   TopTools_ListOfShape anUnTouchedSolids;
 846
 847   // Prepare to the feature removal - fill all necessary containers
 848   GetOriginalFaces(myShape, theSolids, theFeatureFacesMap, theAdjFaces, myHistory,
 849                    aFacesToBeKept, anInternalShapes, aFacesToCheckOri,
 850                    aSolidsToRebuild, aSharedFaces, anUnTouchedSolids);
 851
 852   // To avoid excessive intersection of the faces collect the faces
 853   // of the input shape into a compound
 854   TopoDS_Compound anOrigF;
 855   aBB.MakeCompound(anOrigF);
 856   Standard_Integer aNbFK = aFacesToBeKept.Extent();
 857   for (Standard_Integer i = 1; i <= aNbFK; ++i)
 858     aBB.Add(anOrigF, aFacesToBeKept(i));
 859
 860   // Tool for solids reconstruction
 861   BOPAlgo_MakerVolume aMV;
 862   aMV.SetRunParallel(myRunParallel);
 863   aMV.SetAvoidInternalShapes(Standard_True);
 864   aMV.SetIntersect(bFuseShapes);
 865   aMV.SetNonDestructive(Standard_True);
 866   // Add faces of the input shape
 867   aMV.AddArgument(anOrigF);
 868
 869   // Add reconstructed adjacent faces
 870   for (Standard_Integer i = 1; i <= aNbAF; ++i)
 871   {
 872     const TopTools_ListOfShape& aLFA = theAdjFaces(i);
 873     if (aLFA.Extent() == 1)
 874     {
 875       const TopoDS_Shape& aFA = aLFA.First();
 876       aMV.AddArgument(aFA);
 877       aFacesToBeKept.Add(aFA);
 878     }
 879     else
 880     {
 881       // To avoid intersection among the images, collect them into compound
 882       TopoDS_Compound anAdjF;
 883       aBB.MakeCompound(anAdjF);
 884       TopTools_ListIteratorOfListOfShape itLFA(aLFA);
 885       for (; itLFA.More(); itLFA.Next())
 886         aBB.Add(anAdjF, itLFA.Value());
 887
 888       aMV.AddArgument(anAdjF);
 889       aFacesToBeKept.Add(anAdjF);
 890     }
 891
 892     if (HasHistory())
 893     {
 894       // Look for internal edges in the original adjacent faces
 895       const TopoDS_Shape& aFOr = theAdjFaces.FindKey(i);
 896       FindInternals(aFOr, anInternalShapes);
 897     }
 898   }
 899
 900   // Build solids
 901   aMV.Perform();
 902   if (aMV.HasErrors())
 903   {
 904     // Add warning for the feature
 905     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 906     return;
 907   }
 908
 909   // Result of MV operation
 910   const TopoDS_Shape& aSolids = aMV.Shape();
 911   TopExp_Explorer anExpS(aSolids, TopAbs_SOLID);
 912   if (!anExpS.More())
 913   {
 914     // No solids have been built - add warning for the feature
 915     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 916     return;
 917   }
 918
 919   // Now, it is necessary to:
 920   // - Validate the result by checking faces of the map <aFacesToBeKept>
 921   //   to have some parts kept in the resulting solids;
 922   // - Remove the solids possibly filling the holes in the original shapes;
 923   // - Update history with the history of MakerVolume algorithm.
 924
 925   // Splits of adjacent faces from previous runs
 926   TopTools_MapOfShape anAdjFacesSplits;
 927   for (Standard_Integer i = 1; i <= aNbAF; ++i)
 928   {
 929     const TopoDS_Shape& aF = theAdjFaces.FindKey(i);
 930     const TopTools_ListOfShape& aLFIm = myHistory->Modified(aF);
 931     if (aLFIm.IsEmpty())
 932       anAdjFacesSplits.Add(aF);
 933     else
 934     {
 935       TopTools_ListIteratorOfListOfShape itLFIm(aLFIm);
 936       for (; itLFIm.More(); itLFIm.Next())
 937         anAdjFacesSplits.Add(itLFIm.Value());
 938     }
 939   }
 940
 941   // Validate the result
 942   Standard_Boolean bValid = Standard_True;
 943   aNbFK = aFacesToBeKept.Extent();
 944   for (Standard_Integer i = 1; i <= aNbFK && bValid; ++i)
 945   {
 946     const TopoDS_Shape& aS = aFacesToBeKept(i);
 947     if (anAdjFacesSplits.Contains(aS))
 948       continue;
 949     TopExp_Explorer anExpF(aS, TopAbs_FACE);
 950     for (; anExpF.More(); anExpF.Next())
 951     {
 952       const TopoDS_Shape& aF = anExpF.Current();
 953       if (!aMV.IsDeleted(aF))
 954         break;
 955     }
 956     bValid = anExpF.More();
 957   }
 958
 959   if (!bValid)
 960   {
 961     // Add warning for the feature
 962     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 963     return;
 964   }
 965
 966   // It is possible that the result of MakerVolume operation contains
 967   // some extra solids. Get only correct solids.
 968   TopTools_ListOfShape aLSRes;
 969   // Remember the removed shapes
 970   TopTools_ListOfShape aRemovedShapes;
 971   GetValidSolids(aMV, aFacesToCheckOri, aSharedFaces, anOrigF, theSolids.Extent(), aLSRes, aRemovedShapes);
 972
 973   if (aLSRes.Extent() != theSolids.Extent())
 974   {
 975     // Add warning for the feature
 976     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 977     return;
 978   }
 979
 980   // Remove internal wires from the faces, possibly appeared after intersection
 981   RemoveInternalWires(aLSRes, &anInternalShapes);
 982
 983   // Update history with:
 984   // History of adjacent faces reconstruction
 985   myHistory->Merge(theAdjFacesHistory);
 986   // History of intersection
 987   myHistory->Merge(aMV.History());
 988
 989   if (HasHistory())
 990   {
 991     // Map the result to check if the shape is removed
 992     TopTools_IndexedMapOfShape aMSRes;
 993     TopTools_ListIteratorOfListOfShape itLS(aLSRes);
 994     for (; itLS.More(); itLS.Next())
 995       TopExp::MapShapes(itLS.Value(), aMSRes);
 996
 997     // Remove internal shapes and extra faces
 998     BRepTools_History aRemHist;
 999     anInternalShapes.Append(aRemovedShapes);
1000     MakeRemoved(anInternalShapes, aRemHist, aMSRes);
1001     myHistory->Merge(aRemHist);
1002   }
1003
1004   // Fill the history for the solids
1005   if (theSolidsHistoryNeeded)
1006   {
1007     BRepTools_History aSolidsHistory;
1008     FillSolidsHistory(aSolidsToRebuild, aLSRes, theAdjFaces, aMV, aSolidsHistory);
1009     myHistory->Merge(aSolidsHistory);
1010   }
1011
1012   TopoDS_Compound aCRes;
1013   aBB.MakeCompound(aCRes);
1014   // Add reconstructed solids
1015   TopTools_ListIteratorOfListOfShape itLS(aLSRes);
1016   for (; itLS.More(); itLS.Next())
1017     aBB.Add(aCRes, itLS.Value());
1018
1019   // Add unmodified solids
1020   itLS.Initialize(anUnTouchedSolids);
1021   for (; itLS.More(); itLS.Next())
1022     aBB.Add(aCRes, itLS.Value());
1023
1024   // Save the result
1025   myShape = aCRes;
1026 }
1027
1028 //=======================================================================
1029 // function: UpdateHistory
1030 // purpose: Update history with the removed features
1031 //=======================================================================
1032 void BOPAlgo_RemoveFeatures::UpdateHistory()
1033 {
1034   if (!HasHistory())
1035     return;
1036
1037   // Map the result
1038   myMapShape.Clear();
1039   TopExp::MapShapes(myShape, myMapShape);
1040
1041   // Update the history
1042   BRepTools_History aHistory;
1043
1044   const Standard_Integer aNbS = myInputsMap.Extent();
1045   for (Standard_Integer i = 1; i <= aNbS; ++i)
1046   {
1047     const TopoDS_Shape& aS = myInputsMap(i);
1048     if (!BRepTools_History::IsSupportedType(aS))
1049       continue;
1050
1051     if (myHistory->IsRemoved(aS))
1052       continue;
1053
1054     // Check if the shape has any trace in the result
1055     const TopTools_ListOfShape& aLSIm = myHistory->Modified(aS);
1056     if (aLSIm.IsEmpty())
1057     {
1058       if (!myMapShape.Contains(aS))
1059         aHistory.Remove(aS);
1060     }
1061
1062     TopTools_ListIteratorOfListOfShape itLSIm(aLSIm);
1063     for (; itLSIm.More(); itLSIm.Next())
1064     {
1065       if (!myMapShape.Contains(itLSIm.Value()))
1066         aHistory.Remove(itLSIm.Value());
1067     }
1068   }
1069
1070   myHistory->Merge(aHistory);
1071 }
1072
1073 //=======================================================================
1074 // function: SimplifyResult
1075 // purpose: Simplifies the result by removing extra edges and vertices
1076 //          created during operation
1077 //=======================================================================
1078 void BOPAlgo_RemoveFeatures::SimplifyResult()
1079 {
1080   if (myShape.IsSame(myInputShape))
1081     return;
1082   ShapeUpgrade_UnifySameDomain aSDTool;
1083   aSDTool.Initialize(myShape, Standard_True, Standard_True);
1084   // Do not allow producing internal edges
1085   aSDTool.AllowInternalEdges(Standard_False);
1086   // Avoid removal of the input edges and vertices
1087   if (myMapShape.IsEmpty())
1088     TopExp::MapShapes(myShape, myMapShape);
1089
1090   const Standard_Integer aNbS = myInputsMap.Extent();
1091   for (Standard_Integer i = 1; i <= aNbS; ++i)
1092   {
1093     if (myMapShape.Contains(myInputsMap(i)))
1094       aSDTool.KeepShape(myInputsMap(i));
1095   }
1096
1097   // Perform unification
1098   aSDTool.Build();
1099   myShape = aSDTool.Shape();
1100   if (HasHistory())
1101     myHistory->Merge(aSDTool.History());
1102 }
1103
1104 //=======================================================================
1105 // function: PostTreat
1106 // purpose: Restore the type of the initial shape
1107 //=======================================================================
1108 void BOPAlgo_RemoveFeatures::PostTreat()
1109 {
1110   const TopAbs_ShapeEnum anInputType = myInputShape.ShapeType();
1111   const TopAbs_ShapeEnum aResType = myShape.ShapeType();
1112   if (aResType == anInputType)
1113     return;
1114
1115   TopExp_Explorer anExpS(myShape, TopAbs_SOLID);
1116
1117   if (anInputType == TopAbs_SOLID)
1118   {
1119     myShape = anExpS.Current();
1120     return;
1121   }
1122
1123   TopoDS_Shape aRes;
1124   if (anInputType == TopAbs_COMPOUND)
1125     BRep_Builder().MakeCompound(TopoDS::Compound(aRes));
1126   else
1127     BRep_Builder().MakeCompSolid(TopoDS::CompSolid(aRes));
1128
1129   for (; anExpS.More(); anExpS.Next())
1130     BRep_Builder().Add(aRes, anExpS.Current());
1131
1132   myShape = aRes;
1133 }
1134
1135 //=======================================================================
1136 // static methods definition
1137 //=======================================================================
1138
1139 //=======================================================================
1140 // function: MakeRemoved
1141 // purpose: Makes the shapes in the list removed in the history.
1142 //          Keeps the shapes contained in the map.
1143 //=======================================================================
1144 void MakeRemoved(const TopTools_ListOfShape& theShapes,
1145                  BRepTools_History& theHistory,
1146                  const TopTools_IndexedMapOfShape& theKeepShapes)
1147 {
1148   TopTools_IndexedMapOfShape aShapesMap;
1149   TopTools_ListIteratorOfListOfShape it(theShapes);
1150   for (; it.More(); it.Next())
1151     TopExp::MapShapes(it.Value(), aShapesMap);
1152
1153   const Standard_Integer aNbS = aShapesMap.Extent();
1154   for (Standard_Integer i = 1; i <= aNbS; ++i)
1155   {
1156     const TopoDS_Shape& aS = aShapesMap(i);
1157     if (!theKeepShapes.Contains(aS) &&
1158         BRepTools_History::IsSupportedType(aS))
1159     {
1160       theHistory.Remove(aS);
1161     }
1162   }
1163 }
1164
1165 //=======================================================================
1166 // function: FindInternals
1167 // purpose: Looks for internal shapes inside the face or solid
1168 //=======================================================================
1169 void FindInternals(const TopoDS_Shape& theS,
1170                    TopTools_ListOfShape& theLInt)
1171 {
1172   TopoDS_Iterator itS(theS);
1173   for (; itS.More(); itS.Next())
1174   {
1175     const TopoDS_Shape& aSS = itS.Value();
1176     if (aSS.Orientation() == TopAbs_INTERNAL)
1177       theLInt.Append(aSS);
1178     else
1179     {
1180       TopoDS_Iterator itSS(aSS);
1181       for (; itSS.More(); itSS.Next())
1182       {
1183         if (itSS.Value().Orientation() == TopAbs_INTERNAL)
1184         {
1185           theLInt.Append(aSS);
1186           break;
1187         }
1188       }
1189     }
1190   }
1191 }
1192
1193 //=======================================================================
1194 // function: RemoveInternalWires
1195 // purpose: Removes internal wires from the faces
1196 //=======================================================================
1197 void RemoveInternalWires(const TopTools_ListOfShape& theShapes,
1198                          TopTools_ListOfShape *theRemoved)
1199 {
1200   TopTools_ListIteratorOfListOfShape itLS(theShapes);
1201   for (; itLS.More(); itLS.Next())
1202   {
1203     const TopoDS_Shape& aShape = itLS.Value();
1204     TopExp_Explorer anExpF(aShape, TopAbs_FACE);
1205     for (; anExpF.More(); anExpF.Next())
1206     {
1207       TopoDS_Face& aF = *(TopoDS_Face*)&anExpF.Current();
1208       TopTools_ListOfShape aLWToRemove;
1209       FindInternals(aF, aLWToRemove);
1210       if (aLWToRemove.Extent())
1211       {
1212         aF.Free(Standard_True);
1213         TopTools_ListIteratorOfListOfShape itR(aLWToRemove);
1214         for (; itR.More(); itR.Next())
1215         {
1216           if (theRemoved)
1217             theRemoved->Append(itR.Value());
1218           BRep_Builder().Remove(aF, itR.Value());
1219         }
1220         aF.Free(Standard_False);
1221       }
1222     }
1223   }
1224 }
1225
1226 //=======================================================================
1227 // function: GetOriginalFaces
1228 // purpose: Get original faces from my face
1229 //=======================================================================
1230 void GetOriginalFaces(const TopoDS_Shape& theShape,
1231                       const TopTools_IndexedMapOfShape& theSolids,
1232                       const TopTools_MapOfShape& theFeatureFacesMap,
1233                       const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
1234                       const Handle(BRepTools_History)& theHistory,
1235                       TopTools_IndexedMapOfShape& theFacesToBeKept,
1236                       TopTools_ListOfShape& theInternalShapes,
1237                       TopTools_MapOfShape& theFacesToCheckOri,
1238                       TopTools_IndexedMapOfShape& theSolidsToRebuild,
1239                       TopTools_ListOfShape& theSharedFaces,
1240                       TopTools_ListOfShape& theUnTouchedSolids)
1241 {
1242   // Use only solids which has to be reconstructed by the feature.
1243   // All other solids should be avoided in the feature removal and added
1244   // into result directly.
1245
1246   // Update solids after removal of previous features
1247   const Standard_Integer aNbSols = theSolids.Extent();
1248   for (Standard_Integer i = 1; i <= aNbSols; ++i)
1249   {
1250     const TopoDS_Shape& aSol = theSolids(i);
1251     const TopTools_ListOfShape& aLFIm = theHistory->Modified(aSol);
1252     if (aLFIm.IsEmpty())
1253       theSolidsToRebuild.Add(aSol);
1254     else
1255       theSolidsToRebuild.Add(aLFIm.First());
1256   }
1257
1258   // Splits of the feature faces
1259   TopTools_MapOfShape aFeatureFacesSplits;
1260   TopTools_MapIteratorOfMapOfShape itM(theFeatureFacesMap);
1261   for (; itM.More(); itM.Next())
1262   {
1263     const TopoDS_Shape& aF = itM.Value();
1264     const TopTools_ListOfShape& aLFIm = theHistory->Modified(aF);
1265     if (aLFIm.IsEmpty())
1266       aFeatureFacesSplits.Add(aF);
1267     else
1268     {
1269       TopTools_ListIteratorOfListOfShape itLFIm(aLFIm);
1270       for (; itLFIm.More(); itLFIm.Next())
1271         aFeatureFacesSplits.Add(itLFIm.Value());
1272     }
1273   }
1274
1275   TopExp_Explorer anExpS(theShape, TopAbs_SOLID);
1276   for (; anExpS.More(); anExpS.Next())
1277   {
1278     const TopoDS_Shape& aSol = anExpS.Current();
1279
1280     // Check if the solid has to be reconstructed
1281     if (!theSolidsToRebuild.Contains(aSol))
1282     {
1283       // untouched solid
1284       theUnTouchedSolids.Append(aSol);
1285       continue;
1286     }
1287
1288     TopoDS_Iterator itSh(aSol);
1289     for (; itSh.More(); itSh.Next())
1290     {
1291       const TopoDS_Shape& aSh = itSh.Value();
1292       if (aSh.ShapeType() != TopAbs_SHELL)
1293       {
1294         theInternalShapes.Append(aSh);
1295         continue;
1296       }
1297
1298       TopoDS_Iterator itF(aSh);
1299       for (; itF.More(); itF.Next())
1300       {
1301         const TopoDS_Shape& aF = itF.Value();
1302         // Avoid the feature faces
1303         if (aFeatureFacesSplits.Contains(aF))
1304           continue;
1305
1306         // Avoid the adjacent faces
1307         if (theAdjFaces.Contains(aF))
1308           continue;
1309
1310         if (aF.Orientation() != TopAbs_INTERNAL)
1311         {
1312           theFacesToBeKept.Add(aF);
1313
1314           if (!theFacesToCheckOri.Add(aF))
1315           {
1316             theFacesToCheckOri.Remove(aF);
1317             theSharedFaces.Append(aF);
1318           }
1319         }
1320         else
1321           theInternalShapes.Append(aSh);
1322       }
1323     }
1324   }
1325 }
1326
1327 //=======================================================================
1328 // function: FindShape
1329 // purpose: Find the shape in the other shape
1330 //=======================================================================
1331 void FindShape(const TopoDS_Shape& theSWhat,
1332                const TopoDS_Shape& theSWhere,
1333                TopoDS_Shape& theSFound)
1334 {
1335   TopExp_Explorer anExp(theSWhere, theSWhat.ShapeType());
1336   for (; anExp.More(); anExp.Next())
1337   {
1338     const TopoDS_Shape& aS = anExp.Current();
1339     if (aS.IsSame(theSWhat))
1340     {
1341       theSFound = aS;
1342       break;
1343     }
1344   }
1345 }
1346
1347 //=======================================================================
1348 // function: GetValidSolids
1349 // purpose: Checks the validity of the solids and keeps only valid ones
1350 //=======================================================================
1351 void GetValidSolids(BOPAlgo_MakerVolume& theMV,
1352                     const TopTools_MapOfShape& theFacesToCheckOri,
1353                     const TopTools_ListOfShape& aSharedFaces,
1354                     const TopoDS_Shape& theOrigFaces,
1355                     const Standard_Integer theNbSol,
1356                     TopTools_ListOfShape& theLSRes,
1357                     TopTools_ListOfShape& theRemovedShapes)
1358 {
1359   TopExp_Explorer anExpS(theMV.Shape(), TopAbs_SOLID);
1360   for (; anExpS.More(); anExpS.Next())
1361     theLSRes.Append(anExpS.Current());
1362
1363   if (theLSRes.Extent() > theNbSol)
1364   {
1365     // Find Solids filling the holes in the initial shape
1366     TopTools_MapOfShape aSolidsToAvoid;
1367     TopTools_IndexedDataMapOfShapeListOfShape aFSMap;
1368     TopExp::MapShapesAndAncestors(theMV.Shape(), TopAbs_FACE, TopAbs_SOLID, aFSMap);
1369     FindExtraShapes(aFSMap, theFacesToCheckOri, theMV, aSolidsToAvoid);
1370
1371     TopTools_ListIteratorOfListOfShape itLS(theLSRes);
1372     for (; itLS.More(); )
1373     {
1374       if (aSolidsToAvoid.Contains(itLS.Value()))
1375         theLSRes.Remove(itLS);
1376       else
1377         itLS.Next();
1378     }
1379   }
1380
1381   if (theLSRes.Extent() > theNbSol)
1382   {
1383     // Check if the splits of the adjacent faces split the solids
1384     AvoidExtraSharedFaces(theLSRes, aSharedFaces, theMV, theRemovedShapes);
1385   }
1386
1387   if (theLSRes.Extent() > theNbSol)
1388   {
1389     // Remove solids containing only the adjacent faces
1390     TopTools_MapOfShape anOrigFacesRes;
1391     TopExp_Explorer anExpF(theOrigFaces, TopAbs_FACE);
1392     for (; anExpF.More(); anExpF.Next())
1393       TakeModified(anExpF.Current(), theMV, anOrigFacesRes);
1394
1395     TopTools_ListIteratorOfListOfShape itLS(theLSRes);
1396     for (; itLS.More(); )
1397     {
1398       anExpF.Init(itLS.Value(), TopAbs_FACE);
1399       for (; anExpF.More(); anExpF.Next())
1400       {
1401         if (anOrigFacesRes.Contains(anExpF.Current()))
1402           break;
1403       }
1404       if (!anExpF.More())
1405       {
1406         theRemovedShapes.Append(itLS.Value());
1407         theLSRes.Remove(itLS);
1408       }
1409       else
1410         itLS.Next();
1411     }
1412   }
1413 }
1414
1415 //=======================================================================
1416 // function: FindExtraShape
1417 // purpose: Find shapes possibly filling the holes in the original shape
1418 //=======================================================================
1419 void FindExtraShapes(const TopTools_IndexedDataMapOfShapeListOfShape& theConnectionMap,
1420                      const TopTools_MapOfShape& theShapesToCheckOri,
1421                      BOPAlgo_Builder& theBuilder,
1422                      TopTools_MapOfShape& theShapesToAvoid,
1423                      TopTools_MapOfShape* theValidShapes)
1424 {
1425   Handle(IntTools_Context) aCtx = theBuilder.Context();
1426   TopTools_MapOfShape aValidShapes;
1427   TopTools_MapOfShape* pValidShapes = theValidShapes ? theValidShapes : &aValidShapes;
1428   TopTools_MapIteratorOfMapOfShape itM(theShapesToCheckOri);
1429   for (; itM.More(); itM.Next())
1430   {
1431     const TopoDS_Shape& aSToCheckOri = itM.Value();
1432     // Check modification of the shape during intersection
1433     TopTools_ListOfShape aLSIm;
1434     TakeModified(aSToCheckOri, theBuilder, aLSIm);
1435
1436     TopTools_ListIteratorOfListOfShape itLSIm(aLSIm);
1437     for (; itLSIm.More(); itLSIm.Next())
1438     {
1439       const TopoDS_Shape& aSIm = itLSIm.Value();
1440
1441       const TopTools_ListOfShape* pShapesToValidate = theConnectionMap.Seek(aSIm);
1442       if (!pShapesToValidate)
1443         continue;
1444
1445       TopTools_ListIteratorOfListOfShape itSV(*pShapesToValidate);
1446       for (; itSV.More(); itSV.Next())
1447       {
1448         const TopoDS_Shape& aShapeToValidate = itSV.Value();
1449         if (pValidShapes->Contains(aShapeToValidate))
1450           continue;
1451
1452         TopoDS_Face aSInShape;
1453         FindShape(aSIm, aShapeToValidate, aSInShape);
1454
1455         Standard_Boolean bSameOri =
1456           !BOPTools_AlgoTools::IsSplitToReverse(aSInShape, aSToCheckOri, aCtx);
1457
1458         if (bSameOri)
1459           pValidShapes->Add(aShapeToValidate);
1460         else
1461           theShapesToAvoid.Add(aShapeToValidate);
1462       }
1463     }
1464   }
1465
1466   itM.Initialize(*pValidShapes);
1467   for (; itM.More(); itM.Next())
1468     theShapesToAvoid.Remove(itM.Value());
1469 }
1470
1471 //=======================================================================
1472 // function: AvoidExtraSharedFaces
1473 // purpose: Looks for the extra faces splitting the solids
1474 //=======================================================================
1475 void AvoidExtraSharedFaces(TopTools_ListOfShape& theLSolids,
1476                            const TopTools_ListOfShape& theLFSharedToAvoid,
1477                            BOPAlgo_Builder& theBuilder,
1478                            TopTools_ListOfShape& theExtraFaces)
1479 {
1480   // Get all splits of shared faces to avoid in the check
1481   TopTools_MapOfShape aMFSharedSp;
1482   {
1483     TopTools_ListOfShape aLFSharedSp;
1484     TopTools_ListIteratorOfListOfShape itLFS(theLFSharedToAvoid);
1485     for (; itLFS.More(); itLFS.Next())
1486       TakeModified(itLFS.Value(), theBuilder, aMFSharedSp);
1487   }
1488
1489   TopTools_IndexedDataMapOfShapeListOfShape aFSMap;
1490   TopTools_ListIteratorOfListOfShape itLS(theLSolids);
1491   for (; itLS.More(); itLS.Next())
1492     TopExp::MapShapesAndAncestors(itLS.Value(), TopAbs_FACE, TopAbs_SOLID, aFSMap);
1493
1494   TopTools_ListOfShape anExtraFaces;
1495   TopTools_ListOfShape aLFArguments;
1496   itLS.Initialize(theLSolids);
1497   for (; itLS.More(); itLS.Next())
1498   {
1499     const TopoDS_Shape& aSol = itLS.Value();
1500     TopExp_Explorer anExpF(aSol, TopAbs_FACE);
1501     for (; anExpF.More(); anExpF.Next())
1502     {
1503       const TopoDS_Shape& aF = anExpF.Current();
1504       const TopTools_ListOfShape& aLSol = aFSMap.FindFromKey(aF);
1505       if (aLSol.Extent() != 2 || aMFSharedSp.Contains(aF))
1506         aLFArguments.Append(aF);
1507       else
1508         anExtraFaces.Append(aF);
1509     }
1510   }
1511
1512   if (anExtraFaces.IsEmpty())
1513     return;
1514
1515   // Rebuild the solids avoiding the extra faces
1516   BOPAlgo_BuilderSolid aBS;
1517   aBS.SetAvoidInternalShapes(Standard_True);
1518   aBS.SetShapes(aLFArguments);
1519   aBS.Perform();
1520   if (aBS.HasErrors())
1521     return;
1522
1523   theLSolids = aBS.Areas();
1524   theExtraFaces.Append(anExtraFaces);
1525 }
1526
1527 //=======================================================================
1528 // function: FillSolidsHistory
1529 // purpose: Fills the history of solids modifications
1530 //=======================================================================
1531 void FillSolidsHistory(const TopTools_IndexedMapOfShape& theSolIn,
1532                        TopTools_ListOfShape& theSolidsOut,
1533                        const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
1534                        BOPAlgo_Builder& theBuilder,
1535                        BRepTools_History& theSolidsHistory)
1536 {
1537   const Standard_Integer aNbS = theSolIn.Extent();
1538   for (Standard_Integer i = 1; i <= aNbS; ++i)
1539   {
1540     const TopoDS_Shape& aSolIn = theSolIn(i);
1541
1542     TopoDS_Shape aSolOut;
1543     FindSolid(aSolIn, theSolidsOut, theAdjFaces, theBuilder, aSolOut);
1544
1545     if (aSolOut.IsNull())
1546     {
1547       theSolidsHistory.Remove(aSolIn);
1548       continue;
1549     }
1550
1551     // Check if the solid has really been modified
1552     BOPTools_Set aSTIn, aSTOut;
1553     aSTIn.Add(aSolIn, TopAbs_FACE);
1554     aSTOut.Add(aSolOut, TopAbs_FACE);
1555     if (aSTIn.IsEqual(aSTOut))
1556     {
1557       // The solids are the same. Replace the resulting solid in the result list
1558       // with the initial solid.
1559       TopTools_ListIteratorOfListOfShape itLS(theSolidsOut);
1560       for (; itLS.More(); itLS.Next())
1561       {
1562         if (itLS.Value().IsSame(aSolOut))
1563         {
1564           theSolidsOut.InsertBefore(aSolIn, itLS);
1565           theSolidsOut.Remove(itLS);
1566           break;
1567         }
1568       }
1569     }
1570     else
1571     {
1572       theSolidsHistory.AddModified(aSolIn, aSolOut);
1573     }
1574   }
1575 }
1576
1577 //=======================================================================
1578 // function: TakeModified
1579 // purpose: Stores the modified object into the list
1580 //=======================================================================
1581 void TakeModified(const TopoDS_Shape& theS,
1582                   BOPAlgo_Builder& theBuilder,
1583                   TopTools_ListOfShape& theList)
1584 {
1585   const TopTools_ListOfShape& aModified = theBuilder.Modified(theS);
1586   if (aModified.IsEmpty() && !theBuilder.IsDeleted(theS))
1587     theList.Append(theS);
1588   else
1589   {
1590     TopTools_ListIteratorOfListOfShape itM(aModified);
1591     for (; itM.More(); itM.Next())
1592       theList.Append(itM.Value());
1593   }
1594 }
1595 //=======================================================================
1596 // function: TakeModified
1597 // purpose: Stores the modified object into the map
1598 //=======================================================================
1599 void TakeModified(const TopoDS_Shape& theS,
1600                   BOPAlgo_Builder& theBuilder,
1601                   TopTools_MapOfShape& theMap)
1602 {
1603   const TopTools_ListOfShape& aModified = theBuilder.Modified(theS);
1604   if (aModified.IsEmpty() && !theBuilder.IsDeleted(theS))
1605     theMap.Add(theS);
1606   else
1607   {
1608     TopTools_ListIteratorOfListOfShape itM(aModified);
1609     for (; itM.More(); itM.Next())
1610       theMap.Add(itM.Value());
1611   }
1612 }
1613
1614 //=======================================================================
1615 // function: FindSolid
1616 // purpose: Looks for the image of the solid in the list of resulting solids
1617 //=======================================================================
1618 void FindSolid(const TopoDS_Shape& theSolIn,
1619                const TopTools_ListOfShape& theSolidsRes,
1620                const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
1621                BOPAlgo_Builder& theBuilder,
1622                TopoDS_Shape& theSolOut)
1623 {
1624   Handle(IntTools_Context) aCtx = theBuilder.Context();
1625
1626   // Take the face in the IN solid, and find it in the OUT list
1627   TopExp_Explorer anExpF(theSolIn, TopAbs_FACE);
1628   for (; anExpF.More(); anExpF.Next())
1629   {
1630     const TopoDS_Shape& aFS = anExpF.Current();
1631     // Images of the face
1632     TopTools_MapOfShape aMFSIm;
1633     const TopTools_ListOfShape* pLFA = theAdjFaces.Seek(aFS);
1634     if (pLFA)
1635     {
1636       TopTools_ListIteratorOfListOfShape itLFA(*pLFA);
1637       for (; itLFA.More(); itLFA.Next())
1638         TakeModified(itLFA.Value(), theBuilder, aMFSIm);
1639     }
1640     else
1641     {
1642       TakeModified(aFS, theBuilder, aMFSIm);
1643     }
1644
1645     // Find any of these faces in the list of solids
1646     TopTools_ListIteratorOfListOfShape itLS(theSolidsRes);
1647     for (; itLS.More(); itLS.Next())
1648     {
1649       const TopoDS_Shape& aSol = itLS.Value();
1650       TopExp_Explorer anExpFOut(aSol, TopAbs_FACE);
1651       for (; anExpFOut.More(); anExpFOut.Next())
1652       {
1653         const TopoDS_Shape& aF = anExpFOut.Current();
1654         if (aMFSIm.Contains(aF))
1655         {
1656           // check orientations
1657           if (!BOPTools_AlgoTools::IsSplitToReverse(aF, aFS, aCtx))
1658           {
1659             theSolOut = aSol;
1660             return;
1661           }
1662         }
1663       }
1664     }
1665   }
1666 }