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