89bb2be6589d8cf4e2abc5d13092692c0b787e4f
[occt.git] / src / BOPAlgo / BOPAlgo_BuilderSolid.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_BuilderSolid.ixx>
19 //
20 #include <NCollection_List.hxx>
21 #include <NCollection_DataMap.hxx>
22 #include <NCollection_UBTreeFiller.hxx>
23 #include <NCollection_IncAllocator.hxx>
24 //
25 #include <gp_Pnt2d.hxx>
26 #include <gp_Pln.hxx>
27 #include <gp_Vec.hxx>
28 #include <gp_Dir.hxx>
29 #include <gp_Pnt.hxx>
30 //
31 #include <TColStd_MapIntegerHasher.hxx>
32 //
33 #include <Geom_Curve.hxx>
34 #include <Geom_Surface.hxx>
35 #include <Geom2d_Curve.hxx>
36 //
37 #include <TopAbs.hxx>
38 //
39 #include <TopoDS_Iterator.hxx>
40 #include <TopoDS_Face.hxx>
41 #include <TopoDS_Shape.hxx>
42 #include <TopoDS_Shell.hxx>
43 #include <TopoDS_Edge.hxx>
44 #include <TopoDS_Solid.hxx>
45 #include <TopoDS_Vertex.hxx>
46 #include <TopoDS_Compound.hxx>
47
48 #include <BRep_Builder.hxx>
49 #include <BRep_Tool.hxx>
50 //
51 #include <TopExp.hxx>
52 #include <TopExp_Explorer.hxx>
53 //
54 #include <BRepBndLib.hxx>
55 #include <BRepClass3d_SolidClassifier.hxx>
56 //
57 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
58 #include <BOPCol_ListOfShape.hxx>
59 #include <BOPCol_MapOfOrientedShape.hxx>
60 #include <BOPCol_DataMapOfShapeShape.hxx>
61 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
62 #include <BOPCol_MapOfShape.hxx>
63 #include <BOPCol_BoxBndTree.hxx>
64 #include <BOPCol_ListOfInteger.hxx>
65 #include <BOPCol_NCVector.hxx>
66 #include <BOPCol_Parallel.hxx>
67 //
68 #include <BOPTools.hxx>
69 #include <BOPTools_CoupleOfShape.hxx>
70 #include <BOPTools_AlgoTools.hxx>
71 #include <BOPTools_AlgoTools3D.hxx>
72 //
73 #include <IntTools_Context.hxx>
74 //
75 #include <BOPAlgo_ShellSplitter.hxx>
76
77
78 static
79   Standard_Boolean IsGrowthShell(const TopoDS_Shape& ,
80                                  const BOPCol_IndexedMapOfShape& );
81 static
82   Standard_Boolean IsHole(const TopoDS_Shape& ,
83                           Handle(IntTools_Context)& );
84 static
85   Standard_Boolean IsInside(const TopoDS_Shape& ,
86                             const TopoDS_Shape& ,
87                             Handle(IntTools_Context)& );
88 static
89   void MakeInternalShells(const BOPCol_MapOfShape& ,
90                           BOPCol_ListOfShape& );
91
92 //=======================================================================
93 //class     : BOPAlgo_BuilderSolid_ShapeBox
94 //purpose   : Auxiliary class
95 //=======================================================================
96 class BOPAlgo_BuilderSolid_ShapeBox {
97  public:
98   BOPAlgo_BuilderSolid_ShapeBox() {
99     myIsHole=Standard_False;
100   };
101   //
102   ~BOPAlgo_BuilderSolid_ShapeBox() {
103   };
104   //
105   void SetShape(const TopoDS_Shape& aS) {
106     myShape=aS;
107   };
108   //
109   const TopoDS_Shape& Shape()const {
110     return myShape;
111   };
112   //
113   void SetBox(const Bnd_Box& aBox) {
114     myBox=aBox;
115   };
116   //
117   const Bnd_Box& Box()const {
118     return myBox;
119   };
120   //
121   void SetIsHole(const Standard_Boolean bFlag) {
122     myIsHole=bFlag;
123   };
124   //
125   Standard_Boolean IsHole()const {
126     return myIsHole;
127   };
128   //
129  protected:
130   Standard_Boolean myIsHole;
131   TopoDS_Shape myShape;
132   Bnd_Box myBox;
133 };
134 //
135 typedef NCollection_DataMap
136   <Standard_Integer, 
137   BOPAlgo_BuilderSolid_ShapeBox, 
138   TColStd_MapIntegerHasher> BOPAlgo_DataMapOfIntegerBSSB; 
139 //
140 typedef BOPAlgo_DataMapOfIntegerBSSB::Iterator 
141   BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB; 
142 //
143 //=======================================================================
144 //function : BOPAlgo_FacePnt
145 //purpose  : 
146 //=======================================================================
147 class BOPAlgo_FacePnt {
148  public:
149   BOPAlgo_FacePnt() {
150   }
151   //
152   virtual ~BOPAlgo_FacePnt() {
153   }
154   //
155   void SetFace(const TopoDS_Face& aFace) {
156     myFace=aFace;
157   }
158   //
159   const TopoDS_Face& Face()const {
160     return myFace;
161   }
162   // 
163   void SetPnt(const gp_Pnt& aPnt) {
164     myPnt=aPnt;
165   }
166   //
167   const gp_Pnt& Pnt()const {
168     return myPnt;
169   }
170   //
171  protected:
172   gp_Pnt myPnt;
173   TopoDS_Face myFace;
174 };
175 //
176 typedef BOPCol_NCVector
177   <BOPAlgo_FacePnt> BOPAlgo_VectorOfFacePnt; 
178 //
179 //=======================================================================
180 //function : BOPAlgo_FaceSolid
181 //purpose  : 
182 //=======================================================================
183 class BOPAlgo_FaceSolid : public BOPAlgo_Algo {
184  public:
185   DEFINE_STANDARD_ALLOC
186
187   BOPAlgo_FaceSolid() :
188     myIsInternalFace(Standard_False) {
189   }
190   //
191   virtual ~BOPAlgo_FaceSolid() {
192   }
193   //
194   void SetFace(const TopoDS_Face& aFace) {
195     myFace=aFace;
196   }
197   //
198   const TopoDS_Face& Face()const {
199     return myFace;
200   }
201   //
202   void SetSolid(const TopoDS_Solid& aSolid) {
203     mySolid=aSolid;
204   }
205   //
206   const TopoDS_Solid& Solid()const {
207     return mySolid;
208   }
209   //
210   void SetPnt(const gp_Pnt& aPnt) {
211     myPnt=aPnt;
212   }
213   //
214   const gp_Pnt& Pnt()const {
215     return myPnt;
216   }
217   void SetContext(const Handle(IntTools_Context)& aContext) {
218     myContext=aContext;
219   }
220   //
221   const Handle(IntTools_Context)& Context()const {
222     return myContext;
223   }
224   //
225   Standard_Boolean IsInternalFace() const {
226     return myIsInternalFace;
227   }
228   //
229   virtual void Perform () {
230     TopAbs_State aState;
231     //
232     BOPAlgo_Algo::UserBreak();
233     //
234     aState=BOPTools_AlgoTools::ComputeState(myPnt, mySolid,
235                                             Precision::Confusion(),
236                                             myContext);
237     //
238     myIsInternalFace=(aState==TopAbs_IN);
239   }
240   //
241  protected:
242   Standard_Boolean myIsInternalFace;
243   gp_Pnt myPnt;
244   TopoDS_Face myFace;
245   TopoDS_Solid mySolid;
246   Handle(IntTools_Context) myContext;
247 };
248 //=======================================================================
249 typedef BOPCol_NCVector
250   <BOPAlgo_FaceSolid> BOPAlgo_VectorOfFaceSolid; 
251 //
252 typedef BOPCol_ContextFunctor 
253   <BOPAlgo_FaceSolid,
254   BOPAlgo_VectorOfFaceSolid,
255   Handle(IntTools_Context), 
256   IntTools_Context> BOPAlgo_FaceSolidFunctor;
257 //
258 typedef BOPCol_ContextCnt 
259   <BOPAlgo_FaceSolidFunctor,
260   BOPAlgo_VectorOfFaceSolid,
261   Handle(IntTools_Context)> BOPAlgo_FaceSolidCnt;
262 //
263 //=======================================================================
264 typedef NCollection_DataMap
265   <TopoDS_Shape, 
266   gp_Pnt, 
267   TopTools_ShapeMapHasher> BOPAlgo_DataMapOfShapePnt; 
268
269 typedef BOPAlgo_DataMapOfShapePnt::Iterator 
270   BOPAlgo_DataMapIteratorOfDataMapOfShapePnt; 
271 //
272 //=======================================================================
273 //function : 
274 //purpose  : 
275 //=======================================================================
276 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid()
277 :
278   BOPAlgo_BuilderArea()
279 {
280 }
281 //=======================================================================
282 //function : 
283 //purpose  : 
284 //=======================================================================
285 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid
286   (const Handle(NCollection_BaseAllocator)& theAllocator)
287 :
288   BOPAlgo_BuilderArea(theAllocator)
289 {
290 }
291 //=======================================================================
292 //function : ~
293 //purpose  : 
294 //=======================================================================
295 BOPAlgo_BuilderSolid::~BOPAlgo_BuilderSolid()
296 {
297 }
298 //=======================================================================
299 //function : SetSolid 
300 //purpose  : 
301 //=======================================================================
302 void BOPAlgo_BuilderSolid::SetSolid(const TopoDS_Solid& aS)
303 {
304   mySolid=aS;
305 }
306 //=======================================================================
307 //function : Solid 
308 //purpose  : 
309 //=======================================================================
310 const TopoDS_Solid& BOPAlgo_BuilderSolid::Solid()const
311 {
312   return mySolid;
313 }
314 //=======================================================================
315 //function : Perform
316 //purpose  : 
317 //=======================================================================
318 void BOPAlgo_BuilderSolid::Perform()
319 {
320   myErrorStatus=0;
321   //
322   if (myContext.IsNull()) {
323     myContext=new IntTools_Context;
324   }
325   //
326   TopoDS_Compound aC;
327   BRep_Builder aBB;
328   BOPCol_ListIteratorOfListOfShape aIt;
329   //
330   aBB.MakeCompound(aC);
331   aIt.Initialize(myShapes);
332   for(; aIt.More(); aIt.Next()) {
333     const TopoDS_Shape& aF=aIt.Value();
334     aBB.Add(aC, aF);
335   }
336   //
337   UserBreak();
338   //
339   PerformShapesToAvoid();
340   if (myErrorStatus) {
341     return;
342   }
343   //
344   UserBreak();
345   //
346   PerformLoops();
347   if (myErrorStatus) {
348     return;
349   }
350   //
351   UserBreak();
352   //
353   PerformAreas();
354   if (myErrorStatus) {
355     return;
356   }
357   //
358   UserBreak();
359   //
360   PerformInternalShapes();
361   if (myErrorStatus) {
362     return;
363   }
364 }
365 //=======================================================================
366 //function :PerformShapesToAvoid
367 //purpose  : 
368 //=======================================================================
369 void BOPAlgo_BuilderSolid::PerformShapesToAvoid()
370 {
371   Standard_Boolean bFound;
372   Standard_Integer i, iCnt, aNbE, aNbF;
373   TopAbs_Orientation aOrE;
374   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
375   BOPCol_ListIteratorOfListOfShape aIt;
376   //
377   myShapesToAvoid.Clear();
378   //
379   iCnt=0;
380   for(;;) {
381     ++iCnt;
382     bFound=Standard_False;
383     //
384     // 1. MEF
385     aMEF.Clear();
386     aIt.Initialize (myShapes);
387     for (; aIt.More(); aIt.Next()) {
388       const TopoDS_Shape& aF=aIt.Value();
389       if (!myShapesToAvoid.Contains(aF)) {
390         BOPTools::MapShapesAndAncestors(aF, 
391                                         TopAbs_EDGE, 
392                                         TopAbs_FACE, 
393                                         aMEF);
394       }
395     }
396     aNbE=aMEF.Extent();
397     //
398     // 2. myFacesToAvoid
399     for (i=1; i<=aNbE; ++i) {
400       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aMEF.FindKey(i)));
401       if (BRep_Tool::Degenerated(aE)) {
402         continue;
403       }
404       //
405       BOPCol_ListOfShape& aLF=aMEF.ChangeFromKey(aE);
406       aNbF=aLF.Extent();
407       if (!aNbF) {
408         continue;
409       }
410       //
411       aOrE=aE.Orientation();
412       //
413       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
414       if (aNbF==1) {
415         if (aOrE==TopAbs_INTERNAL) {
416           continue;
417         }
418         bFound=Standard_True;
419         myShapesToAvoid.Add(aF1);
420       }
421       else if (aNbF==2) {
422         const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
423         if (aF2.IsSame(aF1)) {
424           if (BRep_Tool::IsClosed(aE, aF1)) {
425             continue;
426           }
427           //
428           if (aOrE==TopAbs_INTERNAL) {
429             continue;
430           }
431           //
432           bFound=Standard_True;
433           myShapesToAvoid.Add(aF1);
434           myShapesToAvoid.Add(aF2);
435         }
436       }
437     }// for (i=1; i<=aNbE; ++i) {
438     //
439     if (!bFound) {
440       break;
441     }
442     //
443   }//for(;;) {
444 }  
445 //=======================================================================
446 //function : PerformLoops
447 //purpose  : 
448 //=======================================================================
449 void BOPAlgo_BuilderSolid::PerformLoops()
450 {
451   Standard_Integer iErr;
452   BOPCol_ListIteratorOfListOfShape aIt;
453   TopoDS_Iterator aItS;
454   BOPCol_MapIteratorOfMapOfOrientedShape aItM;
455   Handle(NCollection_BaseAllocator) aAlr;
456   // 
457   myErrorStatus=0;
458   myLoops.Clear();
459   //
460   aAlr=new NCollection_IncAllocator();
461   BOPAlgo_ShellSplitter aSSp(aAlr);
462   //
463   // 1. Shells Usual
464   aIt.Initialize (myShapes);
465   for (; aIt.More(); aIt.Next()) {
466     const TopoDS_Shape& aF=aIt.Value();
467     if (!myShapesToAvoid.Contains(aF)) {
468       aSSp.AddStartElement(aF);
469     }
470   }
471   //
472   aSSp.SetRunParallel(myRunParallel);
473   aSSp.Perform();
474   iErr=aSSp.ErrorStatus();
475   if (iErr) {
476     return;
477   }
478   //
479   const BOPCol_ListOfShape& aLSh=aSSp.Shells();
480   aIt.Initialize (aLSh);
481   for (; aIt.More(); aIt.Next()) {
482     const TopoDS_Shape& aSh=aIt.Value();
483     myLoops.Append(aSh);
484   }
485   //=================================================
486   //
487   // 2. Post Treatment
488   BRep_Builder aBB;
489   BOPCol_MapOfOrientedShape AddedFacesMap;
490   BOPCol_IndexedDataMapOfShapeListOfShape aEFMap;
491   BOPCol_MapOfOrientedShape aMP;
492   //
493   // a. collect all edges that are in loops
494   aIt.Initialize (myLoops);
495   for (; aIt.More(); aIt.Next()) {
496     const TopoDS_Shape& aS=aIt.Value();
497     aItS.Initialize(aS);
498     for (; aItS.More(); aItS.Next()) {
499       const TopoDS_Shape& aF=aItS.Value();
500       aMP.Add(aF);
501     }
502   }
503   // 
504   // b. collect all edges that are to avoid
505   aItM.Initialize(myShapesToAvoid);
506   for (; aItM.More(); aItM.Next()) {
507     const TopoDS_Shape& aF=aItM.Key();
508     aMP.Add(aF);
509   }
510   //
511   // c. add all edges that are not processed to myShapesToAvoid
512   aIt.Initialize (myShapes);
513   for (; aIt.More(); aIt.Next()) {
514     const TopoDS_Shape& aF=aIt.Value();
515     if (!aMP.Contains(aF)) {
516       myShapesToAvoid.Add(aF);
517     }
518   }
519   //=================================================
520   //
521   // 3.Internal Shells
522   myLoopsInternal.Clear();
523   //
524   aEFMap.Clear();
525   AddedFacesMap.Clear();
526   //
527   aItM.Initialize(myShapesToAvoid);
528   for (; aItM.More(); aItM.Next()) {
529     const TopoDS_Shape& aFF=aItM.Key();
530     BOPTools::MapShapesAndAncestors(aFF, 
531         TopAbs_EDGE, TopAbs_FACE, 
532         aEFMap);
533   }
534   //
535   aItM.Initialize(myShapesToAvoid);
536   for (; aItM.More(); aItM.Next()) {
537     const TopoDS_Shape& aFF=aItM.Key();
538     if (!AddedFacesMap.Add(aFF)) {
539       continue;
540     }
541     //
542     // make a new shell
543     TopExp_Explorer aExp;
544     TopoDS_Shell aShell;
545     aBB.MakeShell(aShell);
546     aBB.Add(aShell, aFF);
547     //
548     aItS.Initialize(aShell);
549     for (; aItS.More(); aItS.Next()) {
550       const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItS.Value()));
551       //
552       aExp.Init(aF, TopAbs_EDGE);
553       for (; aExp.More(); aExp.Next()) {
554         const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
555         const BOPCol_ListOfShape& aLF=aEFMap.FindFromKey(aE);
556         aIt.Initialize(aLF);
557         for (; aIt.More(); aIt.Next()) { 
558           const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aIt.Value()));
559           if (AddedFacesMap.Add(aFL)){
560             aBB.Add(aShell, aFL);
561           }
562         }
563       }
564     }
565     aShell.Closed (BRep_Tool::IsClosed (aShell));
566     myLoopsInternal.Append(aShell);
567   }
568 }
569 //=======================================================================
570 //function : PerformAreas
571 //purpose  : 
572 //=======================================================================
573 void BOPAlgo_BuilderSolid::PerformAreas()
574 {
575   Standard_Boolean bIsGrowth, bIsHole;
576   Standard_Integer k;
577   BRep_Builder aBB; 
578   BOPCol_ListIteratorOfListOfShape aItLS;
579   BOPCol_ListOfShape aNewSolids, aHoleShells; 
580   BOPCol_DataMapOfShapeShape aInOutMap;
581   BOPCol_IndexedMapOfShape aMHF;
582   BOPCol_ListIteratorOfListOfInteger aItLI;
583   BOPCol_BoxBndTreeSelector aSelector;
584   BOPCol_BoxBndTree aBBTree;
585   NCollection_UBTreeFiller 
586     <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
587   BOPAlgo_DataMapOfIntegerBSSB aDMISB(100);
588   BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB aItDMISB;
589   BOPCol_DataMapOfShapeListOfShape aMSH;
590   BOPCol_DataMapIteratorOfDataMapOfShapeShape aItDMSS;
591   BOPCol_DataMapIteratorOfDataMapOfShapeListOfShape aItMSH;
592   //
593   myErrorStatus=0;
594   //
595   myAreas.Clear();
596   //
597   //  Draft solids [aNewSolids]
598   aItLS.Initialize(myLoops);
599   for (k=0; aItLS.More(); aItLS.Next(), ++k) {
600     TopoDS_Solid aSolid;
601     Bnd_Box aBox;
602     BOPAlgo_BuilderSolid_ShapeBox aSB;
603     //
604     const TopoDS_Shape& aShell = aItLS.Value();
605     aSB.SetShape(aShell);
606     //
607     BRepBndLib::Add(aShell, aBox);
608     bIsHole=Standard_False;
609     //
610     bIsGrowth=IsGrowthShell(aShell, aMHF);
611     if (bIsGrowth) {
612       // make a growth solid from a shell
613       aBB.MakeSolid(aSolid);
614       aBB.Add (aSolid, aShell);
615       //
616       aNewSolids.Append (aSolid);
617       aSB.SetShape(aSolid);
618     }
619     else{
620       // check if a shell is a hole
621       bIsHole=IsHole(aShell, myContext);
622       if (bIsHole) {
623         aHoleShells.Append(aShell);
624         BOPTools::MapShapes(aShell, TopAbs_FACE, aMHF);
625         aSB.SetShape(aShell);
626       }
627       else {
628         // make a growth solid from a shell
629         aBB.MakeSolid(aSolid);
630         aBB.Add (aSolid, aShell);
631         //
632         aNewSolids.Append (aSolid);
633         aSB.SetShape(aSolid);
634       }
635     }
636     //
637     aSB.SetBox(aBox);
638     aSB.SetIsHole(bIsHole);
639     aDMISB.Bind(k, aSB);
640   }  
641   //
642   // 2. Prepare TreeFiller
643   aItDMISB.Initialize(aDMISB);
644   for (; aItDMISB.More(); aItDMISB.Next()) {
645     k=aItDMISB.Key();
646     const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
647     //
648     bIsHole=aSB.IsHole();
649     if (bIsHole) {
650       const Bnd_Box& aBox=aSB.Box();
651       aTreeFiller.Add(k, aBox);
652     }
653   }
654   //
655   // 3. Shake TreeFiller
656   aTreeFiller.Fill();
657   //
658   // 4. Find outer growth shell that is most close 
659   //    to each hole shell
660   aItDMISB.Initialize(aDMISB);
661   for (; aItDMISB.More(); aItDMISB.Next()) {
662     k=aItDMISB.Key();
663     const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
664     bIsHole=aSB.IsHole();
665     if (bIsHole) {
666       continue;
667     }
668     //
669     const TopoDS_Shape aSolid=aSB.Shape();
670     const Bnd_Box& aBoxSolid=aSB.Box();
671     //
672     aSelector.Clear();
673     aSelector.SetBox(aBoxSolid);
674     //
675     aBBTree.Select(aSelector);
676     //
677     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
678     //
679     aItLI.Initialize(aLI);
680     for (; aItLI.More(); aItLI.Next()) {
681       k=aItLI.Value();
682       const BOPAlgo_BuilderSolid_ShapeBox& aSBk=aDMISB.Find(k);
683       const TopoDS_Shape& aHole=aSBk.Shape();
684       //
685       if (!IsInside(aHole, aSolid, myContext)){
686         continue;
687       }
688       //
689       if (aInOutMap.IsBound (aHole)){
690         const TopoDS_Shape& aSolidWas=aInOutMap(aHole);
691         if (IsInside(aSolid, aSolidWas, myContext)) {
692           aInOutMap.UnBind(aHole);
693           aInOutMap.Bind (aHole, aSolid);
694         }
695       }
696       else{
697         aInOutMap.Bind(aHole, aSolid);
698       }
699     }
700   }//for (; aItDMISB.More(); aItDMISB.Next()) {
701   //
702   // 5. Map [Solid/Holes] -> aMSH 
703   aItDMSS.Initialize(aInOutMap);
704   for (; aItDMSS.More(); aItDMSS.Next()) {
705     const TopoDS_Shape& aHole=aItDMSS.Key();
706     const TopoDS_Shape& aSolid=aItDMSS.Value();
707     //
708     if (aMSH.IsBound(aSolid)) {
709       BOPCol_ListOfShape& aLH=aMSH.ChangeFind(aSolid);
710       aLH.Append(aHole);
711     }
712     else {
713       BOPCol_ListOfShape aLH;
714       aLH.Append(aHole);
715       aMSH.Bind(aSolid, aLH);
716     }
717   }
718   //
719   // 6. Add aHoles to Solids
720   aItMSH.Initialize(aMSH);
721   for (; aItMSH.More(); aItMSH.Next()) {
722     TopoDS_Solid aSolid=(*(TopoDS_Solid*)(&aItMSH.Key()));
723     //
724     const BOPCol_ListOfShape& aLH=aItMSH.Value();
725     aItLS.Initialize(aLH);
726     for (; aItLS.More(); aItLS.Next()) {
727       const TopoDS_Shape& aHole = aItLS.Value();
728       aBB.Add (aSolid, aHole);
729     }
730     //
731     // update classifier
732     BRepClass3d_SolidClassifier& aSC=
733       myContext->SolidClassifier(aSolid);
734     aSC.Load(aSolid);
735     //
736   }
737   //
738   // 7. These aNewSolids are draft solids that 
739   // do not contain any internal shapes
740   aItLS.Initialize(aNewSolids);
741   for ( ; aItLS.More(); aItLS.Next()) {
742     const TopoDS_Shape& aSx=aItLS.Value();
743     myAreas.Append(aSx);
744   }
745   // Add holes that outside the solids to myAreas
746   aItLS.Initialize(aHoleShells);
747   for (; aItLS.More(); aItLS.Next()) {
748     const TopoDS_Shape& aHole = aItLS.Value();
749     if (!aInOutMap.IsBound(aHole)){
750       TopoDS_Solid aSolid;
751       //
752       aBB.MakeSolid(aSolid);
753       aBB.Add (aSolid, aHole);
754       //
755       myAreas.Append(aSolid);
756     }
757   }
758 }
759 //=======================================================================
760 //function : PerformInternalShapes
761 //purpose  : 
762 //=======================================================================
763 void BOPAlgo_BuilderSolid::PerformInternalShapes()
764 {
765   myErrorStatus=0;
766   //
767   Standard_Integer aNbFI=myLoopsInternal.Extent();
768   if (!aNbFI) {// nothing to do
769     return;
770   }
771   // 
772   Standard_Boolean bIsInternalFace;
773   Standard_Integer k, aNbVFS, aNbSLF, aNbVFP, aNbA;
774   BRep_Builder aBB;
775   TopoDS_Iterator aIt;
776   TopExp_Explorer aExp;
777   BOPCol_ListIteratorOfListOfShape  aItLS;
778   BOPCol_MapOfShape aMFs;
779   BOPCol_ListOfShape aLSI;
780   BOPAlgo_VectorOfFaceSolid aVFS;
781   BOPAlgo_VectorOfFacePnt aVFP;
782   BOPCol_ListIteratorOfListOfInteger aItLI;
783   BOPCol_BoxBndTreeSelector aSelector;
784   BOPCol_BoxBndTree aBBTree;
785   NCollection_UBTreeFiller 
786     <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
787   //
788   aNbA=myAreas.Extent();
789   //
790   // 1. aVFP
791   aItLS.Initialize(myLoopsInternal);
792   for (; aItLS.More(); aItLS.Next()) {
793     const TopoDS_Shape& aShell=aItLS.Value();
794     aIt.Initialize(aShell);
795     for (; aIt.More(); aIt.Next()) {
796       const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
797       //
798       if (aMFs.Add(aF)) {
799         gp_Pnt aP;
800         gp_Pnt2d aP2D;
801         //
802         if (aNbA) {
803           BOPTools_AlgoTools3D::PointInFace(aF, aP, aP2D, myContext);
804         }
805         //
806         BOPAlgo_FacePnt& aFP=aVFP.Append1();
807         aFP.SetFace(aF);
808         aFP.SetPnt(aP);
809       }
810     }
811   }
812   //
813   if (!aNbA) {
814     // 7b. "Rest" faces treatment
815     TopoDS_Solid aSolid;
816     aBB.MakeSolid(aSolid);
817     //
818     MakeInternalShells(aMFs, aLSI);
819     //
820     aItLS.Initialize(aLSI);
821     for (; aItLS.More(); aItLS.Next()) {
822       const TopoDS_Shape& aSI=aItLS.Value();
823        aBB.Add (aSolid, aSI);
824     }
825     myAreas.Append(aSolid);
826     //
827     return; // =>
828   }//if (!aNbA) {
829   //
830   // 2. Prepare TreeFiller 
831   aNbVFP=aVFP.Extent();
832   for(k=0; k<aNbVFP; ++k) {
833     Bnd_Box aBox;
834     //
835     const BOPAlgo_FacePnt& aFP=aVFP(k);
836     const TopoDS_Face& aF=aFP.Face();
837     //
838     BRepBndLib::Add(aF, aBox);
839     aTreeFiller.Add(k, aBox);
840   }
841   //
842   aTreeFiller.Fill();
843   //
844   // 3. Face/Solid candidates: aVFS
845   aItLS.Initialize(myAreas);
846   for (; aItLS.More(); aItLS.Next()) {
847     Bnd_Box aBox;
848     //
849     TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aItLS.Value()));
850     BRepBndLib::Add(aSolid, aBox);
851     //
852     aMFs.Clear();
853     aExp.Init(aSolid, TopAbs_FACE);
854     for (; aExp.More(); aExp.Next()) {
855       const TopoDS_Shape& aFs=aExp.Current();
856       aMFs.Add(aFs);
857     }
858     //
859     aSelector.Clear();
860     aSelector.SetBox(aBox);
861     //
862     aBBTree.Select(aSelector);
863     //
864     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
865     aItLI.Initialize(aLI);
866     for (; aItLI.More(); aItLI.Next()) {
867       k=aItLI.Value();
868       const BOPAlgo_FacePnt& aFP=aVFP(k);
869       const TopoDS_Face& aF=aFP.Face();
870       if (aMFs.Contains(aF)) {
871         continue;
872       }
873       //
874       const gp_Pnt& aP=aFP.Pnt();
875       //
876       BOPAlgo_FaceSolid& aFS=aVFS.Append1();
877       aFS.SetPnt(aP);
878       aFS.SetFace(aF);
879       aFS.SetSolid(aSolid);
880     }
881   }
882   //
883   aNbVFS=aVFS.Extent();
884   if (!aNbVFS) {
885     return;
886   }
887   // 4. Refine candidares
888   //=============================================================
889   BOPAlgo_FaceSolidCnt::Perform(myRunParallel, aVFS, myContext);
890   //=============================================================
891   // 
892   // 5. Solid/Faces:  aMSLF
893   BOPCol_IndexedDataMapOfShapeListOfShape aMSLF;
894   BOPCol_MapOfShape aMFProcessed;
895   //  
896   for (k=0; k < aNbVFS; ++k) {
897     const BOPAlgo_FaceSolid& aFS=aVFS(k);
898     //
899     const TopoDS_Solid& aSolid=aFS.Solid();
900     const TopoDS_Face& aF=aFS.Face();
901     //
902     bIsInternalFace=aFS.IsInternalFace();
903     if (!bIsInternalFace) {
904       continue;
905     }
906     //
907     if (aMSLF.Contains(aSolid)) {
908       BOPCol_ListOfShape& aLF=aMSLF.ChangeFromKey(aSolid);
909       aLF.Append(aF);
910     }
911     else {
912       BOPCol_ListOfShape aLF;
913       //
914       aLF.Append(aF);
915       aMSLF.Add(aSolid, aLF);
916     }
917   }// for (k=0; k < aNbVE; ++k) {
918   //
919   // 6. Update Solids by internal Faces
920   aNbSLF=aMSLF.Extent();
921   for (k=1; k <= aNbSLF; ++k) {
922     const TopoDS_Shape& aSolid=aMSLF.FindKey(k);
923     TopoDS_Shape *pSolid=(TopoDS_Shape*)&aSolid;
924     //
925     const BOPCol_ListOfShape& aLF=aMSLF(k);
926     //
927     aMFs.Clear();
928     aItLS.Initialize(aLF);
929     for (; aItLS.More(); aItLS.Next()) {
930       const TopoDS_Shape& aF=aItLS.Value();
931       aMFs.Add(aF);
932       aMFProcessed.Add(aF);
933     }
934     //
935     aLSI.Clear();
936     MakeInternalShells(aMFs, aLSI);
937     //
938     aItLS.Initialize(aLSI);
939     for (; aItLS.More(); aItLS.Next()) {
940       const TopoDS_Shape& aSI=aItLS.Value();
941       aBB.Add (*pSolid, aSI);
942     }
943   }
944   // 
945   // 7. "Rest" faces treatment (if there are)
946   aMFs.Clear();
947   for (k=0; k < aNbVFS; ++k) {
948     const BOPAlgo_FaceSolid& aFS=aVFS(k);
949     //
950     const TopoDS_Face& aF=aFS.Face();
951     if (!aMFProcessed.Contains(aF)) {
952       aMFs.Add(aF);
953     }
954   }
955   //
956   aNbFI=aMFs.Extent();
957   if (aNbFI) {
958     TopoDS_Solid aSolid;
959     aBB.MakeSolid(aSolid);
960     //
961     aLSI.Clear();
962     MakeInternalShells(aMFs, aLSI);
963     //
964     aItLS.Initialize(aLSI);
965     for (; aItLS.More(); aItLS.Next()) {
966       const TopoDS_Shape& aSI=aItLS.Value();
967       aBB.Add (aSolid, aSI);
968     }
969     myAreas.Append(aSolid);
970   }
971 }
972 //=======================================================================
973 //function : MakeInternalShells
974 //purpose  : 
975 //=======================================================================
976 void MakeInternalShells(const BOPCol_MapOfShape& theMF,
977                         BOPCol_ListOfShape& theShells)
978 {
979   BOPCol_ListIteratorOfListOfShape aItF;
980   BRep_Builder aBB;
981   //
982   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
983   BOPCol_MapIteratorOfMapOfShape aItM;
984   BOPCol_MapOfShape aAddedFacesMap;
985   //
986   aItM.Initialize(theMF);
987   for (; aItM.More(); aItM.Next()) {
988     const TopoDS_Shape& aF=aItM.Key();
989     BOPTools::MapShapesAndAncestors(aF, 
990         TopAbs_EDGE, TopAbs_FACE, 
991         aMEF);
992   }
993   //
994   aItM.Initialize(theMF);
995   for (; aItM.More(); aItM.Next()) {
996     TopoDS_Shape aFF=aItM.Key();
997     if (!aAddedFacesMap.Add(aFF)) {
998       continue;
999     }
1000     //
1001     // make a new shell
1002     TopoDS_Shell aShell;
1003     aBB.MakeShell(aShell);    
1004     aFF.Orientation(TopAbs_INTERNAL);
1005     aBB.Add(aShell, aFF);
1006     //
1007     TopoDS_Iterator aItAddedF (aShell);
1008     for (; aItAddedF.More(); aItAddedF.Next()) {
1009       const TopoDS_Shape& aF =aItAddedF.Value();
1010       //
1011       TopExp_Explorer aEdgeExp(aF, TopAbs_EDGE);
1012       for (; aEdgeExp.More(); aEdgeExp.Next()) {
1013         const TopoDS_Shape& aE =aEdgeExp.Current();
1014         const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
1015         aItF.Initialize(aLF);
1016         for (; aItF.More(); aItF.Next()) { 
1017           TopoDS_Shape aFL=aItF.Value();
1018           if (aAddedFacesMap.Add(aFL)){
1019             aFL.Orientation(TopAbs_INTERNAL);
1020             aBB.Add(aShell, aFL);
1021           }
1022         }
1023       }
1024     }
1025     aShell.Closed (BRep_Tool::IsClosed (aShell));
1026     theShells.Append(aShell);
1027   }
1028 }
1029 //=======================================================================
1030 //function : IsHole
1031 //purpose  : 
1032 //=======================================================================
1033 Standard_Boolean IsHole(const TopoDS_Shape& theS2,
1034                         Handle(IntTools_Context)& theContext)
1035 {
1036   TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
1037   BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
1038   //
1039   aClsf.PerformInfinitePoint(::RealSmall());
1040   //
1041   return (aClsf.State()==TopAbs_IN);
1042 }
1043 //=======================================================================
1044 //function : IsInside
1045 //purpose  : 
1046 //=======================================================================
1047 Standard_Boolean IsInside(const TopoDS_Shape& theS1,
1048                           const TopoDS_Shape& theS2,
1049                           Handle(IntTools_Context)& theContext)
1050 {
1051   TopExp_Explorer aExp;
1052   TopAbs_State aState;
1053   //
1054   TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
1055   //
1056   aExp.Init(theS1, TopAbs_FACE);
1057   if (!aExp.More()){
1058     BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
1059     aClsf.PerformInfinitePoint(::RealSmall());
1060     aState=aClsf.State();
1061   }
1062   else {
1063     BOPCol_IndexedMapOfShape aBounds;
1064     BOPTools::MapShapes(*pS2, TopAbs_EDGE, aBounds);
1065     const TopoDS_Face& aF = (*(TopoDS_Face*)(&aExp.Current()));
1066     aState=BOPTools_AlgoTools::ComputeState(aF, *pS2,
1067                                             Precision::Confusion(),
1068                                             aBounds, theContext);
1069   }
1070   return (aState==TopAbs_IN);
1071 }
1072 //=======================================================================
1073 //function : IsGrowthShell
1074 //purpose  : 
1075 //=======================================================================
1076 Standard_Boolean IsGrowthShell(const TopoDS_Shape& theShell,
1077                                const BOPCol_IndexedMapOfShape& theMHF)
1078 {
1079   Standard_Boolean bRet;
1080   TopoDS_Iterator aIt;
1081   // 
1082   bRet=Standard_False;
1083   if (theMHF.Extent()) {
1084     aIt.Initialize(theShell);
1085     for(; aIt.More(); aIt.Next()) {
1086       const TopoDS_Shape& aF=aIt.Value();
1087       if (theMHF.Contains(aF)) {
1088         return !bRet;
1089       }
1090     }
1091   }
1092   return bRet;
1093 }