0028226: Incorrect history support in ShapeUpgrade_UnifySameDomain algorithm
[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 <TopoDS_Compound.hxx>
19
20 #include <BRep_Builder.hxx>
21
22 #include <TopExp_Explorer.hxx>
23
24 #include <BOPTools.hxx>
25 #include <BOPTools_AlgoTools.hxx>
26
27 #include <BOPAlgo_BuilderSolid.hxx>
28
29 #include <ShapeUpgrade_UnifySameDomain.hxx>
30
31
32 static
33   TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
34
35 static
36   void MakeTypedContainers(const TopoDS_Shape& theSC,
37                            const TopAbs_ShapeEnum aType,
38                            TopoDS_Shape& theResult);
39
40 //=======================================================================
41 //function : empty constructor
42 //purpose  : 
43 //=======================================================================
44 BOPAlgo_CellsBuilder::BOPAlgo_CellsBuilder()
45 :
46   BOPAlgo_Builder(),
47   myType(TopAbs_SHAPE),
48   myIndex(100, myAllocator),
49   myMaterials(100, myAllocator),
50   myShapeMaterial(100, myAllocator),
51   myMapGenerated(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   myType(TopAbs_SHAPE),
64   myIndex(100, myAllocator),
65   myMaterials(100, myAllocator),
66   myShapeMaterial(100, myAllocator),
67   myMapGenerated(100, myAllocator)
68 {
69 }
70
71 //=======================================================================
72 //function : ~
73 //purpose  : 
74 //=======================================================================
75 BOPAlgo_CellsBuilder::~BOPAlgo_CellsBuilder()
76 {
77   Clear();
78 }
79
80
81 //=======================================================================
82 //function : Clear
83 //purpose  : 
84 //=======================================================================
85 void BOPAlgo_CellsBuilder::Clear()
86 {
87   BOPAlgo_Builder::Clear();
88   myIndex.Clear();
89   myMaterials.Clear();
90   myShapeMaterial.Clear();
91   myMapGenerated.Clear();
92 }
93
94 //=======================================================================
95 //function : GetAllParts
96 //purpose  : 
97 //=======================================================================
98 const TopoDS_Shape& BOPAlgo_CellsBuilder::GetAllParts() const
99 {
100   return myAllParts;
101 }
102
103 //=======================================================================
104 //function : Prepare
105 //purpose  : 
106 //=======================================================================
107 void BOPAlgo_CellsBuilder::Prepare()
108 {
109   BOPAlgo_Builder::Prepare();
110   //
111   myFlagHistory=Standard_False;
112 }
113
114 //=======================================================================
115 // function: CheckData
116 // purpose: 
117 //=======================================================================
118 void BOPAlgo_CellsBuilder::CheckData()
119 {
120   BOPAlgo_Builder::CheckData();
121   if (myErrorStatus) {
122     return;
123   }
124   //
125   // additional check for the arguments to be of the same dimension.
126   Standard_Integer aDim1, aDimi;
127   BOPCol_ListIteratorOfListOfShape aIt;
128   //
129   aIt.Initialize(myArguments);
130   const TopoDS_Shape& aS1 = aIt.Value();
131   aDim1 = BOPTools_AlgoTools::Dimension(aS1);
132   //
133   for (aIt.Next(); aIt.More(); aIt.Next()) {
134     const TopoDS_Shape& aSi = aIt.Value();
135     aDimi = BOPTools_AlgoTools::Dimension(aSi);
136     //
137     if (aDim1 != aDimi) {
138       myErrorStatus = 201; // non-homogenous arguments
139       break;
140     }
141   }
142 }
143
144 //=======================================================================
145 //function : PerformInternal1
146 //purpose  : 
147 //=======================================================================
148 void BOPAlgo_CellsBuilder::PerformInternal1(const BOPAlgo_PaveFiller& theFiller)
149 {
150   BOPAlgo_Builder::PerformInternal1(theFiller);
151   //
152   if (myErrorStatus) {
153     return;
154   }
155   //
156   // save the splits to <myAllParts>
157   TakeAllParts();
158   //
159   // index all the parts to its origins
160   IndexParts();
161   //
162   // and nullify <myShape> for building the result;
163   RemoveAllFromResult();
164   //
165   myFlagHistory = Standard_True;
166 }
167
168 //=======================================================================
169 //function : TakeAllParts
170 //purpose  : 
171 //=======================================================================
172 void BOPAlgo_CellsBuilder::TakeAllParts()
173 {
174   Standard_Integer aDim;
175   TopoDS_Compound aC;
176   BRep_Builder aBB;
177   //
178   aDim = BOPTools_AlgoTools::Dimension(myArguments.First());
179   myType = TypeToExplore(aDim);
180   //
181   aBB.MakeCompound(aC);
182   TopExp_Explorer aExp(myShape, myType);
183   for (; aExp.More(); aExp.Next()) {
184     const TopoDS_Shape& aS = aExp.Current();
185     aBB.Add(aC, aS);
186   }
187   myAllParts = aC;
188 }
189
190 //=======================================================================
191 //function : IndexParts
192 //purpose  : 
193 //=======================================================================
194 void BOPAlgo_CellsBuilder::IndexParts()
195 {
196   BOPCol_ListIteratorOfListOfShape aIt, aItIm;
197   TopExp_Explorer aExp;
198   //
199   aIt.Initialize(myArguments);
200   for (; aIt.More(); aIt.Next()) {
201     const TopoDS_Shape& aS = aIt.Value();
202     //
203     aExp.Init(aS, myType);
204     for (; aExp.More(); aExp.Next()) {
205       const TopoDS_Shape& aST = aExp.Current();
206       const BOPCol_ListOfShape* pLSIm = myImages.Seek(aST);
207       if (!pLSIm) {
208         BOPCol_ListOfShape* pLS = myIndex.ChangeSeek(aST);
209         if (!pLS) {
210           pLS = &myIndex(myIndex.Add(aST, BOPCol_ListOfShape()));
211         }
212         pLS ->Append(aS);
213         continue;
214       }
215       //
216       aItIm.Initialize(*pLSIm);
217       for (; aItIm.More(); aItIm.Next()) {
218         const TopoDS_Shape& aSTIm = aItIm.Value();
219         //
220         BOPCol_ListOfShape* pLS = myIndex.ChangeSeek(aSTIm);
221         if (!pLS) {
222           pLS = &myIndex(myIndex.Add(aSTIm, BOPCol_ListOfShape()));
223         }
224         pLS ->Append(aS);
225       } // for (; aItIm.More(); aItIm.Next()) {
226     } // for (; aExp.More(); aExp.Next()) {
227   } // for (; aIt.More(); aIt.Next()) {
228 }
229
230 //=======================================================================
231 //function : AddToResult
232 //purpose  : 
233 //=======================================================================
234 void BOPAlgo_CellsBuilder::AddToResult(const BOPCol_ListOfShape& theLSToTake,
235                                        const BOPCol_ListOfShape& theLSToAvoid,
236                                        const Standard_Integer theMaterial,
237                                        const Standard_Boolean theUpdate)
238 {
239   // find parts
240   BOPCol_ListOfShape aParts;
241   FindParts(theLSToTake, theLSToAvoid, aParts);
242   if (aParts.IsEmpty()) {
243     return;
244   }
245   //
246   Standard_Boolean bChanged;
247   BRep_Builder aBB;
248   BOPCol_MapOfShape aResParts;
249   TopExp_Explorer aExp;
250   BOPCol_ListIteratorOfListOfShape aIt;
251   //
252   bChanged = Standard_False;
253   // collect result parts to avoid multiple adding of the same parts
254   aExp.Init(myShape, myType);
255   for (; aExp.More(); aExp.Next()) {
256     const TopoDS_Shape& aPart = aExp.Current();
257     aResParts.Add(aPart);
258   }
259   // add parts to result 
260   aIt.Initialize(aParts);
261   for (; aIt.More(); aIt.Next()) {
262     const TopoDS_Shape& aPart = aIt.Value();
263     if (aResParts.Add(aPart)) {
264       aBB.Add(myShape, aPart);
265       bChanged = Standard_True;
266     }
267   }
268   //
269   // update the material
270   if (theMaterial != 0) {
271     BOPCol_ListOfShape aLSP;
272     aIt.Initialize(aParts);
273     for (; aIt.More(); aIt.Next()) {
274       const TopoDS_Shape& aPart = aIt.Value();
275       if (!myShapeMaterial.IsBound(aPart)) {
276         myShapeMaterial.Bind(aPart, theMaterial);
277         aLSP.Append(aPart);
278       }
279     } // for (; aIt.More(); aIt.Next()) {
280     //
281     if (aLSP.Extent()) {
282       if (myMaterials.IsBound(theMaterial)) {
283         BOPCol_ListOfShape& aLS = myMaterials.ChangeFind(theMaterial);
284         aLS.Append(aLSP);
285       } // if (myMaterials.IsBound(theMaterial)) {
286       else {
287         myMaterials.Bind(theMaterial, aLSP);
288       }
289     } // if (aLSP.Extent()) {
290   } // if (theMaterial != 0) {
291   //
292   if (!theUpdate) {
293     if (bChanged) {
294       PrepareHistory();
295     }
296   }
297   else {
298     RemoveInternalBoundaries();
299   }
300 }
301
302 //=======================================================================
303 //function : AddAllToResult
304 //purpose  : 
305 //=======================================================================
306 void BOPAlgo_CellsBuilder::AddAllToResult(const Standard_Integer theMaterial,
307                                           const Standard_Boolean theUpdate)
308 {
309   TopoDS_Compound aResult;
310   BRep_Builder aBB;
311   BOPCol_ListOfShape aLSM;
312   //
313   aBB.MakeCompound(aResult);
314   myShapeMaterial.Clear();
315   myMaterials.Clear();
316   myMapGenerated.Clear();
317   //
318   TopoDS_Iterator aIt(myAllParts);
319   for (; aIt.More(); aIt.Next()) {
320     const TopoDS_Shape& aPart = aIt.Value();
321     aBB.Add(aResult, aPart);
322     //
323     if (theMaterial != 0) {
324       myShapeMaterial.Bind(aPart, theMaterial);
325       aLSM.Append(aPart);
326     }
327   }
328   //
329   myShape = aResult;
330   //
331   if (theMaterial != 0) {
332     myMaterials.Bind(theMaterial, aLSM);
333   }
334   //
335   if (!theUpdate) {
336     PrepareHistory();
337   }
338   else {
339     RemoveInternalBoundaries();
340   }
341 }
342
343 //=======================================================================
344 //function : RemoveFromResult
345 //purpose  : 
346 //=======================================================================
347 void BOPAlgo_CellsBuilder::RemoveFromResult(const BOPCol_ListOfShape& theLSToTake,
348                                             const BOPCol_ListOfShape& theLSToAvoid)
349 {
350   // find parts
351   BOPCol_ListOfShape aParts;
352   FindParts(theLSToTake, theLSToAvoid, aParts);
353   if (aParts.IsEmpty()) {
354     return;
355   }
356   //
357   BOPCol_MapOfShape aPartsToRemove;
358   BOPCol_ListIteratorOfListOfShape aItP, aItM;
359   //
360   // collect parts into the map and remove parts from materials
361   aItP.Initialize(aParts);
362   for (; aItP.More(); aItP.Next()) {
363     const TopoDS_Shape& aPart = aItP.Value();
364     aPartsToRemove.Add(aPart);
365     //
366     if (myShapeMaterial.IsBound(aPart)) {
367       Standard_Integer iMaterial = myShapeMaterial.Find(aPart);
368       if (!myMaterials.IsBound(iMaterial)) {
369         myShapeMaterial.UnBind(aPart);
370         continue;
371       }
372       //
373       BOPCol_ListOfShape& aLSM = myMaterials.ChangeFind(iMaterial);
374       //
375       aItM.Initialize(aLSM);
376       for (; aItM.More(); aItM.Next()) {
377         const TopoDS_Shape& aSM = aItM.Value();
378         if (aSM.IsSame(aPart)) {
379           aLSM.Remove(aItM);
380           break;
381         } // if (aSM.IsSame(aPart)) {
382       } // for (; aItM.More(); aItM.Next()) {
383       //
384       myShapeMaterial.UnBind(aPart);
385     } // if (myShapeMaterial.IsBound(aPart)) {
386   } // for (; aItP.More(); aItP.Next()) {
387   //
388   Standard_Boolean bChanged;
389   TopoDS_Compound aResult;
390   BRep_Builder aBB;
391   TopoDS_Iterator aIt1, aIt2;
392   TopAbs_ShapeEnum aType;
393   //
394   aBB.MakeCompound(aResult);
395   bChanged = Standard_False;
396   //
397   aIt1.Initialize(myShape);
398   for (; aIt1.More(); aIt1.Next()) {
399     const TopoDS_Shape& aS = aIt1.Value();
400     aType = aS.ShapeType();
401     //
402     if (aType == myType) {
403       // basic element
404       if (aPartsToRemove.Contains(aS)) {
405         bChanged = Standard_True;
406         continue;
407       }
408       aBB.Add(aResult, aS);
409     } // if (aType == myType) {
410     else {
411       // container
412       Standard_Boolean bNotEmpty;
413       TopoDS_Compound aSC;
414       aBB.MakeCompound(aSC);
415       //
416       bNotEmpty = Standard_False;
417       aIt2.Initialize(aS);
418       for (; aIt2.More(); aIt2.Next()) {
419         const TopoDS_Shape& aSS = aIt2.Value();
420         if (aPartsToRemove.Contains(aSS)) {
421           bChanged = Standard_True;
422           continue;
423         }
424         aBB.Add(aSC, aSS);
425         bNotEmpty = Standard_True;
426       } // for (; aIt2.More(); aIt2.Next()) {
427       //
428       if (bNotEmpty) {
429         MakeTypedContainers(aSC, myType, aResult);
430       }
431     } // else {
432   } // for (; aIt1.More(); aIt1.Next()) {
433   //
434   if (bChanged) {
435     myShape = aResult;
436     //
437     PrepareHistory();
438   }
439 }
440
441 //=======================================================================
442 //function : RemoveAllFromResult
443 //purpose  : 
444 //=======================================================================
445 void BOPAlgo_CellsBuilder::RemoveAllFromResult()
446 {
447   // empty compound
448   TopoDS_Compound aC;
449   BRep_Builder aBB;
450   //
451   aBB.MakeCompound(aC);
452   myShape = aC;
453   //
454   myMaterials.Clear();
455   myShapeMaterial.Clear();
456   myMapGenerated.Clear();
457   //
458   PrepareHistory();
459 }
460
461 //=======================================================================
462 //function : RemoveInternalBoundaries
463 //purpose  : 
464 //=======================================================================
465 void BOPAlgo_CellsBuilder::RemoveInternalBoundaries()
466 {
467   if (myMaterials.IsEmpty()) {
468     return;
469   }
470   //
471   Standard_Integer iMaterial, iErr;
472   TopoDS_Compound aResult;
473   BRep_Builder aBB;
474   TopExp_Explorer aExp;
475   BOPCol_ListIteratorOfListOfShape aItS;
476   BOPCol_DataMapIteratorOfDataMapOfIntegerListOfShape aItM;
477   //
478   aBB.MakeCompound(aResult);
479   aExp.Init(myShape, myType);
480   for (; aExp.More(); aExp.Next()) {
481     const TopoDS_Shape& aS = aExp.Current();
482     if (!myShapeMaterial.IsBound(aS)) {
483       aBB.Add(aResult, aS);
484     }
485   }
486   //
487   aItM.Initialize(myMaterials);
488   for (; aItM.More(); aItM.Next()) {
489     iMaterial = aItM.Key();
490     //
491     BOPCol_ListOfShape aLSNew;
492     BOPCol_ListOfShape& aLS = myMaterials(iMaterial);
493     iErr = RemoveInternals(aLS, aLSNew);
494     if (iErr || aLSNew.IsEmpty()) {
495       myErrorStatus = 202; // unable to remove internal boundaries
496       return;
497     }
498     //
499     // update materials maps and add new shapes to result
500     aLS.Assign(aLSNew);
501     aItS.Initialize(aLSNew);
502     for (; aItS.More(); aItS.Next()) {
503       const TopoDS_Shape& aS = aItS.Value();
504       aBB.Add(aResult, aS);
505       if (!myShapeMaterial.IsBound(aS)) {
506         myShapeMaterial.Bind(aS, iMaterial);
507       }
508     }
509   }
510   //
511   myShape = aResult;
512   //
513   PrepareHistory();
514 }
515
516 //=======================================================================
517 //function : FindPart
518 //purpose  : 
519 //=======================================================================
520 void BOPAlgo_CellsBuilder::FindParts(const BOPCol_ListOfShape& theLSToTake,
521                                      const BOPCol_ListOfShape& theLSToAvoid,
522                                      BOPCol_ListOfShape& theParts)
523 {
524   if (theLSToTake.IsEmpty()) {
525     return;
526   }
527   //
528   Standard_Boolean bFound;
529   Standard_Integer aNbS;
530   BOPCol_ListIteratorOfListOfShape aItIm, aItArgs;
531   BOPCol_MapOfShape aMSToTake, aMSToAvoid, aMS;
532   TopExp_Explorer aExp;
533   //
534   aItArgs.Initialize(theLSToAvoid);
535   for (; aItArgs.More(); aItArgs.Next()) {
536     const TopoDS_Shape& aS = aItArgs.Value();
537     aMSToAvoid.Add(aS);
538   }
539   //
540   aItArgs.Initialize(theLSToTake);
541   for (; aItArgs.More(); aItArgs.Next()) {
542     const TopoDS_Shape& aS = aItArgs.Value();
543     aMSToTake.Add(aS);
544   }
545   //
546   aNbS = aMSToTake.Extent();
547   //
548   const TopoDS_Shape& aSToTake = theLSToTake.First();
549   aExp.Init(aSToTake, myType);
550   for (; aExp.More(); aExp.Next()) {
551     const TopoDS_Shape& aST = aExp.Current();
552     BOPCol_ListOfShape aLSTIm;
553     if (!myImages.IsBound(aST)) {
554       aLSTIm.Append(aST);
555     } else {
556       aLSTIm = myImages.Find(aST);
557     }
558     //
559     aItIm.Initialize(aLSTIm);
560     for (; aItIm.More(); aItIm.Next()) {
561       const TopoDS_Shape& aPart = aItIm.Value();
562       //
563       if (!myIndex.Contains(aPart)) {
564         continue;
565       }
566       //
567       const BOPCol_ListOfShape& aLS = myIndex.FindFromKey(aPart);
568       if (aLS.Extent() < aNbS) {
569         continue;
570       }
571       //
572       aMS.Clear();
573       aItArgs.Initialize(aLS);
574       for (bFound = Standard_True; aItArgs.More() && bFound; aItArgs.Next()) {
575         const TopoDS_Shape& aS = aItArgs.Value();
576         bFound = !aMSToAvoid.Contains(aS);
577         aMS.Add(aS);
578       }
579       //
580       if (!bFound) {
581         continue;
582       }
583       //
584       aItArgs.Initialize(theLSToTake);
585       for (; aItArgs.More() && bFound; aItArgs.Next()) {
586         const TopoDS_Shape& aS = aItArgs.Value();
587         bFound = aMS.Contains(aS);
588       }
589       //
590       if (bFound) {
591         theParts.Append(aPart);
592       } // if (bFound) {
593     } // for (; aItIm.More(); aItIm.Next()) {
594   } // for (; aExp.More(); aExp.Next()) {
595 }
596
597 //=======================================================================
598 //function : MakeContainers
599 //purpose  : 
600 //=======================================================================
601 void BOPAlgo_CellsBuilder::MakeContainers()
602 {
603   TopoDS_Compound aResult;
604   BRep_Builder aBB;
605   //
606   aBB.MakeCompound(aResult);
607   MakeTypedContainers(myShape, myType, aResult);
608   myShape = aResult;
609 }
610
611 //=======================================================================
612 //function : RemoveInternals
613 //purpose  : 
614 //=======================================================================
615 Standard_Integer BOPAlgo_CellsBuilder::RemoveInternals(const BOPCol_ListOfShape& theLS,
616                                                        BOPCol_ListOfShape& theLSNew)
617 {
618   Standard_Integer iErr = 0;
619   if (theLS.Extent() < 2) {
620     theLSNew = theLS;
621     return iErr;
622   }
623   //  
624   TopExp_Explorer aExp;
625   //
626   TopAbs_ShapeEnum aType = theLS.First().ShapeType();
627   //
628   if (aType == TopAbs_EDGE ||
629       aType == TopAbs_FACE) {
630     //
631     // make container
632     BRep_Builder aBB;
633     TopoDS_Shape aShape;
634     //
635     BOPTools_AlgoTools::MakeContainer
636       ((aType == TopAbs_FACE) ? TopAbs_SHELL : TopAbs_WIRE, aShape);
637     //
638     for (BOPCol_ListIteratorOfListOfShape aIt(theLS); aIt.More(); aIt.Next()) {
639       const TopoDS_Shape& aS = aIt.Value();
640       aBB.Add(aShape, aS);
641     }
642     //
643     // Unify same domain
644     Standard_Boolean bFaces, bEdges;
645     //
646     bFaces = (aType == TopAbs_FACE);
647     bEdges = (aType == TopAbs_EDGE);
648     //
649     ShapeUpgrade_UnifySameDomain anUnify (aShape, bEdges, bFaces);
650     anUnify.Build();
651     const TopoDS_Shape& aSNew = anUnify.Shape();
652     //
653     aExp.Init(aSNew, aType);
654     for (; aExp.More(); aExp.Next()) {
655       const TopoDS_Shape& aSn = aExp.Current();
656       theLSNew.Append(aSn);
657     }
658     //
659     // fill map of generated shapes
660     BOPCol_IndexedMapOfShape aMG;
661     Standard_Integer i, aNb;
662     //
663     BOPTools::MapShapes(aShape, TopAbs_VERTEX, aMG);
664     BOPTools::MapShapes(aShape, TopAbs_EDGE,   aMG);
665     BOPTools::MapShapes(aShape, TopAbs_FACE,   aMG);
666     //
667     aNb = aMG.Extent();
668     for (i = 1; i <= aNb; ++i) {
669       const TopoDS_Shape& aSS = aMG(i);
670       const TopTools_ListOfShape& aLSGen = anUnify.Generated(aSS);
671       TopTools_ListIteratorOfListOfShape aIt(aLSGen);
672       for (; aIt.More(); aIt.Next()) {
673         const TopoDS_Shape& aShape = aIt.Value();
674         if (!aShape.IsNull() && !aSS.IsSame(aShape))
675           myMapGenerated.Bind(aSS, aShape);
676       }
677       const TopTools_ListOfShape& aLSMod = anUnify.Modified(aSS);
678       for (aIt.Init(aLSMod); aIt.More(); aIt.Next()) {
679         const TopoDS_Shape& aShape = aIt.Value();
680         if (!aShape.IsNull() && !aSS.IsSame(aShape))
681           myMapGenerated.Bind(aSS, aShape);
682       }
683     }
684   }
685   else if (aType == TopAbs_SOLID) {
686     // build all solids from the faces
687     BOPCol_ListOfShape aLSF;
688     //
689     for (BOPCol_ListIteratorOfListOfShape aIt(theLS); aIt.More(); aIt.Next()) {
690       const TopoDS_Shape& aS = aIt.Value();
691       //
692       aExp.Init(aS, TopAbs_FACE);
693       for (; aExp.More(); aExp.Next()) {
694         const TopoDS_Shape& aF = aExp.Current();
695         aLSF.Append(aF);
696       }
697     }
698     //
699     BOPAlgo_BuilderSolid aBS;
700     aBS.SetShapes(aLSF);
701     aBS.Perform();
702     //
703     iErr = aBS.ErrorStatus();
704     if (iErr) {
705       return iErr;
706     }
707     //
708     theLSNew = aBS.Areas();
709     if (theLSNew.Extent() == 1) {
710       return iErr;
711     }
712     //
713     // result is a list of solids. we need to select external faces.
714     BOPCol_IndexedDataMapOfShapeListOfShape aDMFS;
715     BOPCol_ListOfShape aLFNew;
716     Standard_Integer i, aNb;
717     //
718     // map faces and solids
719     for (BOPCol_ListIteratorOfListOfShape aIt(theLSNew); aIt.More(); aIt.Next()) {
720       const TopoDS_Shape& aS = aIt.Value();
721       //
722       aExp.Init(aS, TopAbs_FACE);
723       for (; aExp.More(); aExp.Next()) {
724         const TopoDS_Shape& aF = aExp.Current();
725         if (aDMFS.Contains(aF)) {
726           BOPCol_ListOfShape& aLFS = aDMFS.ChangeFromKey(aF);
727           aLFS.Append(aS);
728         }
729         else {
730           BOPCol_ListOfShape aLFS;
731           aLFS.Append(aS);
732           aDMFS.Add(aF, aLFS);
733         }
734       }
735     }
736     //
737     // select faces attached to only one solid
738     aNb = aDMFS.Extent();
739     for (i = 1; i <= aNb; ++i) {
740       const BOPCol_ListOfShape& aLS = aDMFS(i);
741       if (aLS.Extent() == 1) {
742         const TopoDS_Shape& aF = aDMFS.FindKey(i);
743         aLFNew.Append(aF);
744       }
745     }
746     //
747     if (aNb == aLFNew.Extent()) {
748       return iErr;
749     }
750     //
751     // build new solid
752     BOPAlgo_BuilderSolid aBS1;
753     aBS1.SetShapes(aLFNew);
754     aBS1.Perform();
755     //
756     iErr = aBS1.ErrorStatus();
757     if (iErr) {
758       return iErr;
759     }
760     //
761     theLSNew = aBS1.Areas();
762   }
763   //
764   return iErr;
765 }
766
767 //=======================================================================
768 //function : IsDeleted
769 //purpose  : 
770 //=======================================================================
771 Standard_Boolean BOPAlgo_CellsBuilder::IsDeleted(const TopoDS_Shape& theS)
772 {
773   Standard_Boolean bRet = Standard_True;
774   if (theS.IsNull()) {
775     return bRet;
776   }
777   //
778   TopAbs_ShapeEnum aType = theS.ShapeType();
779   if (!(aType==TopAbs_EDGE || aType==TopAbs_FACE || 
780       aType==TopAbs_VERTEX || aType==TopAbs_SOLID)) {
781     return bRet;
782   }
783   //
784   Standard_Boolean bHasImage, bHasGenerated;
785   //
786   bHasImage = myImages.IsBound(theS);
787   bHasGenerated = myMapGenerated.IsBound(theS);
788   if (!bHasImage && !bHasGenerated) {
789     bRet = !myMapShape.Contains(theS);
790     return bRet;
791   }
792   //
793   if (bHasGenerated) {
794     const TopoDS_Shape& aSG = myMapGenerated.Find(theS);
795     if (myMapShape.Contains(aSG)) {
796       bRet = Standard_False;
797       return bRet;
798     }
799   }
800   //
801   if (bHasImage) {
802     const BOPCol_ListOfShape& aLSp = myImages.Find(theS);
803     BOPCol_ListIteratorOfListOfShape aIt(aLSp);
804     for (; aIt.More(); aIt.Next()) {
805       const TopoDS_Shape& aSp = aIt.Value();
806       const TopoDS_Shape& aSpR = myShapesSD.IsBound(aSp) ? 
807         myShapesSD.Find(aSp) : aSp;
808       //
809       const TopoDS_Shape& aSpRG = myMapGenerated.IsBound(aSpR) ?
810         myMapGenerated.Find(aSpR) : aSpR;
811       if (myMapShape.Contains(aSpRG)) {
812         bRet = Standard_False;
813         break;
814       }
815     }
816   }
817   //
818   return bRet;
819 }
820
821 //=======================================================================
822 //function : Generated
823 //purpose  : 
824 //=======================================================================
825 const TopTools_ListOfShape& BOPAlgo_CellsBuilder::Generated(const TopoDS_Shape& theS)
826 {
827   myHistShapes.Clear();
828   if (theS.IsNull()) {
829     return myHistShapes;
830   }
831   //
832   TopAbs_ShapeEnum aType = theS.ShapeType();
833   if (!(aType==TopAbs_EDGE || aType==TopAbs_FACE || aType==TopAbs_VERTEX)) {
834     return myHistShapes;
835   }
836   //
837   Standard_Boolean bHasGenerated = myMapGenerated.IsBound(theS);
838   if (bHasGenerated) {
839     const TopoDS_Shape& aSG = myMapGenerated.Find(theS);
840     if (myMapShape.Contains(aSG)) {
841       myHistShapes.Append(aSG);
842     }
843     return myHistShapes;
844   }
845   //
846   Standard_Boolean bHasImage = myImages.IsBound(theS);
847   if (!bHasImage) {
848     return myHistShapes;
849   }
850   //
851   BOPCol_MapOfShape aMFence;
852   const BOPCol_ListOfShape& aLSp = myImages.Find(theS);
853   BOPCol_ListIteratorOfListOfShape aIt(aLSp);
854   for (; aIt.More(); aIt.Next()) {
855     const TopoDS_Shape aSp = aIt.Value();
856     const TopoDS_Shape& aSpR = myShapesSD.IsBound(aSp) ? 
857       myShapesSD.Find(aSp) : aSp;
858     //
859     if (myMapGenerated.IsBound(aSpR)) {
860       const TopoDS_Shape& aSG = myMapGenerated.Find(aSpR);
861       if (myMapShape.Contains(aSG)) {
862         if (aMFence.Add(aSG)) {
863           myHistShapes.Append(aSG);
864         }
865       }
866     }
867   }
868   //
869   return myHistShapes;
870 }
871
872 //=======================================================================
873 //function : MakeTypedContainers
874 //purpose  : 
875 //=======================================================================
876 void MakeTypedContainers(const TopoDS_Shape& theSC,
877                          const TopAbs_ShapeEnum aType,
878                          TopoDS_Shape& theResult)
879 {
880   TopAbs_ShapeEnum aContainerType, aConnexityType, aPartType;
881   //
882   aPartType = aType;
883   switch (aPartType) {
884     case TopAbs_EDGE: {
885       aContainerType = TopAbs_WIRE;
886       aConnexityType = TopAbs_VERTEX;
887       break;
888     }
889     case TopAbs_FACE: {
890       aContainerType = TopAbs_SHELL;
891       aConnexityType = TopAbs_EDGE;
892       break;
893     }
894     case TopAbs_SOLID: {
895       aContainerType = TopAbs_COMPSOLID;
896       aConnexityType = TopAbs_FACE;
897       break;
898     }
899     default:
900       return;
901   }
902   //
903   BOPCol_ListOfShape aLCB;
904   BOPTools_AlgoTools::MakeConnexityBlocks(theSC, aConnexityType, aPartType, aLCB);
905   if (aLCB.IsEmpty()) {
906     return;
907   }
908   //
909   BRep_Builder aBB;
910   TopExp_Explorer aExp;
911   BOPCol_ListIteratorOfListOfShape aItCB;
912   //
913   aItCB.Initialize(aLCB);
914   for (; aItCB.More(); aItCB.Next()) {
915     TopoDS_Shape aRCB;
916     BOPTools_AlgoTools::MakeContainer(aContainerType, aRCB);
917     //
918     const TopoDS_Shape& aCB = aItCB.Value();
919     aExp.Init(aCB, aPartType);
920     for (; aExp.More(); aExp.Next()) {
921       const TopoDS_Shape& aCBS = aExp.Current();
922       aBB.Add(aRCB, aCBS);
923     }
924     //
925     if (aContainerType == TopAbs_SHELL) {
926       BOPTools_AlgoTools::OrientFacesOnShell(aRCB);
927     }
928     //
929     aBB.Add(theResult, aRCB);
930   }
931 }
932
933 //=======================================================================
934 //function : TypeToExplore
935 //purpose  : 
936 //=======================================================================
937 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
938 {
939   TopAbs_ShapeEnum aRet;
940   //
941   switch(theDim) {
942   case 0:
943     aRet=TopAbs_VERTEX;
944     break;
945   case 1:
946     aRet=TopAbs_EDGE;
947     break;
948   case 2:
949     aRet=TopAbs_FACE;
950     break;
951   case 3:
952     aRet=TopAbs_SOLID;
953     break;
954   default:
955     aRet=TopAbs_SHAPE;
956     break;
957   }
958   return aRet;
959 }