0030386: Modeling Algorithms - Unable to perform Cut operation
[occt.git] / src / BOPAlgo / BOPAlgo_CellsBuilder.cxx
1 // Created by: Eugeny MALTCHIKOV
2 // Copyright (c) 2015 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
16 #include <BOPAlgo_CellsBuilder.hxx>
17
18 #include <BOPAlgo_Alerts.hxx>
19 #include <BOPAlgo_BuilderSolid.hxx>
20 #include <BOPDS_DS.hxx>
21 #include <BOPTools_AlgoTools.hxx>
22 #include <BOPTools_AlgoTools3D.hxx>
23 #include <BRep_Builder.hxx>
24 #include <ShapeUpgrade_UnifySameDomain.hxx>
25 #include <TColStd_MapOfInteger.hxx>
26 #include <TopExp.hxx>
27 #include <TopExp_Explorer.hxx>
28 #include <TopoDS_Compound.hxx>
29
30
31 static
32   TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
33
34 static
35   void MakeTypedContainers(const TopoDS_Shape& theSC,
36                            TopoDS_Shape& theResult);
37
38 static void CollectMaterialBoundaries(const TopTools_ListOfShape& theLS,
39                                       TopTools_MapOfShape& theMapKeepBnd);
40
41 //=======================================================================
42 //function : empty constructor
43 //purpose  : 
44 //=======================================================================
45 BOPAlgo_CellsBuilder::BOPAlgo_CellsBuilder()
46 :
47   BOPAlgo_Builder(),
48   myIndex(100, myAllocator),
49   myMaterials(100, myAllocator),
50   myShapeMaterial(100, myAllocator),
51   myMapModified(100, myAllocator)
52 {
53 }
54
55 //=======================================================================
56 //function : empty constructor
57 //purpose  : 
58 //=======================================================================
59 BOPAlgo_CellsBuilder::BOPAlgo_CellsBuilder
60   (const Handle(NCollection_BaseAllocator)& theAllocator)
61 :
62   BOPAlgo_Builder(theAllocator),
63   myIndex(100, myAllocator),
64   myMaterials(100, myAllocator),
65   myShapeMaterial(100, myAllocator),
66   myMapModified(100, myAllocator)
67 {
68 }
69
70 //=======================================================================
71 //function : ~
72 //purpose  : 
73 //=======================================================================
74 BOPAlgo_CellsBuilder::~BOPAlgo_CellsBuilder()
75 {
76   Clear();
77 }
78
79 //=======================================================================
80 //function : Clear
81 //purpose  : 
82 //=======================================================================
83 void BOPAlgo_CellsBuilder::Clear()
84 {
85   BOPAlgo_Builder::Clear();
86   myIndex.Clear();
87   myMaterials.Clear();
88   myShapeMaterial.Clear();
89   myMapModified.Clear();
90 }
91
92 //=======================================================================
93 //function : GetAllParts
94 //purpose  : 
95 //=======================================================================
96 const TopoDS_Shape& BOPAlgo_CellsBuilder::GetAllParts() const
97 {
98   return myAllParts;
99 }
100
101 //=======================================================================
102 //function : PerformInternal1
103 //purpose  : 
104 //=======================================================================
105 void BOPAlgo_CellsBuilder::PerformInternal1(const BOPAlgo_PaveFiller& theFiller)
106 {
107   // Avoid filling history after GF operation as later
108   // in this method the result shape will be nullified
109   Standard_Boolean isHistory = HasHistory();
110   SetToFillHistory(Standard_False);
111   // Perform splitting of the arguments
112   BOPAlgo_Builder::PerformInternal1(theFiller);
113   if (HasErrors()) {
114     return;
115   }
116
117   // index all the parts to its origins
118   IndexParts();
119
120   // and nullify <myShape> for building the result;
121   RemoveAllFromResult();
122
123   // Restore user's history settings
124   SetToFillHistory(isHistory);
125 }
126
127 //=======================================================================
128 //function : IndexParts
129 //purpose  : 
130 //=======================================================================
131 void BOPAlgo_CellsBuilder::IndexParts()
132 {
133   BRep_Builder aBB;
134   // all split parts of the shapes
135   TopoDS_Compound anAllParts;
136   aBB.MakeCompound(anAllParts);
137   //
138   TopTools_MapOfShape aMFence;
139   TColStd_MapOfInteger aMDims;
140   //
141   TopTools_ListIteratorOfListOfShape aIt(myArguments);
142   for (; aIt.More(); aIt.Next()) {
143     const TopoDS_Shape& aS = aIt.Value();
144
145     TopTools_ListOfShape aLSubS;
146     BOPTools_AlgoTools::TreatCompound (aS, aLSubS);
147     for (TopTools_ListOfShape::Iterator itSub (aLSubS); itSub.More(); itSub.Next())
148     {
149       const TopoDS_Shape& aSS = itSub.Value();
150       Standard_Integer iDim = BOPTools_AlgoTools::Dimension (aSS);
151       aMDims.Add(iDim);
152       TopAbs_ShapeEnum aType = TypeToExplore (iDim);
153       TopExp_Explorer aExp (aSS, aType);
154       for (; aExp.More(); aExp.Next())
155       {
156         const TopoDS_Shape& aST = aExp.Current();
157         const TopTools_ListOfShape* pLSIm = myImages.Seek(aST);
158         if (!pLSIm) {
159           TopTools_ListOfShape* pLS = myIndex.ChangeSeek(aST);
160           if (!pLS) {
161             pLS = &myIndex(myIndex.Add(aST, TopTools_ListOfShape()));
162           }
163           pLS->Append(aS);
164           //
165           if (aMFence.Add(aST)) {
166             aBB.Add(anAllParts, aST);
167           }
168           //
169           continue;
170         }
171         //
172         TopTools_ListIteratorOfListOfShape aItIm(*pLSIm);
173         for (; aItIm.More(); aItIm.Next()) {
174           const TopoDS_Shape& aSTIm = aItIm.Value();
175           //
176           TopTools_ListOfShape* pLS = myIndex.ChangeSeek(aSTIm);
177           if (!pLS) {
178             pLS = &myIndex(myIndex.Add(aSTIm, TopTools_ListOfShape()));
179           }
180           pLS->Append(aS);
181           //
182           if (aMFence.Add(aSTIm)) {
183             aBB.Add(anAllParts, aSTIm);
184           }
185         } // for (; aItIm.More(); aItIm.Next()) {
186       } // for (; aExp.More(); aExp.Next()) {
187     } // for (; itSub.More(); itSub.Next())
188   } // for (; aIt.More(); aIt.Next()) {
189   //
190   myAllParts = anAllParts;
191   //
192   if (aMDims.Extent() == 1) {
193     return;
194   }
195   //
196   // for the multi-dimensional case
197   // add sub-shapes of the splits into the <myIndex> map
198   //
199   Standard_Integer i, aNbS = myIndex.Extent();
200   for (i = 1; i <= aNbS; ++i) {
201     const TopoDS_Shape& aSP = myIndex.FindKey(i);
202     const TopTools_ListOfShape& aLSOr = myIndex(i);
203     //
204     Standard_Integer iType = BOPTools_AlgoTools::Dimension(aSP);
205     TColStd_MapIteratorOfMapOfInteger aItM(aMDims);
206     for (; aItM.More(); aItM.Next()) {
207       Standard_Integer k = aItM.Value();
208       if (k >= iType) {
209         continue;
210       }
211       //
212       TopExp_Explorer aExp(aSP, TypeToExplore(k));
213       for (; aExp.More(); aExp.Next()) {
214         const TopoDS_Shape& aSS = aExp.Current();
215         TopTools_ListOfShape* pLSSOr = myIndex.ChangeSeek(aSS);
216         if (!pLSSOr) {
217           myIndex.Add(aSS, aLSOr);
218           continue;
219         }
220         // add ancestors of the shape to the ancestors of the sub-shape
221         TopTools_ListIteratorOfListOfShape aItLS(aLSOr);
222         for (; aItLS.More(); aItLS.Next()) {
223           const TopoDS_Shape& aSOr = aItLS.Value();
224           // provide uniqueness of the ancestors
225           TopTools_ListIteratorOfListOfShape aItLSS(*pLSSOr);
226           for (; aItLSS.More(); aItLSS.Next()) {
227             if (aSOr.IsSame(aItLSS.Value())) {
228               break;
229             }
230           }
231           //
232           if (!aItLSS.More()) {
233             pLSSOr->Append(aSOr);
234           }
235         }
236       }
237     }
238   }
239 }
240
241 //=======================================================================
242 //function : AddToResult
243 //purpose  : 
244 //=======================================================================
245 void BOPAlgo_CellsBuilder::AddToResult(const TopTools_ListOfShape& theLSToTake,
246                                        const TopTools_ListOfShape& theLSToAvoid,
247                                        const Standard_Integer theMaterial,
248                                        const Standard_Boolean theUpdate)
249 {
250   // find parts
251   TopTools_ListOfShape aParts;
252   FindParts(theLSToTake, theLSToAvoid, aParts);
253   if (aParts.IsEmpty()) {
254     return;
255   }
256   //
257   // collect result parts to avoid multiple adding of the same parts
258   TopTools_MapOfShape aResParts;
259   TopoDS_Iterator aIt(myShape);
260   for (; aIt.More(); aIt.Next()) {
261     aResParts.Add(aIt.Value());
262   }
263   //
264   Standard_Boolean bChanged = Standard_False;
265   // add parts to result
266   TopTools_ListIteratorOfListOfShape aItLP(aParts);
267   for (; aItLP.More(); aItLP.Next()) {
268     const TopoDS_Shape& aPart = aItLP.Value();
269     // provide uniqueness of the parts 
270     if (aResParts.Add(aPart) && !myShapeMaterial.IsBound(aPart)) {
271       BRep_Builder().Add(myShape, aPart);
272       bChanged = Standard_True;
273     }
274   }
275   //
276   // update the material
277   if (theMaterial != 0) {
278     TopTools_ListOfShape aLSP;
279     aItLP.Initialize(aParts);
280     for (; aItLP.More(); aItLP.Next()) {
281       const TopoDS_Shape& aPart = aItLP.Value();
282       if (!myShapeMaterial.IsBound(aPart)) {
283         myShapeMaterial.Bind(aPart, theMaterial);
284         aLSP.Append(aPart);
285       }
286     } // for (; aIt.More(); aIt.Next()) {
287     //
288     if (aLSP.Extent()) {
289       TopTools_ListOfShape* pLS = myMaterials.ChangeSeek(theMaterial);
290       if (!pLS) {
291         pLS = myMaterials.Bound(theMaterial, TopTools_ListOfShape());
292       }
293       pLS->Append(aLSP);
294     } // if (aLSP.Extent()) {
295   } // if (theMaterial != 0) {
296   //
297   if (!theUpdate) {
298     if (bChanged) {
299       PrepareHistory();
300     }
301   }
302   else {
303     RemoveInternalBoundaries();
304   }
305 }
306
307 //=======================================================================
308 //function : AddAllToResult
309 //purpose  : 
310 //=======================================================================
311 void BOPAlgo_CellsBuilder::AddAllToResult(const Standard_Integer theMaterial,
312                                           const Standard_Boolean theUpdate)
313 {
314   myShapeMaterial.Clear();
315   myMaterials.Clear();
316   myMapModified.Clear();
317   //
318   myShape = myAllParts;
319   //
320   if (theMaterial != 0) {
321     TopTools_ListOfShape* pLSM = myMaterials.Bound(theMaterial, TopTools_ListOfShape());
322     //
323     TopoDS_Iterator aIt(myAllParts);
324     for (; aIt.More(); aIt.Next()) {
325       const TopoDS_Shape& aPart = aIt.Value();
326       myShapeMaterial.Bind(aPart, theMaterial);
327       pLSM->Append(aPart);
328     }
329   }
330   //
331   if (!theUpdate) {
332     PrepareHistory();
333   }
334   else {
335     RemoveInternalBoundaries();
336   }
337 }
338
339 //=======================================================================
340 //function : RemoveFromResult
341 //purpose  : 
342 //=======================================================================
343 void BOPAlgo_CellsBuilder::RemoveFromResult(const TopTools_ListOfShape& theLSToTake,
344                                             const TopTools_ListOfShape& theLSToAvoid)
345 {
346   // find parts
347   TopTools_ListOfShape aParts;
348   FindParts(theLSToTake, theLSToAvoid, aParts);
349   if (aParts.IsEmpty()) {
350     return;
351   }
352   //
353   // collect parts into the map and remove parts from materials
354   TopTools_MapOfShape aPartsToRemove;
355   TopTools_ListIteratorOfListOfShape aItP(aParts);
356   for (; aItP.More(); aItP.Next()) {
357     const TopoDS_Shape& aPart = aItP.Value();
358     aPartsToRemove.Add(aPart);
359     //
360     const Standard_Integer* pMaterial = myShapeMaterial.Seek(aPart);
361     if (pMaterial) {
362       TopTools_ListOfShape* pLSM = myMaterials.ChangeSeek(*pMaterial);
363       if (pLSM) {
364         TopTools_ListIteratorOfListOfShape aItM(*pLSM);
365         for (; aItM.More(); aItM.Next()) {
366           if (aPart.IsSame(aItM.Value())) {
367             pLSM->Remove(aItM);
368             break;
369           }
370         }
371       }
372       myShapeMaterial.UnBind(aPart);
373     }
374   }
375   //
376   BRep_Builder aBB;
377   TopoDS_Compound aResult;
378   aBB.MakeCompound(aResult);
379   Standard_Boolean bChanged = Standard_False;
380   //
381   TopoDS_Iterator aIt(myShape);
382   for (; aIt.More(); aIt.Next()) {
383     const TopoDS_Shape& aS = aIt.Value();
384     TopAbs_ShapeEnum aType = aS.ShapeType();
385     if (aType != TopAbs_WIRE &&
386         aType != TopAbs_SHELL &&
387         aType != TopAbs_COMPSOLID) {
388       // basic element
389       if (aPartsToRemove.Contains(aS)) {
390         bChanged = Standard_True;
391         continue;
392       }
393       aBB.Add(aResult, aS);
394     }
395     else {
396       // container
397       TopoDS_Compound aSC;
398       aBB.MakeCompound(aSC);
399       Standard_Boolean bSCNotEmpty = Standard_False;
400       //
401       TopoDS_Iterator aItSC(aS);
402       for (; aItSC.More(); aItSC.Next()) {
403         const TopoDS_Shape& aSS = aItSC.Value();
404         if (aPartsToRemove.Contains(aSS)) {
405           bChanged = Standard_True;
406           continue;
407         }
408         //
409         bSCNotEmpty = Standard_True;
410         aBB.Add(aSC, aSS);
411       }
412       //
413       if (bSCNotEmpty) {
414         MakeTypedContainers(aSC, aResult);
415       }
416     }
417   }
418   //
419   if (bChanged) {
420     myShape = aResult;
421     //
422     PrepareHistory();
423   }
424 }
425
426 //=======================================================================
427 //function : RemoveAllFromResult
428 //purpose  : 
429 //=======================================================================
430 void BOPAlgo_CellsBuilder::RemoveAllFromResult()
431 {
432   // empty compound
433   TopoDS_Compound aC;
434   BRep_Builder().MakeCompound(aC);
435   myShape = aC;
436   //
437   myMaterials.Clear();
438   myShapeMaterial.Clear();
439   myMapModified.Clear();
440   //
441   PrepareHistory();
442 }
443
444 //=======================================================================
445 //function : RemoveInternalBoundaries
446 //purpose  : 
447 //=======================================================================
448 void BOPAlgo_CellsBuilder::RemoveInternalBoundaries()
449 {
450   if (myMaterials.IsEmpty()) {
451     return;
452   }
453   //
454   BRep_Builder aBB;
455   TopoDS_Compound aResult;
456   aBB.MakeCompound(aResult);
457   //
458   Standard_Boolean bChanged = Standard_False;
459   // try to remove the internal boundaries between the
460   // shapes of the same material
461   TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape aItM(myMaterials);
462   TopTools_ListOfShape aLSUnify[2];
463   TopTools_MapOfShape aKeepMap[2];
464   for (; aItM.More(); aItM.Next()) {
465     Standard_Integer iMaterial = aItM.Key();
466     TopTools_ListOfShape& aLS = aItM.ChangeValue();
467     //
468     if (aLS.IsEmpty()) {
469       continue;
470     }
471     //
472     if (aLS.Extent() == 1) {
473       TopAbs_ShapeEnum aType = aLS.First().ShapeType();
474       if (aType != TopAbs_WIRE &&
475           aType != TopAbs_SHELL &&
476           aType != TopAbs_COMPSOLID) {
477         aBB.Add(aResult, aLS.First());
478         continue;
479       }
480     }
481     //
482     // check the shapes of the same material to be of the same type
483     TopTools_ListIteratorOfListOfShape aItLS(aLS);
484     TopAbs_ShapeEnum aType = aItLS.Value().ShapeType();
485     for (aItLS.Next(); aItLS.More(); aItLS.Next()) {
486       if (aType != aItLS.Value().ShapeType()) {
487         break;
488       }
489     }
490
491     if (aItLS.More())
492     {
493       // add the warning
494       TopoDS_Compound aMultiDimS;
495       aBB.MakeCompound(aMultiDimS);
496       aBB.Add(aMultiDimS, aLS.First());
497       aBB.Add(aMultiDimS, aItLS.Value());
498       AddWarning(new BOPAlgo_AlertRemovalOfIBForMDimShapes(aMultiDimS));
499     }
500     else
501     {
502       if (aType == TopAbs_EDGE || aType == TopAbs_FACE)
503       {
504         // for edges and faces, just collect shapes to unify them later after exiting the loop;
505         // collect boundaries of shapes of current material in the keep map
506         Standard_Integer iType = (aType == TopAbs_EDGE ? 0 : 1);
507         CollectMaterialBoundaries(aLS, aKeepMap[iType]);
508         // save shapes to unify later
509         TopTools_ListOfShape aCopy(aLS);
510         aLSUnify[iType].Append(aCopy);
511         continue;
512       }
513       else
514       {
515         // aType is Solid;
516         // remove internal faces between solids of the same material just now
517         TopTools_ListOfShape aLSNew;
518         if (RemoveInternals(aLS, aLSNew))
519         {
520           bChanged = Standard_True;
521           // update materials maps
522           for (aItLS.Initialize(aLSNew); aItLS.More(); aItLS.Next()) {
523             const TopoDS_Shape& aS = aItLS.Value();
524             myShapeMaterial.Bind(aS, iMaterial);
525           }
526           aLS.Assign(aLSNew);
527         }
528       }
529     }
530     // add shapes to result (multidimensional and solids)
531     for (aItLS.Initialize(aLS); aItLS.More(); aItLS.Next()) {
532       const TopoDS_Shape& aS = aItLS.Value();
533       aBB.Add(aResult, aS);
534     }
535   }
536
537   // remove internal boundaries for edges and faces
538   for (Standard_Integer iType = 0; iType < 2; ++iType)
539   {
540     if (aLSUnify[iType].IsEmpty())
541       continue;
542     TopTools_ListOfShape aLSN;
543     if (RemoveInternals(aLSUnify[iType], aLSN, aKeepMap[iType]))
544       bChanged = Standard_True;
545     // add shapes to result ([unified] edges or faces)
546     for (TopTools_ListIteratorOfListOfShape aItLS(aLSN); aItLS.More(); aItLS.Next()) {
547       const TopoDS_Shape& aS = aItLS.Value();
548       aBB.Add(aResult, aS);
549     }
550   }
551   //
552   if (bChanged) {
553     // add shapes without material into result
554     TopoDS_Iterator aIt(myShape);
555     for (; aIt.More(); aIt.Next()) {
556       const TopoDS_Shape& aS = aIt.Value();
557       //
558       if (myShapeMaterial.IsBound(aS)) {
559         continue;
560       }
561       //
562       // check if it is not a collection
563       TopAbs_ShapeEnum aType = aS.ShapeType();
564       if (aType != TopAbs_WIRE &&
565           aType != TopAbs_SHELL &&
566           aType != TopAbs_COMPSOLID) {
567         aBB.Add(aResult, aS);
568       }
569       else {
570         TopoDS_Compound aSC;
571         aBB.MakeCompound(aSC);
572         Standard_Boolean bSCEmpty(Standard_True), bSCChanged(Standard_False);
573         //
574         TopoDS_Iterator aItSC(aS);
575         for (; aItSC.More(); aItSC.Next()) {
576           const TopoDS_Shape& aSS = aItSC.Value();
577           if (!myShapeMaterial.IsBound(aSS)) {
578             aBB.Add(aSC, aSS);
579             bSCEmpty = Standard_False;
580           }
581           else {
582             bSCChanged = Standard_True;
583           }
584         }
585         //
586         if (bSCEmpty) {
587           continue;
588         }
589         //
590         if (bSCChanged) {
591           MakeTypedContainers(aSC, aResult);
592         }
593         else {
594           aBB.Add(aResult, aS);
595         }
596       }
597     }
598     //
599     myShape = aResult;
600     //
601     PrepareHistory();
602   }
603 }
604
605 //=======================================================================
606 //function : FindPart
607 //purpose  : 
608 //=======================================================================
609 void BOPAlgo_CellsBuilder::FindParts(const TopTools_ListOfShape& theLSToTake,
610                                      const TopTools_ListOfShape& theLSToAvoid,
611                                      TopTools_ListOfShape& theParts)
612 {
613   if (theLSToTake.IsEmpty()) {
614     return;
615   }
616   //
617   // map shapes to avoid
618   TopTools_MapOfShape aMSToAvoid;
619   TopTools_ListIteratorOfListOfShape aItArgs(theLSToAvoid);
620   for (; aItArgs.More(); aItArgs.Next()) {
621     const TopoDS_Shape& aS = aItArgs.Value();
622     aMSToAvoid.Add(aS);
623   }
624   //
625   // map shapes to be taken
626   TopTools_MapOfShape aMSToTake;
627   aItArgs.Initialize(theLSToTake);
628   for (; aItArgs.More(); aItArgs.Next()) {
629     const TopoDS_Shape& aS = aItArgs.Value();
630     aMSToTake.Add(aS);
631   }
632   //
633   Standard_Integer aNbS = aMSToTake.Extent();
634   //
635   // among the shapes to be taken into result, find any one
636   // of minimal dimension
637   Standard_Integer iDimMin = 10;
638   TopoDS_Shape aSMin;
639   //
640   aItArgs.Initialize(theLSToTake);
641   for (; aItArgs.More(); aItArgs.Next()) {
642     const TopoDS_Shape& aS = aItArgs.Value();
643     Standard_Integer iDim = BOPTools_AlgoTools::Dimension(aS);
644     if (iDim < iDimMin) {
645       iDimMin = iDim;
646       aSMin = aS;
647     }
648   }
649   //
650   // among the split parts of the shape of minimal dimension
651   // look for the parts to be taken into result
652   TopAbs_ShapeEnum aType = TypeToExplore(iDimMin);
653   TopExp_Explorer aExp(aSMin, aType);
654   for (; aExp.More(); aExp.Next()) {
655     const TopoDS_Shape& aST = aExp.Current();
656     // get split parts of the shape
657     TopTools_ListOfShape aLSTIm;
658     if (!myImages.IsBound(aST)) {
659       aLSTIm.Append(aST);
660     } else {
661       aLSTIm = myImages.Find(aST);
662     }
663     //
664     TopTools_ListIteratorOfListOfShape aItIm(aLSTIm);
665     for (; aItIm.More(); aItIm.Next()) {
666       const TopoDS_Shape& aPart = aItIm.Value();
667       //
668       if (!myIndex.Contains(aPart)) {
669         continue;
670       }
671       //
672       // get input shapes in which the split part is contained
673       const TopTools_ListOfShape& aLS = myIndex.FindFromKey(aPart);
674       if (aLS.Extent() < aNbS) {
675         continue;
676       }
677       //
678       // check that input shapes containing the part should not be avoided
679       TopTools_MapOfShape aMS;
680       aItArgs.Initialize(aLS);
681       for (; aItArgs.More(); aItArgs.Next()) {
682         const TopoDS_Shape& aS = aItArgs.Value();
683         aMS.Add(aS);
684         if (aMSToAvoid.Contains(aS)) {
685           break;
686         }
687       }
688       //
689       if (aItArgs.More()) {
690         continue;
691       }
692       //
693       // check that all shapes which should be taken contain the part
694       aItArgs.Initialize(theLSToTake);
695       for (; aItArgs.More(); aItArgs.Next()) {
696         if (!aMS.Contains(aItArgs.Value())) {
697           break;
698         }
699       }
700       //
701       if (!aItArgs.More()) {
702         theParts.Append(aPart);
703       }
704     }
705   }
706 }
707
708 //=======================================================================
709 //function : MakeContainers
710 //purpose  : 
711 //=======================================================================
712 void BOPAlgo_CellsBuilder::MakeContainers()
713 {
714   BRep_Builder aBB;
715   TopoDS_Compound aResult;
716   aBB.MakeCompound(aResult);
717   //
718   // basic elements of type EDGE, FACE and SOLID added into result
719   TopTools_ListOfShape aLS[3];
720   //
721   TopoDS_Iterator aIt(myShape);
722   for (; aIt.More(); aIt.Next()) {
723     const TopoDS_Shape& aS = aIt.Value();
724     //
725     Standard_Integer iDim = BOPTools_AlgoTools::Dimension(aS);
726     if (iDim <= 0) {
727       aBB.Add(aResult, aS);
728       continue;
729     }
730     //
731     aLS[iDim-1].Append(aS);
732   }
733   //
734   for (Standard_Integer i = 0; i < 3; ++i) {
735     if (aLS[i].IsEmpty()) {
736       continue;
737     }
738     //
739     TopoDS_Compound aC;
740     aBB.MakeCompound(aC);
741     TopTools_ListIteratorOfListOfShape aItLS(aLS[i]);
742     for (; aItLS.More(); aItLS.Next()) {
743       aBB.Add(aC, aItLS.Value());
744     }
745     //
746     MakeTypedContainers(aC, aResult);
747   }
748   myShape = aResult;
749 }
750
751 //=======================================================================
752 //function : RemoveInternals
753 //purpose  : 
754 //=======================================================================
755 Standard_Boolean BOPAlgo_CellsBuilder::RemoveInternals(const TopTools_ListOfShape& theLS,
756                                                        TopTools_ListOfShape& theLSNew,
757                                                        const TopTools_MapOfShape& theMapKeepBnd)
758 {
759   Standard_Boolean bRemoved = Standard_False;
760   if (theLS.Extent() < 2) {
761     theLSNew = theLS;
762     return bRemoved;
763   }
764   //
765   TopAbs_ShapeEnum aType = theLS.First().ShapeType();
766   //
767   if (aType == TopAbs_EDGE ||
768       aType == TopAbs_FACE) {
769     //
770     // make container
771     BRep_Builder aBB;
772     TopoDS_Shape aShape;
773     //
774     BOPTools_AlgoTools::MakeContainer
775       ((aType == TopAbs_FACE) ? TopAbs_SHELL : TopAbs_WIRE, aShape);
776     //
777     for (TopTools_ListIteratorOfListOfShape aIt(theLS); aIt.More(); aIt.Next()) {
778       const TopoDS_Shape& aS = aIt.Value();
779       aBB.Add(aShape, aS);
780     }
781     //
782     // Unify same domain
783     Standard_Boolean bFaces, bEdges;
784     //
785     bFaces = (aType == TopAbs_FACE);
786     bEdges = (aType == TopAbs_EDGE);
787     ShapeUpgrade_UnifySameDomain anUnify (aShape, bEdges, bFaces);
788     anUnify.KeepShapes(theMapKeepBnd);
789     anUnify.Build();
790     const TopoDS_Shape& aSNew = anUnify.Shape();
791     //
792     TopExp_Explorer aExp(aSNew, aType);
793     for (; aExp.More(); aExp.Next()) {
794       const TopoDS_Shape& aSn = aExp.Current();
795       theLSNew.Append(aSn);
796     }
797     //
798     if (theLSNew.IsEmpty()) {
799       // add the warning
800       if (bFaces)
801         AddWarning (new BOPAlgo_AlertRemovalOfIBForFacesFailed (aShape));
802       else
803         AddWarning (new BOPAlgo_AlertRemovalOfIBForEdgesFailed (aShape));
804       //
805       theLSNew.Assign(theLS);
806       return bRemoved;
807     }
808     //
809     // fill map of modified shapes
810     TopTools_IndexedMapOfShape aMG;
811     Standard_Integer i, aNb;
812     //
813     TopExp::MapShapes(aShape, TopAbs_VERTEX, aMG);
814     TopExp::MapShapes(aShape, TopAbs_EDGE,   aMG);
815     TopExp::MapShapes(aShape, TopAbs_FACE,   aMG);
816     //
817     aNb = aMG.Extent();
818     for (i = 1; i <= aNb; ++i) {
819       const TopoDS_Shape& aSS = aMG(i);
820       const Standard_Integer* pMaterial = myShapeMaterial.Seek(aSS);
821       const TopTools_ListOfShape& aLSMod = anUnify.History()->Modified(aSS);
822       TopTools_ListIteratorOfListOfShape aIt(aLSMod);
823       for (; aIt.More(); aIt.Next()) {
824         const TopoDS_Shape& aSU = aIt.Value();
825         myMapModified.Bind(aSS, aSU);
826         bRemoved = Standard_True;
827         if (pMaterial && !myShapeMaterial.IsBound(aSU))
828           myShapeMaterial.Bind(aSU, *pMaterial);
829       }
830     }
831   }
832   else if (aType == TopAbs_SOLID) {
833     BRep_Builder aBB;
834     TopoDS_Compound aSolids;
835     aBB.MakeCompound(aSolids);
836     //
837     TopTools_ListIteratorOfListOfShape aItLS(theLS);
838     for (; aItLS.More(); aItLS.Next()) {
839       const TopoDS_Shape& aSol = aItLS.Value();
840       aBB.Add(aSolids, aSol);
841     }
842     //
843     // Make connexity blocks of solids to create from each isolated block one solid.
844     // It will allow attaching internal entities of the solids to new solid.
845     TopTools_ListOfShape aLCB;
846     BOPTools_AlgoTools::MakeConnexityBlocks(aSolids, TopAbs_FACE, TopAbs_SOLID, aLCB);
847     //
848     // for each block remove internal faces
849     TopTools_ListIteratorOfListOfShape aItLCB(aLCB);
850     for (; aItLCB.More(); aItLCB.Next()) {
851       const TopoDS_Shape& aCB = aItLCB.Value();
852       //
853       // Map faces and solids to find boundary faces that can be removed
854       TopTools_IndexedDataMapOfShapeListOfShape aDMFS;
855       // internal entities
856       TopTools_ListOfShape aLSInt;
857       //
858       TopoDS_Iterator aItS(aCB);
859       for (; aItS.More(); aItS.Next()) {
860         const TopoDS_Shape& aSol = aItS.Value();
861         //
862         TopoDS_Iterator aItIS(aSol);
863         for (; aItIS.More(); aItIS.Next()) {
864           const TopoDS_Shape& aSI = aItIS.Value();
865           if (aSI.Orientation() == TopAbs_INTERNAL) {
866             aLSInt.Append(aSI);
867           }
868           else {
869             TopoDS_Iterator aItF(aSI);
870             for (; aItF.More(); aItF.Next()) {
871               const TopoDS_Shape& aF = aItF.Value();
872               TopTools_ListOfShape *pLSols = aDMFS.ChangeSeek(aF);
873               if (!pLSols) {
874                 pLSols = &aDMFS(aDMFS.Add(aF, TopTools_ListOfShape()));
875               }
876               pLSols->Append(aSol);
877             }
878           }
879         }
880       }
881       //
882       // to build unified solid, select only faces attached to only one solid
883       TopTools_ListOfShape aLFUnique;
884       Standard_Integer i, aNb = aDMFS.Extent();
885       for (i = 1; i <= aNb; ++i) {
886         if (aDMFS(i).Extent() == 1) {
887           aLFUnique.Append(aDMFS.FindKey(i));
888         }
889       }
890       //
891       if (aNb == aLFUnique.Extent()) {
892         // no faces to remove
893         aItS.Initialize(aCB);
894         for (; aItS.More(); aItS.Next()) {
895           theLSNew.Append(aItS.Value());
896         }
897         continue;
898       }
899       //
900       // build new solid
901       BOPAlgo_BuilderSolid aBS;
902       aBS.SetShapes(aLFUnique);
903       aBS.Perform();
904       //
905       if (aBS.HasErrors() || aBS.Areas().Extent() != 1) {
906         // add the warning
907         {
908           TopoDS_Compound aUniqeFaces;
909           aBB.MakeCompound(aUniqeFaces);
910           TopTools_ListIteratorOfListOfShape aItLFUniqe(aLFUnique);
911           for (; aItLFUniqe.More(); aItLFUniqe.Next()) {
912             aBB.Add(aUniqeFaces, aItLFUniqe.Value());
913           }
914           //
915           AddWarning (new BOPAlgo_AlertRemovalOfIBForSolidsFailed (aUniqeFaces));
916         }
917         //
918         aItS.Initialize(aCB);
919         for (; aItS.More(); aItS.Next()) {
920           theLSNew.Append(aItS.Value());
921         }
922         continue;
923       }
924       //
925       myReport->Merge(aBS.GetReport());
926       //
927       TopoDS_Solid& aSNew = *(TopoDS_Solid*)&aBS.Areas().First();
928       //
929       // put all internal parts into new solid
930       aSNew.Free(Standard_True);
931       TopTools_ListIteratorOfListOfShape aItLSI(aLSInt);
932       for (; aItLSI.More(); aItLSI.Next()) {
933         aBB.Add(aSNew, aItLSI.Value());
934       }
935       aSNew.Free(Standard_False);
936       //
937       theLSNew.Append(aSNew);
938       bRemoved = Standard_True;
939
940       // Save information about the fuse of the solids into a history map
941       aItS.Initialize(aCB);
942       for (; aItS.More(); aItS.Next())
943         myMapModified.Bind(aItS.Value(), aSNew);
944     }
945   }
946   return bRemoved;
947 }
948
949 //=======================================================================
950 //function : LocModified
951 //purpose  : 
952 //=======================================================================
953 const TopTools_ListOfShape* BOPAlgo_CellsBuilder::LocModified(const TopoDS_Shape& theS)
954 {
955   // Get shape's modification coming from GF operation
956   const TopTools_ListOfShape* pLSp = BOPAlgo_Builder::LocModified(theS);
957   if (myMapModified.IsEmpty())
958     // No local modifications
959     return pLSp;
960
961   myHistShapes.Clear();
962
963   // Check if the shape (or its splits) has participated in unification
964   if (!pLSp)
965   {
966     // No splits from GF operation.
967     // Check if the shape has been unified with other shapes
968     const TopoDS_Shape* pSU = myMapModified.Seek(theS);
969     if (!pSU)
970       return NULL;
971
972     myHistShapes.Append(*pSU);
973   }
974   else
975   {
976     TopTools_MapOfShape aMFence;
977     // Process all GF splits and check them for local unification with other shapes
978     TopTools_ListIteratorOfListOfShape aIt(*pLSp);
979     for (; aIt.More(); aIt.Next())
980     {
981       const TopoDS_Shape* pSp = &aIt.Value();
982       const TopoDS_Shape* pSU = myMapModified.Seek(*pSp);
983       if (pSU) pSp = pSU;
984       if (aMFence.Add(*pSp))
985         myHistShapes.Append(*pSp);
986     }
987   }
988   return &myHistShapes;
989 }
990
991 //=======================================================================
992 //function : MakeTypedContainers
993 //purpose  : 
994 //=======================================================================
995 void MakeTypedContainers(const TopoDS_Shape& theSC,
996                          TopoDS_Shape& theResult)
997 {
998   TopAbs_ShapeEnum aContainerType, aConnexityType, aPartType;
999   //
1000   aPartType = TypeToExplore(BOPTools_AlgoTools::Dimension(theSC));
1001   switch (aPartType) {
1002     case TopAbs_EDGE: {
1003       aContainerType = TopAbs_WIRE;
1004       aConnexityType = TopAbs_VERTEX;
1005       break;
1006     }
1007     case TopAbs_FACE: {
1008       aContainerType = TopAbs_SHELL;
1009       aConnexityType = TopAbs_EDGE;
1010       break;
1011     }
1012     case TopAbs_SOLID: {
1013       aContainerType = TopAbs_COMPSOLID;
1014       aConnexityType = TopAbs_FACE;
1015       break;
1016     }
1017     default:
1018       return;
1019   }
1020   //
1021   TopTools_ListOfShape aLCB;
1022   BOPTools_AlgoTools::MakeConnexityBlocks(theSC, aConnexityType, aPartType, aLCB);
1023   if (aLCB.IsEmpty()) {
1024     return;
1025   }
1026   //
1027   BRep_Builder aBB;
1028   TopExp_Explorer aExp;
1029   TopTools_ListIteratorOfListOfShape aItCB;
1030   //
1031   aItCB.Initialize(aLCB);
1032   for (; aItCB.More(); aItCB.Next()) {
1033     TopoDS_Shape aRCB;
1034     BOPTools_AlgoTools::MakeContainer(aContainerType, aRCB);
1035     //
1036     const TopoDS_Shape& aCB = aItCB.Value();
1037     aExp.Init(aCB, aPartType);
1038     for (; aExp.More(); aExp.Next()) {
1039       const TopoDS_Shape& aCBS = aExp.Current();
1040       aBB.Add(aRCB, aCBS);
1041     }
1042     //
1043     if (aContainerType == TopAbs_SHELL) {
1044       BOPTools_AlgoTools::OrientFacesOnShell(aRCB);
1045     }
1046     //
1047     aBB.Add(theResult, aRCB);
1048   }
1049 }
1050
1051 //=======================================================================
1052 //function : CollectMaterialBoundaries
1053 //purpose  : Add to theMapKeepBnd the boundary shapes of the area defined by shapes from the list
1054 //=======================================================================
1055 static void CollectMaterialBoundaries(const TopTools_ListOfShape& theLS,
1056                                       TopTools_MapOfShape& theMapKeepBnd)
1057 {
1058   TopAbs_ShapeEnum aType = theLS.First().ShapeType();
1059   TopAbs_ShapeEnum aTypeSubsh = (aType == TopAbs_FACE ? TopAbs_EDGE : TopAbs_VERTEX);
1060   TopTools_IndexedDataMapOfShapeListOfShape aMapSubSh;
1061   TopTools_ListIteratorOfListOfShape anIt(theLS);
1062   for (; anIt.More(); anIt.Next())
1063   {
1064     const TopoDS_Shape& aS = anIt.Value();
1065     TopExp::MapShapesAndAncestors(aS, aTypeSubsh, aType, aMapSubSh);
1066   }
1067   for (int i = 1; i <= aMapSubSh.Extent(); i++)
1068   {
1069     // check if the subshape belongs to boundary of the area
1070     if (aMapSubSh(i).Extent() == 1)
1071     {
1072       // add to theMapKeepBnd
1073       theMapKeepBnd.Add(aMapSubSh.FindKey(i));
1074     }
1075   }
1076 }
1077
1078 //=======================================================================
1079 //function : TypeToExplore
1080 //purpose  : 
1081 //=======================================================================
1082 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
1083 {
1084   TopAbs_ShapeEnum aRet;
1085   //
1086   switch(theDim) {
1087   case 0:
1088     aRet=TopAbs_VERTEX;
1089     break;
1090   case 1:
1091     aRet=TopAbs_EDGE;
1092     break;
1093   case 2:
1094     aRet=TopAbs_FACE;
1095     break;
1096   case 3:
1097     aRet=TopAbs_SOLID;
1098     break;
1099   default:
1100     aRet=TopAbs_SHAPE;
1101     break;
1102   }
1103   return aRet;
1104 }