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