0030386: Modeling Algorithms - Unable to perform Cut operation
[occt.git] / src / BOPAlgo / BOPAlgo_BOP.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 1999-2014 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_BOP.hxx>
17 #include <BOPAlgo_BuilderSolid.hxx>
18 #include <BOPAlgo_PaveFiller.hxx>
19 #include <BOPAlgo_Tools.hxx>
20 #include <BOPAlgo_Alerts.hxx>
21 #include <BOPDS_DS.hxx>
22 #include <BOPTools_AlgoTools.hxx>
23 #include <BOPTools_AlgoTools3D.hxx>
24 #include <BOPTools_IndexedDataMapOfSetShape.hxx>
25 #include <BOPTools_Set.hxx>
26 #include <BOPTools_SetMapHasher.hxx>
27 #include <BRep_Builder.hxx>
28 #include <BRep_Tool.hxx>
29 #include <NCollection_DataMap.hxx>
30 #include <TopAbs_ShapeEnum.hxx>
31 #include <TopExp.hxx>
32 #include <TopExp_Explorer.hxx>
33 #include <TopoDS.hxx>
34 #include <TopoDS_Compound.hxx>
35 #include <TopoDS_Edge.hxx>
36 #include <TopoDS_Iterator.hxx>
37 #include <TopoDS_Shape.hxx>
38 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
39 #include <TopTools_IndexedMapOfShape.hxx>
40 #include <TopTools_ListOfShape.hxx>
41 #include <TopTools_MapOfShape.hxx>
42
43 static
44   TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
45 //
46 static
47   void CollectContainers(const TopoDS_Shape& theS,
48                          TopTools_ListOfShape& theLSC);
49 //
50 static
51   void RemoveDuplicates(TopTools_ListOfShape& theContainers);
52 //
53 static
54   void RemoveDuplicates(TopTools_ListOfShape& theContainers,
55                         const TopAbs_ShapeEnum theType);
56 //
57 static
58   Standard_Integer NbCommonItemsInMap(const TopTools_MapOfShape& theM1,
59                                       const TopTools_MapOfShape& theM2);
60 //
61 static
62   void MapFacesToBuildSolids(const TopoDS_Shape& theSol,
63                              TopTools_IndexedDataMapOfShapeListOfShape& theMFS,
64                              TopTools_IndexedMapOfShape& theMFI);
65
66 //=======================================================================
67 //function : 
68 //purpose  : 
69 //=======================================================================
70 BOPAlgo_BOP::BOPAlgo_BOP()
71 : BOPAlgo_ToolsProvider()
72 {
73   Clear();
74 }
75 //=======================================================================
76 //function : 
77 //purpose  : 
78 //=======================================================================
79 BOPAlgo_BOP::BOPAlgo_BOP(const Handle(NCollection_BaseAllocator)& theAllocator)
80 : BOPAlgo_ToolsProvider(theAllocator)
81 {
82   Clear();
83 }
84 //=======================================================================
85 //function : ~
86 //purpose  : 
87 //=======================================================================
88 BOPAlgo_BOP::~BOPAlgo_BOP()
89 {
90 }
91 //=======================================================================
92 //function : Clear
93 //purpose  : 
94 //=======================================================================
95 void BOPAlgo_BOP::Clear()
96 {
97   myOperation=BOPAlgo_UNKNOWN;
98   myDims[0]=-1;
99   myDims[1]=-1;
100
101   BOPAlgo_ToolsProvider::Clear();
102 }
103 //=======================================================================
104 //function : SetOperation
105 //purpose  : 
106 //=======================================================================
107 void BOPAlgo_BOP::SetOperation(const BOPAlgo_Operation theOperation)
108 {
109   myOperation=theOperation;
110 }
111 //=======================================================================
112 //function : Operation
113 //purpose  : 
114 //=======================================================================
115 BOPAlgo_Operation BOPAlgo_BOP::Operation()const
116 {
117   return myOperation;
118 }
119 //=======================================================================
120 //function : CheckData
121 //purpose  : 
122 //=======================================================================
123 void BOPAlgo_BOP::CheckData()
124 {
125   Standard_Integer i, j, aNbArgs, aNbTools;
126   Standard_Boolean bFuse;
127   TopTools_ListIteratorOfListOfShape aItLS;
128   //
129   if (!(myOperation==BOPAlgo_COMMON ||
130         myOperation==BOPAlgo_FUSE || 
131         myOperation==BOPAlgo_CUT|| 
132         myOperation==BOPAlgo_CUT21)) {
133     // non-licit operation
134     AddError (new BOPAlgo_AlertBOPNotSet);
135     return;
136   }
137   //
138   aNbArgs=myArguments.Extent();
139   if (!aNbArgs) {
140     // invalid number of Arguments
141     AddError (new BOPAlgo_AlertTooFewArguments);
142     return;
143   }
144   //
145   aNbTools=myTools.Extent();
146   if (!aNbTools) { 
147     // invalid number of Tools
148     AddError (new BOPAlgo_AlertTooFewArguments);
149     return;
150   }
151   //
152   CheckFiller();
153   if (HasErrors()) {
154     return;
155   }
156   //
157   bFuse = (myOperation == BOPAlgo_FUSE);
158   //
159   // The rules for different types of operations are the following:
160   // 1. FUSE:   All arguments and tools should have the same dimension;
161   // 2. CUT:    The MAXIMAL dimension of the ARGUMENTS should be less
162   //            or equal to the MINIMAL dimension of the TOOLS;
163   // 3. CUT21:  The MINIMAL dimension of ARGUMENTS should be grater
164   //            or equal to the MAXIMAL dimension of the TOOLS;
165   // 4. COMMON: The arguments and tools could have any dimensions.
166   //
167   Standard_Integer iDimMin[2] = { 3, 3 },
168                    iDimMax[2] = { 0, 0 };
169   Standard_Boolean bHasValid[2] = {Standard_False, Standard_False};
170   //
171   for (i=0; i<2; ++i) {
172     const TopTools_ListOfShape& aLS=(!i)? myArguments : myTools;
173     aItLS.Initialize(aLS);
174     for (j=0; aItLS.More(); aItLS.Next(), ++j) {
175       const TopoDS_Shape& aS=aItLS.Value();
176       Standard_Boolean bIsEmpty = BOPTools_AlgoTools3D::IsEmptyShape(aS);
177       if (bIsEmpty)
178       {
179         AddWarning(new BOPAlgo_AlertEmptyShape (aS));
180         continue;
181       }
182
183       Standard_Integer iDMin, iDMax;
184       BOPTools_AlgoTools::Dimensions(aS, iDMin, iDMax);
185
186       if (iDMin < iDimMin[i])
187         iDimMin[i] = iDMin;
188       if (iDMax > iDimMax[i])
189         iDimMax[i] = iDMax;
190
191       if (bFuse && (iDimMin[i] != iDimMax[i]))
192       {
193         // non-homogeneous argument
194         AddError (new BOPAlgo_AlertBOPNotAllowed);
195         return;
196       }
197       bHasValid[i] = Standard_True;
198     }
199   }
200   //
201   if (bHasValid[0] && bHasValid[1]) {
202     if (((myOperation == BOPAlgo_FUSE)  && (iDimMax[0] != iDimMax[1])) ||
203         ((myOperation == BOPAlgo_CUT)   && (iDimMax[0] >  iDimMin[1])) ||
204         ((myOperation == BOPAlgo_CUT21) && (iDimMin[0] <  iDimMax[1])) )
205     {
206       // non-licit operation for the arguments
207       AddError (new BOPAlgo_AlertBOPNotAllowed);
208       return;
209     }
210   }
211
212   if (bHasValid[0] || bHasValid[1])
213   {
214     // In case of all empty shapes in one of the groups
215     // this group acquires the dimension of other group
216     myDims[0] = bHasValid[0] ? iDimMin[0] : iDimMin[1];
217     myDims[1] = bHasValid[1] ? iDimMin[1] : iDimMin[0];
218   }
219 }
220 //=======================================================================
221 //function : TreatEmtpyShape
222 //purpose  : 
223 //=======================================================================
224 Standard_Boolean BOPAlgo_BOP::TreatEmptyShape()
225 {
226   if (! GetReport()->HasAlert (STANDARD_TYPE(BOPAlgo_AlertEmptyShape)))
227   {
228     return Standard_False;
229   }
230   //
231   // Find non-empty objects
232   TopTools_ListOfShape aLValidObjs;
233   TopTools_ListIteratorOfListOfShape aItLS(myArguments);
234   for (; aItLS.More(); aItLS.Next()) {
235     if (!BOPTools_AlgoTools3D::IsEmptyShape(aItLS.Value())) {
236       aLValidObjs.Append(aItLS.Value());
237     }
238   }
239   //
240   // Find non-empty tools
241   TopTools_ListOfShape aLValidTools;
242   aItLS.Initialize(myTools);
243   for (; aItLS.More() ; aItLS.Next()) {
244     if (!BOPTools_AlgoTools3D::IsEmptyShape(aItLS.Value())) {
245       aLValidTools.Append(aItLS.Value());
246     }
247   }
248   //
249   Standard_Boolean bHasValidObj  = (aLValidObjs .Extent() > 0);
250   Standard_Boolean bHasValidTool = (aLValidTools.Extent() > 0);
251   //
252   if (bHasValidObj && bHasValidTool) {
253     // We need to continue the operation to obtain the result
254     return Standard_False;
255   }
256   //
257   if (!bHasValidObj && !bHasValidTool) {
258     // All shapes are empty shapes, the result will always be empty shape
259     return Standard_True;
260   }
261   //
262   // One of the groups of arguments consists of empty shapes only,
263   // so we can build the result of operation right away just by
264   // choosing the list of shapes to add to result, depending on
265   // the type of the operation.
266   // Although, if the group with valid shapes consists from more
267   // than just one shape, depending on the operation type we may need
268   // to split the shapes in this group before adding them into result.
269
270   TopTools_ListOfShape *pLResult = NULL;
271   //
272   switch (myOperation) {
273     case BOPAlgo_FUSE:
274     {
275       if (aLValidObjs.Extent() + aLValidTools.Extent() > 1)
276         // The arguments must be split before adding into result
277         return Standard_False;
278
279       // Add not empty shapes into result
280       pLResult = bHasValidObj ? &aLValidObjs : &aLValidTools;
281       break;
282     }
283     case BOPAlgo_CUT:
284     {
285       if (aLValidObjs.Extent() > 1)
286         // The objects must be split before adding into result
287         return Standard_False;
288
289       // Add objects into result
290       pLResult = &aLValidObjs;
291       break;
292     }
293     case BOPAlgo_CUT21:
294     {
295       if (aLValidTools.Extent() > 1)
296         // The tools must be split before adding into result
297         return Standard_False;
298
299       // Add tools into result
300       pLResult = &aLValidTools;
301       break;
302     }
303     case BOPAlgo_COMMON:
304       // Common will always be empty
305       break;
306     default:
307       break;
308   }
309   //
310   if (pLResult) {
311     aItLS.Initialize(*pLResult);
312     for (; aItLS.More(); aItLS.Next()) {
313       BRep_Builder().Add(myShape, aItLS.Value());
314     }
315   }
316   return Standard_True;
317 }
318 //=======================================================================
319 //function : BuildResult
320 //purpose  : 
321 //=======================================================================
322 void BOPAlgo_BOP::BuildResult(const TopAbs_ShapeEnum theType)
323 {
324   TopAbs_ShapeEnum aType;
325   BRep_Builder aBB;
326   TopTools_MapOfShape aM;
327   TopTools_ListIteratorOfListOfShape aIt, aItIm;
328   //
329   const TopTools_ListOfShape& aLA=myDS->Arguments();
330   aIt.Initialize(aLA);
331   for (; aIt.More(); aIt.Next()) {
332     const TopoDS_Shape& aS=aIt.Value();
333     aType=aS.ShapeType();
334     if (aType==theType) {
335       if (myImages.IsBound(aS)){
336         const TopTools_ListOfShape& aLSIm=myImages.Find(aS);
337         aItIm.Initialize(aLSIm);
338         for (; aItIm.More(); aItIm.Next()) {
339           const TopoDS_Shape& aSIm=aItIm.Value();
340           if (aM.Add(aSIm)) {
341             aBB.Add(myShape, aSIm);
342           }
343         }
344       }
345       else {
346         if (aM.Add(aS)) {
347           aBB.Add(myShape, aS);
348         }
349       }
350     }
351   }
352 }
353 //=======================================================================
354 //function : Perform
355 //purpose  : 
356 //=======================================================================
357 void BOPAlgo_BOP::Perform()
358 {
359   Handle(NCollection_BaseAllocator) aAllocator;
360   BOPAlgo_PaveFiller* pPF;
361   TopTools_ListIteratorOfListOfShape aItLS;
362   //
363   GetReport()->Clear();
364   //
365   if (myEntryPoint==1) {
366     if (myPaveFiller) {
367       delete myPaveFiller;
368       myPaveFiller=NULL;
369     }
370   }
371   //
372   aAllocator=
373     NCollection_BaseAllocator::CommonBaseAllocator();
374   TopTools_ListOfShape aLS(aAllocator);
375   //
376   aItLS.Initialize(myArguments);
377   for (; aItLS.More(); aItLS.Next()) {
378     const TopoDS_Shape& aS=aItLS.Value();
379     aLS.Append(aS);
380   }
381   //
382   aItLS.Initialize(myTools);
383   for (; aItLS.More(); aItLS.Next()) {
384     const TopoDS_Shape& aS=aItLS.Value();
385     aLS.Append(aS);
386   }
387   //
388   pPF=new BOPAlgo_PaveFiller(aAllocator);
389   pPF->SetArguments(aLS);
390   pPF->SetRunParallel(myRunParallel);
391   pPF->SetProgressIndicator(myProgressIndicator);
392   pPF->SetFuzzyValue(myFuzzyValue);
393   pPF->SetNonDestructive(myNonDestructive);
394   pPF->SetGlue(myGlue);
395   pPF->SetUseOBB(myUseOBB);
396   //
397   pPF->Perform();
398   //
399   myEntryPoint=1;
400   PerformInternal(*pPF);
401 }
402 //=======================================================================
403 //function : PerformInternal1
404 //purpose  : 
405 //=======================================================================
406 void BOPAlgo_BOP::PerformInternal1(const BOPAlgo_PaveFiller& theFiller)
407 {
408   myPaveFiller=(BOPAlgo_PaveFiller*)&theFiller;
409   myDS=myPaveFiller->PDS();
410   myContext=myPaveFiller->Context();
411   myFuzzyValue = myPaveFiller->FuzzyValue();
412   myNonDestructive = myPaveFiller->NonDestructive();
413   //
414   // 1. CheckData
415   CheckData();
416   if (HasErrors()) {
417     return;
418   }
419   //
420   // 2. Prepare
421   Prepare();
422   if (HasErrors()) {
423     return;
424   }
425   //
426   if (GetReport()->HasAlert (STANDARD_TYPE(BOPAlgo_AlertEmptyShape)))
427   {
428     Standard_Boolean bDone = TreatEmptyShape();
429     if (bDone) {
430       PrepareHistory();
431       return;
432     }
433   }
434   //
435   // 3. Fill Images
436   // 3.1 Vertices
437   FillImagesVertices();
438   if (HasErrors()) {
439     return;
440   }
441   //
442   BuildResult(TopAbs_VERTEX);
443   if (HasErrors()) {
444     return;
445   }
446   // 3.2 Edges
447   FillImagesEdges();
448   if (HasErrors()) {
449     return;
450   }
451   //
452   BuildResult(TopAbs_EDGE);
453   if (HasErrors()) {
454     return;
455   }
456   //
457   // 3.3 Wires
458   FillImagesContainers(TopAbs_WIRE);
459   if (HasErrors()) {
460     return;
461   }
462   //
463   BuildResult(TopAbs_WIRE);
464   if (HasErrors()) {
465     return;
466   }
467   //
468   // 3.4 Faces
469   FillImagesFaces();
470   if (HasErrors()) {
471     return;
472   }
473   
474   BuildResult(TopAbs_FACE);
475   if (HasErrors()) {
476     return;
477   }
478   //
479   // 3.5 Shells
480   FillImagesContainers(TopAbs_SHELL);
481   if (HasErrors()) {
482     return;
483   }
484   //
485   BuildResult(TopAbs_SHELL);
486   if (HasErrors()) {
487     return;
488   }
489   //
490   // 3.6 Solids
491   FillImagesSolids();
492   if (HasErrors()) {
493     return;
494   }
495   //
496   BuildResult(TopAbs_SOLID);
497   if (HasErrors()) {
498     return;
499   }
500   //
501   // 3.7 CompSolids
502   FillImagesContainers(TopAbs_COMPSOLID);
503   if (HasErrors()) {
504     return;
505   }
506   //
507   BuildResult(TopAbs_COMPSOLID);
508   if (HasErrors()) {
509     return;
510   }
511   //
512   // 3.8 Compounds
513   FillImagesCompounds();
514   if (HasErrors()) {
515     return;
516   }
517   //
518   BuildResult(TopAbs_COMPOUND);
519   if (HasErrors()) {
520     return;
521   }
522   //
523   // 4.BuildShape;
524   BuildShape();
525   if (HasErrors()) {
526     return;
527   }
528   // 
529   // 5.History
530   PrepareHistory();
531   //
532   // 6 Post-treatment 
533   PostTreat();
534 }
535 //=======================================================================
536 //function : BuildRC
537 //purpose  : 
538 //=======================================================================
539 void BOPAlgo_BOP::BuildRC()
540 {
541   TopAbs_ShapeEnum aType;
542   TopoDS_Compound aC;
543   BRep_Builder aBB;
544   //
545   aBB.MakeCompound(aC);
546   //
547   // A. Fuse
548   if (myOperation == BOPAlgo_FUSE) {
549     TopTools_MapOfShape aMFence;
550     aType = TypeToExplore(myDims[0]);
551     TopExp_Explorer aExp(myShape, aType);
552     for (; aExp.More(); aExp.Next()) {
553       const TopoDS_Shape& aS = aExp.Current();
554       if (aMFence.Add(aS)) {
555         aBB.Add(aC, aS);
556       }
557     }
558     myRC = aC;
559     return;
560   }
561   //
562   // B. Common, Cut, Cut21
563   //
564   Standard_Integer i, j, aNb, iDim;
565   Standard_Boolean bCheckEdges, bContains, bCut21, bCommon;
566   TopTools_ListIteratorOfListOfShape aItLS;
567   //
568   // prepare the building elements of arguments to get its splits
569   TopTools_IndexedMapOfShape aMArgs, aMTools;
570   for (i = 0; i < 2; ++i) {
571     const TopTools_ListOfShape& aLS = !i ? myArguments : myTools;
572     TopTools_IndexedMapOfShape& aMS = !i ? aMArgs : aMTools;
573     aItLS.Initialize(aLS);
574     for (; aItLS.More(); aItLS.Next()) {
575       const TopoDS_Shape& aS = aItLS.Value();
576       TopTools_ListOfShape aList;
577       BOPTools_AlgoTools::TreatCompound (aS, aList);
578       for (TopTools_ListOfShape::Iterator itList (aList); itList.More(); itList.Next())
579       {
580         const TopoDS_Shape& aSS = itList.Value();
581         iDim = BOPTools_AlgoTools::Dimension (aSS);
582         if (iDim < 0)
583           continue;
584         aType = TypeToExplore (iDim);
585         TopExp::MapShapes (aSS, aType, aMS);
586       }
587     }
588   }
589   //
590   bCheckEdges = Standard_False;
591   //
592   // get splits of building elements
593   TopTools_IndexedMapOfShape aMArgsIm, aMToolsIm;
594   BOPTools_IndexedDataMapOfSetShape aMSetArgs, aMSetTools;
595
596   for (i = 0; i < 2; ++i) {
597     const TopTools_IndexedMapOfShape& aMS = !i ? aMArgs : aMTools;
598     TopTools_IndexedMapOfShape& aMSIm = !i ? aMArgsIm : aMToolsIm;
599     BOPTools_IndexedDataMapOfSetShape& aMSet = !i ? aMSetArgs : aMSetTools;
600     //
601     aNb = aMS.Extent();
602     for (j = 1; j <= aNb; ++j) {
603       const TopoDS_Shape& aS = aMS(j);
604       aType = aS.ShapeType();
605       if (aType == TopAbs_EDGE) {
606         const TopoDS_Edge& aE = *(TopoDS_Edge*)&aS;
607         bCheckEdges = Standard_True;
608         if (BRep_Tool::Degenerated(aE)) {
609           continue;
610         }
611       }
612       //
613       if (myImages.IsBound(aS)) {
614         const TopTools_ListOfShape& aLSIm = myImages.Find(aS);
615         aItLS.Initialize(aLSIm);
616         for (; aItLS.More(); aItLS.Next()) {
617           const TopoDS_Shape& aSIm = aItLS.Value();
618           aMSIm.Add(aSIm);
619         }
620       }
621       else {
622         aMSIm.Add(aS);
623         if (aS.ShapeType() == TopAbs_SOLID) {
624           BOPTools_Set aST;
625           aST.Add(aS, TopAbs_FACE);
626           if (!aMSet.Contains(aST)) {
627             aMSet.Add(aST, aS);
628           }
629         }
630       }
631     }
632   }
633   //
634   // compare the maps and make the result
635   //
636   Standard_Integer iDimMin, iDimMax;
637   //
638   iDimMin = Min(myDims[0], myDims[1]);
639   bCommon = (myOperation == BOPAlgo_COMMON);
640   bCut21  = (myOperation == BOPAlgo_CUT21);
641   //
642   const TopTools_IndexedMapOfShape& aMIt = bCut21 ? aMToolsIm : aMArgsIm;
643   const TopTools_IndexedMapOfShape& aMCheck = bCut21 ? aMArgsIm : aMToolsIm;
644   const BOPTools_IndexedDataMapOfSetShape& aMSetCheck = bCut21 ? aMSetArgs : aMSetTools;
645   //
646   TopTools_IndexedMapOfShape aMCheckExp, aMItExp;
647   //
648   if (bCommon) {
649     aNb = aMIt.Extent();
650     for (i = 1; i <= aNb; ++i) {
651       const TopoDS_Shape& aS = aMIt(i);
652       iDimMax = BOPTools_AlgoTools::Dimension(aS);
653       for (iDim = iDimMin; iDim < iDimMax; ++iDim) {
654         aType = TypeToExplore(iDim);
655         TopExp::MapShapes(aS, aType, aMItExp);
656       }
657       aMItExp.Add(aS);
658     }
659   }
660   else {
661     aMItExp = aMIt;
662   }
663   //
664   aNb = aMCheck.Extent();
665   for (i = 1; i <= aNb; ++i) {
666     const TopoDS_Shape& aS = aMCheck(i);
667     iDimMax = BOPTools_AlgoTools::Dimension(aS);
668     for (iDim = iDimMin; iDim < iDimMax; ++iDim) {
669       aType = TypeToExplore(iDim);
670       TopExp::MapShapes(aS, aType, aMCheckExp);
671     }
672     aMCheckExp.Add(aS);
673   }
674   //
675   aNb = aMItExp.Extent();
676   for (i = 1; i <= aNb; ++i) {
677     const TopoDS_Shape& aS = aMItExp(i);
678     //
679     bContains = aMCheckExp.Contains(aS);
680     if (!bContains && aS.ShapeType() == TopAbs_SOLID) {
681       BOPTools_Set aST;
682       aST.Add(aS, TopAbs_FACE);
683       bContains = aMSetCheck.Contains(aST);
684     }
685     //
686     if (bCommon) {
687       if (bContains) {
688         aBB.Add(aC, aS);
689       }
690     }
691     else {
692       if (!bContains) {
693         aBB.Add(aC, aS);
694       }
695     }
696   }
697   //
698   // filter result for COMMON operation
699   if (bCommon) {
700     TopTools_MapOfShape aMFence;
701     TopExp_Explorer aExp;
702     TopoDS_Compound aCx;
703     aBB.MakeCompound(aCx);
704     //
705     for (iDim = 3; iDim >= iDimMin; --iDim) {
706       aType = TypeToExplore(iDim);
707       aExp.Init(aC, aType);
708       for (; aExp.More(); aExp.Next()) {
709         const TopoDS_Shape& aS = aExp.Current();
710         if (aMFence.Add(aS)) {
711           aBB.Add(aCx, aS);
712           TopExp::MapShapes(aS, aMFence);
713         }
714       }
715     }
716     aC = aCx;
717   }
718   //
719   if (!bCheckEdges) {
720     myRC = aC;
721     return;
722   }
723   //
724   // The squats around degenerated edges
725   Standard_Integer nVD;
726   TopTools_IndexedMapOfShape aMVC;
727   //
728   // 1. Vertices of aC
729   TopExp::MapShapes(aC, TopAbs_VERTEX, aMVC);
730   //
731   // 2. DE candidates
732   aNb = myDS->NbSourceShapes();
733   for (i = 0; i < aNb; ++i) {
734     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
735     aType = aSI.ShapeType();
736     if (aType != TopAbs_EDGE) {
737       continue;
738     }
739     //
740     const TopoDS_Edge& aE = *((TopoDS_Edge*)&aSI.Shape());
741     if (!BRep_Tool::Degenerated(aE)) {
742       continue;
743     }
744     //
745     nVD = aSI.SubShapes().First();
746     const TopoDS_Shape& aVD = myDS->Shape(nVD);
747     //
748     if (!aMVC.Contains(aVD)) {
749       continue;
750     }
751     //
752     if (myDS->IsNewShape(nVD)) {
753       continue;
754     }
755     //
756     if (myDS->HasInterf(nVD)) {
757       continue;
758     }
759     //
760     aBB.Add(aC, aE);
761   }
762   //
763   myRC=aC;
764 }
765 //=======================================================================
766 //function : BuildShape
767 //purpose  : 
768 //=======================================================================
769 void BOPAlgo_BOP::BuildShape()
770 {
771   if (myDims[0] == 3 && myDims[1] == 3)
772   {
773     // For the Boolean operation on solids we need to check first
774     // if we are dealing with closed solids, because for open solids
775     // we cannot expect the BuilderSolid algorithm to produce good
776     // splits for them and have to try the alternative approach for
777     // building the result shape.
778     // This approach is not used by default as it will loose the
779     // modification history for solids, because the result solid
780     // will be built from scratch using the splits of faces.
781     Standard_Boolean hasNotClosedSolids = CheckArgsForOpenSolid();
782     if (hasNotClosedSolids)
783     {
784       Handle(Message_Report) aReport = new Message_Report();
785       BuildBOP(myArguments, myTools, myOperation, aReport);
786       if (aReport->GetAlerts(Message_Fail).IsEmpty())
787       {
788         // Success. Merge the report into the main report.
789         myReport->Merge(aReport);
790         return;
791       }
792     }
793   }
794
795   // Build the result using splits of arguments.
796
797   BuildRC();
798   //
799   if ((myOperation == BOPAlgo_FUSE) && (myDims[0] == 3)) {
800     BuildSolid();
801     return;
802   }
803   //
804   Standard_Integer i;
805   TopAbs_ShapeEnum aType, aT1, aT2;
806   TopTools_ListOfShape aLSC, aLCB;
807   TopTools_ListIteratorOfListOfShape aItLS, aItLSIm, aItLCB;
808   TopoDS_Iterator aIt;
809   BRep_Builder aBB;
810   TopoDS_Shape aRC, aRCB;
811   //
812   TopTools_MapOfShape aMSRC;
813   TopExp::MapShapes(myRC, aMSRC);
814   //
815   // collect images of containers
816   for (i = 0; i < 2; ++i) {
817     const TopTools_ListOfShape& aLS = !i ? myArguments : myTools;
818     //
819     aItLS.Initialize(aLS);
820     for (; aItLS.More(); aItLS.Next()) {
821       const TopoDS_Shape& aS = aItLS.Value();
822       //
823       CollectContainers(aS, aLSC);
824     }
825   }
826   // make containers
827   TopTools_ListOfShape aLCRes;
828   TopTools_MapOfShape aMInpFence;
829   aItLS.Initialize(aLSC);
830   for (; aItLS.More(); aItLS.Next()) {
831     const TopoDS_Shape& aSC = aItLS.Value();
832     aMInpFence.Add(aSC);
833     //
834     BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
835     //
836     aIt.Initialize(aSC);
837     for (; aIt.More(); aIt.Next()) {
838       const TopoDS_Shape& aS = aIt.Value();
839       if (myImages.IsBound(aS)) {
840         const TopTools_ListOfShape& aLSIm = myImages.Find(aS);
841         //
842         aItLSIm.Initialize(aLSIm);
843         for (; aItLSIm.More(); aItLSIm.Next()) {
844           const TopoDS_Shape& aSIm = aItLSIm.Value();
845           if (aMSRC.Contains(aSIm)) {
846             aBB.Add(aRC, aSIm);
847           }
848         }
849       }
850       else if (aMSRC.Contains(aS)) {
851         aBB.Add(aRC, aS);
852       }
853     }
854     //
855     aType = aSC.ShapeType();
856     switch (aType) {
857       case TopAbs_WIRE: {
858         aT1 = TopAbs_VERTEX;
859         aT2 = TopAbs_EDGE;
860         break;
861       }
862       case TopAbs_SHELL: {
863         aT1 = TopAbs_EDGE;
864         aT2 = TopAbs_FACE;
865         break;
866       }
867       default: {
868         aT1 = TopAbs_FACE;
869         aT2 = TopAbs_SOLID;
870       }
871     }
872     //
873     aLCB.Clear();
874     BOPTools_AlgoTools::MakeConnexityBlocks(aRC, aT1, aT2, aLCB);
875     if (aLCB.IsEmpty()) {
876       continue;
877     }
878     //
879     aItLCB.Initialize(aLCB);
880     for (; aItLCB.More(); aItLCB.Next()) {
881       BOPTools_AlgoTools::MakeContainer(aType, aRCB);
882       //
883       const TopoDS_Shape& aCB = aItLCB.Value();
884       aIt.Initialize(aCB);
885       for (; aIt.More(); aIt.Next()) {
886         const TopoDS_Shape& aCBS = aIt.Value();
887         aBB.Add(aRCB, aCBS);
888       }
889       //
890       if (aType == TopAbs_WIRE) {
891         // reorient wire
892         BOPTools_AlgoTools::OrientEdgesOnWire(aRCB);
893       }
894       else if (aType == TopAbs_SHELL) {
895         BOPTools_AlgoTools::OrientFacesOnShell(aRCB);
896       }
897       //
898       aRCB.Orientation(aSC.Orientation());
899       //
900       aLCRes.Append(aRCB);
901     }
902   }
903   //
904   RemoveDuplicates(aLCRes);
905   //
906   // add containers to result
907   TopoDS_Compound aResult;
908   aBB.MakeCompound(aResult);
909   //
910   aItLS.Initialize(aLCRes);
911   for (; aItLS.More(); aItLS.Next()) {
912     aBB.Add(aResult, aItLS.Value());
913   }
914
915   // create map of containers
916   TopTools_MapOfShape aMSResult;
917   TopExp::MapShapes(aResult, aMSResult);
918
919   // get input non-container shapes
920   TopTools_ListOfShape aLSNonCont;
921   for (i = 0; i < 2; ++i)
922   {
923     const TopTools_ListOfShape& aLS = !i ? myArguments : myTools;
924     aItLS.Initialize(aLS);
925     for (; aItLS.More(); aItLS.Next())
926     {
927       const TopoDS_Shape& aS = aItLS.Value();
928       BOPTools_AlgoTools::TreatCompound(aS, aLSNonCont, &aMInpFence);
929     }
930   }
931
932   // put non-container shapes in the result
933   aItLS.Initialize(aLSNonCont);
934   for (; aItLS.More(); aItLS.Next())
935   {
936     const TopoDS_Shape& aS = aItLS.Value();
937     if (myImages.IsBound(aS))
938     {
939       const TopTools_ListOfShape& aLSIm = myImages.Find(aS);
940       aItLSIm.Initialize(aLSIm);
941       for (; aItLSIm.More(); aItLSIm.Next())
942       {
943         const TopoDS_Shape& aSIm = aItLSIm.Value();
944         if (aMSRC.Contains(aSIm) && aMSResult.Add(aSIm))
945           aBB.Add(aResult, aSIm);
946       }
947     }
948     else if (aMSRC.Contains(aS) && aMSResult.Add(aS))
949       aBB.Add(aResult, aS);
950   }
951
952   myShape = aResult;
953 }
954 //=======================================================================
955 //function : BuildSolid
956 //purpose  : 
957 //=======================================================================
958 void BOPAlgo_BOP::BuildSolid()
959 {
960   // Containers
961   TopTools_ListOfShape aLSC;
962   //
963   TopTools_ListIteratorOfListOfShape aItLS;
964   TopExp_Explorer aExp;
965   BRep_Builder aBB;
966   //
967   // Get solids from input arguments
968   TopTools_MapOfShape aMSA;
969   // Map the arguments to find shared faces
970   TopTools_IndexedDataMapOfShapeListOfShape aMFS;
971   for (Standard_Integer i = 0; i < 2; ++i) {
972     const TopTools_ListOfShape& aLSA = (i) ? myArguments : myTools;
973     aItLS.Initialize(aLSA);
974     for (; aItLS.More(); aItLS.Next()) {
975       const TopoDS_Shape& aSA = aItLS.Value();
976       aExp.Init(aSA, TopAbs_SOLID);
977       for (; aExp.More(); aExp.Next()) {
978         const TopoDS_Shape& aSol = aExp.Current();
979         aMSA.Add(aSol);
980         TopExp::MapShapesAndAncestors(aSol, TopAbs_FACE, TopAbs_SOLID, aMFS);
981       }
982       //
983       // get Compsolids from input arguments
984       CollectContainers(aSA, aLSC);
985     }
986   }
987   //
988   // Find solids in input arguments sharing faces with other solids
989   TopTools_MapOfShape aMTSols;
990   Standard_Integer i, aNb = aMFS.Extent();
991   for (i = 1; i < aNb; ++i) {
992     const TopTools_ListOfShape& aLSols = aMFS(i);
993     if (aLSols.Extent() > 1) {
994       aItLS.Initialize(aLSols);
995       for(; aItLS.More(); aItLS.Next()) {
996         aMTSols.Add(aItLS.Value());
997       }
998     }
999   }
1000   //
1001   // Possibly untouched solids - to be added to results as is
1002   TopTools_IndexedMapOfShape aMUSols;
1003   // Use map to chose the most outer faces to build result solids
1004   aMFS.Clear();
1005   // Internal faces
1006   TopTools_IndexedMapOfShape aMFI;
1007   //
1008   TopoDS_Iterator aIt(myRC);
1009   for (; aIt.More(); aIt.Next()) {
1010     const TopoDS_Shape& aSx = aIt.Value();
1011     if (aMSA.Contains(aSx)) {
1012       if (!aMTSols.Contains(aSx)) {
1013         aMUSols.Add(aSx);
1014         continue;
1015       }
1016     }
1017     //
1018     MapFacesToBuildSolids(aSx, aMFS, aMFI);
1019   } // for (; aIt.More(); aIt.Next()) {
1020   //
1021   // Process possibly untouched solids.
1022   // Really untouched solids will be added into result as is.
1023   // Others will be processed by BuilderSolid.
1024   BOPTools_IndexedDataMapOfSetShape aDMSTS;
1025   //
1026   aNb = aMUSols.Extent();
1027   for (i = 1; i <= aNb; ++i) {
1028     const TopoDS_Shape& aSx = aMUSols(i);
1029     //
1030     aExp.Init(aSx, TopAbs_FACE);
1031     for (; aExp.More(); aExp.Next()) {
1032       if (aMFS.Contains(aExp.Current())) {
1033         break;
1034       }
1035     }
1036     //
1037     if (aExp.More()) {
1038       MapFacesToBuildSolids(aSx, aMFS, aMFI);
1039     }
1040     else {
1041       BOPTools_Set aST;
1042       aST.Add(aSx, TopAbs_FACE);
1043       if (!aDMSTS.Contains(aST)) {
1044         aDMSTS.Add(aST, aSx);
1045       }
1046     }
1047   }
1048   //
1049   TopTools_IndexedDataMapOfShapeListOfShape aMEF;
1050   // Fill the list of faces to build the result solids
1051   TopTools_ListOfShape aSFS;
1052   aNb = aMFS.Extent();
1053   for (i = 1; i <= aNb; ++i) {
1054     const TopTools_ListOfShape& aLSx = aMFS(i);
1055     if (aLSx.Extent() == 1) {
1056       const TopoDS_Shape& aFx = aMFS.FindKey(i);
1057       TopExp::MapShapesAndAncestors(aFx, TopAbs_EDGE, TopAbs_FACE, aMEF);
1058       aSFS.Append(aFx);
1059     }
1060   }
1061   // Internal faces
1062   aNb = aMFI.Extent();
1063   for (i = 1; i <= aNb; ++i) {
1064     TopoDS_Shape aFx = aMFI.FindKey(i);
1065     aSFS.Append(aFx.Oriented(TopAbs_FORWARD));
1066     aSFS.Append(aFx.Oriented(TopAbs_REVERSED));
1067   }
1068   //
1069   TopoDS_Shape aRC;
1070   BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
1071   if (aSFS.Extent()) {
1072     // Build solids from set of faces
1073     BOPAlgo_BuilderSolid aBS;
1074     aBS.SetContext(myContext);
1075     aBS.SetShapes(aSFS);
1076     aBS.Perform();
1077     if (aBS.HasErrors()) {
1078       AddError (new BOPAlgo_AlertSolidBuilderFailed); // SolidBuilder failed
1079       return;
1080     }
1081
1082     myReport->Merge(aBS.GetReport());
1083
1084     // new solids
1085     const TopTools_ListOfShape& aLSR = aBS.Areas();
1086     //
1087     // add new solids to result
1088     aItLS.Initialize(aLSR);
1089     for (; aItLS.More(); aItLS.Next()) {
1090       const TopoDS_Shape& aSR = aItLS.Value();
1091       aBB.Add(aRC, aSR);
1092     }
1093   }
1094   //
1095   // add untouched solids to result
1096   aNb = aDMSTS.Extent();
1097   for (i = 1; i <= aNb; ++i) {
1098     const TopoDS_Shape& aSx = aDMSTS(i);
1099     aBB.Add(aRC, aSx);
1100   }
1101   //
1102   if (aLSC.IsEmpty()) {
1103     // no Compsolids in arguments
1104     myShape = aRC;
1105     return;
1106   }
1107   //
1108   // build new Compsolids from new solids containing splits
1109   // of faces from arguments of type Compsolid
1110   //
1111   TopoDS_Shape aResult;
1112   BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aResult);
1113   //
1114   aIt.Initialize(aRC);
1115   if (!aIt.More()) {
1116     // no solids in the result
1117     myShape = aRC;
1118     return;
1119   }
1120   //
1121   const TopoDS_Shape& aSol1 = aIt.Value();
1122   aIt.Next();
1123   //
1124   // optimization for one solid in the result
1125   if (!aIt.More()) {
1126     TopoDS_Shape aCS;
1127     BOPTools_AlgoTools::MakeContainer(TopAbs_COMPSOLID, aCS);
1128     aBB.Add(aCS, aSol1);
1129     //
1130     aBB.Add(aResult, aCS);
1131     myShape = aResult;
1132     return;
1133   }
1134   //
1135   // get splits of faces of the Compsolid arguments
1136   TopTools_MapOfShape aMFCs;
1137   aItLS.Initialize(aLSC);
1138   for (; aItLS.More(); aItLS.Next()) {
1139     const TopoDS_Shape& aCs = aItLS.Value();
1140     aExp.Init(aCs, TopAbs_FACE);
1141     for (; aExp.More(); aExp.Next()) {
1142       const TopoDS_Shape& aF = aExp.Current();
1143       const TopTools_ListOfShape* pLFIm = myImages.Seek(aF);
1144       if (!pLFIm) {
1145         aMFCs.Add(aF);
1146       }
1147       else {
1148         TopTools_ListIteratorOfListOfShape aItLFIm(*pLFIm);
1149         for (; aItLFIm.More(); aItLFIm.Next()) {
1150           aMFCs.Add(aItLFIm.Value());
1151         }
1152       }
1153     }
1154   }
1155   //
1156   // build connexity blocks from new solids
1157   TopTools_ListOfShape aLCBS;
1158   BOPTools_AlgoTools::MakeConnexityBlocks(aRC, TopAbs_FACE, TopAbs_SOLID, aLCBS);
1159   //
1160   aItLS.Initialize(aLCBS);
1161   for (; aItLS.More(); aItLS.Next()) {
1162     const TopoDS_Shape& aCB = aItLS.Value();
1163     //
1164     // check if the Compsolid should be created
1165     aExp.Init(aCB, TopAbs_FACE);
1166     for (; aExp.More(); aExp.Next()) {
1167       if (aMFCs.Contains(aExp.Current())) {
1168         break;
1169       }
1170     }
1171     //
1172     if (!aExp.More()) {
1173       // add solids directly into result as their origins are not Compsolids
1174       for (aIt.Initialize(aCB); aIt.More(); aIt.Next()) {
1175         aBB.Add(aResult, aIt.Value());
1176       }
1177       continue;
1178     }
1179     //
1180     // make Compsolid
1181     TopoDS_Shape aCS;
1182     BOPTools_AlgoTools::MakeContainer(TopAbs_COMPSOLID, aCS);
1183     //
1184     aIt.Initialize(aCB);
1185     for (; aIt.More(); aIt.Next()) {
1186       aBB.Add(aCS, aIt.Value());
1187     }
1188     //
1189     aBB.Add(aResult, aCS);
1190   }
1191   //
1192   myShape = aResult;
1193 }
1194
1195 //=======================================================================
1196 //function : CheckArgsForOpenSolid
1197 //purpose  : 
1198 //=======================================================================
1199 Standard_Boolean BOPAlgo_BOP::CheckArgsForOpenSolid()
1200 {
1201   // Analyze the report to find if BuilderSolid has generated warnings
1202   // for any of the solids and collect these solids to check if they are open.
1203   TopTools_MapOfShape aFailedSolids;
1204   {
1205     const Message_ListOfAlert& aList = myReport->GetAlerts(Message_Warning);
1206     for (Message_ListOfAlert::Iterator aIt(aList); aIt.More(); aIt.Next())
1207     {
1208       const Handle(Standard_Type)& aType = aIt.Value()->DynamicType();
1209       if (aType != STANDARD_TYPE(BOPAlgo_AlertSolidBuilderUnusedFaces))
1210         continue;
1211
1212       Handle(TopoDS_AlertWithShape) aShapeAlert = Handle(TopoDS_AlertWithShape)::DownCast(aIt.Value());
1213       if (!aShapeAlert.IsNull())
1214       {
1215         const TopoDS_Shape& aWarnShape = aShapeAlert->GetShape();
1216         if (!aWarnShape.IsNull())
1217         {
1218           TopExp_Explorer expS(aWarnShape, TopAbs_SOLID);
1219           for (; expS.More(); expS.Next())
1220             aFailedSolids.Add(expS.Current());
1221         }
1222       }
1223     }
1224   }
1225
1226   // Iterate on all solids from the arguments and check if any
1227   // of them are not closed.
1228   // At the same time, collect all internal faces of the input solids
1229   // to check if the splits of open solids did not acquire any new
1230   // internal faces.
1231
1232   const Standard_Integer aNbS = myDS->NbSourceShapes();
1233   for (Standard_Integer i = 0; i < aNbS; ++i)
1234   {
1235     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
1236     if (aSI.ShapeType() != TopAbs_SOLID)
1237       continue;
1238
1239     const TopoDS_Shape& aSolid = aSI.Shape();
1240
1241     // Check that not INTERNAL faces create closed loops
1242     TopTools_IndexedDataMapOfShapeListOfShape aMEF;
1243     // Collect all splits of internal faces
1244     TopTools_MapOfShape aMFInternal;
1245
1246     for (TopoDS_Iterator itSh(aSolid); itSh.More(); itSh.Next())
1247     {
1248       const TopoDS_Shape& aSh = itSh.Value();
1249       if (aSh.ShapeType() != TopAbs_SHELL)
1250         continue;
1251
1252       for (TopoDS_Iterator itF(aSh); itF.More(); itF.Next())
1253       {
1254         const TopoDS_Shape& aF = itF.Value();
1255         if (aF.Orientation() == TopAbs_INTERNAL)
1256         {
1257           const TopTools_ListOfShape* pLFIm = myImages.Seek(aF);
1258           if (pLFIm)
1259           {
1260             TopTools_ListOfShape::Iterator itLFIm(*pLFIm);
1261             for (; itLFIm.More(); itLFIm.Next())
1262               aMFInternal.Add(itLFIm.Value());
1263           }
1264           else
1265             aMFInternal.Add(aF);
1266         }
1267         else
1268           TopExp::MapShapesAndAncestors(aF, TopAbs_EDGE, TopAbs_FACE, aMEF);
1269       }
1270     }
1271
1272     // Analyze the Edge-Face connection map on free edges
1273     Standard_Boolean isClosed = Standard_True;
1274     const Standard_Integer aNbE = aMEF.Extent();
1275     for (Standard_Integer j = 1; j <= aNbE && isClosed; ++j)
1276     {
1277       const TopoDS_Edge& aE = TopoDS::Edge(aMEF.FindKey(j));
1278       if (BRep_Tool::Degenerated(aE))
1279         // Skip degenerated edges
1280         continue;
1281
1282       isClosed = (aMEF(j).Extent() > 1);
1283       if (!isClosed)
1284       {
1285         const TopoDS_Face& aF = TopoDS::Face(aMEF(j).First());
1286         isClosed = BRep_Tool::IsClosed(aE, aF); // Check for seam edges
1287         if (!isClosed)
1288         {
1289           // Check if the edge is not internal in the face
1290           TopExp_Explorer expE(aF, TopAbs_EDGE);
1291           for (; expE.More(); expE.Next())
1292           {
1293             if (expE.Current().IsSame(aE))
1294             {
1295               isClosed = (expE.Current().Orientation() == TopAbs_INTERNAL);
1296               break;
1297             }
1298           }
1299         }
1300       }
1301     }
1302
1303     if (isClosed)
1304       continue;
1305
1306     // Not closed solid is found
1307
1308     if (aFailedSolids.Contains(aSolid))
1309       // Warning has been generated for this solid, return positive result right away.
1310       return Standard_True;
1311
1312     
1313     // Check the splits not to acquire new INTERNAL faces
1314     const TopTools_ListOfShape *pLSIm = myImages.Seek(aSolid);
1315     if (!pLSIm)
1316       continue;
1317
1318     TopTools_ListOfShape::Iterator itLSIm(*pLSIm);
1319     for (; itLSIm.More(); itLSIm.Next())
1320     {
1321       const TopoDS_Shape& aSIm = itLSIm.Value();
1322       for (TopoDS_Iterator itSh(aSIm); itSh.More(); itSh.Next())
1323       {
1324         const TopoDS_Shape& aSh = itSh.Value();
1325         if (aSh.ShapeType() != TopAbs_SHELL)
1326           continue;
1327
1328         for (TopoDS_Iterator itF(aSh); itF.More(); itF.Next())
1329         {
1330           const TopoDS_Shape& aF = itF.Value();
1331           if (aF.Orientation() == TopAbs_INTERNAL)
1332           {
1333             if (!aMFInternal.Contains(aF))
1334               // New internal face is found
1335               return Standard_True;
1336           }
1337         }
1338       }
1339     }
1340   }
1341
1342   return Standard_False;
1343 }
1344
1345 //=======================================================================
1346 //function : TypeToExplore
1347 //purpose  : 
1348 //=======================================================================
1349 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
1350 {
1351   TopAbs_ShapeEnum aRet;
1352   //
1353   switch(theDim) {
1354   case 0:
1355     aRet=TopAbs_VERTEX;
1356     break;
1357   case 1:
1358     aRet=TopAbs_EDGE;
1359     break;
1360   case 2:
1361     aRet=TopAbs_FACE;
1362     break;
1363   case 3:
1364     aRet=TopAbs_SOLID;
1365     break;
1366   default:
1367     aRet=TopAbs_SHAPE;
1368     break;
1369   }
1370   return aRet;
1371 }
1372 //=======================================================================
1373 //function : CollectContainers
1374 //purpose  : 
1375 //=======================================================================
1376 void CollectContainers(const TopoDS_Shape& theS,
1377                        TopTools_ListOfShape& theLSC)
1378 {
1379   TopAbs_ShapeEnum aType = theS.ShapeType();
1380   if (aType == TopAbs_WIRE ||
1381       aType == TopAbs_SHELL ||
1382       aType == TopAbs_COMPSOLID) {
1383     theLSC.Append(theS);
1384     return;
1385   }
1386   //
1387   if (aType != TopAbs_COMPOUND) {
1388     return;
1389   }
1390   //
1391   TopoDS_Iterator aIt(theS);
1392   for (; aIt.More(); aIt.Next()) {
1393     const TopoDS_Shape& aS = aIt.Value();
1394     CollectContainers(aS, theLSC);
1395   }
1396 }
1397
1398 //=======================================================================
1399 //function : RemoveDuplicates
1400 //purpose  : Filters the containers with identical contents
1401 //=======================================================================
1402 void RemoveDuplicates(TopTools_ListOfShape& theContainers)
1403 {
1404   RemoveDuplicates(theContainers, TopAbs_WIRE);
1405   RemoveDuplicates(theContainers, TopAbs_SHELL);
1406   RemoveDuplicates(theContainers, TopAbs_COMPSOLID);
1407 }
1408
1409 //=======================================================================
1410 //function : RemoveDuplicates
1411 //purpose  : Filters the containers of given type with identical contents
1412 //=======================================================================
1413 void RemoveDuplicates(TopTools_ListOfShape& theContainers,
1414                       const TopAbs_ShapeEnum theType)
1415 {
1416   // get containers of given type
1417   TopTools_ListOfShape aLC;
1418   TopTools_ListIteratorOfListOfShape aItLC(theContainers);
1419   for (; aItLC.More(); aItLC.Next()) {
1420     const TopoDS_Shape& aC = aItLC.Value();
1421     if (aC.ShapeType() == theType) {
1422       aLC.Append(aC);
1423     }
1424   }
1425   //
1426   if (aLC.IsEmpty()) {
1427     return;
1428   }
1429   //
1430   // map containers to compare its contents
1431   NCollection_IndexedDataMap<TopoDS_Shape, TopTools_MapOfShape> aContents;
1432   //
1433   aItLC.Initialize(aLC);
1434   for (; aItLC.More(); aItLC.Next()) {
1435     const TopoDS_Shape& aC = aItLC.Value();
1436     //
1437     TopTools_MapOfShape& aMC = aContents(aContents.Add(aC, TopTools_MapOfShape()));
1438     //
1439     TopoDS_Iterator aIt(aC);
1440     for (; aIt.More(); aIt.Next()) {
1441       aMC.Add(aIt.Value());
1442     }
1443   }
1444   //
1445   // compare the contents of the containers and find duplicates
1446   TopTools_MapOfShape aDuplicates;
1447   //
1448   Standard_Integer i, j, aNb = aContents.Extent();
1449   for (i = 1; i <= aNb; ++i) {
1450     const TopoDS_Shape& aCi = aContents.FindKey(i);
1451     if (aDuplicates.Contains(aCi)) {
1452       continue;
1453     }
1454     const TopTools_MapOfShape& aMi = aContents(i);
1455     Standard_Integer aNbi = aMi.Extent();
1456     //
1457     for (j = i + 1; j <= aNb; ++j) {
1458       const TopoDS_Shape& aCj = aContents.FindKey(j);
1459       if (aDuplicates.Contains(aCj)) {
1460         continue;
1461       }
1462       const TopTools_MapOfShape& aMj = aContents(j);
1463       Standard_Integer aNbj = aMj.Extent();
1464       //
1465       Standard_Integer aNbCommon = NbCommonItemsInMap(aMi, aMj);
1466       //
1467       if (aNbj == aNbCommon) {
1468         aDuplicates.Add(aCj);
1469         continue;
1470       }
1471       //
1472       if (aNbi == aNbCommon) {
1473         aDuplicates.Add(aCi);
1474         break;
1475       }
1476     }
1477   }
1478   //
1479   if (aDuplicates.IsEmpty()) {
1480     return;
1481   }
1482   //
1483   // remove duplicating containers
1484   aItLC.Initialize(theContainers);
1485   for (; aItLC.More(); ) {
1486     const TopoDS_Shape& aC = aItLC.Value();
1487     if (aDuplicates.Contains(aC)) {
1488       theContainers.Remove(aItLC);
1489       continue;
1490     }
1491     aItLC.Next();
1492   }
1493 }
1494
1495 //=======================================================================
1496 //function : NbCommonItemsInMap
1497 //purpose  : Counts the items contained in both maps
1498 //=======================================================================
1499 Standard_Integer NbCommonItemsInMap(const TopTools_MapOfShape& theM1,
1500                                     const TopTools_MapOfShape& theM2)
1501 {
1502   const TopTools_MapOfShape* aMap1 = &theM1;
1503   const TopTools_MapOfShape* aMap2 = &theM2;
1504   //
1505   if (theM2.Extent() < theM1.Extent()) {
1506     aMap1 = &theM2;
1507     aMap2 = &theM1;
1508   }
1509   //
1510   Standard_Integer iCommon = 0;
1511   for (TopTools_MapIteratorOfMapOfShape aIt(*aMap1); aIt.More(); aIt.Next()) {
1512     if (aMap2->Contains(aIt.Value())) {
1513       ++iCommon;
1514     }
1515   }
1516   return iCommon;
1517 }
1518 //=======================================================================
1519 //function : MapFacesToBuildSolids
1520 //purpose  : Stores the faces of the given solid into outgoing maps:
1521 //           <theMFS> - not internal faces with reference to solid;
1522 //           <theMFI> - internal faces.
1523 //=======================================================================
1524 void MapFacesToBuildSolids(const TopoDS_Shape& theSol,
1525                            TopTools_IndexedDataMapOfShapeListOfShape& theMFS,
1526                            TopTools_IndexedMapOfShape& theMFI)
1527 {
1528   TopExp_Explorer aExp(theSol, TopAbs_FACE);
1529   for (; aExp.More(); aExp.Next()) {
1530     const TopoDS_Shape& aF = aExp.Current();
1531     //
1532     if (aF.Orientation() == TopAbs_INTERNAL) {
1533       theMFI.Add(aF);
1534       continue;
1535     }
1536     //
1537     TopTools_ListOfShape* pLSol = theMFS.ChangeSeek(aF);
1538     if (!pLSol) {
1539       pLSol = &theMFS(theMFS.Add(aF, TopTools_ListOfShape()));
1540       pLSol->Append(theSol);
1541     }
1542     else {
1543       const TopoDS_Shape& aF1 = theMFS.FindKey(theMFS.FindIndex(aF));
1544       if (aF1.Orientation() != aF.Orientation()) {
1545         pLSol->Append(theSol);
1546       }
1547     }
1548   }
1549 }