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