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