0024187: Wrong result of COMMON operation.
[occt.git] / src / BOPAlgo / BOPAlgo_Builder_3.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2012 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 // The content of this file is subject to the Open CASCADE Technology Public
8 // License Version 6.5 (the "License"). You may not use the content of this file
9 // except in compliance with the License. Please obtain a copy of the License
10 // at http://www.opencascade.org and read it completely before using this file.
11 //
12 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
13 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
14 //
15 // The Original Code and all software distributed under the License is
16 // distributed on an "AS IS" basis, without warranty of any kind, and the
17 // Initial Developer hereby disclaims all such warranties, including without
18 // limitation, any warranties of merchantability, fitness for a particular
19 // purpose or non-infringement. Please see the License for the specific terms
20 // and conditions governing the rights and limitations under the License.
21
22 #include <BOPAlgo_Builder.hxx>
23
24 #include <NCollection_IncAllocator.hxx>
25
26 #include <TopAbs_State.hxx>
27
28 #include <TopoDS.hxx>
29 #include <TopoDS_Iterator.hxx>
30 #include <TopoDS_Solid.hxx>
31 #include <TopoDS_Shape.hxx>
32 #include <TopoDS_Face.hxx>
33 #include <TopoDS_Edge.hxx>
34 #include <TopoDS_Solid.hxx>
35 #include <TopoDS_Iterator.hxx>
36 #include <TopoDS_Shell.hxx>
37 #include <TopoDS_Compound.hxx>
38
39 #include <TopExp.hxx>
40 #include <TopExp_Explorer.hxx>
41
42 #include <BRep_Builder.hxx>
43 #include <BRepTools.hxx>
44 #include <BRepClass3d_SolidClassifier.hxx>
45 //
46 #include <BOPCol_IndexedMapOfShape.hxx>
47 #include <BOPCol_MapOfShape.hxx>
48 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
49 #include <BOPCol_ListOfShape.hxx>
50 //
51 #include <BOPDS_DS.hxx>
52 #include <BOPDS_ShapeInfo.hxx>
53 //
54 #include <BOPTools.hxx>
55 #include <BOPTools_AlgoTools.hxx>
56 //
57 #include <BOPTools_MapOfSet.hxx>
58 #include <BOPTools_Set.hxx>
59 //
60 #include <BOPAlgo_BuilderSolid.hxx>
61
62 #include <BOPCol_DataMapOfIntegerShape.hxx>
63 #include <Bnd_Box.hxx>
64 #include <BRepBndLib.hxx>
65
66 #include <NCollection_UBTreeFiller.hxx>
67 #include <BOPDS_BoxBndTree.hxx>
68 #include <BOPCol_ListOfInteger.hxx>
69 #include <BOPInt_Context.hxx>
70
71
72 static
73   Standard_Boolean IsClosedShell(const TopoDS_Shell& aSh);
74
75 static
76   void OwnInternalShapes(const TopoDS_Shape& ,
77                          BOPCol_IndexedMapOfShape& );
78
79 static
80   void TreatCompound(const TopoDS_Shape& theS,
81                      BOPCol_MapOfShape& aMFence,
82                      BOPCol_ListOfShape& theLS);
83
84 //=======================================================================
85 //class     : BOPAlgo_ShapeBox
86 //purpose   : Auxiliary class
87 //=======================================================================
88 class BOPAlgo_ShapeBox {
89  public:
90   BOPAlgo_ShapeBox() {
91   };
92   //
93   ~BOPAlgo_ShapeBox() {
94   };
95   //
96   void SetShape(const TopoDS_Shape& aS) {
97     myShape=aS;
98   };
99   //
100   const TopoDS_Shape& Shape()const {
101     return myShape;
102   };
103   //
104   void SetBox(const Bnd_Box& aBox) {
105     myBox=aBox;
106   };
107   //
108   const Bnd_Box& Box()const {
109     return myBox;
110   };
111   //
112  protected:
113   TopoDS_Shape myShape;
114   Bnd_Box myBox;
115 };
116 //
117 typedef NCollection_DataMap\
118   <Standard_Integer, BOPAlgo_ShapeBox, TColStd_MapIntegerHasher> \
119   BOPAlgo_DataMapOfIntegerShapeBox; 
120 //
121 typedef BOPAlgo_DataMapOfIntegerShapeBox::Iterator \
122   BOPAlgo_DataMapIteratorOfDataMapOfIntegerShapeBox; 
123 // 
124
125 //=======================================================================
126 //function : FillImagesSolids
127 //purpose  : 
128 //=======================================================================
129 void BOPAlgo_Builder::FillImagesSolids()
130 {
131   Standard_Boolean bHasSolids;
132   Standard_Integer i, aNbS;
133   //
134   myErrorStatus=0;
135   //
136   bHasSolids=Standard_False;
137   aNbS=myDS->NbSourceShapes();
138   for (i=0; i<aNbS; ++i) {
139     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
140     if (aSI.ShapeType()==TopAbs_SOLID) {
141       bHasSolids=!bHasSolids;
142       break;
143     }
144   }
145   //
146   if (!bHasSolids) {
147     return;
148   }
149   //
150   Handle(NCollection_IncAllocator) aAlr;
151   //
152   aAlr=new NCollection_IncAllocator();
153   //
154   BOPCol_DataMapOfShapeListOfShape theInParts(100, aAlr);
155   BOPCol_DataMapOfShapeShape theDraftSolids(100, aAlr);
156   //
157   FillIn3DParts(theInParts, theDraftSolids, aAlr);
158   BuildSplitSolids(theInParts, theDraftSolids, aAlr);
159   FillInternalShapes();
160   //
161   theInParts.Clear();
162   theDraftSolids.Clear();
163 }
164 //=======================================================================
165 //function : FillIn3DParts
166 //purpose  : 
167 //=======================================================================
168 void BOPAlgo_Builder::FillIn3DParts(BOPCol_DataMapOfShapeListOfShape& theInParts,
169                                     BOPCol_DataMapOfShapeShape& theDraftSolids,
170                                     const BOPCol_BaseAllocator& )
171 {
172   Standard_Boolean bHasImage;
173   Standard_Integer i, k, aNbS, aNbLIF, nFP, aNbFP, aNbFIN, iIsIN;
174   TopoDS_Solid aSD;
175   TopoDS_Iterator aIt;
176   BRep_Builder aBB; 
177   BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
178   BOPCol_ListIteratorOfListOfShape aItLS;
179   BOPAlgo_ShapeBox aSB;
180   Handle(NCollection_IncAllocator) aAlr0;
181   //
182   aAlr0=new NCollection_IncAllocator();
183   BOPAlgo_DataMapOfIntegerShapeBox aDMISB(100, aAlr0);
184   BOPAlgo_DataMapIteratorOfDataMapOfIntegerShapeBox aItDMISB;
185   //
186   myErrorStatus=0;
187   theDraftSolids.Clear();
188   //
189   // 1. aDMISB map Index/FaceBox
190   k=0;
191   aNbS=myDS->NbSourceShapes();
192   for (i=0; i<aNbS; ++i) {
193     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
194     if (aSI.ShapeType()!=TopAbs_FACE) {
195       continue;
196     }
197     //
198     const TopoDS_Shape& aS=aSI.Shape();
199     //
200     if (myImages.IsBound(aS)) {
201       const BOPCol_ListOfShape& aLS=myImages.Find(aS);
202       aItLS.Initialize(aLS);
203       for (; aItLS.More(); aItLS.Next()) {
204         const TopoDS_Shape& aSx=aItLS.Value();
205         //
206         Bnd_Box aBox;
207         BRepBndLib::Add(aSx, aBox);
208         //
209         aSB.SetShape(aSx);
210         aSB.SetBox(aBox);
211         //
212         aDMISB.Bind(k, aSB);
213         ++k;
214       }
215     }
216     else {
217       const Bnd_Box& aBox=aSI.Box();
218       //
219       aSB.SetShape(aS);
220       aSB.SetBox(aBox);
221       //
222       aDMISB.Bind(k, aSB);
223       ++k;
224     }
225   }//for (i=0; i<aNbS; ++i) {
226   //
227   // 2. Solids
228   for (i=0; i<aNbS; ++i) {
229     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
230     if (aSI.ShapeType()!=TopAbs_SOLID) {
231       continue;
232     }
233     // 
234     //---------------------------------------------
235     Handle(NCollection_IncAllocator) aAlr1;
236     //
237     aAlr1=new NCollection_IncAllocator();
238     //
239     BOPCol_ListOfShape aLFIN(aAlr1);
240     BOPCol_ListOfShape aLIF(aAlr1);
241     BOPCol_IndexedMapOfShape aMF(100, aAlr1);
242     BOPCol_IndexedDataMapOfShapeListOfShape aMEF(100, aAlr1);
243     //
244     BOPDS_BoxBndTreeSelector aSelector;
245     BOPDS_BoxBndTree aBBTree;
246     NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
247     Bnd_Box aBoxS;
248     //
249     const TopoDS_Shape& aS=aSI.Shape();
250     const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
251     //
252     // 2.0 Flag bHasImage
253     bHasImage=Standard_False;
254     aIt.Initialize(aS);
255     for (; aIt.More(); aIt.Next()) {
256       const TopoDS_Shape& aShell=aIt.Value();
257       bHasImage=myImages.IsBound(aShell);
258       if (bHasImage){
259         break;
260       }
261     }
262     //
263     // 2.1 Compute Bnd_Box for the solid aS  [ aBoxS ]
264     BuildBndBox(i, aBoxS);
265     //-----
266     //
267     // 2.2 Build Draft Solid [aSD]
268     aBB.MakeSolid(aSD);
269     //
270     BuildDraftSolid(aSolid, aSD, aLIF);
271     aNbLIF=aLIF.Extent();
272     //
273     BOPTools::MapShapesAndAncestors(aSD, TopAbs_EDGE, TopAbs_FACE, aMEF);
274     //
275     // 2.3 Faces from aSD and own internal faces => aMF 
276     BOPTools::MapShapes(aSD, TopAbs_FACE, aMF);
277     //
278     aItLS.Initialize(aLIF);
279     for (; aItLS.More(); aItLS.Next()) {
280       const TopoDS_Shape& aFI=aItLS.Value();
281       aMF.Add(aFI);
282     }
283     //
284     // 2.4. Prepare TreeFiller
285     aItDMISB.Initialize(aDMISB);
286     for (; aItDMISB.More(); aItDMISB.Next()) {
287       k=aItDMISB.Key();
288       const BOPAlgo_ShapeBox& aSBk=aItDMISB.Value();
289       const TopoDS_Shape& aFk=aSBk.Shape();
290       if (aMF.Contains(aFk)) {
291         continue;
292       }
293       //
294       const Bnd_Box& aBk=aSBk.Box();
295       //
296       aTreeFiller.Add(k, aBk);
297     }
298     //
299     // 2.5. Shake TreeFiller
300     aTreeFiller.Fill();
301     //
302     // 2.6. Select boxes of faces that are not out of aBoxS
303     aSelector.Clear();
304     aSelector.SetBox(aBoxS);
305     //
306     aNbFP=aBBTree.Select(aSelector);
307     //
308     const BOPCol_ListOfInteger& aLIFP=aSelector.Indices();
309     //
310     // 2.7. Collect faces that are IN aSolid [ aLFIN ]
311     BOPCol_ListOfShape aLFP(aAlr1);
312     BOPCol_ListOfShape aLCBF(aAlr1);
313     BOPCol_MapOfShape aMFDone(100, aAlr1);
314     BOPCol_IndexedMapOfShape aME(100, aAlr1);
315     //
316     BOPTools::MapShapes(aSD, TopAbs_EDGE, aME);
317     //
318     aItLI.Initialize(aLIFP);
319     for (; aItLI.More(); aItLI.Next()) {
320       nFP=aItLI.Value();
321       const BOPAlgo_ShapeBox& aSBF=aDMISB.Find(nFP);
322       const TopoDS_Face& aFP=(*(TopoDS_Face*)&aSBF.Shape());
323       if (aMFDone.Contains(aFP)) {
324         continue;
325       }
326       //
327       aMFDone.Add(aFP);
328       //
329       iIsIN=BOPTools_AlgoTools::IsInternalFace(aFP, aSD, aMEF, 1.e-14, myContext);
330       //
331       aLFP.Clear();
332       aLFP.Append(aFP);
333       //
334       aItLI1.Initialize(aLIFP);
335       for (; aItLI1.More(); aItLI1.Next()) {
336         const TopoDS_Shape& aFx=aDMISB.Find(aItLI1.Value()).Shape();
337         if (!aMFDone.Contains(aFx)) {
338           aLFP.Append(aFx);
339         }
340       }
341       //
342       aLCBF.Clear();
343       //---------------------------------------- 
344       {
345         Handle(NCollection_IncAllocator) aAlr2;
346         aAlr2=new NCollection_IncAllocator();
347         //
348         BOPTools_AlgoTools::MakeConnexityBlock(aLFP, aME, aLCBF, aAlr2);
349       }
350       //----------------------------------------
351       aItLS.Initialize(aLCBF);
352       for (; aItLS.More(); aItLS.Next()) {
353         const TopoDS_Shape& aFx=aItLS.Value();
354         aMFDone.Add(aFx);
355         if (iIsIN) {
356           aLFIN.Append(aFx);
357         }
358       }
359     }// for (; aItLI.More(); aItLI.Next()) {
360     //
361     // 2.8. Store the results in theInParts, theDraftSolids
362     aNbFIN=aLFIN.Extent();
363     if (aNbFIN || aNbLIF) {
364       aItLS.Initialize(aLIF);
365       for (; aItLS.More(); aItLS.Next()) {
366         const TopoDS_Shape& aFI=aItLS.Value();
367         aLFIN.Append(aFI);
368       }
369       theInParts.Bind(aSolid, aLFIN);
370     }
371     //
372     if (aNbFIN || bHasImage) {
373       theDraftSolids.Bind(aSolid, aSD);
374     }
375     //---------------------------------------------
376   }// for (i=0; i<aNbS; ++i) {
377 }
378
379 //=======================================================================
380 //function : BuildDraftSolid
381 //purpose  : 
382 //=======================================================================
383 void BOPAlgo_Builder::BuildDraftSolid(const TopoDS_Shape& theSolid,
384                                       TopoDS_Shape& theDraftSolid,
385                                       BOPCol_ListOfShape& theLIF)
386 {
387   myErrorStatus=0;
388   //
389   Standard_Boolean bToReverse;
390   Standard_Integer iFlag;
391   TopAbs_Orientation aOrF, aOrSh, aOrSd;
392   TopoDS_Iterator aIt1, aIt2;
393   TopoDS_Shell aShD;
394   TopoDS_Shape aFSDx, aFx;
395   BRep_Builder aBB;
396   BOPCol_ListIteratorOfListOfShape aItS;        
397   //
398   aOrSd=theSolid.Orientation();
399   theDraftSolid.Orientation(aOrSd);
400   //
401   aIt1.Initialize(theSolid);
402   for (; aIt1.More(); aIt1.Next()) {
403     const TopoDS_Shape& aSh=aIt1.Value();
404     if(aSh.ShapeType()!=TopAbs_SHELL) {
405       continue; // mb internal edges,vertices
406     }
407     //
408     aOrSh=aSh.Orientation();
409     aBB.MakeShell(aShD);
410     aShD.Orientation(aOrSh);
411     iFlag=0;
412     //
413     aIt2.Initialize(aSh);
414     for (; aIt2.More(); aIt2.Next()) {
415       const TopoDS_Shape& aF=aIt2.Value();
416       aOrF=aF.Orientation();
417       //
418       if (myImages.IsBound(aF)) {
419         const BOPCol_ListOfShape& aLSp=myImages.Find(aF);
420         aItS.Initialize(aLSp);
421         for (; aItS.More(); aItS.Next()) {
422           aFx=aItS.Value();
423           //
424           if (myShapesSD.IsBound(aFx)) {
425             aFSDx=myShapesSD.Find(aFx);
426             //
427             if (aOrF==TopAbs_INTERNAL) {
428               aFSDx.Orientation(aOrF);
429               theLIF.Append(aFSDx);
430             }
431             else {
432               bToReverse=BOPTools_AlgoTools::IsSplitToReverse(aFSDx, aF, myContext); 
433               if (bToReverse) {
434                 aFSDx.Reverse();
435               }
436               //
437               iFlag=1;
438               aBB.Add(aShD, aFSDx);
439             }
440           }//if (myShapesSD.IsBound(aFx)) {
441           else {
442             aFx.Orientation(aOrF);
443             if (aOrF==TopAbs_INTERNAL) {
444               theLIF.Append(aFx);
445             }
446             else{
447               iFlag=1;
448               aBB.Add(aShD, aFx);
449             }
450           }
451         }
452       } // if (myImages.IsBound(aF)) { 
453       //
454       else {
455         if (aOrF==TopAbs_INTERNAL) {
456           theLIF.Append(aF);
457         }
458         else{
459           iFlag=1;
460           aBB.Add(aShD, aF);
461         }
462       }
463     } //for (; aIt2.More(); aIt2.Next()) {
464     //
465     if (iFlag) {
466       aBB.Add(theDraftSolid, aShD);
467     }
468   } //for (; aIt1.More(); aIt1.Next()) {
469 }
470 //=======================================================================
471 //function : BuildSplitSolids
472 //purpose  : 
473 //=======================================================================
474 void BOPAlgo_Builder::BuildSplitSolids(BOPCol_DataMapOfShapeListOfShape& theInParts,
475                                        BOPCol_DataMapOfShapeShape& theDraftSolids,
476                                        const BOPCol_BaseAllocator&  )
477 {
478   myErrorStatus=0;
479   //
480   Standard_Boolean bFlagSD;
481   Standard_Integer i, aNbS, iErr, aNbSFS;
482   TopExp_Explorer aExp;
483   BOPCol_ListIteratorOfListOfShape aIt;
484   BOPCol_DataMapIteratorOfDataMapOfShapeShape aIt1;
485   //
486   Handle(NCollection_IncAllocator) aAlr0;
487   aAlr0=new NCollection_IncAllocator();
488   //
489   BOPCol_ListOfShape aSFS(aAlr0), aLSEmpty(aAlr0);
490   BOPCol_MapOfShape aMFence(100, aAlr0);
491   BOPTools_MapOfSet aMST(100, aAlr0);
492   //
493   // 0. Find same domain solids for non-interferred solids
494   aNbS=myDS->NbSourceShapes();
495   for (i=0; i<aNbS; ++i) {
496     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
497     //
498     if (aSI.ShapeType()!=TopAbs_SOLID) {
499       continue;
500     }
501     //
502     const TopoDS_Shape& aS=aSI.Shape();
503     if (!aMFence.Add(aS)) {
504       continue;
505     }
506     if(theDraftSolids.IsBound(aS)) {
507       continue;
508     }
509     //
510     BOPTools_Set aST;
511     //
512     aST.Add(aS, TopAbs_FACE);
513     aMST.Add(aST);
514     //
515   } //for (i=1; i<=aNbS; ++i) 
516   //
517   // 1. Build solids for interferred source solids
518   for (i=0; i<aNbS; ++i) {
519     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
520     //
521     if (aSI.ShapeType()!=TopAbs_SOLID) {
522       continue;
523     }
524     //
525     const TopoDS_Shape& aS=aSI.Shape();
526     if(!theDraftSolids.IsBound(aS)) {
527       continue;
528     }
529     const TopoDS_Shape& aSD=theDraftSolids.Find(aS);
530     const BOPCol_ListOfShape& aLFIN=
531       (theInParts.IsBound(aS)) ? theInParts.Find(aS) : aLSEmpty;
532     //
533     // 1.1 Fill Shell Faces Set
534     aSFS.Clear();
535     aExp.Init(aSD, TopAbs_FACE);
536     for (; aExp.More(); aExp.Next()) {
537       const TopoDS_Shape& aF=aExp.Current();
538       aSFS.Append(aF);
539     }
540     //
541     aIt.Initialize(aLFIN);
542     for (; aIt.More(); aIt.Next()) {
543       TopoDS_Shape aF=aIt.Value();
544       //
545       aF.Orientation(TopAbs_FORWARD);
546       aSFS.Append(aF);
547       aF.Orientation(TopAbs_REVERSED);
548       aSFS.Append(aF);
549     }
550     //
551     aNbSFS=aSFS.Extent();
552     //
553     // 1.3 Build new solids   
554     Handle(NCollection_IncAllocator) aAlr1;
555     aAlr1=new NCollection_IncAllocator();  
556     //
557     BOPAlgo_BuilderSolid aSB(aAlr1);
558     //
559     //aSB.SetContext(myContext);
560     aSB.SetShapes(aSFS);
561     aSB.Perform();
562     iErr=aSB.ErrorStatus();
563     if (iErr) {
564       myErrorStatus=30; // SolidBuilder failed
565       return;
566     }
567     //
568     const BOPCol_ListOfShape& aLSR=aSB.Areas();
569     //
570     // 1.4 Collect resulting solids and theirs set of faces. 
571     //     Update Images.
572     if (!myImages.IsBound(aS)) {
573       BOPCol_ListOfShape aLSx;
574       //
575       myImages.Bind(aS, aLSx);
576       BOPCol_ListOfShape& aLSIm=myImages.ChangeFind(aS);
577       //
578       aIt.Initialize(aLSR);
579       for (; aIt.More(); aIt.Next()) {
580         BOPTools_Set aST;
581         //
582         const TopoDS_Shape& aSR=aIt.Value();
583         aST.Add(aSR, TopAbs_FACE);
584         //
585         bFlagSD=aMST.Contains(aST);
586         //
587         const BOPTools_Set& aSTx=aMST.Added(aST);
588         const TopoDS_Shape& aSx=aSTx.Shape();
589         aLSIm.Append(aSx);
590         //
591         if (bFlagSD) {
592           myShapesSD.Bind(aSR, aSx);
593         }
594       }
595     }
596   }// for (i=0; i<aNbS; ++i) {
597 }
598
599 //=======================================================================
600 //function :FillInternalShapes 
601 //purpose  : 
602 //=======================================================================
603 void BOPAlgo_Builder::FillInternalShapes()
604 {
605   myErrorStatus=0;
606   //
607   Standard_Integer i, j,  aNbS, aNbSI, aNbSx, aNbSd;
608   TopAbs_ShapeEnum aType;
609   TopAbs_State aState; 
610   TopoDS_Iterator aItS;
611   BRep_Builder aBB;
612   BOPCol_MapIteratorOfMapOfShape aItM;
613   BOPCol_ListIteratorOfListOfShape aIt, aIt1;
614   //
615   Handle(NCollection_IncAllocator) aAllocator;
616   //-----------------------------------------------------scope f
617   aAllocator=new NCollection_IncAllocator();
618   //
619   BOPCol_IndexedDataMapOfShapeListOfShape aMSx(100, aAllocator);
620   BOPCol_IndexedMapOfShape aMx(100, aAllocator);
621   BOPCol_MapOfShape aMSI(100, aAllocator);
622   BOPCol_MapOfShape aMFence(100, aAllocator);
623   BOPCol_MapOfShape aMSOr(100, aAllocator);
624   BOPCol_ListOfShape aLSd(aAllocator);
625   BOPCol_ListOfShape aLArgs(aAllocator);
626   BOPCol_ListOfShape aLSC(aAllocator);
627   //
628   // 1. Shapes to process
629   //
630   // 1.1 Shapes from pure arguments aMSI 
631   // 1.1.1 vertex, edge, wire
632   //
633   aIt.Initialize(myArguments);
634   for (; aIt.More(); aIt.Next()) {
635     const TopoDS_Shape& aS=aIt.Value();
636     TreatCompound(aS, aMFence, aLSC);
637   }
638   aIt.Initialize(aLSC);
639   for (; aIt.More(); aIt.Next()) {
640     const TopoDS_Shape& aS=aIt.Value();
641     aType=aS.ShapeType();
642     if (aType==TopAbs_WIRE) {
643       aItS.Initialize(aS);
644       for(; aItS.More(); aItS.Next()) {
645         const TopoDS_Shape& aE=aItS.Value();
646         if (aMFence.Add(aE)) {
647           aLArgs.Append(aE);
648         }
649       }
650     }
651     else if (aType==TopAbs_VERTEX || aType==TopAbs_EDGE){
652       aLArgs.Append(aS);
653     } 
654   }
655   aMFence.Clear();
656   //
657   aIt.Initialize(aLArgs);
658   for (; aIt.More(); aIt.Next()) {
659     const TopoDS_Shape& aS=aIt.Value();
660     aType=aS.ShapeType();
661     if (aType==TopAbs_VERTEX || aType==TopAbs_EDGE ||aType==TopAbs_WIRE) {
662       if (aMFence.Add(aS)) {
663         if (myImages.IsBound(aS)) {
664           const BOPCol_ListOfShape &aLSp=myImages.Find(aS);
665           aIt1.Initialize(aLSp);
666           for (; aIt1.More(); aIt1.Next()) {
667             const TopoDS_Shape& aSp=aIt1.Value();
668             aMSI.Add(aSp);
669           }
670         }
671         else {
672           aMSI.Add(aS);
673         }
674       }
675     }
676   }
677   
678   aNbSI=aMSI.Extent();
679   //
680   // 2. Internal vertices, edges from source solids
681   aMFence.Clear();
682   aLSd.Clear();
683   //
684   aNbS=myDS->NbSourceShapes();
685   for (i=0; i<aNbS; ++i) {
686     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
687     //
688     if (aSI.ShapeType()!=TopAbs_SOLID) {
689       continue;
690     }
691     //
692     const TopoDS_Shape& aS=aSI.Shape();
693     //
694     aMx.Clear();
695     OwnInternalShapes(aS, aMx);
696     //
697     aNbSx=aMx.Extent();
698     for (j=1; j<=aNbSx; ++j) {
699       const TopoDS_Shape& aSi=aMx(j);
700       if (myImages.IsBound(aSi)) {
701         const BOPCol_ListOfShape &aLSp=myImages.Find(aSi);
702         aIt1.Initialize(aLSp);
703         for (; aIt1.More(); aIt1.Next()) {
704           const TopoDS_Shape& aSp=aIt1.Value();
705           aMSI.Add(aSp);
706         }
707       }
708       else {
709         aMSI.Add(aSi);
710       }
711     }
712     //
713     // build aux map from splits of solids
714     if (myImages.IsBound(aS)) {
715       const BOPCol_ListOfShape &aLSp=myImages.Find(aS);
716       aIt.Initialize(aLSp);
717       for (; aIt.More(); aIt.Next()) {
718         const TopoDS_Shape& aSp=aIt.Value();
719         if (aMFence.Add(aSp)) { 
720           BOPTools::MapShapesAndAncestors(aSp, TopAbs_VERTEX, TopAbs_EDGE, aMSx);
721           BOPTools::MapShapesAndAncestors(aSp, TopAbs_VERTEX, TopAbs_FACE, aMSx);
722           BOPTools::MapShapesAndAncestors(aSp, TopAbs_EDGE  , TopAbs_FACE, aMSx);
723           aLSd.Append(aSp);
724         }
725       }
726     }
727     else {
728       if (aMFence.Add(aS)) {
729         BOPTools::MapShapesAndAncestors(aS, TopAbs_VERTEX, TopAbs_EDGE, aMSx);
730         BOPTools::MapShapesAndAncestors(aS, TopAbs_VERTEX, TopAbs_FACE, aMSx);
731         BOPTools::MapShapesAndAncestors(aS, TopAbs_EDGE  , TopAbs_FACE, aMSx);
732         aLSd.Append(aS);
733         aMSOr.Add(aS); 
734       }
735     }
736   }// for (i=0; i<aNbS; ++i) {
737   //
738   aNbSd=aLSd.Extent();
739   //
740   // 3. Some shapes of aMSI can be already tied with faces of 
741   //    split solids
742   aItM.Initialize(aMSI); 
743   for (; aItM.More(); aItM.Next()) {
744     const TopoDS_Shape& aSI=aItM.Key();
745     if (aMSx.Contains(aSI)) {
746       const BOPCol_ListOfShape &aLSx=aMSx.FindFromKey(aSI);
747       aNbSx=aLSx.Extent();
748       if (aNbSx) {
749         aMSI.Remove(aSI);
750       }
751     }
752   }
753   //
754   // 4. Just check it
755   aNbSI=aMSI.Extent();
756   if (!aNbSI) {
757     return;
758   }
759   //
760   // 5 Settle internal vertices and edges into solids
761   aMx.Clear();
762   aIt.Initialize(aLSd);
763   for (; aIt.More(); aIt.Next()) {
764     TopoDS_Solid aSd=TopoDS::Solid(aIt.Value());
765     //
766     aItM.Initialize(aMSI); 
767     for (; aItM.More(); aItM.Next()) {
768       TopoDS_Shape aSI=aItM.Key();
769       aSI.Orientation(TopAbs_INTERNAL);
770       //
771       aState=BOPTools_AlgoTools::ComputeStateByOnePoint(aSI, aSd, 1.e-11, myContext);
772       if (aState==TopAbs_IN) {
773         //
774         if(aMSOr.Contains(aSd)) {
775           //
776           TopoDS_Solid aSdx;
777           //
778           aBB.MakeSolid(aSdx);
779           aItS.Initialize(aSd);
780           for (; aItS.More(); aItS.Next()) {
781             const TopoDS_Shape& aSh=aItS.Value();
782             aBB.Add(aSdx, aSh);
783           }
784           //
785           aBB.Add(aSdx, aSI);
786           //
787           if (myImages.IsBound(aSdx)) {
788             BOPCol_ListOfShape& aLS=myImages.ChangeFind(aSdx);
789             aLS.Append(aSdx);
790           } 
791           else {
792             BOPCol_ListOfShape aLS;
793             aLS.Append(aSdx);
794             myImages.Bind(aSd, aLS);
795           }
796           //
797           aMSOr.Remove(aSd);
798           aSd=aSdx;
799         }
800         else {
801           aBB.Add(aSd, aSI);
802         }
803         //
804         aMSI.Remove(aSI);
805       } //if (aState==TopAbs_IN) {
806     }// for (; aItM.More(); aItM.Next()) {
807   }//for (; aIt1.More(); aIt1.Next()) {
808   //
809   //-----------------------------------------------------scope t
810   aLArgs.Clear();
811   aLSd.Clear();
812   aMSOr.Clear();
813   aMFence.Clear();
814   aMSI.Clear();
815   aMx.Clear();
816   aMSx.Clear();
817 }
818 //=======================================================================
819 //function : BuildBndBox
820 //purpose  : 
821 //=======================================================================
822 void BOPAlgo_Builder::BuildBndBox(const Standard_Integer theIndex,
823                                   Bnd_Box& aBoxS)
824 {
825   Standard_Boolean bIsOpenBox;
826   Standard_Integer nSh, nFc;
827   Standard_Real aTolS, aTolFc;
828   TopAbs_State aState; 
829   BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
830   //
831   const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(theIndex);
832   const TopoDS_Shape& aS=aSI.Shape();
833   const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
834   //
835   bIsOpenBox=Standard_False;
836   //
837   aTolS=0.;
838   const BOPCol_ListOfInteger& aLISh=aSI.SubShapes();
839   aItLI.Initialize(aLISh);
840   for (; aItLI.More(); aItLI.Next()) {
841     nSh=aItLI.Value();
842     const BOPDS_ShapeInfo& aSISh=myDS->ShapeInfo(nSh);
843     if (aSISh.ShapeType()!=TopAbs_SHELL) {
844       continue;
845     }
846     //
847     const BOPCol_ListOfInteger& aLIFc=aSISh.SubShapes();
848     aItLI1.Initialize(aLIFc);
849     for (; aItLI1.More(); aItLI1.Next()) {
850       nFc=aItLI1.Value();
851       const BOPDS_ShapeInfo& aSIFc=myDS->ShapeInfo(nFc);
852       if (aSIFc.ShapeType()!=TopAbs_FACE) {
853         continue;
854       }
855       //
856       const Bnd_Box& aBFc=aSIFc.Box();
857       aBoxS.Add(aBFc);
858       //
859       if (!bIsOpenBox) {
860         bIsOpenBox=(aBFc.IsOpenXmin() || aBFc.IsOpenXmax() ||
861                     aBFc.IsOpenYmin() || aBFc.IsOpenYmax() ||
862                     aBFc.IsOpenZmin() || aBFc.IsOpenZmax()); 
863         if (bIsOpenBox) {
864           break;
865         }
866       }
867       //
868       const TopoDS_Face& aFc=*((TopoDS_Face*)&aSIFc.Shape());
869       aTolFc=BRep_Tool::Tolerance(aFc);
870       if (aTolFc>aTolS) {
871         aTolS=aTolFc;
872       }
873     }//for (; aItLI1.More(); aItLI1.Next()) {
874     if (bIsOpenBox) {
875       break;
876     }
877     //
878     const TopoDS_Shell& aSh=*((TopoDS_Shell*)&aSISh.Shape());
879     bIsOpenBox=IsClosedShell(aSh);
880     if (bIsOpenBox) {
881       break;
882     }
883   }//for (; aItLI.More(); aItLI.Next()) {
884   //
885   if (bIsOpenBox) {
886     aBoxS.SetWhole();
887   }
888   else {
889     BRepClass3d_SolidClassifier& aSC=myContext->SolidClassifier(aSolid);
890     aSC.PerformInfinitePoint(aTolS);
891     aState=aSC.State();
892     if (aState==TopAbs_IN) {
893       aBoxS.SetWhole();
894     }
895   }
896 }
897 //=======================================================================
898 //function : OwnInternalShapes
899 //purpose  : 
900 //=======================================================================
901   void OwnInternalShapes(const TopoDS_Shape& theS,
902                          BOPCol_IndexedMapOfShape& theMx)
903 {
904   TopoDS_Iterator aIt;
905   //
906   aIt.Initialize(theS);
907   for (; aIt.More(); aIt.Next()) {
908     const TopoDS_Shape& aSx=aIt.Value();
909     if (aSx.ShapeType()!=TopAbs_SHELL) {
910       theMx.Add(aSx);
911     }
912   }
913 }
914 //=======================================================================
915 //function : IsClosedShell
916 //purpose  : 
917 //=======================================================================
918 Standard_Boolean IsClosedShell(const TopoDS_Shell& aSh)
919 {
920   Standard_Boolean bRet;
921   Standard_Integer i, aNbE, aNbF;
922   TopAbs_Orientation aOrF;
923   BOPCol_IndexedDataMapOfShapeListOfShape aMEF; 
924   BOPCol_ListIteratorOfListOfShape aItLS;
925   //
926   bRet=Standard_False;
927   //
928   BOPTools::MapShapesAndAncestors(aSh, TopAbs_EDGE, TopAbs_FACE, aMEF);
929   // 
930   aNbE=aMEF.Extent();
931   for (i=1; i<=aNbE; ++i) {
932     const TopoDS_Edge& aE=*((TopoDS_Edge*)&aMEF.FindKey(i));
933     if (BRep_Tool::Degenerated(aE)) {
934       continue;
935     }
936     //
937     aNbF=0;
938     const BOPCol_ListOfShape& aLF=aMEF(i);
939     aItLS.Initialize(aLF);
940     for (; aItLS.More(); aItLS.Next()) {
941       const TopoDS_Shape& aF=aItLS.Value();
942       aOrF=aF.Orientation();
943       if (aOrF==TopAbs_INTERNAL || aOrF==TopAbs_EXTERNAL) {
944         continue;
945       }
946       ++aNbF;
947     }
948     //
949     if (aNbF==1) {
950       bRet=!bRet; // True
951       break;
952     }
953   }
954   //
955   return bRet;
956 }
957 //=======================================================================
958 //function : TreatCompound
959 //purpose  : 
960 //=======================================================================
961 void TreatCompound(const TopoDS_Shape& theS,
962                    BOPCol_MapOfShape& aMFence,
963                    BOPCol_ListOfShape& theLS)
964 {
965   TopAbs_ShapeEnum aType;
966   //
967   aType = theS.ShapeType();
968   if (aType != TopAbs_COMPOUND) {
969     if (aMFence.Add(theS)) {
970       theLS.Append(theS);
971     }
972     return;
973   }
974   //
975   TopoDS_Iterator aIt;
976   //
977   aIt.Initialize(theS);
978   for (; aIt.More(); aIt.Next()) {
979     const TopoDS_Shape& aS = aIt.Value();
980     TreatCompound(aS, aMFence, theLS);
981   }
982 }
983
984 //
985 // ErrorStatus
986 // 30 - SolidBuilder failed
987 // A