0030386: Modeling Algorithms - Unable to perform Cut operation
[occt.git] / 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 }