7584d5a729839addc748a939c190cac42105faa9
[occt.git] / src / BOPAlgo / BOPAlgo_WireSplitter_1.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 //
4 // This file is part of Open CASCADE Technology software library.
5 //
6 // This library is free software; you can redistribute it and / or modify it
7 // under the terms of the GNU Lesser General Public version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
11 //
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
14
15 #include <BOPAlgo_WireSplitter.ixx>
16
17 #include <Precision.hxx>
18
19 #include <gp_Pnt2d.hxx>
20 #include <gp_Vec2d.hxx>
21 #include <gp_Dir2d.hxx>
22 #include <Geom2d_Curve.hxx>
23 #include <GeomAdaptor_Surface.hxx>
24
25 #include <TopoDS_Edge.hxx>
26 #include <TopoDS_Vertex.hxx>
27 #include <TopoDS_Wire.hxx>
28 #include <TopoDS_Iterator.hxx>
29 #include <BRep_Tool.hxx>
30 #include <BRepAdaptor_Surface.hxx>
31
32 #include <BOPCol_ListOfShape.hxx>
33 #include <BOPCol_SequenceOfShape.hxx>
34 #include <BOPCol_SequenceOfPnt2d.hxx>
35 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
36 //
37 #include <Geom_Surface.hxx>
38 #include <Geom_Plane.hxx>
39 #include <Geom_RectangularTrimmedSurface.hxx>
40 #include <Geom_RectangularTrimmedSurface.hxx>
41 #include <BOPTools_AlgoTools2D.hxx>
42 #include <TopLoc_Location.hxx>
43 #include <BRep_Builder.hxx>
44 #include <BOPCol_SequenceOfReal.hxx>
45 #include <TopExp.hxx>
46 #include <TopExp_Explorer.hxx>
47 #include <BOPTools_AlgoTools2D.hxx>
48 #include <Geom2dAdaptor_Curve.hxx>
49 //
50
51 static
52   Standard_Real Angle (const gp_Dir2d& aDir2D);
53
54 static
55   Standard_Real Angle2D (const TopoDS_Vertex& aV,
56                          const TopoDS_Edge& anEdge,
57                          const TopoDS_Face& myFace,
58                          const GeomAdaptor_Surface& aGAS,
59                          const Standard_Boolean aFlag);
60
61 static
62   void GetNextVertex(const TopoDS_Vertex& aV,
63                      const TopoDS_Edge& aE,
64                      TopoDS_Vertex& aV1);
65
66 static
67   Standard_Real AngleIn(const TopoDS_Edge& aEIn,
68                         const BOPAlgo_ListOfEdgeInfo& aLEInfo);
69
70 static
71   Standard_Integer NbWaysOut(const BOPAlgo_ListOfEdgeInfo& aLEInfo);
72
73 static
74   gp_Pnt2d Coord2dVf (const TopoDS_Edge& aE,
75                       const TopoDS_Face& aF);
76
77 static
78   gp_Pnt2d Coord2d (const TopoDS_Vertex& aV1,
79                     const TopoDS_Edge& aE1,
80                     const TopoDS_Face& aF);
81
82
83 static
84   Standard_Real ClockWiseAngle(const Standard_Real aAngleIn,
85                                const Standard_Real aAngleOut);
86
87 static 
88   void Path (const GeomAdaptor_Surface& aGAS,
89              const TopoDS_Face& myFace,
90              const TopoDS_Vertex& aVa,
91              const TopoDS_Edge& aEOuta,
92              BOPAlgo_EdgeInfo& anEdgeInfo,
93              BOPCol_SequenceOfShape& aLS,
94              BOPCol_SequenceOfShape& aVertVa,
95              BOPCol_SequenceOfPnt2d& aCoordVa,
96              BOPTools_ConnexityBlock& aCB,
97              BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap);
98              
99 static
100   Standard_Real Angle2D (const TopoDS_Vertex& aV,
101                          const TopoDS_Edge& anEdge,
102                          const TopoDS_Face& myFace,
103                          const GeomAdaptor_Surface& aGAS,
104                          const Standard_Boolean aFlag);
105 static
106   Standard_Real Angle (const gp_Dir2d& aDir2D);
107
108 static
109   Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
110                              const GeomAdaptor_Surface& aGAS);
111
112
113
114 static
115   Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
116                               const GeomAdaptor_Surface& aGAS);
117 static
118   Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
119                               const GeomAdaptor_Surface& aGAS);
120
121 static
122   Standard_Boolean RecomputeAngles(const BOPAlgo_ListOfEdgeInfo& aLEInfo, 
123                                    const TopoDS_Face&            theFace, 
124                                    const gp_Pnt2d&               thePb, 
125                                    const TopoDS_Vertex&          theVb,
126                                    const GeomAdaptor_Surface&    theGAS,
127                                    const TopoDS_Edge&            theEOuta, 
128                                    const Standard_Boolean&       bHasClosed,
129                                    const Standard_Real&          theTol2D,
130                                    BOPCol_SequenceOfReal&        theRecomputedAngles);
131
132 //=======================================================================
133 //function : SplitBlock
134 //purpose  : 
135 //=======================================================================
136   void BOPAlgo_WireSplitter::SplitBlock(BOPTools_ConnexityBlock& aCB)
137 {
138   Standard_Boolean bNothingToDo;
139   Standard_Integer aIx, aNb, i, aCntIn, aCntOut;
140   Standard_Real aAngle;
141   TopAbs_Orientation aOr;
142   TopoDS_Iterator aItS;
143   TopoDS_Vertex aVV;
144   BOPCol_ListIteratorOfListOfShape aIt;
145   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
146   //
147   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo mySmartMap(100, myAllocator);
148   //
149   const TopoDS_Face& myFace=myWES->Face();
150   const BOPCol_ListOfShape& myEdges=aCB.Shapes();
151   //
152   // 1.Filling mySmartMap
153   BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane(myEdges, myFace);
154   //
155   aIt.Initialize(myEdges);
156   for(; aIt.More(); aIt.Next()) {
157     const TopoDS_Edge& aE=(*(TopoDS_Edge *)&aIt.Value());
158     if (!BOPTools_AlgoTools2D::HasCurveOnSurface (aE, myFace)) {
159       continue;
160     }
161     //
162     aItS.Initialize(aE);
163     for(; aItS.More(); aItS.Next()) {
164       const TopoDS_Shape& aV=aItS.Value();
165       aIx=mySmartMap.FindIndex(aV);
166       if (!aIx) {
167         BOPAlgo_ListOfEdgeInfo aLEIx(myAllocator);
168         aIx=mySmartMap.Add(aV, aLEIx);
169       }
170       //
171       BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(aIx);
172       //
173       BOPAlgo_EdgeInfo aEI;
174       //
175       aEI.SetEdge(aE);
176       aOr=aV.Orientation();
177       if (aOr==TopAbs_FORWARD) {
178         aEI.SetInFlag(Standard_False);
179       }
180       else if (aOr==TopAbs_REVERSED) {
181         aEI.SetInFlag(Standard_True);
182       }
183       aLEI.Append(aEI);
184     }
185   }
186   //
187   aNb=mySmartMap.Extent();
188   //
189   bNothingToDo=Standard_True;
190   for (i=1; i<=aNb; i++) {
191     aCntIn=0;
192     aCntOut=0;
193     const BOPAlgo_ListOfEdgeInfo& aLEInfo= mySmartMap(i);
194     BOPAlgo_ListIteratorOfListOfEdgeInfo anIt(aLEInfo);
195     for (; anIt.More(); anIt.Next()) {
196       const BOPAlgo_EdgeInfo& aEI=anIt.Value();
197       if (aEI.IsIn()) {
198         aCntIn++;
199       }
200       else {
201         aCntOut++;
202       }
203     }
204     if (aCntIn!=1 || aCntOut!=1) {
205       bNothingToDo=Standard_False;
206       break;
207     }
208   }
209   //
210   // Each vertex has one edge In and one - Out. Good. But it is not enought
211   // to consider that nothing to do with this. We must check edges on TShape
212   // coinsidence. If there are such edges there is something to do with.
213   if (bNothingToDo) {
214     Standard_Integer aNbE, aNbMapEE;
215     Standard_Boolean bFlag;
216     //
217     BOPCol_IndexedDataMapOfShapeListOfShape aMapEE(100, myAllocator);
218     aNbE=myEdges.Extent();
219     //
220     aIt.Initialize(myEdges);
221     for (; aIt.More(); aIt.Next()) {
222       const TopoDS_Shape& aE = aIt.Value();
223       if (!aMapEE.Contains(aE)) {
224         BOPCol_ListOfShape aLEx(myAllocator);
225         aLEx.Append(aE);
226         aMapEE.Add(aE, aLEx);
227       }
228       else {
229         BOPCol_ListOfShape& aLEx=aMapEE.ChangeFromKey(aE);
230         aLEx.Append(aE);
231       }
232     }
233     //
234     bFlag=Standard_True;
235     aNbMapEE=aMapEE.Extent();
236     for (i=1; i<=aNbMapEE; ++i) {
237       const BOPCol_ListOfShape& aLEx=aMapEE(i);
238       aNbE=aLEx.Extent();
239       if (aNbE==1) {// usual case
240         continue;
241       }
242       else if (aNbE==2){
243         const TopoDS_Shape& aE1=aLEx.First();
244         const TopoDS_Shape& aE2=aLEx.Last();
245         if (aE1.IsSame(aE2)) {
246           bFlag=Standard_False;
247           break;
248         }
249       }
250       else {
251         bFlag=Standard_False;
252         break;
253       }
254     }
255     bNothingToDo=bNothingToDo && bFlag;
256   } // if (bNothingToDo) {
257   if (bNothingToDo) {
258     TopoDS_Wire aW;
259     //
260     BOPCol_ListOfShape& aLECB=aCB.ChangeShapes();
261     BOPAlgo_WireSplitter::MakeWire(aLECB, aW);
262     BOPCol_ListOfShape& aLoops=aCB.ChangeLoops();
263     aLoops.Append(aW);
264     //
265     myErrorStatus=0;
266     return;
267   }
268   //
269   // 3. Angles in mySmartMap
270   BRepAdaptor_Surface aBAS(myFace);
271   const GeomAdaptor_Surface& aGAS=aBAS.Surface();
272   //
273   for (i=1; i<=aNb; i++) {
274     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i))); 
275     const BOPAlgo_ListOfEdgeInfo& aLEI= mySmartMap(i);
276
277     aItLEI.Initialize(aLEI);
278     for (; aItLEI.More(); aItLEI.Next()) {
279       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
280       const TopoDS_Edge& aE=aEI.Edge();
281       //
282       aVV=aV;
283       if (aEI.IsIn()) {
284         aVV.Orientation(TopAbs_REVERSED);
285         aAngle=Angle2D (aVV, aE, myFace, aGAS, Standard_True);
286       }
287       else { // OUT
288         aVV.Orientation(TopAbs_FORWARD);
289         aAngle=Angle2D (aVV, aE, myFace, aGAS, Standard_False);
290       }
291       aEI.SetAngle(aAngle);
292     }
293   }// for (i=1; i<=aNb; i++) {
294   //
295   // 4. Do
296   //
297   Standard_Boolean bIsOut, bIsNotPassed;
298   BOPCol_SequenceOfShape aLS, aVertVa;
299   BOPCol_SequenceOfPnt2d aCoordVa;
300   //
301   for (i=1; i<=aNb; ++i) {
302     const TopoDS_Vertex& aVa=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i))); 
303     const BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
304     aItLEI.Initialize(aLEI);
305     for (; aItLEI.More(); aItLEI.Next()) {
306       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
307       const TopoDS_Edge& aEOuta=aEI.Edge();
308       //
309       bIsOut=!aEI.IsIn();
310       bIsNotPassed=!aEI.Passed();
311       if (bIsOut && bIsNotPassed) {
312         //
313         aLS.Clear();
314         aVertVa.Clear();
315         aCoordVa.Clear();
316         //
317         Path(aGAS, myFace, aVa, aEOuta, aEI, aLS, 
318              aVertVa, aCoordVa, aCB, mySmartMap);
319       }
320     }
321   }// for (i=1; i<=aNb; ++i) {
322 }
323 //=======================================================================
324 // function: Path
325 // purpose: 
326 //=======================================================================
327 void Path (const GeomAdaptor_Surface& aGAS,
328            const TopoDS_Face& myFace,
329            const TopoDS_Vertex& aVa,
330            const TopoDS_Edge& aEOuta,
331            BOPAlgo_EdgeInfo& anEdgeInfo,
332            BOPCol_SequenceOfShape& aLS,
333            BOPCol_SequenceOfShape& aVertVa,
334            BOPCol_SequenceOfPnt2d& aCoordVa,
335            BOPTools_ConnexityBlock& aCB,
336            BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap)
337      
338 {
339   Standard_Integer i, j, aNb, aNbj;
340   Standard_Real aTol, anAngleIn, anAngleOut, anAngle, aMinAngle;
341   Standard_Real aTol2D, aTol2D2;
342   Standard_Real aTol2, aD2, aTwoPI;
343   Standard_Boolean anIsSameV2d, anIsSameV, anIsFound, anIsOut, anIsNotPassed;
344   TopoDS_Vertex aVb;
345   TopoDS_Edge aEOutb;
346   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
347   //
348   aTwoPI = M_PI + M_PI;
349   aTol=1.e-7;
350   //
351   // append block
352   //
353   // Do not escape through edge from which you enter 
354   aNb=aLS.Length();
355   if (aNb==1) {
356     const TopoDS_Shape& anEPrev=aLS(aNb);
357     if (anEPrev.IsSame(aEOuta)) {
358       return;
359     }
360   }
361   //
362   anEdgeInfo.SetPassed(Standard_True);
363   aLS.Append(aEOuta);
364   aVertVa.Append(aVa);
365   
366   TopoDS_Vertex pVa=aVa;
367   pVa.Orientation(TopAbs_FORWARD);
368   gp_Pnt2d aPa=Coord2d(pVa, aEOuta, myFace);
369   aCoordVa.Append(aPa);
370   
371   GetNextVertex (pVa, aEOuta, aVb);
372
373   gp_Pnt2d aPb=Coord2d(aVb, aEOuta, myFace);
374
375   const BOPAlgo_ListOfEdgeInfo& aLEInfoVb=mySmartMap.FindFromKey(aVb);
376   //
377   aTol=2.*Tolerance2D(aVb, aGAS);
378   aTol2=10.*aTol*aTol;
379
380   TopoDS_Vertex aV1, aV2;
381   TopExp::Vertices(aEOuta, aV1, aV2);
382   Standard_Boolean bIsClosedEdge = aV1.IsNull() || aV2.IsNull() || aV1.IsSame(aV2);
383   Standard_Boolean bIsDegenerated = BRep_Tool::Degenerated(aEOuta);
384   Standard_Boolean bIsSeam = BRep_Tool::IsClosed(aEOuta, myFace);
385
386   anIt.Initialize(aLEInfoVb);
387   for (; anIt.More(); anIt.Next()) {
388     const BOPAlgo_EdgeInfo& anEI = anIt.Value();
389     const TopoDS_Edge& aE = anEI.Edge();
390     bIsDegenerated = bIsDegenerated || BRep_Tool::Degenerated(aE);
391     bIsSeam = bIsSeam || BRep_Tool::IsClosed(aE, myFace);
392     aV1.Nullify();
393     aV2.Nullify();
394     TopExp::Vertices(aE, aV1, aV2);
395     bIsClosedEdge = bIsClosedEdge || aV1.IsNull() || aV2.IsNull() || aV1.IsSame(aV2);
396   }
397   //
398   aNb=aLS.Length();
399   if (aNb>0) {
400     //
401     BOPCol_ListOfShape aBuf;
402     //
403     for (i=aNb; i>0; --i) {
404       const TopoDS_Shape& aVPrev=aVertVa(i);
405       const gp_Pnt2d& aPaPrev=aCoordVa(i);
406       const TopoDS_Shape& aEPrev=aLS(i);
407
408       aBuf.Append(aEPrev);
409
410       anIsSameV=aVPrev.IsSame(aVb);
411       anIsSameV2d=Standard_False;
412
413       if (anIsSameV) {
414         anIsSameV2d = Standard_True;
415         //
416         aD2=aPaPrev.SquareDistance(aPb);
417         anIsSameV2d =aD2<aTol2;
418         if(anIsSameV2d && 
419            (bIsDegenerated || bIsSeam || bIsClosedEdge)) {
420           Standard_Real udist = fabs(aPaPrev.X() - aPb.X());
421           Standard_Real vdist = fabs(aPaPrev.Y() - aPb.Y());
422           Standard_Real aTolU = 2. * UTolerance2D(aVb, aGAS);
423           Standard_Real aTolV = 2. * VTolerance2D(aVb, aGAS);
424           //
425           if((udist > aTolU) ||
426              (vdist > aTolV)) {
427             anIsSameV2d = Standard_False;
428           }
429         }
430       }//if (anIsSameV) {
431       //
432       if (anIsSameV && anIsSameV2d) {
433         Standard_Integer iPriz;
434         iPriz=1;
435         if (aBuf.Extent()==2) {
436           if(aBuf.First().IsSame(aBuf.Last())) {
437             iPriz=0;
438           }
439         }
440         if (iPriz) {
441           TopoDS_Wire aW;
442           BOPAlgo_WireSplitter::MakeWire(aBuf, aW);
443           aCB.ChangeLoops().Append(aW);
444         }
445         //
446         aNbj=i-1;
447         if (aNbj<1) {
448           //
449           aLS.Clear();
450           aVertVa.Clear();
451           aCoordVa.Clear();
452           //
453           return;
454         }
455         //
456         BOPCol_SequenceOfShape aLSt, aVertVat;
457         BOPCol_SequenceOfPnt2d aCoordVat;
458         //
459         aVb=(*(TopoDS_Vertex *)(&aVertVa(i))); 
460         //
461         for (j=1; j<=aNbj; ++j) {
462           aLSt.Append(aLS(j));
463           aVertVat.Append(aVertVa(j));
464           aCoordVat.Append(aCoordVa(j));
465         }
466         //
467         aLS.Clear();
468         aVertVa.Clear();
469         aCoordVa.Clear();
470         
471         aLS=aLSt;
472         aVertVa=aVertVat;
473         aCoordVa=aCoordVat;
474         //
475         break;
476       }
477     }
478   }
479   //
480   aTol2D=2.*Tolerance2D(aVb, aGAS);
481   aTol2D2=1000.*aTol2D*aTol2D;//100.*aTol2D*aTol2D;
482   //
483   // anAngleIn in Vb from edge aEOuta
484   const BOPAlgo_ListOfEdgeInfo& aLEInfo=mySmartMap.FindFromKey(aVb);
485   //
486   anAngleIn=AngleIn(aEOuta, aLEInfo);
487   BOPCol_SequenceOfReal aRecomputedAngles;
488
489   Standard_Boolean bRecomputeAngle = 
490     RecomputeAngles(aLEInfo, myFace, aPb, aVb, aGAS, aEOuta, 
491                     (bIsDegenerated || bIsSeam || bIsClosedEdge),
492                     aTol2D, aRecomputedAngles);
493
494   //
495   // aEOutb
496   BOPAlgo_EdgeInfo *pEdgeInfo=NULL;
497   //
498   aMinAngle=100.;
499   anIsFound=Standard_False;
500   Standard_Integer aCurIndexE = 0;
501   anIt.Initialize(aLEInfo);
502   for (; anIt.More(); anIt.Next()) {
503     BOPAlgo_EdgeInfo& anEI=anIt.ChangeValue();
504     const TopoDS_Edge& aE=anEI.Edge();
505     anIsOut=!anEI.IsIn();
506     anIsNotPassed=!anEI.Passed();
507     
508     if (anIsOut && anIsNotPassed) {
509       aCurIndexE++;
510       //
511       // Is there one way to go out of the vertex 
512       // we have to use it only.
513       Standard_Integer iCnt;
514       iCnt=NbWaysOut (aLEInfo);
515       //
516       if (!iCnt) {
517         // no way to go . (Error)
518         return ;
519       }
520       //
521       if (iCnt==1) {
522         // the one and only way to go out .
523         pEdgeInfo=&anEI;
524         anIsFound=Standard_True;
525         break;
526       }
527       //
528       if (aE.IsSame(aEOuta)) {
529         anAngle = aTwoPI;
530       } else {
531         // Look for minimal angle and make the choice.
532         gp_Pnt2d aP2Dx;
533         //
534         aP2Dx=Coord2dVf(aE, myFace);
535         //
536         aD2=aP2Dx.SquareDistance(aPb);
537         if (aD2 > aTol2D2){
538           continue;
539         }
540         //
541         //
542         anAngleOut=anEI.Angle();
543         //
544         if(bRecomputeAngle) {
545           if(aCurIndexE <= aRecomputedAngles.Length()) {
546             anAngleOut = aRecomputedAngles.Value(aCurIndexE);
547           }
548         }
549         anAngle=ClockWiseAngle(anAngleIn, anAngleOut);
550       }
551       if (anAngle < aMinAngle) {
552         aMinAngle=anAngle;
553         pEdgeInfo=&anEI;
554         anIsFound=Standard_True;
555       }
556     }
557   } // for (; anIt.More(); anIt.Next()) 
558   //
559   if (!anIsFound) {
560     // no way to go . (Error)
561     return;
562   }
563   
564   aEOutb=pEdgeInfo->Edge();
565   //
566   Path (aGAS, myFace, aVb, aEOutb, *pEdgeInfo, aLS, 
567         aVertVa, aCoordVa, aCB, mySmartMap);
568 }
569 //=======================================================================
570 // function:  ClockWiseAngle
571 // purpose:
572 //=======================================================================
573  Standard_Real ClockWiseAngle(const Standard_Real aAngleIn,
574                               const Standard_Real aAngleOut)
575 {
576   Standard_Real aTwoPi=M_PI+M_PI;
577   Standard_Real dA, A1, A2, AIn, AOut ;
578
579   AIn=aAngleIn;
580   AOut=aAngleOut;
581   if (AIn >= aTwoPi) {
582     AIn=AIn-aTwoPi;
583   }
584   
585   if (AOut >= aTwoPi) {
586     AOut=AOut-aTwoPi;
587   }
588
589   A1=AIn+M_PI;
590   
591   if (A1 >= aTwoPi) {
592     A1=A1-aTwoPi;
593   }
594   
595   A2=AOut;
596   
597   dA=A1-A2;
598   if (dA <= 0.) {
599     dA=aTwoPi+dA;
600   }
601   //xx
602   //else if (dA <= 1.e-15) {
603   else if (dA <= 1.e-14) {
604     dA=aTwoPi;
605   }
606   return dA;
607 }
608 //=======================================================================
609 // function:  Coord2d
610 // purpose:
611 //=======================================================================
612  gp_Pnt2d Coord2d (const TopoDS_Vertex& aV1,
613                    const TopoDS_Edge& aE1,
614                    const TopoDS_Face& aF)
615 {
616   Standard_Real aT, aFirst, aLast;
617   Handle(Geom2d_Curve) aC2D;
618   gp_Pnt2d aP2D1;
619   //
620   aT=BRep_Tool::Parameter (aV1, aE1, aF);
621   aC2D=BRep_Tool::CurveOnSurface(aE1, aF, aFirst, aLast);
622   aC2D->D0 (aT, aP2D1);
623   //
624   return aP2D1;
625 }
626 //=======================================================================
627 // function:  Coord2dVf
628 // purpose:
629 //=======================================================================
630  gp_Pnt2d Coord2dVf (const TopoDS_Edge& aE,
631                      const TopoDS_Face& aF)
632 {
633   Standard_Real aCoord=99.;
634   gp_Pnt2d aP2D1(aCoord, aCoord);
635   TopoDS_Iterator aIt;
636   //
637   aIt.Initialize(aE);
638   for (; aIt.More(); aIt.Next()) {
639     const TopoDS_Shape& aVx=aIt.Value();
640     if (aVx.Orientation()==TopAbs_FORWARD) {
641       
642       const TopoDS_Vertex& aVxx=(*(TopoDS_Vertex *)(&aVx));// TopoDS::Vertex(aVx);
643       aP2D1=Coord2d(aVxx, aE, aF);
644       return aP2D1;
645     }
646   }
647   return aP2D1;
648 }
649
650 //=======================================================================
651 // function: NbWaysOut
652 // purpose: 
653 //=======================================================================
654 Standard_Integer NbWaysOut(const BOPAlgo_ListOfEdgeInfo& aLEInfo)
655 {
656   Standard_Boolean bIsOut, bIsNotPassed;
657   Standard_Integer iCnt=0;
658   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
659   //
660   anIt.Initialize(aLEInfo);
661   for (; anIt.More(); anIt.Next()) {
662     const BOPAlgo_EdgeInfo& anEI=anIt.Value();
663     //
664     bIsOut=!anEI.IsIn();
665     bIsNotPassed=!anEI.Passed();
666     if (bIsOut && bIsNotPassed) {
667       iCnt++;
668     }
669   }
670   return iCnt;
671 }
672
673 //=======================================================================
674 // function:  AngleIn
675 // purpose:
676 //=======================================================================
677  Standard_Real AngleIn(const TopoDS_Edge& aEIn,
678                        const BOPAlgo_ListOfEdgeInfo& aLEInfo)
679 {
680   Standard_Real anAngleIn;
681   Standard_Boolean anIsIn;
682   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
683
684   anIt.Initialize(aLEInfo);
685   for (; anIt.More(); anIt.Next()) {
686     const BOPAlgo_EdgeInfo& anEdgeInfo=anIt.Value();
687     const TopoDS_Edge& aE=anEdgeInfo.Edge();
688     anIsIn=anEdgeInfo.IsIn();
689     //
690     if (anIsIn && aE==aEIn) {
691       anAngleIn=anEdgeInfo.Angle();
692       return anAngleIn;
693     }
694   }
695   anAngleIn=0.;
696   return anAngleIn;
697 }
698 //=======================================================================
699 // function: GetNextVertex
700 // purpose: 
701 //=======================================================================
702  void GetNextVertex(const TopoDS_Vertex& aV,
703                     const TopoDS_Edge& aE,
704                     TopoDS_Vertex& aV1)
705 {
706   TopoDS_Iterator aIt;
707   //
708   aIt.Initialize(aE);
709   for (; aIt.More(); aIt.Next()) {
710     const TopoDS_Shape& aVx=aIt.Value();
711     if (!aVx.IsEqual(aV)) {
712       aV1=(*(TopoDS_Vertex *)(&aVx)); 
713       return ;
714     }
715   }
716   aV1=aV;
717 }
718 //=======================================================================
719 // function: Angle2D
720 // purpose: 
721 //=======================================================================
722   Standard_Real Angle2D (const TopoDS_Vertex& aV,
723                          const TopoDS_Edge& anEdge,
724                          const TopoDS_Face& myFace,
725                          const GeomAdaptor_Surface& aGAS,
726                          const Standard_Boolean aFlag)
727 {
728   Standard_Real aFirst, aLast, aToler, dt, aTV, aTV1, anAngle, aTX;
729   gp_Pnt2d aPV, aPV1;
730   gp_Vec2d aV2D;
731   Handle(Geom2d_Curve) aC2D;
732   //
733   aTV=BRep_Tool::Parameter (aV, anEdge, myFace);
734   if (Precision::IsInfinite(aTV)) {
735     return 0.;
736   }
737   //
738   BOPTools_AlgoTools2D::CurveOnSurface (anEdge, myFace, aC2D, 
739                                         aFirst, aLast, aToler);
740   dt=2.*Tolerance2D(aV, aGAS);
741   //
742   //for case chl/927/r9
743   aTX=0.05*(aLast - aFirst);//aTX=0.25*(aLast - aFirst);
744   if (aTX < 5.e-5) {
745     aTX = 5.e-5;
746   }
747   if(dt > aTX) {
748     // to save direction of the curve as much as it possible
749     // in the case of big tolerances
750     dt = aTX; 
751   }
752   //
753   GeomAbs_CurveType aType;
754   Geom2dAdaptor_Curve aGAC2D(aC2D);
755   aType=aGAC2D.GetType();
756   if (aType==GeomAbs_BSplineCurve || aType==GeomAbs_BezierCurve) {
757     dt=1.1*dt;
758   }
759   if (fabs (aTV-aFirst) < fabs(aTV - aLast)) {
760     aTV1=aTV + dt;
761   }
762   else {
763     aTV1=aTV - dt;
764   }
765   //
766   aC2D->D0 (aTV1, aPV1);
767   aC2D->D0 (aTV, aPV);
768   //
769   if (aFlag) {//IN
770     gp_Vec2d aV2DIn(aPV1, aPV);
771     aV2D=aV2DIn;
772   }
773   else {
774     gp_Vec2d aV2DOut(aPV, aPV1);
775     aV2D=aV2DOut;
776   }
777   //
778   gp_Dir2d aDir2D(aV2D);
779   anAngle=Angle(aDir2D);
780   //
781   return anAngle;
782 }
783 //=======================================================================
784 // function: Angle
785 // purpose: 
786 //=======================================================================
787 Standard_Real Angle (const gp_Dir2d& aDir2D)
788 {
789   gp_Dir2d aRefDir(1., 0.);
790   Standard_Real anAngle;
791   
792   anAngle = aRefDir.Angle(aDir2D);
793   if (anAngle < 0.)
794     anAngle += M_PI + M_PI;
795   return anAngle;
796 }
797 //=======================================================================
798 // function:  Tolerance2D
799 // purpose:
800 //=======================================================================
801  Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
802                             const GeomAdaptor_Surface& aGAS)         
803 {
804   Standard_Real aTol2D, anUr, aVr, aTolV3D;
805   GeomAbs_SurfaceType aType;
806   //
807   aType=aGAS.GetType();
808   aTolV3D=BRep_Tool::Tolerance(aV);
809
810   anUr=aGAS.UResolution(aTolV3D);
811   aVr =aGAS.VResolution(aTolV3D);
812   aTol2D=(aVr>anUr) ? aVr : anUr;
813   //
814   if (aTol2D < aTolV3D) {
815     aTol2D=aTolV3D;
816   }
817   if (aType==GeomAbs_BSplineSurface) {
818     aTol2D=1.1*aTol2D;
819   }
820   //
821   return aTol2D;
822 }
823
824 //=======================================================================
825 //function : UTolerance2D
826 //purpose  : 
827 //=======================================================================
828 Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
829                             const GeomAdaptor_Surface& aGAS)
830 {
831   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
832   const Standard_Real anUr = aGAS.UResolution(aTolV3D);
833   //
834   return anUr;
835 }
836
837 //=======================================================================
838 //function : VTolerance2D
839 //purpose  : 
840 //=======================================================================
841 Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
842                             const GeomAdaptor_Surface& aGAS)
843 {
844   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
845   const Standard_Real anVr = aGAS.VResolution(aTolV3D);
846   //
847   return anVr;
848 }
849
850 //=======================================================================
851 // function: RecomputeAngles
852 // purpose: 
853 //=======================================================================
854 Standard_Boolean RecomputeAngles(const BOPAlgo_ListOfEdgeInfo& aLEInfo, 
855                                  const TopoDS_Face&            theFace, 
856                                  const gp_Pnt2d&               thePb, 
857                                  const TopoDS_Vertex&          theVb,
858                                  const GeomAdaptor_Surface&    theGAS,
859                                  const TopoDS_Edge&            theEOuta, 
860                                  const Standard_Boolean&       bIsClosed,
861                                  const Standard_Real&          theTol2D,
862                                  BOPCol_SequenceOfReal&        theRecomputedAngles)
863 {
864   Standard_Boolean bRecomputeAngle = Standard_False;
865   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
866   anIt.Initialize(aLEInfo);
867
868   for (; anIt.More(); anIt.Next()) {
869     const BOPAlgo_EdgeInfo& anEI=anIt.Value();
870     const TopoDS_Edge& aE=anEI.Edge();
871     Standard_Boolean anIsOut=!anEI.IsIn();
872     Standard_Boolean anIsNotPassed=!anEI.Passed();
873     
874     if (anIsOut && anIsNotPassed) {
875       theRecomputedAngles.Append(anEI.Angle());
876       Standard_Integer acurindex = theRecomputedAngles.Length();
877
878       Standard_Boolean bRecomputeAngleLocal = Standard_False;
879       TopExp_Explorer anExp1(aE, TopAbs_VERTEX);
880
881       for(; anExp1.More(); anExp1.Next()) {
882         TopExp_Explorer anExp2(theEOuta, TopAbs_VERTEX);
883         Standard_Boolean existsInEdge = Standard_False;
884         
885         for(; anExp2.More(); anExp2.Next()) {
886           if(anExp1.Current().IsSame(anExp2.Current())) {
887             existsInEdge = Standard_True;
888             break;
889           }
890         }
891         
892         if(!existsInEdge) {
893           bRecomputeAngleLocal = Standard_False;
894           break;
895         }
896         bRecomputeAngleLocal = Standard_True;
897       }
898       bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
899
900       if(!bRecomputeAngle) {
901         BOPAlgo_ListIteratorOfListOfEdgeInfo anIt2(aLEInfo);
902         
903         for(; anIt2.More(); anIt2.Next()) {
904           const BOPAlgo_EdgeInfo& anEI2=anIt2.Value();
905           const TopoDS_Edge& aE2=anEI2.Edge();
906           
907           if(aE2.IsSame(aE))
908             continue;
909           Standard_Boolean anIsOut2=!anEI2.IsIn();
910           Standard_Boolean anIsNotPassed2=!anEI2.Passed();
911           
912           if (anIsOut2 && anIsNotPassed2) {
913             anExp1.Init(aE, TopAbs_VERTEX);
914             
915             for(; anExp1.More(); anExp1.Next()) {
916               TopExp_Explorer anExp2(aE2, TopAbs_VERTEX);
917               Standard_Boolean existsInEdge = Standard_False;
918               
919               for(; anExp2.More(); anExp2.Next()) {
920                 if(anExp1.Current().IsSame(anExp2.Current())) {
921                   existsInEdge = Standard_True;
922                   break;
923                 }
924               }
925               
926               if(!existsInEdge) {
927                 bRecomputeAngleLocal = Standard_False;
928                 break;
929               }
930               bRecomputeAngleLocal = Standard_True;
931             }
932             bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
933           }
934         }
935       }
936       
937       bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
938
939       if(bRecomputeAngle) {
940         gp_Pnt2d aP2Dx;
941         //
942         aP2Dx=Coord2dVf(aE, theFace);
943         Standard_Real aD = aP2Dx.Distance(thePb);
944         
945         TopoDS_Vertex aVf;
946         TopExp_Explorer anExp(aE, TopAbs_VERTEX);
947         
948         for (; anExp.More(); anExp.Next()) {
949           const TopoDS_Vertex& aVx=*(TopoDS_Vertex*)(&anExp.Current());
950           if (aVx.Orientation()==TopAbs_FORWARD) {
951             aVf = aVx;
952           }
953         }
954         Standard_Boolean bIgnore = Standard_False;
955         
956         if(bIsClosed || aVf.IsNull() || !aVf.IsSame(theVb)) {
957           bIgnore = (aD > theTol2D);
958         }
959         
960         if(!bIgnore && (theTol2D > M_PI)) {
961           Standard_Real udist = fabs(aP2Dx.X() - thePb.X());
962           Standard_Real vdist = fabs(aP2Dx.Y() - thePb.Y());
963           Standard_Real aTolU = 2. * UTolerance2D(theVb, theGAS);
964           Standard_Real aTolV = 2. * VTolerance2D(theVb, theGAS);
965           
966           if((udist > aTolU) ||
967              (vdist > aTolV)) {
968             bIgnore = Standard_True;
969           }
970         }
971         
972         if((aD > Precision::Confusion()) && !bIgnore) {
973           Standard_Real f1, l1;
974           Handle(Geom2d_Curve) ac1 = BRep_Tool::CurveOnSurface(aE, theFace, f1, l1);
975           
976           Standard_Real aTV1 = BRep_Tool::Parameter (aVf, aE, theFace);
977           Standard_Real aTV12 = 0.;
978           Standard_Real dt1 = (l1 - f1) * 0.5;
979           
980           if (fabs (aTV1-f1) < fabs(aTV1 - l1)) {
981             aTV12 = aTV1 + dt1;
982           }
983           else {
984             aTV12 = aTV1 - dt1;
985           }
986           
987           gp_Pnt2d aPointNew = ac1->Value(aTV12);
988           gp_Vec2d aV2DOut(thePb, aPointNew);
989           
990           gp_Dir2d aDir2D(aV2DOut);
991           Standard_Real anAngleOut = Angle(aDir2D);
992           theRecomputedAngles.ChangeValue(acurindex) = anAngleOut;
993         }
994       }
995     }
996   }
997   return bRecomputeAngle;
998 }