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