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