e1b1bdf133bef720deadfc5943225b9f4d5d50d2
[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 #include <Geom2dLProp_CLProps2d.hxx>
52 typedef NCollection_DataMap \
53   <TopoDS_Shape, Standard_Boolean, TopTools_ShapeMapHasher> \
54   BOPCol_DataMapOfShapeBoolean; 
55 //
56
57 static
58   Standard_Real Angle (const gp_Dir2d& aDir2D);
59
60 static
61   Standard_Real Angle2D (const TopoDS_Vertex& aV,
62                          const TopoDS_Edge& anEdge,
63                          const TopoDS_Face& myFace,
64                          const GeomAdaptor_Surface& aGAS,
65                          const Standard_Boolean aFlag,
66                          const Handle(IntTools_Context)& theContext);
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                     const Handle(IntTools_Context)&);
127
128
129 static
130   void RefineAngles(const TopoDS_Vertex& ,
131                   const TopoDS_Face& ,
132                   const BOPCol_MapOfShape& ,
133                   BOPAlgo_ListOfEdgeInfo&,
134                   const Handle(IntTools_Context)&);
135
136 static
137   Standard_Boolean RefineAngle2D(const TopoDS_Vertex& ,
138                                  const TopoDS_Edge& ,
139                                  const TopoDS_Face& ,
140                                  const Standard_Real ,
141                                  const Standard_Real ,
142                                  const Standard_Real, 
143                                  Standard_Real& ,
144                                  const Handle(IntTools_Context)& );
145
146 //=======================================================================
147 //function : SplitBlock
148 //purpose  : 
149 //=======================================================================
150 void BOPAlgo_WireSplitter::SplitBlock(const TopoDS_Face& myFace,
151                                       BOPTools_ConnexityBlock& aCB,
152                                       const Handle(IntTools_Context)& theContext)
153 {
154   Standard_Boolean bNothingToDo, bIsClosed, bIsIN;
155   Standard_Integer aIx, aNb, i, aCntIn, aCntOut;
156   Standard_Real aAngle;
157   TopAbs_Orientation aOr;
158   TopoDS_Iterator aItS;
159   TopoDS_Vertex aVV;
160   TopoDS_Shape aV1;
161   BOPCol_ListIteratorOfListOfShape aIt;
162   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
163   //
164   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo mySmartMap(100);
165   BOPCol_DataMapOfShapeBoolean aVertMap;
166   //
167   const BOPCol_ListOfShape& myEdges=aCB.Shapes();
168   //
169   // 1.Filling mySmartMap
170   aIt.Initialize(myEdges);
171   for(; aIt.More(); aIt.Next()) {
172     const TopoDS_Edge& aE=(*(TopoDS_Edge *)&aIt.Value());
173     if (!BOPTools_AlgoTools2D::HasCurveOnSurface (aE, myFace)) {
174       continue;
175     }
176     //
177     bIsClosed = BRep_Tool::Degenerated(aE) || 
178                 BRep_Tool::IsClosed(aE, myFace);
179     //
180     aItS.Initialize(aE);
181     for(i = 0; aItS.More(); aItS.Next(), ++i) {
182       const TopoDS_Shape& aV = aItS.Value();
183       aIx = mySmartMap.FindIndex(aV);
184       if (!aIx) {
185         BOPAlgo_ListOfEdgeInfo aLEIx;
186         aIx = mySmartMap.Add(aV, aLEIx);
187       }
188       //
189       BOPAlgo_ListOfEdgeInfo& aLEI = mySmartMap(aIx);
190       BOPAlgo_EdgeInfo aEI;
191       //
192       aEI.SetEdge(aE);
193       aOr = aV.Orientation();
194       bIsIN = (aOr == TopAbs_REVERSED);
195       aEI.SetInFlag(bIsIN);
196       aLEI.Append(aEI);
197       //
198       if (!i) {
199         aV1 = aV;
200       } else {
201         bIsClosed = bIsClosed || aV1.IsSame(aV);
202       }
203       //
204       if (aVertMap.IsBound(aV)) {
205         if (bIsClosed) {
206           aVertMap.ChangeFind(aV) = bIsClosed;
207         }
208       } else {
209         aVertMap.Bind(aV, bIsClosed);
210       }
211     }
212   }
213   //
214   aNb=mySmartMap.Extent();
215   //
216   bNothingToDo=Standard_True;
217   for (i=1; i<=aNb; i++) {
218     aCntIn=0;
219     aCntOut=0;
220     const BOPAlgo_ListOfEdgeInfo& aLEInfo= mySmartMap(i);
221     BOPAlgo_ListIteratorOfListOfEdgeInfo anIt(aLEInfo);
222     for (; anIt.More(); anIt.Next()) {
223       const BOPAlgo_EdgeInfo& aEI=anIt.Value();
224       if (aEI.IsIn()) {
225         aCntIn++;
226       }
227       else {
228         aCntOut++;
229       }
230     }
231     if (aCntIn!=1 || aCntOut!=1) {
232       bNothingToDo=Standard_False;
233       break;
234     }
235   }
236   //
237   // Each vertex has one edge In and one - Out. Good. But it is not enought
238   // to consider that nothing to do with this. We must check edges on TShape
239   // coinsidence. If there are such edges there is something to do with.
240   if (bNothingToDo) {
241     Standard_Integer aNbE, aNbMapEE;
242     Standard_Boolean bFlag;
243     //
244     BOPCol_IndexedDataMapOfShapeListOfShape aMapEE(100);
245     aNbE=myEdges.Extent();
246     //
247     aIt.Initialize(myEdges);
248     for (; aIt.More(); aIt.Next()) {
249       const TopoDS_Shape& aE = aIt.Value();
250       if (!aMapEE.Contains(aE)) {
251         BOPCol_ListOfShape aLEx;
252         aLEx.Append(aE);
253         aMapEE.Add(aE, aLEx);
254       }
255       else {
256         BOPCol_ListOfShape& aLEx=aMapEE.ChangeFromKey(aE);
257         aLEx.Append(aE);
258       }
259     }
260     //
261     bFlag=Standard_True;
262     aNbMapEE=aMapEE.Extent();
263     for (i=1; i<=aNbMapEE; ++i) {
264       const BOPCol_ListOfShape& aLEx=aMapEE(i);
265       aNbE=aLEx.Extent();
266       if (aNbE==1) {// usual case
267         continue;
268       }
269       else if (aNbE==2){
270         const TopoDS_Shape& aE1=aLEx.First();
271         const TopoDS_Shape& aE2=aLEx.Last();
272         if (aE1.IsSame(aE2)) {
273           bFlag=Standard_False;
274           break;
275         }
276       }
277       else {
278         bFlag=Standard_False;
279         break;
280       }
281     }
282     bNothingToDo=bNothingToDo && bFlag;
283   } // if (bNothingToDo) {
284   if (bNothingToDo) {
285     TopoDS_Wire aW;
286     //
287     BOPCol_ListOfShape& aLECB=aCB.ChangeShapes();
288     BOPAlgo_WireSplitter::MakeWire(aLECB, aW);
289     BOPCol_ListOfShape& aLoops=aCB.ChangeLoops();
290     aLoops.Append(aW);
291     //
292     return;
293   }
294   //
295   // 3. Angles in mySmartMap
296   const BRepAdaptor_Surface& aBAS = theContext->SurfaceAdaptor(myFace);
297   const GeomAdaptor_Surface& aGAS=aBAS.Surface();
298   //
299   for (i=1; i<=aNb; i++) {
300     const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&mySmartMap.FindKey(i))); 
301     const BOPAlgo_ListOfEdgeInfo& aLEI= mySmartMap(i);
302     aItLEI.Initialize(aLEI);
303     for (; aItLEI.More(); aItLEI.Next()) {
304       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
305       const TopoDS_Edge& aE=aEI.Edge();
306       //
307       aVV = aV;
308       bIsIN = aEI.IsIn();
309       aOr = bIsIN ? TopAbs_REVERSED : TopAbs_FORWARD;
310       aVV.Orientation(aOr);
311       aAngle = Angle2D(aVV, aE, myFace, aGAS, bIsIN, theContext);
312       aEI.SetAngle(aAngle);
313     }
314   }// for (i=1; i<=aNb; i++) {
315   //
316   //Theme: The treatment p-curves convergent in node.
317   //The refining the angles of p-curves taking into account 
318   //bounding curves if exist. 
319   RefineAngles(myFace, myEdges, mySmartMap, theContext);
320   //
321   // 4. Do
322   //
323   Standard_Boolean bIsOut, bIsNotPassed;
324   BOPCol_SequenceOfShape aLS, aVertVa;
325   BOPCol_SequenceOfPnt2d aCoordVa;
326   //
327   for (i=1; i<=aNb; ++i) {
328     const TopoDS_Vertex& aVa=(*(TopoDS_Vertex *)(&mySmartMap.FindKey(i))); 
329     const BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
330     aItLEI.Initialize(aLEI);
331     for (; aItLEI.More(); aItLEI.Next()) {
332       BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
333       const TopoDS_Edge& aEOuta=aEI.Edge();
334       //
335       bIsOut=!aEI.IsIn();
336       bIsNotPassed=!aEI.Passed();
337       if (bIsOut && bIsNotPassed) {
338         //
339         aLS.Clear();
340         aVertVa.Clear();
341         aCoordVa.Clear();
342         //
343         Path(aGAS, myFace, aVa, aEOuta, aEI, aLS, 
344              aVertVa, aCoordVa, aCB, mySmartMap, aVertMap);
345       }
346     }
347   }// for (i=1; i<=aNb; ++i) {
348 }
349 //=======================================================================
350 // function: Path
351 // purpose: 
352 //=======================================================================
353 void Path (const GeomAdaptor_Surface& aGAS,
354            const TopoDS_Face& myFace,
355            const TopoDS_Vertex& aVFirst,
356            const TopoDS_Edge& aEFirst,
357            BOPAlgo_EdgeInfo& aEIFirst,
358            BOPCol_SequenceOfShape& aLS,
359            BOPCol_SequenceOfShape& aVertVa,
360            BOPCol_SequenceOfPnt2d& aCoordVa,
361            BOPTools_ConnexityBlock& aCB,
362            BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap,
363            BOPCol_DataMapOfShapeBoolean aVertMap)
364      
365 {
366   Standard_Integer i, j, aNb, aNbj;
367   Standard_Real anAngleIn, anAngleOut, anAngle, aMinAngle;
368   Standard_Real aTol2D, aTol2D2, aD2, aTwoPI;
369   Standard_Boolean anIsSameV2d, anIsSameV, anIsFound, anIsOut, anIsNotPassed;
370   Standard_Boolean bIsClosed;
371   TopoDS_Vertex aVa, aVb;
372   TopoDS_Edge aEOuta;
373   BOPAlgo_ListIteratorOfListOfEdgeInfo anIt;
374   Standard_Real eps = Epsilon(1.);
375   //
376   aVa = aVFirst;
377   aEOuta = aEFirst;
378   BOPAlgo_EdgeInfo* anEdgeInfo = &aEIFirst;
379   //
380   aTwoPI = M_PI + M_PI;
381   //
382   // append block
383   //
384   for (;;) {
385     // Do not escape through edge from which you enter 
386     aNb=aLS.Length();
387     if (aNb==1) {
388       const TopoDS_Shape& anEPrev=aLS(aNb);
389       if (anEPrev.IsSame(aEOuta)) {
390         return;
391       }
392     }
393     //
394     anEdgeInfo->SetPassed(Standard_True);
395     aLS.Append(aEOuta);
396     aVertVa.Append(aVa);
397     
398     TopoDS_Vertex pVa=aVa;
399     pVa.Orientation(TopAbs_FORWARD);
400     gp_Pnt2d aPa=Coord2d(pVa, aEOuta, myFace);
401     aCoordVa.Append(aPa);
402     
403     GetNextVertex (pVa, aEOuta, aVb);
404     
405     gp_Pnt2d aPb=Coord2d(aVb, aEOuta, myFace);
406     
407     const BOPAlgo_ListOfEdgeInfo& aLEInfo=mySmartMap.FindFromKey(aVb);
408     //
409     aTol2D = 2.*Tolerance2D(aVb, aGAS);
410     aTol2D2 = aTol2D * aTol2D;
411     //
412     bIsClosed = aVertMap.Find(aVb);
413     {
414       BOPCol_ListOfShape aBuf;
415       //
416       aNb = aLS.Length();
417       for (i = aNb; i>0; --i) {
418         const TopoDS_Shape& aVPrev=aVertVa(i);
419         const gp_Pnt2d& aPaPrev=aCoordVa(i);
420         const TopoDS_Shape& aEPrev=aLS(i);
421         
422         aBuf.Append(aEPrev);
423         
424         anIsSameV = aVPrev.IsSame(aVb);
425         anIsSameV2d = anIsSameV;
426         if (anIsSameV) {
427           if(bIsClosed) {
428             aD2 = aPaPrev.SquareDistance(aPb);
429             anIsSameV2d = aD2 < aTol2D2;
430             if (anIsSameV2d) {
431               Standard_Real udist = fabs(aPaPrev.X() - aPb.X());
432               Standard_Real vdist = fabs(aPaPrev.Y() - aPb.Y());
433               Standard_Real aTolU = 2.*UTolerance2D(aVb, aGAS);
434               Standard_Real aTolV = 2.*VTolerance2D(aVb, aGAS);
435               //
436               if((udist > aTolU) || (vdist > aTolV)) {
437                 anIsSameV2d = Standard_False;
438               }
439             }
440           }
441         }//if (anIsSameV) {
442         //
443         if (anIsSameV && anIsSameV2d) {
444           Standard_Integer iPriz;
445           iPriz=1;
446           if (aBuf.Extent()==2) {
447             if(aBuf.First().IsSame(aBuf.Last())) {
448               iPriz=0;
449             }
450           }
451           if (iPriz) {
452             TopoDS_Wire aW;
453             BOPAlgo_WireSplitter::MakeWire(aBuf, aW);
454             aCB.ChangeLoops().Append(aW);
455           }
456           //
457           aNbj=i-1;
458           if (aNbj<1) {
459             //
460             aLS.Clear();
461             aVertVa.Clear();
462             aCoordVa.Clear();
463             //
464             return;
465           }
466           //
467           BOPCol_SequenceOfShape aLSt, aVertVat;
468           BOPCol_SequenceOfPnt2d aCoordVat;
469           //
470           aVb=(*(TopoDS_Vertex *)(&aVertVa(i))); 
471           //
472           for (j=1; j<=aNbj; ++j) {
473             aLSt.Append(aLS(j));
474             aVertVat.Append(aVertVa(j));
475             aCoordVat.Append(aCoordVa(j));
476           }
477           //
478           aLS.Clear();
479           aVertVa.Clear();
480           aCoordVa.Clear();
481           
482           aLS=aLSt;
483           aVertVa=aVertVat;
484           aCoordVa=aCoordVat;
485           //
486           break;
487         }
488       }
489     }
490     //
491     // aEOutb
492     BOPAlgo_EdgeInfo *pEdgeInfo=NULL;
493     //
494     anAngleIn = AngleIn(aEOuta, aLEInfo);
495     aMinAngle = 100.;
496     anIsFound = Standard_False;
497     Standard_Integer iCnt = NbWaysOut(aLEInfo);
498     Standard_Integer aCurIndexE = 0;
499     anIt.Initialize(aLEInfo);
500     for (; anIt.More(); anIt.Next()) {
501       BOPAlgo_EdgeInfo& anEI=anIt.ChangeValue();
502       const TopoDS_Edge& aE=anEI.Edge();
503       anIsOut=!anEI.IsIn();
504       anIsNotPassed=!anEI.Passed();
505       //
506       if (anIsOut && anIsNotPassed) {
507         aCurIndexE++;
508         //
509         // Is there one way to go out of the vertex 
510         // we have to use it only.
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 - eps) {
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                          const Handle(IntTools_Context)& theContext)
720 {
721   Standard_Real aFirst, aLast, aToler, dt, aTV, aTV1, anAngle, aTX;
722   gp_Pnt2d aPV, aPV1;
723   gp_Vec2d aV2D;
724   Handle(Geom2d_Curve) aC2D;
725   //
726   aTV=BRep_Tool::Parameter (aV, anEdge, myFace);
727   if (Precision::IsInfinite(aTV)) {
728     return 0.;
729   }
730   //
731   BOPTools_AlgoTools2D::CurveOnSurface (anEdge, myFace, aC2D, 
732                                         aFirst, aLast, aToler, theContext);
733   Standard_Real tol2d =2.*Tolerance2D(aV, aGAS);
734   //
735   GeomAbs_CurveType aType;
736   Geom2dAdaptor_Curve aGAC2D(aC2D);
737   //
738   dt = Max(aGAC2D.Resolution(tol2d), Precision::PConfusion());
739   //
740   aType=aGAC2D.GetType();
741   if (aType != GeomAbs_Line ) 
742   {
743     Geom2dLProp_CLProps2d LProp(aC2D,  aTV, 2, Precision::PConfusion());
744     if(LProp.IsTangentDefined())
745     {
746       Standard_Real R = LProp.Curvature();
747       if(R > Precision::PConfusion())
748       {
749         R = 1./R;
750         Standard_Real cosphi = R / (R + tol2d);
751         dt = Max(dt, ACos(cosphi)); //to avoid small dt for big R.
752       }
753     }
754   }
755   //for case chl/927/r9
756   aTX=0.05*(aLast - aFirst);//aTX=0.25*(aLast - aFirst);  
757   if (aTX < 5.e-5) {
758     aTX = 5.e-5;
759   }
760   if(dt > aTX) {
761     // to save direction of the curve as much as it possible
762     // in the case of big tolerances
763     dt = aTX; 
764   }
765
766   if (fabs (aTV-aFirst) < fabs(aTV - aLast)) {
767     aTV1=aTV + dt;
768   }
769   else {
770     aTV1=aTV - dt;
771   }
772   //
773   aGAC2D.D0 (aTV1, aPV1);
774   aGAC2D.D0 (aTV, aPV);
775   //
776   aV2D = bIsIN ? gp_Vec2d(aPV1, aPV) : gp_Vec2d(aPV, aPV1);
777   //
778   gp_Dir2d aDir2D(aV2D);
779   anAngle=Angle(aDir2D);
780   //
781   return anAngle;
782 }
783 //=======================================================================
784 // function: Angle
785 // purpose: 
786 //=======================================================================
787 Standard_Real Angle (const gp_Dir2d& aDir2D)
788 {
789   gp_Dir2d aRefDir(1., 0.);
790   Standard_Real anAngle;
791   
792   anAngle = aRefDir.Angle(aDir2D);
793   if (anAngle < 0.)
794     anAngle += M_PI + M_PI;
795   return anAngle;
796 }
797 //=======================================================================
798 // function:  Tolerance2D
799 // purpose:
800 //=======================================================================
801  Standard_Real Tolerance2D (const TopoDS_Vertex& aV,
802                             const GeomAdaptor_Surface& aGAS)         
803 {
804   Standard_Real aTol2D, anUr, aVr, aTolV3D;
805   GeomAbs_SurfaceType aType;
806   //
807   aType=aGAS.GetType();
808   aTolV3D=BRep_Tool::Tolerance(aV);
809
810   anUr=aGAS.UResolution(aTolV3D);
811   aVr =aGAS.VResolution(aTolV3D);
812   aTol2D=(aVr>anUr) ? aVr : anUr;
813   //
814   if (aTol2D < aTolV3D) {
815     aTol2D=aTolV3D;
816   }
817   if (aType==GeomAbs_BSplineSurface) {
818     aTol2D=1.1*aTol2D;
819   }
820   //
821   return aTol2D;
822 }
823
824 //=======================================================================
825 //function : UTolerance2D
826 //purpose  : 
827 //=======================================================================
828 Standard_Real UTolerance2D (const TopoDS_Vertex& aV,
829                             const GeomAdaptor_Surface& aGAS)
830 {
831   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
832   const Standard_Real anUr = aGAS.UResolution(aTolV3D);
833   //
834   return anUr;
835 }
836
837 //=======================================================================
838 //function : VTolerance2D
839 //purpose  : 
840 //=======================================================================
841 Standard_Real VTolerance2D (const TopoDS_Vertex& aV,
842                             const GeomAdaptor_Surface& aGAS)
843 {
844   const Standard_Real aTolV3D = BRep_Tool::Tolerance(aV);
845   const Standard_Real anVr = aGAS.VResolution(aTolV3D);
846   //
847   return anVr;
848 }
849
850 //=======================================================================
851 //function : RefineAngles
852 //purpose  : 
853 //=======================================================================
854 void RefineAngles(const TopoDS_Face& myFace,
855                   const BOPCol_ListOfShape& myEdges,
856                   BOPAlgo_IndexedDataMapOfShapeListOfEdgeInfo& mySmartMap,
857                   const Handle(IntTools_Context)& theContext)
858 {
859   Standard_Integer aNb, i;
860   BOPCol_IndexedDataMapOfShapeInteger aMSI;
861   BOPCol_MapOfShape aMBE;
862   BOPCol_ListIteratorOfListOfShape aIt;
863   //
864   // 1. Boundary Edges
865   aIt.Initialize(myEdges);
866   for(; aIt.More(); aIt.Next()) {
867     const TopoDS_Shape& aE=aIt.Value();
868     if(aMSI.Contains(aE)) {
869       Standard_Integer& iCnt = aMSI.ChangeFromKey(aE);
870       ++iCnt;
871     }
872     else {
873       Standard_Integer iCnt = 1;
874       aMSI.Add(aE, iCnt);
875     }
876   }
877   //
878   aNb = aMSI.Extent();
879   for (i = 1; i <= aNb; ++i) {
880     Standard_Integer iCnt = aMSI(i);
881     if (iCnt == 1) {
882       const TopoDS_Shape& aE = aMSI.FindKey(i);
883       aMBE.Add(aE);
884     }
885   }
886   //
887   aMSI.Clear();
888   //
889   aNb = mySmartMap.Extent();
890   for (i = 1; i <= aNb; ++i) {
891     const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&mySmartMap.FindKey(i)); 
892     BOPAlgo_ListOfEdgeInfo& aLEI=mySmartMap(i);
893     //
894     RefineAngles(aV, myFace, aMBE, aLEI, theContext);
895   }
896 }
897 //=======================================================================
898 typedef NCollection_DataMap \
899   <TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> \
900    BOPCol_DataMapOfShapeReal; 
901 typedef BOPCol_DataMapOfShapeReal::Iterator \
902   BOPCol_DataMapIteratorOfDataMapOfShapeReal; 
903 //
904 //=======================================================================
905 //function : RefineAngles
906 //purpose  : 
907 //=======================================================================
908 void RefineAngles(const TopoDS_Vertex& aV,
909                   const TopoDS_Face& myFace,
910                   const BOPCol_MapOfShape& aMBE,
911                   BOPAlgo_ListOfEdgeInfo& aLEI,
912                   const Handle(IntTools_Context)& theContext)
913 {
914   Standard_Boolean bIsIn, bIsBoundary, bRefined; 
915   Standard_Integer iCntBnd, iCntInt;
916   Standard_Real aA, aA1, aA2;
917   BOPCol_DataMapOfShapeReal aDMSR;
918   BOPAlgo_ListIteratorOfListOfEdgeInfo aItLEI;
919   //
920   aA1=0.;  // angle of outgoing edge
921   aA2=0.;  // angle of incoming edge
922   iCntBnd=0;
923   iCntInt=0;
924   aItLEI.Initialize(aLEI);
925   for (; aItLEI.More(); aItLEI.Next()) {
926     BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
927     const TopoDS_Edge& aE=aEI.Edge();
928     bIsIn=aEI.IsIn();
929     aA=aEI.Angle();
930     //
931     if (aMBE.Contains(aE)) {
932       ++iCntBnd;
933       if (!bIsIn) {
934         aA1=aA;
935       }
936       else {
937         aA2=aA;
938       }
939     }
940     else {
941       ++iCntInt;
942     }
943   }
944   //
945   if (iCntBnd!=2) {
946     return;
947   }
948   //
949   Standard_Real aDelta = ClockWiseAngle(aA2, aA1);
950   aItLEI.Initialize(aLEI);
951   for (; aItLEI.More(); aItLEI.Next()) {
952     BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
953     const TopoDS_Edge& aE=aEI.Edge();
954     //
955     bIsBoundary=aMBE.Contains(aE);
956     bIsIn=aEI.IsIn();
957     if (bIsBoundary || bIsIn) {
958       continue;
959     }
960     //
961     aA=aEI.Angle();
962     Standard_Real aDA = ClockWiseAngle(aA2, aA);
963     if (aDA < aDelta) {
964       continue;  // already inside
965     }
966     //
967     bRefined=RefineAngle2D(aV, aE, myFace, aA1, aA2, aDelta, aA, theContext);
968     if (bRefined) {
969       aDMSR.Bind(aE, aA);
970     }
971     else if (iCntInt == 2) {
972       aA = (aA <= aA1) ? (aA1 + Precision::Angular()) :
973                          (aA2 - Precision::Angular());
974       aDMSR.Bind(aE, aA);
975     }
976   }
977   
978   if (aDMSR.IsEmpty()) {
979     return;
980   }
981   //
982   // update Angles
983   aItLEI.Initialize(aLEI);
984   for (; aItLEI.More(); aItLEI.Next()) {
985     BOPAlgo_EdgeInfo& aEI=aItLEI.ChangeValue();
986     const TopoDS_Edge& aE=aEI.Edge();
987     //
988     bIsIn=aEI.IsIn();
989     if (!aDMSR.IsBound(aE)) {
990       continue;
991     }
992     //
993     aA=aDMSR.Find(aE);
994     if (bIsIn) {
995       aA=aA+M_PI;
996     }
997     //
998     aEI.SetAngle(aA);
999   }
1000 }
1001 //=======================================================================
1002 //function : RefineAngle2D
1003 //purpose  : 
1004 //=======================================================================
1005 Standard_Boolean RefineAngle2D(const TopoDS_Vertex& aV,
1006                                const TopoDS_Edge& aE,
1007                                const TopoDS_Face& myFace,
1008                                const Standard_Real aA1,
1009                                const Standard_Real aA2,
1010                                const Standard_Real aDelta,
1011                                Standard_Real& aA,
1012                                const Handle(IntTools_Context)& theContext)
1013 {
1014   Standard_Boolean bRet;
1015   Standard_Integer i, j, aNbP;
1016   Standard_Real aTV, aTol, aT1, aT2, dT, aAngle, aT, aTOp;
1017   Standard_Real aTolInt, aAi, aXi, aYi, aT1j, aT2j, aT1max, aT2max, aCf; 
1018   gp_Pnt2d aPV, aP, aP1, aP2;
1019   Handle(Geom2d_Curve) aC2D;
1020   Handle(Geom2d_Line) aLi;
1021   Geom2dAdaptor_Curve aGAC1, aGAC2;
1022   Geom2dInt_GInter aGInter;
1023   IntRes2d_Domain aDomain1, aDomain2;
1024   //
1025   bRet=Standard_True;
1026   aCf=0.01;
1027   aTolInt=1.e-10;  
1028   //
1029   BOPTools_AlgoTools2D::CurveOnSurface(aE, myFace, aC2D, aT1, aT2, aTol, theContext);
1030   aGAC1.Load(aC2D, aT1, aT2);
1031   //
1032   aTV=BRep_Tool::Parameter (aV, aE, myFace);
1033   aGAC1.D0(aTV, aPV);
1034   //
1035   aTOp = (fabs(aTV-aT1) < fabs(aTV-aT2)) ? aT2 : aT1;
1036   //
1037   const Standard_Real MaxDT = 0.3 * (aT2 - aT1);
1038   aGAC1.D0(aT1, aP1);
1039   aGAC1.D0(aT2, aP2);
1040   aDomain1.SetValues(aP1, aT1, aTolInt, aP2, aT2, aTolInt);
1041   //
1042   for (i=0; i<2; ++i) {
1043     aAi=(!i) ? aA1 : (aA2 + M_PI);
1044     aXi=cos(aAi);
1045     aYi=sin(aAi);
1046     gp_Dir2d aDiri(aXi, aYi);
1047     aLi=new Geom2d_Line(aPV, aDiri);
1048     //
1049     aGAC2.Load(aLi);
1050     //
1051     aGInter.Perform(aGAC1, aDomain1, aGAC2, aDomain2, aTolInt, aTolInt);
1052     if (!aGInter.IsDone()) {
1053       continue;
1054     }
1055     //
1056     aNbP = aGInter.NbPoints();
1057     aT1max = aTV;
1058     aT2max = -1.;
1059     for (j = 1; j <= aNbP; ++j) {
1060       const IntRes2d_IntersectionPoint& aIPj = aGInter.Point(j);
1061       aT1j = aIPj.ParamOnFirst();
1062       aT2j = aIPj.ParamOnSecond();
1063       //
1064       if (aT2j > aT2max && Abs(aT1j - aTV) < MaxDT) {
1065         aT2max = aT2j;
1066         aT1max = aT1j;
1067       }
1068     }
1069     //
1070     if (aT2max > 0) {
1071       dT = aTOp - aT1max;
1072       if (Abs(dT) < aTolInt) {
1073         continue;
1074       }
1075       //
1076       aT = aT1max + aCf*dT;
1077       aGAC1.D0(aT, aP);
1078       gp_Vec2d aV2D(aPV, aP);
1079       gp_Dir2d aDir2D(aV2D);
1080       //
1081       aAngle = Angle(aDir2D);
1082       Standard_Real aDA = ClockWiseAngle(aA2, aAngle);
1083       if (aDA < aDelta) {
1084         aA = aAngle;
1085         return bRet;
1086       }
1087     }
1088   }// for (i=0; i<2; ++i) {
1089   return !bRet;
1090 }