97d06be3764205460699e3a1412e36431d7b94c4
[occt.git] / src / BRepFill / BRepFill_OffsetWire.cxx
1 // Created on: 1995-04-20
2 // Created by: Bruno DUMORTIER
3 // Copyright (c) 1995-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 - Fri Jul  8 11:21:38 2005 OCC9145
18
19 #include <stdio.h>
20
21 #include <BRepFill_OffsetWire.ixx>
22
23 #include <BRepAdaptor_Curve.hxx>
24 #include <BRepAdaptor_Surface.hxx>
25
26 #include <BRepFill_DataMapOfNodeShape.hxx>
27 #include <BRepFill_DataMapOfShapeSequenceOfPnt.hxx>
28 #include <BRepFill_DataMapOfShapeSequenceOfReal.hxx> 
29 #include <BRepFill_DataMapOfOrientedShapeListOfShape.hxx> 
30 #include <BRepFill_TrimEdgeTool.hxx>
31 #include <BRepLib.hxx>
32 #include <BRepLib_MakeVertex.hxx>
33 #include <BRepLib_MakeFace.hxx>
34 #include <BRepLib_MakeWire.hxx>
35 #include <BRepLib_MakeEdge.hxx>
36 #include <BRepTools.hxx>
37 #include <BRep_Builder.hxx>
38 #include <BRep_Tool.hxx>
39 #include <BRep_TEdge.hxx>
40 #include <BRep_CurveRepresentation.hxx>
41 #include <BRep_GCurve.hxx>
42 #include <BRepTools_WireExplorer.hxx>
43 #include <BRepMAT2d_Explorer.hxx>
44 #include <Geom2dAdaptor_Curve.hxx>
45 #include <Geom2dAdaptor_HCurve.hxx>
46 #include <Adaptor3d_OffsetCurve.hxx>
47 #include <Adaptor3d_Curve.hxx>
48 #include <Geom_Surface.hxx>
49 #include <Geom_Plane.hxx>
50 #include <Geom2d_Curve.hxx>
51 #include <Geom2d_Circle.hxx>
52 #include <Geom2d_Line.hxx>
53 #include <Geom2d_TrimmedCurve.hxx>
54 #include <Geom2d_OffsetCurve.hxx>
55 #include <GeomAPI.hxx>
56 #include <Geom_TrimmedCurve.hxx>
57 #include <Geom_Circle.hxx>
58 #include <Geom_OffsetCurve.hxx>
59 #include <MAT_Arc.hxx>
60 #include <MAT_Node.hxx>
61 #include <MAT_Graph.hxx>
62 #include <MAT2d_CutCurve.hxx>
63 #include <Precision.hxx>
64 #include <Standard_NotImplemented.hxx>
65 #include <TColgp_SequenceOfPnt.hxx>
66 #include <TColStd_SequenceOfReal.hxx> 
67 #include <TopAbs.hxx> 
68 #include <TopExp.hxx>
69 #include <TopExp_Explorer.hxx>
70 #include <TopoDS.hxx>
71 #include <TopoDS_Wire.hxx>
72 #include <TopoDS_Compound.hxx>
73 #include <TopoDS_Iterator.hxx>
74 #include <TopTools_MapOfShape.hxx>
75 #include <TopTools_MapIteratorOfMapOfShape.hxx>
76 #include <TopTools_ListIteratorOfListOfShape.hxx>
77 #include <TopTools_DataMapOfShapeListOfShape.hxx>
78 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
79 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
80 #include <TopTools_SequenceOfShape.hxx>
81 #include <TopTools_ListOfShape.hxx>    
82 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>    
83 #include <TopTools_DataMapOfShapeSequenceOfShape.hxx>
84
85 #include <gp.hxx>
86 #include <gp_Vec.hxx>
87 #include <gp_Ax2.hxx>
88 #include <gp_Pln.hxx>
89 #include <gp_Dir2d.hxx>
90
91 #include <BRep_TVertex.hxx>
92 #include <TopTools_IndexedMapOfShape.hxx>
93 #include <Geom2d_BSplineCurve.hxx>
94 #include <TColgp_Array1OfPnt2d.hxx>
95 #include <TColStd_Array1OfReal.hxx>
96 #include <TColStd_Array1OfInteger.hxx>
97 #include <BRepTools_Substitution.hxx>
98 #include <BRepLib_MakeVertex.hxx>
99 #include <Geom2dLProp_CLProps2d.hxx>
100 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
101 #include <Standard_ErrorHandler.hxx>
102
103 #ifdef DRAW
104 #include <Draw.hxx>
105 #include <DrawTrSurf.hxx>
106 #include <DrawTrSurf_Curve2d.hxx>
107 #include <DBRep.hxx>
108 static Standard_Boolean AffichGeom  = Standard_False;
109 static Standard_Boolean Affich2d    = Standard_False;
110 static Standard_Boolean AffichEdge  = Standard_False;
111 static Standard_Integer NbTRIMEDGES = 0;
112 static Standard_Integer NbOFFSET    = 0;
113 static Standard_Integer NbEDGES     = 0;
114 static Standard_Integer NbBISSEC    = 0;
115 #endif
116
117 //  Modified by Sergey KHROMOV - Thu Nov 16 17:24:39 2000 Begin
118
119 static void QuasiFleche(const Adaptor3d_Curve& C,
120                         const Standard_Real Deflection2, 
121                         const Standard_Real Udeb,
122                         const gp_Pnt& Pdeb,
123                         const gp_Vec& Vdeb,
124                         const Standard_Real Ufin,
125                         const gp_Pnt& Pfin,
126                         const gp_Vec& Vfin,
127                         const Standard_Integer Nbmin,
128                         const Standard_Real Eps,
129                         TColStd_SequenceOfReal& Parameters,
130                         TColgp_SequenceOfPnt& Points);
131
132 static Standard_Boolean PerformCurve (TColStd_SequenceOfReal& Parameters,
133                                       TColgp_SequenceOfPnt&   Points,
134                                       const Adaptor3d_Curve& C, 
135                                       const Standard_Real Deflection,
136                                       const Standard_Real U1,
137                                       const Standard_Real U2,
138                                       const Standard_Real EPSILON,
139                                       const Standard_Integer Nbmin);
140
141 static void CheckBadEdges(const TopoDS_Face& Spine, const Standard_Real Offset,
142                           const BRepMAT2d_BisectingLocus& Locus, 
143                           const BRepMAT2d_LinkTopoBilo&   Link,
144                           TopTools_ListOfShape& BadEdges);
145
146 static Standard_Integer CutEdge (const TopoDS_Edge& E, 
147                                  const TopoDS_Face& F,
148                                        Standard_Integer ForceCut,
149                                        TopTools_ListOfShape& Cuts);
150
151
152 static void CutCurve (const Handle(Geom2d_TrimmedCurve)& C,
153                       const Standard_Integer nbParts,
154                             TColGeom2d_SequenceOfCurve& theCurves);
155 //  Modified by Sergey KHROMOV - Thu Nov 16 17:24:47 2000 End
156
157
158 static void EdgeVertices (const TopoDS_Edge&   E,
159                                 TopoDS_Vertex& V1, 
160                                 TopoDS_Vertex& V2)
161 {
162   if (E.Orientation() == TopAbs_REVERSED) {
163     TopExp::Vertices(E,V2,V1);
164   }
165   else {
166     TopExp::Vertices(E,V1,V2);
167   }
168 }
169                                       
170 static void UpdateDetromp (TopTools_ListOfShape&           Detromp1, 
171                            TopTools_ListOfShape&           Detromp2, 
172                            const TopTools_SequenceOfShape& Vertices, 
173                            const TColgp_SequenceOfPnt&     Params, 
174                            const Bisector_Bisec&           Bisec,
175                            const Standard_Boolean          SOnE,
176                            const Standard_Boolean          EOnE,
177                            const BRepFill_TrimEdgeTool&    Trim);
178
179 static Standard_Boolean VertexFromNode
180 (const Handle(MAT_Node)&      aNode, 
181  const Standard_Real          Offset,
182  gp_Pnt2d&                    PN,
183  BRepFill_DataMapOfNodeShape& MapNodeVertex,
184  TopoDS_Vertex&               VN);
185
186 static void StoreInMap (const TopoDS_Shape& V1,
187                         const TopoDS_Shape& V2,
188                         TopTools_IndexedDataMapOfShapeShape& MapVV);
189
190 static void TrimEdge (const TopoDS_Edge&              CurrentEdge,
191                       const TopTools_ListOfShape&     D,
192                             TopTools_SequenceOfShape& Sv,  
193                             TColStd_SequenceOfReal&   MapverPar,
194                             TopTools_SequenceOfShape& S,
195                             TopTools_IndexedDataMapOfShapeShape& MapVV);
196
197 static Standard_Boolean DoubleOrNotInside (const TopTools_ListOfShape& EC,
198                                            const TopoDS_Vertex&        V);
199
200 static Standard_Boolean IsSmallClosedEdge(const TopoDS_Edge& anEdge,
201                                           const TopoDS_Vertex& aVertex);
202
203 static void MakeCircle 
204 (const TopoDS_Edge&                          E, 
205  const TopoDS_Vertex&                        V, 
206  const TopoDS_Face&                          F,
207  const Standard_Real                         Offset, 
208  BRepFill_IndexedDataMapOfOrientedShapeListOfShape& Map,
209  const Handle(Geom_Plane)&                   RefPlane);
210
211 static void MakeOffset 
212 (const TopoDS_Edge&                          E,
213  const TopoDS_Face&                          F,
214  const Standard_Real                         Offset, 
215  BRepFill_IndexedDataMapOfOrientedShapeListOfShape& Map,
216  const Handle(Geom_Plane)&                   RefPlane);
217
218
219
220 //=======================================================================
221 //function : CheckFace
222 //purpose  : Check if face contains an edge with C0 continuity
223 //=======================================================================
224 //
225 static void CheckFace(const TopoDS_Face& theFace)
226   {
227   TopExp_Explorer ex(theFace,TopAbs_EDGE);
228   for(; ex.More(); ex.Next())
229     {
230     TopoDS_Edge anEdge=TopoDS::Edge(ex.Current());
231     Standard_Real f,l;
232     const Handle(Geom2d_Curve) C = BRep_Tool::CurveOnSurface(anEdge,theFace,f,l);
233     if (C->Continuity() == GeomAbs_C0)
234       Standard_ConstructionError::Raise("Initial shape contains an edge with C0 continuity");
235     }
236   }
237
238 //=======================================================================
239 //function : KPartCircle
240 //purpose  : 
241 //=======================================================================
242
243 static Standard_Boolean KPartCircle
244 (const TopoDS_Face&  mySpine,
245  const Standard_Real myOffset,
246  const Standard_Real Alt,
247  TopoDS_Shape&       myShape, 
248  BRepFill_IndexedDataMapOfOrientedShapeListOfShape& myMap,
249  Standard_Boolean&    myIsDone)
250 {
251   // The only contour which is a closed circle
252   TopExp_Explorer exp(mySpine,TopAbs_EDGE);
253   Standard_Integer NbEdges = 0;
254   TopoDS_Edge      E;
255
256   for (; exp.More(); exp.Next()) {
257     NbEdges++;
258     E = TopoDS::Edge(exp.Current());
259     if (NbEdges > 1) return Standard_False;
260   }
261   TopoDS_Vertex V1,V2;
262   TopExp::Vertices(E,V1,V2);
263   if (!V1.IsSame(V2)) return Standard_False;
264
265   Standard_Real      f,l;
266   TopLoc_Location    L;
267   Handle(Geom_Curve) C =  BRep_Tool::Curve(E,L,f,l);
268
269   if (C->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
270     Handle(Geom_TrimmedCurve) Ct = Handle(Geom_TrimmedCurve)::DownCast(C);
271     C = Ct->BasisCurve();
272   }
273
274   if (!C->IsKind(STANDARD_TYPE(Geom_Circle))) return Standard_False;
275   Handle(Geom_Circle) CE = Handle(Geom_Circle)::DownCast(C);
276   Standard_Real anOffset = myOffset;
277   if (E.Orientation() == TopAbs_REVERSED) anOffset *= -1;
278   
279   if (anOffset < 0. || Abs(anOffset) < CE->Radius()) {
280     Handle(Geom_Circle) OC = new Geom_Circle (CE->Position(),CE->Radius() - anOffset);
281     myShape = BRepLib_MakeEdge(OC,f,l);
282
283     myShape.Orientation(E.Orientation());
284     myShape.Location(L);
285     if (Alt != 0.) {
286       BRepAdaptor_Surface S(mySpine,0);
287       gp_Ax1 Nor = S.Plane().Axis();
288       gp_Trsf T;
289       gp_Vec Trans(Nor.Direction());
290       Trans = Alt*Trans;
291       T.SetTranslation(Trans);
292       myShape.Move(TopLoc_Location(T));
293     }
294     
295     TopTools_ListOfShape LL;
296     LL.Append(myShape);
297     myMap.Add(E,LL);
298   }
299   myIsDone = Standard_True;
300   return Standard_True;
301 }
302
303 //=======================================================================
304 //function : BRepFill_OffsetWire
305 //purpose  : 
306 //=======================================================================
307
308 BRepFill_OffsetWire::BRepFill_OffsetWire() 
309 :myIsDone(Standard_False)
310 {
311 }
312
313
314 //=======================================================================
315 //function : BRepFill_OffsetWire
316 //purpose  : 
317 //=======================================================================
318
319 BRepFill_OffsetWire::BRepFill_OffsetWire(const TopoDS_Face&     Spine,
320                                          const GeomAbs_JoinType Join )
321 {
322   Init(Spine,Join);
323 }
324
325 //=======================================================================
326 //function : Init
327 //purpose  : 
328 //=======================================================================
329
330 void BRepFill_OffsetWire::Init(const TopoDS_Face&     Spine,
331                                const GeomAbs_JoinType Join )
332 {
333   Standard_NotImplemented_Raise_if(Join > GeomAbs_Arc,
334                                    "Only GeomAbs_Arc is implemented");
335
336   myIsDone   = Standard_False;
337   TopoDS_Shape aLocalShape = Spine.Oriented(TopAbs_FORWARD);
338   mySpine    = TopoDS::Face(aLocalShape);
339 //  mySpine    = TopoDS::Face(Spine.Oriented(TopAbs_FORWARD));
340   myJoinType = Join;
341
342   CheckFace(mySpine);
343   
344   myMap.Clear();
345   myMapSpine.Clear();
346   //------------------------------------------------------------------
347   // cut the spine for bissectors.
348   //------------------------------------------------------------------
349 //  Modified by Sergey KHROMOV - Tue Nov 26 17:39:03 2002 Begin
350   static BRepMAT2d_Explorer Exp;
351
352   Exp.Perform(mySpine);
353
354 //  TopoDS_Face anOldSpine = mySpine;
355
356   mySpine = TopoDS::Face(Exp.ModifiedShape(mySpine));
357   PrepareSpine  ();
358
359 //  Modified by Sergey KHROMOV - Tue Nov 26 17:39:03 2002 End
360   TopoDS_Shape aShape;
361   BRepFill_IndexedDataMapOfOrientedShapeListOfShape aMap;
362   Standard_Boolean Done;
363   if (KPartCircle(myWorkSpine,1.,0.,aShape,aMap,Done)) return;
364   
365
366   //-----------------------------------------------------
367   // Calculate the map of bissectors to the left.  
368   // and Links Topology -> base elements of the map.
369   //-----------------------------------------------------
370   
371 //  Modified by Sergey KHROMOV - Tue Nov 26 17:39:03 2002 Begin
372 //   static BRepMAT2d_Explorer Exp;
373 //  Modified by Sergey KHROMOV - Tue Nov 26 17:39:03 2002 End
374   Exp.Perform(myWorkSpine);
375   myBilo.Compute(Exp,1,MAT_Left);
376   myLink.Perform(Exp,myBilo);
377 }
378
379
380 //=======================================================================
381 //function : IsDone
382 //purpose  : 
383 //=======================================================================
384
385 Standard_Boolean BRepFill_OffsetWire::IsDone() const 
386 {
387   return myIsDone;
388 }
389
390
391 //=======================================================================
392 //function : Spine
393 //purpose  : 
394 //=======================================================================
395
396 const TopoDS_Face& BRepFill_OffsetWire::Spine() const 
397 {
398   return mySpine;
399 }
400
401
402 //=======================================================================
403 //function : Shape
404 //purpose  : 
405 //=======================================================================
406
407 const TopoDS_Shape& BRepFill_OffsetWire::Shape() const 
408 {
409   return myShape;
410 }
411
412
413 //=======================================================================
414 //function : GeneratedShapes
415 //purpose  : 
416 //=======================================================================
417
418 const TopTools_ListOfShape& BRepFill_OffsetWire::GeneratedShapes
419 (const TopoDS_Shape& SpineShape)
420 {  
421   if (!myCallGen) {
422     if (!myMapSpine.IsEmpty()) {
423       // myMapSpine can be empty if passed by PerformWithBilo.
424       TopTools_DataMapIteratorOfDataMapOfShapeShape it(myMapSpine);
425       for (; it.More(); it.Next()) {
426         if (myMap.Contains(it.Key())) {
427           if (!myMap.Contains(it.Value())) {
428             TopTools_ListOfShape L;
429             myMap.Add(it.Value(),L);
430           }
431           if ( !it.Value().IsSame(it.Key())) {
432             myMap.ChangeFromKey(it.Value()).Append(myMap.ChangeFromKey(it.Key()));
433             //myMap.UnBind(it.Key());
434             TopoDS_Shape LastShape = myMap.FindKey(myMap.Extent());
435             TopTools_ListOfShape LastList;
436             LastList.Append(myMap(myMap.Extent()));
437             myMap.RemoveLast();
438             if (myMap.FindIndex(it.Key()) != 0)
439               myMap.Substitute(myMap.FindIndex(it.Key()), LastShape, LastList);
440           }
441         }
442         if (myMap.Contains(it.Key().Reversed())) {
443           if (!myMap.Contains(it.Value().Reversed())) {
444             TopTools_ListOfShape L;
445             myMap.Add(it.Value().Reversed(),L);
446           }
447           if ( !it.Value().IsSame(it.Key())) {
448             myMap.ChangeFromKey(it.Value().Reversed()).Append(myMap.ChangeFromKey(it.Key().Reversed()));
449             //myMap.UnBind(it.Key().Reversed());
450             TopoDS_Shape LastShape = myMap.FindKey(myMap.Extent());
451             TopTools_ListOfShape LastList;
452             LastList.Append(myMap(myMap.Extent()));
453             myMap.RemoveLast();
454             if (myMap.FindIndex(it.Key().Reversed()) != 0)
455               myMap.Substitute(myMap.FindIndex(it.Key().Reversed()), LastShape, LastList);
456           }
457         }
458       }
459     }
460     myCallGen = Standard_True;
461   }
462   
463   if (myMap.Contains(SpineShape)) {
464     return myMap.FindFromKey(SpineShape);
465   }
466   else {
467     static TopTools_ListOfShape Empty;
468     return Empty;
469   }
470 }
471
472
473 //=======================================================================
474 //function : JoinType
475 //purpose  : 
476 //=======================================================================
477
478 GeomAbs_JoinType BRepFill_OffsetWire::JoinType() const 
479 {
480   return myJoinType;
481 }
482
483 //=======================================================================
484 //function : Perform
485 //purpose  : 
486 //=======================================================================
487
488 void BRepFill_OffsetWire::Perform (const Standard_Real Offset,
489                                    const Standard_Real Alt)
490 {
491   //  Modified by skv - Fri Jul  8 11:21:38 2005 OCC9145 Begin
492   try
493   {
494     OCC_CATCH_SIGNALS
495       myCallGen = Standard_False;
496     if (KPartCircle(mySpine,Offset,Alt,myShape,myMap,myIsDone)) return;
497
498     TopoDS_Face oldWorkSpain = myWorkSpine;
499
500     TopTools_ListOfShape BadEdges;
501     CheckBadEdges(myWorkSpine,Offset,myBilo,myLink,BadEdges);
502
503     if(!BadEdges.IsEmpty())
504     {
505       // Modification of myWorkSpine;
506       //cout << "Modification of myWorkSpine : " << BadEdges.Extent() << endl;
507       BRepTools_Substitution aSubst;
508       TopTools_ListIteratorOfListOfShape it(BadEdges);
509       TopTools_ListOfShape aL;
510       Standard_Real aDefl = .01 * Abs(Offset);
511       TColStd_SequenceOfReal Parameters;
512       TColgp_SequenceOfPnt Points;
513
514       for(; it.More(); it.Next()) {
515         aL.Clear();
516         Parameters.Clear();
517         Points.Clear();
518         const TopoDS_Shape& anE = it.Value();
519
520         TopoDS_Vertex Vf, Vl;
521         TopExp::Vertices(TopoDS::Edge(anE), Vf, Vl);
522
523         Standard_Real f, l;
524         Handle(Geom_Curve) G3d = BRep_Tool::Curve(TopoDS::Edge(anE),f,l);
525         GeomAdaptor_Curve  AC(G3d,f,l);
526
527         PerformCurve(Parameters, Points, AC, aDefl, f, 
528                                           l, Precision::Confusion(), 2);
529
530         Standard_Integer NPnts = Points.Length();
531         if(NPnts > 2)
532         {
533           //cout << NPnts << " points " << endl;
534           TopoDS_Vertex FV = Vf;
535           TopoDS_Vertex LV;
536           TopoDS_Edge newE;
537           Standard_Integer np;
538           for(np = 2; np < NPnts; np++) {
539             gp_Pnt LP = Points(np);
540             LV = BRepLib_MakeVertex(LP);
541             newE = BRepLib_MakeEdge(FV, LV);
542             aL.Append(newE);
543             FV = LV;
544           }
545           LV = Vl;
546           newE = BRepLib_MakeEdge(FV, LV);
547           aL.Append(newE);
548         }
549         else
550         {
551           //cout << " 2 points " << endl;
552           TopoDS_Edge newE = BRepLib_MakeEdge(Vf, Vl);
553           aL.Append(newE);
554         }
555         //Update myMapSpine
556         if (myMapSpine.IsBound( anE ))
557         {
558           TopTools_ListIteratorOfListOfShape newit( aL );
559           for (; newit.More(); newit.Next())
560           {
561             TopoDS_Edge NewEdge = TopoDS::Edge( newit.Value() );
562             myMapSpine.Bind( NewEdge, myMapSpine(anE) );
563             TopoDS_Vertex NewV1, NewV2;
564             EdgeVertices( NewEdge, NewV1, NewV2 );
565             if (!myMapSpine.IsBound(NewV1)) myMapSpine.Bind( NewV1, myMapSpine(anE) );
566             if (!myMapSpine.IsBound(NewV2)) myMapSpine.Bind( NewV2, myMapSpine(anE) );
567           }
568           myMapSpine.UnBind( anE );
569         }
570         ///////////////////
571         aSubst.Substitute(anE, aL);
572       }
573
574       TopTools_DataMapOfShapeListOfShape wwmap;
575       TopoDS_Iterator itws( myWorkSpine );
576       for (; itws.More(); itws.Next())
577       {
578         TopoDS_Shape aWire = itws.Value();
579         aSubst.Build( aWire );
580         if (aSubst.IsCopied(aWire))
581         {
582           TopoDS_Wire NewWire = TopoDS::Wire( aSubst.Copy(aWire).First() );
583           NewWire.Closed( aWire.Closed() );
584           TopTools_ListOfShape Lw;
585           Lw.Append( NewWire );
586           wwmap.Bind( aWire, Lw );
587         }
588       }
589       aSubst.Clear();
590       TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itmap( wwmap );
591       for (; itmap.More(); itmap.Next())
592         aSubst.Substitute( itmap.Key(), itmap.Value() );
593       
594       aSubst.Build(myWorkSpine);
595       
596       if(aSubst.IsCopied(myWorkSpine)) {
597         myWorkSpine = TopoDS::Face(aSubst.Copy(myWorkSpine).First());
598
599         BRepMAT2d_Explorer newExp;
600         newExp.Perform(myWorkSpine);
601         BRepMAT2d_BisectingLocus newBilo;
602         BRepMAT2d_LinkTopoBilo newLink;
603         newBilo.Compute(newExp,1,MAT_Left);
604
605         if(!newBilo.IsDone())
606         {
607           myShape.Nullify();
608           myIsDone = Standard_False;
609           return;
610         }
611
612         newLink.Perform(newExp,newBilo);
613         PerformWithBiLo(myWorkSpine,Offset,newBilo,newLink,myJoinType,Alt);
614         myWorkSpine = oldWorkSpain;
615       }
616       else {
617         PerformWithBiLo(myWorkSpine,Offset,myBilo,myLink,myJoinType,Alt);
618       }
619     }
620     else
621     {
622       PerformWithBiLo(myWorkSpine,Offset,myBilo,myLink,myJoinType,Alt);
623     }
624   }
625   catch (...)//Every exception was caught.
626   {
627     myShape.Nullify();
628     myIsDone = Standard_False;
629     cout<<"An exception was caught in BRepFill_OffsetWire::Perform : ";
630     Standard_Failure::Caught()->Print(cout);
631     cout<<endl;
632
633     return;
634   }
635
636   //  Modified by skv - Fri Jul  8 11:21:38 2005 OCC9145 End
637   //  Modified by Sergey KHROMOV - Thu Mar 14 10:48:15 2002 Begin
638   TopExp_Explorer anExp(myShape, TopAbs_WIRE);
639
640   for (; anExp.More(); anExp.Next()) {
641     const TopoDS_Shape &aWire = anExp.Current();
642
643     if (!aWire.Closed()) {
644       myShape.Nullify();
645       myIsDone = Standard_False;
646       Standard_ConstructionError::Raise("Offset wire is not closed.");
647     }
648   }
649   //  Modified by Sergey KHROMOV - Thu Mar 14 10:48:16 2002 End
650 }
651
652 //=======================================================================
653 //function : Compute
654 //purpose  : 
655 //=======================================================================
656
657 void Compute (const TopoDS_Face&  Spine,
658                     TopoDS_Shape& aShape,
659                     BRepFill_IndexedDataMapOfOrientedShapeListOfShape& Map,
660               const Standard_Real Alt)
661 {
662   BRep_Builder B;
663   B.MakeCompound(TopoDS::Compound(aShape));
664   Standard_Real ALT = Alt;
665   if ( Spine.Orientation() == TopAbs_REVERSED) ALT = -Alt;
666   gp_Trsf T;
667   T.SetTranslation(gp_Vec(0.,0.,ALT));
668   TopLoc_Location L(T);
669
670   for ( TopExp_Explorer exp(Spine,TopAbs_WIRE); exp.More(); exp.Next()) {
671     const TopoDS_Wire& CurW = TopoDS::Wire(exp.Current());
672     TopoDS_Shape aLocalShape = CurW.Moved(L);
673     TopoDS_Wire        NewW = TopoDS::Wire(aLocalShape);
674 //    TopoDS_Wire        NewW = TopoDS::Wire(CurW.Moved(L));
675     B.Add(aShape,NewW);
676     // update Map.
677     TopoDS_Iterator it1( CurW);
678     TopoDS_Iterator it2( NewW);
679     for ( ; it1.More(); it1.Next(), it2.Next()) {
680       TopTools_ListOfShape List;
681       List.Append(it2.Value());
682       Map.Add(it1.Value(), List);
683     }
684   }
685 }
686
687 //=======================================================================
688 //function : PerformWithBiLo
689 //purpose  : 
690 //=======================================================================
691
692 void BRepFill_OffsetWire::PerformWithBiLo
693 (const TopoDS_Face&              Spine,
694  const Standard_Real             Offset,
695  const BRepMAT2d_BisectingLocus& Locus, 
696        BRepMAT2d_LinkTopoBilo&   Link,
697  const GeomAbs_JoinType          Join,
698  const Standard_Real             Alt)
699 {
700   Standard_NotImplemented_Raise_if (Join > GeomAbs_Arc,
701                                     "Only GeomAbs_Arc is implemented");
702
703   myIsDone     = Standard_False;
704   TopoDS_Shape aLocalShape = Spine.Oriented(TopAbs_FORWARD);
705   myWorkSpine  = TopoDS::Face(aLocalShape);
706 //  myWorkSpine  = TopoDS::Face(Spine.Oriented(TopAbs_FORWARD));
707   myJoinType   = Join;
708   myOffset     = Offset ;
709   myShape.Nullify();
710
711
712   if (mySpine.IsNull()) {
713     TopoDS_Shape aLocalShape = Spine.Oriented(TopAbs_FORWARD);
714     mySpine = TopoDS::Face(aLocalShape);
715 //    mySpine = TopoDS::Face(Spine.Oriented(TopAbs_FORWARD));
716 }
717   myMap.Clear();
718
719   if ( Abs(myOffset) < Precision::Confusion()) {
720     Compute(mySpine,myShape,myMap,Alt);
721     myIsDone = Standard_True;
722     return;
723   }
724
725   //********************************
726   // Calculate for a non null offset 
727   //********************************
728   if (KPartCircle(mySpine,Offset,Alt,myShape,myMap,myIsDone))
729     return;
730
731   BRep_Builder myBuilder;
732   myBuilder.MakeCompound(TopoDS::Compound(myShape));
733   
734   //---------------------------------------------------------------------
735   // MapNodeVertex : associate to each node of the map (key1) and to
736   //                 each element of the profile (key2) a vertex (item).
737   // MapBis        : all edges or vertices (item) generated by 
738   //                 a bisectrice on a face or an edge (key) of revolution tubes.
739   // MapVerPar     : Map of parameters of vertices on parallel edges 
740   //                 the list contained in MapVerPar (E) corresponds to 
741   //                 parameters on E of vertices contained in MapBis(E);
742   //---------------------------------------------------------------------
743
744
745   BRepFill_DataMapOfNodeShape               MapNodeVertex; 
746   TopTools_DataMapOfShapeSequenceOfShape    MapBis;  
747   BRepFill_DataMapOfShapeSequenceOfReal     MapVerPar;
748
749   TopTools_DataMapOfShapeShape              EmptyMap;
750   TopTools_SequenceOfShape                  EmptySeq;
751   TopTools_ListOfShape                      EmptyList;
752   TColStd_SequenceOfReal                    EmptySeqOfReal;
753
754   Standard_Real ALT = Alt;
755   Handle(Geom_Plane) RefPlane = 
756     Handle(Geom_Plane)::DownCast(BRep_Tool::Surface(myWorkSpine));
757   if ( myWorkSpine.Orientation() == TopAbs_REVERSED) ALT = -Alt;
758   RefPlane = Handle(Geom_Plane)::DownCast
759     (RefPlane->Translated( ALT * gp_Vec(RefPlane->Axis().Direction() )));
760
761   //---------------------------------------------------------------
762   // Construction of Circles and OffsetCurves
763   //---------------------------------------------------------------
764  
765   for (Standard_Integer ic = 1; ic <= Locus.NumberOfContours(); ic++) {
766     TopoDS_Shape PEE = Link.GeneratingShape(Locus.BasicElt(ic,Locus.NumberOfElts(ic)));
767     TopoDS_Shape& PE = PEE ;      
768     for (Standard_Integer ie = 1; ie <= Locus.NumberOfElts(ic); ie++) {
769       const TopoDS_Shape& SE = Link.GeneratingShape(Locus.BasicElt(ic,ie));
770       if (SE.ShapeType() == TopAbs_VERTEX) {
771         MakeCircle (TopoDS::Edge(PE),TopoDS::Vertex(SE),
772                     myWorkSpine,myOffset,myMap,RefPlane);
773       }
774       else {
775         MakeOffset (TopoDS::Edge(SE),myWorkSpine,myOffset,myMap,RefPlane);
776         PE = SE;
777       }
778     }
779   }
780
781
782 #ifdef DRAW
783   if (AffichEdge) {
784     cout << " End Construction of geometric primitives "<<endl;
785   }
786 #endif
787
788
789   //---------------------------------------------------
790   // Construction of offset vertices.
791   //---------------------------------------------------
792   BRepFill_DataMapOfOrientedShapeListOfShape Detromp;
793   Handle(MAT_Arc)        CurrentArc;
794   Handle(Geom2d_Curve)   Bis, PCurve1, PCurve2 ;
795   Handle(Geom_Curve)     CBis;
796   Standard_Boolean       Reverse;
797   TopoDS_Edge            CurrentEdge;
798   TopoDS_Shape           S       [2];
799   TopoDS_Edge            E       [2];
800   TopLoc_Location        L;
801   Standard_Integer       j, k;
802
803   for (Standard_Integer i = 1; i <= Locus.Graph()->NumberOfArcs(); i++) {
804
805     CurrentArc           = Locus.Graph()->Arc(i);
806     Bisector_Bisec Bisec = Locus.GeomBis(CurrentArc,Reverse);
807     
808 #ifdef DRAW
809   if ( AffichGeom) {
810     char name[256];
811     sprintf(name,"BISSEC_%d",NbBISSEC++);
812     DrawTrSurf::Set(name,Bisec.Value());
813   }
814 #endif
815
816     //-------------------------------------------------------------------
817     // Return elements of the spine corresponding to separate basicElts.
818     //-------------------------------------------------------------------
819     S [0] = Link.GeneratingShape(CurrentArc->FirstElement());
820     S [1] = Link.GeneratingShape(CurrentArc->SecondElement());
821
822     TopTools_SequenceOfShape Vertices;
823     TColgp_SequenceOfPnt     Params;
824     
825     TopTools_DataMapOfShapeSequenceOfShape MapSeqVer;
826     BRepFill_DataMapOfShapeSequenceOfPnt   MapSeqPar;
827
828     //-----------------------------------------------------------
829     // Return parallel edges on each face.
830     // If no offset generated => move to the next bissectrice. 
831     //--------------------------------------------------------------
832     if (myMap.Contains(S[0]) && myMap.Contains(S[1])) {
833       E [0] = TopoDS::Edge(myMap.FindFromKey(S[0]).First());
834       E [1] = TopoDS::Edge(myMap.FindFromKey(S[1]).First());
835     }
836     else continue;
837
838     //-----------------------------------------------------------
839     // Construction of vertices corresponding to the node of the map.
840     // if they are on the offset.
841     //-----------------------------------------------------------
842     TopoDS_Vertex VS,VE;
843     Handle(MAT_Node) Node1, Node2;
844
845     if (Reverse) {
846       Node1 = CurrentArc->SecondNode();
847       Node2 = CurrentArc->FirstNode();
848     }
849     else  {
850       Node1 = CurrentArc->FirstNode();
851       Node2 = CurrentArc->SecondNode();
852     }
853     
854     Standard_Boolean StartOnEdge = 0, EndOnEdge = 0;
855     
856     if (!Node1->Infinite()) {
857       gp_Pnt2d aLocalPnt2d = Locus.GeomElt(Node1);
858       StartOnEdge = VertexFromNode(Node1, myOffset, aLocalPnt2d ,MapNodeVertex,VS);
859 //      StartOnEdge = VertexFromNode(Node1, myOffset, Locus.GeomElt(Node1),
860 //                                 MapNodeVertex,VS);
861     }
862     if (!Node2->Infinite()) {
863       gp_Pnt2d aLocalPnt2d = Locus.GeomElt(Node2) ;
864       EndOnEdge   = VertexFromNode(Node2, myOffset, aLocalPnt2d ,MapNodeVertex,VE);
865 //      EndOnEdge   = VertexFromNode(Node2, myOffset, Locus.GeomElt(Node2),
866 //                                 MapNodeVertex,VE);
867     }
868
869     //---------------------------------------------
870     // Construction of geometries.
871     //---------------------------------------------
872     BRepFill_TrimEdgeTool Trim (Bisec, 
873                                 Locus.GeomElt(CurrentArc->FirstElement()),
874                                 Locus.GeomElt(CurrentArc->SecondElement()),
875                                 myOffset);
876
877     //-----------------------------------------------------------
878     // Construction of vertices on edges parallel to the spine.
879     //-----------------------------------------------------------
880
881     Trim.IntersectWith(E [0], E [1], Params);
882
883     for (Standard_Integer s = 1; s <= Params.Length(); s++) {
884       TopoDS_Vertex VC;
885       myBuilder.MakeVertex (VC);
886       gp_Pnt2d P2  = Bisec.Value()->Value(Params.Value(s).X());
887       gp_Pnt   PVC(P2.X(),P2.Y(),0.);
888
889       myBuilder.UpdateVertex(VC,PVC,Precision::Confusion());
890       Vertices.Append(VC);
891     }
892     if (StartOnEdge) {
893       Standard_Boolean Start = 1;
894       Trim.AddOrConfuse(Start, E[0], E[1], Params);
895       if (Params.Length() == Vertices.Length()) 
896          Vertices.SetValue(1,VS);
897       
898       else
899         // the point was not found by IntersectWith
900         Vertices.Prepend(VS);
901     }
902     if (EndOnEdge) {      
903       Standard_Boolean Start = 0;
904       Trim.AddOrConfuse(Start, E[0], E[1], Params);
905       if (Params.Length() == Vertices.Length()) 
906          Vertices.SetValue(Params.Length(),VE);
907       
908       else
909         // the point was not found by IntersectWith
910         Vertices.Append(VE);
911     }
912
913     //------------------------------------------------------------
914     // Update Detromp.
915     // Detromp allows to remove vertices on the offset 
916     // corresponding to tangency zones
917     // Detromp ranks the vertices that limit
918     // the parts of the bissectrices located between the spine and the 
919     // offset.
920     //------------------------------------------------------------
921     if (!Detromp.IsBound(S[0])) Detromp.Bind(S[0],EmptyList);
922     if (!Detromp.IsBound(S[1])) Detromp.Bind(S[1],EmptyList);
923
924     
925     UpdateDetromp (Detromp(S[0]), Detromp(S[1]), Vertices, Params, 
926                    Bisec, StartOnEdge, EndOnEdge, Trim);
927     //----------------------------------------------
928     // Storage of vertices on parallel edges.
929     // fill MapBis and MapVerPar.
930     //----------------------------------------------
931     if (!Vertices.IsEmpty()) {
932       for (k = 0; k <= 1; k++) {
933         if (!MapBis.IsBound(E[k])) {
934           MapBis   .Bind(E[k],EmptySeq);
935           MapVerPar.Bind(E[k],EmptySeqOfReal);
936         } 
937         for (Standard_Integer ii = 1; ii <= Vertices.Length(); ii++) {
938           MapBis (E[k]).Append(Vertices.Value(ii));
939           if (k == 0) MapVerPar (E[k]).Append(Params.Value(ii).Y());
940           else        MapVerPar (E[k]).Append(Params.Value(ii).Z());
941         }
942       }
943     }
944     else {
945       //------------------------------------------------------------
946       // FOR COMPLETE CIRCLES. the parallel line can be contained
947       // in the zone without intersection with the border
948       // no intersection 
949       // if myoffset is < distance of nodes the parallel can be valid.
950       //-------------------------------------------------------------
951       for (k = 0; k <= 1; k++) {
952         if (!MapBis.IsBound(E[k])) {
953           if (Node1->Distance() > myOffset && Node2->Distance() > myOffset) {
954             MapBis   .Bind(E[k],EmptySeq); 
955             MapVerPar.Bind(E[k],EmptySeqOfReal);
956           }
957         }
958       }
959     }
960   }
961   
962 #ifdef DRAW
963   if (AffichEdge) {
964     cout << " End Construction of vertices on offsets"<<endl;
965   }
966 #endif
967
968   //----------------------------------
969   // Construction of parallel edges.
970   //----------------------------------
971   TopTools_IndexedDataMapOfShapeShape MapVV;
972
973   TopoDS_Shape CurrentSpine;
974
975   //BRepFill_DataMapIteratorOfDataMapOfOrientedShapeListOfShape ite1;  
976
977   for (j = 1; j <= myMap.Extent(); j++) {
978     CurrentSpine = myMap.FindKey(j);
979     CurrentEdge  = TopoDS::Edge(myMap(j).First());
980
981     myMap(j).Clear();
982     if (MapBis.IsBound(CurrentEdge)) {
983       TopTools_SequenceOfShape S;
984       if (!MapBis(CurrentEdge).IsEmpty()) {
985         TrimEdge (CurrentEdge,
986                   Detromp  (CurrentSpine),
987                   MapBis   (CurrentEdge) ,  
988                   MapVerPar(CurrentEdge) ,
989                   S, MapVV);
990         for ( k = 1; k <= S.Length(); k++) {
991           myMap(j).Append(S.Value(k));
992         }
993       }
994       else {
995         //-----------------
996         // Complete circles
997         //-----------------
998         myMap(j).Append(CurrentEdge);
999       }
1000     }
1001   }
1002   
1003   Standard_Integer ind;
1004   for (ind = 1; ind <= MapVV.Extent(); ind++)
1005     {
1006       TopoDS_Vertex OldV = TopoDS::Vertex(MapVV.FindKey(ind));
1007       TopoDS_Vertex NewV = TopoDS::Vertex(MapVV(ind));
1008       gp_Pnt P1 = BRep_Tool::Pnt(OldV);
1009       gp_Pnt P2 = BRep_Tool::Pnt(NewV);
1010       myBuilder.UpdateVertex(NewV, P1.Distance(P2));
1011       TopTools_ListOfShape LV;
1012       LV.Append( NewV.Oriented(TopAbs_FORWARD) );
1013       BRepTools_Substitution aSubst;
1014       aSubst.Substitute( OldV, LV );
1015       for (j = 1; j <= myMap.Extent(); j++)
1016         {
1017           TopTools_ListIteratorOfListOfShape itl(myMap(j));
1018           for (; itl.More(); itl.Next())
1019             {
1020               aSubst.Build(itl.Value());
1021               if (aSubst.IsCopied(itl.Value()))
1022                 {
1023                   const TopTools_ListOfShape& listSh = aSubst.Copy(itl.Value());
1024                   TopAbs_Orientation SaveOr = itl.Value().Orientation();
1025                   itl.Value() = listSh.First();
1026                   itl.Value().Orientation(SaveOr);
1027                 }
1028             }
1029         }
1030     }
1031       
1032   //----------------------------------
1033   // Construction of offset wires.
1034   //----------------------------------
1035   MakeWires ();
1036
1037   // Update vertices ( Constructed in the plane Z = 0) !!!
1038   TopTools_MapOfShape MapVertex;
1039   for ( TopExp_Explorer exp(myShape,TopAbs_VERTEX); exp.More(); exp.Next()) {
1040     TopoDS_Vertex V = TopoDS::Vertex(exp.Current());
1041     if ( MapVertex.Add(V)) {
1042       gp_Pnt        P = BRep_Tool::Pnt(V);
1043       P = RefPlane->Value(P.X(),P.Y());
1044       myBuilder.UpdateVertex(V,P, Precision::Confusion());
1045     }
1046   }
1047
1048   // Construction of curves 3d.
1049   BRepLib::BuildCurves3d(myShape);
1050   MapVertex.Clear();
1051   TopExp_Explorer Explo( myShape, TopAbs_EDGE );
1052   for (; Explo.More(); Explo.Next())
1053     {
1054       TopoDS_Edge E = TopoDS::Edge( Explo.Current() );
1055       TopoDS_Vertex V1, V2;
1056       TopExp::Vertices( E, V1, V2 );
1057       Handle(BRep_TVertex)& TV1 = *((Handle(BRep_TVertex)*) &(V1).TShape());
1058       Handle(BRep_TVertex)& TV2 = *((Handle(BRep_TVertex)*) &(V2).TShape());
1059       
1060       TopLoc_Location loc;
1061       Standard_Real f, l;
1062       Handle( Geom_Curve ) theCurve = BRep_Tool::Curve( E, loc, f, l );
1063       theCurve = Handle( Geom_Curve )::DownCast( theCurve->Copy() );
1064       theCurve->Transform( loc.Transformation() );
1065       gp_Pnt f3d = theCurve->Value( f );
1066       gp_Pnt l3d = theCurve->Value( l );
1067
1068       Standard_Real dist1, dist2;
1069       dist1 = f3d.Distance( TV1->Pnt() );
1070       dist2 = l3d.Distance( TV2->Pnt() );
1071       if (! MapVertex.Contains( V1 ))
1072         {
1073           TV1->Pnt( f3d );
1074           MapVertex.Add( V1 );
1075         }
1076       else
1077         TV1->UpdateTolerance( 1.5*dist1 );
1078       if (! MapVertex.Contains( V2 ))
1079         {
1080           TV2->Pnt( l3d );
1081           MapVertex.Add( V2 );
1082         }
1083       else
1084         TV2->UpdateTolerance( 1.5*dist2 );
1085     }
1086
1087   FixHoles();
1088
1089   myIsDone = Standard_True;
1090 }
1091
1092
1093 //=======================================================================
1094 //function : Generated
1095 //purpose  : 
1096 //=======================================================================
1097
1098 BRepFill_IndexedDataMapOfOrientedShapeListOfShape& 
1099 BRepFill_OffsetWire::Generated() 
1100 {
1101   return myMap;
1102 }
1103
1104
1105 //=======================================================================
1106 //function : PrepareSpine
1107 //purpose  : 
1108 //=======================================================================
1109
1110 void BRepFill_OffsetWire::PrepareSpine()
1111 {
1112   BRep_Builder      B;
1113   TopTools_ListOfShape Cuts;
1114   TopTools_ListIteratorOfListOfShape IteCuts;
1115   TopoDS_Vertex V1,V2;
1116
1117   myWorkSpine.Nullify();
1118   myMapSpine.Clear();
1119
1120   TopLoc_Location L;
1121   const Handle(Geom_Surface)& S    = BRep_Tool::Surface  (mySpine,L);
1122   Standard_Real               TolF = BRep_Tool::Tolerance(mySpine);
1123   B.MakeFace(myWorkSpine,S,L,TolF);
1124   
1125   for (TopoDS_Iterator IteF(mySpine) ; IteF.More(); IteF.Next()) {
1126
1127     TopoDS_Wire NW;
1128     B.MakeWire (NW);
1129
1130 //  Modified by Sergey KHROMOV - Thu Nov 16 17:29:55 2000 Begin
1131     Standard_Integer ForcedCut = 0;
1132     Standard_Integer nbResEdges = -1;
1133     TopTools_IndexedMapOfShape EdgeMap;
1134
1135     TopExp::MapShapes(IteF.Value(), TopAbs_EDGE, EdgeMap);
1136     Standard_Integer nbEdges = EdgeMap.Extent();
1137     
1138     if (nbEdges == 1)
1139       ForcedCut = 2;
1140 //  Modified by Sergey KHROMOV - Thu Nov 16 17:29:48 2000 End
1141
1142     for (TopoDS_Iterator IteW(IteF.Value()); IteW.More(); IteW.Next()) {
1143       
1144       const TopoDS_Edge& E = TopoDS::Edge(IteW.Value());
1145       EdgeVertices(E,V1,V2);
1146       myMapSpine.Bind(V1,V1);
1147       myMapSpine.Bind(V2,V2);
1148       Cuts.Clear();
1149
1150       // Cut
1151       TopoDS_Shape aLocalShape = E.Oriented(TopAbs_FORWARD);
1152 //  Modified by Sergey KHROMOV - Thu Nov 16 17:29:29 2000 Begin
1153       if (nbEdges == 2 && nbResEdges == 0)
1154         ForcedCut = 1;
1155 //  Modified by Sergey KHROMOV - Thu Nov 16 17:29:33 2000 End
1156       nbResEdges = CutEdge (TopoDS::Edge(aLocalShape), mySpine, ForcedCut, Cuts);
1157       
1158       if (Cuts.IsEmpty()) {
1159         B.Add(NW,E);
1160         myMapSpine.Bind(E,E);
1161       }
1162       else {    
1163         for (IteCuts.Initialize(Cuts); IteCuts.More(); IteCuts.Next()) {
1164           TopoDS_Edge NE = TopoDS::Edge(IteCuts.Value());
1165           NE.Orientation(E.Orientation());
1166           B.Add(NW,NE);
1167           myMapSpine.Bind(NE,E);
1168           EdgeVertices(NE,V1,V2);
1169           if (!myMapSpine.IsBound(V1)) myMapSpine.Bind(V1,E);
1170           if (!myMapSpine.IsBound(V2)) myMapSpine.Bind(V2,E);
1171         }
1172       }
1173     }
1174 //  Modified by Sergey KHROMOV - Thu Mar  7 09:17:41 2002 Begin
1175     TopoDS_Vertex aV1;
1176     TopoDS_Vertex aV2;
1177
1178     TopExp::Vertices(NW, aV1, aV2);
1179
1180     NW.Closed(aV1.IsSame(aV2));
1181 //  Modified by Sergey KHROMOV - Thu Mar  7 09:17:43 2002 End
1182     B.Add(myWorkSpine, NW);
1183   }
1184
1185 #ifdef DRAW
1186   if ( AffichEdge) {
1187     DBRep::Set("WS",myWorkSpine);
1188   }
1189 #endif
1190
1191 }
1192
1193 //=======================================================================
1194 //function : MakeWires
1195 //purpose  : 
1196 //=======================================================================
1197
1198 void BRepFill_OffsetWire::MakeWires()
1199 {
1200   //--------------------------------------------------------
1201   // creation of a single list of created parallel edges.
1202   //--------------------------------------------------------
1203   TopTools_SequenceOfShape TheEdges;
1204   TopTools_ListOfShape     TheWires;
1205   TopTools_ListIteratorOfListOfShape                          itl;
1206   //BRepFill_DataMapIteratorOfDataMapOfOrientedShapeListOfShape ite;  
1207   TopTools_IndexedDataMapOfShapeListOfShape                   MVE;
1208   //TopTools_DataMapIteratorOfDataMapOfShapeListOfShape         MVEit;
1209   TopoDS_Vertex V1,V2,VF,CV;
1210   Standard_Integer i;
1211
1212   for (i = 1; i <= myMap.Extent(); i++) {    
1213     for (itl.Initialize(myMap(i)); itl.More(); itl.Next()) {
1214       const TopoDS_Edge& E = TopoDS::Edge(itl.Value());
1215       TopExp::Vertices (E,V1,V2);
1216       if (V1.IsSame(V2) && IsSmallClosedEdge(E, V1))
1217         continue; //remove small closed edges
1218       if (!MVE.Contains(V1)) {
1219         TopTools_ListOfShape empty;
1220         MVE.Add(V1,empty);
1221       }
1222       MVE.ChangeFromKey(V1).Append(E);
1223       if (!MVE.Contains(V2)) {
1224         TopTools_ListOfShape empty;
1225         MVE.Add(V2,empty);
1226       }
1227       MVE.ChangeFromKey(V2).Append(E);
1228     }
1229   }
1230
1231   //--------------------------------------
1232   // Creation of parallel wires.
1233   //--------------------------------------
1234   BRep_Builder B;
1235
1236 //  Standard_Integer NbEdges;
1237 //  Standard_Boolean NewWire  = Standard_True;
1238 //  Standard_Boolean AddEdge  = Standard_False;
1239
1240   TopoDS_Wire      NW;
1241   Standard_Boolean End;
1242   TopoDS_Edge CE;
1243
1244   while (!MVE.IsEmpty()) {
1245     B.MakeWire(NW);
1246
1247     //MVEit.Initialize(MVE);
1248     for (i = 1; i <= MVE.Extent(); i++)
1249       if(MVE(i).Extent() == 1)
1250         break;
1251
1252     //if(!MVEit.More()) MVEit.Initialize(MVE);
1253     if (i > MVE.Extent())
1254       i = 1;
1255     
1256     CV  = VF = TopoDS::Vertex(MVE.FindKey(i));
1257     CE  = TopoDS::Edge(MVE(i).First());
1258     End = Standard_False;
1259     MVE.ChangeFromKey(CV).RemoveFirst(); 
1260
1261 //  Modified by Sergey KHROMOV - Thu Mar 14 11:29:59 2002 Begin
1262     Standard_Boolean isClosed = Standard_False;
1263 //  Modified by Sergey KHROMOV - Thu Mar 14 11:30:00 2002 End
1264
1265     while(!End) {      
1266       //-------------------------------
1267       // Construction of a wire.
1268       //-------------------------------
1269       TopExp::Vertices(CE,V1,V2);
1270       if (!CV.IsSame(V1)) CV = V1; else CV = V2;
1271
1272       B.Add (NW,CE);
1273
1274       if (VF.IsSame(CV) || !MVE.Contains(CV)) {
1275 //  Modified by Sergey KHROMOV - Thu Mar 14 11:30:14 2002 Begin
1276         isClosed = VF.IsSame(CV);
1277 //  Modified by Sergey KHROMOV - Thu Mar 14 11:30:15 2002 End
1278         End = Standard_True;
1279         //MVE.UnBind(VF);
1280         TopoDS_Shape LastShape = MVE.FindKey(MVE.Extent());
1281         TopTools_ListOfShape LastList;
1282         LastList.Append(MVE(MVE.Extent()));
1283         MVE.RemoveLast();
1284         if (MVE.FindIndex(VF) != 0)
1285           MVE.Substitute(MVE.FindIndex(VF), LastShape, LastList);
1286       }
1287
1288       if (!End) {
1289         if (MVE.FindFromKey(CV).Extent() > 2) {
1290           //cout <<"vertex on more that 2 edges in a face."<<endl;
1291         }
1292         for ( itl.Initialize(MVE.FindFromKey(CV)); itl.More(); itl.Next()) {
1293           if (itl.Value().IsSame(CE)) {
1294             MVE.ChangeFromKey(CV).Remove(itl);
1295             break;
1296           }
1297         }
1298         if (!MVE.FindFromKey(CV).IsEmpty()) {
1299           CE = TopoDS::Edge(MVE.FindFromKey(CV).First());
1300           MVE.ChangeFromKey(CV).RemoveFirst();
1301         }
1302         if (MVE.FindFromKey(CV).IsEmpty())
1303         {
1304           //MVE.UnBind(CV);
1305           TopoDS_Shape LastShape = MVE.FindKey(MVE.Extent());
1306           TopTools_ListOfShape LastList;
1307           LastList.Append(MVE(MVE.Extent()));
1308           MVE.RemoveLast();
1309           if (MVE.FindIndex(CV) != 0)
1310             MVE.Substitute(MVE.FindIndex(CV), LastShape, LastList);
1311         }
1312       }
1313     }
1314 //  Modified by Sergey KHROMOV - Thu Mar 14 11:29:31 2002 Begin
1315 //     NW.Closed(Standard_True);
1316     NW.Closed(isClosed);
1317 //  Modified by Sergey KHROMOV - Thu Mar 14 11:29:37 2002 End
1318     TheWires.Append(NW);
1319   }
1320
1321   // update myShape :
1322   //      -- if only one wire : myShape is a Wire
1323   //      -- if several wires : myShape is a Compound.
1324   if ( TheWires.Extent() == 1) {
1325     myShape = TheWires.First();
1326   }
1327   else {
1328     TopoDS_Compound R;
1329     B.MakeCompound(R);
1330     TopTools_ListIteratorOfListOfShape it(TheWires);
1331     for ( ; it.More(); it.Next()) {
1332       B.Add(R, it.Value());
1333     }
1334     myShape = R;
1335   }
1336   
1337 }
1338
1339 //=======================================================================
1340 //function : FixHoles
1341 //purpose  : 
1342 //=======================================================================
1343
1344 void BRepFill_OffsetWire::FixHoles()
1345 {
1346   TopTools_SequenceOfShape ClosedWires, UnclosedWires, IsolatedWires;
1347
1348   Standard_Real MaxTol = 0.;
1349   Standard_Integer i;
1350   BRep_Builder BB;
1351
1352   TopExp_Explorer Explo( mySpine, TopAbs_VERTEX );
1353   for (; Explo.More(); Explo.Next())
1354   {
1355     const TopoDS_Vertex& aVertex = TopoDS::Vertex( Explo.Current() );
1356     Standard_Real Tol = BRep_Tool::Tolerance(aVertex);
1357     if (Tol > MaxTol)
1358       MaxTol = Tol;
1359   }
1360   MaxTol *= 100.;
1361
1362   Explo.Init( myShape, TopAbs_WIRE );
1363   for (; Explo.More(); Explo.Next())
1364   {
1365     TopoDS_Shape aWire = Explo.Current();
1366     // Remove duplicated edges
1367     TopTools_DataMapOfShapeListOfShape EEmap;
1368     TopoDS_Iterator it( aWire );
1369     for (; it.More(); it.Next())
1370     {
1371       const TopoDS_Shape& anEdge = it.Value();
1372       if (! EEmap.IsBound( anEdge ))
1373       {
1374         TopTools_ListOfShape LE;
1375         EEmap.Bind( anEdge, LE );
1376       }
1377       else
1378         EEmap(anEdge).Append( anEdge );
1379     }
1380     aWire.Free( Standard_True );
1381     TopTools_DataMapIteratorOfDataMapOfShapeListOfShape mapit( EEmap );
1382     for (; mapit.More(); mapit.Next())
1383     {
1384       const TopTools_ListOfShape& LE = mapit.Value();
1385       TopTools_ListIteratorOfListOfShape itl( LE );
1386       for (; itl.More(); itl.Next())
1387         BB.Remove( aWire, itl.Value() );
1388     }
1389     // Sorting
1390     if (aWire.Closed())
1391       ClosedWires.Append( aWire );
1392     else
1393       UnclosedWires.Append( aWire );
1394   }
1395
1396   while (!UnclosedWires.IsEmpty())
1397   {
1398     TopoDS_Wire& Base = TopoDS::Wire( UnclosedWires(1) );
1399     TopoDS_Vertex Vf, Vl;
1400     TopExp::Vertices( Base, Vf, Vl );
1401     if(Vf.IsNull() || Vl.IsNull())
1402       Standard_Failure::Raise("BRepFill_OffsetWire::FixHoles(): Wrong wire.");
1403     gp_Pnt Pf, Pl;
1404     Pf = BRep_Tool::Pnt(Vf);
1405     Pl = BRep_Tool::Pnt(Vl);
1406     Standard_Real DistF = RealLast(), DistL = RealLast();
1407     Standard_Integer IndexF = 1, IndexL = 1;
1408     Standard_Boolean IsFirstF = Standard_False, IsFirstL = Standard_False;
1409     for (Standard_Integer i = 2; i <= UnclosedWires.Length(); i++)
1410     {
1411       TopoDS_Wire aWire = TopoDS::Wire( UnclosedWires(i) );
1412       TopoDS_Vertex V1, V2;
1413       TopExp::Vertices( aWire, V1, V2 );
1414
1415       if(V1.IsNull() || V2.IsNull())
1416         Standard_Failure::Raise("BRepFill_OffsetWire::FixHoles(): Wrong wire.");
1417
1418       gp_Pnt P1, P2;
1419       P1 = BRep_Tool::Pnt(V1);
1420       P2 = BRep_Tool::Pnt(V2);
1421       Standard_Real dist = Pf.Distance( P1 );
1422       if (dist < DistF)
1423       {
1424         DistF = dist;
1425         IndexF = i;
1426         IsFirstF = Standard_True;
1427       }
1428       dist = Pf.Distance( P2 );
1429       if (dist < DistF)
1430       {
1431         DistF = dist;
1432         IndexF = i;
1433         IsFirstF = Standard_False;
1434       }
1435       dist = Pl.Distance( P1 );
1436       if (dist < DistL)
1437       {
1438         DistL = dist;
1439         IndexL = i;
1440         IsFirstL = Standard_True;
1441       }
1442       dist = Pl.Distance( P2 );
1443       if (dist < DistL)
1444       {
1445         DistL = dist;
1446         IndexL = i;
1447         IsFirstL = Standard_False;
1448       }
1449     }
1450     TopoDS_Wire theWire;
1451     TopoDS_Edge theEdge;
1452     TopoDS_Vertex theVertex;
1453     Standard_Real CommonTol;
1454     Standard_Boolean TryToClose = Standard_True;
1455     if (DistF <= MaxTol && DistL <= MaxTol && IndexF == IndexL && IsFirstF == IsFirstL)
1456     {
1457       if (DistF < DistL)
1458       {
1459         DistL = RealLast();
1460         IndexL++;
1461       }
1462       else
1463       {
1464         DistF = RealLast();
1465         IndexF++;
1466       }
1467       TryToClose = Standard_False;
1468     }
1469     if (DistF <= MaxTol)
1470     {
1471       theWire = TopoDS::Wire( UnclosedWires(IndexF) );
1472       TopoDS_Vertex V1, V2;
1473       TopExp::Vertices( theWire, V1, V2 );
1474       TopTools_IndexedDataMapOfShapeListOfShape VEmap;
1475       TopExp::MapShapesAndAncestors( theWire, TopAbs_VERTEX, TopAbs_EDGE, VEmap );
1476       theEdge = (IsFirstF)? TopoDS::Edge(VEmap.FindFromKey( V1 ).First()) :
1477         TopoDS::Edge(VEmap.FindFromKey( V2 ).First());
1478       TopoDS_Iterator it( theWire );
1479       for (; it.More(); it.Next())
1480       {
1481         TopoDS_Edge anEdge = TopoDS::Edge( it.Value() );
1482         if (IsFirstF) anEdge.Reverse();
1483         if (!anEdge.IsSame( theEdge ))
1484           BB.Add( Base, anEdge );
1485       }
1486       theVertex = (IsFirstF)? V1 : V2;
1487       CommonTol = Max( BRep_Tool::Tolerance(Vf), BRep_Tool::Tolerance(theVertex) );
1488       if (DistF <= CommonTol)
1489       {
1490         theEdge.Free( Standard_True );
1491         Vf.Orientation( theVertex.Orientation() );
1492         BB.Remove( theEdge, theVertex );
1493         BB.Add( theEdge, Vf );
1494         BB.UpdateVertex( Vf, CommonTol );
1495         if (IsFirstF) theEdge.Reverse();
1496         BB.Add( Base, theEdge );
1497       }
1498       else
1499       {
1500         if (IsFirstF) theEdge.Reverse();
1501         BB.Add( Base, theEdge );
1502         // Creating new edge from theVertex to Vf
1503         TopoDS_Edge NewEdge = BRepLib_MakeEdge( theVertex, Vf );
1504         BB.Add( Base, NewEdge );
1505       }
1506     }
1507     if (DistL <= MaxTol && IndexL != IndexF)
1508     {
1509       theWire = TopoDS::Wire( UnclosedWires(IndexL) );
1510       TopoDS_Vertex V1, V2;
1511       TopExp::Vertices( theWire, V1, V2 );
1512       TopTools_IndexedDataMapOfShapeListOfShape VEmap;
1513       TopExp::MapShapesAndAncestors( theWire, TopAbs_VERTEX, TopAbs_EDGE, VEmap );
1514       theEdge = (IsFirstL)? TopoDS::Edge(VEmap.FindFromKey( V1 ).First()) :
1515         TopoDS::Edge(VEmap.FindFromKey( V2 ).First());
1516       TopoDS_Iterator it( theWire );
1517       for (; it.More(); it.Next())
1518       {
1519         TopoDS_Edge anEdge = TopoDS::Edge( it.Value() );
1520         if (!IsFirstL) anEdge.Reverse();
1521         if (!anEdge.IsSame( theEdge ))
1522           BB.Add( Base, anEdge );
1523       }
1524       theVertex = (IsFirstL)? V1 : V2;
1525       CommonTol = Max( BRep_Tool::Tolerance(Vl), BRep_Tool::Tolerance(theVertex) );
1526       if (DistL <= CommonTol)
1527       {
1528         theEdge.Free( Standard_True );
1529         Vl.Orientation( theVertex.Orientation() );
1530         BB.Remove( theEdge, theVertex );
1531         BB.Add( theEdge, Vl );
1532         BB.UpdateVertex( Vl, CommonTol );
1533         if (!IsFirstL) theEdge.Reverse();
1534         BB.Add( Base, theEdge );
1535       }
1536       else
1537       {
1538         if (!IsFirstL) theEdge.Reverse();
1539         BB.Add( Base, theEdge );
1540         // Creating new edge from Vl to theVertex
1541         TopoDS_Edge NewEdge = BRepLib_MakeEdge( Vl, theVertex );
1542         BB.Add( Base, NewEdge );
1543       }
1544     }
1545     // Check if it is possible to close resulting wire
1546     if (TryToClose)
1547     {
1548       TopExp::Vertices( Base, Vf, Vl );
1549       CommonTol = Max( BRep_Tool::Tolerance(Vf), BRep_Tool::Tolerance(Vl) );
1550       TopTools_IndexedDataMapOfShapeListOfShape VEmap;
1551       TopExp::MapShapesAndAncestors( Base, TopAbs_VERTEX, TopAbs_EDGE, VEmap );
1552       TopoDS_Edge Efirst, Elast;
1553       Efirst = TopoDS::Edge(VEmap.FindFromKey( Vf ).First());
1554       Elast  = TopoDS::Edge(VEmap.FindFromKey( Vl ).First());
1555       Pf = BRep_Tool::Pnt(Vf);
1556       Pl = BRep_Tool::Pnt(Vl);
1557       Standard_Real Dist = Pf.Distance(Pl);
1558       if (Dist <= CommonTol)
1559       {
1560         Elast.Free( Standard_True );
1561         Vf.Orientation( Vl.Orientation() );
1562         BB.Remove( Elast, Vl );
1563         BB.Add( Elast, Vf );
1564         BB.UpdateVertex( Vf, CommonTol );
1565         Base.Closed( Standard_True );
1566       }
1567       else if (Dist <= MaxTol)
1568       {
1569         // Creating new edge from Vl to Vf
1570         TopoDS_Edge NewEdge = BRepLib_MakeEdge( Vf, Vl );
1571         BB.Add( Base, NewEdge );
1572         Base.Closed( Standard_True );
1573       }
1574     }
1575     // Updating sequences ClosedWires and UnclosedWires
1576     if (DistF <= MaxTol)
1577       UnclosedWires.Remove( IndexF );
1578     if (DistL <= MaxTol && IndexL != IndexF)
1579     {
1580       if (DistF <= MaxTol && IndexL > IndexF)
1581         IndexL--;
1582       UnclosedWires.Remove( IndexL );
1583     }
1584     if (Base.Closed())
1585     {
1586       ClosedWires.Append( Base );
1587       UnclosedWires.Remove( 1 );
1588     }
1589     else if (DistF > MaxTol && DistL > MaxTol)
1590     {
1591       IsolatedWires.Append( Base );
1592       UnclosedWires.Remove( 1 );
1593     }
1594   }
1595
1596   // Updating myShape
1597   if (ClosedWires.Length() + IsolatedWires.Length() == 1)
1598   {
1599     if (!ClosedWires.IsEmpty())
1600       myShape = ClosedWires.First();
1601     else
1602       myShape = IsolatedWires.First();
1603   }
1604   else
1605   {
1606     TopoDS_Compound R;
1607     BB.MakeCompound( R );
1608     for (i = 1; i <= ClosedWires.Length(); i++)
1609       BB.Add( R, ClosedWires(i) );
1610     for (i = 1; i <= IsolatedWires.Length(); i++)
1611       BB.Add( R, IsolatedWires(i) );
1612     myShape = R;
1613   }
1614 }
1615
1616 //=======================================================================
1617 //function : CutEdge
1618 //purpose  : Cut edge at the extrema of curvatures and points of inflexion.
1619 //           So, closed circles are cut in two.
1620 //           If <Cuts> is empty, the edge is not modified.
1621 //           The first and the last vertex of the initial edge 
1622 //           belong to the first and the last parts respectively.
1623 //=======================================================================
1624 Standard_Integer CutEdge (const TopoDS_Edge& E, 
1625                           const TopoDS_Face& F,
1626                                 Standard_Integer ForceCut,
1627                                 TopTools_ListOfShape& Cuts)
1628 {
1629   Cuts.Clear();
1630   MAT2d_CutCurve              Cuter;
1631   TColGeom2d_SequenceOfCurve  theCurves;
1632   Standard_Real               f,l;
1633   Handle(Geom2d_Curve)        C2d;
1634   Handle(Geom2d_TrimmedCurve) CT2d;
1635 //  Modified by Sergey KHROMOV - Wed Mar  6 17:36:25 2002 Begin
1636   Standard_Real               aTol = BRep_Tool::Tolerance(E);
1637   Handle(Geom_Curve)          aC;
1638 //  Modified by Sergey KHROMOV - Wed Mar  6 17:36:25 2002 End
1639   
1640   TopoDS_Vertex V1,V2,VF,VL;
1641   TopExp::Vertices (E,V1,V2);
1642   BRep_Builder B;
1643   
1644   C2d  = BRep_Tool::CurveOnSurface (E,F,f,l);
1645 //  Modified by Sergey KHROMOV - Wed Mar  6 17:36:54 2002 Begin
1646   aC   = BRep_Tool::Curve(E,f,l);
1647 //  Modified by Sergey KHROMOV - Wed Mar  6 17:36:54 2002 End
1648   CT2d = new Geom2d_TrimmedCurve(C2d,f,l);
1649   //if (E.Orientation() == TopAbs_REVERSED) CT2d->Reverse();
1650
1651   if (CT2d->BasisCurve()->IsKind(STANDARD_TYPE(Geom2d_Circle)) &&
1652       ( Abs(f-l) >= M_PI) ) {
1653     return 0;
1654   }
1655
1656   //-------------------------
1657   // Cut curve.
1658   //-------------------------
1659   Cuter.Perform(CT2d);
1660
1661 //  Modified by Sergey KHROMOV - Thu Nov 16 17:28:29 2000 Begin
1662   if (ForceCut == 0) {
1663     if (Cuter.UnModified()) {
1664     //-----------------------------
1665     // edge not modified => return.
1666     //-----------------------------
1667       return 0;
1668     } else {
1669       for (Standard_Integer k = 1; k <= Cuter.NbCurves(); k++)
1670         theCurves.Append(Cuter.Value(k));
1671     }
1672   } else if (ForceCut == 1) {
1673     if (Cuter.UnModified()) {
1674       CutCurve (CT2d, 2, theCurves);
1675     } else {
1676       for (Standard_Integer k = 1; k <= Cuter.NbCurves(); k++)
1677         theCurves.Append(Cuter.Value(k));
1678     }
1679   } else if (ForceCut == 2) {
1680     if (Cuter.UnModified()) {
1681       CutCurve (CT2d, 3, theCurves);
1682     } else {
1683       if (Cuter.NbCurves() == 2) {
1684         Handle(Geom2d_TrimmedCurve)CC = Cuter.Value(1);
1685
1686         if (CC->LastParameter() > (l+f)/2.) {
1687           CutCurve (CC, 2, theCurves);
1688           theCurves.Append(Cuter.Value(2));
1689         } else {
1690           theCurves.Append(CC);
1691           CutCurve (Cuter.Value(2), 2, theCurves);
1692         }
1693       } else {
1694         for (Standard_Integer k = 1; k <= Cuter.NbCurves(); k++)
1695           theCurves.Append(Cuter.Value(k));
1696       }
1697     }
1698   }
1699 //  Modified by Sergey KHROMOV - Thu Nov 16 17:28:37 2000 End
1700
1701   //--------------------------------------
1702   // Creation of cut edges.
1703   //--------------------------------------
1704   VF = V1;
1705
1706   for (Standard_Integer k = 1; k <= theCurves.Length(); k++) {
1707
1708     Handle(Geom2d_TrimmedCurve)CC = Handle(Geom2d_TrimmedCurve)::DownCast(theCurves.Value(k));
1709
1710     if (k == theCurves.Length()) {VL = V2;}
1711     else { 
1712 //  Modified by Sergey KHROMOV - Wed Mar  6 17:38:02 2002 Begin
1713       gp_Pnt        P = aC->Value(CC->LastParameter());
1714
1715       VL = BRepLib_MakeVertex(P);
1716       B.UpdateVertex(VL, aTol);
1717 //  Modified by Sergey KHROMOV - Wed Mar  6 17:38:05 2002 End
1718     }
1719     TopoDS_Shape aLocalShape = E.EmptyCopied();
1720     TopoDS_Edge NE = TopoDS::Edge(aLocalShape);
1721 //      TopoDS_Edge NE = TopoDS::Edge(E.EmptyCopied());
1722     NE.Orientation(TopAbs_FORWARD);
1723     B.Add  (NE,VF.Oriented(TopAbs_FORWARD));
1724     B.Add  (NE,VL.Oriented(TopAbs_REVERSED));      
1725     B.Range(NE,CC->FirstParameter(),CC->LastParameter());
1726     Cuts.Append(NE.Oriented(E.Orientation()));
1727     VF = VL;
1728   }
1729
1730   return theCurves.Length();
1731 }
1732
1733 //  Modified by Sergey KHROMOV - Thu Nov 16 17:27:56 2000 Begin
1734 //=======================================================================
1735 //function : CutCurve
1736 //purpose  : 
1737 //=======================================================================
1738
1739 void CutCurve (const Handle(Geom2d_TrimmedCurve)& C,
1740                const Standard_Integer nbParts,
1741                      TColGeom2d_SequenceOfCurve& theCurves)
1742 {
1743   Handle(Geom2d_TrimmedCurve) TrimC;
1744   Standard_Real               UF,UL,UC;
1745   Standard_Real               Step;
1746   gp_Pnt2d                    PF,PL,PC;
1747   Standard_Real               PTol  = Precision::PConfusion()*10;
1748   Standard_Real               Tol   = Precision::Confusion()*10;
1749   Standard_Boolean            YaCut = Standard_False;
1750
1751   UF = C->FirstParameter();
1752   UL = C->LastParameter ();
1753   PF = C->Value(UF);
1754   PL = C->Value(UL);
1755
1756   Step = (UL - UF)/nbParts;
1757
1758   for (Standard_Integer i = 1; i < nbParts; i++) {
1759
1760     UC = UF + i*Step;
1761     PC = C->Value(UC);
1762
1763     if (UC - UF > PTol && PC.Distance(PF) > Tol) {
1764       if ( UL - UC < PTol || PL.Distance(PC) < Tol)
1765         continue;
1766
1767       TrimC = new Geom2d_TrimmedCurve(C,UF,UC);
1768       theCurves.Append(TrimC);
1769       UF = UC;
1770       PF = PC;
1771       YaCut = Standard_True;
1772     }
1773   }
1774   if (YaCut) {
1775     TrimC = new Geom2d_TrimmedCurve(C,UF,UL);
1776     theCurves.Append(TrimC);
1777   } else
1778     theCurves.Append(C);
1779 }
1780 //  Modified by Sergey KHROMOV - Thu Nov 16 17:28:13 2000 End
1781
1782 //=======================================================================
1783 //function : MakeCircle
1784 //purpose  : 
1785 //=======================================================================
1786
1787 void MakeCircle (const TopoDS_Edge&          E,
1788                  const TopoDS_Vertex&        V,
1789                  const TopoDS_Face&          F,
1790                  const Standard_Real         Offset, 
1791                        BRepFill_IndexedDataMapOfOrientedShapeListOfShape& Map,
1792                  const Handle(Geom_Plane)&   RefPlane)
1793 {
1794   // evaluate the Axis of the Circle.
1795   Standard_Real f,l;
1796   Handle(Geom2d_Curve) GC = BRep_Tool::CurveOnSurface(E,F,f,l);
1797   gp_Vec2d DX;
1798   gp_Pnt2d P;
1799
1800   if (E.Orientation() == TopAbs_FORWARD) {
1801     GC->D1(l,P,DX);
1802     DX.Reverse();
1803   }
1804   else GC->D1(f,P,DX);
1805
1806   gp_Ax2d Axis(P,gp_Dir2d(DX));
1807   Handle(Geom2d_Circle) Circ 
1808     = new  Geom2d_Circle(Axis, Abs(Offset), Offset < 0.);
1809
1810   // Bind the edges in my Map.
1811   TopoDS_Edge OE = BRepLib_MakeEdge(Circ, RefPlane);
1812   TopTools_ListOfShape LL;
1813
1814   LL.Append(OE);
1815   Map.Add(V,LL);
1816
1817 #ifdef DRAW
1818   if ( AffichGeom && !OE.IsNull()) {
1819     char name[256];
1820     sprintf(name,"OFFSET_%d",++NbOFFSET);
1821     DBRep::Set(name,OE);
1822   }
1823 #endif
1824 }
1825
1826 //=======================================================================
1827 //function : MakeOffset
1828 //purpose  : 
1829 //=======================================================================
1830
1831 void MakeOffset (const TopoDS_Edge&        E, 
1832                  const TopoDS_Face&        F,
1833                  const Standard_Real       Offset, 
1834                        BRepFill_IndexedDataMapOfOrientedShapeListOfShape& Map,
1835                  const Handle(Geom_Plane)& RefPlane)
1836 {
1837   Standard_Real f,l;
1838   Standard_Real anOffset = Offset;
1839
1840   if (E.Orientation() == TopAbs_REVERSED) anOffset *= -1;
1841
1842   Handle(Geom2d_Curve) G2d = BRep_Tool::CurveOnSurface(E,F,f,l);
1843   Handle(Geom2d_Curve) G2dOC;
1844
1845   Geom2dAdaptor_Curve  AC(G2d,f,l);
1846   if ( AC.GetType() == GeomAbs_Circle) {
1847     // if the offset is greater otr equal to the radius and the side of the  
1848     // concavity of the circle => edge null.
1849     gp_Circ2d C1(AC.Circle());
1850     gp_Ax22d axes( C1.Axis());
1851     gp_Dir2d Xd = axes.XDirection();
1852     gp_Dir2d Yd = axes.YDirection();
1853     Standard_Real Crossed = Xd.X()*Yd.Y()-Xd.Y()*Yd.X();
1854     Standard_Real Signe = ( Crossed > 0.) ? 1. : -1.;
1855
1856     if (anOffset*Signe < AC.Circle().Radius()) {
1857
1858       Handle(Geom2dAdaptor_HCurve) AHC = 
1859         new Geom2dAdaptor_HCurve(G2d);
1860       Adaptor3d_OffsetCurve   Off(AHC,-anOffset);
1861       Handle(Geom2d_Circle) CC = new Geom2d_Circle(Off.Circle());      
1862
1863       Standard_Real Delta = 2*M_PI - l + f;
1864       f -= 0.2*Delta; l += 0.2*Delta;
1865
1866       G2dOC = new Geom2d_TrimmedCurve(CC,f,l);
1867     }
1868   }
1869   else if (AC.GetType() == GeomAbs_Line) {
1870     Handle(Geom2dAdaptor_HCurve) AHC = 
1871       new Geom2dAdaptor_HCurve(G2d);
1872     Adaptor3d_OffsetCurve Off(AHC,anOffset);
1873     Handle(Geom2d_Line)       CC = new Geom2d_Line(Off.Line());
1874     Standard_Real Delta = (l - f);
1875     f -= Delta; l += Delta;
1876     G2dOC = new Geom2d_TrimmedCurve(CC,f,l);
1877   }
1878   else {
1879
1880     anOffset = -anOffset;
1881     Handle(Geom2d_TrimmedCurve) G2dT = new Geom2d_TrimmedCurve(G2d,f,l);
1882     G2dOC = new Geom2d_OffsetCurve( G2dT, anOffset);
1883
1884   }
1885
1886   // Bind the edges in my Map.
1887   if (!G2dOC.IsNull()) {
1888     TopoDS_Edge OE = BRepLib_MakeEdge(G2dOC, RefPlane);
1889     OE.Orientation(E.Orientation());
1890     TopTools_ListOfShape LL;
1891     LL.Append(OE);
1892     Map.Add(E,LL);
1893
1894 #ifdef DRAW  
1895     if (AffichGeom && !OE.IsNull()) {
1896       char name[256];
1897       sprintf(name,"OFFSET_%d",++NbOFFSET);
1898       DBRep::Set(name,OE);
1899       Standard_Real ii = 0;
1900     }
1901 #endif
1902     
1903   }
1904 }  
1905
1906 //=======================================================================
1907 //function : UpdateDetromp
1908 //purpose  : For each interval on bissectrice defined by parameters
1909 //           test if the medium point is at a distance > offset 
1910 //           in this case vertices corresponding to the extremities of the interval
1911 //           are ranked in the proofing.
1912 //           => If the same vertex appears in the proofing, the 
1913 //           border of the zone of proximity is tangent to the offset .
1914 //=======================================================================
1915
1916 void UpdateDetromp (TopTools_ListOfShape&           Detromp1,
1917                     TopTools_ListOfShape&           Detromp2, 
1918                     const TopTools_SequenceOfShape& Vertices, 
1919                     const TColgp_SequenceOfPnt&     Params, 
1920                     const Bisector_Bisec&           Bisec,
1921                     const Standard_Boolean          SOnE,
1922                     const Standard_Boolean          EOnE,
1923                     const BRepFill_TrimEdgeTool&    Trim)
1924 {
1925   Standard_Integer ii = 1;
1926   Standard_Real    U1,U2;
1927   TopoDS_Vertex    V1,V2;
1928
1929   Handle(Geom2d_Curve) Bis = Bisec.Value();
1930
1931   U1 = Bis->FirstParameter();
1932   
1933   if (SOnE) { 
1934     // the first point of the bissectrice is on the offset
1935     V1 = TopoDS::Vertex(Vertices.Value(ii));
1936     ii++; 
1937   }
1938
1939   while (ii <= Vertices.Length()) {
1940     U2 = Params.Value(ii).X();
1941     V2 = TopoDS::Vertex(Vertices.Value(ii));
1942
1943     gp_Pnt2d P = Bis->Value((U2 + U1)*0.5);  
1944     if (!Trim.IsInside(P)) {
1945       if (!V1.IsNull()) {
1946           Detromp1.Append(V1);
1947           Detromp2.Append(V1);
1948       }
1949       Detromp1.Append(V2);
1950       Detromp2.Append(V2);
1951     }
1952     U1 = U2;
1953     V1 = V2;
1954     ii ++;
1955   }
1956
1957   // test medium point between the last parameter and the end of the bissectrice.
1958   U2 = Bis->LastParameter();
1959   if (!EOnE) {
1960     if (!Precision::IsInfinite(U2)) {
1961       gp_Pnt2d P = Bis->Value((U2 + U1)*0.5);  
1962       if (!Trim.IsInside(P)) {
1963         if (!V1.IsNull()) {
1964           Detromp1.Append(V1);
1965           Detromp2.Append(V1);
1966         }
1967       }
1968     }
1969     else {
1970       if (!V1.IsNull()) {
1971         Detromp1.Append(V1);
1972         Detromp2.Append(V1);
1973       }
1974     }
1975   }    
1976 }
1977
1978 //=======================================================================
1979 //function : VertexFromNode
1980 //purpose  : 
1981 //=======================================================================
1982
1983 Standard_Boolean VertexFromNode (const Handle(MAT_Node)&      aNode, 
1984                                  const Standard_Real          Offset,
1985                                   gp_Pnt2d&                   PN,
1986                                  BRepFill_DataMapOfNodeShape& MapNodeVertex,
1987                                  TopoDS_Vertex&               VN)
1988 {  
1989   Standard_Boolean Status;
1990   Standard_Real    Tol = Precision::Confusion();
1991   BRep_Builder     B;
1992
1993   if (!aNode->Infinite() && Abs(aNode->Distance()-Offset) < Tol) {
1994     //------------------------------------------------
1995     // the Node gives a vertex on the offset
1996     //------------------------------------------------
1997     if (MapNodeVertex.IsBound(aNode)) {
1998       VN = TopoDS::Vertex(MapNodeVertex(aNode));
1999     }
2000     else { 
2001       gp_Pnt P(PN.X(),PN.Y(),0.);
2002       B.MakeVertex (VN);
2003       B.UpdateVertex(VN,P, Precision::Confusion());
2004       MapNodeVertex.Bind(aNode,VN);
2005     }
2006     Status = Standard_True;
2007   }
2008   else Status = Standard_False;
2009
2010   return Status;
2011 }
2012
2013
2014 //=======================================================================
2015 //function : StoreInMap
2016 //purpose  : 
2017 //=======================================================================
2018
2019 void StoreInMap (const TopoDS_Shape& V1,
2020                  const TopoDS_Shape& V2,
2021                  TopTools_IndexedDataMapOfShapeShape& MapVV)
2022 {
2023   TopoDS_Shape OldV = V1, NewV = V2;
2024   Standard_Integer i;
2025
2026   if (MapVV.Contains(V2))
2027     NewV = MapVV.FindFromKey(V2);
2028
2029   if (MapVV.Contains(V1))
2030     MapVV.ChangeFromKey(V1) = NewV;
2031
2032   for (i = 1; i <= MapVV.Extent(); i++)
2033     if (MapVV(i).IsSame(V1))
2034       MapVV(i) = NewV;
2035
2036   MapVV.Add(V1, NewV);
2037 }
2038
2039 //=======================================================================
2040 //function : TrimEdge
2041 //purpose  : 
2042 //=======================================================================
2043
2044 void TrimEdge (const TopoDS_Edge&              E,
2045                const TopTools_ListOfShape&     Detromp,
2046                      TopTools_SequenceOfShape& TheVer,
2047                      TColStd_SequenceOfReal&   ThePar,
2048                      TopTools_SequenceOfShape& S,
2049                      TopTools_IndexedDataMapOfShapeShape& MapVV)
2050 {
2051   Standard_Boolean         Change = Standard_True;
2052   BRep_Builder             TheBuilder;
2053   S.Clear();
2054
2055   //-----------------------------------------------------------
2056   // Parse two sequences depending on the parameter on the edge.
2057   //-----------------------------------------------------------
2058   while (Change) {
2059     Change = Standard_False;
2060     for (Standard_Integer i = 1; i < ThePar.Length(); i++) {
2061       if (ThePar.Value(i) > ThePar.Value(i+1)) {
2062         ThePar.Exchange(i,i+1);
2063         TheVer.Exchange(i,i+1);
2064         Change = Standard_True;
2065       }
2066     }
2067   }
2068
2069   //----------------------------------------------------------
2070   // If a vertex is not in the proofing, it is eliminated.
2071   //----------------------------------------------------------
2072   if (!BRep_Tool::Degenerated(E)) {
2073     for (Standard_Integer k = 1; k <= TheVer.Length(); k ++) {
2074       if ( DoubleOrNotInside (Detromp,
2075                               TopoDS::Vertex(TheVer.Value(k)))) {
2076         TheVer.Remove(k);
2077         ThePar.Remove(k);
2078         k--;
2079       }
2080     }
2081   }
2082
2083   //----------------------------------------------------------
2084   // If a vertex_double appears twice in the proofing 
2085   // the vertex is removed.
2086   // otherwise preserve only one of its representations.
2087   //----------------------------------------------------------
2088   if (!BRep_Tool::Degenerated(E)) {
2089     for (Standard_Integer k = 1; k < TheVer.Length(); k ++) {
2090       if (TheVer.Value(k).IsSame(TheVer.Value(k+1)) || 
2091          Abs(ThePar.Value(k)-ThePar.Value(k+1)) <= Precision::PConfusion()) {
2092
2093         if(k+1 == TheVer.Length()) {
2094           StoreInMap(TheVer(k), TheVer(k+1), MapVV);
2095           TheVer.Remove(k);
2096           ThePar.Remove(k);
2097         }
2098         else {
2099           StoreInMap(TheVer(k+1), TheVer(k), MapVV);
2100           TheVer.Remove(k+1);
2101           ThePar.Remove(k+1);
2102         }
2103         /*
2104         if ( DoubleOrNotInside (Detromp,
2105                                 TopoDS::Vertex(TheVer.Value(k)))) {
2106           TheVer.Remove(k);
2107           ThePar.Remove(k);
2108           k--;
2109         }
2110         */
2111         k--;
2112       }
2113     }
2114   }
2115   //-----------------------------------------------------------
2116   // Creation of edges.
2117   // the number of vertices should be even. The created edges  
2118   // go from a vertex with uneven index i to vertex i+1;
2119   //-----------------------------------------------------------
2120   for (Standard_Integer k = 1; k < TheVer.Length(); k = k+2) {
2121     TopoDS_Shape aLocalShape = E.EmptyCopied();
2122     TopoDS_Edge NewEdge = TopoDS::Edge(aLocalShape);
2123 //    TopoDS_Edge NewEdge = TopoDS::Edge(E.EmptyCopied());
2124
2125     if (NewEdge.Orientation() == TopAbs_REVERSED) {
2126       TheBuilder.Add  (NewEdge,TheVer.Value(k)  .Oriented(TopAbs_REVERSED));
2127       TheBuilder.Add  (NewEdge,TheVer.Value(k+1).Oriented(TopAbs_FORWARD));
2128     }
2129     else {      
2130       TheBuilder.Add  (NewEdge,TheVer.Value(k)  .Oriented(TopAbs_FORWARD));
2131       TheBuilder.Add  (NewEdge,TheVer.Value(k+1).Oriented(TopAbs_REVERSED));
2132     }
2133
2134
2135     TheBuilder.Range(NewEdge,ThePar.Value(k),ThePar.Value(k+1));
2136
2137 #ifdef DRAW
2138     if ( AffichEdge) {
2139       char name[256];
2140       sprintf(name,"TRIMEDGE_%d",NbTRIMEDGES);
2141       DBRep::Set(name,NewEdge);  
2142     }
2143     if (Affich2d) {
2144       TopLoc_Location L;
2145       Standard_Real f,l;
2146       Handle(Geom_Surface) Surf;  
2147       Handle(Geom2d_Curve) C;
2148       BRep_Tool::CurveOnSurface(NewEdge,C,Surf,L,f,l);
2149       char name[256];
2150       sprintf(name,"OFFSET2d_%d",NbTRIMEDGES++);
2151       Handle(Geom2d_TrimmedCurve) C2d = new Geom2d_TrimmedCurve(C,f,l);
2152       Handle(DrawTrSurf_Curve2d) dr =
2153         new DrawTrSurf_Curve2d(C2d,Standard_False);
2154       dr->SetColor(Draw_bleu);
2155       Draw::Set(name,dr);
2156     }
2157 #endif
2158
2159     S.Append(NewEdge);
2160   }
2161 }
2162
2163 //=======================================================================
2164 //function : DoubleOrNotInside
2165 //purpose  : return True if V appears twice in LV or is not inside.
2166 //=======================================================================
2167
2168 Standard_Boolean DoubleOrNotInside (const TopTools_ListOfShape& LV,
2169                                     const TopoDS_Vertex&        V)
2170 {  
2171   Standard_Boolean Vu = Standard_False;
2172   TopTools_ListIteratorOfListOfShape it(LV);
2173
2174   for ( ; it.More(); it.Next()) {
2175     if (V.IsSame(it.Value())) {
2176       if  (Vu) return Standard_True;
2177       else       Vu = Standard_True;
2178     }
2179   }
2180   if (Vu) return Standard_False;
2181   else    return Standard_True;   
2182 }
2183
2184 Standard_Boolean IsSmallClosedEdge(const TopoDS_Edge& anEdge,
2185                                    const TopoDS_Vertex& aVertex)
2186 {
2187   gp_Pnt PV = BRep_Tool::Pnt(aVertex);
2188   gp_Pnt2d PV2d, Pfirst, Plast, Pmid;
2189   PV2d.SetCoord( PV.X(), PV.Y() );
2190
2191   Handle(Geom2d_Curve) PCurve;
2192   Handle( BRep_CurveRepresentation ) CurveRep =
2193     ((Handle(BRep_TEdge)::DownCast(anEdge.TShape()))->Curves()).First();
2194   PCurve = CurveRep->PCurve();
2195
2196   Standard_Real fpar = (Handle(BRep_GCurve)::DownCast(CurveRep))->First();
2197   Standard_Real lpar = (Handle(BRep_GCurve)::DownCast(CurveRep))->Last();
2198   Pfirst = PCurve->Value(fpar);
2199   Plast  = PCurve->Value(lpar);
2200   Pmid   = PCurve->Value((fpar + lpar)*0.5);
2201
2202   Standard_Real theTol = BRep_Tool::Tolerance(aVertex);
2203   theTol *= 1.5;
2204
2205   Standard_Real dist1 = Pfirst.Distance(PV2d);
2206   Standard_Real dist2 = Plast.Distance(PV2d);
2207   Standard_Real dist3 = Pmid.Distance(PV2d);
2208
2209   if (dist1 <= theTol && dist2 <= theTol && dist3 <= theTol)
2210     return Standard_True;
2211
2212   return Standard_False;
2213 }
2214
2215 static void CheckBadEdges(const TopoDS_Face& Spine, const Standard_Real Offset,
2216                           const BRepMAT2d_BisectingLocus& Locus, 
2217                           const BRepMAT2d_LinkTopoBilo&   Link,
2218                           TopTools_ListOfShape& BadEdges)
2219 {
2220
2221   TopoDS_Face F = TopoDS::Face(Spine.Oriented(TopAbs_FORWARD));
2222   Standard_Real eps = Precision::Confusion(); 
2223   Standard_Real LimCurv = 1./Offset;
2224
2225   TopTools_MapOfShape aMap;
2226
2227   for (Standard_Integer ic = 1; ic <= Locus.NumberOfContours(); ic++) {
2228     for (Standard_Integer ie = 1; ie <= Locus.NumberOfElts(ic); ie++) {
2229       const TopoDS_Shape& SE = Link.GeneratingShape(Locus.BasicElt(ic,ie));
2230       if (SE.ShapeType() == TopAbs_EDGE) {
2231
2232         if (aMap.Contains(SE)) {
2233           //cout << "Edge is treated second time" << endl;
2234           continue;
2235         }
2236
2237         TopoDS_Edge E = TopoDS::Edge(SE);
2238
2239         Standard_Real f,l;
2240
2241         Handle(Geom2d_Curve) G2d = BRep_Tool::CurveOnSurface(E,F,f,l);
2242
2243         Geom2dAdaptor_Curve  AC(G2d,f,l);
2244         GeomAbs_CurveType aCType = AC.GetType();
2245
2246         if(aCType != GeomAbs_Line && aCType != GeomAbs_Circle) {
2247
2248           Standard_Boolean reverse = Standard_False;
2249           if (E.Orientation() == TopAbs_FORWARD) reverse = Standard_True;
2250
2251           gp_Pnt2d P, Pc;
2252           gp_Dir2d N;
2253
2254           Geom2dLProp_CLProps2d aCLProps(G2d, 2, eps);
2255
2256           aCLProps.SetParameter(f);
2257           if(!aCLProps.IsTangentDefined()) {
2258             BadEdges.Append(SE);
2259             aMap.Add(SE);
2260             continue;
2261           }
2262
2263           P = aCLProps.Value();
2264           Standard_Real Crv = aCLProps.Curvature();
2265
2266           if(Crv >= eps) {
2267             aCLProps.Tangent(N);
2268             Standard_Real x = N.Y(), y = -N.X();
2269             N.SetCoord(x, y);
2270             if (reverse) N.Reverse();
2271             aCLProps.CentreOfCurvature(Pc);
2272             gp_Vec2d Dir( P, Pc );
2273             if (N.Dot(Dir) > 0.) {
2274               if (LimCurv <= Crv + eps) {
2275                 BadEdges.Append(SE);
2276                 aMap.Add(SE);
2277                 continue;
2278               }
2279             }
2280           }  
2281
2282           aCLProps.SetParameter(l);
2283           if(!aCLProps.IsTangentDefined()) {
2284             BadEdges.Append(SE);
2285             aMap.Add(SE);
2286             continue;
2287           }
2288
2289           P = aCLProps.Value();
2290           Crv = aCLProps.Curvature();
2291
2292           if(Crv >= eps) {
2293             aCLProps.Tangent(N);
2294             Standard_Real x = N.Y(), y = -N.X();
2295             N.SetCoord(x, y);
2296             if (reverse) N.Reverse();
2297             aCLProps.CentreOfCurvature(Pc);
2298             gp_Vec2d Dir( P, Pc );
2299             if (N.Dot(Dir) > 0.) {
2300               if (LimCurv <= Crv + eps) {
2301                 BadEdges.Append(SE);
2302                 aMap.Add(SE);
2303                 continue;
2304               }
2305             }
2306           }  
2307         }
2308       }
2309     }
2310   }
2311 }
2312
2313
2314 //=======================================================================
2315 //function : PerformCurve
2316 //purpose  : 
2317 //=======================================================================
2318
2319 static Standard_Boolean PerformCurve (TColStd_SequenceOfReal& Parameters,
2320                                       TColgp_SequenceOfPnt&   Points,
2321                                       const Adaptor3d_Curve& C, 
2322                                       const Standard_Real Deflection,
2323                                       const Standard_Real U1,
2324                                       const Standard_Real U2,
2325                                       const Standard_Real EPSILON,
2326                                       const Standard_Integer Nbmin)
2327 {
2328   Standard_Real UU1 = Min(U1, U2);
2329   Standard_Real UU2 = Max(U1, U2);
2330
2331   gp_Pnt Pdeb, Pfin;
2332   gp_Vec Ddeb,Dfin;
2333   C.D1(UU1,Pdeb,Ddeb);
2334   Parameters.Append(UU1);
2335   Points.Append(Pdeb);
2336
2337   C.D1(UU2,Pfin,Dfin);
2338
2339   const Standard_Real aDelta = UU2 - UU1;
2340   const Standard_Real aDist = Pdeb.Distance(Pfin);
2341
2342   if((aDelta/aDist) > 5.0e-14)
2343   {
2344     QuasiFleche(C,Deflection*Deflection,
2345                       UU1,Pdeb,
2346                       Ddeb,
2347                       UU2,Pfin,
2348                       Dfin,
2349                       Nbmin,
2350                       EPSILON*EPSILON,
2351                       Parameters,Points);
2352   }
2353
2354   return Standard_True;
2355 }
2356 //=======================================================================
2357 //function : QuasiFleche
2358 //purpose  : 
2359 //=======================================================================
2360
2361 static void QuasiFleche(const Adaptor3d_Curve& C,
2362                         const Standard_Real Deflection2, 
2363                         const Standard_Real Udeb,
2364                         const gp_Pnt& Pdeb,
2365                         const gp_Vec& Vdeb,
2366                         const Standard_Real Ufin,
2367                         const gp_Pnt& Pfin,
2368                         const gp_Vec& Vfin,
2369                         const Standard_Integer Nbmin,
2370                         const Standard_Real Eps,
2371                         TColStd_SequenceOfReal& Parameters,
2372                         TColgp_SequenceOfPnt& Points)
2373 {
2374   Standard_Integer Ptslength = Points.Length();
2375   Standard_Real Udelta = Ufin-Udeb;
2376   gp_Pnt Pdelta;
2377   gp_Vec Vdelta;
2378   if (Nbmin > 2) {
2379     Udelta /=(Nbmin-1);
2380     C.D1(Udeb+Udelta,Pdelta,Vdelta);
2381   }
2382   else {
2383     Pdelta = Pfin;
2384     Vdelta = Vfin;
2385   }
2386
2387
2388   Standard_Real Norme = gp_Vec(Pdeb,Pdelta).SquareMagnitude();
2389   Standard_Real theFleche=0;
2390   Standard_Boolean flecheok = Standard_False;
2391   if (Norme > Eps) { 
2392     // Evaluation of the arrow by interpolation. See IntWalk_IWalking_5.gxx
2393     Standard_Real N1 = Vdeb.SquareMagnitude();
2394     Standard_Real N2 = Vdelta.SquareMagnitude();
2395     if (N1 > Eps && N2 > Eps) {
2396       Standard_Real Normediff = 
2397         (Vdeb.Normalized().XYZ()-Vdelta.Normalized().XYZ()).SquareModulus();
2398       if (Normediff > Eps) {
2399         theFleche = Normediff*Norme/64.;
2400         flecheok = Standard_True;
2401       }
2402     }
2403   }
2404   if (!flecheok) {
2405     gp_Pnt Pmid((Pdeb.XYZ()+Pdelta.XYZ())/2.);
2406     gp_Pnt Pverif(C.Value(Udeb+Udelta/2.));
2407     theFleche = Pmid.SquareDistance(Pverif);
2408   }
2409
2410   if (theFleche < Deflection2) {
2411     Parameters.Append(Udeb+Udelta);
2412     Points.Append(Pdelta);
2413   }
2414   else {
2415     QuasiFleche(C,Deflection2,Udeb,Pdeb,
2416                 Vdeb,
2417                 Udeb+Udelta,Pdelta,
2418                 Vdelta,
2419                 3,
2420                 Eps,
2421                 Parameters,Points);
2422
2423   }
2424
2425   if (Nbmin > 2) {
2426     QuasiFleche(C,Deflection2,Udeb+Udelta,Pdelta,
2427                 Vdelta,
2428                 Ufin,Pfin,
2429                 Vfin,
2430                 Nbmin-(Points.Length()-Ptslength),
2431                 Eps,
2432                 Parameters,Points);
2433   }
2434 }
2435