0028187: Add possibility to avoid creation of Internal parts in the result of Volume...
[occt.git] / src / BOPAlgo / BOPAlgo_BuilderFace.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2012 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 //
7 //
8 // This file is part of Open CASCADE Technology software library.
9 //
10 // This library is free software; you can redistribute it and/or modify it under
11 // the terms of the GNU Lesser General Public License version 2.1 as published
12 // by the Free Software Foundation, with special exception defined in the file
13 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
14 // distribution for complete text of the license and disclaimer of any warranty.
15 //
16 // Alternatively, this file may be used under the terms of Open CASCADE
17 // commercial license or contractual agreement.
18
19 #include <Bnd_Box.hxx>
20 #include <BOPAlgo_BuilderFace.hxx>
21 #include <BOPAlgo_WireEdgeSet.hxx>
22 #include <BOPAlgo_WireSplitter.hxx>
23 #include <BOPCol_Box2DBndTree.hxx>
24 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
25 #include <BOPCol_DataMapOfShapeShape.hxx>
26 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
27 #include <BOPCol_ListOfShape.hxx>
28 #include <BOPCol_MapOfShape.hxx>
29 #include <BOPCol_MapOfOrientedShape.hxx>
30 #include <BOPTools.hxx>
31 #include <BOPTools_AlgoTools.hxx>
32 #include <BOPTools_AlgoTools2D.hxx>
33 #include <BRep_Builder.hxx>
34 #include <BRep_Tool.hxx>
35 #include <BRepBndLib.hxx>
36 #include <BRepTools.hxx>
37 #include <Geom_Surface.hxx>
38 #include <gp_Dir.hxx>
39 #include <gp_Pln.hxx>
40 #include <gp_Pnt.hxx>
41 #include <gp_Pnt2d.hxx>
42 #include <gp_Vec.hxx>
43 #include <IntTools_Context.hxx>
44 #include <IntTools_FClass2d.hxx>
45 #include <NCollection_DataMap.hxx>
46 #include <NCollection_UBTreeFiller.hxx>
47 #include <TColStd_MapIntegerHasher.hxx>
48 #include <TopAbs.hxx>
49 #include <TopExp.hxx>
50 #include <TopExp_Explorer.hxx>
51 #include <TopLoc_Location.hxx>
52 #include <TopoDS_Edge.hxx>
53 #include <TopoDS_Face.hxx>
54 #include <TopoDS_Iterator.hxx>
55 #include <TopoDS_Shape.hxx>
56 #include <TopoDS_Vertex.hxx>
57 #include <TopoDS_Wire.hxx>
58
59 //
60 static
61   Standard_Boolean IsGrowthWire(const TopoDS_Shape& ,
62                                 const BOPCol_IndexedMapOfShape& );
63
64 static 
65   Standard_Boolean IsInside(const TopoDS_Shape& ,
66                             const TopoDS_Shape& ,
67                             Handle(IntTools_Context)& );
68 static
69   void MakeInternalWires(const BOPCol_IndexedMapOfShape& ,
70                          BOPCol_ListOfShape& );
71 static 
72   void GetWire(const TopoDS_Shape& , 
73         TopoDS_Shape& ); 
74 //
75
76 //
77 //=======================================================================
78 //class     : BOPAlgo_ShapeBox2D
79 //purpose   : Auxiliary class
80 //=======================================================================
81 class BOPAlgo_ShapeBox2D {
82  public:
83   BOPAlgo_ShapeBox2D() {
84     myIsHole=Standard_False;
85   };
86   //
87   ~BOPAlgo_ShapeBox2D() {
88   };
89   //
90   void SetShape(const TopoDS_Shape& aS) {
91     myShape=aS;
92   };
93   //
94   const TopoDS_Shape& Shape()const {
95     return myShape;
96   };
97   //
98   void SetBox2D(const Bnd_Box2d& aBox2D) {
99     myBox2D=aBox2D;
100   };
101   //
102   const Bnd_Box2d& Box2D()const {
103     return myBox2D;
104   };
105   //
106   void SetIsHole(const Standard_Boolean bFlag) {
107     myIsHole=bFlag;
108   };
109   //
110   Standard_Boolean IsHole()const {
111     return myIsHole;
112   };
113   //
114  protected:
115   Standard_Boolean myIsHole;
116   TopoDS_Shape myShape;
117   Bnd_Box2d myBox2D;
118 };
119 //
120 typedef NCollection_IndexedDataMap 
121   <Standard_Integer, 
122   BOPAlgo_ShapeBox2D, 
123   TColStd_MapIntegerHasher>  BOPAlgo_IndexedDataMapOfIntegerShapeBox2D; 
124
125 typedef NCollection_IndexedDataMap 
126   <TopoDS_Shape, 
127   TopoDS_Shape, 
128   TopTools_ShapeMapHasher> BOPCol_IndexedDataMapOfShapeShape; 
129 //
130 //=======================================================================
131 //function : 
132 //purpose  : 
133 //=======================================================================
134 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace()
135 :
136   BOPAlgo_BuilderArea()
137 {
138   myOrientation=TopAbs_EXTERNAL;
139 }
140 //=======================================================================
141 //function : 
142 //purpose  : 
143 //=======================================================================
144 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace
145   (const Handle(NCollection_BaseAllocator)& theAllocator)
146 :
147   BOPAlgo_BuilderArea(theAllocator)
148
149   myOrientation=TopAbs_EXTERNAL;
150 }
151 //=======================================================================
152 //function : ~
153 //purpose  : 
154 //=======================================================================
155   BOPAlgo_BuilderFace::~BOPAlgo_BuilderFace()
156 {
157 }
158 //=======================================================================
159 //function : SetFace
160 //purpose  : 
161 //=======================================================================
162 void BOPAlgo_BuilderFace::SetFace(const TopoDS_Face& theFace)
163 {
164   myOrientation=theFace.Orientation();
165   myFace=theFace;
166   myFace.Orientation(TopAbs_FORWARD);
167 }
168 //=======================================================================
169 //function : Orientation
170 //purpose  : 
171 //=======================================================================
172 TopAbs_Orientation BOPAlgo_BuilderFace::Orientation()const
173 {
174   return myOrientation;
175 }
176 //=======================================================================
177 //function : Face
178 //purpose  : 
179 //=======================================================================
180 const TopoDS_Face& BOPAlgo_BuilderFace::Face()const
181 {
182   return myFace;
183 }
184 //=======================================================================
185 //function : CheckData
186 //purpose  : 
187 //=======================================================================
188 void BOPAlgo_BuilderFace::CheckData()
189 {
190   myErrorStatus=0;
191   //
192   if (myFace.IsNull()) {
193     myErrorStatus=12;// Null face generix
194     return;
195   }
196   if (myContext.IsNull()) {
197     myContext = new IntTools_Context;
198   }
199 }
200 //=======================================================================
201 //function : Perform
202 //purpose  : 
203 //=======================================================================
204 void BOPAlgo_BuilderFace::Perform()
205 {
206   myErrorStatus=0;
207   //
208   CheckData();
209   if (myErrorStatus) {
210     return;
211   }
212   //
213   UserBreak();
214   //
215   PerformShapesToAvoid();
216   if (myErrorStatus) {
217     return;
218   }
219   //
220   UserBreak();
221   //
222   PerformLoops();
223   if (myErrorStatus) {
224     return;
225   }
226   //
227   UserBreak();
228   //
229   PerformAreas();
230   if (myErrorStatus) {
231     return;
232   }
233   //
234   UserBreak();
235   //
236   PerformInternalShapes();
237   if (myErrorStatus) {
238     return;
239   }
240 }
241 //=======================================================================
242 //function :PerformShapesToAvoid
243 //purpose  : 
244 //=======================================================================
245 void BOPAlgo_BuilderFace::PerformShapesToAvoid()
246 {
247   Standard_Boolean bFound;
248   Standard_Integer i, iCnt, aNbV, aNbE;
249   BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
250   BOPCol_ListIteratorOfListOfShape aIt;
251   //
252   myShapesToAvoid.Clear();
253   //
254   iCnt=0;
255   for(;;) {
256     ++iCnt;
257     bFound=Standard_False;
258     //
259     // 1. MEF
260     aMVE.Clear();
261     aIt.Initialize (myShapes);
262     for (; aIt.More(); aIt.Next()) {
263       const TopoDS_Shape& aE=aIt.Value();
264       if (!myShapesToAvoid.Contains(aE)) {
265         BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
266       }
267     }
268     aNbV=aMVE.Extent();
269     //
270     // 2. myEdgesToAvoid
271     for (i=1; i<=aNbV; ++i) {
272       const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aMVE.FindKey(i)));
273       //
274       BOPCol_ListOfShape& aLE=aMVE.ChangeFromKey(aV);
275       aNbE=aLE.Extent();
276       if (!aNbE) {
277         continue;
278       }
279       //
280       const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aLE.First()));
281       if (aNbE==1) {
282         if (BRep_Tool::Degenerated(aE1)) {
283           continue;
284         }
285         if (aV.Orientation()==TopAbs_INTERNAL) {
286           continue;
287         }
288         bFound=Standard_True;
289         myShapesToAvoid.Add(aE1);
290       }
291       else if (aNbE==2) {
292         const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aLE.Last()));
293         if (aE2.IsSame(aE1)) {
294           TopoDS_Vertex aV1x, aV2x;
295           //
296           TopExp::Vertices(aE1, aV1x, aV2x);
297           if (aV1x.IsSame(aV2x)) {
298             continue;
299           }
300           bFound=Standard_True;
301           myShapesToAvoid.Add(aE1);
302           myShapesToAvoid.Add(aE2);
303         }
304       }
305     }// for (i=1; i<=aNbE; ++i) {
306     //
307     if (!bFound) {
308       break;
309     }
310     //
311   }//while (1) 
312   //printf(" EdgesToAvoid=%d, iCnt=%d\n", EdgesToAvoid.Extent(), iCnt);
313 }  
314 //=======================================================================
315 //function : PerformLoops
316 //purpose  : 
317 //=======================================================================
318 void BOPAlgo_BuilderFace::PerformLoops()
319 {
320   myErrorStatus=0;
321   //
322   Standard_Boolean bFlag;
323   Standard_Integer i, iErr, aNbEA;
324   BOPCol_ListIteratorOfListOfShape aIt;
325   BOPCol_IndexedDataMapOfShapeListOfShape aVEMap;
326   BOPCol_MapOfOrientedShape aMAdded;
327   TopoDS_Iterator aItW;
328   BRep_Builder aBB; 
329   BOPAlgo_WireEdgeSet aWES(myAllocator);
330   BOPAlgo_WireSplitter aWSp(myAllocator);
331   //
332   // 1. 
333   myLoops.Clear();
334   aWES.SetFace(myFace);
335   //
336   aIt.Initialize(myShapes);
337   for (; aIt.More(); aIt.Next()) {
338     const TopoDS_Shape& aE=aIt.Value();
339     if (!myShapesToAvoid.Contains(aE)) {
340       aWES.AddStartElement(aE);
341     }
342   }
343   //
344   aWSp.SetWES(aWES);
345   aWSp.SetRunParallel(myRunParallel);
346   aWSp.SetContext(myContext);
347   aWSp.Perform();
348   iErr=aWSp.ErrorStatus();
349   if (iErr) {
350     return;
351   }
352   //
353   const BOPCol_ListOfShape& aLW=aWES.Shapes();
354   aIt.Initialize (aLW);
355   for (; aIt.More(); aIt.Next()) {
356     const TopoDS_Shape& aW=aIt.Value();
357     myLoops.Append(aW);
358   }
359   // Post Treatment
360   BOPCol_MapOfOrientedShape aMEP;
361   // 
362   // a. collect all edges that are in loops
363   aIt.Initialize (myLoops);
364   for (; aIt.More(); aIt.Next()) {
365     const TopoDS_Shape& aW=aIt.Value();
366     aItW.Initialize(aW);
367     for (; aItW.More(); aItW.Next()) {
368       const TopoDS_Shape& aE=aItW.Value();
369       aMEP.Add(aE);
370     }
371   }
372   // 
373   // b. collect all edges that are to avoid
374   aNbEA = myShapesToAvoid.Extent();
375   for (i = 1; i <= aNbEA; ++i) {
376     const TopoDS_Shape& aE = myShapesToAvoid(i);
377     aMEP.Add(aE);
378   }
379   //
380   // c. add all edges that are not processed to myShapesToAvoid
381   aIt.Initialize (myShapes);
382   for (; aIt.More(); aIt.Next()) {
383     const TopoDS_Shape& aE=aIt.Value();
384     if (!aMEP.Contains(aE)) {
385       myShapesToAvoid.Add(aE);
386     }
387   }
388   //
389   // 2. Internal Wires
390   myLoopsInternal.Clear();
391   //
392   aNbEA = myShapesToAvoid.Extent();
393   for (i = 1; i <= aNbEA; ++i) {
394     const TopoDS_Shape& aEE = myShapesToAvoid(i);
395     BOPTools::MapShapesAndAncestors(aEE, 
396                                     TopAbs_VERTEX, 
397                                     TopAbs_EDGE, 
398                                     aVEMap);
399   }
400   //
401   bFlag=Standard_True;
402   for (i = 1; (i <= aNbEA) && bFlag; ++i) {
403     const TopoDS_Shape& aEE = myShapesToAvoid(i);
404     if (!aMAdded.Add(aEE)) {
405       continue;
406     }
407     //
408     // make new wire
409     TopoDS_Wire aW;
410     aBB.MakeWire(aW);
411     aBB.Add(aW, aEE);
412     //
413     aItW.Initialize(aW);
414     for (; aItW.More()&&bFlag; aItW.Next()) {
415       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
416       //
417       TopoDS_Iterator aItE(aE);
418       for (; aItE.More()&&bFlag; aItE.Next()) {
419         const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aItE.Value()));
420         const BOPCol_ListOfShape& aLE=aVEMap.FindFromKey(aV);
421         aIt.Initialize(aLE);
422         for (; aIt.More()&&bFlag; aIt.Next()) { 
423           const TopoDS_Shape& aEx=aIt.Value();
424           if (aMAdded.Add(aEx)) {
425             aBB.Add(aW, aEx);
426             if(aMAdded.Extent()==aNbEA) {
427               bFlag=!bFlag;
428             }
429           }
430         }//for (; aIt.More(); aIt.Next()) { 
431       }//for (; aItE.More(); aItE.Next()) {
432     }//for (; aItW.More(); aItW.Next()) {
433     aW.Closed(BRep_Tool::IsClosed(aW));
434     myLoopsInternal.Append(aW);
435   }//for (i = 1; (i <= aNbEA) && bFlag; ++i) {
436 }
437 //=======================================================================
438 //function : PerformAreas
439 //purpose  : 
440 //=======================================================================
441 void BOPAlgo_BuilderFace::PerformAreas()
442 {
443   Standard_Boolean bIsGrowth, bIsHole;
444   Standard_Integer k, aNbS, aNbHoles, aNbDMISB, m, aNbMSH, aNbInOutMap;
445   Standard_Real aTol;
446   TopLoc_Location aLoc;
447   Handle(Geom_Surface) aS;
448   BRep_Builder aBB;
449   TopoDS_Face aFace;
450   BOPCol_ListIteratorOfListOfInteger aItLI;
451   BOPCol_IndexedMapOfShape aMHE;
452   BOPCol_ListIteratorOfListOfShape aIt1;
453   BOPCol_IndexedDataMapOfShapeListOfShape aMSH;
454   BOPCol_IndexedDataMapOfShapeShape aInOutMap;
455   BOPAlgo_IndexedDataMapOfIntegerShapeBox2D aDMISB(100);
456   //
457   BOPCol_Box2DBndTreeSelector aSelector;
458   BOPCol_Box2DBndTree aBBTree;
459   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box2d> aTreeFiller(aBBTree);
460   //
461   myErrorStatus=0;
462   aNbHoles=0;
463   //
464   aTol=BRep_Tool::Tolerance(myFace);
465   aS=BRep_Tool::Surface(myFace, aLoc);
466   //
467   myAreas.Clear();
468   //
469   if (myLoops.IsEmpty()) {
470     if (myContext->IsInfiniteFace(myFace)) {
471       aBB.MakeFace(aFace, aS, aLoc, aTol);
472       if (BRep_Tool::NaturalRestriction(myFace)) {
473         aBB.NaturalRestriction(aFace, Standard_True);
474       }
475       myAreas.Append(aFace); 
476     }
477     return;
478   }
479   //
480   // 1. Growthes and Holes -> aDMISB: [Index/ShapeBox2D]
481   aIt1.Initialize(myLoops);
482   for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
483     Bnd_Box2d aBox2D;
484     //
485     const TopoDS_Shape& aWire=aIt1.Value();
486     //
487     aBB.MakeFace(aFace, aS, aLoc, aTol);
488     aBB.Add (aFace, aWire);
489     BRepTools::AddUVBounds(aFace, aBox2D);
490     //
491     bIsGrowth=IsGrowthWire(aWire, aMHE);
492     if (bIsGrowth) {
493       bIsHole=Standard_False;
494     }
495     else{
496       // check if a wire is a hole 
497       IntTools_FClass2d& aClsf=myContext->FClass2d(aFace);
498       aClsf.Init(aFace, aTol);
499       //
500       bIsHole=aClsf.IsHole();
501       if (bIsHole) {
502         BOPTools::MapShapes(aWire, TopAbs_EDGE, aMHE);
503         //
504         bIsHole=Standard_True;
505       }
506       else {
507         bIsHole=Standard_False;
508       }
509     }
510     //
511     BOPAlgo_ShapeBox2D aSB2D;
512     //
513     aSB2D.SetShape(aFace);
514     aSB2D.SetBox2D(aBox2D);
515     aSB2D.SetIsHole(bIsHole);
516     //
517     aDMISB.Add(k, aSB2D);
518   }// for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
519   //
520   // 2. Prepare TreeFiller
521   aNbDMISB=aDMISB.Extent();
522   for (m=1; m<=aNbDMISB; ++m) { 
523     k=aDMISB.FindKey(m);
524     const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
525     //
526     bIsHole=aSB2D.IsHole();
527     if (bIsHole) {
528       const Bnd_Box2d& aBox2D=aSB2D.Box2D();
529       aTreeFiller.Add(k, aBox2D);
530       ++aNbHoles;
531     }
532   }
533   //
534   // 3. Shake TreeFiller
535   aTreeFiller.Fill();
536   //
537   // 4. Find outer growth shell that is most close 
538   //    to each hole shell
539   for (m=1; m<=aNbDMISB; ++m) {
540     const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
541     bIsHole=aSB2D.IsHole();
542     if (bIsHole) {
543       continue;
544     }
545     //
546     const Bnd_Box2d& aBox2DF=aSB2D.Box2D();
547     const TopoDS_Shape aF=aSB2D.Shape();
548     //
549     aSelector.Clear();
550     aSelector.SetBox(aBox2DF);
551     //
552     aNbS = aBBTree.Select(aSelector);
553     if (!aNbS) {
554       continue;
555     }
556     //
557     const BOPCol_ListOfInteger& aLI=aSelector.Indices();
558     //
559     aItLI.Initialize(aLI);
560     for (; aItLI.More(); aItLI.Next()) {
561       k=aItLI.Value();
562       const BOPAlgo_ShapeBox2D& aSB2Dk=aDMISB.FindFromKey(k);
563       const TopoDS_Shape& aHole=aSB2Dk.Shape();
564       //
565       if (!IsInside(aHole, aF, myContext)){
566         continue;
567       }
568       //
569       if (aInOutMap.Contains(aHole)){
570         TopoDS_Shape& aF2=aInOutMap.ChangeFromKey(aHole);
571         if (IsInside(aF, aF2, myContext)) {
572           aF2=aF;
573         }
574       }
575       else{
576         aInOutMap.Add(aHole, aF);
577       }
578     }
579   }// for (m=1; m<=aNbDMISB; ++m)
580   //
581   // 5.1 Map [Face/Holes] -> aMSH 
582   aNbInOutMap=aInOutMap.Extent();
583   for (m=1; m<=aNbInOutMap; ++m) {
584     const TopoDS_Shape& aHole=aInOutMap.FindKey(m);
585     const TopoDS_Shape& aF=aInOutMap.FindFromIndex(m);
586     //
587     if (aMSH.Contains(aF)) {
588       BOPCol_ListOfShape& aLH=aMSH.ChangeFromKey(aF);
589       aLH.Append(aHole);
590     }
591     else {
592       BOPCol_ListOfShape aLH;
593       aLH.Append(aHole);
594       aMSH.Add(aF, aLH);
595     }
596   }
597   //
598   // 5.2. Add unused holes to the original face
599   if (aNbHoles != aNbInOutMap) {
600     Bnd_Box aBoxF;
601     BRepBndLib::Add(myFace, aBoxF);
602     if (aBoxF.IsOpenXmin() || aBoxF.IsOpenXmax() ||
603         aBoxF.IsOpenYmin() || aBoxF.IsOpenYmax() ||
604         aBoxF.IsOpenZmin() || aBoxF.IsOpenZmax()) {
605       //
606       BOPCol_ListOfShape anUnUsedHoles;
607       for (m = 1; m <= aNbDMISB; ++m) {
608         const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
609         if (aSB2D.IsHole()) {
610           const TopoDS_Shape& aHole = aSB2D.Shape();
611           if (!aInOutMap.Contains(aHole)) {
612             anUnUsedHoles.Append(aHole);
613           }
614         }
615       }
616       //
617       if (anUnUsedHoles.Extent()) {
618         aBB.MakeFace(aFace, aS, aLoc, aTol);
619         aMSH.Add(aFace, anUnUsedHoles);
620         //
621         BOPAlgo_ShapeBox2D aSB2D;
622         //
623         aSB2D.SetShape(aFace);
624         aSB2D.SetIsHole(Standard_False);
625         //
626         aDMISB.Add(aNbDMISB, aSB2D);
627         ++aNbDMISB;
628       }
629     }
630   }
631   //
632   // 6. Add aHoles to Faces
633   aNbMSH=aMSH.Extent();
634   for (m=1; m<=aNbMSH; ++m) {
635     TopoDS_Face aF=(*(TopoDS_Face *)(&aMSH.FindKey(m)));
636     const BOPCol_ListOfShape& aLH=aMSH.FindFromIndex(m);
637     //
638     aIt1.Initialize(aLH);
639     for (; aIt1.More(); aIt1.Next()) {
640       TopoDS_Shape aWHole;
641       //
642       const TopoDS_Shape& aFHole=aIt1.Value();
643       GetWire(aFHole, aWHole);
644       aBB.Add (aF, aWHole);
645     }
646     //
647     // update classifier 
648     aTol=BRep_Tool::Tolerance(aF);
649     IntTools_FClass2d& aClsf=myContext->FClass2d(aF);
650     aClsf.Init(aF, aTol);
651   }
652   //
653   // 7. Fill myAreas
654   //    NB:These aNewFaces are draft faces that 
655   //    do not contain any internal shapes
656   for (m=1; m<=aNbDMISB; ++m) {
657     const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
658     bIsHole=aSB2D.IsHole();
659     if (!bIsHole) {
660       const TopoDS_Shape aF=aSB2D.Shape();
661       myAreas.Append(aF);
662     }
663   }
664 }
665 //=======================================================================
666 //function : GetWire
667 //purpose  : 
668 //=======================================================================
669 void GetWire(const TopoDS_Shape& aF, TopoDS_Shape& aW) 
670 {
671   TopoDS_Shape aWx;
672   TopoDS_Iterator aIt;
673   //
674   aIt.Initialize(aF);
675   for (; aIt.More(); aIt.Next()) {
676     aW=aIt.Value();
677   }
678 }
679 //=======================================================================
680 //function : PerformInternalShapes
681 //purpose  : 
682 //=======================================================================
683 void BOPAlgo_BuilderFace::PerformInternalShapes()
684 {
685   myErrorStatus=0;
686   if (myAvoidInternalShapes) {
687     return;
688   }
689   //
690   Standard_Integer aNbWI=myLoopsInternal.Extent();
691   if (!aNbWI) {// nothing to do
692     return;
693   }
694   // 
695   //Standard_Real aTol;
696   Standard_Integer i;
697   BRep_Builder aBB;
698   BOPCol_ListIteratorOfListOfShape aIt1, aIt2;
699   TopoDS_Iterator aIt; 
700   BOPCol_IndexedMapOfShape aME1, aME2, aMEP;
701   BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
702   BOPCol_ListOfShape aLSI;
703   //
704   // 1. All internal edges
705   aIt1.Initialize(myLoopsInternal);
706   for (; aIt1.More(); aIt1.Next()) {
707     const TopoDS_Shape& aWire=aIt1.Value();
708     aIt.Initialize(aWire);
709     for (; aIt.More(); aIt.Next()) {
710       const TopoDS_Shape& aE=aIt.Value();
711       aME1.Add(aE);
712     }
713   }
714   //
715   // 2 Process faces
716   aIt2.Initialize(myAreas);
717   for ( ; aIt2.More(); aIt2.Next()) {
718     TopoDS_Face& aF=(*(TopoDS_Face *)(&aIt2.Value()));
719     //
720     aMVE.Clear();
721     BOPTools::MapShapesAndAncestors(aF, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
722     //
723     // 2.1 Separate faces to process aMEP
724     aME2.Clear();
725     aMEP.Clear();
726     aNbWI = aME1.Extent();
727     for (i = 1; i <= aNbWI; ++i) {
728       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aME1(i)));
729       if (IsInside(aE, aF, myContext)) {
730         aMEP.Add(aE);
731       }
732       else {
733         aME2.Add(aE);
734       }
735     }
736     //
737     // 2.2 Make Internal Wires
738     aLSI.Clear();
739     MakeInternalWires(aMEP, aLSI);
740     //
741     // 2.3 Add them to aF
742     aIt1.Initialize(aLSI);
743     for (; aIt1.More(); aIt1.Next()) {
744       const TopoDS_Shape& aSI=aIt1.Value();
745       aBB.Add (aF, aSI);
746     }
747     //
748     // 2.4 Remove faces aMFP from aMF
749     aME1 = aME2;
750     //
751     aNbWI = aME1.Extent();
752     if (!aNbWI) {
753       break;
754     }
755   } //for ( ; aIt2.More(); aIt2.Next()) {
756 }
757 //=======================================================================
758 //function : MakeInternalWires
759 //purpose  : 
760 //=======================================================================
761 void MakeInternalWires(const BOPCol_IndexedMapOfShape& theME,
762                        BOPCol_ListOfShape& theWires)
763 {
764   Standard_Integer i, aNbE;
765   BOPCol_MapOfShape aAddedMap;
766   BOPCol_ListIteratorOfListOfShape aItE;
767   BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
768   BRep_Builder aBB;
769   //
770   aNbE = theME.Extent();
771   for (i = 1; i <= aNbE; ++i) {
772     const TopoDS_Shape& aE = theME(i);
773     BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
774   }
775   //
776   for (i = 1; i <= aNbE; ++i) {
777     TopoDS_Shape aEE = theME(i);
778     if (!aAddedMap.Add(aEE)) {
779       continue;
780     }
781     //
782     // make a new shell
783     TopoDS_Wire aW;
784     aBB.MakeWire(aW);    
785     aEE.Orientation(TopAbs_INTERNAL);
786     aBB.Add(aW, aEE);
787     //
788     TopoDS_Iterator aItAdded (aW);
789     for (; aItAdded.More(); aItAdded.Next()) {
790       const TopoDS_Shape& aE =aItAdded.Value();
791       //
792       TopExp_Explorer aExp(aE, TopAbs_VERTEX);
793       for (; aExp.More(); aExp.Next()) {
794         const TopoDS_Shape& aV =aExp.Current();
795         const BOPCol_ListOfShape& aLE=aMVE.FindFromKey(aV);
796         aItE.Initialize(aLE);
797         for (; aItE.More(); aItE.Next()) { 
798           TopoDS_Shape aEL=aItE.Value();
799           if (aAddedMap.Add(aEL)){
800             aEL.Orientation(TopAbs_INTERNAL);
801             aBB.Add(aW, aEL);
802           }
803         }
804       }
805     }
806     aW.Closed(BRep_Tool::IsClosed(aW));
807     theWires.Append(aW);
808   }
809 }
810 //=======================================================================
811 //function : IsInside
812 //purpose  : 
813 //=======================================================================
814 Standard_Boolean IsInside(const TopoDS_Shape& theHole,
815                           const TopoDS_Shape& theF2,
816                           Handle(IntTools_Context)& theContext)
817 {
818   Standard_Boolean bRet;
819   Standard_Real aT, aU, aV;
820   
821   TopAbs_State aState;
822   TopExp_Explorer aExp;
823   BOPCol_IndexedMapOfShape aME2;
824   gp_Pnt2d aP2D;
825   //
826   bRet=Standard_False;
827   aState=TopAbs_UNKNOWN;
828   const TopoDS_Face& aF2=(*(TopoDS_Face *)(&theF2));
829   //
830   BOPTools::MapShapes(aF2, TopAbs_EDGE, aME2);//AA
831   //
832   aExp.Init(theHole, TopAbs_EDGE);
833   if (aExp.More()) {
834     const TopoDS_Edge& aE =(*(TopoDS_Edge *)(&aExp.Current()));
835     if (aME2.Contains(aE)) {
836       return bRet;
837     }
838     if (!BRep_Tool::Degenerated(aE)) {
839       //
840       aT=BOPTools_AlgoTools2D::IntermediatePoint(aE);
841       BOPTools_AlgoTools2D::PointOnSurface(aE, aF2, aT, aU, aV, theContext);
842       aP2D.SetCoord(aU, aV);
843       //
844       IntTools_FClass2d& aClsf=theContext->FClass2d(aF2);
845       aState=aClsf.Perform(aP2D);
846       bRet=(aState==TopAbs_IN);
847     }
848   }
849   //
850   return bRet;
851 }
852
853 //=======================================================================
854 //function : IsGrowthWire
855 //purpose  : 
856 //=======================================================================
857 Standard_Boolean IsGrowthWire(const TopoDS_Shape& theWire,
858                               const BOPCol_IndexedMapOfShape& theMHE)
859 {
860   Standard_Boolean bRet;
861   TopoDS_Iterator aIt;
862   // 
863   bRet=Standard_False;
864   if (theMHE.Extent()) {
865     aIt.Initialize(theWire);
866     for(; aIt.More(); aIt.Next()) {
867       const TopoDS_Shape& aE=aIt.Value();
868       if (theMHE.Contains(aE)) {
869         return !bRet;
870       }
871     }
872   }
873   return bRet;
874 }
875
876 //BRepTools::Write(aFF, "ff");
877 //
878 //  ErrorStatus :
879 // 11 - Null Context
880 // 12 - Null face generix