0026555: Modeling Algorithms - Exception-safe status reporting in BRepOffset_MakeOffset
[occt.git] / src / BRepOffset / BRepOffset_Inter2d.cxx
1 // Created on: 1996-09-03
2 // Created by: Yves FRICAUD
3 // Copyright (c) 1996-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 //  Modified by skv - Wed Dec 24 18:08:39 2003 OCC4455
18
19 #include <Adaptor2d_HCurve2d.hxx>
20 #include <Adaptor3d_CurveOnSurface.hxx>
21 #include <Adaptor3d_HSurface.hxx>
22 #include <Bnd_Box.hxx>
23 #include <BndLib_Add3dCurve.hxx>
24 #include <BOPTools_AlgoTools.hxx>
25 #include <BRep_Builder.hxx>
26 #include <BRep_CurveRepresentation.hxx>
27 #include <BRep_GCurve.hxx>
28 #include <BRep_ListIteratorOfListOfCurveRepresentation.hxx>
29 #include <BRep_TEdge.hxx>
30 #include <BRep_Tool.hxx>
31 #include <BRepAdaptor_Curve.hxx>
32 #include <BRepAdaptor_Curve2d.hxx>
33 #include <BRepAdaptor_Surface.hxx>
34 #include <BRepAlgo_AsDes.hxx>
35 #include <BRepLib.hxx>
36 #include <BRepLib_MakeVertex.hxx>
37 #include <BRepOffset_Analyse.hxx>
38 #include <BRepOffset_Inter2d.hxx>
39 #include <BRepOffset_Offset.hxx>
40 #include <BRepOffset_Tool.hxx>
41 #include <BRepTools.hxx>
42 #include <BRepTools_WireExplorer.hxx>
43 #include <Geom2d_BezierCurve.hxx>
44 #include <Geom2d_BSplineCurve.hxx>
45 #include <Geom2d_Line.hxx>
46 #include <Geom2d_TrimmedCurve.hxx>
47 #include <Geom2dAdaptor_HCurve.hxx>
48 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
49 #include <Geom2dInt_GInter.hxx>
50 #include <Geom_BSplineCurve.hxx>
51 #include <Geom_BSplineSurface.hxx>
52 #include <Geom_ConicalSurface.hxx>
53 #include <Geom_CylindricalSurface.hxx>
54 #include <Geom_Line.hxx>
55 #include <Geom_Plane.hxx>
56 #include <Geom_TrimmedCurve.hxx>
57 #include <GeomAdaptor_HSurface.hxx>
58 #include <GeomAdaptor_Surface.hxx>
59 #include <GeomAPI_ProjectPointOnCurve.hxx>
60 #include <GeomConvert_CompCurveToBSplineCurve.hxx>
61 #include <GeomLib.hxx>
62 #include <GeomProjLib.hxx>
63 #include <gp_Pnt.hxx>
64 #include <IntRes2d_IntersectionPoint.hxx>
65 #include <IntRes2d_IntersectionSegment.hxx>
66 #include <Precision.hxx>
67 #include <TColGeom2d_SequenceOfCurve.hxx>
68 #include <TColgp_Array1OfPnt2d.hxx>
69 #include <TColgp_SequenceOfPnt.hxx>
70 #include <TopExp.hxx>
71 #include <TopExp_Explorer.hxx>
72 #include <TopoDS.hxx>
73 #include <TopoDS_Edge.hxx>
74 #include <TopoDS_Face.hxx>
75 #include <TopoDS_Iterator.hxx>
76 #include <TopoDS_Vertex.hxx>
77 #include <TopoDS_Wire.hxx>
78 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
79 #include <TopTools_ListIteratorOfListOfShape.hxx>
80 #include <TopTools_ListOfShape.hxx>
81
82 #include <stdio.h>
83 #ifdef DRAW 
84 #include <DBRep.hxx>
85 #include <Geom2d_BoundedCurve.hxx>
86 #include <Geom_BoundedSurface.hxx>
87 #include <Geom_BoundedCurve.hxx>
88 #include <BRep_CurveOnSurface.hxx>
89 #include <Geom_Surface.hxx>
90 Standard_Boolean Inter2dAffichInt2d;
91 static Standard_Integer NbF2d = 0;
92 static Standard_Integer NbE2d = 0;
93 static Standard_Integer NbNewVertices  = 0;
94 #endif
95
96 //=======================================================================
97 //function : CommonVertex
98 //purpose  : 
99 //=======================================================================
100
101 static TopoDS_Vertex CommonVertex(TopoDS_Edge& E1,
102                                   TopoDS_Edge& E2)
103 {
104   TopoDS_Vertex V1[2],V2[2],V;
105   //
106   TopExp::Vertices(E1,V1[0],V1[1], Standard_True);
107   TopExp::Vertices(E2,V2[0],V2[1], Standard_True);
108   // The first edge is the current one, the second edge is the next one.
109   // We check last vertex of the first edge first.
110   if (V1[1].IsSame(V2[0]) || V1[1].IsSame(V2[1])) return V1[1];
111   if (V1[0].IsSame(V2[0]) || V1[0].IsSame(V2[1])) return V1[0];
112   //
113   return V;
114 }
115
116 static Standard_Boolean IsOrientationChanged(TopTools_IndexedMapOfShape& theMap,
117                                              const TopoDS_Edge& theEdge)
118 {
119   Standard_Boolean IsOrChanged = Standard_False;
120   
121   if (!theMap.Contains(theEdge))
122     theMap.Add(theEdge);
123   else
124   {
125     Standard_Integer anInd = theMap.FindIndex(theEdge);
126     const TopoDS_Shape& anEdge = theMap(anInd);
127     if (theEdge.Orientation() != anEdge.Orientation())
128     {
129       theMap.Substitute( anInd, theEdge );
130       IsOrChanged = Standard_True;
131     }
132   }
133
134   return IsOrChanged;
135 }
136
137
138 //=======================================================================
139 //function : Store
140 //purpose  : Store the vertices <theLV> into AsDes for the edge <theEdge>.
141 //           The vertices are added despite of the coincidence with
142 //           already added vertices. When all vertices for all edges
143 //           are added the coinciding chains of vertices should be fused
144 //           using FuseVertices() method.
145 //=======================================================================
146 static void Store(const TopoDS_Edge& theEdge,
147                   const TopTools_ListOfShape& theLV,
148                   const Standard_Real theTol,
149                   const Standard_Boolean IsToUpdate,
150                   Handle(BRepAlgo_AsDes) theAsDes2d,
151                   TopTools_IndexedDataMapOfShapeListOfShape& theDMVV)
152 {
153   const TopTools_ListOfShape& aLVEx = theAsDes2d->Descendant(theEdge);
154   if (!IsToUpdate && aLVEx.IsEmpty()) {
155     if (theLV.Extent()) theAsDes2d->Add(theEdge, theLV);
156     return;
157   }
158   //
159   GeomAPI_ProjectPointOnCurve aProjPC;
160   if (IsToUpdate) {
161     Standard_Real aT1, aT2;
162     const Handle(Geom_Curve)& aC = BRep_Tool::Curve(theEdge, aT1, aT2);
163     aProjPC.Init(aC, aT1, aT2);
164   }
165   //
166   TopTools_MapOfShape aMV;
167   TopTools_ListIteratorOfListOfShape aIt(theLV);
168   for (; aIt.More(); aIt.Next()) {
169     const TopoDS_Vertex& aV = TopoDS::Vertex(aIt.Value());
170     if (!aMV.Add(aV)) {
171       continue;
172     }
173     //
174     const gp_Pnt& aP = BRep_Tool::Pnt(aV);
175     //
176     TopTools_ListOfShape aLVC;
177     TopTools_ListIteratorOfListOfShape aItEx(aLVEx);
178     for (; aItEx.More(); aItEx.Next()) {
179       const TopoDS_Vertex& aVEx = TopoDS::Vertex(aItEx.Value());
180       if (aV.IsSame(aVEx)) {
181         break;
182       }
183       const gp_Pnt& aPEx = BRep_Tool::Pnt(aVEx);
184       if (aP.IsEqual(aPEx, theTol)) {
185         aLVC.Append(aVEx);
186       }
187     }
188     //
189     if (aItEx.More()) {
190       continue;
191     }
192     //
193     if (IsToUpdate) {
194       // get parameter of the vertex on the edge
195       aProjPC.Perform(aP);
196       if (!aProjPC.NbPoints()) {
197         continue;
198       }
199       //
200       if (aProjPC.LowerDistance() > theTol) {
201         continue;
202       }
203       //
204       Standard_Real aT = aProjPC.LowerDistanceParameter();
205       TopoDS_Shape aLocalShape = aV.Oriented(TopAbs_INTERNAL);
206       BRep_Builder().UpdateVertex(TopoDS::Vertex(aLocalShape), aT, theEdge, theTol);
207     }
208     else {
209       BRep_Builder().UpdateVertex(aV, theTol);
210     }
211     //
212     if (aLVC.Extent()) {
213       TopTools_ListIteratorOfListOfShape aItLV(aLVC);
214       for (; aItLV.More(); aItLV.Next()) {
215         const TopoDS_Shape& aVC = aItLV.Value();
216         TopTools_ListOfShape* pLV = theDMVV.ChangeSeek(aVC);
217         if (!pLV) {
218           pLV = &theDMVV(theDMVV.Add(aVC, TopTools_ListOfShape()));
219         }
220         pLV->Append(aV);
221       }
222       //
223       TopTools_ListOfShape* pLV = theDMVV.ChangeSeek(aV);
224       if (!pLV) {
225         pLV = &theDMVV(theDMVV.Add(aV, TopTools_ListOfShape()));
226       }
227       pLV->Append(aLVC);
228     }
229     theAsDes2d->Add(theEdge, aV);
230   }
231 }
232
233 //=======================================================================
234 //function : Store
235 //purpose  : Store the intersection vertices between two edges into AsDes
236 //=======================================================================
237 static void  Store (const TopoDS_Edge& theE1,
238                     const TopoDS_Edge& theE2,
239                     const TopTools_ListOfShape& theLV1,
240                     const TopTools_ListOfShape& theLV2,
241                     const Standard_Real theTol,
242                     Handle(BRepAlgo_AsDes) theAsDes2d,
243                     TopTools_IndexedDataMapOfShapeListOfShape& theDMVV)
244 {
245   for (Standard_Integer i = 0; i < 2; ++i) {
246     const TopoDS_Edge& aE = !i ? theE1 : theE2;
247     const TopTools_ListOfShape& aLV = !i ? theLV1 : theLV2;
248     Store(aE, aLV, theTol, Standard_False, theAsDes2d, theDMVV);
249   }
250 }
251
252 //=======================================================================
253 //function : EdgeInter
254 //purpose  : 
255 //=======================================================================
256
257 static void EdgeInter(const TopoDS_Face&              F,
258                       const BRepAdaptor_Surface&      BAsurf,
259                       const TopoDS_Edge&              E1,
260                       const TopoDS_Edge&              E2,
261                       const Handle(BRepAlgo_AsDes)&   AsDes,
262                       Standard_Real                   Tol,
263                       Standard_Boolean                WithOri,
264                       TopTools_IndexedDataMapOfShapeListOfShape& aDMVV)
265 {
266 #ifdef DRAW
267   if (Inter2dAffichInt2d) {
268     char name[256];
269     sprintf(name,"E2d_%d_%d",NbF2d,NbE2d++);
270     DBRep::Set(name,E1);
271     sprintf(name,"E2d_%d_%d",NbF2d,NbE2d++);
272     DBRep::Set(name,E2);
273   }
274 #endif
275
276   if (E1.IsSame(E2))
277     return;
278
279   Standard_Real f[3],l[3];
280   Standard_Real TolDub = 1.e-7;
281   Standard_Integer i;
282
283   BRep_Tool::Range(E1, f[1], l[1]);
284   BRep_Tool::Range(E2, f[2], l[2]);
285
286   BRepAdaptor_Curve CE1(E1,F);
287   BRepAdaptor_Curve CE2(E2,F);
288
289   TopoDS_Edge                 EI[3]; EI[1] = E1; EI[2] = E2;
290   TopTools_ListOfShape        LV1;   
291   TopTools_ListOfShape        LV2; 
292   BRep_Builder                B;
293
294   TopoDS_Vertex CV;
295   if (!TopExp::CommonVertex( E1, E2, CV ))
296     {
297       BRepLib::BuildCurve3d(E1);
298       BRepLib::BuildCurve3d(E2);
299       
300       Standard_Real TolSum = BRep_Tool::Tolerance(E1) + BRep_Tool::Tolerance(E2);
301       TolSum = Max( TolSum, 1.e-5 );
302
303       TColgp_SequenceOfPnt   ResPoints;
304       TColStd_SequenceOfReal ResParamsOnE1, ResParamsOnE2;
305       gp_Pnt DegPoint;
306       Standard_Boolean WithDegen = BRep_Tool::Degenerated(E1) || BRep_Tool::Degenerated(E2);
307       
308       if (WithDegen)
309         {
310           Standard_Integer ideg = (BRep_Tool::Degenerated(E1))? 1 : 2;
311           TopoDS_Iterator iter( EI[ideg] );
312           if (iter.More())
313             {
314               const TopoDS_Vertex& vdeg = TopoDS::Vertex(iter.Value());
315               DegPoint = BRep_Tool::Pnt(vdeg);
316             }
317           else
318             {
319               BRepAdaptor_Curve CEdeg( EI[ideg], F );
320               DegPoint = CEdeg.Value( CEdeg.FirstParameter() );
321             }
322         }
323         //
324       Handle(Geom2d_Curve) pcurve1 = BRep_Tool::CurveOnSurface(E1, F, f[1], l[1]);
325       Handle(Geom2d_Curve) pcurve2 = BRep_Tool::CurveOnSurface(E2, F, f[2], l[2]);
326       Geom2dAdaptor_Curve GAC1(pcurve1, f[1], l[1]);
327       Geom2dAdaptor_Curve GAC2(pcurve2, f[2], l[2]);
328       Geom2dInt_GInter Inter2d( GAC1, GAC2, TolDub, TolDub );
329       for (i = 1; i <= Inter2d.NbPoints(); i++)
330         {
331           gp_Pnt P3d;
332           if (WithDegen)
333             P3d = DegPoint;
334           else
335             {
336               gp_Pnt2d P2d = Inter2d.Point(i).Value();
337               P3d = BAsurf.Value( P2d.X(), P2d.Y() );
338             }
339           ResPoints.Append( P3d );
340           ResParamsOnE1.Append( Inter2d.Point(i).ParamOnFirst() );
341           ResParamsOnE2.Append( Inter2d.Point(i).ParamOnSecond() );
342         }
343
344       for (i = 1; i <= ResPoints.Length(); i++)
345         {
346           Standard_Real aT1 = ResParamsOnE1(i); //ponc1.Parameter();
347           Standard_Real aT2 = ResParamsOnE2(i); //ponc2.Parameter();
348           if (Precision::IsInfinite(aT1) || Precision::IsInfinite(aT2))
349             {
350 #ifdef OCCT_DEBUG
351               std::cout << "Inter2d : Solution rejected due to infinite parameter"<<std::endl;
352 #endif
353               continue;
354             }
355           
356           gp_Pnt P = ResPoints(i); //ponc1.Value();
357           TopoDS_Vertex aNewVertex = BRepLib_MakeVertex(P);
358           aNewVertex.Orientation(TopAbs_INTERNAL);
359           B.UpdateVertex( aNewVertex, aT1, E1, Tol );
360           B.UpdateVertex( aNewVertex, aT2, E2, Tol );
361           gp_Pnt P1 = CE1.Value(aT1);
362           gp_Pnt P2 = CE2.Value(aT2);
363           Standard_Real dist1, dist2, dist3;
364           dist1 = P1.Distance(P);
365           dist2 = P2.Distance(P);
366           dist3 = P1.Distance(P2);
367           dist1 = Max( dist1, dist2 );
368           dist1 = Max( dist1, dist3 );
369           B.UpdateVertex( aNewVertex, dist1 );
370           
371 #ifdef OCCT_DEBUG
372           if (aT1 < f[1]-Tol  || aT1 > l[1]+Tol)
373             {
374               std::cout << "out of limit"<<std::endl;
375               std::cout<<"aT1 = "<<aT1<<", f[1] = "<<f[1]<<", l[1] = "<<l[1]<<std::endl;
376             }
377           if (aT2 < f[2]-Tol  || aT2 > l[2]+Tol)
378             {
379               std::cout << "out of limit"<<std::endl;
380               std::cout<<"aT2 = "<<aT2<<", f[2] = "<<f[2]<<", l[2] = "<<l[2]<<std::endl;
381             }
382           Standard_Real MilTol2 = 1000*Tol*Tol;
383           if (P1.SquareDistance(P) >  MilTol2 || P2.SquareDistance(P) > MilTol2 || P1.Distance(P2) > 2.*Tol)
384             {
385               std::cout << "Inter2d : Solution rejected "<<std::endl;
386               std::cout<<"P  = "<<P.X()<<" "<<P.Y()<<" "<<P.Z()<<std::endl;
387               std::cout<<"P1 = "<<P1.X()<<" "<<P1.Y()<<" "<<P1.Z()<<std::endl;
388               std::cout<<"P2 = "<<P2.X()<<" "<<P2.Y()<<" "<<P2.Z()<<std::endl;
389               std::cout<<"MaxDist = "<<dist1<<std::endl;
390             }
391 #endif
392           //define the orientation of a new vertex
393           TopAbs_Orientation OO1 = TopAbs_REVERSED;
394           TopAbs_Orientation OO2 = TopAbs_REVERSED;
395           if (WithOri)
396             {
397               BRepAdaptor_Curve2d PCE1( E1, F );
398               BRepAdaptor_Curve2d PCE2( E2, F );
399               gp_Pnt2d P2d1, P2d2;
400               gp_Vec2d V1, V2, V1or, V2or;
401               PCE1.D1( aT1, P2d1, V1 );
402               PCE2.D1( aT2, P2d2, V2 );
403               V1or = V1; V2or = V2;
404               if (E1.Orientation() == TopAbs_REVERSED) V1or.Reverse();
405               if (E2.Orientation() == TopAbs_REVERSED) V2or.Reverse();
406               Standard_Real CrossProd = V2or ^ V1;
407 #ifdef OCCT_DEBUG
408               if (Abs(CrossProd) <= gp::Resolution())
409                 std::cout<<std::endl<<"CrossProd = "<<CrossProd<<std::endl;
410 #endif
411               if (CrossProd > 0.)
412                 OO1 = TopAbs_FORWARD;
413               CrossProd = V1or ^ V2;
414               if (CrossProd > 0.)
415                 OO2 = TopAbs_FORWARD;
416             }
417           LV1.Append( aNewVertex.Oriented(OO1) );
418           LV2.Append( aNewVertex.Oriented(OO2) );
419         }
420     }
421   
422   //----------------------------------
423   // Test at end.
424   //---------------------------------
425   Standard_Real U1,U2;
426   Standard_Real TolConf = Tol;
427   TopoDS_Vertex V1[2],V2[2];
428   TopExp::Vertices(E1,V1[0],V1[1]);
429   TopExp::Vertices(E2,V2[0],V2[1]);
430
431   Standard_Integer j;
432   for (j = 0; j < 2; j++) {
433     if (V1[j].IsNull()) continue;
434     for (Standard_Integer k = 0; k < 2; k++) {
435       if (V2[k].IsNull()) continue;
436       if (V1[j].IsSame(V2[k])) {
437         if (AsDes->HasAscendant(V1[j])) {
438           continue;
439         }
440       }
441       //
442       gp_Pnt P1 = BRep_Tool::Pnt(V1[j]);
443       gp_Pnt P2 = BRep_Tool::Pnt(V2[k]);
444       Standard_Real Dist = P1.Distance(P2); 
445       if (Dist < TolConf) {
446         Standard_Real aTol = 
447           Max(BRep_Tool::Tolerance(V1[j]), BRep_Tool::Tolerance(V2[k]));
448         TopoDS_Vertex V = BRepLib_MakeVertex(P1);
449         U1 = (j == 0) ? f[1] : l[1];
450         U2 = (k == 0) ? f[2] : l[2];
451         //
452         TopoDS_Shape aLocalShape = V.Oriented(TopAbs_INTERNAL);
453         B.UpdateVertex(TopoDS::Vertex(aLocalShape),U1,E1,aTol);
454         B.UpdateVertex(TopoDS::Vertex(aLocalShape),U2,E2,aTol);
455         //
456         LV1.Prepend(V.Oriented(V1[j].Orientation()));
457         LV2.Prepend(V.Oriented(V2[k].Orientation()));
458       }
459     }
460   }
461
462   Standard_Boolean AffichPurge = Standard_False;
463
464   if ( !LV1.IsEmpty()) {
465     //----------------------------------
466     // Remove all vertices.
467     // There can be doubles
468     //----------------------------------
469     TopTools_ListIteratorOfListOfShape it1LV1,it1LV2,it2LV1;
470     gp_Pnt P1,P2;
471     Standard_Boolean Purge = Standard_True;
472
473     while (Purge) {
474       i = 1;
475       Purge = Standard_False;
476       for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2); 
477            it1LV1.More(); it1LV1.Next(),it1LV2.Next()) {
478         j = 1;
479         it2LV1.Initialize(LV1);
480         while (j < i) {      
481           P1 = BRep_Tool::Pnt(TopoDS::Vertex(it1LV1.Value()));
482           P2 = BRep_Tool::Pnt(TopoDS::Vertex(it2LV1.Value()));
483 //  Modified by skv - Thu Jan 22 18:19:04 2004 OCC4455 Begin
484 //           if (P1.IsEqual(P2,10*Tol)) {
485           Standard_Real aTol;
486
487           aTol = Max(BRep_Tool::Tolerance(TopoDS::Vertex(it1LV1.Value())),
488                      BRep_Tool::Tolerance(TopoDS::Vertex(it2LV1.Value())));
489           if (P1.IsEqual(P2,aTol)) {
490 //  Modified by skv - Thu Jan 22 18:19:05 2004 OCC4455 End
491             LV1.Remove(it1LV1);
492             LV2.Remove(it1LV2);
493             if (AffichPurge) std::cout <<"Doubles removed in EdgeInter."<<std::endl;
494             Purge = Standard_True;
495             break;
496           }
497           j++;
498           it2LV1.Next();
499         }
500         if (Purge) break;
501         i++;
502       }
503     }
504     //---------------------------------
505     // Vertex storage in DS.
506     //---------------------------------
507     Standard_Real TolStore = BRep_Tool::Tolerance(E1) + BRep_Tool::Tolerance(E2);
508     TolStore = Max(TolStore, 10.*Tol);
509     Store (E1,E2,LV1,LV2,TolStore,AsDes, aDMVV);
510   }
511 }
512 //=======================================================================
513 //function : EdgeInter
514 //purpose  : 
515 //=======================================================================
516
517 static void RefEdgeInter(const TopoDS_Face&              F,
518                          const BRepAdaptor_Surface&      BAsurf,
519                          const TopoDS_Edge&              E1,
520                          const TopoDS_Edge&              E2,
521                          const Handle(BRepAlgo_AsDes)&   AsDes,
522                          Standard_Real                   Tol,
523                          Standard_Boolean                WithOri,
524                          gp_Pnt&                         Pref,
525                          TopTools_IndexedDataMapOfShapeListOfShape& aDMVV,
526                          Standard_Boolean&               theCoincide)
527 {
528 #ifdef DRAW
529   if (Inter2dAffichInt2d) {
530     char name[256];
531     sprintf(name,"E2d_%d_%d",NbF2d,NbE2d++);
532     DBRep::Set(name,E1);
533     sprintf(name,"E2d_%d_%d",NbF2d,NbE2d++);
534     DBRep::Set(name,E2);
535   }
536 #endif
537   //
538   theCoincide = Standard_False;
539   //
540   if (E1.IsSame(E2))
541     return;
542
543   Standard_Real f[3],l[3];
544   Standard_Real TolDub = 1.e-7;
545   Standard_Integer i;
546
547   //BRep_Tool::Range(E1, f[1], l[1]);
548   //BRep_Tool::Range(E2, f[2], l[2]);
549
550   BRepAdaptor_Curve CE1(E1,F);
551   BRepAdaptor_Curve CE2(E2,F);
552
553   TopoDS_Edge                 EI[3]; EI[1] = E1; EI[2] = E2;
554   TopTools_ListOfShape        LV1;   
555   TopTools_ListOfShape        LV2; 
556   BRep_Builder                B;
557
558   BRepLib::BuildCurve3d(E1);
559   BRepLib::BuildCurve3d(E2);
560
561   Standard_Real TolSum = BRep_Tool::Tolerance(E1) + BRep_Tool::Tolerance(E2);
562   TolSum = Max( TolSum, 1.e-5 );
563
564   TColgp_SequenceOfPnt   ResPoints;
565   TColStd_SequenceOfReal ResParamsOnE1, ResParamsOnE2;
566   gp_Pnt DegPoint;
567   Standard_Boolean WithDegen = BRep_Tool::Degenerated(E1) || BRep_Tool::Degenerated(E2);
568   
569   if (WithDegen)
570     {
571       Standard_Integer ideg = (BRep_Tool::Degenerated(E1))? 1 : 2;
572       TopoDS_Iterator iter( EI[ideg] );
573       if (iter.More())
574         {
575           const TopoDS_Vertex& vdeg = TopoDS::Vertex(iter.Value());
576           DegPoint = BRep_Tool::Pnt(vdeg);
577         }
578       else
579         {
580           BRepAdaptor_Curve CEdeg( EI[ideg], F );
581           DegPoint = CEdeg.Value( CEdeg.FirstParameter() );
582         }
583     }
584   //
585   Handle(Geom2d_Curve) pcurve1 = BRep_Tool::CurveOnSurface(E1, F, f[1], l[1]);
586   Handle(Geom2d_Curve) pcurve2 = BRep_Tool::CurveOnSurface(E2, F, f[2], l[2]);
587   Geom2dAdaptor_Curve GAC1(pcurve1, f[1], l[1]);
588   Geom2dAdaptor_Curve GAC2(pcurve2, f[2], l[2]);
589   if ((GAC1.GetType() == GeomAbs_Line) &&
590       (GAC2.GetType() == GeomAbs_Line))
591   {
592     // Just quickly check if lines coincide
593     if (GAC1.Line().Direction().IsParallel (GAC2.Line().Direction(), 1.e-8))
594     {
595       theCoincide = Standard_True;
596       return;
597     }
598   }
599
600   Geom2dInt_GInter Inter2d( GAC1, GAC2, TolDub, TolDub );
601   //
602   if (!Inter2d.IsDone() || !Inter2d.NbPoints()) {
603     theCoincide = (Inter2d.NbSegments() &&
604                   (GAC1.GetType() == GeomAbs_Line) &&
605                   (GAC2.GetType() == GeomAbs_Line));
606     return;
607   }
608   //
609   for (i = 1; i <= Inter2d.NbPoints(); i++)
610     {
611       gp_Pnt P3d;
612       if (WithDegen)
613         P3d = DegPoint;
614       else
615         {
616           gp_Pnt2d P2d = Inter2d.Point(i).Value();
617           P3d = BAsurf.Value( P2d.X(), P2d.Y() );
618         }
619       ResPoints.Append( P3d );
620       ResParamsOnE1.Append( Inter2d.Point(i).ParamOnFirst() );
621       ResParamsOnE2.Append( Inter2d.Point(i).ParamOnSecond() );
622     }
623   
624   for (i = 1; i <= ResPoints.Length(); i++)
625     {
626       Standard_Real aT1 = ResParamsOnE1(i); //ponc1.Parameter();
627       Standard_Real aT2 = ResParamsOnE2(i); //ponc2.Parameter();
628       if (Precision::IsInfinite(aT1) || Precision::IsInfinite(aT2))
629         {
630 #ifdef OCCT_DEBUG
631           std::cout << "Inter2d : Solution rejected due to infinite parameter"<<std::endl;
632 #endif
633           continue;
634         }
635       
636       gp_Pnt P = ResPoints(i); //ponc1.Value();
637       TopoDS_Vertex aNewVertex = BRepLib_MakeVertex(P);
638       aNewVertex.Orientation(TopAbs_INTERNAL);
639       B.UpdateVertex( aNewVertex, aT1, E1, Tol );
640       B.UpdateVertex( aNewVertex, aT2, E2, Tol );
641       gp_Pnt P1 = CE1.Value(aT1);
642       gp_Pnt P2 = CE2.Value(aT2);
643       Standard_Real dist1, dist2, dist3;
644       dist1 = P1.Distance(P);
645       dist2 = P2.Distance(P);
646       dist3 = P1.Distance(P2);
647       dist1 = Max( dist1, dist2 );
648       dist1 = Max( dist1, dist3 );
649       B.UpdateVertex( aNewVertex, dist1 );
650       
651 #ifdef OCCT_DEBUG
652       if (aT1 < f[1]-Tol  || aT1 > l[1]+Tol)
653         {
654           std::cout << "out of limit"<<std::endl;
655           std::cout<<"aT1 = "<<aT1<<", f[1] = "<<f[1]<<", l[1] = "<<l[1]<<std::endl;
656         }
657       if (aT2 < f[2]-Tol  || aT2 > l[2]+Tol)
658         {
659           std::cout << "out of limit"<<std::endl;
660           std::cout<<"aT2 = "<<aT2<<", f[2] = "<<f[2]<<", l[2] = "<<l[2]<<std::endl;
661         }
662       Standard_Real MilTol2 = 1000*Tol*Tol;
663       if (P1.SquareDistance(P) >  MilTol2 || P2.SquareDistance(P) > MilTol2 || P1.Distance(P2) > 2.*Tol)
664         {
665           std::cout << "Inter2d : Solution rejected"<<std::endl;
666           std::cout<<"P  = "<<P.X()<<" "<<P.Y()<<" "<<P.Z()<<std::endl;
667           std::cout<<"P1 = "<<P1.X()<<" "<<P1.Y()<<" "<<P1.Z()<<std::endl;
668           std::cout<<"P2 = "<<P2.X()<<" "<<P2.Y()<<" "<<P2.Z()<<std::endl;
669           std::cout<<"MaxDist = "<<dist1<<std::endl;
670         }
671 #endif
672       //define the orientation of a new vertex
673       TopAbs_Orientation OO1 = TopAbs_REVERSED;
674       TopAbs_Orientation OO2 = TopAbs_REVERSED;
675       if (WithOri)
676         {
677           BRepAdaptor_Curve2d PCE1( E1, F );
678           BRepAdaptor_Curve2d PCE2( E2, F );
679           gp_Pnt2d P2d1, P2d2;
680           gp_Vec2d V1, V2, V1or, V2or;
681           PCE1.D1( aT1, P2d1, V1 );
682           PCE2.D1( aT2, P2d2, V2 );
683           V1or = V1; V2or = V2;
684           if (E1.Orientation() == TopAbs_REVERSED) V1or.Reverse();
685           if (E2.Orientation() == TopAbs_REVERSED) V2or.Reverse();
686           Standard_Real CrossProd = V2or ^ V1;
687 #ifdef OCCT_DEBUG
688           if (Abs(CrossProd) <= gp::Resolution())
689             std::cout<<std::endl<<"CrossProd = "<<CrossProd<<std::endl;
690 #endif
691           if (CrossProd > 0.)
692             OO1 = TopAbs_FORWARD;
693           CrossProd = V1or ^ V2;
694           if (CrossProd > 0.)
695             OO2 = TopAbs_FORWARD;
696         }
697       LV1.Append( aNewVertex.Oriented(OO1) );
698       LV2.Append( aNewVertex.Oriented(OO2) );
699     }
700   
701   //----------------------------------
702   // Test at end.
703   //---------------------------------
704   Standard_Real U1,U2;
705   Standard_Real TolConf = Tol;
706   TopoDS_Vertex V1[2],V2[2];
707   TopExp::Vertices(E1,V1[0],V1[1]);
708   TopExp::Vertices(E2,V2[0],V2[1]);
709
710   Standard_Integer j;
711   for (j = 0; j < 2; j++) {
712     if (V1[j].IsNull()) continue;
713     for (Standard_Integer k = 0; k < 2; k++) {
714       if (V2[k].IsNull()) continue;
715       if (V1[j].IsSame(V2[k])) {
716         if (AsDes->HasAscendant(V1[j])) {
717           continue;
718         }
719       }
720       //
721       gp_Pnt P1 = BRep_Tool::Pnt(V1[j]);
722       gp_Pnt P2 = BRep_Tool::Pnt(V2[k]);
723       Standard_Real Dist = P1.Distance(P2); 
724       if (Dist < TolConf) {
725         TopoDS_Vertex V = BRepLib_MakeVertex(P1);
726         U1 = (j == 0) ? f[1] : l[1];
727         U2 = (k == 0) ? f[2] : l[2];
728         TopoDS_Shape aLocalShape = V.Oriented(TopAbs_INTERNAL);
729         B.UpdateVertex(TopoDS::Vertex(aLocalShape),U1,E1,Tol);
730         B.UpdateVertex(TopoDS::Vertex(aLocalShape),U2,E2,Tol);
731         LV1.Prepend(V.Oriented(V1[j].Orientation()));
732         LV2.Prepend(V.Oriented(V2[k].Orientation()));
733       }
734     }
735   }
736
737   Standard_Boolean AffichPurge = Standard_False;
738
739   if ( !LV1.IsEmpty()) {
740     //----------------------------------
741     // Remove all vertices.
742     // there can be doubles
743     //----------------------------------
744     TopTools_ListIteratorOfListOfShape it1LV1,it1LV2,it2LV1;
745     gp_Pnt P1,P2;
746     Standard_Boolean Purge = Standard_True;
747
748     while (Purge) {
749       i = 1;
750       Purge = Standard_False;
751       for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2); 
752            it1LV1.More(); it1LV1.Next(),it1LV2.Next()) {
753         j = 1;
754         it2LV1.Initialize(LV1);
755         while (j < i) {      
756           P1 = BRep_Tool::Pnt(TopoDS::Vertex(it1LV1.Value()));
757           P2 = BRep_Tool::Pnt(TopoDS::Vertex(it2LV1.Value()));
758           if (P1.IsEqual(P2,10*Tol)) {
759             LV1.Remove(it1LV1);
760             LV2.Remove(it1LV2);
761             if (AffichPurge) std::cout <<"Doubles removed in EdgeInter."<<std::endl;
762             Purge = Standard_True;
763             break;
764           }
765           j++;
766           it2LV1.Next();
767         }
768         if (Purge) break;
769         i++;
770       }
771     }
772     //---------------------------------
773     // Vertex storage in SD.
774     //---------------------------------
775 ////-----------------------------------------------------
776     if(LV1.Extent() > 1) {
777       //std::cout << "IFV - RefEdgeInter: remove vertex" << std::endl;
778       Standard_Real dmin = RealLast();
779       TopoDS_Vertex Vmin;
780       for (it1LV1.Initialize(LV1); it1LV1.More(); it1LV1.Next()) {
781         gp_Pnt P = BRep_Tool::Pnt(TopoDS::Vertex(it1LV1.Value()));
782         Standard_Real d = P.SquareDistance(Pref);
783         if(d < dmin) {
784           dmin = d;
785           Vmin = TopoDS::Vertex(it1LV1.Value());
786         }
787       }
788       for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2); 
789            it1LV1.More(); it1LV1.Next(),it1LV2.Next()) {
790         if(!Vmin.IsSame(it1LV1.Value())) {
791           LV1.Remove(it1LV1);
792           LV2.Remove(it1LV2);
793           if(!it1LV1.More()) break;
794         }
795       }
796     }
797       
798 ////-----------------------------------------------------
799     Standard_Real TolStore = BRep_Tool::Tolerance(E1) + BRep_Tool::Tolerance(E2);
800     TolStore = Max(TolStore, 10.*Tol);
801     Store (E1,E2,LV1,LV2,TolStore,AsDes, aDMVV);
802   }
803 }
804
805
806 //======================================================================
807 //function : EvaluateMaxSegment
808 //purpose  : return MaxSegment to pass in approximation
809 //======================================================================
810
811 static Standard_Integer evaluateMaxSegment(const Adaptor3d_CurveOnSurface& aCurveOnSurface)
812 {
813   Handle(Adaptor3d_HSurface) aSurf   = aCurveOnSurface.GetSurface();
814   Handle(Adaptor2d_HCurve2d) aCurv2d = aCurveOnSurface.GetCurve();
815
816   Standard_Real aNbSKnots = 0, aNbC2dKnots = 0;
817   
818   if (aSurf->GetType() == GeomAbs_BSplineSurface) {
819     Handle(Geom_BSplineSurface) aBSpline = aSurf->BSpline();
820     aNbSKnots = Max(aBSpline->NbUKnots(), aBSpline->NbVKnots());
821   }
822   if (aCurv2d->GetType() == GeomAbs_BSplineCurve) {
823     aNbC2dKnots = aCurv2d->NbKnots();
824   }
825   Standard_Integer aReturn = (Standard_Integer) (  30 + Max(aNbSKnots, aNbC2dKnots) ) ;
826   return aReturn;
827 }
828
829
830 //=======================================================================
831 //function : ExtendPCurve
832 //purpose  : 
833 //=======================================================================
834
835 static Standard_Boolean ExtendPCurve(const Handle(Geom2d_Curve)& aPCurve,
836                                      const Standard_Real anEf,
837                                      const Standard_Real anEl,
838                                      const Standard_Real a2Offset,
839                                      Handle(Geom2d_Curve)& NewPCurve)
840 {
841   NewPCurve = aPCurve;
842   if (NewPCurve->IsInstance(STANDARD_TYPE(Geom2d_TrimmedCurve)))
843     NewPCurve = Handle(Geom2d_TrimmedCurve)::DownCast (NewPCurve)->BasisCurve();
844   
845   Standard_Real FirstPar = NewPCurve->FirstParameter();
846   Standard_Real LastPar  = NewPCurve->LastParameter();
847
848   if (NewPCurve->IsKind(STANDARD_TYPE(Geom2d_BoundedCurve)) &&
849       (FirstPar > anEf - a2Offset || LastPar < anEl + a2Offset))
850     {
851       if (NewPCurve->IsInstance(STANDARD_TYPE(Geom2d_BezierCurve)))
852         {
853           Handle(Geom2d_BezierCurve) aBezier = Handle(Geom2d_BezierCurve)::DownCast (NewPCurve);
854           if (aBezier->NbPoles() == 2)
855             {
856               TColgp_Array1OfPnt2d thePoles(1,2);
857               aBezier->Poles(thePoles);
858               gp_Vec2d aVec(thePoles(1), thePoles(2));
859               NewPCurve = new Geom2d_Line(thePoles(1), aVec);
860               return Standard_True;
861             }
862         }
863       else if (NewPCurve->IsInstance(STANDARD_TYPE(Geom2d_BSplineCurve)))
864         {
865           Handle(Geom2d_BSplineCurve) aBSpline = Handle(Geom2d_BSplineCurve)::DownCast (NewPCurve);
866           if (aBSpline->NbKnots() == 2 && aBSpline->NbPoles() == 2)
867             {
868               TColgp_Array1OfPnt2d thePoles(1,2);
869               aBSpline->Poles(thePoles);
870               gp_Vec2d aVec(thePoles(1), thePoles(2));
871               NewPCurve = new Geom2d_Line(thePoles(1), aVec);
872               return Standard_True;
873             }
874         }
875     }
876
877   FirstPar = aPCurve->FirstParameter();
878   LastPar  = aPCurve->LastParameter();
879   Handle(Geom2d_TrimmedCurve) aTrCurve = 
880     new Geom2d_TrimmedCurve(aPCurve, FirstPar, LastPar);
881   
882   // The curve is not prolonged on begin or end.
883   // Trying to prolong it adding a segment to its bound.
884   gp_Pnt2d                              aPBnd;
885   gp_Vec2d                              aVBnd;
886   gp_Pnt2d                              aPBeg;
887   gp_Dir2d                              aDBnd;
888   Handle(Geom2d_Line)                   aLin;
889   Handle(Geom2d_TrimmedCurve)           aSegment;
890   Geom2dConvert_CompCurveToBSplineCurve aCompCurve(aTrCurve, Convert_RationalC1);
891   Standard_Real                         aTol = Precision::Confusion();
892   Standard_Real                         aDelta = Max(a2Offset, 1.);
893   
894   if (FirstPar > anEf - a2Offset) {
895     aPCurve->D1(FirstPar, aPBnd, aVBnd);
896     aDBnd.SetXY(aVBnd.XY());
897     aPBeg    = aPBnd.Translated(gp_Vec2d(-aDelta*aDBnd.XY()));
898     aLin     = new Geom2d_Line(aPBeg, aDBnd);
899     aSegment = new Geom2d_TrimmedCurve(aLin, 0, aDelta);
900     
901     if (!aCompCurve.Add(aSegment, aTol))
902       return Standard_False;
903   }
904   
905   if (LastPar < anEl + a2Offset) {
906     aPCurve->D1(LastPar, aPBeg, aVBnd);
907     aDBnd.SetXY(aVBnd.XY());
908     aLin     = new Geom2d_Line(aPBeg, aDBnd);
909     aSegment = new Geom2d_TrimmedCurve(aLin, 0, aDelta);
910     
911     if (!aCompCurve.Add(aSegment, aTol))
912       return Standard_False;
913   }
914   
915   NewPCurve  = aCompCurve.BSplineCurve();
916   return Standard_True;
917 }
918
919 //=======================================================================
920 //function : ExtentEdge
921 //purpose  : 
922 //=======================================================================
923
924 //  Modified by skv - Fri Dec 26 17:00:55 2003 OCC4455 Begin
925 //static void ExtentEdge(const TopoDS_Edge& E,TopoDS_Edge& NE) 
926 Standard_Boolean BRepOffset_Inter2d::ExtentEdge(const TopoDS_Edge& E,TopoDS_Edge& NE, const Standard_Real theOffset)
927 {
928   //BRepLib::BuildCurve3d(E);
929
930   TopoDS_Shape  aLocalShape = E.EmptyCopied();
931   Standard_Real anEf;
932   Standard_Real anEl;
933   Standard_Real a2Offset = 2.*Abs(theOffset);
934   BRep_Builder BB;
935   Standard_Integer i, j;
936
937   BRep_Tool::Range(E, anEf, anEl);
938   NE = TopoDS::Edge(aLocalShape); 
939 //  NE = TopoDS::Edge(E.EmptyCopied()); 
940   // Enough for analytic edges, for general case reconstruct the
941   // geometry of the edge recalculating the intersection of surfaces.
942
943   //BRepLib::BuildCurve3d(E);
944
945   Standard_Integer NbPCurves = 0;
946   Standard_Real FirstParOnPC = RealFirst(), LastParOnPC = RealLast();
947   Handle(Geom2d_Curve) MinPC;
948   Handle(Geom_Surface) MinSurf;
949   TopLoc_Location      MinLoc;
950
951   BRep_ListIteratorOfListOfCurveRepresentation itr( (Handle(BRep_TEdge)::DownCast(NE.TShape()))->ChangeCurves() );
952   for (; itr.More(); itr.Next())
953     {
954       Handle( BRep_CurveRepresentation ) CurveRep = itr.Value();
955       Standard_Real FirstPar, LastPar;
956       if (CurveRep->IsCurveOnSurface())
957         {
958           NbPCurves++;
959           Handle(Geom2d_Curve) theCurve = CurveRep->PCurve();
960           FirstPar = theCurve->FirstParameter();
961           LastPar  = theCurve->LastParameter();
962
963           if (theCurve->IsKind(STANDARD_TYPE(Geom2d_BoundedCurve)) &&
964               (FirstPar > anEf - a2Offset || LastPar < anEl + a2Offset))
965             {
966               Handle(Geom2d_Curve) NewPCurve;
967               if (ExtendPCurve(theCurve, anEf, anEl, a2Offset, NewPCurve))
968                 {
969                   CurveRep->PCurve(NewPCurve);
970                   FirstPar = NewPCurve->FirstParameter();
971                   LastPar  = NewPCurve->LastParameter();
972                   if (CurveRep->IsCurveOnClosedSurface())
973                     {
974                       Handle(Geom2d_Curve) PCurve2 = CurveRep->PCurve2();
975                       if (ExtendPCurve(PCurve2, anEf, anEl, a2Offset, NewPCurve))
976                         CurveRep->PCurve2(NewPCurve);
977                     }
978                 }
979             }
980           else if (theCurve->IsPeriodic())
981             {
982               Standard_Real delta = (theCurve->Period() - (anEl - anEf))*0.5;
983               delta *= 0.95;
984               FirstPar = anEf - delta;
985               LastPar  = anEl + delta;
986             }
987           else if (theCurve->IsClosed())
988             LastPar -= 0.05*(LastPar - FirstPar);
989
990           //check FirstPar and LastPar: the pcurve should be in its surface
991           theCurve = CurveRep->PCurve();
992           Handle(Geom_Surface) theSurf = CurveRep->Surface();
993           Standard_Real Umin, Umax, Vmin, Vmax;
994           theSurf->Bounds(Umin, Umax, Vmin, Vmax);
995           TColGeom2d_SequenceOfCurve BoundLines;
996           if (!Precision::IsInfinite(Vmin))
997             {
998               Handle(Geom2d_Line) aLine = new Geom2d_Line(gp_Pnt2d( 0., Vmin ),
999                                                           gp_Dir2d( 1., 0. ));
1000               BoundLines.Append(aLine);
1001             }
1002           if (!Precision::IsInfinite(Umin))
1003             {
1004               Handle(Geom2d_Line) aLine = new Geom2d_Line(gp_Pnt2d( Umin, 0. ),
1005                                                           gp_Dir2d( 0., 1. ));
1006               BoundLines.Append(aLine);
1007             }
1008           if (!Precision::IsInfinite(Vmax))
1009             {
1010               Handle(Geom2d_Line) aLine = new Geom2d_Line(gp_Pnt2d( 0., Vmax ),
1011                                                           gp_Dir2d( 1., 0. ));
1012               BoundLines.Append(aLine);
1013             }
1014           if (!Precision::IsInfinite(Umax))
1015             {
1016               Handle(Geom2d_Line) aLine = new Geom2d_Line(gp_Pnt2d( Umax, 0. ),
1017                                                           gp_Dir2d( 0., 1. ));
1018               BoundLines.Append(aLine);
1019             }
1020
1021           TColStd_SequenceOfReal params;
1022           Geom2dInt_GInter IntCC;
1023           Geom2dAdaptor_Curve GAcurve(theCurve);
1024           for (i = 1; i <= BoundLines.Length(); i++)
1025             {
1026               Geom2dAdaptor_Curve GAline( BoundLines(i) );
1027               IntCC.Perform( GAcurve, GAline, Precision::PConfusion(), Precision::PConfusion());
1028               if (IntCC.IsDone())
1029                 {
1030                   for (j = 1; j <= IntCC.NbPoints(); j++)
1031                     {
1032                       const IntRes2d_IntersectionPoint& ip = IntCC.Point(j);
1033                       gp_Pnt2d aPoint = ip.Value();
1034                       if (aPoint.X() >= Umin && aPoint.X() <= Umax &&
1035                           aPoint.Y() >= Vmin && aPoint.Y() <= Vmax)
1036                         params.Append( ip.ParamOnFirst() );
1037                     }
1038                   for (j = 1; j <= IntCC.NbSegments(); j++)
1039                     {
1040                       const IntRes2d_IntersectionSegment& is = IntCC.Segment(j);
1041                       if (is.HasFirstPoint())
1042                         {
1043                           const IntRes2d_IntersectionPoint& ip = is.FirstPoint();
1044                           gp_Pnt2d aPoint = ip.Value();
1045                           if (aPoint.X() >= Umin && aPoint.X() <= Umax &&
1046                               aPoint.Y() >= Vmin && aPoint.Y() <= Vmax)
1047                             params.Append( ip.ParamOnFirst() );
1048                         }
1049                       if (is.HasLastPoint())
1050                         {
1051                           const IntRes2d_IntersectionPoint& ip = is.LastPoint();
1052                           gp_Pnt2d aPoint = ip.Value();
1053                           if (aPoint.X() >= Umin && aPoint.X() <= Umax &&
1054                               aPoint.Y() >= Vmin && aPoint.Y() <= Vmax)
1055                             params.Append( ip.ParamOnFirst() );
1056                         }
1057                     }
1058                 }
1059             }
1060           if (!params.IsEmpty())
1061             {
1062               if (params.Length() == 1)
1063                 {
1064                   gp_Pnt2d PntFirst = theCurve->Value(FirstPar);
1065                   if (PntFirst.X() >= Umin && PntFirst.X() <= Umax &&
1066                       PntFirst.Y() >= Vmin && PntFirst.Y() <= Vmax)
1067                     {
1068                       if (LastPar > params(1))
1069                         LastPar = params(1);
1070                     }
1071                   else if (FirstPar < params(1))
1072                     FirstPar = params(1);
1073                 }
1074               else
1075                 {
1076                   Standard_Real fpar = RealLast(), lpar = RealFirst();
1077                   for (i = 1; i <= params.Length(); i++)
1078                     {
1079                       if (params(i) < fpar)
1080                         fpar = params(i);
1081                       if (params(i) > lpar)
1082                         lpar = params(i);
1083                     }
1084                   if (FirstPar < fpar)
1085                     FirstPar = fpar;
1086                   if (LastPar > lpar)
1087                     LastPar = lpar;
1088                 }
1089             }
1090           //// end of check ////
1091           (Handle(BRep_GCurve)::DownCast(CurveRep))->SetRange( FirstPar, LastPar );
1092           //gp_Pnt2d Pfirst = theCurve->Value(FirstPar);
1093           //gp_Pnt2d Plast  = theCurve->Value(LastPar);
1094           //(Handle(BRep_CurveOnSurface)::DownCast(CurveRep))->SetUVPoints( Pfirst, Plast );
1095
1096           //update FirstParOnPC and LastParOnPC
1097           if (FirstPar > FirstParOnPC)
1098             {
1099               FirstParOnPC = FirstPar;
1100               MinPC   = theCurve;
1101               MinSurf = theSurf;
1102               MinLoc  = CurveRep->Location();
1103             }
1104           if (LastPar  < LastParOnPC)
1105             {
1106               LastParOnPC  = LastPar;
1107               MinPC   = theCurve;
1108               MinSurf = theSurf;
1109               MinLoc  = CurveRep->Location();
1110             }
1111         }
1112     }
1113
1114   Standard_Real f, l;
1115   Handle(Geom_Curve) C3d = BRep_Tool::Curve( NE, f, l );
1116   if (NbPCurves)
1117     {
1118       MinLoc = E.Location() * MinLoc;
1119       if (!C3d.IsNull())
1120         {
1121           if (MinPC->IsClosed())
1122             {
1123               f = FirstParOnPC;
1124               l = LastParOnPC;
1125             }
1126           else if (C3d->IsPeriodic())
1127             {
1128               Standard_Real delta = (C3d->Period() - (l - f))*0.5;
1129               delta *= 0.95;
1130               f -= delta;
1131               l += delta;
1132             }
1133           else if (C3d->IsClosed())
1134             l -= 0.05*(l - f);
1135           else
1136             {
1137               f = FirstParOnPC;
1138               l = LastParOnPC;
1139               GeomAPI_ProjectPointOnCurve Projector;
1140               if (!Precision::IsInfinite(FirstParOnPC))
1141                 {
1142                   gp_Pnt2d P2d1 = MinPC->Value(FirstParOnPC);
1143                   gp_Pnt P1 = MinSurf->Value( P2d1.X(), P2d1.Y() );
1144                   P1.Transform(MinLoc.Transformation());
1145                   Projector.Init( P1, C3d );
1146                   if (Projector.NbPoints() > 0)
1147                     f = Projector.LowerDistanceParameter();
1148 #ifdef OCCT_DEBUG
1149                   else
1150                     std::cout<<"ProjectPointOnCurve not done"<<std::endl;
1151 #endif
1152                 }
1153               if (!Precision::IsInfinite(LastParOnPC))
1154                 {
1155                   gp_Pnt2d P2d2 = MinPC->Value(LastParOnPC);
1156                   gp_Pnt P2 = MinSurf->Value( P2d2.X(), P2d2.Y() );
1157                   P2.Transform(MinLoc.Transformation());
1158                   Projector.Init( P2, C3d );
1159                   if (Projector.NbPoints() > 0)
1160                     l = Projector.LowerDistanceParameter();
1161 #ifdef OCCT_DEBUG
1162                   else
1163                     std::cout<<"ProjectPointOnCurve not done"<<std::endl;
1164 #endif
1165                 }
1166             }
1167           BB.Range( NE, f, l );
1168           if (!Precision::IsInfinite(f) && !Precision::IsInfinite(l))
1169             BRepLib::SameParameter( NE, Precision::Confusion(), Standard_True );
1170         }
1171       else if (!BRep_Tool::Degenerated(E)) //no 3d curve
1172         {
1173           MinSurf = Handle(Geom_Surface)::DownCast
1174             (MinSurf->Transformed(MinLoc.Transformation()));
1175           Standard_Real max_deviation = 0.;
1176           if (Precision::IsInfinite(FirstParOnPC) || Precision::IsInfinite(LastParOnPC))
1177             {
1178               if (MinPC->IsInstance(STANDARD_TYPE(Geom2d_Line)))
1179                 {
1180                   Standard_Boolean IsLine = Standard_False;
1181                   if (MinSurf->IsInstance(STANDARD_TYPE(Geom_Plane)))
1182                     IsLine = Standard_True;
1183                   else if (MinSurf->IsInstance(STANDARD_TYPE(Geom_CylindricalSurface)) ||
1184                            MinSurf->IsInstance(STANDARD_TYPE(Geom_ConicalSurface)))
1185                     {
1186                       Handle(Geom2d_Line) theLine = Handle(Geom2d_Line)::DownCast (MinPC);
1187                       gp_Dir2d LineDir = theLine->Direction();
1188                       if (LineDir.IsParallel( gp::DY2d(), Precision::Angular() ))
1189                         IsLine = Standard_True;
1190                     }
1191                   if (IsLine)
1192                     {
1193                       gp_Pnt2d P2d1 = MinPC->Value(0.), P2d2 = MinPC->Value(1.);
1194                       gp_Pnt P1 = MinSurf->Value(P2d1.X(), P2d1.Y());
1195                       gp_Pnt P2 = MinSurf->Value(P2d2.X(), P2d2.Y());
1196                       gp_Vec aVec(P1, P2);
1197                       C3d = new Geom_Line( P1, aVec );
1198                     }
1199                 }
1200             }
1201           else
1202             {
1203               Geom2dAdaptor_Curve AC2d( MinPC, FirstParOnPC, LastParOnPC );
1204               GeomAdaptor_Surface GAsurf( MinSurf );
1205               Handle(Geom2dAdaptor_HCurve) HC2d  = new Geom2dAdaptor_HCurve( AC2d );
1206               Handle(GeomAdaptor_HSurface) HSurf = new GeomAdaptor_HSurface( GAsurf );
1207               Adaptor3d_CurveOnSurface ConS( HC2d, HSurf );
1208               Standard_Real /*max_deviation,*/ average_deviation;
1209               GeomAbs_Shape Continuity = GeomAbs_C1;
1210               Standard_Integer MaxDegree = 14;
1211               Standard_Integer MaxSegment = evaluateMaxSegment(ConS);
1212               GeomLib::BuildCurve3d(Precision::Confusion(),
1213                                     ConS, FirstParOnPC, LastParOnPC,
1214                                     C3d, max_deviation, average_deviation,
1215                                     Continuity, MaxDegree, MaxSegment);
1216             }
1217           BB.UpdateEdge( NE, C3d, max_deviation );
1218           //BB.Range( NE, FirstParOnPC, LastParOnPC );
1219           Standard_Boolean ProjectionSuccess = Standard_True;
1220           if (NbPCurves > 1)
1221             //BRepLib::SameParameter( NE, Precision::Confusion(), Standard_True );
1222             for (itr.Initialize((Handle(BRep_TEdge)::DownCast(NE.TShape()))->ChangeCurves());
1223                  itr.More();
1224                  itr.Next())
1225               {
1226                 Handle( BRep_CurveRepresentation ) CurveRep = itr.Value();
1227                 Standard_Real FirstPar, LastPar;
1228                 if (CurveRep->IsCurveOnSurface())
1229                   {
1230                     Handle(Geom2d_Curve) theCurve = CurveRep->PCurve();
1231                     Handle(Geom_Surface) theSurf  = CurveRep->Surface();
1232                     TopLoc_Location      theLoc   = CurveRep->Location();
1233                     if (theCurve == MinPC && theSurf == MinSurf && theLoc == MinLoc)
1234                       continue;
1235                     FirstPar = (Handle(BRep_GCurve)::DownCast(CurveRep))->First();
1236                     LastPar  = (Handle(BRep_GCurve)::DownCast(CurveRep))->Last();
1237                     if (Abs(FirstPar - FirstParOnPC) > Precision::PConfusion() ||
1238                         Abs(LastPar  - LastParOnPC)  > Precision::PConfusion())
1239                       {
1240                         theLoc = E.Location() * theLoc;
1241                         theSurf = Handle(Geom_Surface)::DownCast
1242                           (theSurf->Transformed(theLoc.Transformation()));
1243
1244                         if (theCurve->IsInstance(STANDARD_TYPE(Geom2d_Line)) &&
1245                             theSurf->IsKind(STANDARD_TYPE(Geom_BoundedSurface)))
1246                           {
1247                             gp_Dir2d theDir = Handle(Geom2d_Line)::DownCast (theCurve)->Direction();
1248                             if (theDir.IsParallel(gp::DX2d(), Precision::Angular()) ||
1249                                 theDir.IsParallel(gp::DY2d(), Precision::Angular()))
1250                               {
1251                                 Standard_Real U1, U2, V1, V2;
1252                                 theSurf->Bounds(U1, U2, V1, V2);
1253                                 gp_Pnt2d Origin = Handle(Geom2d_Line)::DownCast (theCurve)->Location();
1254                                 if (Abs(Origin.X()-U1) <= Precision::Confusion() ||
1255                                     Abs(Origin.X()-U2) <= Precision::Confusion() ||
1256                                     Abs(Origin.Y()-V1) <= Precision::Confusion() ||
1257                                     Abs(Origin.Y()-V2) <= Precision::Confusion())
1258                                   {
1259                                     BRepLib::SameParameter( NE, Precision::Confusion(), Standard_True );
1260                                     break;
1261                                   }
1262                               }
1263                           }
1264                         if (!C3d.IsNull() && FirstParOnPC < LastParOnPC)
1265                         {
1266                           Handle(Geom2d_Curve) ProjPCurve =
1267                             GeomProjLib::Curve2d(C3d, FirstParOnPC, LastParOnPC, theSurf);
1268                           if (ProjPCurve.IsNull())
1269                             ProjectionSuccess = Standard_False;
1270                           else
1271                             CurveRep->PCurve(ProjPCurve);
1272                         }
1273                         else
1274                         {
1275                           return Standard_False;
1276                         }
1277                       }
1278                   }
1279               }
1280           if (ProjectionSuccess)
1281             BB.Range( NE, FirstParOnPC, LastParOnPC );
1282           else
1283             {
1284               BB.Range( NE, FirstParOnPC, LastParOnPC, Standard_True );
1285               BRepLib::SameParameter( NE, Precision::Confusion(), Standard_True );
1286             }
1287         }
1288     }
1289   else //no pcurves
1290     {
1291       Standard_Real FirstPar = C3d->FirstParameter();
1292       Standard_Real LastPar  = C3d->LastParameter();
1293       
1294       if (C3d->IsKind(STANDARD_TYPE(Geom_BoundedCurve)) &&
1295           (FirstPar > anEf - a2Offset || LastPar < anEl + a2Offset))
1296         {
1297           Handle(Geom_TrimmedCurve) aTrCurve = 
1298             new Geom_TrimmedCurve(C3d, FirstPar, LastPar);
1299           
1300           // The curve is not prolonged on begin or end.
1301           // Trying to prolong it adding a segment to its bound.
1302           gp_Pnt                              aPBnd;
1303           gp_Vec                              aVBnd;
1304           gp_Pnt                              aPBeg;
1305           gp_Dir                              aDBnd;
1306           Handle(Geom_Line)                   aLin;
1307           Handle(Geom_TrimmedCurve)           aSegment;
1308           GeomConvert_CompCurveToBSplineCurve aCompCurve(aTrCurve, Convert_RationalC1);
1309           Standard_Real                       aTol = Precision::Confusion();
1310           Standard_Real                       aDelta = Max(a2Offset, 1.);
1311           
1312           if (FirstPar > anEf - a2Offset) {
1313             C3d->D1(FirstPar, aPBnd, aVBnd);
1314             aDBnd.SetXYZ(aVBnd.XYZ());
1315             aPBeg    = aPBnd.Translated(gp_Vec(-aDelta*aDBnd.XYZ()));
1316             aLin     = new Geom_Line(aPBeg, aDBnd);
1317             aSegment = new Geom_TrimmedCurve(aLin, 0, aDelta);
1318             
1319             if (!aCompCurve.Add(aSegment, aTol))
1320               return Standard_True;
1321           }
1322           
1323           if (LastPar < anEl + a2Offset) {
1324             C3d->D1(LastPar, aPBeg, aVBnd);
1325             aDBnd.SetXYZ(aVBnd.XYZ());
1326             aLin     = new Geom_Line(aPBeg, aDBnd);
1327             aSegment = new Geom_TrimmedCurve(aLin, 0, aDelta);
1328             
1329             if (!aCompCurve.Add(aSegment, aTol))
1330               return Standard_True;
1331           }
1332           
1333           C3d = aCompCurve.BSplineCurve();
1334           FirstPar = C3d->FirstParameter();
1335           LastPar  = C3d->LastParameter();
1336           BB.UpdateEdge(NE, C3d, Precision::Confusion());
1337         }
1338       else if (C3d->IsPeriodic())
1339         {
1340           Standard_Real delta = (C3d->Period() - (anEl - anEf))*0.5;
1341           delta *= 0.95;
1342           FirstPar = anEf - delta;
1343           LastPar  = anEl + delta;
1344         }
1345       else if (C3d->IsClosed())
1346         LastPar -= 0.05*(LastPar - FirstPar);
1347       
1348       BB.Range( NE, FirstPar, LastPar );
1349     }
1350   return Standard_True;
1351 }
1352 //  Modified by skv - Fri Dec 26 17:00:57 2003 OCC4455 End
1353
1354
1355 //=======================================================================
1356 //function : UpdateVertex
1357 //purpose  : 
1358 //=======================================================================
1359
1360 static Standard_Boolean  UpdateVertex(TopoDS_Vertex V,
1361                                       TopoDS_Edge&  OE,
1362                                       TopoDS_Edge&  NE,
1363                                       Standard_Real TolConf)
1364 {
1365   BRepAdaptor_Curve OC(OE);
1366   BRepAdaptor_Curve NC(NE);
1367   Standard_Real Of = OC.FirstParameter(); Standard_Real Ol = OC.LastParameter();
1368   Standard_Real Nf = NC.FirstParameter(); Standard_Real Nl = NC.LastParameter();
1369   Standard_Real U = 0.;
1370   Standard_Real ParTol = Precision::PConfusion();
1371   gp_Pnt           P  = BRep_Tool::Pnt(V);
1372   Standard_Boolean OK = Standard_False;
1373
1374   if (P.Distance(OC.Value(Of)) < TolConf) {
1375     if (Of >= Nf + ParTol && Of <= Nl + ParTol  && P.Distance(NC.Value(Of)) < TolConf) {
1376       OK = Standard_True;
1377       U    = Of;
1378     }
1379   }
1380   if (P.Distance(OC.Value(Ol)) < TolConf) {
1381     if (Ol >= Nf + ParTol && Ol <= Nl + ParTol  && P.Distance(NC.Value(Ol)) < TolConf) {
1382       OK = Standard_True;
1383       U    = Ol;
1384     }
1385   }
1386   if (OK) {
1387     BRep_Builder B;
1388     TopoDS_Shape aLocalShape = NE.Oriented(TopAbs_FORWARD);
1389     TopoDS_Edge EE = TopoDS::Edge(aLocalShape);
1390 //    TopoDS_Edge EE = TopoDS::Edge(NE.Oriented(TopAbs_FORWARD));
1391     aLocalShape = V.Oriented(TopAbs_INTERNAL);
1392     B.UpdateVertex(TopoDS::Vertex(aLocalShape),
1393                    U,NE,BRep_Tool::Tolerance(NE));
1394 //    B.UpdateVertex(TopoDS::Vertex(V.Oriented(TopAbs_INTERNAL)),
1395 //                   U,NE,BRep_Tool::Tolerance(NE));
1396   }
1397   return OK;  
1398 }
1399
1400 //=======================================================================
1401 //function : Compute
1402 //purpose  : 
1403 //=======================================================================
1404
1405 void BRepOffset_Inter2d::Compute (const Handle(BRepAlgo_AsDes)&     AsDes,
1406                                   const TopoDS_Face&                F,
1407                                   const TopTools_IndexedMapOfShape& NewEdges,
1408                                   const Standard_Real               Tol,
1409                                   TopTools_IndexedDataMapOfShapeListOfShape& theDMVV)
1410 {
1411 #ifdef DRAW
1412   NbF2d++;
1413   NbE2d = 0;
1414 #endif 
1415
1416   //Do not intersect the edges of face
1417   TopTools_MapOfShape EdgesOfFace;
1418   TopExp_Explorer Explo( F, TopAbs_EDGE );
1419   for (; Explo.More(); Explo.Next())
1420     EdgesOfFace.Add( Explo.Current() );
1421
1422   //-----------------------------------------------------------
1423   // calculate intersections2d on faces touched by  
1424   // intersection3d
1425   //---------------------------------------------------------
1426   TopTools_ListIteratorOfListOfShape it1LE ;    
1427   TopTools_ListIteratorOfListOfShape it2LE ;  
1428
1429   //-----------------------------------------------
1430   // Intersection of edges 2*2.
1431   //-----------------------------------------------
1432   const TopTools_ListOfShape&        LE = AsDes->Descendant(F);
1433   TopoDS_Vertex                      V1,V2;
1434   Standard_Integer                   j, i = 1;
1435   BRepAdaptor_Surface BAsurf(F);
1436   //
1437   for ( it1LE.Initialize(LE) ; it1LE.More(); it1LE.Next()) {
1438     const TopoDS_Edge& E1 = TopoDS::Edge(it1LE.Value());        
1439     j = 1;
1440     it2LE.Initialize(LE);
1441     
1442     while (j < i && it2LE.More()) {
1443       const TopoDS_Edge& E2 = TopoDS::Edge(it2LE.Value());
1444       //--------------------------------------------------------------
1445       // Intersections of New edges obtained by intersection
1446       // between them and with edges of restrictions
1447       //------------------------------------------------------
1448       if ( (!EdgesOfFace.Contains(E1) || !EdgesOfFace.Contains(E2)) &&
1449            (NewEdges.Contains(E1) || NewEdges.Contains(E2)) ) {
1450         TopoDS_Shape aLocalShape = F.Oriented(TopAbs_FORWARD);
1451         EdgeInter(TopoDS::Face(aLocalShape),BAsurf,E1,E2,AsDes,Tol,Standard_True, theDMVV);
1452 //          EdgeInter(TopoDS::Face(F.Oriented(TopAbs_FORWARD)),E1,E2,AsDes,Tol,Standard_True);
1453       }
1454       it2LE.Next();
1455       j++;
1456     }
1457     i++;
1458   }
1459 }
1460
1461 //=======================================================================
1462 //function : ConnexIntByInt
1463 //purpose  : 
1464 //=======================================================================
1465 Standard_Boolean BRepOffset_Inter2d::ConnexIntByInt
1466  (const TopoDS_Face&            FI,
1467   BRepOffset_Offset&            OFI,
1468   TopTools_DataMapOfShapeShape& MES,
1469   const TopTools_DataMapOfShapeShape& Build,
1470   const Handle(BRepAlgo_AsDes)& AsDes2d,
1471   const Standard_Real           Offset,
1472   const Standard_Real           Tol,
1473   const BRepOffset_Analyse&     Analyse,
1474   TopTools_IndexedMapOfShape&   FacesWithVerts,
1475   TopTools_IndexedDataMapOfShapeListOfShape& theDMVV)
1476 {  
1477
1478   TopTools_DataMapOfShapeListOfShape MVE;
1479   BRepOffset_Tool::MapVertexEdges(FI,MVE);
1480
1481   //---------------------
1482   // Extension of edges.
1483   //---------------------
1484   TopoDS_Edge  NE;
1485   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape it(MVE);
1486   for  ( ; it.More(); it.Next()) {
1487     const TopTools_ListOfShape&  L = it.Value();
1488     Standard_Boolean   YaBuild = 0;
1489     TopTools_ListIteratorOfListOfShape itL(L);
1490     for (; itL.More(); itL.Next()) {
1491       YaBuild = Build.IsBound(itL.Value());
1492       if (YaBuild) break;
1493     }
1494     if (YaBuild) {
1495       for (itL.Initialize(L); itL.More(); itL.Next()) {
1496         const TopoDS_Edge& EI = TopoDS::Edge(itL.Value());
1497         if (EI.Orientation() != TopAbs_FORWARD &&
1498             EI.Orientation() != TopAbs_REVERSED)
1499           continue;
1500         TopoDS_Shape aLocalShape = OFI.Generated(EI);
1501         const TopoDS_Edge& OE = TopoDS::Edge(aLocalShape);
1502         if (!MES.IsBound(OE) && !Build.IsBound(EI)) {
1503           if (!ExtentEdge(OE, NE, Offset))
1504           {
1505             return Standard_False;
1506           }
1507           MES.Bind  (OE,NE);
1508         }
1509       }
1510     } 
1511   }
1512   
1513   TopoDS_Face           FIO = TopoDS::Face(OFI.Face());
1514   if (MES.IsBound(FIO)) FIO = TopoDS::Face(MES(FIO));
1515   //
1516   BRepAdaptor_Surface BAsurf(FIO);
1517   
1518   TopExp_Explorer exp(FI.Oriented(TopAbs_FORWARD),TopAbs_WIRE);
1519   for (; exp.More(); exp.Next()) {
1520     const TopoDS_Wire&     W = TopoDS::Wire(exp.Current());
1521     BRepTools_WireExplorer wexp;
1522     Standard_Boolean       end = Standard_False ;
1523     TopoDS_Edge            FirstE,CurE,NextE;
1524
1525     TopoDS_Shape aLocalWire = W .Oriented(TopAbs_FORWARD);
1526     TopoDS_Shape aLocalFace = FI.Oriented(TopAbs_FORWARD);
1527     wexp.Init(TopoDS::Wire(aLocalWire),TopoDS::Face(aLocalFace));
1528     if (!wexp.More())
1529       continue; // Protection from case when explorer does not contain edges.
1530     CurE = FirstE  = wexp.Current();
1531     TopTools_IndexedMapOfShape Edges;
1532     Standard_Boolean ToReverse1, ToReverse2;
1533     ToReverse1 = IsOrientationChanged(Edges, CurE);
1534     while (!end) {
1535       wexp.Next();
1536       if (wexp.More()) {
1537         NextE = wexp.Current();
1538       } 
1539       else {
1540         NextE = FirstE; end = Standard_True;
1541       }
1542       if (CurE.IsSame(NextE)) continue;
1543
1544       ToReverse2 = IsOrientationChanged(Edges, NextE);
1545
1546       TopoDS_Vertex Vref = CommonVertex(CurE, NextE); 
1547       gp_Pnt Pref = BRep_Tool::Pnt(Vref);
1548
1549       CurE = Analyse.EdgeReplacement (FI, CurE);
1550       NextE = Analyse.EdgeReplacement (FI, NextE);
1551
1552       TopoDS_Shape aLocalShape = OFI.Generated(CurE);
1553       TopoDS_Edge CEO = TopoDS::Edge(aLocalShape);
1554       aLocalShape = OFI.Generated(NextE);
1555       TopoDS_Edge NEO = TopoDS::Edge(aLocalShape);
1556       //------------------------------------------
1557       // Inter processing of images of CurE NextE.
1558       //------------------------------------------
1559       TopTools_ListOfShape LV1,LV2;
1560       Standard_Boolean     DoInter = 1;
1561       TopoDS_Shape         NE1,NE2;
1562       
1563       if (Build.IsBound(CurE) && Build.IsBound(NextE)) {
1564         NE1 = Build(CurE );
1565         NE2 = Build(NextE);
1566       }
1567       else if (Build.IsBound(CurE) && MES.IsBound(NEO)) {
1568         NE1 = Build(CurE);
1569         NE2 = MES  (NEO);
1570       }
1571       else if (Build.IsBound(NextE) && MES.IsBound(CEO)) {
1572         NE1 = Build(NextE);
1573         NE2 = MES(CEO);
1574         Standard_Boolean Tmp = ToReverse1;
1575         ToReverse1 = ToReverse2;
1576         ToReverse2 = Tmp;
1577       }
1578       else {
1579         DoInter = 0;
1580       }
1581       if (DoInter) {
1582         //------------------------------------
1583         // NE1,NE2 can be a compound of Edges.
1584         //------------------------------------
1585         Standard_Boolean bCoincide;
1586         TopExp_Explorer Exp1, Exp2;
1587         for (Exp1.Init(NE1, TopAbs_EDGE); Exp1.More(); Exp1.Next()) {
1588           TopoDS_Edge aE1 = TopoDS::Edge(Exp1.Current());
1589           for (Exp2.Init(NE2, TopAbs_EDGE); Exp2.More(); Exp2.Next()) {
1590             TopoDS_Edge aE2 = TopoDS::Edge(Exp2.Current());
1591
1592             //Correct orientation of edges
1593             if (ToReverse1)
1594               aE1.Reverse();
1595             if (ToReverse2)
1596               aE2.Reverse();
1597             //////////////////////////////
1598             
1599             RefEdgeInter(FIO, BAsurf, aE1, aE2, AsDes2d,
1600                          Tol, Standard_True, Pref, theDMVV, bCoincide);
1601           }
1602         }
1603         //
1604         // check if some of the offset edges have been
1605         // generated out of the common vertex
1606         if (Build.IsBound(Vref)) {
1607           FacesWithVerts.Add(FI);
1608         }
1609       }
1610       else {
1611         TopoDS_Vertex  V = CommonVertex(CEO,NEO);
1612         if (!V.IsNull())
1613         {
1614           if (MES.IsBound(CEO)) {
1615             UpdateVertex  (V,CEO,TopoDS::Edge(MES(CEO)),Tol);
1616             AsDes2d->Add     (MES(CEO),V);
1617           }
1618           if (MES.IsBound(NEO)) {
1619             UpdateVertex (V,NEO,TopoDS::Edge(MES(NEO)),Tol);
1620             AsDes2d->Add    (MES(NEO),V);
1621           }
1622         }
1623       }
1624       CurE = wexp.Current();
1625       ToReverse1 = ToReverse2;
1626     }
1627   }
1628   return Standard_True;
1629 }
1630
1631 //=======================================================================
1632 //function : ConnexIntByIntInVert
1633 //purpose  : Intersection of the edges generated out of vertices
1634 //=======================================================================
1635 void BRepOffset_Inter2d::ConnexIntByIntInVert
1636  (const TopoDS_Face&            FI,
1637   BRepOffset_Offset&            OFI,
1638   TopTools_DataMapOfShapeShape& MES,
1639   const TopTools_DataMapOfShapeShape& Build,
1640   const Handle(BRepAlgo_AsDes)& AsDes,
1641   const Handle(BRepAlgo_AsDes)& AsDes2d,
1642   const Standard_Real           Tol,
1643   const BRepOffset_Analyse&     Analyse,
1644   TopTools_IndexedDataMapOfShapeListOfShape& theDMVV)
1645 {
1646   TopoDS_Face           FIO = TopoDS::Face(OFI.Face());
1647   if (MES.IsBound(FIO)) FIO = TopoDS::Face(MES(FIO));
1648   //
1649   TopTools_MapOfShape aME;
1650   const TopTools_ListOfShape& aLE = AsDes->Descendant(FIO);
1651   TopTools_ListIteratorOfListOfShape aItLE(aLE);
1652   for (; aItLE.More(); aItLE.Next()) {
1653     const TopoDS_Shape& aE = aItLE.Value();
1654     aME.Add(aE);
1655   }
1656   //
1657   BRepAdaptor_Surface BAsurf(FIO);
1658   //
1659   TopExp_Explorer exp(FI.Oriented(TopAbs_FORWARD),TopAbs_WIRE);
1660   for (; exp.More(); exp.Next()) {
1661     const TopoDS_Wire&     W = TopoDS::Wire(exp.Current());
1662     //
1663     BRepTools_WireExplorer wexp;
1664     Standard_Boolean       end = Standard_False ;
1665     TopoDS_Edge            FirstE,CurE,NextE;
1666     //
1667     TopoDS_Shape aLocalWire = W .Oriented(TopAbs_FORWARD);
1668     TopoDS_Shape aLocalFace = FI.Oriented(TopAbs_FORWARD);
1669     wexp.Init(TopoDS::Wire(aLocalWire),TopoDS::Face(aLocalFace));
1670     if (!wexp.More())
1671       continue; // Protection from case when explorer does not contain edges.
1672     //
1673     CurE = FirstE  = wexp.Current(); 
1674     while (!end) {
1675       wexp.Next();
1676       if (wexp.More()) {
1677         NextE = wexp.Current();
1678       } 
1679       else {
1680         NextE = FirstE; end = Standard_True;
1681       }
1682       if (CurE.IsSame(NextE)) continue;
1683       //
1684       TopoDS_Vertex Vref = CommonVertex(CurE, NextE); 
1685       gp_Pnt Pref = BRep_Tool::Pnt(Vref);
1686       if (!Build.IsBound(Vref)) {
1687         CurE = NextE;
1688         continue;
1689       }
1690
1691       CurE = Analyse.EdgeReplacement (FI, CurE);
1692       NextE = Analyse.EdgeReplacement (FI, NextE);
1693
1694       TopoDS_Shape aLocalShape = OFI.Generated(CurE);
1695       TopoDS_Edge CEO = TopoDS::Edge(aLocalShape);
1696       aLocalShape = OFI.Generated(NextE);
1697       TopoDS_Edge NEO = TopoDS::Edge(aLocalShape);
1698       //
1699       TopoDS_Shape         NE1,NE2;
1700       
1701       if (Build.IsBound(CurE) && Build.IsBound(NextE)) {
1702         NE1 = Build(CurE );
1703         NE2 = Build(NextE);
1704       }
1705       else if (Build.IsBound(CurE) && MES.IsBound(NEO)) {
1706         NE1 = Build(CurE);
1707         NE2 = MES  (NEO);
1708       }
1709       else if (Build.IsBound(NextE) && MES.IsBound(CEO)) {
1710         NE1 = Build(NextE);
1711         NE2 = MES(CEO);
1712       }
1713       else {
1714         CurE = wexp.Current();
1715         continue;
1716       }
1717       //
1718       TopExp_Explorer Exp1, Exp2;
1719       Standard_Boolean bCoincide;
1720       // intersect edges generated from vertex with the edges of the face
1721       TopoDS_Shape NE3 = Build(Vref);
1722       //
1723       for (Exp2.Init(NE3, TopAbs_EDGE); Exp2.More(); Exp2.Next()) {
1724         const TopoDS_Edge& aE3 = *(TopoDS_Edge*)&Exp2.Current();
1725         if (!aME.Contains(aE3)) {
1726           continue;
1727         }
1728         //
1729         // intersection with first edge
1730         for (Exp1.Init(NE1, TopAbs_EDGE); Exp1.More(); Exp1.Next()) {
1731           const TopoDS_Edge& aE1 = TopoDS::Edge(Exp1.Current());
1732           RefEdgeInter(FIO, BAsurf, aE1, aE3, AsDes2d,
1733             Tol, Standard_True, Pref, theDMVV, bCoincide);
1734           if (bCoincide) {
1735             // in case of coincidence trim the edge E3 the same way as E1
1736             Store(aE3, AsDes2d->Descendant(aE1), Tol, Standard_True, AsDes2d, theDMVV);
1737           }
1738         }
1739         //
1740         // intersection with second edge
1741         for (Exp1.Init(NE2, TopAbs_EDGE); Exp1.More(); Exp1.Next()) {
1742           const TopoDS_Edge& aE2 = TopoDS::Edge(Exp1.Current());
1743           RefEdgeInter(FIO, BAsurf, aE2, aE3, AsDes2d,
1744             Tol, Standard_True, Pref, theDMVV, bCoincide);
1745           if (bCoincide) {
1746             // in case of coincidence trim the edge E3 the same way as E2
1747             Store(aE3, AsDes2d->Descendant(aE2), Tol, Standard_True, AsDes2d, theDMVV);
1748           }
1749         }
1750         //
1751         // intersection of the edges generated from vertex
1752         // among themselves
1753         for (Exp1.Init(NE3, TopAbs_EDGE); Exp1.More(); Exp1.Next()) {
1754           if (aE3.IsSame(Exp1.Current())) {
1755             break;
1756           }
1757         }
1758         //
1759         for (Exp1.Next(); Exp1.More(); Exp1.Next()) {
1760           const TopoDS_Edge& aE3Next = TopoDS::Edge(Exp1.Current());
1761           if (aME.Contains(aE3Next)) {
1762             RefEdgeInter(FIO, BAsurf, aE3Next, aE3, AsDes2d,
1763               Tol, Standard_True, Pref, theDMVV, bCoincide);
1764           }
1765         }
1766       }
1767       CurE = wexp.Current();
1768     }
1769   }
1770 }
1771
1772 //=======================================================================
1773 //function : MakeChain
1774 //purpose  : 
1775 //=======================================================================
1776 static void MakeChain(const TopoDS_Shape& theV,
1777                       const TopTools_IndexedDataMapOfShapeListOfShape& theDMVV,
1778                       TopTools_MapOfShape& theMDone,
1779                       TopTools_ListOfShape& theChain)
1780 {
1781   if (theMDone.Add(theV)) {
1782     theChain.Append(theV);
1783     const TopTools_ListOfShape* pLV = theDMVV.Seek(theV);
1784     if (pLV) {
1785       TopTools_ListIteratorOfListOfShape aIt(*pLV);
1786       for (; aIt.More(); aIt.Next()) {
1787         MakeChain(aIt.Value(), theDMVV, theMDone, theChain);
1788       }
1789     }
1790   }
1791 }
1792
1793 //=======================================================================
1794 //function : FuseVertices
1795 //purpose  : 
1796 //=======================================================================
1797 Standard_Boolean BRepOffset_Inter2d::FuseVertices (const TopTools_IndexedDataMapOfShapeListOfShape& theDMVV,
1798                                                    const Handle(BRepAlgo_AsDes)& theAsDes)
1799 {
1800   BRep_Builder aBB;
1801   TopTools_MapOfShape aMVDone;
1802   Standard_Integer i, aNb = theDMVV.Extent();
1803   for (i = 1; i <= aNb; ++i) {
1804     const TopoDS_Vertex& aV = TopoDS::Vertex(theDMVV.FindKey(i));
1805     //
1806     // find chain of vertices
1807     TopTools_ListOfShape aLVChain;
1808     MakeChain(aV, theDMVV, aMVDone, aLVChain);
1809     //
1810     if (aLVChain.Extent() < 2) {
1811       continue;
1812     }
1813     //
1814     // make new vertex
1815     TopoDS_Vertex aVNew;
1816     BOPTools_AlgoTools::MakeVertex(aLVChain, aVNew);
1817     //
1818     TopoDS_Vertex aVNewInt = TopoDS::Vertex(aVNew.Oriented(TopAbs_INTERNAL));
1819     //
1820     TopTools_ListIteratorOfListOfShape aIt(aLVChain);
1821     for (; aIt.More(); aIt.Next()) {
1822       const TopoDS_Shape& aVOld = aIt.Value();
1823       // update the parameters on edges
1824       TopoDS_Vertex aVOldInt = TopoDS::Vertex(aVOld.Oriented(TopAbs_INTERNAL));
1825       const TopTools_ListOfShape& aLE = theAsDes->Ascendant(aVOld);
1826       //
1827       TopTools_ListIteratorOfListOfShape aItLE(aLE);
1828       for (; aItLE.More(); aItLE.Next()) {
1829         const TopoDS_Edge& aE = TopoDS::Edge(aItLE.Value());
1830         Standard_Real aTolE = BRep_Tool::Tolerance(aE);
1831         Standard_Real aT; 
1832         if (!BRep_Tool::Parameter(aVOldInt, aE, aT))
1833         {
1834           return Standard_False;
1835         }
1836         aBB.UpdateVertex(aVNewInt, aT, aE, aTolE);
1837       }
1838       // and replace the vertex
1839       theAsDes->Replace(aVOld, aVNew);
1840     }
1841   }
1842   return Standard_True;
1843 }