0031887: IntTools_Context::IsPointInFace always return TRUE
[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 <Bnd_Box2d.hxx>
21 #include <BOPAlgo_BuilderFace.hxx>
22 #include <BOPAlgo_WireEdgeSet.hxx>
23 #include <BOPAlgo_WireSplitter.hxx>
24 #include <BOPAlgo_Alerts.hxx>
25 #include <BOPTools_AlgoTools.hxx>
26 #include <BOPTools_AlgoTools2D.hxx>
27 #include <BOPTools_BoxTree.hxx>
28 #include <Bnd_Tools.hxx>
29 #include <BRep_Builder.hxx>
30 #include <BRep_Tool.hxx>
31 #include <BRepBndLib.hxx>
32 #include <BRepTools.hxx>
33 #include <Geom_Surface.hxx>
34 #include <gp_Dir.hxx>
35 #include <gp_Pln.hxx>
36 #include <gp_Pnt.hxx>
37 #include <gp_Pnt2d.hxx>
38 #include <gp_Vec.hxx>
39 #include <IntTools_Context.hxx>
40 #include <IntTools_FClass2d.hxx>
41 #include <NCollection_DataMap.hxx>
42 #include <TColStd_MapOfInteger.hxx>
43 #include <TopAbs.hxx>
44 #include <TopExp.hxx>
45 #include <TopExp_Explorer.hxx>
46 #include <TopLoc_Location.hxx>
47 #include <TopoDS.hxx>
48 #include <TopoDS_Edge.hxx>
49 #include <TopoDS_Face.hxx>
50 #include <TopoDS_Iterator.hxx>
51 #include <TopoDS_Shape.hxx>
52 #include <TopoDS_Vertex.hxx>
53 #include <TopoDS_Wire.hxx>
54 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
55 #include <TopTools_IndexedDataMapOfShapeShape.hxx>
56 #include <TopTools_ListOfShape.hxx>
57 #include <TopTools_MapOfShape.hxx>
58 #include <TopTools_MapOfOrientedShape.hxx>
59 //
60 static
61   Standard_Boolean IsGrowthWire(const TopoDS_Shape& ,
62                                 const TopTools_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 TopTools_IndexedMapOfShape& ,
70                          TopTools_ListOfShape& );
71
72 //=======================================================================
73 //function : 
74 //purpose  : 
75 //=======================================================================
76 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace()
77 :
78   BOPAlgo_BuilderArea()
79 {
80   myOrientation=TopAbs_EXTERNAL;
81 }
82 //=======================================================================
83 //function : 
84 //purpose  : 
85 //=======================================================================
86 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace
87   (const Handle(NCollection_BaseAllocator)& theAllocator)
88 :
89   BOPAlgo_BuilderArea(theAllocator)
90
91   myOrientation=TopAbs_EXTERNAL;
92 }
93 //=======================================================================
94 //function : ~
95 //purpose  : 
96 //=======================================================================
97   BOPAlgo_BuilderFace::~BOPAlgo_BuilderFace()
98 {
99 }
100 //=======================================================================
101 //function : SetFace
102 //purpose  : 
103 //=======================================================================
104 void BOPAlgo_BuilderFace::SetFace(const TopoDS_Face& theFace)
105 {
106   myOrientation=theFace.Orientation();
107   myFace=theFace;
108   myFace.Orientation(TopAbs_FORWARD);
109 }
110 //=======================================================================
111 //function : Orientation
112 //purpose  : 
113 //=======================================================================
114 TopAbs_Orientation BOPAlgo_BuilderFace::Orientation()const
115 {
116   return myOrientation;
117 }
118 //=======================================================================
119 //function : Face
120 //purpose  : 
121 //=======================================================================
122 const TopoDS_Face& BOPAlgo_BuilderFace::Face()const
123 {
124   return myFace;
125 }
126 //=======================================================================
127 //function : CheckData
128 //purpose  : 
129 //=======================================================================
130 void BOPAlgo_BuilderFace::CheckData()
131 {
132   if (myFace.IsNull()) {
133     AddError (new BOPAlgo_AlertNullInputShapes);
134     return;
135   }
136   if (myContext.IsNull()) {
137     myContext = new IntTools_Context;
138   }
139 }
140 //=======================================================================
141 //function : Perform
142 //purpose  : 
143 //=======================================================================
144 void BOPAlgo_BuilderFace::Perform()
145 {
146   GetReport()->Clear();
147   //
148   CheckData();
149   if (HasErrors()) {
150     return;
151   }
152   //
153   UserBreak();
154   //
155   PerformShapesToAvoid();
156   if (HasErrors()) {
157     return;
158   }
159   //
160   UserBreak();
161   //
162   PerformLoops();
163   if (HasErrors()) {
164     return;
165   }
166   //
167   UserBreak();
168   //
169   PerformAreas();
170   if (HasErrors()) {
171     return;
172   }
173   //
174   UserBreak();
175   //
176   PerformInternalShapes();
177   if (HasErrors()) {
178     return;
179   }
180 }
181 //=======================================================================
182 //function :PerformShapesToAvoid
183 //purpose  : 
184 //=======================================================================
185 void BOPAlgo_BuilderFace::PerformShapesToAvoid()
186 {
187   Standard_Boolean bFound;
188   Standard_Integer i, iCnt, aNbV, aNbE;
189   TopTools_IndexedDataMapOfShapeListOfShape aMVE;
190   TopTools_ListIteratorOfListOfShape aIt;
191   //
192   myShapesToAvoid.Clear();
193   //
194   iCnt=0;
195   for(;;) {
196     ++iCnt;
197     bFound=Standard_False;
198     //
199     // 1. MEF
200     aMVE.Clear();
201     aIt.Initialize (myShapes);
202     for (; aIt.More(); aIt.Next()) {
203       const TopoDS_Shape& aE=aIt.Value();
204       if (!myShapesToAvoid.Contains(aE)) {
205         TopExp::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
206       }
207     }
208     aNbV=aMVE.Extent();
209     //
210     // 2. myEdgesToAvoid
211     for (i=1; i<=aNbV; ++i) {
212       const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aMVE.FindKey(i)));
213       //
214       TopTools_ListOfShape& aLE=aMVE.ChangeFromKey(aV);
215       aNbE=aLE.Extent();
216       if (!aNbE) {
217         continue;
218       }
219       //
220       const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aLE.First()));
221       if (aNbE==1) {
222         if (BRep_Tool::Degenerated(aE1)) {
223           continue;
224         }
225         if (aV.Orientation()==TopAbs_INTERNAL) {
226           continue;
227         }
228         bFound=Standard_True;
229         myShapesToAvoid.Add(aE1);
230       }
231       else if (aNbE==2) {
232         const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aLE.Last()));
233         if (aE2.IsSame(aE1)) {
234           TopoDS_Vertex aV1x, aV2x;
235           //
236           TopExp::Vertices(aE1, aV1x, aV2x);
237           if (aV1x.IsSame(aV2x)) {
238             continue;
239           }
240           bFound=Standard_True;
241           myShapesToAvoid.Add(aE1);
242           myShapesToAvoid.Add(aE2);
243         }
244       }
245     }// for (i=1; i<=aNbE; ++i) {
246     //
247     if (!bFound) {
248       break;
249     }
250     //
251   }//while (1) 
252   //printf(" EdgesToAvoid=%d, iCnt=%d\n", EdgesToAvoid.Extent(), iCnt);
253 }  
254 //=======================================================================
255 //function : PerformLoops
256 //purpose  : 
257 //=======================================================================
258 void BOPAlgo_BuilderFace::PerformLoops()
259 {
260   Standard_Boolean bFlag;
261   Standard_Integer i, aNbEA;
262   TopTools_ListIteratorOfListOfShape aIt;
263   TopTools_IndexedDataMapOfShapeListOfShape aVEMap;
264   TopTools_MapOfOrientedShape aMAdded;
265   TopoDS_Iterator aItW;
266   BRep_Builder aBB; 
267   BOPAlgo_WireEdgeSet aWES(myAllocator);
268   BOPAlgo_WireSplitter aWSp(myAllocator);
269   //
270   // 1. 
271   myLoops.Clear();
272   aWES.SetFace(myFace);
273   //
274   aIt.Initialize(myShapes);
275   for (; aIt.More(); aIt.Next()) {
276     const TopoDS_Shape& aE=aIt.Value();
277     if (!myShapesToAvoid.Contains(aE)) {
278       aWES.AddStartElement(aE);
279     }
280   }
281   //
282   aWSp.SetWES(aWES);
283   aWSp.SetRunParallel(myRunParallel);
284   aWSp.SetContext(myContext);
285   aWSp.Perform();
286   if (aWSp.HasErrors()) {
287     return;
288   }
289   //
290   const TopTools_ListOfShape& aLW=aWES.Shapes();
291   aIt.Initialize (aLW);
292   for (; aIt.More(); aIt.Next()) {
293     const TopoDS_Shape& aW=aIt.Value();
294     myLoops.Append(aW);
295   }
296   // Post Treatment
297   TopTools_MapOfOrientedShape aMEP;
298   // 
299   // a. collect all edges that are in loops
300   aIt.Initialize (myLoops);
301   for (; aIt.More(); aIt.Next()) {
302     const TopoDS_Shape& aW=aIt.Value();
303     aItW.Initialize(aW);
304     for (; aItW.More(); aItW.Next()) {
305       const TopoDS_Shape& aE=aItW.Value();
306       aMEP.Add(aE);
307     }
308   }
309   // 
310   // b. collect all edges that are to avoid
311   aNbEA = myShapesToAvoid.Extent();
312   for (i = 1; i <= aNbEA; ++i) {
313     const TopoDS_Shape& aE = myShapesToAvoid(i);
314     aMEP.Add(aE);
315   }
316   //
317   // c. add all edges that are not processed to myShapesToAvoid
318   aIt.Initialize (myShapes);
319   for (; aIt.More(); aIt.Next()) {
320     const TopoDS_Shape& aE=aIt.Value();
321     if (!aMEP.Contains(aE)) {
322       myShapesToAvoid.Add(aE);
323     }
324   }
325   //
326   // 2. Internal Wires
327   myLoopsInternal.Clear();
328   //
329   aNbEA = myShapesToAvoid.Extent();
330   for (i = 1; i <= aNbEA; ++i) {
331     const TopoDS_Shape& aEE = myShapesToAvoid(i);
332     TopExp::MapShapesAndAncestors(aEE, 
333                                     TopAbs_VERTEX, 
334                                     TopAbs_EDGE, 
335                                     aVEMap);
336   }
337   //
338   bFlag=Standard_True;
339   for (i = 1; (i <= aNbEA) && bFlag; ++i) {
340     const TopoDS_Shape& aEE = myShapesToAvoid(i);
341     if (!aMAdded.Add(aEE)) {
342       continue;
343     }
344     //
345     // make new wire
346     TopoDS_Wire aW;
347     aBB.MakeWire(aW);
348     aBB.Add(aW, aEE);
349     //
350     aItW.Initialize(aW);
351     for (; aItW.More()&&bFlag; aItW.Next()) {
352       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
353       //
354       TopoDS_Iterator aItE(aE);
355       for (; aItE.More()&&bFlag; aItE.Next()) {
356         const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aItE.Value()));
357         const TopTools_ListOfShape& aLE=aVEMap.FindFromKey(aV);
358         aIt.Initialize(aLE);
359         for (; aIt.More()&&bFlag; aIt.Next()) { 
360           const TopoDS_Shape& aEx=aIt.Value();
361           if (aMAdded.Add(aEx)) {
362             aBB.Add(aW, aEx);
363             if(aMAdded.Extent()==aNbEA) {
364               bFlag=!bFlag;
365             }
366           }
367         }//for (; aIt.More(); aIt.Next()) { 
368       }//for (; aItE.More(); aItE.Next()) {
369     }//for (; aItW.More(); aItW.Next()) {
370     aW.Closed(BRep_Tool::IsClosed(aW));
371     myLoopsInternal.Append(aW);
372   }//for (i = 1; (i <= aNbEA) && bFlag; ++i) {
373 }
374 //=======================================================================
375 //function : PerformAreas
376 //purpose  : 
377 //=======================================================================
378 void BOPAlgo_BuilderFace::PerformAreas()
379 {
380   myAreas.Clear();
381   BRep_Builder aBB;
382   // Location of the myFace
383   TopLoc_Location aLoc;
384   // Get surface from myFace
385   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(myFace, aLoc);
386   // Get tolerance of myFace
387   Standard_Real aTol = BRep_Tool::Tolerance(myFace);
388
389   // Check if there are no loops at all
390   if (myLoops.IsEmpty())
391   {
392     if (myContext->IsInfiniteFace(myFace))
393     {
394       TopoDS_Face aFace;
395       aBB.MakeFace(aFace, aS, aLoc, aTol);
396       if (BRep_Tool::NaturalRestriction(myFace))
397         aBB.NaturalRestriction(aFace, Standard_True);
398       myAreas.Append(aFace);
399     }
400     return;
401   }
402
403   // The new faces
404   TopTools_ListOfShape aNewFaces;
405   // The hole faces which has to be classified relatively new faces
406   TopTools_IndexedMapOfShape aHoleFaces;
407   // Map of the edges of the hole faces for quick check of the growths.
408   // If the analyzed wire contains any of the edges from the hole faces
409   // it is considered as growth.
410   TopTools_IndexedMapOfShape aMHE;
411
412   // Analyze the new wires - classify them to be the holes and growths
413   TopTools_ListIteratorOfListOfShape aItLL(myLoops);
414   for (; aItLL.More(); aItLL.Next())
415   {
416     const TopoDS_Shape& aWire = aItLL.Value();
417
418     TopoDS_Face aFace;
419     aBB.MakeFace(aFace, aS, aLoc, aTol);
420     aBB.Add(aFace, aWire);
421
422     Standard_Boolean bIsGrowth = IsGrowthWire(aWire, aMHE);
423     if (!bIsGrowth)
424     {
425       // Fast check did not give the result, run classification
426       IntTools_FClass2d& aClsf = myContext->FClass2d(aFace);
427       bIsGrowth = !aClsf.IsHole();
428     }
429
430     // Save the face
431     if (bIsGrowth)
432     {
433       aNewFaces.Append(aFace);
434     }
435     else
436     {
437       aHoleFaces.Add(aFace);
438       TopExp::MapShapes(aWire, TopAbs_EDGE, aMHE);
439     }
440   }
441
442   if (aHoleFaces.IsEmpty())
443   {
444     // No holes, stop the analysis
445     myAreas.Append(aNewFaces);
446     return;
447   }
448
449   // Classify holes relatively faces
450
451   // Prepare tree with the boxes of the hole faces
452   BOPTools_Box2dTree aBoxTree;
453   Standard_Integer i, aNbH = aHoleFaces.Extent();
454   aBoxTree.SetSize (aNbH);
455   for (i = 1; i <= aNbH; ++i)
456   {
457     const TopoDS_Face& aHFace = TopoDS::Face(aHoleFaces(i));
458     //
459     Bnd_Box2d aBox;
460     BRepTools::AddUVBounds(aHFace, aBox);
461     aBoxTree.Add(i, Bnd_Tools::Bnd2BVH (aBox));
462   }
463
464   // Build BVH
465   aBoxTree.Build();
466
467   // Find outer growth face that is most close to each hole face
468   TopTools_IndexedDataMapOfShapeShape aHoleFaceMap;
469
470   // Selector
471   BOPTools_Box2dTreeSelector aSelector;
472   aSelector.SetBVHSet (&aBoxTree);
473
474   TopTools_ListIteratorOfListOfShape aItLS(aNewFaces);
475   for (; aItLS.More(); aItLS.Next())
476   {
477     const TopoDS_Face& aFace = TopoDS::Face(aItLS.Value());
478
479     // Build box
480     Bnd_Box2d aBox;
481     BRepTools::AddUVBounds(aFace, aBox);
482
483     aSelector.Clear();
484     aSelector.SetBox(Bnd_Tools::Bnd2BVH (aBox));
485     aSelector.Select();
486
487     const TColStd_ListOfInteger& aLI = aSelector.Indices();
488     TColStd_ListIteratorOfListOfInteger aItLI(aLI);
489     for (; aItLI.More(); aItLI.Next())
490     {
491       Standard_Integer k = aItLI.Value();
492       const TopoDS_Shape& aHole = aHoleFaces(k);
493       // Check if it is inside
494       if (!IsInside(aHole, aFace, myContext))
495         continue;
496
497       // Save the relation
498       TopoDS_Shape* pFaceWas = aHoleFaceMap.ChangeSeek(aHole);
499       if (pFaceWas)
500       {
501         if (IsInside(aFace, *pFaceWas, myContext))
502         {
503           *pFaceWas = aFace;
504         }
505       }
506       else
507       {
508         aHoleFaceMap.Add(aHole, aFace);
509       }
510     }
511   }
512
513   // Make the back map from faces to holes
514   TopTools_IndexedDataMapOfShapeListOfShape aFaceHolesMap;
515
516   aNbH = aHoleFaceMap.Extent();
517   for (i = 1; i <= aNbH; ++i)
518   {
519     const TopoDS_Shape& aHole = aHoleFaceMap.FindKey(i);
520     const TopoDS_Shape& aFace = aHoleFaceMap(i);
521     //
522     TopTools_ListOfShape* pLHoles = aFaceHolesMap.ChangeSeek(aFace);
523     if (!pLHoles)
524       pLHoles = &aFaceHolesMap(aFaceHolesMap.Add(aFace, TopTools_ListOfShape()));
525     pLHoles->Append(aHole);
526   }
527
528   // Add unused holes to the original face
529   if (aHoleFaces.Extent() != aHoleFaceMap.Extent())
530   {
531     Bnd_Box aBoxF;
532     BRepBndLib::Add(myFace, aBoxF);
533     if (aBoxF.IsOpenXmin() || aBoxF.IsOpenXmax() ||
534         aBoxF.IsOpenYmin() || aBoxF.IsOpenYmax() ||
535         aBoxF.IsOpenZmin() || aBoxF.IsOpenZmax())
536     {
537       TopoDS_Face aFace;
538       aBB.MakeFace(aFace, aS, aLoc, aTol);
539       TopTools_ListOfShape& anUnUsedHoles = aFaceHolesMap(aFaceHolesMap.Add(aFace, TopTools_ListOfShape()));
540       aNbH = aHoleFaces.Extent();
541       for (i = 1; i <= aNbH; ++i)
542       {
543         const TopoDS_Shape& aHole = aHoleFaces(i);
544         if (!aHoleFaceMap.Contains(aHole))
545           anUnUsedHoles.Append(aHole);
546       }
547       // Save it
548       aNewFaces.Append(aFace);
549     }
550   }
551
552   // Add Holes to Faces and add them to myAreas
553   aItLS.Initialize(aNewFaces);
554   for ( ; aItLS.More(); aItLS.Next())
555   {
556     TopoDS_Face& aFace = *(TopoDS_Face*)&aItLS.Value();
557     const TopTools_ListOfShape* pLHoles = aFaceHolesMap.Seek(aFace);
558     if (pLHoles)
559     {
560       // update faces with the holes
561       TopTools_ListIteratorOfListOfShape aItLH(*pLHoles);
562       for (; aItLH.More(); aItLH.Next())
563       {
564         const TopoDS_Shape& aFHole = aItLH.Value();
565         // The hole face contains only one wire
566         TopoDS_Iterator aItW(aFHole);
567         aBB.Add(aFace, aItW.Value());
568       }
569
570       // update classifier
571       myContext->FClass2d(aFace).Init(aFace, aTol);
572     }
573
574     // The face is just a draft that does not contain any internal shapes
575     myAreas.Append(aFace);
576   }
577 }
578 //=======================================================================
579 //function : PerformInternalShapes
580 //purpose  : 
581 //=======================================================================
582 void BOPAlgo_BuilderFace::PerformInternalShapes()
583 {
584   if (myAvoidInternalShapes)
585     // User-defined option to avoid internal edges
586     // in the result is in force.
587     return;
588
589   if (myLoopsInternal.IsEmpty())
590     // No edges left for classification
591     return;
592
593   // Prepare tree with the boxes of the edges to classify
594   BOPTools_Box2dTree aBoxTree;
595
596   // Map of edges to classify
597   TopTools_IndexedMapOfShape anEdgesMap;
598
599   // Fill the tree and the map
600   TopTools_ListIteratorOfListOfShape itLE(myLoopsInternal);
601   for (; itLE.More(); itLE.Next())
602   {
603     TopoDS_Iterator itE(itLE.Value());
604     for (; itE.More(); itE.Next())
605     {
606       const TopoDS_Edge& aE = TopoDS::Edge(itE.Value());
607       if (!anEdgesMap.Contains(aE))
608       {
609         Bnd_Box2d aBoxE;
610         BRepTools::AddUVBounds(myFace, aE, aBoxE);
611         // Make sure the index of edge in the map and
612         // of the box in the tree is the same
613         aBoxTree.Add(anEdgesMap.Add(aE), Bnd_Tools::Bnd2BVH (aBoxE));
614       }
615     }
616   }
617
618   // Build BVH
619   aBoxTree.Build();
620
621   // Fence map
622   TColStd_MapOfInteger aMEDone;
623
624   // Classify edges relatively faces
625   TopTools_ListIteratorOfListOfShape itLF(myAreas);
626   for (; itLF.More(); itLF.Next())
627   {
628     TopoDS_Face& aF = *(TopoDS_Face*)&itLF.Value();
629
630     // Build box
631     Bnd_Box2d aBoxF;
632     BRepTools::AddUVBounds(aF, aBoxF);
633
634     // Select edges for the classification
635     BOPTools_Box2dTreeSelector aSelector;
636     aSelector.SetBVHSet (&aBoxTree);
637     aSelector.SetBox(Bnd_Tools::Bnd2BVH (aBoxF));
638     if (!aSelector.Select())
639       continue;
640
641     // Collect edges inside the face
642     TopTools_IndexedMapOfShape anEdgesInside;
643
644     const TColStd_ListOfInteger& aLI = aSelector.Indices();
645     TColStd_ListIteratorOfListOfInteger itLI(aLI);
646     for (; itLI.More(); itLI.Next())
647     {
648       const Standard_Integer nE = itLI.Value();
649       if (aMEDone.Contains(nE))
650         continue;
651
652       const TopoDS_Edge& aE = TopoDS::Edge(anEdgesMap(nE));
653       if (IsInside(aE, aF, myContext))
654       {
655         anEdgesInside.Add(aE);
656         aMEDone.Add(nE);
657       }
658     }
659
660     if (anEdgesInside.IsEmpty())
661       continue;
662
663     // Make internal wires
664     TopTools_ListOfShape aLSI;
665     MakeInternalWires(anEdgesInside, aLSI);
666
667     // Add wires to a face
668     TopTools_ListIteratorOfListOfShape itLSI(aLSI);
669     for (; itLSI.More(); itLSI.Next())
670     {
671       const TopoDS_Shape& aWI = itLSI.Value();
672       BRep_Builder().Add(aF, aWI);
673     }
674
675     // Condition of early exit
676     if (aMEDone.Extent() == anEdgesMap.Extent())
677       // All edges are classified and added into the faces
678       return;
679   }
680
681   // Some edges are left unclassified - warn user about them
682   TopTools_IndexedMapOfShape anEdgesUnUsed;
683   for (Standard_Integer i = 1; i <= anEdgesMap.Extent(); ++i)
684   {
685     if (!aMEDone.Contains(i))
686       anEdgesUnUsed.Add(anEdgesMap(i));
687   }
688
689   // Make internal wires
690   TopTools_ListOfShape aLSI;
691   MakeInternalWires(anEdgesUnUsed, aLSI);
692
693   // Make compound
694   TopoDS_Compound aWShape;
695   BRep_Builder().MakeCompound(aWShape);
696   BRep_Builder().Add(aWShape, myFace);
697   if (aLSI.Extent() == 1)
698     BRep_Builder().Add(aWShape, aLSI.First());
699   else
700   {
701     TopoDS_Compound aCE;
702     BRep_Builder().MakeCompound(aCE);
703     for (TopTools_ListIteratorOfListOfShape it(aLSI); it.More(); it.Next())
704       BRep_Builder().Add(aCE, it.Value());
705     BRep_Builder().Add(aWShape, aCE);
706   }
707
708   // Add warning
709   AddWarning(new BOPAlgo_AlertFaceBuilderUnusedEdges(aWShape));
710 }
711 //=======================================================================
712 //function : MakeInternalWires
713 //purpose  : 
714 //=======================================================================
715 void MakeInternalWires(const TopTools_IndexedMapOfShape& theME,
716                        TopTools_ListOfShape& theWires)
717 {
718   Standard_Integer i, aNbE;
719   TopTools_MapOfShape aAddedMap;
720   TopTools_ListIteratorOfListOfShape aItE;
721   TopTools_IndexedDataMapOfShapeListOfShape aMVE;
722   BRep_Builder aBB;
723   //
724   aNbE = theME.Extent();
725   for (i = 1; i <= aNbE; ++i) {
726     const TopoDS_Shape& aE = theME(i);
727     TopExp::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
728   }
729   //
730   for (i = 1; i <= aNbE; ++i) {
731     TopoDS_Shape aEE = theME(i);
732     if (!aAddedMap.Add(aEE)) {
733       continue;
734     }
735     //
736     // make a new shell
737     TopoDS_Wire aW;
738     aBB.MakeWire(aW);    
739     aEE.Orientation(TopAbs_INTERNAL);
740     aBB.Add(aW, aEE);
741     //
742     TopoDS_Iterator aItAdded (aW);
743     for (; aItAdded.More(); aItAdded.Next()) {
744       const TopoDS_Shape& aE =aItAdded.Value();
745       //
746       TopExp_Explorer aExp(aE, TopAbs_VERTEX);
747       for (; aExp.More(); aExp.Next()) {
748         const TopoDS_Shape& aV =aExp.Current();
749         const TopTools_ListOfShape& aLE=aMVE.FindFromKey(aV);
750         aItE.Initialize(aLE);
751         for (; aItE.More(); aItE.Next()) { 
752           TopoDS_Shape aEL=aItE.Value();
753           if (aAddedMap.Add(aEL)){
754             aEL.Orientation(TopAbs_INTERNAL);
755             aBB.Add(aW, aEL);
756           }
757         }
758       }
759     }
760     aW.Closed(BRep_Tool::IsClosed(aW));
761     theWires.Append(aW);
762   }
763 }
764 //=======================================================================
765 //function : IsInside
766 //purpose  : 
767 //=======================================================================
768 Standard_Boolean IsInside(const TopoDS_Shape& theWire,
769                           const TopoDS_Shape& theF,
770                           Handle(IntTools_Context)& theContext)
771 {
772   // Check if the wire is located inside the face:
773   // take unique point from the wire and classify it relatively the face
774
775   // Avoid edges of the face
776   TopTools_IndexedMapOfShape aFaceEdgesMap;
777   TopExp::MapShapes(theF, TopAbs_EDGE, aFaceEdgesMap);
778
779   // Get classification tool from the context
780   const TopoDS_Face& aF = TopoDS::Face(theF);
781   IntTools_FClass2d& aClassifier = theContext->FClass2d(aF);
782
783   Standard_Boolean isInside = Standard_False;
784
785   // Iterate on wire edges until first classification is performed
786   TopExp_Explorer anExp(theWire, TopAbs_EDGE);
787   for (; anExp.More(); anExp.Next())
788   {
789     const TopoDS_Edge& aE = TopoDS::Edge(anExp.Current());
790     if (BRep_Tool::Degenerated(aE))
791       // Avoid checking degenerated edges.
792       continue;
793
794     if (aFaceEdgesMap.Contains(aE))
795       // Face contains the edge from the wire, thus the wire cannot be
796       // inside that face.
797       return isInside;
798
799     // Get 2d curve of the edge on the face
800     Standard_Real aT1, aT2;
801     const Handle(Geom2d_Curve)& aC2D = BRep_Tool::CurveOnSurface(aE, aF, aT1, aT2);
802     if (aC2D.IsNull())
803       continue;
804
805     // Get middle point on the curve
806     gp_Pnt2d aP2D = aC2D->Value((aT1 + aT2) / 2.);
807
808     // Classify the point
809     TopAbs_State aState = aClassifier.Perform(aP2D);
810     isInside = (aState == TopAbs_IN);
811     break;
812   }
813   return isInside;
814 }
815 //=======================================================================
816 //function : IsGrowthWire
817 //purpose  : 
818 //=======================================================================
819 Standard_Boolean IsGrowthWire(const TopoDS_Shape& theWire,
820                               const TopTools_IndexedMapOfShape& theMHE)
821 {
822   if (theMHE.Extent())
823   {
824     TopoDS_Iterator aIt(theWire);
825     for(; aIt.More(); aIt.Next())
826     {
827       if (theMHE.Contains(aIt.Value()))
828         return Standard_True;
829     }
830   }
831   return Standard_False;
832 }