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