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