0024952: Possibility to break Boolean operations algorithm by user request
[occt.git] / src / BOPAlgo / BOPAlgo_Builder_3.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 //
7 // This file is part of Open CASCADE Technology software library.
8 //
9 // This library is free software; you can redistribute it and/or modify it under
10 // the terms of the GNU Lesser General Public License version 2.1 as published
11 // by the Free Software Foundation, with special exception defined in the file
12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
13 // distribution for complete text of the license and disclaimer of any warranty.
14 //
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
17
18 #include <BOPAlgo_Builder.hxx>
19 //
20 #include <NCollection_IncAllocator.hxx>
21 #include <NCollection_UBTreeFiller.hxx>
22 //
23 #include <Bnd_Box.hxx>
24 #include <TopAbs_State.hxx>
25 //
26 #include <TopoDS.hxx>
27 #include <TopoDS_Iterator.hxx>
28 #include <TopoDS_Solid.hxx>
29 #include <TopoDS_Shape.hxx>
30 #include <TopoDS_Face.hxx>
31 #include <TopoDS_Edge.hxx>
32 #include <TopoDS_Solid.hxx>
33 #include <TopoDS_Iterator.hxx>
34 #include <TopoDS_Shell.hxx>
35 #include <TopoDS_Compound.hxx>
36 //
37 #include <TopExp.hxx>
38 #include <TopExp_Explorer.hxx>
39 //
40 #include <BRep_Builder.hxx>
41 #include <BRepTools.hxx>
42 #include <BRepClass3d_SolidClassifier.hxx>
43 #include <BRepBndLib.hxx>
44 //
45 #include <BOPCol_IndexedMapOfShape.hxx>
46 #include <BOPCol_MapOfShape.hxx>
47 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
48 #include <BOPCol_ListOfShape.hxx>
49 #include <BOPCol_BoxBndTree.hxx>
50 #include <BOPCol_ListOfInteger.hxx>
51 #include <BOPCol_DataMapOfIntegerShape.hxx>
52 #include <BOPCol_NCVector.hxx>
53 #include <BOPCol_TBB.hxx>
54 //
55 #include <IntTools_Context.hxx>
56 //
57 #include <BOPDS_DS.hxx>
58 #include <BOPDS_ShapeInfo.hxx>
59 //
60 #include <BOPTools.hxx>
61 #include <BOPTools_AlgoTools.hxx>
62 #include <BOPTools_MapOfSet.hxx>
63 #include <BOPTools_Set.hxx>
64 //
65 #include <BOPAlgo_BuilderSolid.hxx>
66
67
68 static
69   void OwnInternalShapes(const TopoDS_Shape& ,
70                          BOPCol_IndexedMapOfShape& );
71
72 static
73   void TreatCompound(const TopoDS_Shape& theS,
74                      BOPCol_MapOfShape& aMFence,
75                      BOPCol_ListOfShape& theLS);
76
77 //=======================================================================
78 // BOPAlgo_BuilderSolid
79 //
80 typedef BOPCol_NCVector
81   <BOPAlgo_BuilderSolid> BOPAlgo_VectorOfBuilderSolid;
82 //
83 typedef BOPCol_TBBFunctor 
84   <BOPAlgo_BuilderSolid,
85   BOPAlgo_VectorOfBuilderSolid> BOPAlgo_BuilderSolidFunctor;
86 //
87 typedef BOPCol_TBBCnt 
88   <BOPAlgo_BuilderSolidFunctor,
89   BOPAlgo_VectorOfBuilderSolid> BOPAlgo_BuilderSolidCnt;
90 //
91 //=======================================================================
92 //class     : BOPAlgo_ShapeBox
93 //purpose   : Auxiliary class
94 //=======================================================================
95 class BOPAlgo_ShapeBox {
96  public:
97   BOPAlgo_ShapeBox() {
98   };
99   //
100   ~BOPAlgo_ShapeBox() {
101   };
102   //
103   void SetShape(const TopoDS_Shape& aS) {
104     myShape=aS;
105   };
106   //
107   const TopoDS_Shape& Shape()const {
108     return myShape;
109   };
110   //
111   void SetBox(const Bnd_Box& aBox) {
112     myBox=aBox;
113   };
114   //
115   const Bnd_Box& Box()const {
116     return myBox;
117   };
118   //
119  protected:
120   TopoDS_Shape myShape;
121   Bnd_Box myBox;
122 };
123 //
124 typedef NCollection_DataMap\
125   <Standard_Integer, BOPAlgo_ShapeBox, TColStd_MapIntegerHasher> \
126   BOPAlgo_DataMapOfIntegerShapeBox; 
127 //
128 typedef BOPAlgo_DataMapOfIntegerShapeBox::Iterator \
129   BOPAlgo_DataMapIteratorOfDataMapOfIntegerShapeBox; 
130 // 
131
132 //=======================================================================
133 //function : FillImagesSolids
134 //purpose  : 
135 //=======================================================================
136 void BOPAlgo_Builder::FillImagesSolids()
137 {
138   Standard_Boolean bHasSolids;
139   Standard_Integer i, aNbS;
140   //
141   myErrorStatus=0;
142   //
143   bHasSolids=Standard_False;
144   aNbS=myDS->NbSourceShapes();
145   for (i=0; i<aNbS; ++i) {
146     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
147     if (aSI.ShapeType()==TopAbs_SOLID) {
148       bHasSolids=!bHasSolids;
149       break;
150     }
151   }
152   //
153   if (!bHasSolids) {
154     return;
155   }
156   //
157   Handle(NCollection_IncAllocator) aAlr;
158   //
159   aAlr=new NCollection_IncAllocator();
160   BOPCol_DataMapOfShapeListOfShape theInParts(100, aAlr);
161   BOPCol_DataMapOfShapeShape theDraftSolids(100, aAlr);
162   //
163   FillIn3DParts(theInParts, theDraftSolids, aAlr); 
164   BuildSplitSolids(theInParts, theDraftSolids, aAlr);
165   FillInternalShapes();
166   //
167   theInParts.Clear();
168   theDraftSolids.Clear();
169 }
170 //=======================================================================
171 //function : FillIn3DParts
172 //purpose  : 
173 //=======================================================================
174 void BOPAlgo_Builder::FillIn3DParts
175   (BOPCol_DataMapOfShapeListOfShape& theInParts,
176    BOPCol_DataMapOfShapeShape& theDraftSolids,
177    const BOPCol_BaseAllocator& )
178 {
179   Standard_Boolean bHasImage;
180   Standard_Integer i, k, aNbS, aNbLIF, nFP, aNbFP, aNbFIN, iIsIN;
181   TopoDS_Solid aSD;
182   TopoDS_Iterator aIt;
183   BRep_Builder aBB; 
184   BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
185   BOPCol_ListIteratorOfListOfShape aItLS;
186   BOPAlgo_ShapeBox aSB;
187   Handle(NCollection_IncAllocator) aAlr0;
188   //
189   aAlr0=new NCollection_IncAllocator();
190   BOPAlgo_DataMapOfIntegerShapeBox aDMISB(100, aAlr0);
191   BOPAlgo_DataMapIteratorOfDataMapOfIntegerShapeBox aItDMISB;
192   //
193   myErrorStatus=0;
194   theDraftSolids.Clear();
195   //
196   // 1. aDMISB map Index/FaceBox 
197   k=0;
198   aNbS=myDS->NbSourceShapes();
199   for (i=0; i<aNbS; ++i) {
200     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
201     if (aSI.ShapeType()!=TopAbs_FACE) {
202       continue;
203     }
204     //
205     const TopoDS_Shape& aS=aSI.Shape();
206     //
207     if (myImages.IsBound(aS)) {
208       const BOPCol_ListOfShape& aLS=myImages.Find(aS);
209       aItLS.Initialize(aLS);
210       for (; aItLS.More(); aItLS.Next()) {
211         const TopoDS_Shape& aSx=aItLS.Value();
212         //
213         Bnd_Box aBox;
214         BRepBndLib::Add(aSx, aBox);
215         //
216         aSB.SetShape(aSx);
217         aSB.SetBox(aBox);
218         //
219         aDMISB.Bind(k, aSB);
220         ++k;
221       }
222     }
223     else {
224       const Bnd_Box& aBox=aSI.Box();
225       //
226       aSB.SetShape(aS);
227       aSB.SetBox(aBox);
228       //
229       aDMISB.Bind(k, aSB);
230       ++k;
231     }
232   }//for (i=0; i<aNbS; ++i) {
233   //
234   // 1.2. Prepare TreeFiller
235   BOPCol_BoxBndTree aBBTree;
236   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
237   //
238   aItDMISB.Initialize(aDMISB);
239   for (; aItDMISB.More(); aItDMISB.Next()) {
240     k=aItDMISB.Key();
241     const BOPAlgo_ShapeBox& aSBk=aItDMISB.Value();
242     const Bnd_Box& aBk=aSBk.Box();
243     //
244     aTreeFiller.Add(k, aBk);
245   }
246   //
247   // 1.3. Shake TreeFiller
248   aTreeFiller.Fill();
249   //
250   //---------------------------------------------
251   // 2. Solids
252   for (i=0; i<aNbS; ++i) {
253     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
254     if (aSI.ShapeType()!=TopAbs_SOLID) {
255       continue;
256     }
257     // 
258     UserBreak();
259     //---------------------------------------------
260     Handle(NCollection_IncAllocator) aAlr1;
261     //
262     aAlr1=new NCollection_IncAllocator();
263     //
264     BOPCol_ListOfShape aLFIN(aAlr1);
265     BOPCol_ListOfShape aLIF(aAlr1);
266     BOPCol_IndexedMapOfShape aMF(100, aAlr1);
267     BOPCol_IndexedDataMapOfShapeListOfShape aMEF(100, aAlr1);
268     BOPCol_BoxBndTreeSelector aSelector;
269     Bnd_Box aBoxS;
270     //
271     const TopoDS_Shape& aS=aSI.Shape();
272     const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
273     //
274     // 2.0 Flag bHasImage
275     bHasImage=Standard_False;
276     aIt.Initialize(aS);
277     for (; aIt.More(); aIt.Next()) {
278       const TopoDS_Shape& aShell=aIt.Value();
279       bHasImage=myImages.IsBound(aShell);
280       if (bHasImage){
281         break;
282       }
283     }
284     //
285     // 2.1 Bounding box for the solid aS  [ aBoxS ]
286     aBoxS=aSI.Box();
287     //-----
288     //
289     // 2.2 Build Draft Solid [aSD]
290     aBB.MakeSolid(aSD);
291     //
292     BuildDraftSolid(aSolid, aSD, aLIF);
293     aNbLIF=aLIF.Extent();
294     //
295     BOPTools::MapShapesAndAncestors(aSD, TopAbs_EDGE, TopAbs_FACE, aMEF);
296     //
297     // 2.3 Faces from aSD and own internal faces => aMF 
298     BOPTools::MapShapes(aSD, TopAbs_FACE, aMF);
299     //
300     aItLS.Initialize(aLIF);
301     for (; aItLS.More(); aItLS.Next()) {
302       const TopoDS_Shape& aFI=aItLS.Value();
303       aMF.Add(aFI);
304     }
305     //
306     // 2.4. Select boxes of faces that are not out of aBoxS
307     aSelector.Clear();
308     aSelector.SetBox(aBoxS);
309     //
310     aNbFP=aBBTree.Select(aSelector);
311     //
312     const BOPCol_ListOfInteger& aLIFP=aSelector.Indices();
313     //
314     // 2.5. Collect faces that are IN aSolid [ aLFIN ]
315     BOPCol_ListOfShape aLFP(aAlr1);
316     BOPCol_ListOfShape aLCBF(aAlr1);
317     BOPCol_MapOfShape aMFDone(100, aAlr1);
318     BOPCol_IndexedMapOfShape aME(100, aAlr1);
319     //
320     BOPTools::MapShapes(aSD, TopAbs_EDGE, aME);
321     //
322     aItLI.Initialize(aLIFP);
323     for (; aItLI.More(); aItLI.Next()) {
324       nFP=aItLI.Value();
325       const BOPAlgo_ShapeBox& aSBF=aDMISB.Find(nFP);
326       const TopoDS_Face& aFP=(*(TopoDS_Face*)&aSBF.Shape());
327       if (aMF.Contains(aFP)) {
328         continue;
329       }
330       if (aMFDone.Contains(aFP)) {
331         continue;
332       }
333       //
334       aMFDone.Add(aFP);
335       //
336       iIsIN=BOPTools_AlgoTools::IsInternalFace(aFP, aSD, aMEF, 1.e-14, myContext);
337       //
338       aLFP.Clear();
339       aLFP.Append(aFP);
340       //
341       aItLI1.Initialize(aLIFP);
342       for (; aItLI1.More(); aItLI1.Next()) {
343         const TopoDS_Shape& aFx=aDMISB.Find(aItLI1.Value()).Shape();
344         if (!aMFDone.Contains(aFx)) {
345           aLFP.Append(aFx);
346         }
347       }
348       //
349       aLCBF.Clear();
350       //---------------------------------------- 
351       {
352         Handle(NCollection_IncAllocator) aAlr2;
353         aAlr2=new NCollection_IncAllocator();
354         //
355         BOPTools_AlgoTools::MakeConnexityBlock(aLFP, aME, aLCBF, aAlr2);
356       }
357       //----------------------------------------
358       aItLS.Initialize(aLCBF);
359       for (; aItLS.More(); aItLS.Next()) {
360         const TopoDS_Shape& aFx=aItLS.Value();
361         aMFDone.Add(aFx);
362         if (iIsIN) {
363           aLFIN.Append(aFx);
364         }
365       }
366     }// for (; aItLI.More(); aItLI.Next()) {
367     //
368     // 2.6. Store the results in theInParts, theDraftSolids
369     aNbFIN=aLFIN.Extent();
370     if (aNbFIN || aNbLIF) {
371       aItLS.Initialize(aLIF);
372       for (; aItLS.More(); aItLS.Next()) {
373         const TopoDS_Shape& aFI=aItLS.Value();
374         aLFIN.Append(aFI);
375       }
376       theInParts.Bind(aSolid, aLFIN);
377     }
378     //
379     if (aNbFIN || bHasImage) {
380       theDraftSolids.Bind(aSolid, aSD);
381     }
382     //---------------------------------------------
383   }// for (i=0; i<aNbS; ++i) {
384 }
385 //=======================================================================
386 //function : BuildDraftSolid
387 //purpose  : 
388 //=======================================================================
389 void BOPAlgo_Builder::BuildDraftSolid(const TopoDS_Shape& theSolid,
390                                       TopoDS_Shape& theDraftSolid,
391                                       BOPCol_ListOfShape& theLIF)
392 {
393   myErrorStatus=0;
394   //
395   Standard_Boolean bToReverse;
396   Standard_Integer iFlag;
397   TopAbs_Orientation aOrF, aOrSh, aOrSd;
398   TopoDS_Iterator aIt1, aIt2;
399   TopoDS_Shell aShD;
400   TopoDS_Shape aFSDx, aFx;
401   BRep_Builder aBB;
402   BOPCol_ListIteratorOfListOfShape aItS; 
403   //
404   aOrSd=theSolid.Orientation();
405   theDraftSolid.Orientation(aOrSd);
406   //
407   aIt1.Initialize(theSolid);
408   for (; aIt1.More(); aIt1.Next()) {
409     const TopoDS_Shape& aSh=aIt1.Value();
410     if(aSh.ShapeType()!=TopAbs_SHELL) {
411       continue; // mb internal edges,vertices
412     }
413     //
414     aOrSh=aSh.Orientation();
415     aBB.MakeShell(aShD);
416     aShD.Orientation(aOrSh);
417     iFlag=0;
418     //
419     aIt2.Initialize(aSh);
420     for (; aIt2.More(); aIt2.Next()) {
421       const TopoDS_Shape& aF=aIt2.Value();
422       aOrF=aF.Orientation();
423       //
424       if (myImages.IsBound(aF)) {
425         const BOPCol_ListOfShape& aLSp=myImages.Find(aF);
426         aItS.Initialize(aLSp);
427         for (; aItS.More(); aItS.Next()) {
428           aFx=aItS.Value();
429           //
430           if (myShapesSD.IsBound(aFx)) {
431             aFSDx=myShapesSD.Find(aFx);
432             //
433             if (aOrF==TopAbs_INTERNAL) {
434               aFSDx.Orientation(aOrF);
435               theLIF.Append(aFSDx);
436             }
437             else {
438               bToReverse=BOPTools_AlgoTools::IsSplitToReverse
439                 (aFSDx, aF, myContext); 
440               if (bToReverse) {
441                 aFSDx.Reverse();
442               }
443               //
444               iFlag=1;
445               aBB.Add(aShD, aFSDx);
446             }
447           }//if (myShapesSD.IsBound(aFx)) {
448           else {
449             aFx.Orientation(aOrF);
450             if (aOrF==TopAbs_INTERNAL) {
451               theLIF.Append(aFx);
452             }
453             else{
454               iFlag=1;
455               aBB.Add(aShD, aFx);
456             }
457           }
458         }
459       } // if (myImages.IsBound(aF)) { 
460       //
461       else {
462         if (aOrF==TopAbs_INTERNAL) {
463           theLIF.Append(aF);
464         }
465         else{
466           iFlag=1;
467           aBB.Add(aShD, aF);
468         }
469       }
470     } //for (; aIt2.More(); aIt2.Next()) {
471     //
472     if (iFlag) {
473       aBB.Add(theDraftSolid, aShD);
474     }
475   } //for (; aIt1.More(); aIt1.Next()) {
476 }
477 //=======================================================================
478 //function : BuildSplitSolids
479 //purpose  : 
480 //=======================================================================
481 void BOPAlgo_Builder::BuildSplitSolids
482   (BOPCol_DataMapOfShapeListOfShape& theInParts,
483    BOPCol_DataMapOfShapeShape& theDraftSolids,
484    const BOPCol_BaseAllocator&  )
485 {
486   myErrorStatus=0;
487   //
488   Standard_Boolean bFlagSD;
489   Standard_Integer i, aNbS;
490   TopExp_Explorer aExp;
491   BOPCol_ListIteratorOfListOfShape aIt;
492   BOPCol_DataMapIteratorOfDataMapOfShapeShape aIt1;
493   //
494   Handle(NCollection_IncAllocator) aAlr0;
495   aAlr0=new NCollection_IncAllocator();
496   //
497   BOPCol_ListOfShape aSFS(aAlr0), aLSEmpty(aAlr0);
498   BOPCol_MapOfShape aMFence(100, aAlr0);
499   BOPTools_MapOfSet aMST(100, aAlr0);
500   BOPAlgo_VectorOfBuilderSolid aVBS;
501   //
502   // 0. Find same domain solids for non-interferred solids
503   aNbS=myDS->NbSourceShapes();
504   for (i=0; i<aNbS; ++i) {
505     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
506     //
507     if (aSI.ShapeType()!=TopAbs_SOLID) {
508       continue;
509     }
510     //
511     const TopoDS_Shape& aS=aSI.Shape();
512     if (!aMFence.Add(aS)) {
513       continue;
514     }
515     if(theDraftSolids.IsBound(aS)) {
516       continue;
517     }
518     //
519     BOPTools_Set aST;
520     //
521     aST.Add(aS, TopAbs_FACE);
522     aMST.Add(aST);
523     //
524   } //for (i=1; i<=aNbS; ++i) 
525   //
526   // 1. Build solids for interferred source solids
527   for (i=0; i<aNbS; ++i) {
528     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
529     //
530     if (aSI.ShapeType()!=TopAbs_SOLID) {
531       continue;
532     }
533     //
534     const TopoDS_Shape& aS=aSI.Shape();
535     const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
536     if(!theDraftSolids.IsBound(aS)) {
537       continue;
538     }
539     const TopoDS_Shape& aSD=theDraftSolids.Find(aS);
540     const BOPCol_ListOfShape& aLFIN=
541       (theInParts.IsBound(aS)) ? theInParts.Find(aS) : aLSEmpty;
542     //
543     // 1.1 Fill Shell Faces Set
544     aSFS.Clear();
545     aExp.Init(aSD, TopAbs_FACE);
546     for (; aExp.More(); aExp.Next()) {
547       const TopoDS_Shape& aF=aExp.Current();
548       aSFS.Append(aF);
549     }
550     //
551     aIt.Initialize(aLFIN);
552     for (; aIt.More(); aIt.Next()) {
553       TopoDS_Shape aF=aIt.Value();
554       //
555       aF.Orientation(TopAbs_FORWARD);
556       aSFS.Append(aF);
557       aF.Orientation(TopAbs_REVERSED);
558       aSFS.Append(aF);
559     }
560     //
561     // 1.3 Build new solids   
562     Handle(NCollection_IncAllocator) aAlr1;
563     aAlr1=new NCollection_IncAllocator();  
564     //
565     BOPAlgo_BuilderSolid& aBS=aVBS.Append1();
566     aBS.SetSolid(aSolid);
567     aBS.SetShapes(aSFS);
568     aBS.SetProgressIndicator(myProgressIndicator);
569   }//for (i=0; i<aNbS; ++i) {
570   //
571   Standard_Integer k, aNbBS;
572   //
573   aNbBS=aVBS.Extent();
574   //
575   //===================================================
576   BOPAlgo_BuilderSolidCnt::Perform(myRunParallel, aVBS);
577   //===================================================
578   //
579   for (k=0; k<aNbBS; ++k) {
580     BOPAlgo_BuilderSolid& aBS=aVBS(k);
581     const TopoDS_Solid& aS=aBS.Solid();
582     const BOPCol_ListOfShape& aLSR=aBS.Areas();
583     //
584     if (!myImages.IsBound(aS)) {
585       BOPCol_ListOfShape aLSx;
586       //
587       myImages.Bind(aS, aLSx);
588       BOPCol_ListOfShape& aLSIm=myImages.ChangeFind(aS);
589       //
590       aIt.Initialize(aLSR);
591       for (; aIt.More(); aIt.Next()) {
592         BOPTools_Set aST;
593         //
594         const TopoDS_Shape& aSR=aIt.Value();
595         aST.Add(aSR, TopAbs_FACE);
596         //
597         bFlagSD=aMST.Contains(aST);
598         //
599         const BOPTools_Set& aSTx=aMST.Added(aST);
600         const TopoDS_Shape& aSx=aSTx.Shape();
601         aLSIm.Append(aSx);
602         //
603         if (bFlagSD) {
604           myShapesSD.Bind(aSR, aSx);
605         }
606       }
607     }
608   }
609 }
610 //=======================================================================
611 //function :FillInternalShapes 
612 //purpose  : 
613 //=======================================================================
614 void BOPAlgo_Builder::FillInternalShapes()
615 {
616   myErrorStatus=0;
617   //
618   Standard_Integer i, j,  aNbS, aNbSI, aNbSx;
619   TopAbs_ShapeEnum aType;
620   TopAbs_State aState; 
621   TopoDS_Iterator aItS;
622   BRep_Builder aBB;
623   BOPCol_MapIteratorOfMapOfShape aItM;
624   BOPCol_ListIteratorOfListOfShape aIt, aIt1;
625   //
626   Handle(NCollection_IncAllocator) aAllocator;
627   //-----------------------------------------------------scope f
628   aAllocator=new NCollection_IncAllocator();
629   //
630   BOPCol_IndexedDataMapOfShapeListOfShape aMSx(100, aAllocator);
631   BOPCol_IndexedMapOfShape aMx(100, aAllocator);
632   BOPCol_MapOfShape aMSI(100, aAllocator);
633   BOPCol_MapOfShape aMFence(100, aAllocator);
634   BOPCol_MapOfShape aMSOr(100, aAllocator);
635   BOPCol_ListOfShape aLSd(aAllocator);
636   BOPCol_ListOfShape aLArgs(aAllocator);
637   BOPCol_ListOfShape aLSC(aAllocator);
638   //
639   // 1. Shapes to process
640   //
641   // 1.1 Shapes from pure arguments aMSI 
642   // 1.1.1 vertex, edge, wire
643   //
644   const BOPCol_ListOfShape& aArguments=myDS->Arguments();
645   aIt.Initialize(aArguments);
646   for (; aIt.More(); aIt.Next()) {
647     const TopoDS_Shape& aS=aIt.Value();
648     TreatCompound(aS, aMFence, aLSC);
649   }
650   aIt.Initialize(aLSC);
651   for (; aIt.More(); aIt.Next()) {
652     const TopoDS_Shape& aS=aIt.Value();
653     aType=aS.ShapeType();
654     if (aType==TopAbs_WIRE) {
655       aItS.Initialize(aS);
656       for(; aItS.More(); aItS.Next()) {
657         const TopoDS_Shape& aE=aItS.Value();
658         if (aMFence.Add(aE)) {
659           aLArgs.Append(aE);
660         }
661       }
662     }
663     else if (aType==TopAbs_VERTEX || aType==TopAbs_EDGE){
664       aLArgs.Append(aS);
665     } 
666   }
667   aMFence.Clear();
668   //
669   aIt.Initialize(aLArgs);
670   for (; aIt.More(); aIt.Next()) {
671     const TopoDS_Shape& aS=aIt.Value();
672     aType=aS.ShapeType();
673     if (aType==TopAbs_VERTEX || 
674         aType==TopAbs_EDGE ||
675         aType==TopAbs_WIRE) {
676       if (aMFence.Add(aS)) {
677         if (myImages.IsBound(aS)) {
678           const BOPCol_ListOfShape &aLSp=myImages.Find(aS);
679           aIt1.Initialize(aLSp);
680           for (; aIt1.More(); aIt1.Next()) {
681             const TopoDS_Shape& aSp=aIt1.Value();
682             aMSI.Add(aSp);
683           }
684         }
685         else {
686           aMSI.Add(aS);
687         }
688       }
689     }
690   }
691   
692   aNbSI=aMSI.Extent();
693   //
694   // 2. Internal vertices, edges from source solids
695   aMFence.Clear();
696   aLSd.Clear();
697   //
698   aNbS=myDS->NbSourceShapes();
699   for (i=0; i<aNbS; ++i) {
700     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
701     //
702     if (aSI.ShapeType()!=TopAbs_SOLID) {
703       continue;
704     }
705     //
706     UserBreak();
707     //
708     const TopoDS_Shape& aS=aSI.Shape();
709     //
710     aMx.Clear();
711     OwnInternalShapes(aS, aMx);
712     //
713     aNbSx=aMx.Extent();
714     for (j=1; j<=aNbSx; ++j) {
715       const TopoDS_Shape& aSi=aMx(j);
716       if (myImages.IsBound(aSi)) {
717         const BOPCol_ListOfShape &aLSp=myImages.Find(aSi);
718         aIt1.Initialize(aLSp);
719         for (; aIt1.More(); aIt1.Next()) {
720           const TopoDS_Shape& aSp=aIt1.Value();
721           aMSI.Add(aSp);
722         }
723       }
724       else {
725         aMSI.Add(aSi);
726       }
727     }
728     //
729     // build aux map from splits of solids
730     if (myImages.IsBound(aS)) {
731       const BOPCol_ListOfShape &aLSp=myImages.Find(aS);
732       aIt.Initialize(aLSp);
733       for (; aIt.More(); aIt.Next()) {
734         const TopoDS_Shape& aSp=aIt.Value();
735         if (aMFence.Add(aSp)) { 
736           BOPTools::MapShapesAndAncestors(aSp, TopAbs_VERTEX, TopAbs_EDGE, aMSx);
737           BOPTools::MapShapesAndAncestors(aSp, TopAbs_VERTEX, TopAbs_FACE, aMSx);
738           BOPTools::MapShapesAndAncestors(aSp, TopAbs_EDGE  , TopAbs_FACE, aMSx);
739           aLSd.Append(aSp);
740         }
741       }
742     }
743     else {
744       if (aMFence.Add(aS)) {
745         BOPTools::MapShapesAndAncestors(aS, TopAbs_VERTEX, TopAbs_EDGE, aMSx);
746         BOPTools::MapShapesAndAncestors(aS, TopAbs_VERTEX, TopAbs_FACE, aMSx);
747         BOPTools::MapShapesAndAncestors(aS, TopAbs_EDGE  , TopAbs_FACE, aMSx);
748         aLSd.Append(aS);
749         aMSOr.Add(aS); 
750       }
751     }
752   }// for (i=0; i<aNbS; ++i) {
753   //
754   // 3. Some shapes of aMSI can be already tied with faces of 
755   //    split solids
756   aItM.Initialize(aMSI); 
757   for (; aItM.More(); aItM.Next()) {
758     const TopoDS_Shape& aSI=aItM.Key();
759     if (aMSx.Contains(aSI)) {
760       const BOPCol_ListOfShape &aLSx=aMSx.FindFromKey(aSI);
761       aNbSx=aLSx.Extent();
762       if (aNbSx) {
763         aMSI.Remove(aSI);
764       }
765     }
766   }
767   //
768   // 4. Just check it
769   aNbSI=aMSI.Extent();
770   if (!aNbSI) {
771     return;
772   }
773   //
774   // 5 Settle internal vertices and edges into solids
775   aMx.Clear();
776   aIt.Initialize(aLSd);
777   for (; aIt.More(); aIt.Next()) {
778     TopoDS_Solid aSd=TopoDS::Solid(aIt.Value());
779     //
780     aItM.Initialize(aMSI); 
781     for (; aItM.More(); aItM.Next()) {
782       TopoDS_Shape aSI=aItM.Key();
783       aSI.Orientation(TopAbs_INTERNAL);
784       //
785       aState=BOPTools_AlgoTools::ComputeStateByOnePoint(aSI, aSd, 1.e-11, myContext);
786       if (aState==TopAbs_IN) {
787         //
788         if(aMSOr.Contains(aSd)) {
789           //
790           TopoDS_Solid aSdx;
791           //
792           aBB.MakeSolid(aSdx);
793           aItS.Initialize(aSd);
794           for (; aItS.More(); aItS.Next()) {
795             const TopoDS_Shape& aSh=aItS.Value();
796             aBB.Add(aSdx, aSh);
797           }
798           //
799           aBB.Add(aSdx, aSI);
800           //
801           if (myImages.IsBound(aSdx)) {
802             BOPCol_ListOfShape& aLS=myImages.ChangeFind(aSdx);
803             aLS.Append(aSdx);
804           } 
805           else {
806             BOPCol_ListOfShape aLS;
807             aLS.Append(aSdx);
808             myImages.Bind(aSd, aLS);
809           }
810           //
811           aMSOr.Remove(aSd);
812           aSd=aSdx;
813         }
814         else {
815           aBB.Add(aSd, aSI);
816         }
817         //
818         aMSI.Remove(aSI);
819       } //if (aState==TopAbs_IN) {
820     }// for (; aItM.More(); aItM.Next()) {
821   }//for (; aIt1.More(); aIt1.Next()) {
822   //
823   //-----------------------------------------------------scope t
824   aLArgs.Clear();
825   aLSd.Clear();
826   aMSOr.Clear();
827   aMFence.Clear();
828   aMSI.Clear();
829   aMx.Clear();
830   aMSx.Clear();
831 }
832 //=======================================================================
833 //function : OwnInternalShapes
834 //purpose  : 
835 //=======================================================================
836 void OwnInternalShapes(const TopoDS_Shape& theS,
837                        BOPCol_IndexedMapOfShape& theMx)
838 {
839   TopoDS_Iterator aIt;
840   //
841   aIt.Initialize(theS);
842   for (; aIt.More(); aIt.Next()) {
843     const TopoDS_Shape& aSx=aIt.Value();
844     if (aSx.ShapeType()!=TopAbs_SHELL) {
845       theMx.Add(aSx);
846     }
847   }
848 }
849 //=======================================================================
850 //function : TreatCompound
851 //purpose  : 
852 //=======================================================================
853 void TreatCompound(const TopoDS_Shape& theS,
854                    BOPCol_MapOfShape& aMFence,
855                    BOPCol_ListOfShape& theLS)
856 {
857   TopAbs_ShapeEnum aType;
858   //
859   aType = theS.ShapeType();
860   if (aType != TopAbs_COMPOUND) {
861     if (aMFence.Add(theS)) {
862       theLS.Append(theS);
863     }
864     return;
865   }
866   //
867   TopoDS_Iterator aIt;
868   //
869   aIt.Initialize(theS);
870   for (; aIt.More(); aIt.Next()) {
871     const TopoDS_Shape& aS = aIt.Value();
872     TreatCompound(aS, aMFence, theLS);
873   }
874 }
875
876 //
877 // ErrorStatus
878 // 30 - SolidBuilder failed
879 // A