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     BOPAlgo_Tools::TreatCompound(myInputShape, aMFence, aShapes);
 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 typedef BOPTools_Functor <FillGap, VectorOfFillGap> FillGapFunctor;
 720
 721 typedef BOPTools_Cnt <FillGapFunctor, VectorOfFillGap> FillGapCnt;
 722
 723 //=======================================================================
 724
 725 //=======================================================================
 726 // function: RemoveFeatures
 727 // purpose: Remove features by filling the gaps by extension of the
 728 //          adjacent faces
 729 //=======================================================================
 730 void BOPAlgo_RemoveFeatures::RemoveFeatures()
 731 {
 732   // For each feature:
 733   // - Find the faces adjacent to the feature;
 734   // - Extend the adjacent faces;
 735   // - Trim the extended faces to fill the gap;
 736   // - Rebuild the solids with reconstructed adjacent faces
 737   //   and avoiding the feature faces.
 738
 739   // Make Edge-Face connection map of the input
 740   // shape to find faces adjacent to the feature
 741   TopTools_IndexedDataMapOfShapeListOfShape anEFMap;
 742   TopExp::MapShapesAndAncestors(myInputShape, TopAbs_EDGE, TopAbs_FACE, anEFMap);
 743
 744   // Make Face-Solid connection map to find the solids
 745   // participating in the removal of each feature
 746   TopTools_IndexedDataMapOfShapeListOfShape anFSMap;
 747   TopExp::MapShapesAndAncestors(myInputShape, TopAbs_FACE, TopAbs_SOLID, anFSMap);
 748
 749   // Tool for reconstruction of the faces adjacent to the feature
 750   // in parallel threads if necessary.
 751   VectorOfFillGap aVFG;
 752   // Fill the vector
 753   TopTools_ListIteratorOfListOfShape itF(myFeatures);
 754   for (; itF.More(); itF.Next())
 755   {
 756     const TopoDS_Shape& aFeature = itF.Value();
 757     FillGap& aFG = aVFG.Appended();
 758     aFG.SetFeature(aFeature);
 759     aFG.SetEFConnectionMap(anEFMap);
 760     aFG.SetFSConnectionMap(anFSMap);
 761     aFG.SetRunParallel(myRunParallel);
 762   }
 763
 764   // Perform the reconstruction of the adjacent faces
 765   FillGapCnt::Perform(myRunParallel, aVFG);
 766
 767   // Even if the history is not requested, it is necessary to track:
 768   // - The solids modification after each feature removal to find
 769   //   the necessary solids to rebuild on the next step.
 770   // - The faces modification after each feature removal to find the
 771   //   splits of the adjacent and feature faces for the next steps.
 772   if (myHistory.IsNull())
 773     myHistory = new BRepTools_History();
 774
 775   // Remove the features one by one.
 776   // It will allow removing the features even if there were
 777   // some problems with removal of the previous features.
 778   const Standard_Integer aNbF = aVFG.Length();
 779   for (Standard_Integer i = 0; i < aNbF; ++i)
 780   {
 781     FillGap& aFG = aVFG(i);
 782
 783     // No need to fill the history for solids if the history is not
 784     // requested and the current feature is the last one.
 785     Standard_Boolean isSolidsHistoryNeeded = HasHistory() || (i < (aNbF - 1));
 786
 787     // Perform removal of the single feature
 788     RemoveFeature(aFG.Feature(), aFG.Solids(), aFG.FeatureFacesMap(),
 789                   aFG.HasAdjacentFaces(), aFG.Faces(), aFG.History(),
 790                   isSolidsHistoryNeeded);
 791   }
 792 }
 793
 794 //=======================================================================
 795 // function: RemoveFeature
 796 // purpose: Remove the single feature
 797 //=======================================================================
 798 void BOPAlgo_RemoveFeatures::RemoveFeature
 799   (const TopoDS_Shape& theFeature,
 800    const TopTools_IndexedMapOfShape& theSolids,
 801    const TopTools_MapOfShape& theFeatureFacesMap,
 802    const Standard_Boolean theHasAdjacentFaces,
 803    const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
 804    const Handle(BRepTools_History)& theAdjFacesHistory,
 805    const Standard_Boolean theSolidsHistoryNeeded)
 806 {
 807   Standard_Boolean bFuseShapes = Standard_True;
 808   const Standard_Integer aNbAF = theAdjFaces.Extent();
 809   if (aNbAF == 0)
 810   {
 811     if (theHasAdjacentFaces)
 812     {
 813       // The adjacent faces have been found for the feature,
 814       // but something went wrong during their rebuilding.
 815       // Add error
 816       AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 817       return;
 818     }
 819
 820     // No adjacent faces have been found for the feature.
 821     // Most likely, the intention is to remove some internal part of the shape.
 822     // We just have to rebuild the shape without the feature, no fuse is necessary.
 823     bFuseShapes = Standard_False;
 824   }
 825
 826   // Rebuild the shape using MakerVolume algorithm avoiding the faces of the
 827   // feature and replacing the adjacent faces with their images
 828
 829   BRep_Builder aBB;
 830
 831   // From the faces of input shape build map of faces with which the result will be validated:
 832   // - all non-internal faces of the input shape (except for adjacent and feature faces)
 833   //   must have some trace in the result solids;
 834   // - all adjacent faces (if any) must have some trace in the result solids.
 835   TopTools_IndexedMapOfShape aFacesToBeKept;
 836   // Build also the map of faces to compare orientation of the original and result faces
 837   TopTools_MapOfShape aFacesToCheckOri;
 838
 839   // Collect list of internal entities of the input shape to be avoided in result
 840   // and to make them removed in the history.
 841   TopTools_ListOfShape anInternalShapes;
 842
 843   // In the feature removal will participate only the solids connected to the feature
 844   // or the faces adjacent to the feature.
 845
 846   // Solids to be rebuilt  after the feature removal
 847   TopTools_IndexedMapOfShape aSolidsToRebuild;
 848   // Find faces shared between solids
 849   TopTools_ListOfShape aSharedFaces;
 850   // Solids to be avoided in the feature removal and added into result directly
 851   TopTools_ListOfShape anUnTouchedSolids;
 852
 853   // Prepare to the feature removal - fill all necessary containers
 854   GetOriginalFaces(myShape, theSolids, theFeatureFacesMap, theAdjFaces, myHistory,
 855                    aFacesToBeKept, anInternalShapes, aFacesToCheckOri,
 856                    aSolidsToRebuild, aSharedFaces, anUnTouchedSolids);
 857
 858   // To avoid excessive intersection of the faces collect the faces
 859   // of the input shape into a compound
 860   TopoDS_Compound anOrigF;
 861   aBB.MakeCompound(anOrigF);
 862   Standard_Integer aNbFK = aFacesToBeKept.Extent();
 863   for (Standard_Integer i = 1; i <= aNbFK; ++i)
 864     aBB.Add(anOrigF, aFacesToBeKept(i));
 865
 866   // Tool for solids reconstruction
 867   BOPAlgo_MakerVolume aMV;
 868   aMV.SetRunParallel(myRunParallel);
 869   aMV.SetAvoidInternalShapes(Standard_True);
 870   aMV.SetIntersect(bFuseShapes);
 871   aMV.SetNonDestructive(Standard_True);
 872   // Add faces of the input shape
 873   aMV.AddArgument(anOrigF);
 874
 875   // Add reconstructed adjacent faces
 876   for (Standard_Integer i = 1; i <= aNbAF; ++i)
 877   {
 878     const TopTools_ListOfShape& aLFA = theAdjFaces(i);
 879     if (aLFA.Extent() == 1)
 880     {
 881       const TopoDS_Shape& aFA = aLFA.First();
 882       aMV.AddArgument(aFA);
 883       aFacesToBeKept.Add(aFA);
 884     }
 885     else
 886     {
 887       // To avoid intersection among the images, collect them into compound
 888       TopoDS_Compound anAdjF;
 889       aBB.MakeCompound(anAdjF);
 890       TopTools_ListIteratorOfListOfShape itLFA(aLFA);
 891       for (; itLFA.More(); itLFA.Next())
 892         aBB.Add(anAdjF, itLFA.Value());
 893
 894       aMV.AddArgument(anAdjF);
 895       aFacesToBeKept.Add(anAdjF);
 896     }
 897
 898     if (HasHistory())
 899     {
 900       // Look for internal edges in the original adjacent faces
 901       const TopoDS_Shape& aFOr = theAdjFaces.FindKey(i);
 902       FindInternals(aFOr, anInternalShapes);
 903     }
 904   }
 905
 906   // Build solids
 907   aMV.Perform();
 908   if (aMV.HasErrors())
 909   {
 910     // Add warning for the feature
 911     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 912     return;
 913   }
 914
 915   // Result of MV operation
 916   const TopoDS_Shape& aSolids = aMV.Shape();
 917   TopExp_Explorer anExpS(aSolids, TopAbs_SOLID);
 918   if (!anExpS.More())
 919   {
 920     // No solids have been built - add warning for the feature
 921     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 922     return;
 923   }
 924
 925   // Now, it is necessary to:
 926   // - Validate the result by checking faces of the map <aFacesToBeKept>
 927   //   to have some parts kept in the resulting solids;
 928   // - Remove the solids possibly filling the holes in the original shapes;
 929   // - Update history with the history of MakerVolume algorithm.
 930
 931   // Splits of adjacent faces from previous runs
 932   TopTools_MapOfShape anAdjFacesSplits;
 933   for (Standard_Integer i = 1; i <= aNbAF; ++i)
 934   {
 935     const TopoDS_Shape& aF = theAdjFaces.FindKey(i);
 936     const TopTools_ListOfShape& aLFIm = myHistory->Modified(aF);
 937     if (aLFIm.IsEmpty())
 938       anAdjFacesSplits.Add(aF);
 939     else
 940     {
 941       TopTools_ListIteratorOfListOfShape itLFIm(aLFIm);
 942       for (; itLFIm.More(); itLFIm.Next())
 943         anAdjFacesSplits.Add(itLFIm.Value());
 944     }
 945   }
 946
 947   // Validate the result
 948   Standard_Boolean bValid = Standard_True;
 949   aNbFK = aFacesToBeKept.Extent();
 950   for (Standard_Integer i = 1; i <= aNbFK && bValid; ++i)
 951   {
 952     const TopoDS_Shape& aS = aFacesToBeKept(i);
 953     if (anAdjFacesSplits.Contains(aS))
 954       continue;
 955     TopExp_Explorer anExpF(aS, TopAbs_FACE);
 956     for (; anExpF.More(); anExpF.Next())
 957     {
 958       const TopoDS_Shape& aF = anExpF.Current();
 959       if (!aMV.IsDeleted(aF))
 960         break;
 961     }
 962     bValid = anExpF.More();
 963   }
 964
 965   if (!bValid)
 966   {
 967     // Add warning for the feature
 968     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 969     return;
 970   }
 971
 972   // It is possible that the result of MakerVolume operation contains
 973   // some extra solids. Get only correct solids.
 974   TopTools_ListOfShape aLSRes;
 975   // Remember the removed shapes
 976   TopTools_ListOfShape aRemovedShapes;
 977   GetValidSolids(aMV, aFacesToCheckOri, aSharedFaces, anOrigF, theSolids.Extent(), aLSRes, aRemovedShapes);
 978
 979   if (aLSRes.Extent() != theSolids.Extent())
 980   {
 981     // Add warning for the feature
 982     AddWarning(new BOPAlgo_AlertUnableToRemoveTheFeature(theFeature));
 983     return;
 984   }
 985
 986   // Remove internal wires from the faces, possibly appeared after intersection
 987   RemoveInternalWires(aLSRes, &anInternalShapes);
 988
 989   // Update history with:
 990   // History of adjacent faces reconstruction
 991   myHistory->Merge(theAdjFacesHistory);
 992   // History of intersection
 993   myHistory->Merge(aMV.History());
 994
 995   if (HasHistory())
 996   {
 997     // Map the result to check if the shape is removed
 998     TopTools_IndexedMapOfShape aMSRes;
 999     TopTools_ListIteratorOfListOfShape itLS(aLSRes);
1000     for (; itLS.More(); itLS.Next())
1001       TopExp::MapShapes(itLS.Value(), aMSRes);
1002
1003     // Remove internal shapes and extra faces
1004     BRepTools_History aRemHist;
1005     anInternalShapes.Append(aRemovedShapes);
1006     MakeRemoved(anInternalShapes, aRemHist, aMSRes);
1007     myHistory->Merge(aRemHist);
1008   }
1009
1010   // Fill the history for the solids
1011   if (theSolidsHistoryNeeded)
1012   {
1013     BRepTools_History aSolidsHistory;
1014     FillSolidsHistory(aSolidsToRebuild, aLSRes, theAdjFaces, aMV, aSolidsHistory);
1015     myHistory->Merge(aSolidsHistory);
1016   }
1017
1018   TopoDS_Compound aCRes;
1019   aBB.MakeCompound(aCRes);
1020   // Add reconstructed solids
1021   TopTools_ListIteratorOfListOfShape itLS(aLSRes);
1022   for (; itLS.More(); itLS.Next())
1023     aBB.Add(aCRes, itLS.Value());
1024
1025   // Add unmodified solids
1026   itLS.Initialize(anUnTouchedSolids);
1027   for (; itLS.More(); itLS.Next())
1028     aBB.Add(aCRes, itLS.Value());
1029
1030   // Save the result
1031   myShape = aCRes;
1032 }
1033
1034 //=======================================================================
1035 // function: UpdateHistory
1036 // purpose: Update history with the removed features
1037 //=======================================================================
1038 void BOPAlgo_RemoveFeatures::UpdateHistory()
1039 {
1040   if (!HasHistory())
1041     return;
1042
1043   // Map the result
1044   myMapShape.Clear();
1045   TopExp::MapShapes(myShape, myMapShape);
1046
1047   // Update the history
1048   BRepTools_History aHistory;
1049
1050   const Standard_Integer aNbS = myInputsMap.Extent();
1051   for (Standard_Integer i = 1; i <= aNbS; ++i)
1052   {
1053     const TopoDS_Shape& aS = myInputsMap(i);
1054     if (!BRepTools_History::IsSupportedType(aS))
1055       continue;
1056
1057     if (myHistory->IsRemoved(aS))
1058       continue;
1059
1060     // Check if the shape has any trace in the result
1061     const TopTools_ListOfShape& aLSIm = myHistory->Modified(aS);
1062     if (aLSIm.IsEmpty())
1063     {
1064       if (!myMapShape.Contains(aS))
1065         aHistory.Remove(aS);
1066     }
1067
1068     TopTools_ListIteratorOfListOfShape itLSIm(aLSIm);
1069     for (; itLSIm.More(); itLSIm.Next())
1070     {
1071       if (!myMapShape.Contains(itLSIm.Value()))
1072         aHistory.Remove(itLSIm.Value());
1073     }
1074   }
1075
1076   myHistory->Merge(aHistory);
1077 }
1078
1079 //=======================================================================
1080 // function: SimplifyResult
1081 // purpose: Simplifies the result by removing extra edges and vertices
1082 //          created during operation
1083 //=======================================================================
1084 void BOPAlgo_RemoveFeatures::SimplifyResult()
1085 {
1086   if (myShape.IsSame(myInputShape))
1087     return;
1088   ShapeUpgrade_UnifySameDomain aSDTool;
1089   aSDTool.Initialize(myShape, Standard_True, Standard_True);
1090   // Do not allow producing internal edges
1091   aSDTool.AllowInternalEdges(Standard_False);
1092   // Avoid removal of the input edges and vertices
1093   if (myMapShape.IsEmpty())
1094     TopExp::MapShapes(myShape, myMapShape);
1095
1096   const Standard_Integer aNbS = myInputsMap.Extent();
1097   for (Standard_Integer i = 1; i <= aNbS; ++i)
1098   {
1099     if (myMapShape.Contains(myInputsMap(i)))
1100       aSDTool.KeepShape(myInputsMap(i));
1101   }
1102
1103   // Perform unification
1104   aSDTool.Build();
1105   myShape = aSDTool.Shape();
1106   if (HasHistory())
1107     myHistory->Merge(aSDTool.History());
1108 }
1109
1110 //=======================================================================
1111 // function: PostTreat
1112 // purpose: Restore the type of the initial shape
1113 //=======================================================================
1114 void BOPAlgo_RemoveFeatures::PostTreat()
1115 {
1116   const TopAbs_ShapeEnum anInputType = myInputShape.ShapeType();
1117   const TopAbs_ShapeEnum aResType = myShape.ShapeType();
1118   if (aResType == anInputType)
1119     return;
1120
1121   TopExp_Explorer anExpS(myShape, TopAbs_SOLID);
1122
1123   if (anInputType == TopAbs_SOLID)
1124   {
1125     myShape = anExpS.Current();
1126     return;
1127   }
1128
1129   TopoDS_Shape aRes;
1130   if (anInputType == TopAbs_COMPOUND)
1131     BRep_Builder().MakeCompound(TopoDS::Compound(aRes));
1132   else
1133     BRep_Builder().MakeCompSolid(TopoDS::CompSolid(aRes));
1134
1135   for (; anExpS.More(); anExpS.Next())
1136     BRep_Builder().Add(aRes, anExpS.Current());
1137
1138   myShape = aRes;
1139 }
1140
1141 //=======================================================================
1142 // static methods definition
1143 //=======================================================================
1144
1145 //=======================================================================
1146 // function: MakeRemoved
1147 // purpose: Makes the shapes in the list removed in the history.
1148 //          Keeps the shapes contained in the map.
1149 //=======================================================================
1150 void MakeRemoved(const TopTools_ListOfShape& theShapes,
1151                  BRepTools_History& theHistory,
1152                  const TopTools_IndexedMapOfShape& theKeepShapes)
1153 {
1154   TopTools_IndexedMapOfShape aShapesMap;
1155   TopTools_ListIteratorOfListOfShape it(theShapes);
1156   for (; it.More(); it.Next())
1157     TopExp::MapShapes(it.Value(), aShapesMap);
1158
1159   const Standard_Integer aNbS = aShapesMap.Extent();
1160   for (Standard_Integer i = 1; i <= aNbS; ++i)
1161   {
1162     const TopoDS_Shape& aS = aShapesMap(i);
1163     if (!theKeepShapes.Contains(aS) &&
1164         BRepTools_History::IsSupportedType(aS))
1165     {
1166       theHistory.Remove(aS);
1167     }
1168   }
1169 }
1170
1171 //=======================================================================
1172 // function: FindInternals
1173 // purpose: Looks for internal shapes inside the face or solid
1174 //=======================================================================
1175 void FindInternals(const TopoDS_Shape& theS,
1176                    TopTools_ListOfShape& theLInt)
1177 {
1178   TopoDS_Iterator itS(theS);
1179   for (; itS.More(); itS.Next())
1180   {
1181     const TopoDS_Shape& aSS = itS.Value();
1182     if (aSS.Orientation() == TopAbs_INTERNAL)
1183       theLInt.Append(aSS);
1184     else
1185     {
1186       TopoDS_Iterator itSS(aSS);
1187       for (; itSS.More(); itSS.Next())
1188       {
1189         if (itSS.Value().Orientation() == TopAbs_INTERNAL)
1190         {
1191           theLInt.Append(aSS);
1192           break;
1193         }
1194       }
1195     }
1196   }
1197 }
1198
1199 //=======================================================================
1200 // function: RemoveInternalWires
1201 // purpose: Removes internal wires from the faces
1202 //=======================================================================
1203 void RemoveInternalWires(const TopTools_ListOfShape& theShapes,
1204                          TopTools_ListOfShape *theRemoved)
1205 {
1206   TopTools_ListIteratorOfListOfShape itLS(theShapes);
1207   for (; itLS.More(); itLS.Next())
1208   {
1209     const TopoDS_Shape& aShape = itLS.Value();
1210     TopExp_Explorer anExpF(aShape, TopAbs_FACE);
1211     for (; anExpF.More(); anExpF.Next())
1212     {
1213       TopoDS_Face& aF = *(TopoDS_Face*)&anExpF.Current();
1214       TopTools_ListOfShape aLWToRemove;
1215       FindInternals(aF, aLWToRemove);
1216       if (aLWToRemove.Extent())
1217       {
1218         aF.Free(Standard_True);
1219         TopTools_ListIteratorOfListOfShape itR(aLWToRemove);
1220         for (; itR.More(); itR.Next())
1221         {
1222           if (theRemoved)
1223             theRemoved->Append(itR.Value());
1224           BRep_Builder().Remove(aF, itR.Value());
1225         }
1226         aF.Free(Standard_False);
1227       }
1228     }
1229   }
1230 }
1231
1232 //=======================================================================
1233 // function: GetOriginalFaces
1234 // purpose: Get original faces from my face
1235 //=======================================================================
1236 void GetOriginalFaces(const TopoDS_Shape& theShape,
1237                       const TopTools_IndexedMapOfShape& theSolids,
1238                       const TopTools_MapOfShape& theFeatureFacesMap,
1239                       const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
1240                       const Handle(BRepTools_History)& theHistory,
1241                       TopTools_IndexedMapOfShape& theFacesToBeKept,
1242                       TopTools_ListOfShape& theInternalShapes,
1243                       TopTools_MapOfShape& theFacesToCheckOri,
1244                       TopTools_IndexedMapOfShape& theSolidsToRebuild,
1245                       TopTools_ListOfShape& theSharedFaces,
1246                       TopTools_ListOfShape& theUnTouchedSolids)
1247 {
1248   // Use only solids which has to be reconstructed by the feature.
1249   // All other solids should be avoided in the feature removal and added
1250   // into result directly.
1251
1252   // Update solids after removal of previous features
1253   const Standard_Integer aNbSols = theSolids.Extent();
1254   for (Standard_Integer i = 1; i <= aNbSols; ++i)
1255   {
1256     const TopoDS_Shape& aSol = theSolids(i);
1257     const TopTools_ListOfShape& aLFIm = theHistory->Modified(aSol);
1258     if (aLFIm.IsEmpty())
1259       theSolidsToRebuild.Add(aSol);
1260     else
1261       theSolidsToRebuild.Add(aLFIm.First());
1262   }
1263
1264   // Splits of the feature faces
1265   TopTools_MapOfShape aFeatureFacesSplits;
1266   TopTools_MapIteratorOfMapOfShape itM(theFeatureFacesMap);
1267   for (; itM.More(); itM.Next())
1268   {
1269     const TopoDS_Shape& aF = itM.Value();
1270     const TopTools_ListOfShape& aLFIm = theHistory->Modified(aF);
1271     if (aLFIm.IsEmpty())
1272       aFeatureFacesSplits.Add(aF);
1273     else
1274     {
1275       TopTools_ListIteratorOfListOfShape itLFIm(aLFIm);
1276       for (; itLFIm.More(); itLFIm.Next())
1277         aFeatureFacesSplits.Add(itLFIm.Value());
1278     }
1279   }
1280
1281   TopExp_Explorer anExpS(theShape, TopAbs_SOLID);
1282   for (; anExpS.More(); anExpS.Next())
1283   {
1284     const TopoDS_Shape& aSol = anExpS.Current();
1285
1286     // Check if the solid has to be reconstructed
1287     if (!theSolidsToRebuild.Contains(aSol))
1288     {
1289       // untouched solid
1290       theUnTouchedSolids.Append(aSol);
1291       continue;
1292     }
1293
1294     TopoDS_Iterator itSh(aSol);
1295     for (; itSh.More(); itSh.Next())
1296     {
1297       const TopoDS_Shape& aSh = itSh.Value();
1298       if (aSh.ShapeType() != TopAbs_SHELL)
1299       {
1300         theInternalShapes.Append(aSh);
1301         continue;
1302       }
1303
1304       TopoDS_Iterator itF(aSh);
1305       for (; itF.More(); itF.Next())
1306       {
1307         const TopoDS_Shape& aF = itF.Value();
1308         // Avoid the feature faces
1309         if (aFeatureFacesSplits.Contains(aF))
1310           continue;
1311
1312         // Avoid the adjacent faces
1313         if (theAdjFaces.Contains(aF))
1314           continue;
1315
1316         if (aF.Orientation() != TopAbs_INTERNAL)
1317         {
1318           theFacesToBeKept.Add(aF);
1319
1320           if (!theFacesToCheckOri.Add(aF))
1321           {
1322             theFacesToCheckOri.Remove(aF);
1323             theSharedFaces.Append(aF);
1324           }
1325         }
1326         else
1327           theInternalShapes.Append(aSh);
1328       }
1329     }
1330   }
1331 }
1332
1333 //=======================================================================
1334 // function: FindShape
1335 // purpose: Find the shape in the other shape
1336 //=======================================================================
1337 void FindShape(const TopoDS_Shape& theSWhat,
1338                const TopoDS_Shape& theSWhere,
1339                TopoDS_Shape& theSFound)
1340 {
1341   TopExp_Explorer anExp(theSWhere, theSWhat.ShapeType());
1342   for (; anExp.More(); anExp.Next())
1343   {
1344     const TopoDS_Shape& aS = anExp.Current();
1345     if (aS.IsSame(theSWhat))
1346     {
1347       theSFound = aS;
1348       break;
1349     }
1350   }
1351 }
1352
1353 //=======================================================================
1354 // function: GetValidSolids
1355 // purpose: Checks the validity of the solids and keeps only valid ones
1356 //=======================================================================
1357 void GetValidSolids(BOPAlgo_MakerVolume& theMV,
1358                     const TopTools_MapOfShape& theFacesToCheckOri,
1359                     const TopTools_ListOfShape& aSharedFaces,
1360                     const TopoDS_Shape& theOrigFaces,
1361                     const Standard_Integer theNbSol,
1362                     TopTools_ListOfShape& theLSRes,
1363                     TopTools_ListOfShape& theRemovedShapes)
1364 {
1365   TopExp_Explorer anExpS(theMV.Shape(), TopAbs_SOLID);
1366   for (; anExpS.More(); anExpS.Next())
1367     theLSRes.Append(anExpS.Current());
1368
1369   if (theLSRes.Extent() > theNbSol)
1370   {
1371     // Find Solids filling the holes in the initial shape
1372     TopTools_MapOfShape aSolidsToAvoid;
1373     TopTools_IndexedDataMapOfShapeListOfShape aFSMap;
1374     TopExp::MapShapesAndAncestors(theMV.Shape(), TopAbs_FACE, TopAbs_SOLID, aFSMap);
1375     FindExtraShapes(aFSMap, theFacesToCheckOri, theMV, aSolidsToAvoid);
1376
1377     TopTools_ListIteratorOfListOfShape itLS(theLSRes);
1378     for (; itLS.More(); )
1379     {
1380       if (aSolidsToAvoid.Contains(itLS.Value()))
1381         theLSRes.Remove(itLS);
1382       else
1383         itLS.Next();
1384     }
1385   }
1386
1387   if (theLSRes.Extent() > theNbSol)
1388   {
1389     // Check if the splits of the adjacent faces split the solids
1390     AvoidExtraSharedFaces(theLSRes, aSharedFaces, theMV, theRemovedShapes);
1391   }
1392
1393   if (theLSRes.Extent() > theNbSol)
1394   {
1395     // Remove solids containing only the adjacent faces
1396     TopTools_MapOfShape anOrigFacesRes;
1397     TopExp_Explorer anExpF(theOrigFaces, TopAbs_FACE);
1398     for (; anExpF.More(); anExpF.Next())
1399       TakeModified(anExpF.Current(), theMV, anOrigFacesRes);
1400
1401     TopTools_ListIteratorOfListOfShape itLS(theLSRes);
1402     for (; itLS.More(); )
1403     {
1404       anExpF.Init(itLS.Value(), TopAbs_FACE);
1405       for (; anExpF.More(); anExpF.Next())
1406       {
1407         if (anOrigFacesRes.Contains(anExpF.Current()))
1408           break;
1409       }
1410       if (!anExpF.More())
1411       {
1412         theRemovedShapes.Append(itLS.Value());
1413         theLSRes.Remove(itLS);
1414       }
1415       else
1416         itLS.Next();
1417     }
1418   }
1419 }
1420
1421 //=======================================================================
1422 // function: FindExtraShape
1423 // purpose: Find shapes possibly filling the holes in the original shape
1424 //=======================================================================
1425 void FindExtraShapes(const TopTools_IndexedDataMapOfShapeListOfShape& theConnectionMap,
1426                      const TopTools_MapOfShape& theShapesToCheckOri,
1427                      BOPAlgo_Builder& theBuilder,
1428                      TopTools_MapOfShape& theShapesToAvoid,
1429                      TopTools_MapOfShape* theValidShapes)
1430 {
1431   Handle(IntTools_Context) aCtx = theBuilder.Context();
1432   TopTools_MapOfShape aValidShapes;
1433   TopTools_MapOfShape* pValidShapes = theValidShapes ? theValidShapes : &aValidShapes;
1434   TopTools_MapIteratorOfMapOfShape itM(theShapesToCheckOri);
1435   for (; itM.More(); itM.Next())
1436   {
1437     const TopoDS_Shape& aSToCheckOri = itM.Value();
1438     // Check modification of the shape during intersection
1439     TopTools_ListOfShape aLSIm;
1440     TakeModified(aSToCheckOri, theBuilder, aLSIm);
1441
1442     TopTools_ListIteratorOfListOfShape itLSIm(aLSIm);
1443     for (; itLSIm.More(); itLSIm.Next())
1444     {
1445       const TopoDS_Shape& aSIm = itLSIm.Value();
1446
1447       const TopTools_ListOfShape* pShapesToValidate = theConnectionMap.Seek(aSIm);
1448       if (!pShapesToValidate)
1449         continue;
1450
1451       TopTools_ListIteratorOfListOfShape itSV(*pShapesToValidate);
1452       for (; itSV.More(); itSV.Next())
1453       {
1454         const TopoDS_Shape& aShapeToValidate = itSV.Value();
1455         if (pValidShapes->Contains(aShapeToValidate))
1456           continue;
1457
1458         TopoDS_Face aSInShape;
1459         FindShape(aSIm, aShapeToValidate, aSInShape);
1460
1461         Standard_Boolean bSameOri =
1462           !BOPTools_AlgoTools::IsSplitToReverse(aSInShape, aSToCheckOri, aCtx);
1463
1464         if (bSameOri)
1465           pValidShapes->Add(aShapeToValidate);
1466         else
1467           theShapesToAvoid.Add(aShapeToValidate);
1468       }
1469     }
1470   }
1471
1472   itM.Initialize(*pValidShapes);
1473   for (; itM.More(); itM.Next())
1474     theShapesToAvoid.Remove(itM.Value());
1475 }
1476
1477 //=======================================================================
1478 // function: AvoidExtraSharedFaces
1479 // purpose: Looks for the extra faces splitting the solids
1480 //=======================================================================
1481 void AvoidExtraSharedFaces(TopTools_ListOfShape& theLSolids,
1482                            const TopTools_ListOfShape& theLFSharedToAvoid,
1483                            BOPAlgo_Builder& theBuilder,
1484                            TopTools_ListOfShape& theExtraFaces)
1485 {
1486   // Get all splits of shared faces to avoid in the check
1487   TopTools_MapOfShape aMFSharedSp;
1488   {
1489     TopTools_ListOfShape aLFSharedSp;
1490     TopTools_ListIteratorOfListOfShape itLFS(theLFSharedToAvoid);
1491     for (; itLFS.More(); itLFS.Next())
1492       TakeModified(itLFS.Value(), theBuilder, aMFSharedSp);
1493   }
1494
1495   TopTools_IndexedDataMapOfShapeListOfShape aFSMap;
1496   TopTools_ListIteratorOfListOfShape itLS(theLSolids);
1497   for (; itLS.More(); itLS.Next())
1498     TopExp::MapShapesAndAncestors(itLS.Value(), TopAbs_FACE, TopAbs_SOLID, aFSMap);
1499
1500   TopTools_ListOfShape anExtraFaces;
1501   TopTools_ListOfShape aLFArguments;
1502   itLS.Initialize(theLSolids);
1503   for (; itLS.More(); itLS.Next())
1504   {
1505     const TopoDS_Shape& aSol = itLS.Value();
1506     TopExp_Explorer anExpF(aSol, TopAbs_FACE);
1507     for (; anExpF.More(); anExpF.Next())
1508     {
1509       const TopoDS_Shape& aF = anExpF.Current();
1510       const TopTools_ListOfShape& aLSol = aFSMap.FindFromKey(aF);
1511       if (aLSol.Extent() != 2 || aMFSharedSp.Contains(aF))
1512         aLFArguments.Append(aF);
1513       else
1514         anExtraFaces.Append(aF);
1515     }
1516   }
1517
1518   if (anExtraFaces.IsEmpty())
1519     return;
1520
1521   // Rebuild the solids avoiding the extra faces
1522   BOPAlgo_BuilderSolid aBS;
1523   aBS.SetAvoidInternalShapes(Standard_True);
1524   aBS.SetShapes(aLFArguments);
1525   aBS.Perform();
1526   if (aBS.HasErrors())
1527     return;
1528
1529   theLSolids = aBS.Areas();
1530   theExtraFaces.Append(anExtraFaces);
1531 }
1532
1533 //=======================================================================
1534 // function: FillSolidsHistory
1535 // purpose: Fills the history of solids modifications
1536 //=======================================================================
1537 void FillSolidsHistory(const TopTools_IndexedMapOfShape& theSolIn,
1538                        TopTools_ListOfShape& theSolidsOut,
1539                        const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
1540                        BOPAlgo_Builder& theBuilder,
1541                        BRepTools_History& theSolidsHistory)
1542 {
1543   const Standard_Integer aNbS = theSolIn.Extent();
1544   for (Standard_Integer i = 1; i <= aNbS; ++i)
1545   {
1546     const TopoDS_Shape& aSolIn = theSolIn(i);
1547
1548     TopoDS_Shape aSolOut;
1549     FindSolid(aSolIn, theSolidsOut, theAdjFaces, theBuilder, aSolOut);
1550
1551     if (aSolOut.IsNull())
1552     {
1553       theSolidsHistory.Remove(aSolIn);
1554       continue;
1555     }
1556
1557     // Check if the solid has really been modified
1558     BOPTools_Set aSTIn, aSTOut;
1559     aSTIn.Add(aSolIn, TopAbs_FACE);
1560     aSTOut.Add(aSolOut, TopAbs_FACE);
1561     if (aSTIn.IsEqual(aSTOut))
1562     {
1563       // The solids are the same. Replace the resulting solid in the result list
1564       // with the initial solid.
1565       TopTools_ListIteratorOfListOfShape itLS(theSolidsOut);
1566       for (; itLS.More(); itLS.Next())
1567       {
1568         if (itLS.Value().IsSame(aSolOut))
1569         {
1570           theSolidsOut.InsertBefore(aSolIn, itLS);
1571           theSolidsOut.Remove(itLS);
1572           break;
1573         }
1574       }
1575     }
1576     else
1577     {
1578       theSolidsHistory.AddModified(aSolIn, aSolOut);
1579     }
1580   }
1581 }
1582
1583 //=======================================================================
1584 // function: TakeModified
1585 // purpose: Stores the modified object into the list
1586 //=======================================================================
1587 void TakeModified(const TopoDS_Shape& theS,
1588                   BOPAlgo_Builder& theBuilder,
1589                   TopTools_ListOfShape& theList)
1590 {
1591   const TopTools_ListOfShape& aModified = theBuilder.Modified(theS);
1592   if (aModified.IsEmpty() && !theBuilder.IsDeleted(theS))
1593     theList.Append(theS);
1594   else
1595   {
1596     TopTools_ListIteratorOfListOfShape itM(aModified);
1597     for (; itM.More(); itM.Next())
1598       theList.Append(itM.Value());
1599   }
1600 }
1601 //=======================================================================
1602 // function: TakeModified
1603 // purpose: Stores the modified object into the map
1604 //=======================================================================
1605 void TakeModified(const TopoDS_Shape& theS,
1606                   BOPAlgo_Builder& theBuilder,
1607                   TopTools_MapOfShape& theMap)
1608 {
1609   const TopTools_ListOfShape& aModified = theBuilder.Modified(theS);
1610   if (aModified.IsEmpty() && !theBuilder.IsDeleted(theS))
1611     theMap.Add(theS);
1612   else
1613   {
1614     TopTools_ListIteratorOfListOfShape itM(aModified);
1615     for (; itM.More(); itM.Next())
1616       theMap.Add(itM.Value());
1617   }
1618 }
1619
1620 //=======================================================================
1621 // function: FindSolid
1622 // purpose: Looks for the image of the solid in the list of resulting solids
1623 //=======================================================================
1624 void FindSolid(const TopoDS_Shape& theSolIn,
1625                const TopTools_ListOfShape& theSolidsRes,
1626                const TopTools_IndexedDataMapOfShapeListOfShape& theAdjFaces,
1627                BOPAlgo_Builder& theBuilder,
1628                TopoDS_Shape& theSolOut)
1629 {
1630   Handle(IntTools_Context) aCtx = theBuilder.Context();
1631
1632   // Take the face in the IN solid, and find it in the OUT list
1633   TopExp_Explorer anExpF(theSolIn, TopAbs_FACE);
1634   for (; anExpF.More(); anExpF.Next())
1635   {
1636     const TopoDS_Shape& aFS = anExpF.Current();
1637     // Images of the face
1638     TopTools_MapOfShape aMFSIm;
1639     const TopTools_ListOfShape* pLFA = theAdjFaces.Seek(aFS);
1640     if (pLFA)
1641     {
1642       TopTools_ListIteratorOfListOfShape itLFA(*pLFA);
1643       for (; itLFA.More(); itLFA.Next())
1644         TakeModified(itLFA.Value(), theBuilder, aMFSIm);
1645     }
1646     else
1647     {
1648       TakeModified(aFS, theBuilder, aMFSIm);
1649     }
1650
1651     // Find any of these faces in the list of solids
1652     TopTools_ListIteratorOfListOfShape itLS(theSolidsRes);
1653     for (; itLS.More(); itLS.Next())
1654     {
1655       const TopoDS_Shape& aSol = itLS.Value();
1656       TopExp_Explorer anExpFOut(aSol, TopAbs_FACE);
1657       for (; anExpFOut.More(); anExpFOut.Next())
1658       {
1659         const TopoDS_Shape& aF = anExpFOut.Current();
1660         if (aMFSIm.Contains(aF))
1661         {
1662           // check orientations
1663           if (!BOPTools_AlgoTools::IsSplitToReverse(aF, aFS, aCtx))
1664           {
1665             theSolOut = aSol;
1666             return;
1667           }
1668         }
1669       }
1670     }
1671   }
1672 }