a18ba9a32695baa1430865172ebd4873c315b587
[occt.git] / src / BRepOffsetAPI / BRepOffsetAPI_MiddlePath.cxx
1 // Created on: 2012-08-06
2 // Created by: jgv@ROLEX
3 // Copyright (c) 2012-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #include <BRepOffsetAPI_MiddlePath.ixx>
17 #include <BRepOffsetAPI_MiddlePath.hxx>
18
19 #include <ShapeUpgrade_UnifySameDomain.hxx>
20
21 #include <gp_Lin.hxx>
22 #include <Geom_Curve.hxx>
23 #include <Geom_TrimmedCurve.hxx>
24 #include <Geom_Line.hxx>
25 #include <Geom_BezierCurve.hxx>
26 #include <Geom_BSplineCurve.hxx>
27 #include <BRep_Tool.hxx>
28 #include <gce_MakeLin.hxx>
29
30 #include <BRepLib_MakeWire.hxx>
31
32 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
33 #include <TopTools_MapIteratorOfMapOfShape.hxx>
34 #include <TopExp.hxx>
35 #include <TopTools_ListIteratorOfListOfShape.hxx>
36 #include <TopoDS.hxx>
37 #include <BRepTools.hxx>
38 #include <TopTools_SequenceOfShape.hxx>
39 #include <BRepTools_WireExplorer.hxx>
40 #include <TopoDS_Iterator.hxx>
41 #include <BRep_Builder.hxx>
42 #include <Precision.hxx>
43 #include <TopExp_Explorer.hxx>
44 #include <BRepExtrema_DistShapeShape.hxx>
45 #include <Geom2d_Curve.hxx>
46 #include <Geom2d_Line.hxx>
47 #include <GCE2d_MakeLine.hxx>
48 #include <BRepLib_MakeEdge.hxx>
49 #include <BRepLib.hxx>
50 #include <GeomAbs_CurveType.hxx>
51 #include <BRepAdaptor_Curve.hxx>
52 #include <TopTools_Array1OfShape.hxx>
53 #include <BRepLib_MakeFace.hxx>
54 #include <TColgp_Array1OfPnt.hxx>
55 #include <TColgp_HArray1OfPnt.hxx>
56 #include <TColgp_Array1OfVec.hxx>
57 #include <TColStd_HArray1OfBoolean.hxx>
58 #include <GProp_GProps.hxx>
59 #include <BRepGProp.hxx>
60 #include <Geom_Circle.hxx>
61 #include <gp_Circ.hxx>
62 #include <GC_MakeCircle.hxx>
63 #include <TColgp_SequenceOfPnt.hxx>
64 #include <GeomLib.hxx>
65 #include <GeomAPI_Interpolate.hxx>
66
67 static Standard_Boolean IsLinear(const TopoDS_Edge& anEdge,
68                                  gp_Lin& aLine)
69 {
70   Standard_Real fpar, lpar;
71   Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
72   if (aCurve->IsInstance(STANDARD_TYPE(Geom_TrimmedCurve)))
73     aCurve = ((Handle(Geom_TrimmedCurve)&) aCurve)->BasisCurve();
74
75   gp_Pnt Pnt1, Pnt2;
76   if (aCurve->IsKind(STANDARD_TYPE(Geom_Line)))
77   {
78     aLine = ((Handle(Geom_Line)&) aCurve)->Lin();
79     return Standard_True;
80   }
81   else if (aCurve->IsKind(STANDARD_TYPE(Geom_BezierCurve)))
82   {
83     Handle(Geom_BezierCurve) theBezier = (Handle(Geom_BezierCurve)&) aCurve;
84     if (theBezier->NbPoles() == 2)
85     {
86       Pnt1 = theBezier->Pole(1);
87       Pnt2 = theBezier->Pole(2);
88       aLine = gce_MakeLin(Pnt1, Pnt2);
89       return Standard_True;
90     }
91   }
92   else if (aCurve->IsKind(STANDARD_TYPE(Geom_BSplineCurve)))
93   {
94     Handle(Geom_BSplineCurve) theBSpline = (Handle(Geom_BSplineCurve)&) aCurve;
95     if (theBSpline->NbPoles() == 2)
96     {
97       Pnt1 = theBSpline->Pole(1);
98       Pnt2 = theBSpline->Pole(2);
99       aLine = gce_MakeLin(Pnt1, Pnt2);
100       return Standard_True;
101     }
102   }
103
104   return Standard_False;
105 }
106
107 static GeomAbs_CurveType TypeOfEdge(const TopoDS_Edge& anEdge)
108 {
109   gp_Lin aLin;
110   if (IsLinear(anEdge, aLin))
111     return GeomAbs_Line;
112
113   BRepAdaptor_Curve BAcurve(anEdge);
114   return BAcurve.GetType();
115 }
116
117 static gp_Vec TangentOfEdge(const TopoDS_Shape& aShape,
118                             const Standard_Boolean OnFirst)
119 {
120   TopoDS_Edge anEdge = TopoDS::Edge(aShape);
121   TopAbs_Orientation anOr = anEdge.Orientation();
122   
123   Standard_Real fpar, lpar;
124   Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
125   Standard_Real thePar;
126   if (OnFirst)
127     thePar = (anOr == TopAbs_FORWARD)? fpar : lpar;
128   else
129     thePar = (anOr == TopAbs_FORWARD)? lpar : fpar;
130
131   gp_Pnt thePoint;
132   gp_Vec theTangent;
133   aCurve->D1(thePar, thePoint, theTangent);
134   if (anOr == TopAbs_REVERSED)
135     theTangent.Reverse();
136
137   return theTangent;
138 }
139
140
141 static Standard_Boolean IsValidEdge(const TopoDS_Edge& theEdge,
142                                     const TopoDS_Face& theFace)
143 {
144   TopoDS_Vertex V1, V2;
145   TopExp::Vertices(theEdge, V1, V2);
146
147   Standard_Real Tol = Precision::Confusion();
148   Standard_Integer i;
149   
150   TopExp_Explorer Explo(theFace, TopAbs_EDGE);
151   for (; Explo.More(); Explo.Next())
152   {
153     const TopoDS_Shape& anEdge = Explo.Current();
154     BRepExtrema_DistShapeShape DistMini(theEdge, anEdge);
155     if (DistMini.Value() <= Tol)
156     {
157       for (i = 1; i <= DistMini.NbSolution(); i++)
158       {
159         BRepExtrema_SupportType theType = DistMini.SupportTypeShape2(i);
160         if (theType == BRepExtrema_IsOnEdge)
161           return Standard_False;
162         //theType is "IsVertex"
163         TopoDS_Shape aVertex = DistMini.SupportOnShape2(i);
164         if (!(aVertex.IsSame(V1) || aVertex.IsSame(V2)))
165           return Standard_False;
166       }
167     }
168   }
169
170   return Standard_True;
171 }
172
173 /*
174 //=======================================================================
175 //function : BRepOffsetAPI_MiddlePath
176 //purpose  : Constructor
177 //=======================================================================
178
179 BRepOffsetAPI_MiddlePath::BRepOffsetAPI_MiddlePath(const TopoDS_Shape& aShape,
180                                                    const TopoDS_Wire&  StartWire)
181 {
182   myInitialShape = aShape;
183   myStartWire    = StartWire;
184   myClosedSection = myStartWire.Closed();
185 }
186
187 //=======================================================================
188 //function : BRepOffsetAPI_MiddlePath
189 //purpose  : Constructor
190 //=======================================================================
191
192 BRepOffsetAPI_MiddlePath::BRepOffsetAPI_MiddlePath(const TopoDS_Shape& aShape,
193                                                    const TopoDS_Edge&  StartEdge)
194 {
195   myInitialShape = aShape;
196
197   BRepLib_MakeWire MW(StartEdge);
198   
199   //BB.Add(myStartWire, StartEdge);
200
201   TopTools_IndexedDataMapOfShapeListOfShape EFmap;
202   TopTools_IndexedDataMapOfShapeListOfShape VEmap;
203   TopExp::MapShapesAndAncestors(myInitialShape, TopAbs_EDGE,   TopAbs_FACE, EFmap);
204   TopExp::MapShapesAndAncestors(myInitialShape, TopAbs_VERTEX, TopAbs_EDGE, VEmap);
205   
206   //Standard_Boolean Start = Standard_True;
207   //if (Start)
208   //{
209   //TopExp::Vertices(CurEdge, V1, V2);
210   //  StartVertex = V1;
211   //  CurVertex   = V2;
212   //  if (VEmap(CurVertex).Extent() == 2) //end: two free edges
213   //  {
214   //    StartVertex = V2;
215   //    CurVertex   = V1;
216   //    if (VEmap(CurVertex).Extent() == 2) //end: two free edges
217   //      break;
218   //  }
219   //  Start = Standard_False;
220   //  continue;
221   //}
222
223   TopoDS_Vertex StartVertex, CurVertex, V1, V2;
224   TopExp::Vertices(StartEdge, StartVertex, CurVertex);
225   TopoDS_Edge CurEdge = StartEdge;
226   Standard_Integer i;
227   for (i = 1; i <= 2; i++)
228   {
229     for (;;)
230     {
231       const TopTools_ListOfShape& LE = VEmap.FindFromKey(CurVertex);
232       if (LE.Extent() == 2) //end: two free edges or one closed free edge
233         break;
234       TopTools_ListIteratorOfListOfShape itl(LE);
235       TopoDS_Edge anEdge;
236       for (; itl.More(); itl.Next())
237       {
238         anEdge = TopoDS::Edge(itl.Value());
239         if (anEdge.IsSame(CurEdge))
240           continue;
241         if (EFmap.FindFromKey(anEdge).Extent() == 1) //another free edge found
242           break;
243       }
244       //BB.Add(myStartWire, anEdge);
245       MW.Add(anEdge);
246       TopExp::Vertices(anEdge, V1, V2);
247       CurVertex = (V1.IsSame(CurVertex))? V2 : V1;
248       CurEdge = anEdge;
249       if (CurVertex.IsSame(StartVertex))
250         break;
251     }
252     if (CurVertex.IsSame(StartVertex))
253       break;
254     CurVertex = StartVertex;
255     CurEdge = StartEdge;
256   }
257   
258   myStartWire = MW.Wire();
259   myClosedSection = myStartWire.Closed();
260 }
261 */
262
263 //=======================================================================
264 //function : BRepOffsetAPI_MiddlePath
265 //purpose  : Constructor
266 //=======================================================================
267
268 BRepOffsetAPI_MiddlePath::BRepOffsetAPI_MiddlePath(const TopoDS_Shape& aShape,
269                                                    const TopoDS_Shape& StartShape,
270                                                    const TopoDS_Shape& EndShape)
271 {
272   ShapeUpgrade_UnifySameDomain Unifier(aShape);
273   Unifier.Build();
274   myInitialShape = Unifier.Shape();
275
276   TopoDS_Wire aStartWire, anEndWire;
277   if (StartShape.ShapeType() == TopAbs_FACE)
278   {
279     const TopoDS_Face& StartFace = TopoDS::Face(StartShape);
280     aStartWire = BRepTools::OuterWire(StartFace);
281   }
282   else
283     aStartWire = TopoDS::Wire(StartShape);
284   
285   if (EndShape.ShapeType() == TopAbs_FACE)
286   {
287     const TopoDS_Face& EndFace = TopoDS::Face(EndShape);
288     anEndWire = BRepTools::OuterWire(EndFace);
289   }
290   else
291     anEndWire = TopoDS::Wire(EndShape);
292
293   BRepLib_MakeWire MWstart;
294   //TopTools_MapOfShape MapEdges;
295   BRepTools_WireExplorer wexp(aStartWire);
296   for (; wexp.More(); wexp.Next())
297   {
298     TopoDS_Shape anEdge = wexp.Current();
299     TopoDS_Shape NewEdge = Unifier.Generated(anEdge);
300     if (!NewEdge.IsNull())
301       MWstart.Add(TopoDS::Edge(NewEdge));
302   }
303   myStartWire = MWstart.Wire();
304
305   BRepLib_MakeWire MWend;
306   //MapEdges.Clear();
307   for (wexp.Init(anEndWire); wexp.More(); wexp.Next())
308   {
309     TopoDS_Shape anEdge = wexp.Current();
310     TopoDS_Shape NewEdge = Unifier.Generated(anEdge);
311     if (!NewEdge.IsNull())
312       MWend.Add(TopoDS::Edge(NewEdge));
313   }
314   myEndWire = MWend.Wire();
315
316   myClosedSection = myStartWire.Closed();
317   myClosedRing    = myStartWire.IsSame(myEndWire);
318 }
319
320 //=======================================================================
321 //function : Build
322 //purpose  : 
323 //=======================================================================
324
325 void BRepOffsetAPI_MiddlePath::Build()
326 {
327   TopTools_ListIteratorOfListOfShape itl;
328   
329   TopTools_SequenceOfShape StartVertices;
330   TopTools_MapOfShape EndVertices;
331   TopTools_MapOfShape EndEdges;
332   BRepOffsetAPI_SequenceOfSequenceOfShape SectionsEdges;
333   
334   BRepTools_WireExplorer wexp(myStartWire);
335   TopTools_SequenceOfShape EdgeSeq;
336   for (; wexp.More(); wexp.Next())
337   {
338     StartVertices.Append(wexp.CurrentVertex());
339     EdgeSeq.Append(wexp.Current());
340   }
341   if (!myClosedSection)
342     StartVertices.Append(wexp.CurrentVertex());
343   SectionsEdges.Append(EdgeSeq);
344   
345   for (wexp.Init(myEndWire); wexp.More(); wexp.Next())
346   {
347     EndVertices.Add(wexp.CurrentVertex());
348     EndEdges.Add(wexp.Current());
349   }
350   if (!myClosedSection)
351     EndVertices.Add(wexp.CurrentVertex());
352   
353
354   TopoDS_Iterator itw(myStartWire);
355   for (; itw.More(); itw.Next())
356     myStartWireEdges.Add(itw.Value());
357   for (itw.Initialize(myEndWire); itw.More(); itw.Next())
358     myEndWireEdges.Add(itw.Value());
359
360   TopTools_IndexedDataMapOfShapeListOfShape VEmap;
361   TopTools_IndexedDataMapOfShapeListOfShape EFmap;
362   TopExp::MapShapesAndAncestors(myInitialShape, TopAbs_VERTEX, TopAbs_EDGE, VEmap);
363   TopExp::MapShapesAndAncestors(myInitialShape, TopAbs_EDGE,   TopAbs_FACE, EFmap);
364
365   TopTools_MapOfShape CurVertices;
366   
367   Standard_Integer i, j, k;
368   TopoDS_Edge anEdge;
369   TopoDS_Vertex V1, V2, NextVertex;
370   //Initialization of <myPaths>
371   for (i = 1; i <= StartVertices.Length(); i++)
372   {
373     TopTools_SequenceOfShape Edges;
374     const TopTools_ListOfShape& LE = VEmap.FindFromKey(StartVertices(i));
375     for (itl.Initialize(LE); itl.More(); itl.Next())
376     {
377       anEdge = TopoDS::Edge(itl.Value());
378       if (!myStartWireEdges.Contains(anEdge))
379       {
380         TopExp::Vertices(anEdge, V1, V2, Standard_True);
381         if (V1.IsSame(StartVertices(i)))
382           CurVertices.Add(V2);
383         else
384         {
385           anEdge.Reverse();
386           CurVertices.Add(V1);
387         }
388         Edges.Append(anEdge);
389         break;
390       }
391     }
392     if (!Edges.IsEmpty())
393       myPaths.Append(Edges);
394     else
395       return;
396   }
397
398   //Filling of "myPaths"
399   TopTools_ListOfShape NextVertices;
400   for (;;)
401   {
402     for (i = 1; i <= myPaths.Length(); i++)
403     {
404       const TopoDS_Shape& theShape = myPaths(i).Last();
405       TopoDS_Edge theEdge;
406       TopoDS_Vertex theVertex;
407       if (theShape.ShapeType() == TopAbs_EDGE)
408       {
409         theEdge = TopoDS::Edge(theShape);
410         theVertex = TopExp::LastVertex(theEdge, Standard_True);
411       }
412       else //last segment of path was punctual
413       {
414         theEdge = TopoDS::Edge(myPaths(i)(myPaths(i).Length()-1));
415         theVertex = TopoDS::Vertex(theShape);
416       }
417       
418       if (EndVertices.Contains(theVertex))
419         continue;
420       const TopTools_ListOfShape& LE = VEmap.FindFromKey(theVertex);
421       TopTools_MapOfShape NextEdgeCandidates;
422       for (itl.Initialize(LE); itl.More(); itl.Next())
423       {
424         anEdge = TopoDS::Edge(itl.Value());
425         if (anEdge.IsSame(theEdge))
426           continue;
427         TopExp::Vertices(anEdge, V1, V2, Standard_True);
428         if (V1.IsSame(theVertex))
429           NextVertex = V2;
430         else
431         {
432           anEdge.Reverse();
433           NextVertex = V1;
434         }
435         if (!CurVertices.Contains(NextVertex))
436           NextEdgeCandidates.Add(anEdge);
437       }
438       if (!NextEdgeCandidates.IsEmpty())
439       {
440         if (NextEdgeCandidates.Extent() > 1)
441           myPaths(i).Append(theVertex); //punctual segment of path
442         else
443         {
444           TopTools_MapIteratorOfMapOfShape mapit(NextEdgeCandidates);
445           anEdge = TopoDS::Edge(mapit.Key());
446           myPaths(i).Append(anEdge);
447           NextVertex = TopExp::LastVertex(anEdge, Standard_True);
448           NextVertices.Append(NextVertex);
449         }
450       }
451     }
452     if (NextVertices.IsEmpty())
453       break;
454     for (itl.Initialize(NextVertices); itl.More(); itl.Next())
455       CurVertices.Add(itl.Value());
456     NextVertices.Clear();
457   }
458
459   //Temporary
460   /*
461   TopoDS_Compound aCompound, aCmp1;
462   BRep_Builder BB;
463   BB.MakeCompound(aCompound);
464   BB.MakeCompound(aCmp1);
465   for (i = 1; i <= myPaths.Length(); i++)
466   {
467     TopoDS_Compound aCmp;
468     BB.MakeCompound(aCmp);
469     for (j = 1; j <= myPaths(i).Length(); j++)
470       BB.Add(aCmp, myPaths(i)(j));
471     BB.Add(aCmp1, aCmp);
472   }
473   BB.Add(aCompound, aCmp1);
474          
475   myShape = aCompound;
476
477   Done();
478   return;
479   */
480   ////////////
481   
482   //Building of set of sections
483   Standard_Integer NbE = EdgeSeq.Length();
484   Standard_Integer NbPaths = myPaths.Length();
485   Standard_Integer NbVer = myPaths.Length();
486   if (myClosedSection)
487     NbVer++;
488   i = 1;
489   for (;;)
490   {
491     for (j = 1; j <= EdgeSeq.Length(); j++)
492       EdgeSeq(j).Nullify();
493
494     Standard_Boolean ToInsertVertex = Standard_False;
495     
496     for (j = 2; j <= NbVer; j++)
497     {
498       if (!EdgeSeq(j-1).IsNull())
499         continue;
500
501       //for the end of initial shape
502       if (myPaths(j-1).Length() < i)
503       {
504         TopoDS_Edge aE1 = TopoDS::Edge(myPaths(j-1)(i-1));
505         TopoDS_Shape LastVer = TopExp::LastVertex(aE1, Standard_True);
506         myPaths(j-1).Append(LastVer);
507       }
508       if (myPaths((j<=NbPaths)? j : 1).Length() < i)
509       {
510         TopoDS_Edge aE2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i-1));
511         TopoDS_Shape LastVer = TopExp::LastVertex(aE2, Standard_True);
512         myPaths((j<=NbPaths)? j : 1).Append(LastVer);
513       }
514       //////////////////////////////
515       
516       if (ToInsertVertex)
517       {
518         if (myPaths(j-1)(i).ShapeType() == TopAbs_EDGE)
519         {
520           TopoDS_Edge aE1 = TopoDS::Edge(myPaths(j-1)(i));
521           TopoDS_Shape fver = TopExp::FirstVertex(aE1, Standard_True);
522           myPaths(j-1).InsertBefore(i, fver);
523         }
524         if (myPaths((j<=NbPaths)? j : 1)(i).ShapeType() == TopAbs_EDGE)
525         {
526           TopoDS_Edge aE2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i));
527           TopoDS_Shape fver = TopExp::FirstVertex(aE2, Standard_True);
528           myPaths((j<=NbPaths)? j : 1).InsertBefore(i, fver);
529         }
530         ToInsertVertex = Standard_False;
531       }
532       
533       TopoDS_Edge E1, E2;
534       if (myPaths(j-1)(i).ShapeType() == TopAbs_EDGE)
535         E1 = TopoDS::Edge(myPaths(j-1)(i));
536       if (myPaths((j<=NbPaths)? j : 1)(i).ShapeType() == TopAbs_EDGE)
537         E2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i));
538       TopoDS_Edge E12 = TopoDS::Edge(SectionsEdges(i)(j-1));
539       //Find the face on which (E1 or E2) and E12 lie
540       TopoDS_Shape E1orE2 = (E1.IsNull())? E2 : E1;
541       if (E1orE2.IsNull()) //both E1 and E2 are vertices =>
542       {
543         EdgeSeq(j-1) = E12; // => proper edge is the edge of previous section between them
544         continue;
545       }
546       const TopTools_ListOfShape& LF = EFmap.FindFromKey(E1orE2);
547       TopoDS_Face theFace;
548       for (itl.Initialize(LF); itl.More(); itl.Next())
549       {
550         const TopoDS_Shape& aFace = itl.Value();
551         const TopTools_ListOfShape& LF2 = EFmap.FindFromKey(E12);
552         TopTools_ListIteratorOfListOfShape itl2(LF2);
553         for (; itl2.More(); itl2.Next())
554         {
555           const TopoDS_Shape& aFace2 = itl2.Value();
556           if (aFace.IsSame(aFace2))
557           {
558             theFace = TopoDS::Face(aFace);
559             break;
560           }
561         }
562         if (!theFace.IsNull())
563           break;
564       }
565       
566       TopoDS_Vertex PrevVertex = (E1.IsNull())? TopoDS::Vertex(myPaths(j-1)(i))
567         : TopExp::LastVertex(E1, Standard_True);
568       TopoDS_Vertex CurVertex = (E2.IsNull())? TopoDS::Vertex(myPaths((j<=NbPaths)? j : 1)(i))
569         : TopExp::LastVertex(E2, Standard_True);
570       
571       TopoDS_Edge ProperEdge;
572       const TopTools_ListOfShape& LE = VEmap.FindFromKey(PrevVertex);
573       //Temporary
574       //Standard_Integer LenList = LE.Extent();
575       ///////////
576       TopTools_IndexedMapOfShape EdgesOfTheFace;
577       TopExp::MapShapes(theFace, TopAbs_EDGE, EdgesOfTheFace);
578       for (itl.Initialize(LE); itl.More(); itl.Next())
579       {
580         anEdge = TopoDS::Edge(itl.Value());
581         TopExp::Vertices(anEdge, V1, V2);
582         if (((V1.IsSame(PrevVertex) && V2.IsSame(CurVertex)) ||
583              (V1.IsSame(CurVertex) && V2.IsSame(PrevVertex))) &&
584             EdgesOfTheFace.Contains(anEdge) && //this condition is for a section of two edges
585             !anEdge.IsSame(E1)) //the last condition is for torus-like shape
586         {
587           ProperEdge = anEdge;
588           break;
589         }
590       }
591       
592       if ((myPaths(j-1)(i)).ShapeType() == TopAbs_VERTEX &&
593           (myPaths((j<=NbPaths)? j : 1)(i)).ShapeType() == TopAbs_VERTEX)
594       {
595         EdgeSeq(j-1) = ProperEdge;
596         continue;
597       }
598
599       TopoDS_Vertex PrevPrevVer = (E1.IsNull())? PrevVertex
600         : TopExp::FirstVertex(E1, Standard_True);
601       TopoDS_Vertex PrevCurVer  = (E2.IsNull())? CurVertex
602         : TopExp::FirstVertex(E2, Standard_True);
603       if (ProperEdge.IsNull()) //no connection between these two vertices
604       {
605         //Find the face on which E1, E2 and E12 lie
606         //ToInsertVertex = Standard_False;
607         TopTools_ListOfShape ListOneFace;
608         ListOneFace.Append(theFace);
609
610         if (E1.IsNull() || E2.IsNull())
611         {
612           if (E1.IsNull())
613             E1 = TopoDS::Edge(myPaths(j-1)(i-1));
614           if (E2.IsNull())
615             E2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i-1));
616           Standard_Real fpar1, lpar1, fpar2, lpar2;
617           Standard_Real LastPar1, LastPar2;
618           Handle(Geom2d_Curve) PCurve1 = BRep_Tool::CurveOnSurface(E1, theFace, fpar1, lpar1);
619           Handle(Geom2d_Curve) PCurve2 = BRep_Tool::CurveOnSurface(E2, theFace, fpar2, lpar2);
620           if (E1.Orientation() == TopAbs_FORWARD)
621           { LastPar1 = lpar1; }
622           else
623           { LastPar1 = fpar1; }
624           if (E2.Orientation() == TopAbs_FORWARD)
625           { LastPar2 = lpar2; }
626           else
627           { LastPar2 = fpar2; }
628           gp_Pnt2d FirstPnt2d = PCurve1->Value(LastPar1);
629           gp_Pnt2d LastPnt2d  = PCurve2->Value(LastPar2);
630           Handle(Geom_Surface) theSurf = BRep_Tool::Surface(theFace);
631           Handle(Geom2d_Line) theLine = GCE2d_MakeLine(FirstPnt2d, LastPnt2d);
632           Standard_Real len_ne = FirstPnt2d.Distance(LastPnt2d);
633           TopoDS_Edge NewEdge = BRepLib_MakeEdge(theLine, theSurf,
634                                                  PrevVertex, CurVertex,
635                                                  0., len_ne);
636           BRepLib::BuildCurve3d(NewEdge);
637           EdgeSeq(j-1) = NewEdge;
638           EFmap.Add(NewEdge, ListOneFace);
639         }
640         else //E1 is edge
641         {
642           //Extract points 2d
643           Standard_Real fpar1, lpar1, fpar2, lpar2;
644           Standard_Real FirstPar1, LastPar1, FirstPar2, LastPar2;
645           Handle(Geom2d_Curve) PCurve1 = BRep_Tool::CurveOnSurface(E1, theFace, fpar1, lpar1);
646           Handle(Geom2d_Curve) PCurve2 = BRep_Tool::CurveOnSurface(E2, theFace, fpar2, lpar2);
647           if (E1.Orientation() == TopAbs_FORWARD)
648           { FirstPar1 = fpar1; LastPar1 = lpar1; }
649           else
650           { FirstPar1 = lpar1; LastPar1 = fpar1; }
651           if (E2.Orientation() == TopAbs_FORWARD)
652           { FirstPar2 = fpar2; LastPar2 = lpar2; }
653           else
654           { FirstPar2 = lpar2; LastPar2 = fpar2; }
655           gp_Pnt2d FirstPnt2d = PCurve1->Value(LastPar1);
656           gp_Pnt2d LastPnt2d  = PCurve2->Value(LastPar2);
657           Handle(Geom_Surface) theSurf = BRep_Tool::Surface(theFace);
658           Handle(Geom2d_Line) theLine = GCE2d_MakeLine(FirstPnt2d, LastPnt2d);
659           Standard_Real len_ne = FirstPnt2d.Distance(LastPnt2d);
660           TopoDS_Edge NewEdge = BRepLib_MakeEdge(theLine, theSurf,
661                                                  PrevVertex, CurVertex,
662                                                  0., len_ne);
663           BRepLib::BuildCurve3d(NewEdge);
664           gp_Pnt2d PrevFirstPnt2d = PCurve1->Value(FirstPar1);
665           gp_Pnt2d PrevLastPnt2d  = PCurve2->Value(FirstPar2);
666           Handle(Geom2d_Line) Line1 = GCE2d_MakeLine(PrevFirstPnt2d, LastPnt2d);
667           Handle(Geom2d_Line) Line2 = GCE2d_MakeLine(FirstPnt2d, PrevLastPnt2d);
668           Standard_Real len_ne1 = PrevFirstPnt2d.Distance(LastPnt2d);
669           TopoDS_Edge NewEdge1 = BRepLib_MakeEdge(Line1, theSurf,
670                                                   PrevPrevVer, CurVertex,
671                                                   0., len_ne1);
672           BRepLib::BuildCurve3d(NewEdge1);
673           Standard_Real len_ne2 = FirstPnt2d.Distance(PrevLastPnt2d);
674           TopoDS_Edge NewEdge2 = BRepLib_MakeEdge(Line2, theSurf,
675                                                   PrevVertex, PrevCurVer,
676                                                   0., len_ne2);
677           BRepLib::BuildCurve3d(NewEdge2);
678           Standard_Boolean good_ne  = IsValidEdge(NewEdge, theFace);
679           Standard_Boolean good_ne1 = IsValidEdge(NewEdge1, theFace);
680
681           GeomAbs_CurveType type_E1 = TypeOfEdge(E1);
682           GeomAbs_CurveType type_E2 = TypeOfEdge(E2);
683
684           Standard_Integer ChooseEdge = 0;
685           
686           if (!good_ne || type_E1 != type_E2)
687           {
688             if (type_E1 == type_E2) //!good_ne
689             {
690               if (good_ne1)
691                 ChooseEdge = 1;
692               else
693                 ChooseEdge = 2;
694             }
695             else //types are different
696             {
697               if (type_E1 == GeomAbs_Line)
698                 ChooseEdge = 1;
699               else if (type_E2 == GeomAbs_Line)
700                 ChooseEdge = 2;
701               else //to be developed later...
702               {}
703             }
704           }
705           
706           if (ChooseEdge == 0)
707           {
708             EdgeSeq(j-1) = NewEdge;
709             EFmap.Add(NewEdge, ListOneFace);
710           }
711           else if (ChooseEdge == 1)
712           {
713             EdgeSeq(j-1) = NewEdge1;
714             EFmap.Add(NewEdge1, ListOneFace);
715             for (k = 1; k < j-1; k++)
716               EdgeSeq(k).Nullify();
717             for (k = 1; k <= j-1; k++)
718             {
719               TopoDS_Edge aLastEdge = TopoDS::Edge(myPaths(k)(i));
720               TopoDS_Shape VertexAsEdge = TopExp::FirstVertex(aLastEdge, Standard_True);
721               myPaths(k).InsertBefore(i, VertexAsEdge);
722             }
723             j = 1; //start from beginning
724           }
725           else if (ChooseEdge == 2)
726           {
727             EdgeSeq(j-1) = NewEdge2;
728             EFmap.Add(NewEdge2, ListOneFace);
729             ToInsertVertex = Standard_True;
730           }
731         } //else //E1 is edge
732       } //if (ProperEdge.IsNull())
733       else //connecting edge exists
734       {
735         /*
736         if (ToInsertVertex)
737         {
738           myPaths(j-1).InsertBefore(i, PrevPrevVer);
739           myPaths((j<=NbPaths)? j : 1).InsertBefore(i, PrevCurVer);
740           EdgeSeq(j-1) = E12;
741         }
742         else
743         */
744           EdgeSeq(j-1) = ProperEdge;
745       }
746     } //for (j = 2; j <= NbVer; j++)
747     SectionsEdges.Append(EdgeSeq);
748
749     //check for exit from for(;;)
750     Standard_Integer NbEndEdges = 0;
751     for (j = 1; j <= EdgeSeq.Length(); j++)
752       if (EndEdges.Contains(EdgeSeq(j)))
753         NbEndEdges++;
754     if (NbEndEdges == NbE)
755       break;
756     
757     i++;
758   } //for (;;)
759   
760
761   //final phase: building of middle path
762   Standard_Integer NbSecFaces = SectionsEdges.Length();
763   TopTools_Array1OfShape SecFaces(1, NbSecFaces);
764   for (i = 1; i <= NbSecFaces; i++)
765   {
766     BRepLib_MakeWire MW;
767     for (j = 1; j <= NbE; j++)
768     {
769       anEdge = TopoDS::Edge(SectionsEdges(i)(j));
770       MW.Add(anEdge);
771     }
772     if (!myClosedSection)
773     {
774       TopExp::Vertices(MW.Wire(), V1, V2);
775       anEdge = BRepLib_MakeEdge(V2, V1);
776       MW.Add(anEdge);
777     }
778     TopoDS_Wire aWire = MW.Wire();
779     BRepLib_MakeFace MF(aWire, Standard_True); //Only plane
780     if (MF.IsDone())
781       SecFaces(i) = MF.Face();
782     else
783       SecFaces(i) = aWire;
784   }
785
786   TColgp_Array1OfPnt Centers(1, NbSecFaces);
787   for (i = 1; i <= NbSecFaces; i++)
788   {
789     GProp_GProps Properties;
790     if (SecFaces(i).ShapeType() == TopAbs_FACE)
791       BRepGProp::SurfaceProperties(SecFaces(i), Properties);
792     else //wire
793       BRepGProp::LinearProperties(SecFaces(i), Properties);
794       
795     Centers(i) = Properties.CentreOfMass();
796   }
797
798   TopTools_Array1OfShape MidEdges(1, NbSecFaces-1);
799   Standard_Real LinTol = 1.e-5;
800   Standard_Real AngTol = 1.e-7;
801   gp_Pnt Pnt1, Pnt2;
802   for (i = 1; i < NbSecFaces; i++)
803   {
804     GeomAbs_CurveType TypeOfMidEdge = GeomAbs_OtherCurve;
805     for (j = 1; j <= myPaths.Length(); j++)
806     {
807       const TopoDS_Shape& aShape = myPaths(j)(i);
808       if (aShape.ShapeType() == TopAbs_VERTEX)
809       {
810         TypeOfMidEdge = GeomAbs_OtherCurve;
811         break;
812       }
813       anEdge = TopoDS::Edge(aShape);
814       GeomAbs_CurveType aType = TypeOfEdge(anEdge);
815       if (j == 1)
816         TypeOfMidEdge = aType;
817       else
818       {
819         if (aType != TypeOfMidEdge)
820         {
821           TypeOfMidEdge = GeomAbs_OtherCurve;
822           break;
823         }
824       }
825     }
826     if (TypeOfMidEdge == GeomAbs_Line)
827       MidEdges(i) = BRepLib_MakeEdge(Centers(i), Centers(i+1));
828     else if (TypeOfMidEdge == GeomAbs_Circle)
829     {
830       gp_Ax1 theAxis;
831       gp_Dir theDir1, theDir2;
832       Standard_Real theAngle = 0.;
833       gp_Vec theTangent;
834       Standard_Boolean SimilarArcs = Standard_True;
835       for (j = 1; j <= myPaths.Length(); j++)
836       {
837         anEdge = TopoDS::Edge(myPaths(j)(i));
838         Standard_Real fpar, lpar;
839         Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
840         if (aCurve->IsInstance(STANDARD_TYPE(Geom_TrimmedCurve)))
841           aCurve = ((Handle(Geom_TrimmedCurve)&) aCurve)->BasisCurve();
842         Pnt1 = aCurve->Value(fpar);
843         Pnt2 = aCurve->Value(lpar);
844         Handle(Geom_Circle) aCircle = Handle(Geom_Circle)::DownCast(aCurve);
845         gp_Circ aCirc = aCircle->Circ();
846         if (j == 1)
847         {
848           theAxis = aCirc.Axis();
849           theDir1 = gp_Vec(aCirc.Location(), Pnt1);
850           theDir2 = gp_Vec(aCirc.Location(), Pnt2);
851           theAngle = lpar - fpar;
852           Standard_Real theParam = (anEdge.Orientation() == TopAbs_FORWARD)?
853             fpar : lpar;
854           aCurve->D1(theParam, Pnt1, theTangent);
855           if (anEdge.Orientation() == TopAbs_REVERSED)
856             theTangent.Reverse();
857         }
858         else
859         {
860           gp_Ax1 anAxis = aCirc.Axis();
861           gp_Lin aLin(anAxis);
862           if (!aLin.Contains(theAxis.Location(), LinTol) ||
863               !anAxis.IsParallel(theAxis, AngTol))
864           {
865             SimilarArcs = Standard_False;
866             break;
867           }
868           gp_Dir aDir1 = gp_Vec(aCirc.Location(), Pnt1);
869           gp_Dir aDir2 = gp_Vec(aCirc.Location(), Pnt2);
870           if (!((aDir1.IsEqual(theDir1, AngTol) && aDir2.IsEqual(theDir2, AngTol)) ||
871                 (aDir1.IsEqual(theDir2, AngTol) && aDir2.IsEqual(theDir1, AngTol))))
872           {
873             SimilarArcs = Standard_False;
874             break;
875           }
876         }
877       }
878       if (SimilarArcs)
879       {
880         gp_XYZ AxisLoc = theAxis.Location().XYZ();
881         gp_XYZ AxisDir = theAxis.Direction().XYZ();
882         Standard_Real Parameter = (Centers(i).XYZ() - AxisLoc) * AxisDir;
883         gp_Pnt theCenterOfCirc(AxisLoc + Parameter*AxisDir);
884         
885         gp_Vec Vec1(theCenterOfCirc, Centers(i));
886         gp_Vec Vec2(theCenterOfCirc, Centers(i+1));
887         /*
888         gp_Dir VecProd = Vec1 ^ Vec2;
889         if (theAxis.Direction() * VecProd < 0.)
890           theAxis.Reverse();
891         */
892         
893         Standard_Real anAngle = Vec1.AngleWithRef(Vec2, theAxis.Direction());
894         if (anAngle < 0.)
895           anAngle += 2.*M_PI;
896         if (Abs(anAngle - theAngle) > AngTol)
897           theAxis.Reverse();
898         gp_Ax2 theAx2(theCenterOfCirc, theAxis.Direction(), Vec1);
899         Handle(Geom_Circle) theCircle = GC_MakeCircle(theAx2, Vec1.Magnitude());
900         gp_Vec aTangent;
901         theCircle->D1( 0., Pnt1, aTangent );
902         if (aTangent * theTangent < 0.)
903         {
904           theAxis.Reverse();
905           theAx2 = gp_Ax2(theCenterOfCirc, theAxis.Direction(), Vec1);
906           theCircle = GC_MakeCircle(theAx2, Vec1.Magnitude());
907         }
908         BRepLib_MakeEdge aME (theCircle, 0., theAngle);
909         aME.Build();
910
911         MidEdges(i) = aME.IsDone() ? 
912           aME.Shape() : 
913           TopoDS_Edge();
914       }
915     }
916   }
917
918   //Build missed edges
919   for (i = 1; i < NbSecFaces; i++)
920   {
921     if (MidEdges(i).IsNull())
922     {
923       for (j = i+1; j < NbSecFaces; j++)
924       {
925         if (!MidEdges(j).IsNull())
926           break;
927       }
928       //from i to j-1 all edges are null
929       Handle(TColgp_HArray1OfPnt) thePoints = new TColgp_HArray1OfPnt(1, j-i+1);
930       TColgp_Array1OfVec theTangents(1, j-i+1);
931       Handle(TColStd_HArray1OfBoolean) theFlags = new TColStd_HArray1OfBoolean(1, j-i+1);
932       for (k = i; k <= j; k++)
933         thePoints->SetValue(k-i+1, Centers(k));
934       for (k = i; k <= j; k++)
935       {
936         TColgp_SequenceOfPnt PntSeq;
937         for (Standard_Integer indp = 1; indp <= myPaths.Length(); indp++)
938         {
939           gp_Vec aTangent;
940           if (k == i)
941           {
942             if (myPaths(indp)(k).ShapeType() == TopAbs_VERTEX)
943               continue;
944             aTangent = TangentOfEdge(myPaths(indp)(k), Standard_True); //at begin
945           }
946           else if (k == j)
947           {
948             if (myPaths(indp)(k-1).ShapeType() == TopAbs_VERTEX)
949               continue;
950             aTangent = TangentOfEdge(myPaths(indp)(k-1), Standard_False); //at end
951           }
952           else
953           {
954             if (myPaths(indp)(k-1).ShapeType() == TopAbs_VERTEX ||
955                 myPaths(indp)(k).ShapeType() == TopAbs_VERTEX)
956               continue;
957             gp_Vec Tangent1 = TangentOfEdge(myPaths(indp)(k-1), Standard_False); //at end
958             gp_Vec Tangent2 = TangentOfEdge(myPaths(indp)(k), Standard_True); //at begin
959             aTangent = Tangent1 + Tangent2;
960           }
961           aTangent.Normalize();
962           gp_Pnt aPnt(aTangent.XYZ());
963           PntSeq.Append(aPnt);
964         }
965         TColgp_Array1OfPnt PntArray(1, PntSeq.Length());
966         for (Standard_Integer ip = 1; ip <= PntSeq.Length(); ip++)
967           PntArray(ip) = PntSeq(ip);
968         gp_Pnt theBary;
969         gp_Dir xdir, ydir;
970         Standard_Real xgap, ygap, zgap;
971         GeomLib::Inertia(PntArray, theBary, xdir, ydir, xgap, ygap, zgap);
972         gp_Vec theTangent(theBary.XYZ());
973         theTangents(k-i+1) = theTangent;
974       }
975       theFlags->Init(Standard_True);
976
977       GeomAPI_Interpolate Interpol(thePoints, Standard_False, LinTol);
978       Interpol.Load(theTangents, theFlags);
979       Interpol.Perform();
980       if (!Interpol.IsDone())
981       {
982         cout<<endl<<"Interpolation failed"<<endl;
983       }
984       Handle(Geom_Curve) InterCurve = Interpol.Curve();
985       MidEdges(i) = BRepLib_MakeEdge(InterCurve);
986       i = j;
987     }
988   }  
989
990   BRepLib_MakeWire MakeFinalWire;
991   for (i = 1; i < NbSecFaces; i++)
992     if (!MidEdges(i).IsNull())
993       MakeFinalWire.Add(TopoDS::Edge(MidEdges(i)));
994
995   TopoDS_Wire FinalWire = MakeFinalWire.Wire();
996   myShape = MakeFinalWire.Wire();
997   
998   //Temporary
999   /*
1000   TopoDS_Compound aCompound, aCmp1, aCmp2;
1001   BRep_Builder BB;
1002   BB.MakeCompound(aCompound);
1003   BB.MakeCompound(aCmp1);
1004   BB.MakeCompound(aCmp2);
1005   for (i = 1; i <= myPaths.Length(); i++)
1006   {
1007     TopoDS_Compound aCmp;
1008     BB.MakeCompound(aCmp);
1009     for (j = 1; j <= myPaths(i).Length(); j++)
1010       BB.Add(aCmp, myPaths(i)(j));
1011     BB.Add(aCmp1, aCmp);
1012   }
1013   for (i = 1; i <= SectionsEdges.Length(); i++)
1014   {
1015     TopoDS_Wire aWire;
1016     BB.MakeWire(aWire);
1017     for (j = 1; j <= SectionsEdges(i).Length(); j++)
1018       BB.Add(aWire, SectionsEdges(i)(j));
1019     BB.Add(aCmp2, aWire);
1020   }
1021   BB.Add(aCompound, aCmp1);
1022   BB.Add(aCompound, aCmp2);
1023   BB.Add(aCompound, FinalWire);
1024          
1025   myShape = aCompound;
1026   */
1027   ////////////
1028
1029   Done();
1030 }