0028226: Incorrect history support in ShapeUpgrade_UnifySameDomain algorithm
[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& aLSG = theUnifier.Generated(anEdge);
274     // take care of processing the result of Generated() before getting Modified()
275     Standard_Boolean isEmpty = aLSG.IsEmpty();
276     if (!isEmpty) {
277       TopTools_ListIteratorOfListOfShape anIt(aLSG);
278       for (; anIt.More(); anIt.Next()) {
279         const TopoDS_Shape& aShape = anIt.Value();
280         //wire shouldn't contain duplicated generated edges
281         if (aGeneratedEdges.Add(aShape))
282           aWMaker.Add(TopoDS::Edge(aShape));
283       }
284     }
285     const TopTools_ListOfShape& aLSM = theUnifier.Modified(anEdge);
286     if (!aLSM.IsEmpty())
287       aWMaker.Add(aLSM);
288     else if (isEmpty)
289       // no change, put original edge
290       aWMaker.Add(TopoDS::Edge(anEdge));
291   }
292   return aWMaker.Wire();
293 }
294
295 //=======================================================================
296 //function : BRepOffsetAPI_MiddlePath
297 //purpose  : Constructor
298 //=======================================================================
299
300 BRepOffsetAPI_MiddlePath::BRepOffsetAPI_MiddlePath(const TopoDS_Shape& aShape,
301                                                    const TopoDS_Shape& StartShape,
302                                                    const TopoDS_Shape& EndShape)
303 {
304   ShapeUpgrade_UnifySameDomain Unifier(aShape);
305   Unifier.Build();
306   myInitialShape = Unifier.Shape();
307
308   TopoDS_Wire aStartWire, anEndWire;
309   if (StartShape.ShapeType() == TopAbs_FACE)
310   {
311     const TopoDS_Face& StartFace = TopoDS::Face(StartShape);
312     aStartWire = BRepTools::OuterWire(StartFace);
313   }
314   else
315     aStartWire = TopoDS::Wire(StartShape);
316   
317   if (EndShape.ShapeType() == TopAbs_FACE)
318   {
319     const TopoDS_Face& EndFace = TopoDS::Face(EndShape);
320     anEndWire = BRepTools::OuterWire(EndFace);
321   }
322   else
323     anEndWire = TopoDS::Wire(EndShape);
324
325   myStartWire = GetUnifiedWire(aStartWire, Unifier);
326   myEndWire = GetUnifiedWire(anEndWire, Unifier);
327
328   myClosedSection = myStartWire.Closed();
329   myClosedRing    = myStartWire.IsSame(myEndWire);
330 }
331
332 //=======================================================================
333 //function : Build
334 //purpose  : 
335 //=======================================================================
336
337 void BRepOffsetAPI_MiddlePath::Build()
338 {
339   TopTools_ListIteratorOfListOfShape itl;
340   
341   TopTools_SequenceOfShape StartVertices;
342   TopTools_MapOfShape EndVertices;
343   TopTools_MapOfShape EndEdges;
344   BRepOffsetAPI_SequenceOfSequenceOfShape SectionsEdges;
345   
346   BRepTools_WireExplorer wexp(myStartWire);
347   TopTools_SequenceOfShape EdgeSeq;
348   for (; wexp.More(); wexp.Next())
349   {
350     StartVertices.Append(wexp.CurrentVertex());
351     EdgeSeq.Append(wexp.Current());
352   }
353   if (!myClosedSection)
354     StartVertices.Append(wexp.CurrentVertex());
355   SectionsEdges.Append(EdgeSeq);
356   
357   for (wexp.Init(myEndWire); wexp.More(); wexp.Next())
358   {
359     EndVertices.Add(wexp.CurrentVertex());
360     EndEdges.Add(wexp.Current());
361   }
362   if (!myClosedSection)
363     EndVertices.Add(wexp.CurrentVertex());
364   
365
366   TopoDS_Iterator itw(myStartWire);
367   for (; itw.More(); itw.Next())
368     myStartWireEdges.Add(itw.Value());
369   for (itw.Initialize(myEndWire); itw.More(); itw.Next())
370     myEndWireEdges.Add(itw.Value());
371
372   TopTools_IndexedDataMapOfShapeListOfShape VEmap;
373   TopTools_IndexedDataMapOfShapeListOfShape EFmap;
374   TopExp::MapShapesAndAncestors(myInitialShape, TopAbs_VERTEX, TopAbs_EDGE, VEmap);
375   TopExp::MapShapesAndAncestors(myInitialShape, TopAbs_EDGE,   TopAbs_FACE, EFmap);
376
377   TopTools_MapOfShape CurVertices;
378   
379   Standard_Integer i, j, k;
380   TopoDS_Edge anEdge;
381   TopoDS_Vertex V1, V2, NextVertex;
382   //Initialization of <myPaths>
383   for (i = 1; i <= StartVertices.Length(); i++)
384   {
385     TopTools_SequenceOfShape Edges;
386     const TopTools_ListOfShape& LE = VEmap.FindFromKey(StartVertices(i));
387     for (itl.Initialize(LE); itl.More(); itl.Next())
388     {
389       anEdge = TopoDS::Edge(itl.Value());
390       if (!myStartWireEdges.Contains(anEdge))
391       {
392         TopExp::Vertices(anEdge, V1, V2, Standard_True);
393         if (V1.IsSame(StartVertices(i)))
394           CurVertices.Add(V2);
395         else
396         {
397           anEdge.Reverse();
398           CurVertices.Add(V1);
399         }
400         Edges.Append(anEdge);
401         break;
402       }
403     }
404     if (!Edges.IsEmpty())
405       myPaths.Append(Edges);
406     else
407       return;
408   }
409
410   //Filling of "myPaths"
411   TopTools_ListOfShape NextVertices;
412   for (;;)
413   {
414     for (i = 1; i <= myPaths.Length(); i++)
415     {
416       const TopoDS_Shape& theShape = myPaths(i).Last();
417       TopoDS_Edge theEdge;
418       TopoDS_Vertex theVertex;
419       if (theShape.ShapeType() == TopAbs_EDGE)
420       {
421         theEdge = TopoDS::Edge(theShape);
422         theVertex = TopExp::LastVertex(theEdge, Standard_True);
423       }
424       else //last segment of path was punctual
425       {
426         theEdge = TopoDS::Edge(myPaths(i)(myPaths(i).Length()-1));
427         theVertex = TopoDS::Vertex(theShape);
428       }
429       
430       if (EndVertices.Contains(theVertex))
431         continue;
432       const TopTools_ListOfShape& LE = VEmap.FindFromKey(theVertex);
433       TopTools_MapOfShape NextEdgeCandidates;
434       for (itl.Initialize(LE); itl.More(); itl.Next())
435       {
436         anEdge = TopoDS::Edge(itl.Value());
437         if (anEdge.IsSame(theEdge))
438           continue;
439         TopExp::Vertices(anEdge, V1, V2, Standard_True);
440         if (V1.IsSame(theVertex))
441           NextVertex = V2;
442         else
443         {
444           anEdge.Reverse();
445           NextVertex = V1;
446         }
447         if (!CurVertices.Contains(NextVertex))
448           NextEdgeCandidates.Add(anEdge);
449       }
450       if (!NextEdgeCandidates.IsEmpty())
451       {
452         if (NextEdgeCandidates.Extent() > 1)
453           myPaths(i).Append(theVertex); //punctual segment of path
454         else
455         {
456           TopTools_MapIteratorOfMapOfShape mapit(NextEdgeCandidates);
457           anEdge = TopoDS::Edge(mapit.Key());
458           myPaths(i).Append(anEdge);
459           NextVertex = TopExp::LastVertex(anEdge, Standard_True);
460           NextVertices.Append(NextVertex);
461         }
462       }
463     }
464     if (NextVertices.IsEmpty())
465       break;
466     for (itl.Initialize(NextVertices); itl.More(); itl.Next())
467       CurVertices.Add(itl.Value());
468     NextVertices.Clear();
469   }
470
471   //Temporary
472   /*
473   TopoDS_Compound aCompound, aCmp1;
474   BRep_Builder BB;
475   BB.MakeCompound(aCompound);
476   BB.MakeCompound(aCmp1);
477   for (i = 1; i <= myPaths.Length(); i++)
478   {
479     TopoDS_Compound aCmp;
480     BB.MakeCompound(aCmp);
481     for (j = 1; j <= myPaths(i).Length(); j++)
482       BB.Add(aCmp, myPaths(i)(j));
483     BB.Add(aCmp1, aCmp);
484   }
485   BB.Add(aCompound, aCmp1);
486          
487   myShape = aCompound;
488
489   Done();
490   return;
491   */
492   ////////////
493   
494   //Building of set of sections
495   Standard_Integer NbE = EdgeSeq.Length();
496   Standard_Integer NbPaths = myPaths.Length();
497   Standard_Integer NbVer = myPaths.Length();
498   if (myClosedSection)
499     NbVer++;
500   i = 1;
501   for (;;)
502   {
503     for (j = 1; j <= EdgeSeq.Length(); j++)
504       EdgeSeq(j).Nullify();
505
506     Standard_Boolean ToInsertVertex = Standard_False;
507     
508     for (j = 2; j <= NbVer; j++)
509     {
510       if (!EdgeSeq(j-1).IsNull())
511         continue;
512
513       //for the end of initial shape
514       if (myPaths(j-1).Length() < i)
515       {
516         TopoDS_Edge aE1 = TopoDS::Edge(myPaths(j-1)(i-1));
517         TopoDS_Shape LastVer = TopExp::LastVertex(aE1, Standard_True);
518         myPaths(j-1).Append(LastVer);
519       }
520       if (myPaths((j<=NbPaths)? j : 1).Length() < i)
521       {
522         TopoDS_Edge aE2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i-1));
523         TopoDS_Shape LastVer = TopExp::LastVertex(aE2, Standard_True);
524         myPaths((j<=NbPaths)? j : 1).Append(LastVer);
525       }
526       //////////////////////////////
527       
528       if (ToInsertVertex)
529       {
530         if (myPaths(j-1)(i).ShapeType() == TopAbs_EDGE)
531         {
532           TopoDS_Edge aE1 = TopoDS::Edge(myPaths(j-1)(i));
533           TopoDS_Shape fver = TopExp::FirstVertex(aE1, Standard_True);
534           myPaths(j-1).InsertBefore(i, fver);
535         }
536         if (myPaths((j<=NbPaths)? j : 1)(i).ShapeType() == TopAbs_EDGE)
537         {
538           TopoDS_Edge aE2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i));
539           TopoDS_Shape fver = TopExp::FirstVertex(aE2, Standard_True);
540           myPaths((j<=NbPaths)? j : 1).InsertBefore(i, fver);
541         }
542         ToInsertVertex = Standard_False;
543       }
544       
545       TopoDS_Edge E1, E2;
546       if (myPaths(j-1)(i).ShapeType() == TopAbs_EDGE)
547         E1 = TopoDS::Edge(myPaths(j-1)(i));
548       if (myPaths((j<=NbPaths)? j : 1)(i).ShapeType() == TopAbs_EDGE)
549         E2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i));
550       TopoDS_Edge E12 = TopoDS::Edge(SectionsEdges(i)(j-1));
551       //Find the face on which (E1 or E2) and E12 lie
552       TopoDS_Shape E1orE2 = (E1.IsNull())? E2 : E1;
553       if (E1orE2.IsNull()) //both E1 and E2 are vertices =>
554       {
555         EdgeSeq(j-1) = E12; // => proper edge is the edge of previous section between them
556         continue;
557       }
558       const TopTools_ListOfShape& LF = EFmap.FindFromKey(E1orE2);
559       TopoDS_Face theFace;
560       for (itl.Initialize(LF); itl.More(); itl.Next())
561       {
562         const TopoDS_Shape& aFace = itl.Value();
563         const TopTools_ListOfShape& LF2 = EFmap.FindFromKey(E12);
564         TopTools_ListIteratorOfListOfShape itl2(LF2);
565         for (; itl2.More(); itl2.Next())
566         {
567           const TopoDS_Shape& aFace2 = itl2.Value();
568           if (aFace.IsSame(aFace2))
569           {
570             theFace = TopoDS::Face(aFace);
571             break;
572           }
573         }
574         if (!theFace.IsNull())
575           break;
576       }
577       
578       TopoDS_Vertex PrevVertex = (E1.IsNull())? TopoDS::Vertex(myPaths(j-1)(i))
579         : TopExp::LastVertex(E1, Standard_True);
580       TopoDS_Vertex CurVertex = (E2.IsNull())? TopoDS::Vertex(myPaths((j<=NbPaths)? j : 1)(i))
581         : TopExp::LastVertex(E2, Standard_True);
582       
583       TopoDS_Edge ProperEdge;
584       const TopTools_ListOfShape& LE = VEmap.FindFromKey(PrevVertex);
585       //Temporary
586       //Standard_Integer LenList = LE.Extent();
587       ///////////
588       TopTools_IndexedMapOfShape EdgesOfTheFace;
589       TopExp::MapShapes(theFace, TopAbs_EDGE, EdgesOfTheFace);
590       for (itl.Initialize(LE); itl.More(); itl.Next())
591       {
592         anEdge = TopoDS::Edge(itl.Value());
593         TopExp::Vertices(anEdge, V1, V2);
594         if (((V1.IsSame(PrevVertex) && V2.IsSame(CurVertex)) ||
595              (V1.IsSame(CurVertex) && V2.IsSame(PrevVertex))) &&
596             EdgesOfTheFace.Contains(anEdge) && //this condition is for a section of two edges
597             !anEdge.IsSame(E1)) //the last condition is for torus-like shape
598         {
599           ProperEdge = anEdge;
600           break;
601         }
602       }
603       
604       if ((myPaths(j-1)(i)).ShapeType() == TopAbs_VERTEX &&
605           (myPaths((j<=NbPaths)? j : 1)(i)).ShapeType() == TopAbs_VERTEX)
606       {
607         EdgeSeq(j-1) = ProperEdge;
608         continue;
609       }
610
611       TopoDS_Vertex PrevPrevVer = (E1.IsNull())? PrevVertex
612         : TopExp::FirstVertex(E1, Standard_True);
613       TopoDS_Vertex PrevCurVer  = (E2.IsNull())? CurVertex
614         : TopExp::FirstVertex(E2, Standard_True);
615       if (ProperEdge.IsNull()) //no connection between these two vertices
616       {
617         //Find the face on which E1, E2 and E12 lie
618         //ToInsertVertex = Standard_False;
619         TopTools_ListOfShape ListOneFace;
620         ListOneFace.Append(theFace);
621
622         if (E1.IsNull() || E2.IsNull())
623         {
624           if (E1.IsNull())
625             E1 = TopoDS::Edge(myPaths(j-1)(i-1));
626           if (E2.IsNull())
627             E2 = TopoDS::Edge(myPaths((j<=NbPaths)? j : 1)(i-1));
628           Standard_Real fpar1, lpar1, fpar2, lpar2;
629           Standard_Real LastPar1, LastPar2;
630           Handle(Geom2d_Curve) PCurve1 = BRep_Tool::CurveOnSurface(E1, theFace, fpar1, lpar1);
631           Handle(Geom2d_Curve) PCurve2 = BRep_Tool::CurveOnSurface(E2, theFace, fpar2, lpar2);
632           if (E1.Orientation() == TopAbs_FORWARD)
633           { LastPar1 = lpar1; }
634           else
635           { LastPar1 = fpar1; }
636           if (E2.Orientation() == TopAbs_FORWARD)
637           { LastPar2 = lpar2; }
638           else
639           { LastPar2 = fpar2; }
640           gp_Pnt2d FirstPnt2d = PCurve1->Value(LastPar1);
641           gp_Pnt2d LastPnt2d  = PCurve2->Value(LastPar2);
642           Handle(Geom_Surface) theSurf = BRep_Tool::Surface(theFace);
643           Handle(Geom2d_Line) theLine = GCE2d_MakeLine(FirstPnt2d, LastPnt2d);
644           Standard_Real len_ne = FirstPnt2d.Distance(LastPnt2d);
645           TopoDS_Edge NewEdge = BRepLib_MakeEdge(theLine, theSurf,
646                                                  PrevVertex, CurVertex,
647                                                  0., len_ne);
648           BRepLib::BuildCurve3d(NewEdge);
649           EdgeSeq(j-1) = NewEdge;
650           EFmap.Add(NewEdge, ListOneFace);
651         }
652         else //E1 is edge
653         {
654           //Extract points 2d
655           Standard_Real fpar1, lpar1, fpar2, lpar2;
656           Standard_Real FirstPar1, LastPar1, FirstPar2, LastPar2;
657           Handle(Geom2d_Curve) PCurve1 = BRep_Tool::CurveOnSurface(E1, theFace, fpar1, lpar1);
658           Handle(Geom2d_Curve) PCurve2 = BRep_Tool::CurveOnSurface(E2, theFace, fpar2, lpar2);
659           if (E1.Orientation() == TopAbs_FORWARD)
660           { FirstPar1 = fpar1; LastPar1 = lpar1; }
661           else
662           { FirstPar1 = lpar1; LastPar1 = fpar1; }
663           if (E2.Orientation() == TopAbs_FORWARD)
664           { FirstPar2 = fpar2; LastPar2 = lpar2; }
665           else
666           { FirstPar2 = lpar2; LastPar2 = fpar2; }
667           gp_Pnt2d FirstPnt2d = PCurve1->Value(LastPar1);
668           gp_Pnt2d LastPnt2d  = PCurve2->Value(LastPar2);
669           Handle(Geom_Surface) theSurf = BRep_Tool::Surface(theFace);
670           Handle(Geom2d_Line) theLine = GCE2d_MakeLine(FirstPnt2d, LastPnt2d);
671           Standard_Real len_ne = FirstPnt2d.Distance(LastPnt2d);
672           TopoDS_Edge NewEdge = BRepLib_MakeEdge(theLine, theSurf,
673                                                  PrevVertex, CurVertex,
674                                                  0., len_ne);
675           BRepLib::BuildCurve3d(NewEdge);
676           gp_Pnt2d PrevFirstPnt2d = PCurve1->Value(FirstPar1);
677           gp_Pnt2d PrevLastPnt2d  = PCurve2->Value(FirstPar2);
678           Handle(Geom2d_Line) Line1 = GCE2d_MakeLine(PrevFirstPnt2d, LastPnt2d);
679           Handle(Geom2d_Line) Line2 = GCE2d_MakeLine(FirstPnt2d, PrevLastPnt2d);
680           Standard_Real len_ne1 = PrevFirstPnt2d.Distance(LastPnt2d);
681           TopoDS_Edge NewEdge1 = BRepLib_MakeEdge(Line1, theSurf,
682                                                   PrevPrevVer, CurVertex,
683                                                   0., len_ne1);
684           BRepLib::BuildCurve3d(NewEdge1);
685           Standard_Real len_ne2 = FirstPnt2d.Distance(PrevLastPnt2d);
686           TopoDS_Edge NewEdge2 = BRepLib_MakeEdge(Line2, theSurf,
687                                                   PrevVertex, PrevCurVer,
688                                                   0., len_ne2);
689           BRepLib::BuildCurve3d(NewEdge2);
690           Standard_Boolean good_ne  = IsValidEdge(NewEdge, theFace);
691           Standard_Boolean good_ne1 = IsValidEdge(NewEdge1, theFace);
692
693           GeomAbs_CurveType type_E1 = TypeOfEdge(E1);
694           GeomAbs_CurveType type_E2 = TypeOfEdge(E2);
695
696           Standard_Integer ChooseEdge = 0;
697           
698           if (!good_ne || type_E1 != type_E2)
699           {
700             if (type_E1 == type_E2) //!good_ne
701             {
702               if (good_ne1)
703                 ChooseEdge = 1;
704               else
705                 ChooseEdge = 2;
706             }
707             else //types are different
708             {
709               if (type_E1 == GeomAbs_Line)
710                 ChooseEdge = 1;
711               else if (type_E2 == GeomAbs_Line)
712                 ChooseEdge = 2;
713               else //to be developed later...
714               {}
715             }
716           }
717           
718           if (ChooseEdge == 0)
719           {
720             EdgeSeq(j-1) = NewEdge;
721             EFmap.Add(NewEdge, ListOneFace);
722           }
723           else if (ChooseEdge == 1)
724           {
725             EdgeSeq(j-1) = NewEdge1;
726             EFmap.Add(NewEdge1, ListOneFace);
727             for (k = 1; k < j-1; k++)
728               EdgeSeq(k).Nullify();
729             for (k = 1; k <= j-1; k++)
730             {
731               TopoDS_Edge aLastEdge = TopoDS::Edge(myPaths(k)(i));
732               TopoDS_Shape VertexAsEdge = TopExp::FirstVertex(aLastEdge, Standard_True);
733               myPaths(k).InsertBefore(i, VertexAsEdge);
734             }
735             j = 1; //start from beginning
736           }
737           else if (ChooseEdge == 2)
738           {
739             EdgeSeq(j-1) = NewEdge2;
740             EFmap.Add(NewEdge2, ListOneFace);
741             ToInsertVertex = Standard_True;
742           }
743         } //else //E1 is edge
744       } //if (ProperEdge.IsNull())
745       else //connecting edge exists
746       {
747         /*
748         if (ToInsertVertex)
749         {
750           myPaths(j-1).InsertBefore(i, PrevPrevVer);
751           myPaths((j<=NbPaths)? j : 1).InsertBefore(i, PrevCurVer);
752           EdgeSeq(j-1) = E12;
753         }
754         else
755         */
756           EdgeSeq(j-1) = ProperEdge;
757       }
758     } //for (j = 2; j <= NbVer; j++)
759     SectionsEdges.Append(EdgeSeq);
760
761     //check for exit from for(;;)
762     Standard_Integer NbEndEdges = 0;
763     for (j = 1; j <= EdgeSeq.Length(); j++)
764       if (EndEdges.Contains(EdgeSeq(j)))
765         NbEndEdges++;
766     if (NbEndEdges == NbE)
767       break;
768     
769     i++;
770   } //for (;;)
771   
772
773   //final phase: building of middle path
774   Standard_Integer NbSecFaces = SectionsEdges.Length();
775   TopTools_Array1OfShape SecFaces(1, NbSecFaces);
776   for (i = 1; i <= NbSecFaces; i++)
777   {
778     BRepLib_MakeWire MW;
779     for (j = 1; j <= NbE; j++)
780     {
781       anEdge = TopoDS::Edge(SectionsEdges(i)(j));
782       MW.Add(anEdge);
783     }
784     if (!myClosedSection)
785     {
786       TopExp::Vertices(MW.Wire(), V1, V2);
787       anEdge = BRepLib_MakeEdge(V2, V1);
788       MW.Add(anEdge);
789     }
790     TopoDS_Wire aWire = MW.Wire();
791     BRepLib_MakeFace MF(aWire, Standard_True); //Only plane
792     if (MF.IsDone())
793       SecFaces(i) = MF.Face();
794     else
795       SecFaces(i) = aWire;
796   }
797
798   TColgp_Array1OfPnt Centers(1, NbSecFaces);
799   for (i = 1; i <= NbSecFaces; i++)
800   {
801     GProp_GProps Properties;
802     if (SecFaces(i).ShapeType() == TopAbs_FACE)
803       BRepGProp::SurfaceProperties(SecFaces(i), Properties);
804     else //wire
805       BRepGProp::LinearProperties(SecFaces(i), Properties);
806       
807     Centers(i) = Properties.CentreOfMass();
808   }
809
810   TopTools_Array1OfShape MidEdges(1, NbSecFaces-1);
811   Standard_Real LinTol = 1.e-5;
812   Standard_Real AngTol = 1.e-7;
813   gp_Pnt Pnt1, Pnt2;
814   for (i = 1; i < NbSecFaces; i++)
815   {
816     GeomAbs_CurveType TypeOfMidEdge = GeomAbs_OtherCurve;
817     for (j = 1; j <= myPaths.Length(); j++)
818     {
819       const TopoDS_Shape& aShape = myPaths(j)(i);
820       if (aShape.ShapeType() == TopAbs_VERTEX)
821       {
822         TypeOfMidEdge = GeomAbs_OtherCurve;
823         break;
824       }
825       anEdge = TopoDS::Edge(aShape);
826       GeomAbs_CurveType aType = TypeOfEdge(anEdge);
827       if (j == 1)
828         TypeOfMidEdge = aType;
829       else
830       {
831         if (aType != TypeOfMidEdge)
832         {
833           TypeOfMidEdge = GeomAbs_OtherCurve;
834           break;
835         }
836       }
837     }
838     if (TypeOfMidEdge == GeomAbs_Line)
839       MidEdges(i) = BRepLib_MakeEdge(Centers(i), Centers(i+1));
840     else if (TypeOfMidEdge == GeomAbs_Circle)
841     {
842       gp_Ax1 theAxis;
843       gp_Dir theDir1, theDir2;
844       Standard_Real theAngle = 0.;
845       gp_Vec theTangent;
846       Standard_Boolean SimilarArcs = Standard_True;
847       for (j = 1; j <= myPaths.Length(); j++)
848       {
849         anEdge = TopoDS::Edge(myPaths(j)(i));
850         Standard_Real fpar, lpar;
851         Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
852         if (aCurve->IsInstance(STANDARD_TYPE(Geom_TrimmedCurve)))
853           aCurve = Handle(Geom_TrimmedCurve)::DownCast (aCurve)->BasisCurve();
854         Pnt1 = aCurve->Value(fpar);
855         Pnt2 = aCurve->Value(lpar);
856         Handle(Geom_Circle) aCircle = Handle(Geom_Circle)::DownCast(aCurve);
857         gp_Circ aCirc = aCircle->Circ();
858         if (j == 1)
859         {
860           theAxis = aCirc.Axis();
861           theDir1 = gp_Vec(aCirc.Location(), Pnt1);
862           theDir2 = gp_Vec(aCirc.Location(), Pnt2);
863           theAngle = lpar - fpar;
864           Standard_Real theParam = (anEdge.Orientation() == TopAbs_FORWARD)?
865             fpar : lpar;
866           aCurve->D1(theParam, Pnt1, theTangent);
867           if (anEdge.Orientation() == TopAbs_REVERSED)
868             theTangent.Reverse();
869         }
870         else
871         {
872           gp_Ax1 anAxis = aCirc.Axis();
873           gp_Lin aLin(anAxis);
874           if (!aLin.Contains(theAxis.Location(), LinTol) ||
875               !anAxis.IsParallel(theAxis, AngTol))
876           {
877             SimilarArcs = Standard_False;
878             break;
879           }
880           gp_Dir aDir1 = gp_Vec(aCirc.Location(), Pnt1);
881           gp_Dir aDir2 = gp_Vec(aCirc.Location(), Pnt2);
882           if (!((aDir1.IsEqual(theDir1, AngTol) && aDir2.IsEqual(theDir2, AngTol)) ||
883                 (aDir1.IsEqual(theDir2, AngTol) && aDir2.IsEqual(theDir1, AngTol))))
884           {
885             SimilarArcs = Standard_False;
886             break;
887           }
888         }
889       }
890       if (SimilarArcs)
891       {
892         gp_XYZ AxisLoc = theAxis.Location().XYZ();
893         gp_XYZ AxisDir = theAxis.Direction().XYZ();
894         Standard_Real Parameter = (Centers(i).XYZ() - AxisLoc) * AxisDir;
895         gp_Pnt theCenterOfCirc(AxisLoc + Parameter*AxisDir);
896         
897         gp_Vec Vec1(theCenterOfCirc, Centers(i));
898         gp_Vec Vec2(theCenterOfCirc, Centers(i+1));
899         /*
900         gp_Dir VecProd = Vec1 ^ Vec2;
901         if (theAxis.Direction() * VecProd < 0.)
902           theAxis.Reverse();
903         */
904         
905         Standard_Real anAngle = Vec1.AngleWithRef(Vec2, theAxis.Direction());
906         if (anAngle < 0.)
907           anAngle += 2.*M_PI;
908         if (Abs(anAngle - theAngle) > AngTol)
909           theAxis.Reverse();
910         gp_Ax2 theAx2(theCenterOfCirc, theAxis.Direction(), Vec1);
911         Handle(Geom_Circle) theCircle = GC_MakeCircle(theAx2, Vec1.Magnitude());
912         gp_Vec aTangent;
913         theCircle->D1( 0., Pnt1, aTangent );
914         if (aTangent * theTangent < 0.)
915         {
916           theAxis.Reverse();
917           theAx2 = gp_Ax2(theCenterOfCirc, theAxis.Direction(), Vec1);
918           theCircle = GC_MakeCircle(theAx2, Vec1.Magnitude());
919         }
920         BRepLib_MakeEdge aME (theCircle, 0., theAngle);
921         aME.Build();
922
923         MidEdges(i) = aME.IsDone() ? 
924           aME.Shape() : 
925           TopoDS_Edge();
926       }
927     }
928   }
929
930   //Build missed edges
931   for (i = 1; i < NbSecFaces; i++)
932   {
933     if (MidEdges(i).IsNull())
934     {
935       for (j = i+1; j < NbSecFaces; j++)
936       {
937         if (!MidEdges(j).IsNull())
938           break;
939       }
940       //from i to j-1 all edges are null
941       Handle(TColgp_HArray1OfPnt) thePoints = new TColgp_HArray1OfPnt(1, j-i+1);
942       TColgp_Array1OfVec theTangents(1, j-i+1);
943       Handle(TColStd_HArray1OfBoolean) theFlags = new TColStd_HArray1OfBoolean(1, j-i+1);
944       for (k = i; k <= j; k++)
945         thePoints->SetValue(k-i+1, Centers(k));
946       for (k = i; k <= j; k++)
947       {
948         TColgp_SequenceOfPnt PntSeq;
949         for (Standard_Integer indp = 1; indp <= myPaths.Length(); indp++)
950         {
951           gp_Vec aTangent;
952           if (k == i)
953           {
954             if (myPaths(indp)(k).ShapeType() == TopAbs_VERTEX)
955               continue;
956             aTangent = TangentOfEdge(myPaths(indp)(k), Standard_True); //at begin
957           }
958           else if (k == j)
959           {
960             if (myPaths(indp)(k-1).ShapeType() == TopAbs_VERTEX)
961               continue;
962             aTangent = TangentOfEdge(myPaths(indp)(k-1), Standard_False); //at end
963           }
964           else
965           {
966             if (myPaths(indp)(k-1).ShapeType() == TopAbs_VERTEX ||
967                 myPaths(indp)(k).ShapeType() == TopAbs_VERTEX)
968               continue;
969             gp_Vec Tangent1 = TangentOfEdge(myPaths(indp)(k-1), Standard_False); //at end
970             gp_Vec Tangent2 = TangentOfEdge(myPaths(indp)(k), Standard_True); //at begin
971             aTangent = Tangent1 + Tangent2;
972           }
973           aTangent.Normalize();
974           gp_Pnt aPnt(aTangent.XYZ());
975           PntSeq.Append(aPnt);
976         }
977         TColgp_Array1OfPnt PntArray(1, PntSeq.Length());
978         for (Standard_Integer ip = 1; ip <= PntSeq.Length(); ip++)
979           PntArray(ip) = PntSeq(ip);
980         gp_Pnt theBary;
981         gp_Dir xdir, ydir;
982         Standard_Real xgap, ygap, zgap;
983         GeomLib::Inertia(PntArray, theBary, xdir, ydir, xgap, ygap, zgap);
984         gp_Vec theTangent(theBary.XYZ());
985         theTangents(k-i+1) = theTangent;
986       }
987       theFlags->Init(Standard_True);
988
989       GeomAPI_Interpolate Interpol(thePoints, Standard_False, LinTol);
990       Interpol.Load(theTangents, theFlags);
991       Interpol.Perform();
992       if (!Interpol.IsDone())
993       {
994         cout<<endl<<"Interpolation failed"<<endl;
995       }
996       Handle(Geom_Curve) InterCurve (Interpol.Curve());
997       MidEdges(i) = BRepLib_MakeEdge(InterCurve);
998       i = j;
999     }
1000   }  
1001
1002   BRepLib_MakeWire MakeFinalWire;
1003   for (i = 1; i < NbSecFaces; i++)
1004     if (!MidEdges(i).IsNull())
1005       MakeFinalWire.Add(TopoDS::Edge(MidEdges(i)));
1006
1007   TopoDS_Wire FinalWire = MakeFinalWire.Wire();
1008   myShape = MakeFinalWire.Wire();
1009   
1010   //Temporary
1011   /*
1012   TopoDS_Compound aCompound, aCmp1, aCmp2;
1013   BRep_Builder BB;
1014   BB.MakeCompound(aCompound);
1015   BB.MakeCompound(aCmp1);
1016   BB.MakeCompound(aCmp2);
1017   for (i = 1; i <= myPaths.Length(); i++)
1018   {
1019     TopoDS_Compound aCmp;
1020     BB.MakeCompound(aCmp);
1021     for (j = 1; j <= myPaths(i).Length(); j++)
1022       BB.Add(aCmp, myPaths(i)(j));
1023     BB.Add(aCmp1, aCmp);
1024   }
1025   for (i = 1; i <= SectionsEdges.Length(); i++)
1026   {
1027     TopoDS_Wire aWire;
1028     BB.MakeWire(aWire);
1029     for (j = 1; j <= SectionsEdges(i).Length(); j++)
1030       BB.Add(aWire, SectionsEdges(i)(j));
1031     BB.Add(aCmp2, aWire);
1032   }
1033   BB.Add(aCompound, aCmp1);
1034   BB.Add(aCompound, aCmp2);
1035   BB.Add(aCompound, FinalWire);
1036          
1037   myShape = aCompound;
1038   */
1039   ////////////
1040
1041   Done();
1042 }