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