0024624: Lost word in license statement in source files
[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 under
7 // the terms of the GNU Lesser General Public License 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(const TopoDS_Face& myFace,
137                                       BOPTools_ConnexityBlock& aCB)
138 {
139   Standard_Boolean bNothingToDo;
140   Standard_Integer aIx, aNb, i, aCntIn, aCntOut;
141   Standard_Real aAngle;
142   TopAbs_Orientation aOr;
143   TopoDS_Iterator aItS;
144   TopoDS_Vertex aVV;
145   BOPCol_ListIteratorOfListOfShape aIt;
146   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
147   //
148   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo mySmartMap(100);
149   //
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;
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);
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;
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     return;
266   }
267   //
268   // 3. Angles in mySmartMap
269   BRepAdaptor_Surface aBAS(myFace);
270   const GeomAdaptor_Surface& aGAS=aBAS.Surface();
271   //
272   for (i=1; i<=aNb; i++) {
273     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i))); 
274     const BOPAlgo_ListOfEdgeInfo& aLEI= mySmartMap(i);
275
276     aItLEI.Initialize(aLEI);
277     for (; aItLEI.More(); aItLEI.Next()) {
278       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
279       const TopoDS_Edge& aE=aEI.Edge();
280       //
281       aVV=aV;
282       if (aEI.IsIn()) {
283         aVV.Orientation(TopAbs_REVERSED);
284         aAngle=Angle2D (aVV, aE, myFace, aGAS, Standard_True);
285       }
286       else { // OUT
287         aVV.Orientation(TopAbs_FORWARD);
288         aAngle=Angle2D (aVV, aE, myFace, aGAS, Standard_False);
289       }
290       aEI.SetAngle(aAngle);
291     }
292   }// for (i=1; i<=aNb; i++) {
293   //
294   // 4. Do
295   //
296   Standard_Boolean bIsOut, bIsNotPassed;
297   BOPCol_SequenceOfShape aLS, aVertVa;
298   BOPCol_SequenceOfPnt2d aCoordVa;
299   //
300   for (i=1; i<=aNb; ++i) {
301     const TopoDS_Vertex& aVa=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i))); 
302     const BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
303     aItLEI.Initialize(aLEI);
304     for (; aItLEI.More(); aItLEI.Next()) {
305       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
306       const TopoDS_Edge& aEOuta=aEI.Edge();
307       //
308       bIsOut=!aEI.IsIn();
309       bIsNotPassed=!aEI.Passed();
310       if (bIsOut && bIsNotPassed) {
311         //
312         aLS.Clear();
313         aVertVa.Clear();
314         aCoordVa.Clear();
315         //
316         Path(aGAS, myFace, aVa, aEOuta, aEI, aLS, 
317              aVertVa, aCoordVa, aCB, mySmartMap);
318       }
319     }
320   }// for (i=1; i<=aNb; ++i) {
321 }
322 //=======================================================================
323 // function: Path
324 // purpose: 
325 //=======================================================================
326 void Path (const GeomAdaptor_Surface& aGAS,
327            const TopoDS_Face& myFace,
328            const TopoDS_Vertex& aVFirst,
329            const TopoDS_Edge& aEFirst,
330            BOPAlgo_EdgeInfo& aEIFirst,
331            BOPCol_SequenceOfShape& aLS,
332            BOPCol_SequenceOfShape& aVertVa,
333            BOPCol_SequenceOfPnt2d& aCoordVa,
334            BOPTools_ConnexityBlock& aCB,
335            BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap)
336      
337 {
338   Standard_Integer i, j, aNb, aNbj;
339   Standard_Real aTol, anAngleIn, anAngleOut, anAngle, aMinAngle;
340   Standard_Real aTol2D, aTol2D2;
341   Standard_Real aTol2, aD2, aTwoPI;
342   Standard_Boolean anIsSameV2d, anIsSameV, anIsFound, anIsOut, anIsNotPassed;
343   TopoDS_Vertex aVa, aVb;
344   TopoDS_Edge aEOuta;
345   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
346   //
347   aVa = aVFirst;
348   aEOuta = aEFirst;
349   BOPAlgo_EdgeInfo* anEdgeInfo = &aEIFirst;
350   //
351   aTwoPI = M_PI + M_PI;
352   aTol=1.e-7;
353   //
354   // append block
355   //
356   for (;;) {
357     // Do not escape through edge from which you enter 
358     aNb=aLS.Length();
359     if (aNb==1) {
360       const TopoDS_Shape& anEPrev=aLS(aNb);
361       if (anEPrev.IsSame(aEOuta)) {
362         return;
363       }
364     }
365     //
366     anEdgeInfo->SetPassed(Standard_True);
367     aLS.Append(aEOuta);
368     aVertVa.Append(aVa);
369     
370     TopoDS_Vertex pVa=aVa;
371     pVa.Orientation(TopAbs_FORWARD);
372     gp_Pnt2d aPa=Coord2d(pVa, aEOuta, myFace);
373     aCoordVa.Append(aPa);
374     
375     GetNextVertex (pVa, aEOuta, aVb);
376     
377     gp_Pnt2d aPb=Coord2d(aVb, aEOuta, myFace);
378     
379     const BOPAlgo_ListOfEdgeInfo& aLEInfoVb=mySmartMap.FindFromKey(aVb);
380     //
381     aTol=2.*Tolerance2D(aVb, aGAS);
382     aTol2=10.*aTol*aTol;
383     
384     TopoDS_Vertex aV1, aV2;
385     TopExp::Vertices(aEOuta, aV1, aV2);
386     Standard_Boolean bIsClosedEdge = aV1.IsNull() || aV2.IsNull() || aV1.IsSame(aV2);
387     Standard_Boolean bIsDegenerated = BRep_Tool::Degenerated(aEOuta);
388     Standard_Boolean bIsSeam = BRep_Tool::IsClosed(aEOuta, myFace);
389     
390     anIt.Initialize(aLEInfoVb);
391     for (; anIt.More(); anIt.Next()) {
392       const BOPAlgo_EdgeInfo& anEI = anIt.Value();
393       const TopoDS_Edge& aE = anEI.Edge();
394       bIsDegenerated = bIsDegenerated || BRep_Tool::Degenerated(aE);
395       bIsSeam = bIsSeam || BRep_Tool::IsClosed(aE, myFace);
396       aV1.Nullify();
397       aV2.Nullify();
398       TopExp::Vertices(aE, aV1, aV2);
399       bIsClosedEdge = bIsClosedEdge || aV1.IsNull() || aV2.IsNull() || aV1.IsSame(aV2);
400     }
401     //
402     aNb=aLS.Length();
403     if (aNb>0) {
404       //
405       BOPCol_ListOfShape aBuf;
406       //
407       for (i=aNb; i>0; --i) {
408         const TopoDS_Shape& aVPrev=aVertVa(i);
409         const gp_Pnt2d& aPaPrev=aCoordVa(i);
410         const TopoDS_Shape& aEPrev=aLS(i);
411         
412         aBuf.Append(aEPrev);
413         
414         anIsSameV=aVPrev.IsSame(aVb);
415         anIsSameV2d=Standard_False;
416         
417         if (anIsSameV) {
418           anIsSameV2d = Standard_True;
419           //
420           aD2=aPaPrev.SquareDistance(aPb);
421           anIsSameV2d =aD2<aTol2;
422           if(anIsSameV2d && 
423              (bIsDegenerated || bIsSeam || bIsClosedEdge)) {
424             Standard_Real udist = fabs(aPaPrev.X() - aPb.X());
425             Standard_Real vdist = fabs(aPaPrev.Y() - aPb.Y());
426             Standard_Real aTolU = 2. * UTolerance2D(aVb, aGAS);
427             Standard_Real aTolV = 2. * VTolerance2D(aVb, aGAS);
428             //
429             if((udist > aTolU) ||
430                (vdist > aTolV)) {
431               anIsSameV2d = Standard_False;
432             }
433           }
434         }//if (anIsSameV) {
435         //
436         if (anIsSameV && anIsSameV2d) {
437           Standard_Integer iPriz;
438           iPriz=1;
439           if (aBuf.Extent()==2) {
440             if(aBuf.First().IsSame(aBuf.Last())) {
441               iPriz=0;
442             }
443           }
444           if (iPriz) {
445             TopoDS_Wire aW;
446             BOPAlgo_WireSplitter::MakeWire(aBuf, aW);
447             aCB.ChangeLoops().Append(aW);
448           }
449           //
450           aNbj=i-1;
451           if (aNbj<1) {
452             //
453             aLS.Clear();
454             aVertVa.Clear();
455             aCoordVa.Clear();
456             //
457             return;
458           }
459           //
460           BOPCol_SequenceOfShape aLSt, aVertVat;
461           BOPCol_SequenceOfPnt2d aCoordVat;
462           //
463           aVb=(*(TopoDS_Vertex *)(&aVertVa(i))); 
464           //
465           for (j=1; j<=aNbj; ++j) {
466             aLSt.Append(aLS(j));
467             aVertVat.Append(aVertVa(j));
468             aCoordVat.Append(aCoordVa(j));
469           }
470           //
471           aLS.Clear();
472           aVertVa.Clear();
473           aCoordVa.Clear();
474           
475           aLS=aLSt;
476           aVertVa=aVertVat;
477           aCoordVa=aCoordVat;
478           //
479           break;
480         }
481       }
482     }
483     //
484     aTol2D=2.*Tolerance2D(aVb, aGAS);
485     aTol2D2=1000.*aTol2D*aTol2D;//100.*aTol2D*aTol2D;
486     //
487     // anAngleIn in Vb from edge aEOuta
488     const BOPAlgo_ListOfEdgeInfo& aLEInfo=mySmartMap.FindFromKey(aVb);
489     //
490     anAngleIn=AngleIn(aEOuta, aLEInfo);
491     BOPCol_SequenceOfReal aRecomputedAngles;
492     
493     Standard_Boolean bRecomputeAngle = 
494       RecomputeAngles(aLEInfo, myFace, aPb, aVb, aGAS, aEOuta, 
495                       (bIsDegenerated || bIsSeam || bIsClosedEdge),
496                       aTol2D, aRecomputedAngles);
497
498     //
499     // aEOutb
500     BOPAlgo_EdgeInfo *pEdgeInfo=NULL;
501     //
502     aMinAngle=100.;
503     anIsFound=Standard_False;
504     Standard_Integer aCurIndexE = 0;
505     anIt.Initialize(aLEInfo);
506     for (; anIt.More(); anIt.Next()) {
507       BOPAlgo_EdgeInfo& anEI=anIt.ChangeValue();
508       const TopoDS_Edge& aE=anEI.Edge();
509       anIsOut=!anEI.IsIn();
510       anIsNotPassed=!anEI.Passed();
511       
512       if (anIsOut && anIsNotPassed) {
513         aCurIndexE++;
514         //
515         // Is there one way to go out of the vertex 
516         // we have to use it only.
517         Standard_Integer iCnt;
518         iCnt=NbWaysOut (aLEInfo);
519         //
520         if (!iCnt) {
521           // no way to go . (Error)
522           return;
523         }
524         //
525         if (iCnt==1) {
526           // the one and only way to go out .
527           pEdgeInfo=&anEI;
528           anIsFound=Standard_True;
529           break;
530         }
531         //
532         if (aE.IsSame(aEOuta)) {
533           anAngle = aTwoPI;
534         } else {
535           // Look for minimal angle and make the choice.
536           gp_Pnt2d aP2Dx;
537           //
538           aP2Dx=Coord2dVf(aE, myFace);
539           //
540           aD2=aP2Dx.SquareDistance(aPb);
541           if (aD2 > aTol2D2){
542             continue;
543           }
544           //
545           //
546           anAngleOut=anEI.Angle();
547           //
548           if(bRecomputeAngle) {
549             if(aCurIndexE <= aRecomputedAngles.Length()) {
550               anAngleOut = aRecomputedAngles.Value(aCurIndexE);
551             }
552           }
553           anAngle=ClockWiseAngle(anAngleIn, anAngleOut);
554         }
555         if (anAngle < aMinAngle) {
556           aMinAngle=anAngle;
557           pEdgeInfo=&anEI;
558           anIsFound=Standard_True;
559         }
560       }
561     } // for (; anIt.More(); anIt.Next()) 
562     //
563     if (!anIsFound) {
564       // no way to go . (Error)
565       return;
566     }
567     //
568     aVa = aVb;
569     aEOuta = pEdgeInfo->Edge();
570     anEdgeInfo = pEdgeInfo;
571   }
572 }
573 //=======================================================================
574 // function:  ClockWiseAngle
575 // purpose:
576 //=======================================================================
577  Standard_Real ClockWiseAngle(const Standard_Real aAngleIn,
578                               const Standard_Real aAngleOut)
579 {
580   Standard_Real aTwoPi=M_PI+M_PI;
581   Standard_Real dA, A1, A2, AIn, AOut ;
582
583   AIn=aAngleIn;
584   AOut=aAngleOut;
585   if (AIn >= aTwoPi) {
586     AIn=AIn-aTwoPi;
587   }
588   
589   if (AOut >= aTwoPi) {
590     AOut=AOut-aTwoPi;
591   }
592
593   A1=AIn+M_PI;
594   
595   if (A1 >= aTwoPi) {
596     A1=A1-aTwoPi;
597   }
598   
599   A2=AOut;
600   
601   dA=A1-A2;
602   if (dA <= 0.) {
603     dA=aTwoPi+dA;
604   }
605   //xx
606   //else if (dA <= 1.e-15) {
607   else if (dA <= 1.e-14) {
608     dA=aTwoPi;
609   }
610   return dA;
611 }
612 //=======================================================================
613 // function:  Coord2d
614 // purpose:
615 //=======================================================================
616  gp_Pnt2d Coord2d (const TopoDS_Vertex& aV1,
617                    const TopoDS_Edge& aE1,
618                    const TopoDS_Face& aF)
619 {
620   Standard_Real aT, aFirst, aLast;
621   Handle(Geom2d_Curve) aC2D;
622   gp_Pnt2d aP2D1;
623   //
624   aT=BRep_Tool::Parameter (aV1, aE1, aF);
625   aC2D=BRep_Tool::CurveOnSurface(aE1, aF, aFirst, aLast);
626   aC2D->D0 (aT, aP2D1);
627   //
628   return aP2D1;
629 }
630 //=======================================================================
631 // function:  Coord2dVf
632 // purpose:
633 //=======================================================================
634  gp_Pnt2d Coord2dVf (const TopoDS_Edge& aE,
635                      const TopoDS_Face& aF)
636 {
637   Standard_Real aCoord=99.;
638   gp_Pnt2d aP2D1(aCoord, aCoord);
639   TopoDS_Iterator aIt;
640   //
641   aIt.Initialize(aE);
642   for (; aIt.More(); aIt.Next()) {
643     const TopoDS_Shape& aVx=aIt.Value();
644     if (aVx.Orientation()==TopAbs_FORWARD) {
645       
646       const TopoDS_Vertex& aVxx=(*(TopoDS_Vertex *)(&aVx));// TopoDS::Vertex(aVx);
647       aP2D1=Coord2d(aVxx, aE, aF);
648       return aP2D1;
649     }
650   }
651   return aP2D1;
652 }
653
654 //=======================================================================
655 // function: NbWaysOut
656 // purpose: 
657 //=======================================================================
658 Standard_Integer NbWaysOut(const BOPAlgo_ListOfEdgeInfo& aLEInfo)
659 {
660   Standard_Boolean bIsOut, bIsNotPassed;
661   Standard_Integer iCnt=0;
662   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
663   //
664   anIt.Initialize(aLEInfo);
665   for (; anIt.More(); anIt.Next()) {
666     const BOPAlgo_EdgeInfo& anEI=anIt.Value();
667     //
668     bIsOut=!anEI.IsIn();
669     bIsNotPassed=!anEI.Passed();
670     if (bIsOut && bIsNotPassed) {
671       iCnt++;
672     }
673   }
674   return iCnt;
675 }
676
677 //=======================================================================
678 // function:  AngleIn
679 // purpose:
680 //=======================================================================
681  Standard_Real AngleIn(const TopoDS_Edge& aEIn,
682                        const BOPAlgo_ListOfEdgeInfo& aLEInfo)
683 {
684   Standard_Real anAngleIn;
685   Standard_Boolean anIsIn;
686   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
687
688   anIt.Initialize(aLEInfo);
689   for (; anIt.More(); anIt.Next()) {
690     const BOPAlgo_EdgeInfo& anEdgeInfo=anIt.Value();
691     const TopoDS_Edge& aE=anEdgeInfo.Edge();
692     anIsIn=anEdgeInfo.IsIn();
693     //
694     if (anIsIn && aE==aEIn) {
695       anAngleIn=anEdgeInfo.Angle();
696       return anAngleIn;
697     }
698   }
699   anAngleIn=0.;
700   return anAngleIn;
701 }
702 //=======================================================================
703 // function: GetNextVertex
704 // purpose: 
705 //=======================================================================
706  void GetNextVertex(const TopoDS_Vertex& aV,
707                     const TopoDS_Edge& aE,
708                     TopoDS_Vertex& aV1)
709 {
710   TopoDS_Iterator aIt;
711   //
712   aIt.Initialize(aE);
713   for (; aIt.More(); aIt.Next()) {
714     const TopoDS_Shape& aVx=aIt.Value();
715     if (!aVx.IsEqual(aV)) {
716       aV1=(*(TopoDS_Vertex *)(&aVx)); 
717       return ;
718     }
719   }
720   aV1=aV;
721 }
722 //=======================================================================
723 // function: Angle2D
724 // purpose: 
725 //=======================================================================
726   Standard_Real Angle2D (const TopoDS_Vertex& aV,
727                          const TopoDS_Edge& anEdge,
728                          const TopoDS_Face& myFace,
729                          const GeomAdaptor_Surface& aGAS,
730                          const Standard_Boolean aFlag)
731 {
732   Standard_Real aFirst, aLast, aToler, dt, aTV, aTV1, anAngle, aTX;
733   gp_Pnt2d aPV, aPV1;
734   gp_Vec2d aV2D;
735   Handle(Geom2d_Curve) aC2D;
736   //
737   aTV=BRep_Tool::Parameter (aV, anEdge, myFace);
738   if (Precision::IsInfinite(aTV)) {
739     return 0.;
740   }
741   //
742   BOPTools_AlgoTools2D::CurveOnSurface (anEdge, myFace, aC2D, 
743                                         aFirst, aLast, aToler);
744   dt=2.*Tolerance2D(aV, aGAS);
745   //
746   //for case chl/927/r9
747   aTX=0.05*(aLast - aFirst);//aTX=0.25*(aLast - aFirst);
748   if (aTX < 5.e-5) {
749     aTX = 5.e-5;
750   }
751   if(dt > aTX) {
752     // to save direction of the curve as much as it possible
753     // in the case of big tolerances
754     dt = aTX; 
755   }
756   //
757   GeomAbs_CurveType aType;
758   Geom2dAdaptor_Curve aGAC2D(aC2D);
759   aType=aGAC2D.GetType();
760   if (aType==GeomAbs_BSplineCurve || aType==GeomAbs_BezierCurve) {
761     dt=1.1*dt;
762   }
763   if (fabs (aTV-aFirst) < fabs(aTV - aLast)) {
764     aTV1=aTV + dt;
765   }
766   else {
767     aTV1=aTV - dt;
768   }
769   //
770   aC2D->D0 (aTV1, aPV1);
771   aC2D->D0 (aTV, aPV);
772   //
773   if (aFlag) {//IN
774     gp_Vec2d aV2DIn(aPV1, aPV);
775     aV2D=aV2DIn;
776   }
777   else {
778     gp_Vec2d aV2DOut(aPV, aPV1);
779     aV2D=aV2DOut;
780   }
781   //
782   gp_Dir2d aDir2D(aV2D);
783   anAngle=Angle(aDir2D);
784   //
785   return anAngle;
786 }
787 //=======================================================================
788 // function: Angle
789 // purpose: 
790 //=======================================================================
791 Standard_Real Angle (const gp_Dir2d& aDir2D)
792 {
793   gp_Dir2d aRefDir(1., 0.);
794   Standard_Real anAngle;
795   
796   anAngle = aRefDir.Angle(aDir2D);
797   if (anAngle < 0.)
798     anAngle += M_PI + M_PI;
799   return anAngle;
800 }
801 //=======================================================================
802 // function:  Tolerance2D
803 // purpose:
804 //=======================================================================
805  Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
806                             const GeomAdaptor_Surface& aGAS)         
807 {
808   Standard_Real aTol2D, anUr, aVr, aTolV3D;
809   GeomAbs_SurfaceType aType;
810   //
811   aType=aGAS.GetType();
812   aTolV3D=BRep_Tool::Tolerance(aV);
813
814   anUr=aGAS.UResolution(aTolV3D);
815   aVr =aGAS.VResolution(aTolV3D);
816   aTol2D=(aVr>anUr) ? aVr : anUr;
817   //
818   if (aTol2D < aTolV3D) {
819     aTol2D=aTolV3D;
820   }
821   if (aType==GeomAbs_BSplineSurface) {
822     aTol2D=1.1*aTol2D;
823   }
824   //
825   return aTol2D;
826 }
827
828 //=======================================================================
829 //function : UTolerance2D
830 //purpose  : 
831 //=======================================================================
832 Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
833                             const GeomAdaptor_Surface& aGAS)
834 {
835   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
836   const Standard_Real anUr = aGAS.UResolution(aTolV3D);
837   //
838   return anUr;
839 }
840
841 //=======================================================================
842 //function : VTolerance2D
843 //purpose  : 
844 //=======================================================================
845 Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
846                             const GeomAdaptor_Surface& aGAS)
847 {
848   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
849   const Standard_Real anVr = aGAS.VResolution(aTolV3D);
850   //
851   return anVr;
852 }
853
854 //=======================================================================
855 // function: RecomputeAngles
856 // purpose: 
857 //=======================================================================
858 Standard_Boolean RecomputeAngles(const BOPAlgo_ListOfEdgeInfo& aLEInfo, 
859                                  const TopoDS_Face&            theFace, 
860                                  const gp_Pnt2d&               thePb, 
861                                  const TopoDS_Vertex&          theVb,
862                                  const GeomAdaptor_Surface&    theGAS,
863                                  const TopoDS_Edge&            theEOuta, 
864                                  const Standard_Boolean&       bIsClosed,
865                                  const Standard_Real&          theTol2D,
866                                  BOPCol_SequenceOfReal&        theRecomputedAngles)
867 {
868   Standard_Boolean bRecomputeAngle = Standard_False;
869   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
870   anIt.Initialize(aLEInfo);
871
872   for (; anIt.More(); anIt.Next()) {
873     const BOPAlgo_EdgeInfo& anEI=anIt.Value();
874     const TopoDS_Edge& aE=anEI.Edge();
875     Standard_Boolean anIsOut=!anEI.IsIn();
876     Standard_Boolean anIsNotPassed=!anEI.Passed();
877     
878     if (anIsOut && anIsNotPassed) {
879       theRecomputedAngles.Append(anEI.Angle());
880       Standard_Integer acurindex = theRecomputedAngles.Length();
881
882       Standard_Boolean bRecomputeAngleLocal = Standard_False;
883       TopExp_Explorer anExp1(aE, TopAbs_VERTEX);
884
885       for(; anExp1.More(); anExp1.Next()) {
886         TopExp_Explorer anExp2(theEOuta, TopAbs_VERTEX);
887         Standard_Boolean existsInEdge = Standard_False;
888         
889         for(; anExp2.More(); anExp2.Next()) {
890           if(anExp1.Current().IsSame(anExp2.Current())) {
891             existsInEdge = Standard_True;
892             break;
893           }
894         }
895         
896         if(!existsInEdge) {
897           bRecomputeAngleLocal = Standard_False;
898           break;
899         }
900         bRecomputeAngleLocal = Standard_True;
901       }
902       bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
903
904       if(!bRecomputeAngle) {
905         BOPAlgo_ListIteratorOfListOfEdgeInfo anIt2(aLEInfo);
906         
907         for(; anIt2.More(); anIt2.Next()) {
908           const BOPAlgo_EdgeInfo& anEI2=anIt2.Value();
909           const TopoDS_Edge& aE2=anEI2.Edge();
910           
911           if(aE2.IsSame(aE))
912             continue;
913           Standard_Boolean anIsOut2=!anEI2.IsIn();
914           Standard_Boolean anIsNotPassed2=!anEI2.Passed();
915           
916           if (anIsOut2 && anIsNotPassed2) {
917             anExp1.Init(aE, TopAbs_VERTEX);
918             
919             for(; anExp1.More(); anExp1.Next()) {
920               TopExp_Explorer anExp2(aE2, TopAbs_VERTEX);
921               Standard_Boolean existsInEdge = Standard_False;
922               
923               for(; anExp2.More(); anExp2.Next()) {
924                 if(anExp1.Current().IsSame(anExp2.Current())) {
925                   existsInEdge = Standard_True;
926                   break;
927                 }
928               }
929               
930               if(!existsInEdge) {
931                 bRecomputeAngleLocal = Standard_False;
932                 break;
933               }
934               bRecomputeAngleLocal = Standard_True;
935             }
936             bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
937           }
938         }
939       }
940       
941       bRecomputeAngle = bRecomputeAngle || bRecomputeAngleLocal;
942
943       if(bRecomputeAngle) {
944         gp_Pnt2d aP2Dx;
945         //
946         aP2Dx=Coord2dVf(aE, theFace);
947         Standard_Real aD = aP2Dx.Distance(thePb);
948         
949         TopoDS_Vertex aVf;
950         TopExp_Explorer anExp(aE, TopAbs_VERTEX);
951         
952         for (; anExp.More(); anExp.Next()) {
953           const TopoDS_Vertex& aVx=*(TopoDS_Vertex*)(&anExp.Current());
954           if (aVx.Orientation()==TopAbs_FORWARD) {
955             aVf = aVx;
956           }
957         }
958         Standard_Boolean bIgnore = Standard_False;
959         
960         if(bIsClosed || aVf.IsNull() || !aVf.IsSame(theVb)) {
961           bIgnore = (aD > theTol2D);
962         }
963         
964         if(!bIgnore && (theTol2D > M_PI)) {
965           Standard_Real udist = fabs(aP2Dx.X() - thePb.X());
966           Standard_Real vdist = fabs(aP2Dx.Y() - thePb.Y());
967           Standard_Real aTolU = 2. * UTolerance2D(theVb, theGAS);
968           Standard_Real aTolV = 2. * VTolerance2D(theVb, theGAS);
969           
970           if((udist > aTolU) ||
971              (vdist > aTolV)) {
972             bIgnore = Standard_True;
973           }
974         }
975         
976         if((aD > Precision::Confusion()) && !bIgnore) {
977           Standard_Real f1, l1;
978           Handle(Geom2d_Curve) ac1 = BRep_Tool::CurveOnSurface(aE, theFace, f1, l1);
979           
980           Standard_Real aTV1 = BRep_Tool::Parameter (aVf, aE, theFace);
981           Standard_Real aTV12 = 0.;
982           Standard_Real dt1 = (l1 - f1) * 0.5;
983           
984           if (fabs (aTV1-f1) < fabs(aTV1 - l1)) {
985             aTV12 = aTV1 + dt1;
986           }
987           else {
988             aTV12 = aTV1 - dt1;
989           }
990           
991           gp_Pnt2d aPointNew = ac1->Value(aTV12);
992           gp_Vec2d aV2DOut(thePb, aPointNew);
993           
994           gp_Dir2d aDir2D(aV2DOut);
995           Standard_Real anAngleOut = Angle(aDir2D);
996           theRecomputedAngles.ChangeValue(acurindex) = anAngleOut;
997         }
998       }
999     }
1000   }
1001   return bRecomputeAngle;
1002 }