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