0024002: Overall code and build procedure refactoring -- automatic
[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
19
20 #include <BOPAlgo_BuilderSolid.hxx>
21 #include <BOPAlgo_ShellSplitter.hxx>
22 #include <BOPCol_BoxBndTree.hxx>
23 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
24 #include <BOPCol_DataMapOfShapeShape.hxx>
25 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
26 #include <BOPCol_ListOfInteger.hxx>
27 #include <BOPCol_ListOfShape.hxx>
28 #include <BOPCol_MapOfOrientedShape.hxx>
29 #include <BOPCol_MapOfShape.hxx>
30 #include <BOPCol_NCVector.hxx>
31 #include <BOPCol_Parallel.hxx>
32 #include <BOPTools.hxx>
33 #include <BOPTools_AlgoTools.hxx>
34 #include <BOPTools_AlgoTools3D.hxx>
35 #include <BOPTools_CoupleOfShape.hxx>
36 #include <BRep_Builder.hxx>
37 #include <BRep_Tool.hxx>
38 #include <BRepBndLib.hxx>
39 #include <BRepClass3d_SolidClassifier.hxx>
40 #include <Geom2d_Curve.hxx>
41 #include <Geom_Curve.hxx>
42 #include <Geom_Surface.hxx>
43 #include <gp_Dir.hxx>
44 #include <gp_Pln.hxx>
45 #include <gp_Pnt.hxx>
46 #include <gp_Pnt2d.hxx>
47 #include <gp_Vec.hxx>
48 #include <IntTools_Context.hxx>
49 #include <NCollection_DataMap.hxx>
50 #include <NCollection_IncAllocator.hxx>
51 #include <NCollection_List.hxx>
52 #include <NCollection_UBTreeFiller.hxx>
53 #include <TColStd_MapIntegerHasher.hxx>
54 #include <TopAbs.hxx>
55 #include <TopExp.hxx>
56 #include <TopExp_Explorer.hxx>
57 #include <TopoDS_Compound.hxx>
58 #include <TopoDS_Edge.hxx>
59 #include <TopoDS_Face.hxx>
60 #include <TopoDS_Iterator.hxx>
61 #include <TopoDS_Shape.hxx>
62 #include <TopoDS_Shell.hxx>
63 #include <TopoDS_Solid.hxx>
64 #include <TopoDS_Vertex.hxx>
65
66 //
67 //
68 //
69 //
70 //
71 //
72 //
73 //
74 //
75 //
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_Face& aF=*((TopoDS_Face*)&aIt.Value());
467     if (myContext->IsInfiniteFace(aF)) {
468       TopoDS_Shell aSh;
469       BRep_Builder aBB;
470       //
471       aBB.MakeShell(aSh);
472       aBB.Add(aSh, aF);
473       myLoops.Append(aSh);
474       continue;
475     }
476     //
477     if (!myShapesToAvoid.Contains(aF)) {
478       aSSp.AddStartElement(aF);
479     }
480   }
481   //
482   aSSp.SetRunParallel(myRunParallel);
483   aSSp.Perform();
484   iErr=aSSp.ErrorStatus();
485   if (iErr) {
486     return;
487   }
488   //
489   const BOPCol_ListOfShape& aLSh=aSSp.Shells();
490   aIt.Initialize (aLSh);
491   for (; aIt.More(); aIt.Next()) {
492     const TopoDS_Shape& aSh=aIt.Value();
493     myLoops.Append(aSh);
494   }
495   //=================================================
496   //
497   // 2. Post Treatment
498   BRep_Builder aBB;
499   BOPCol_MapOfOrientedShape AddedFacesMap;
500   BOPCol_IndexedDataMapOfShapeListOfShape aEFMap;
501   BOPCol_MapOfOrientedShape aMP;
502   //
503   // a. collect all edges that are in loops
504   aIt.Initialize (myLoops);
505   for (; aIt.More(); aIt.Next()) {
506     const TopoDS_Shape& aS=aIt.Value();
507     aItS.Initialize(aS);
508     for (; aItS.More(); aItS.Next()) {
509       const TopoDS_Shape& aF=aItS.Value();
510       aMP.Add(aF);
511     }
512   }
513   // 
514   // b. collect all edges that are to avoid
515   aItM.Initialize(myShapesToAvoid);
516   for (; aItM.More(); aItM.Next()) {
517     const TopoDS_Shape& aF=aItM.Key();
518     aMP.Add(aF);
519   }
520   //
521   // c. add all edges that are not processed to myShapesToAvoid
522   aIt.Initialize (myShapes);
523   for (; aIt.More(); aIt.Next()) {
524     const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
525     if (!myContext->IsInfiniteFace(aF)) {
526       if (!aMP.Contains(aF)) {
527         myShapesToAvoid.Add(aF);
528       }
529     }
530   }
531   //=================================================
532   //
533   // 3.Internal Shells
534   myLoopsInternal.Clear();
535   //
536   aEFMap.Clear();
537   AddedFacesMap.Clear();
538   //
539   aItM.Initialize(myShapesToAvoid);
540   for (; aItM.More(); aItM.Next()) {
541     const TopoDS_Shape& aFF=aItM.Key();
542     BOPTools::MapShapesAndAncestors(aFF, 
543         TopAbs_EDGE, TopAbs_FACE, 
544         aEFMap);
545   }
546   //
547   aItM.Initialize(myShapesToAvoid);
548   for (; aItM.More(); aItM.Next()) {
549     const TopoDS_Shape& aFF=aItM.Key();
550     if (!AddedFacesMap.Add(aFF)) {
551       continue;
552     }
553     //
554     // make a new shell
555     TopExp_Explorer aExp;
556     TopoDS_Shell aShell;
557     aBB.MakeShell(aShell);
558     aBB.Add(aShell, aFF);
559     //
560     aItS.Initialize(aShell);
561     for (; aItS.More(); aItS.Next()) {
562       const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItS.Value()));
563       //
564       aExp.Init(aF, TopAbs_EDGE);
565       for (; aExp.More(); aExp.Next()) {
566         const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
567         const BOPCol_ListOfShape& aLF=aEFMap.FindFromKey(aE);
568         aIt.Initialize(aLF);
569         for (; aIt.More(); aIt.Next()) { 
570           const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aIt.Value()));
571           if (AddedFacesMap.Add(aFL)){
572             aBB.Add(aShell, aFL);
573           }
574         }
575       }
576     }
577     aShell.Closed (BRep_Tool::IsClosed (aShell));
578     myLoopsInternal.Append(aShell);
579   }
580 }
581 //=======================================================================
582 //function : PerformAreas
583 //purpose  : 
584 //=======================================================================
585 void BOPAlgo_BuilderSolid::PerformAreas()
586 {
587   Standard_Boolean bIsGrowth, bIsHole;
588   Standard_Integer k;
589   BRep_Builder aBB; 
590   BOPCol_ListIteratorOfListOfShape aItLS;
591   BOPCol_ListOfShape aNewSolids, aHoleShells; 
592   BOPCol_DataMapOfShapeShape aInOutMap;
593   BOPCol_IndexedMapOfShape aMHF;
594   BOPCol_ListIteratorOfListOfInteger aItLI;
595   BOPCol_BoxBndTreeSelector aSelector;
596   BOPCol_BoxBndTree aBBTree;
597   NCollection_UBTreeFiller 
598     <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
599   BOPAlgo_DataMapOfIntegerBSSB aDMISB(100);
600   BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB aItDMISB;
601   BOPCol_DataMapOfShapeListOfShape aMSH;
602   BOPCol_DataMapIteratorOfDataMapOfShapeShape aItDMSS;
603   BOPCol_DataMapIteratorOfDataMapOfShapeListOfShape aItMSH;
604   //
605   myErrorStatus=0;
606   //
607   myAreas.Clear();
608   //
609   //  Draft solids [aNewSolids]
610   aItLS.Initialize(myLoops);
611   for (k=0; aItLS.More(); aItLS.Next(), ++k) {
612     TopoDS_Solid aSolid;
613     Bnd_Box aBox;
614     BOPAlgo_BuilderSolid_ShapeBox aSB;
615     //
616     const TopoDS_Shape& aShell = aItLS.Value();
617     aSB.SetShape(aShell);
618     //
619     BRepBndLib::Add(aShell, aBox);
620     bIsHole=Standard_False;
621     //
622     bIsGrowth=IsGrowthShell(aShell, aMHF);
623     if (bIsGrowth) {
624       // make a growth solid from a shell
625       aBB.MakeSolid(aSolid);
626       aBB.Add (aSolid, aShell);
627       //
628       aNewSolids.Append (aSolid);
629       aSB.SetShape(aSolid);
630     }
631     else{
632       // check if a shell is a hole
633       bIsHole=IsHole(aShell, myContext);
634       if (bIsHole) {
635         aHoleShells.Append(aShell);
636         BOPTools::MapShapes(aShell, TopAbs_FACE, aMHF);
637         aSB.SetShape(aShell);
638       }
639       else {
640         // make a growth solid from a shell
641         aBB.MakeSolid(aSolid);
642         aBB.Add (aSolid, aShell);
643         //
644         aNewSolids.Append (aSolid);
645         aSB.SetShape(aSolid);
646       }
647     }
648     //
649     aSB.SetBox(aBox);
650     aSB.SetIsHole(bIsHole);
651     aDMISB.Bind(k, aSB);
652   }  
653   //
654   // 2. Prepare TreeFiller
655   aItDMISB.Initialize(aDMISB);
656   for (; aItDMISB.More(); aItDMISB.Next()) {
657     k=aItDMISB.Key();
658     const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
659     //
660     bIsHole=aSB.IsHole();
661     if (bIsHole) {
662       const Bnd_Box& aBox=aSB.Box();
663       aTreeFiller.Add(k, aBox);
664     }
665   }
666   //
667   // 3. Shake TreeFiller
668   aTreeFiller.Fill();
669   //
670   // 4. Find outer growth shell that is most close 
671   //    to each hole shell
672   aItDMISB.Initialize(aDMISB);
673   for (; aItDMISB.More(); aItDMISB.Next()) {
674     k=aItDMISB.Key();
675     const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
676     bIsHole=aSB.IsHole();
677     if (bIsHole) {
678       continue;
679     }
680     //
681     const TopoDS_Shape aSolid=aSB.Shape();
682     const Bnd_Box& aBoxSolid=aSB.Box();
683     //
684     aSelector.Clear();
685     aSelector.SetBox(aBoxSolid);
686     //
687     aBBTree.Select(aSelector);
688     //
689     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
690     //
691     aItLI.Initialize(aLI);
692     for (; aItLI.More(); aItLI.Next()) {
693       k=aItLI.Value();
694       const BOPAlgo_BuilderSolid_ShapeBox& aSBk=aDMISB.Find(k);
695       const TopoDS_Shape& aHole=aSBk.Shape();
696       //
697       if (!IsInside(aHole, aSolid, myContext)){
698         continue;
699       }
700       //
701       if (aInOutMap.IsBound (aHole)){
702         const TopoDS_Shape& aSolidWas=aInOutMap(aHole);
703         if (IsInside(aSolid, aSolidWas, myContext)) {
704           aInOutMap.UnBind(aHole);
705           aInOutMap.Bind (aHole, aSolid);
706         }
707       }
708       else{
709         aInOutMap.Bind(aHole, aSolid);
710       }
711     }
712   }//for (; aItDMISB.More(); aItDMISB.Next()) {
713   //
714   // 5. Map [Solid/Holes] -> aMSH 
715   aItDMSS.Initialize(aInOutMap);
716   for (; aItDMSS.More(); aItDMSS.Next()) {
717     const TopoDS_Shape& aHole=aItDMSS.Key();
718     const TopoDS_Shape& aSolid=aItDMSS.Value();
719     //
720     if (aMSH.IsBound(aSolid)) {
721       BOPCol_ListOfShape& aLH=aMSH.ChangeFind(aSolid);
722       aLH.Append(aHole);
723     }
724     else {
725       BOPCol_ListOfShape aLH;
726       aLH.Append(aHole);
727       aMSH.Bind(aSolid, aLH);
728     }
729   }
730   //
731   // 6. Add aHoles to Solids
732   aItMSH.Initialize(aMSH);
733   for (; aItMSH.More(); aItMSH.Next()) {
734     TopoDS_Solid aSolid=(*(TopoDS_Solid*)(&aItMSH.Key()));
735     //
736     const BOPCol_ListOfShape& aLH=aItMSH.Value();
737     aItLS.Initialize(aLH);
738     for (; aItLS.More(); aItLS.Next()) {
739       const TopoDS_Shape& aHole = aItLS.Value();
740       aBB.Add (aSolid, aHole);
741     }
742     //
743     // update classifier
744     BRepClass3d_SolidClassifier& aSC=
745       myContext->SolidClassifier(aSolid);
746     aSC.Load(aSolid);
747     //
748   }
749   //
750   // 7. These aNewSolids are draft solids that 
751   // do not contain any internal shapes
752   aItLS.Initialize(aNewSolids);
753   for ( ; aItLS.More(); aItLS.Next()) {
754     const TopoDS_Shape& aSx=aItLS.Value();
755     myAreas.Append(aSx);
756   }
757   // Add holes that outside the solids to myAreas
758   aItLS.Initialize(aHoleShells);
759   for (; aItLS.More(); aItLS.Next()) {
760     const TopoDS_Shape& aHole = aItLS.Value();
761     if (!aInOutMap.IsBound(aHole)){
762       TopoDS_Solid aSolid;
763       //
764       aBB.MakeSolid(aSolid);
765       aBB.Add (aSolid, aHole);
766       //
767       myAreas.Append(aSolid);
768     }
769   }
770 }
771 //=======================================================================
772 //function : PerformInternalShapes
773 //purpose  : 
774 //=======================================================================
775 void BOPAlgo_BuilderSolid::PerformInternalShapes()
776 {
777   myErrorStatus=0;
778   //
779   Standard_Integer aNbFI=myLoopsInternal.Extent();
780   if (!aNbFI) {// nothing to do
781     return;
782   }
783   // 
784   Standard_Boolean bIsInternalFace;
785   Standard_Integer k, aNbVFS, aNbSLF, aNbVFP, aNbA;
786   BRep_Builder aBB;
787   TopoDS_Iterator aIt;
788   TopExp_Explorer aExp;
789   BOPCol_ListIteratorOfListOfShape  aItLS;
790   BOPCol_MapOfShape aMFs;
791   BOPCol_ListOfShape aLSI;
792   BOPAlgo_VectorOfFaceSolid aVFS;
793   BOPAlgo_VectorOfFacePnt aVFP;
794   BOPCol_ListIteratorOfListOfInteger aItLI;
795   BOPCol_BoxBndTreeSelector aSelector;
796   BOPCol_BoxBndTree aBBTree;
797   NCollection_UBTreeFiller 
798     <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
799   //
800   aNbA=myAreas.Extent();
801   //
802   // 1. aVFP
803   aItLS.Initialize(myLoopsInternal);
804   for (; aItLS.More(); aItLS.Next()) {
805     const TopoDS_Shape& aShell=aItLS.Value();
806     aIt.Initialize(aShell);
807     for (; aIt.More(); aIt.Next()) {
808       const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
809       //
810       if (aMFs.Add(aF)) {
811         gp_Pnt aP;
812         gp_Pnt2d aP2D;
813         //
814         if (aNbA) {
815           BOPTools_AlgoTools3D::PointInFace(aF, aP, aP2D, myContext);
816         }
817         //
818         BOPAlgo_FacePnt& aFP=aVFP.Append1();
819         aFP.SetFace(aF);
820         aFP.SetPnt(aP);
821       }
822     }
823   }
824   //
825   if (!aNbA) {
826     // 7b. "Rest" faces treatment
827     TopoDS_Solid aSolid;
828     aBB.MakeSolid(aSolid);
829     //
830     MakeInternalShells(aMFs, aLSI);
831     //
832     aItLS.Initialize(aLSI);
833     for (; aItLS.More(); aItLS.Next()) {
834       const TopoDS_Shape& aSI=aItLS.Value();
835        aBB.Add (aSolid, aSI);
836     }
837     myAreas.Append(aSolid);
838     //
839     return; // =>
840   }//if (!aNbA) {
841   //
842   // 2. Prepare TreeFiller 
843   aNbVFP=aVFP.Extent();
844   for(k=0; k<aNbVFP; ++k) {
845     Bnd_Box aBox;
846     //
847     const BOPAlgo_FacePnt& aFP=aVFP(k);
848     const TopoDS_Face& aF=aFP.Face();
849     //
850     BRepBndLib::Add(aF, aBox);
851     aTreeFiller.Add(k, aBox);
852   }
853   //
854   aTreeFiller.Fill();
855   //
856   // 3. Face/Solid candidates: aVFS
857   aItLS.Initialize(myAreas);
858   for (; aItLS.More(); aItLS.Next()) {
859     Bnd_Box aBox;
860     //
861     TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aItLS.Value()));
862     BRepBndLib::Add(aSolid, aBox);
863     //
864     aMFs.Clear();
865     aExp.Init(aSolid, TopAbs_FACE);
866     for (; aExp.More(); aExp.Next()) {
867       const TopoDS_Shape& aFs=aExp.Current();
868       aMFs.Add(aFs);
869     }
870     //
871     aSelector.Clear();
872     aSelector.SetBox(aBox);
873     //
874     aBBTree.Select(aSelector);
875     //
876     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
877     aItLI.Initialize(aLI);
878     for (; aItLI.More(); aItLI.Next()) {
879       k=aItLI.Value();
880       const BOPAlgo_FacePnt& aFP=aVFP(k);
881       const TopoDS_Face& aF=aFP.Face();
882       if (aMFs.Contains(aF)) {
883         continue;
884       }
885       //
886       const gp_Pnt& aP=aFP.Pnt();
887       //
888       BOPAlgo_FaceSolid& aFS=aVFS.Append1();
889       aFS.SetPnt(aP);
890       aFS.SetFace(aF);
891       aFS.SetSolid(aSolid);
892     }
893   }
894   //
895   aNbVFS=aVFS.Extent();
896   if (!aNbVFS) {
897     return;
898   }
899   // 4. Refine candidares
900   //=============================================================
901   BOPAlgo_FaceSolidCnt::Perform(myRunParallel, aVFS, myContext);
902   //=============================================================
903   // 
904   // 5. Solid/Faces:  aMSLF
905   BOPCol_IndexedDataMapOfShapeListOfShape aMSLF;
906   BOPCol_MapOfShape aMFProcessed;
907   //  
908   for (k=0; k < aNbVFS; ++k) {
909     const BOPAlgo_FaceSolid& aFS=aVFS(k);
910     //
911     const TopoDS_Solid& aSolid=aFS.Solid();
912     const TopoDS_Face& aF=aFS.Face();
913     //
914     bIsInternalFace=aFS.IsInternalFace();
915     if (!bIsInternalFace) {
916       continue;
917     }
918     //
919     if (aMSLF.Contains(aSolid)) {
920       BOPCol_ListOfShape& aLF=aMSLF.ChangeFromKey(aSolid);
921       aLF.Append(aF);
922     }
923     else {
924       BOPCol_ListOfShape aLF;
925       //
926       aLF.Append(aF);
927       aMSLF.Add(aSolid, aLF);
928     }
929   }// for (k=0; k < aNbVE; ++k) {
930   //
931   // 6. Update Solids by internal Faces
932   aNbSLF=aMSLF.Extent();
933   for (k=1; k <= aNbSLF; ++k) {
934     const TopoDS_Shape& aSolid=aMSLF.FindKey(k);
935     TopoDS_Shape *pSolid=(TopoDS_Shape*)&aSolid;
936     //
937     const BOPCol_ListOfShape& aLF=aMSLF(k);
938     //
939     aMFs.Clear();
940     aItLS.Initialize(aLF);
941     for (; aItLS.More(); aItLS.Next()) {
942       const TopoDS_Shape& aF=aItLS.Value();
943       aMFs.Add(aF);
944       aMFProcessed.Add(aF);
945     }
946     //
947     aLSI.Clear();
948     MakeInternalShells(aMFs, aLSI);
949     //
950     aItLS.Initialize(aLSI);
951     for (; aItLS.More(); aItLS.Next()) {
952       const TopoDS_Shape& aSI=aItLS.Value();
953       aBB.Add (*pSolid, aSI);
954     }
955   }
956   // 
957   // 7. "Rest" faces treatment (if there are)
958   aMFs.Clear();
959   for (k=0; k < aNbVFS; ++k) {
960     const BOPAlgo_FaceSolid& aFS=aVFS(k);
961     //
962     const TopoDS_Face& aF=aFS.Face();
963     if (!aMFProcessed.Contains(aF)) {
964       aMFs.Add(aF);
965     }
966   }
967   //
968   aNbFI=aMFs.Extent();
969   if (aNbFI) {
970     TopoDS_Solid aSolid;
971     aBB.MakeSolid(aSolid);
972     //
973     aLSI.Clear();
974     MakeInternalShells(aMFs, aLSI);
975     //
976     aItLS.Initialize(aLSI);
977     for (; aItLS.More(); aItLS.Next()) {
978       const TopoDS_Shape& aSI=aItLS.Value();
979       aBB.Add (aSolid, aSI);
980     }
981     myAreas.Append(aSolid);
982   }
983 }
984 //=======================================================================
985 //function : MakeInternalShells
986 //purpose  : 
987 //=======================================================================
988 void MakeInternalShells(const BOPCol_MapOfShape& theMF,
989                         BOPCol_ListOfShape& theShells)
990 {
991   BOPCol_ListIteratorOfListOfShape aItF;
992   BRep_Builder aBB;
993   //
994   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
995   BOPCol_MapIteratorOfMapOfShape aItM;
996   BOPCol_MapOfShape aAddedFacesMap;
997   //
998   aItM.Initialize(theMF);
999   for (; aItM.More(); aItM.Next()) {
1000     const TopoDS_Shape& aF=aItM.Key();
1001     BOPTools::MapShapesAndAncestors(aF, 
1002         TopAbs_EDGE, TopAbs_FACE, 
1003         aMEF);
1004   }
1005   //
1006   aItM.Initialize(theMF);
1007   for (; aItM.More(); aItM.Next()) {
1008     TopoDS_Shape aFF=aItM.Key();
1009     if (!aAddedFacesMap.Add(aFF)) {
1010       continue;
1011     }
1012     //
1013     // make a new shell
1014     TopoDS_Shell aShell;
1015     aBB.MakeShell(aShell);    
1016     aFF.Orientation(TopAbs_INTERNAL);
1017     aBB.Add(aShell, aFF);
1018     //
1019     TopoDS_Iterator aItAddedF (aShell);
1020     for (; aItAddedF.More(); aItAddedF.Next()) {
1021       const TopoDS_Shape& aF =aItAddedF.Value();
1022       //
1023       TopExp_Explorer aEdgeExp(aF, TopAbs_EDGE);
1024       for (; aEdgeExp.More(); aEdgeExp.Next()) {
1025         const TopoDS_Shape& aE =aEdgeExp.Current();
1026         const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
1027         aItF.Initialize(aLF);
1028         for (; aItF.More(); aItF.Next()) { 
1029           TopoDS_Shape aFL=aItF.Value();
1030           if (aAddedFacesMap.Add(aFL)){
1031             aFL.Orientation(TopAbs_INTERNAL);
1032             aBB.Add(aShell, aFL);
1033           }
1034         }
1035       }
1036     }
1037     aShell.Closed (BRep_Tool::IsClosed (aShell));
1038     theShells.Append(aShell);
1039   }
1040 }
1041 //=======================================================================
1042 //function : IsHole
1043 //purpose  : 
1044 //=======================================================================
1045 Standard_Boolean IsHole(const TopoDS_Shape& theS2,
1046                         Handle(IntTools_Context)& theContext)
1047 {
1048   TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
1049   BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
1050   //
1051   aClsf.PerformInfinitePoint(::RealSmall());
1052   //
1053   return (aClsf.State()==TopAbs_IN);
1054 }
1055 //=======================================================================
1056 //function : IsInside
1057 //purpose  : 
1058 //=======================================================================
1059 Standard_Boolean IsInside(const TopoDS_Shape& theS1,
1060                           const TopoDS_Shape& theS2,
1061                           Handle(IntTools_Context)& theContext)
1062 {
1063   TopExp_Explorer aExp;
1064   TopAbs_State aState;
1065   //
1066   TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
1067   //
1068   aExp.Init(theS1, TopAbs_FACE);
1069   if (!aExp.More()){
1070     BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
1071     aClsf.PerformInfinitePoint(::RealSmall());
1072     aState=aClsf.State();
1073   }
1074   else {
1075     BOPCol_IndexedMapOfShape aBounds;
1076     BOPTools::MapShapes(*pS2, TopAbs_EDGE, aBounds);
1077     const TopoDS_Face& aF = (*(TopoDS_Face*)(&aExp.Current()));
1078     aState=BOPTools_AlgoTools::ComputeState(aF, *pS2,
1079                                             Precision::Confusion(),
1080                                             aBounds, theContext);
1081   }
1082   return (aState==TopAbs_IN);
1083 }
1084 //=======================================================================
1085 //function : IsGrowthShell
1086 //purpose  : 
1087 //=======================================================================
1088 Standard_Boolean IsGrowthShell(const TopoDS_Shape& theShell,
1089                                const BOPCol_IndexedMapOfShape& theMHF)
1090 {
1091   Standard_Boolean bRet;
1092   TopoDS_Iterator aIt;
1093   // 
1094   bRet=Standard_False;
1095   if (theMHF.Extent()) {
1096     aIt.Initialize(theShell);
1097     for(; aIt.More(); aIt.Next()) {
1098       const TopoDS_Shape& aF=aIt.Value();
1099       if (theMHF.Contains(aF)) {
1100         return !bRet;
1101       }
1102     }
1103   }
1104   return bRet;
1105 }