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