3a24479ab67b2d936aea6c31d8b906beff95b4e1
[occt.git] / src / BRepFill / BRepFill_CompatibleWires.cxx
1 // Created on: 1998-07-02
2 // Created by: Joelle CHAUVET
3 // Copyright (c) 1998-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17
18 #include <Bnd_Box.hxx>
19 #include <BRep_Builder.hxx>
20 #include <BRep_Tool.hxx>
21 #include <BRepAdaptor_Curve.hxx>
22 #include <BRepBndLib.hxx>
23 #include <BRepCheck_Wire.hxx>
24 #include <BRepExtrema_DistShapeShape.hxx>
25 #include <BRepFill.hxx>
26 #include <BRepFill_CompatibleWires.hxx>
27 #include <BRepGProp.hxx>
28 #include <BRepLib.hxx>
29 #include <BRepLib_FindSurface.hxx>
30 #include <BRepLib_MakeEdge.hxx>
31 #include <BRepLib_MakeWire.hxx>
32 #include <BRepLProp.hxx>
33 #include <BRepTools_WireExplorer.hxx>
34 #include <Geom_Plane.hxx>
35 #include <Geom_Surface.hxx>
36 #include <gp.hxx>
37 #include <gp_Ax2.hxx>
38 #include <gp_Circ.hxx>
39 #include <gp_Elips.hxx>
40 #include <gp_Pln.hxx>
41 #include <gp_Vec.hxx>
42 #include <GProp_GProps.hxx>
43 #include <GProp_PrincipalProps.hxx>
44 #include <Precision.hxx>
45 #include <Standard_ConstructionError.hxx>
46 #include <Standard_NoSuchObject.hxx>
47 #include <TColgp_HArray1OfPnt.hxx>
48 #include <TColgp_HArray1OfVec.hxx>
49 #include <TColStd_Array1OfInteger.hxx>
50 #include <TColStd_Array1OfReal.hxx>
51 #include <TColStd_MapOfInteger.hxx>
52 #include <TColStd_SequenceOfReal.hxx>
53 #include <TopAbs.hxx>
54 #include <TopExp.hxx>
55 #include <TopExp_Explorer.hxx>
56 #include <TopoDS.hxx>
57 #include <TopoDS_Edge.hxx>
58 #include <TopoDS_Wire.hxx>
59 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
60 #include <TopTools_DataMapOfShapeListOfShape.hxx>
61 #include <TopTools_DataMapOfShapeSequenceOfShape.hxx>
62 #include <TopTools_HSequenceOfShape.hxx>
63 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
64 #include <TopTools_ListIteratorOfListOfShape.hxx>
65 #include <TopTools_ListOfShape.hxx>
66 #include <TopTools_SequenceOfShape.hxx>
67
68 #ifdef OCCT_DEBUG_EFV
69 static void EdgesFromVertex (const TopoDS_Wire&   W,
70                              const TopoDS_Vertex& V, 
71                              TopoDS_Edge& E1, 
72                              TopoDS_Edge& E2)
73 {
74   TopTools_IndexedDataMapOfShapeListOfShape Map;
75   TopExp::MapShapesAndAncestors(W,TopAbs_VERTEX,TopAbs_EDGE,Map);
76
77   const TopTools_ListOfShape& List = Map.FindFromKey(V);
78   TopoDS_Edge          e1   = TopoDS::Edge(List.First());
79   TopoDS_Edge          e2   = TopoDS::Edge(List. Last());
80
81   BRepTools_WireExplorer anExp;
82   Standard_Integer I1=0, I2=0, NE=0;
83
84   for(anExp.Init(W); anExp.More(); anExp.Next()) {
85     NE++;
86     const TopoDS_Edge& ECur = anExp.Current();
87     if (e1.IsSame(ECur)) {
88       I1 = NE;
89     }
90     if (e2.IsSame(ECur)) {
91       I2 = NE;
92     }
93   }
94
95   if (Abs(I2-I1)==1) {
96     // consecutive numbers
97     if (I2==I1+1) {
98       E1 = e1;
99       E2 = e2;
100     }
101     else {
102       E1 = e2;
103       E2 = e1;
104     }
105   }
106   else {
107     // non consecutive numbers on a closed wire
108     if (I1==1&&I2==NE) {
109       E1 = e2;
110       E2 = e1;
111     }
112     else {
113       E1 = e1;
114       E2 = e2;
115     }
116   }
117 }
118                                       
119 #endif
120
121 //=======================================================================
122 //function : AddNewEdge
123 //purpose  : for <theEdge> find all newest edges
124 //           in <theEdgeNewEdges> recursively
125 //=======================================================================
126
127 static void AddNewEdge(const TopoDS_Shape& theEdge,
128                        const TopTools_DataMapOfShapeSequenceOfShape& theEdgeNewEdges,
129                        TopTools_ListOfShape& ListNewEdges)
130 {
131   if (theEdgeNewEdges.IsBound(theEdge))
132   {
133     const TopTools_SequenceOfShape& NewEdges = theEdgeNewEdges(theEdge);
134     for (Standard_Integer i = 1; i <= NewEdges.Length(); i++)
135     {
136       TopoDS_Shape anEdge = NewEdges(i);
137       AddNewEdge(anEdge, theEdgeNewEdges, ListNewEdges);
138     }
139   }
140   else
141     ListNewEdges.Append(theEdge);
142 }
143
144 static void SeqOfVertices (const TopoDS_Wire&   W,
145                            TopTools_SequenceOfShape& S)
146 {
147   S.Clear();
148   Standard_Integer jj, cpt = 0;
149   TopExp_Explorer PE;
150   for (PE.Init(W,TopAbs_VERTEX); PE.More(); PE.Next()) {
151     cpt++;
152     Standard_Boolean trouve=Standard_False;
153     for (jj=1;jj<=S.Length() && (!trouve);jj++) {
154       if (S.Value(jj).IsSame(PE.Current())) trouve = Standard_True; 
155       }
156       if (!trouve) S.Append(PE.Current());
157     }
158 }
159                                       
160
161 static Standard_Boolean PlaneOfWire (const TopoDS_Wire& W, gp_Pln& P)
162 {
163   Standard_Boolean isplane = Standard_True;
164   BRepLib_FindSurface findPlanarSurf;
165   Handle(Geom_Surface) S;
166   TopLoc_Location      L;
167
168   GProp_GProps GP;
169   gp_Pnt Bary;
170   Standard_Boolean isBaryDefined = Standard_False;
171
172 // shielding for particular cases : only one edge circle or ellipse
173 // on a closed wire !
174
175   Standard_Boolean wClosed = W.Closed();
176   if (!wClosed)
177   {
178     // it is checked if the vertices are the same.
179     TopoDS_Vertex V1, V2;
180     TopExp::Vertices(W,V1,V2);
181     if ( V1.IsSame(V2)) wClosed = Standard_True;
182   }
183
184   if (wClosed)
185   {
186     Standard_Integer nbEdges = 0;
187     TopoDS_Iterator anIter;
188     anIter.Initialize(W);
189     for(; anIter.More(); anIter.Next())
190       nbEdges ++;
191
192     if(nbEdges == 1)
193     {
194       GeomAdaptor_Curve AdC;
195       Standard_Real first, last;
196       anIter.Initialize(W);
197       AdC.Load(BRep_Tool::Curve(TopoDS::Edge(anIter.Value()), first, last));
198
199       if (AdC.GetType() == GeomAbs_Circle)
200       {
201         Bary = AdC.Circle().Location();
202         isBaryDefined = Standard_True;
203       }
204
205       if (AdC.GetType() == GeomAbs_Ellipse)
206       {
207         Bary = AdC.Ellipse().Location();
208         isBaryDefined = Standard_True;
209       }
210     }
211   }
212
213   if (!isBaryDefined)
214   {
215     BRepGProp::LinearProperties(W,GP);
216     Bary = GP.CentreOfMass();
217   }
218
219   findPlanarSurf.Init(W, -1, Standard_True);
220   if ( findPlanarSurf.Found())
221   {
222     S = findPlanarSurf.Surface();
223     L = findPlanarSurf.Location();
224     if (!L.IsIdentity()) S = Handle(Geom_Surface)::
225       DownCast(S->Transformed(L.Transformation()));
226     P = (Handle(Geom_Plane)::DownCast(S))->Pln();
227     P.SetLocation(Bary);
228   }
229   else
230   {
231     // wire not plane !
232     GProp_PrincipalProps Pp  = GP.PrincipalProperties();
233     gp_Vec Vec;
234     Standard_Real R1, R2, R3,Tol = Precision::Confusion();
235     Pp.RadiusOfGyration(R1,R2,R3);
236     Standard_Real RMax = Max(Max(R1,R2),R3);
237     if ( ( Abs(RMax-R1)<Tol && Abs(RMax-R2)<Tol )
238       || ( Abs(RMax-R1)<Tol && Abs(RMax-R3)<Tol ) 
239       || ( Abs(RMax-R2)<Tol && Abs(RMax-R3)<Tol ) )
240       isplane = Standard_False;
241     else
242     {
243       if (R1>=R2 && R1>=R3)
244       {
245         Vec = Pp.FirstAxisOfInertia();
246       }
247       else if (R2>=R1 && R2>=R3)
248       {
249         Vec = Pp.SecondAxisOfInertia();
250       }
251       else if (R3>=R1 && R3>=R2)
252       {
253         Vec = Pp.ThirdAxisOfInertia();
254       }
255       gp_Dir NDir(Vec);
256       if (R3<=R2 && R3<=R1)
257       {
258         Vec = Pp.ThirdAxisOfInertia();
259       }
260       else if (R2<=R1 && R2<=R3)
261       {
262         Vec = Pp.SecondAxisOfInertia();
263       }
264       else if (R1<=R2 && R1<=R3)
265       {
266         Vec = Pp.FirstAxisOfInertia();
267       }
268       gp_Dir XDir(Vec);
269       gp_Ax3 repere(Bary,NDir,XDir);
270       Geom_Plane GPlan(repere);
271       P = GPlan.Pln();
272     }
273   }
274
275   return isplane;
276
277 }
278                                       
279
280 static void WireContinuity (const TopoDS_Wire& W,
281                             GeomAbs_Shape& contW)
282 {
283   contW = GeomAbs_CN;
284   GeomAbs_Shape cont;
285   Standard_Boolean IsDegenerated = Standard_False;
286
287   BRepTools_WireExplorer anExp;
288   Standard_Integer nbEdges=0;
289   Handle(TopTools_HSequenceOfShape) Edges = new TopTools_HSequenceOfShape();
290   for(anExp.Init(W); anExp.More(); anExp.Next()) {
291     nbEdges++;
292     Edges->Append(anExp.Current());
293     if (BRep_Tool::Degenerated(anExp.Current())) IsDegenerated = Standard_True;
294   }
295   
296   if (!IsDegenerated) {
297
298     Standard_Boolean testconti = Standard_True;
299
300     for (Standard_Integer j=1;j<=nbEdges;j++) {
301       
302       TopoDS_Edge Edge1, Edge2;
303       
304       if (j == nbEdges) {
305         Edge1 = TopoDS::Edge (Edges->Value(nbEdges));
306         Edge2 = TopoDS::Edge (Edges->Value(1));
307       }
308       else {
309         Edge1 = TopoDS::Edge (Edges->Value(j));
310         Edge2 = TopoDS::Edge (Edges->Value(j+1));
311       } 
312       
313       TopoDS_Vertex V1,V2,Vbid;
314       TopExp::Vertices(Edge1,Vbid,V1,Standard_True);
315       TopExp::Vertices(Edge2,V2,Vbid,Standard_True);
316       Standard_Real U1 = BRep_Tool::Parameter(V1,Edge1);
317       Standard_Real U2 = BRep_Tool::Parameter(V2,Edge2);
318       BRepAdaptor_Curve Curve1(Edge1);
319       BRepAdaptor_Curve Curve2(Edge2);
320       Standard_Real Eps = BRep_Tool::Tolerance(V2) + BRep_Tool::Tolerance(V1);
321       
322       if(j == nbEdges) 
323         testconti = Curve1.Value(U1).IsEqual(Curve2.Value(U2), Eps);
324       
325       if(testconti) {
326         cont = BRepLProp::Continuity(Curve1,Curve2,U1,U2,
327                                      Eps, Precision::Angular()); 
328         if (cont <= contW) contW = cont;
329       }
330     }
331   }
332   
333 }
334
335 static void TrimEdge (const TopoDS_Edge&              CurrentEdge,
336                       const TColStd_SequenceOfReal&   CutValues,
337                       const Standard_Real   t0, const Standard_Real   t1,
338                       const Standard_Boolean          SeqOrder,
339                       TopTools_SequenceOfShape& S)
340
341 {
342   S.Clear();
343   Standard_Integer j, ndec=CutValues.Length();
344   Standard_Real first,last,m0,m1;
345   Handle(Geom_Curve) C = BRep_Tool::Curve(CurrentEdge,first,last);
346
347   TopoDS_Vertex Vf,Vl,Vbid,V0,V1;
348   TopAbs_Orientation CurrentOrient = CurrentEdge.Orientation();
349   TopExp::Vertices(CurrentEdge,Vf,Vl);
350   Vbid.Nullify();
351
352   if (SeqOrder) {
353     // from first to last
354     m0 = first;
355     V0 = Vf;
356     for (j=1; j<=ndec; j++) {
357       // piece of edge  
358       m1 = (CutValues.Value(j)-t0)*(last-first)/(t1-t0)+first;
359       TopoDS_Edge CutE = BRepLib_MakeEdge(C,V0,Vbid,m0,m1);
360       CutE.Orientation(CurrentOrient);
361       S.Append(CutE);
362       m0 = m1;
363       V0 = TopExp::LastVertex(CutE);
364       if (j==ndec) {
365         // last piece
366         TopoDS_Edge LastE = BRepLib_MakeEdge(C,V0,Vl,m0,last);
367         LastE.Orientation(CurrentOrient);
368         S.Append(LastE);
369       }
370     }
371   }
372   else {
373     // from last to first
374     m1 = last;
375     V1 = Vl;
376     for (j=ndec; j>=1; j--) {
377       // piece of edge  
378       m0 = (CutValues.Value(j)-t0)*(last-first)/(t1-t0)+first;
379       TopoDS_Edge CutE = BRepLib_MakeEdge(C,Vbid,V1,m0,m1);
380       CutE.Orientation(CurrentOrient);
381       S.Append(CutE);
382       m1 = m0;
383       V1 = TopExp::FirstVertex(CutE);
384       if (j==1) {
385         // last piece
386         TopoDS_Edge LastE = BRepLib_MakeEdge(C,Vf,V1,first,m1);
387         LastE.Orientation(CurrentOrient);
388         S.Append(LastE);
389       }
390     }
391   }
392 }
393
394
395
396 static Standard_Boolean SearchRoot (const TopoDS_Vertex& V,
397                                     const TopTools_DataMapOfShapeListOfShape& Map,
398                                     TopoDS_Vertex& VRoot)
399 {
400   Standard_Boolean trouve = Standard_False;
401   VRoot.Nullify();
402   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape it;
403   for (it.Initialize(Map); it.More(); it.Next()) {
404     const TopTools_ListOfShape & List = it.Value();
405     TopTools_ListIteratorOfListOfShape itL;
406     Standard_Boolean ilyest = Standard_False;
407     for (itL.Initialize(List); itL.More(); itL.Next()) {
408       TopoDS_Vertex Vcur = TopoDS::Vertex(itL.Value());
409       if (Vcur.IsSame(V)) {
410         ilyest = Standard_True;
411       }
412       if (ilyest) break;
413     }
414     if (ilyest) {
415       trouve = Standard_True;
416       VRoot = TopoDS::Vertex(it.Key());
417     }
418     if (trouve) break;
419   }
420   return trouve;
421 }
422
423 static Standard_Boolean SearchVertex (const TopTools_ListOfShape& List,
424                                       const TopoDS_Wire&   W,
425                                       TopoDS_Vertex& VonW)
426 {
427   Standard_Boolean trouve = Standard_False;
428   VonW.Nullify();
429   TopTools_SequenceOfShape SeqV;
430   SeqOfVertices(W,SeqV);
431   for (Standard_Integer ii=1;ii<=SeqV.Length();ii++) {
432     TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
433     TopTools_ListIteratorOfListOfShape itL;
434     Standard_Boolean ilyest = Standard_False;
435     for (itL.Initialize(List); itL.More(); itL.Next()) {
436       TopoDS_Vertex Vcur = TopoDS::Vertex(itL.Value());
437       if (Vcur.IsSame(Vi)) {
438         ilyest = Standard_True;
439       }
440       if (ilyest) break;
441     }
442     if (ilyest) {
443       trouve = Standard_True;
444       VonW = Vi;
445     }
446     if (trouve) break;
447   }
448   return trouve;
449 }
450
451
452 static Standard_Boolean EdgeIntersectOnWire (const gp_Pnt& P1,
453                                              const gp_Pnt& P2,
454                                              Standard_Real percent,
455                                              const TopTools_DataMapOfShapeListOfShape& Map,
456                                              const TopoDS_Wire&   W,
457                                              TopoDS_Vertex& Vsol,
458                                              TopoDS_Wire&   newW,
459                                              TopTools_DataMapOfShapeSequenceOfShape& theEdgeNewEdges)
460 {
461
462   BRepTools_WireExplorer anExp;
463
464   // construction of the edge of intersection
465   Standard_Boolean NewVertex = Standard_False;
466   gp_Lin droite(P1,gp_Dir(gp_Vec(P1,P2)));
467   // ATTENTION : it is required to construct a half-straight
468   //             but there is a bug in BRepExtrema_DistShapeShape
469   //             it is enough to take 100 * distance between P1 and P2
470   //             hoping that it is enough until the bug is corrected
471   //  Standard_Real dernierparam = Precision::Infinite();
472   // ATTENTION : return !!
473   //             100 is better than 10 but it is too much !
474   //             finally, nothing is better than a blocking box
475   //  Standard_Real dernierparam = 100 * P1.Distance(P2);
476   Bnd_Box B;
477   BRepBndLib::Add(W,B);
478   Standard_Real x1,x2,y1,y2,z1,z2;
479   B.Get(x1,y1,z1,x2,y2,z2);
480   gp_Pnt BP1(x1,y1,z1), BP2(x2,y2,z2);
481   Standard_Real diag = BP1.Distance(BP2);
482   Standard_Real dernierparam = diag;
483   BRepLib_MakeEdge ME(droite,0.,dernierparam);
484   TopoDS_Edge ECur = BRepLib_MakeEdge(droite,0.,P1.Distance(P2));
485
486   // calculate the intersection by BRepExtrema (point of min distance)
487   BRepExtrema_DistShapeShape DSS(ME.Edge(),W);
488   if (DSS.IsDone()) {
489     // choose the solution closest to P2
490     Standard_Integer isol = 1;
491     gp_Pnt Psol = DSS.PointOnShape2(isol);
492     Standard_Real dss = P2.Distance(Psol);
493     for (Standard_Integer iss=2; iss<=DSS.NbSolution(); iss++) {
494       gp_Pnt Pss = DSS.PointOnShape2(iss);
495       Standard_Real aDist = P2.Distance(Pss);
496       if (dss > aDist) {
497         dss = aDist;
498         isol = iss;
499 #ifdef OCCT_DEBUG
500         Psol = Pss;
501 #endif
502       }
503     }
504
505     // is the solution a new vertex ?
506     NewVertex = (DSS.SupportTypeShape2(isol) != BRepExtrema_IsVertex);
507     if (NewVertex) {
508       TopoDS_Edge E = TopoDS::Edge(DSS.SupportOnShape2(isol));
509       Standard_Real tol = Precision::PConfusion();
510       Standard_Real first,last,param;
511       BRep_Tool::Range(E,first,last);
512       tol = Max(tol,percent*Abs(last-first));
513       DSS.ParOnEdgeS2(isol,param);
514       if (Abs(first-param)<tol) {
515         NewVertex = Standard_False;
516         Vsol = TopExp::FirstVertex(E);
517       }
518       else if (Abs(last-param)<tol) {
519         NewVertex = Standard_False;
520         Vsol = TopExp::LastVertex(E);
521       }
522       // check
523       if (!NewVertex) {
524         TopoDS_Vertex VRoot;
525         if (SearchRoot(Vsol,Map,VRoot)) NewVertex = Standard_True;
526       }
527     }
528     else {
529       TopoDS_Shape aLocalShape = DSS.SupportOnShape2(isol);
530       Vsol = TopoDS::Vertex(aLocalShape);
531 //      Vsol = TopoDS::Vertex(DSS.SupportOnShape2(isol));
532     }
533
534     // it is required to cut the edge
535     if (NewVertex) {
536       TopoDS_Shape aLocalShape = DSS.SupportOnShape2(isol);
537       TopoDS_Edge E = TopoDS::Edge(aLocalShape);
538 //      TopoDS_Edge E = TopoDS::Edge(DSS.SupportOnShape2(isol));
539       TopTools_SequenceOfShape EmptySeq;
540       theEdgeNewEdges.Bind(E, EmptySeq);
541       Standard_Real first,last,param;
542       DSS.ParOnEdgeS2(isol,param);
543       BRep_Tool::Range(E,first,last);
544       BRepLib_MakeWire MW;
545       for (anExp.Init(W); anExp.More(); anExp.Next()) {
546         if (E.IsSame(anExp.Current())) {
547           Standard_Boolean SO 
548             = (anExp.CurrentVertex().IsSame(TopExp::FirstVertex(E)));
549           TopTools_SequenceOfShape SE;
550           SE.Clear();
551           TColStd_SequenceOfReal SR;
552           SR.Clear();
553           SR.Append(param);
554           TrimEdge(E,SR,first,last,SO,SE);
555           theEdgeNewEdges(E) = SE;
556           TopoDS_Vertex VV1,VV2;
557           TopExp::Vertices(TopoDS::Edge(SE.Value(1)),VV1,VV2);
558           if (TopExp::FirstVertex(E).IsSame(VV1)
559               || TopExp::LastVertex(E).IsSame(VV1)) {
560             Vsol = VV2;
561           }
562           if (TopExp::FirstVertex(E).IsSame(VV2)
563               || TopExp::LastVertex(E).IsSame(VV2)) {
564             Vsol = VV1;
565           }
566           for (Standard_Integer k=1; k<=SE.Length(); k++) {
567             MW.Add(TopoDS::Edge(SE.Value(k)));
568           }
569         }
570         else {
571           MW.Add(anExp.Current());
572         }
573       }
574       newW = MW.Wire();
575     }
576     else {
577       newW = W;
578     }
579     
580     
581   }
582
583   return NewVertex;
584
585 }
586
587
588 static void Transform (const Standard_Boolean WithRotation,
589                        const gp_Pnt& P,
590                        const gp_Pnt& Pos1,
591                        const gp_Vec& Ax1,
592                        const gp_Pnt& Pos2,
593                        const gp_Vec& Ax2,
594                        gp_Pnt& Pnew)
595 {
596
597   Pnew = P.Translated (Pos1,Pos2);
598   gp_Vec axe1 = Ax1, axe2 = Ax2; 
599   if (!axe1.IsParallel(axe2,1.e-4)) {
600     gp_Vec Vtrans(Pos1,Pos2),Vsign;
601     Standard_Real alpha,beta,sign=1;
602     alpha = Vtrans.Dot(axe1);
603     beta = Vtrans.Dot(axe2);
604     if (alpha<-1.e-7) axe1 *=-1;
605     if (beta<1.e-7) axe2 *=-1;
606     alpha = Vtrans.Dot(axe1);
607     beta = Vtrans.Dot(axe2);
608     gp_Vec norm2 = axe1 ^ axe2;
609     Vsign.SetLinearForm(Vtrans.Dot(axe1),axe2,-Vtrans.Dot(axe2),axe1);
610     alpha = Vsign.Dot(axe1);
611     beta = Vsign.Dot(axe2);
612     Standard_Boolean pasnul = (Abs(alpha)>1.e-4 && Abs(beta)>1.e-4);
613     if ( alpha*beta>0.0 && pasnul ) sign=-1;
614     gp_Ax1 Norm(Pos2,norm2);
615     Standard_Real ang = axe1.AngleWithRef(axe2,norm2);
616     if (!WithRotation) {
617       if (ang>M_PI/2) ang = ang - M_PI;
618       if (ang<-M_PI/2) ang = ang + M_PI;
619     }
620     ang *= sign;
621     Pnew = Pnew.Rotated (Norm,ang);
622   }
623 }
624
625 static void BuildConnectedEdges(const TopoDS_Wire& aWire,
626                                 const TopoDS_Edge& StartEdge,
627                                 const TopoDS_Vertex& StartVertex,
628                                 TopTools_ListOfShape& ConnectedEdges)
629 {
630   TopTools_IndexedDataMapOfShapeListOfShape MapVE;
631   TopExp::MapShapesAndAncestors(aWire, TopAbs_VERTEX, TopAbs_EDGE, MapVE);
632   TopoDS_Edge CurEdge = StartEdge;
633   TopoDS_Vertex CurVertex = StartVertex;
634   TopoDS_Vertex Origin, V1, V2;
635   TopExp::Vertices(StartEdge, V1, V2);
636   Origin = (V1.IsSame(StartVertex))? V2 : V1;
637
638   for (;;)
639     {
640       TopTools_ListIteratorOfListOfShape itE( MapVE.FindFromKey(CurVertex) );
641       for (; itE.More(); itE.Next())
642         {
643           TopoDS_Edge anEdge = TopoDS::Edge(itE.Value());
644           if (!anEdge.IsSame(CurEdge))
645             {
646               ConnectedEdges.Append(anEdge);
647               TopExp::Vertices(anEdge, V1, V2);
648               CurVertex = (V1.IsSame(CurVertex))? V2 : V1;
649               CurEdge = anEdge;
650               break;
651             }
652         }
653       if (CurVertex.IsSame(Origin))
654         break;
655     }
656 }
657                                       
658 //=======================================================================
659 //function : BRepFill_CompatibleWires
660 //purpose  : 
661 //=======================================================================
662
663 BRepFill_CompatibleWires::BRepFill_CompatibleWires() 
664 :myIsDone(Standard_False)
665 {
666 }
667
668
669 //=======================================================================
670 //function : BRepFill_CompatibleWires
671 //purpose  : 
672 //=======================================================================
673
674 BRepFill_CompatibleWires::BRepFill_CompatibleWires(const TopTools_SequenceOfShape& Sections)
675 {
676   Init(Sections);
677 }
678
679
680 //=======================================================================
681 //function : Init
682 //purpose  : 
683 //=======================================================================
684
685 void BRepFill_CompatibleWires::Init(const TopTools_SequenceOfShape& Sections)
686 {
687   myInit = Sections;
688   myWork = Sections;
689   myPercent = 0.01;
690   myIsDone = Standard_False;
691   myMap.Clear();
692
693 }
694
695
696 //=======================================================================
697 //function : SetPercent
698 //purpose  : 
699 //=======================================================================
700
701 void BRepFill_CompatibleWires::SetPercent(const Standard_Real Percent)
702 {
703   if (0.<Percent && Percent<1.) myPercent = Percent;
704
705 }
706
707
708 //=======================================================================
709 //function : IsDone
710 //purpose  : 
711 //=======================================================================
712
713 Standard_Boolean BRepFill_CompatibleWires::IsDone() const 
714 {
715   return myIsDone;
716 }
717
718
719 //=======================================================================
720 //function : Shape
721 //purpose  : 
722 //=======================================================================
723
724 const TopTools_SequenceOfShape& BRepFill_CompatibleWires::Shape() const 
725 {
726   return myWork;
727 }
728
729
730 //=======================================================================
731 //function : GeneratedShapes
732 //purpose  : 
733 //=======================================================================
734
735 const TopTools_ListOfShape& BRepFill_CompatibleWires::GeneratedShapes
736 (const TopoDS_Edge& SubSection) const
737 {  
738
739   if (myMap.IsBound(SubSection)) {
740     return myMap(SubSection);
741   }
742   else {
743     static TopTools_ListOfShape Empty;
744     return Empty;
745   }
746 }
747
748
749 //=======================================================================
750 //function : Perform
751 //purpose  : 
752 //=======================================================================
753
754 void BRepFill_CompatibleWires::Perform (const Standard_Boolean WithRotation)
755 {
756   // compute origin and orientation on wires to avoid twisted results
757   // and update wires to have same number of edges
758
759   // determination of report:
760   // if the number of elements is the same and if the wires have discontinuities
761   // by tangency, the report is not carried out by curvilinear abscissa
762   Standard_Integer nbSects = myWork.Length(), i;
763   BRepTools_WireExplorer anExp;
764   Standard_Integer nbmax=0, nbmin=0;
765   TColStd_Array1OfInteger nbEdges(1,nbSects);
766   Standard_Boolean report;
767   GeomAbs_Shape contS=GeomAbs_CN;
768   GeomAbs_Shape cont;
769   for (i=1; i<=nbSects; i++) {
770     TopoDS_Shape aLocalShape = myWork(i).Oriented(TopAbs_FORWARD);
771     myWork(i) = TopoDS::Wire(aLocalShape);
772 //    myWork(i) = TopoDS::Wire(myWork(i).Oriented(TopAbs_FORWARD));
773     TopoDS_Wire W = TopoDS::Wire(myWork(i));
774     WireContinuity(W,cont);
775     if (cont<contS) contS=cont;
776     nbEdges(i) = 0;
777     for(anExp.Init(W); anExp.More(); anExp.Next() ) nbEdges(i)++;
778     if (i==1) nbmin = nbEdges(i);
779     if (nbmax<nbEdges(i)) nbmax = nbEdges(i);
780     if (nbmin>nbEdges(i)) nbmin = nbEdges(i);
781   } 
782   // if the number of elements is not the same or if all wires are at least
783   // C1, the report is carried out by curvilinear abscissa of cuts, otherwise 
784   // a report vertex / Vertex is done
785   report = (nbmax != nbmin || contS >= GeomAbs_C1 );
786   
787   // initialization of the map
788   Standard_Integer nbE = 0;
789   TopTools_ListOfShape Empty;
790   for (i=1; i<=nbSects; i++) {
791     TopoDS_Wire W = TopoDS::Wire(myWork(i));
792     for(anExp.Init(W); anExp.More(); anExp.Next() ) {
793       TopoDS_Edge E = TopoDS::Edge(anExp.Current());
794       myMap.Bind(E,Empty);
795       myMap(E).Append(E);
796       nbE++;
797     }
798   } 
799   
800   // open/closed sections
801   // initialisation of myDegen1, myDegen2
802   Standard_Integer ideb=1, ifin=myWork.Length();
803   // check if the first wire is punctual
804   myDegen1 = Standard_True;
805   for(anExp.Init(TopoDS::Wire(myWork(ideb))); anExp.More(); anExp.Next()) {
806     myDegen1 = myDegen1 && (BRep_Tool::Degenerated(anExp.Current()));
807   }
808   if (myDegen1) ideb++;
809   // check if the last wire is punctual
810   myDegen2 = Standard_True;
811   for(anExp.Init(TopoDS::Wire(myWork(ifin))); anExp.More(); anExp.Next()) {
812     myDegen2 = myDegen2 && (BRep_Tool::Degenerated(anExp.Current()));
813   }
814   if (myDegen2) ifin--;
815   
816   Standard_Boolean wClosed, allClosed = Standard_True, allOpen = Standard_True;
817   for (i=ideb; i<=ifin; i++) {
818     wClosed = myWork(i).Closed();
819     if (!wClosed) {
820       // check if the vertices are the same.
821       TopoDS_Vertex V1, V2;
822       TopExp::Vertices(TopoDS::Wire(myWork(i)),V1,V2);
823       if ( V1.IsSame(V2)) wClosed = Standard_True;
824     }
825     allClosed = (allClosed && wClosed);
826     allOpen = (allOpen && !wClosed);
827   }
828   
829   if (allClosed) {
830     // All sections are closed 
831     if (report) {
832       // same number of elements  
833       SameNumberByPolarMethod(WithRotation);
834     }
835     else {
836       // origin
837       ComputeOrigin(Standard_False);
838     }
839     myIsDone = Standard_True;
840   }
841   else if (allOpen) {
842     // All sections are open
843     // origin
844     SearchOrigin();
845     // same number of elements
846     if (report) {
847       SameNumberByACR(report);
848     }
849     myIsDone = Standard_True;
850   }
851   else {
852     // There are open and closed sections :
853     // not processed
854     throw Standard_DomainError("Sections must be all closed or all open");
855   }
856   
857 }
858
859
860
861
862 //=======================================================================
863 //function : Generated
864 //purpose  : 
865 //=======================================================================
866
867 const TopTools_DataMapOfShapeListOfShape&  BRepFill_CompatibleWires::Generated() const 
868 {
869   return myMap;
870 }
871
872
873 //=======================================================================
874 //function : SameNumberByPolarMethod
875 //purpose  : 
876 //=======================================================================
877
878 void BRepFill_CompatibleWires::
879               SameNumberByPolarMethod(const Standard_Boolean WithRotation)
880 {
881
882   // initialisation 
883   Standard_Integer NbSects=myWork.Length();
884   BRepTools_WireExplorer anExp;
885   TopTools_DataMapOfShapeSequenceOfShape EdgeNewEdges;
886
887   Standard_Boolean allClosed = Standard_True;
888   Standard_Integer i,ii,ideb=1,ifin=NbSects;
889
890   for (i=1; i<=NbSects; i++) {
891     Handle(BRepCheck_Wire) Checker = new BRepCheck_Wire(TopoDS::Wire(myWork(i)));
892     allClosed = (allClosed && (Checker->Closed() == BRepCheck_NoError));
893     //allClosed = (allClosed && myWork(i).Closed());
894   }
895   if (!allClosed)
896     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SameNumberByPolarMethod : the wires must be closed");
897   
898   // sections ponctuelles, sections bouclantes ?
899   if (myDegen1) ideb++;
900   if (myDegen2) ifin--;
901   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
902                                 && (myWork(ideb).IsSame(myWork(ifin)));
903
904   //Removing degenerated edges
905   for (i = ideb; i <= ifin; i++)
906   {
907     Standard_Boolean hasDegEdge = Standard_False;
908     TopoDS_Iterator anItw(myWork(i));
909     for (; anItw.More(); anItw.Next())
910     {
911       const TopoDS_Edge& anEdge = TopoDS::Edge(anItw.Value());
912       if (BRep_Tool::Degenerated(anEdge))
913       {
914         hasDegEdge = Standard_True;
915         break;
916       }
917     }
918     if (hasDegEdge)
919     {
920       TopoDS_Wire aNewWire;
921       BRep_Builder aBBuilder;
922       aBBuilder.MakeWire(aNewWire);
923       for (anItw.Initialize(myWork(i)); anItw.More(); anItw.Next())
924       {
925         const TopoDS_Edge& anEdge = TopoDS::Edge(anItw.Value());
926         if (!BRep_Tool::Degenerated(anEdge))
927           aBBuilder.Add(aNewWire, anEdge);
928       }
929       myWork(i) = aNewWire;
930     }
931   }
932   
933   // Nombre max de decoupes possibles
934   Standard_Integer NbMaxV = 0;
935   for (i=1; i<=NbSects; i++) {
936     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
937       NbMaxV++;
938     }
939   }
940   
941   // construction of tables of planes of wires 
942   gp_Pln P;
943   Handle(TColgp_HArray1OfPnt) Pos
944     = new (TColgp_HArray1OfPnt) (1,NbSects);
945   Handle(TColgp_HArray1OfVec) Axe
946     = new (TColgp_HArray1OfVec) (1,NbSects);
947   for (i=ideb;i<=ifin;i++) {
948     if (PlaneOfWire(TopoDS::Wire(myWork(i)),P)) {
949       Pos->SetValue(i,P.Location());
950       Axe->SetValue(i,gp_Vec(P.Axis().Direction()));
951     }
952   }
953   TopTools_SequenceOfShape SeqV;
954   if (myDegen1) {
955     SeqOfVertices(TopoDS::Wire(myWork(1)),SeqV);
956     Pos->SetValue(1,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
957     Axe->SetValue(1,Axe->Value(ideb));
958   }
959   if (myDegen2) {
960     SeqOfVertices(TopoDS::Wire(myWork(NbSects)),SeqV);
961     Pos->SetValue(NbSects,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
962     Axe->SetValue(NbSects,Axe->Value(ifin));
963   }
964   
965   // construction of RMap, map of reports of wire i to wire i-1
966   TopTools_DataMapOfShapeListOfShape RMap;
967   RMap.Clear();
968   
969   // loop on i
970   for (i=ifin; i>ideb; i--) {
971     
972     const TopoDS_Wire& wire1 = TopoDS::Wire(myWork(i));
973     
974     // sequence of vertices of the first wire
975     SeqOfVertices(wire1,SeqV);
976     if (SeqV.Length()>NbMaxV) 
977       throw Standard_NoSuchObject("BRepFill::SameNumberByPolarMethod failed");
978     
979     // loop on vertices of wire1
980     for (ii=1;ii<=SeqV.Length();ii++) {
981       
982       TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
983       
984       // init of RMap for Vi
985       TopTools_ListOfShape Init;
986       Init.Clear();
987       RMap.Bind(Vi,Init);
988       
989       // it is required to find intersection Vi - wire2
990       gp_Pnt Pi = BRep_Tool::Pnt(Vi);
991       
992       // return Pi in the current plane
993       gp_Pnt Pnew;
994       Transform(WithRotation,Pi,
995                 Pos->Value(i),Axe->Value(i), 
996                 Pos->Value(i-1),Axe->Value(i-1),Pnew);
997       
998       // calculate the intersection
999       TopoDS_Shape Support;
1000       Standard_Boolean NewVertex;
1001       TopoDS_Vertex Vsol;
1002       TopoDS_Wire newwire;
1003       if (Pnew.Distance(Pos->Value(i-1))>Precision::Confusion()) {
1004         Standard_Real percent = myPercent;
1005         NewVertex = EdgeIntersectOnWire(Pos->Value(i-1),Pnew,percent,
1006                                         RMap,TopoDS::Wire(myWork(i-1)),
1007                                         Vsol,newwire,EdgeNewEdges);
1008         if (NewVertex) myWork(i-1) = newwire;
1009         RMap(Vi).Append(Vsol);
1010       }
1011       
1012     } // loop on  ii
1013   }   // loop on  i
1014   
1015   // initialisation of MapVLV, map of correspondences vertex - list of vertices
1016   TopTools_DataMapOfShapeListOfShape MapVLV;
1017   SeqOfVertices(TopoDS::Wire(myWork(ideb)),SeqV);
1018   Standard_Integer SizeMap = SeqV.Length();
1019   MapVLV.Clear();
1020   for (ii=1;ii<=SizeMap;ii++) {
1021     TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
1022     TopTools_ListOfShape Init;
1023     Init.Clear();
1024     Init.Append(Vi);
1025     MapVLV.Bind(Vi,Init);
1026     Standard_Integer NbV = 1;
1027     TopoDS_Vertex V0,V1;
1028     V0 = Vi;
1029     Standard_Boolean tantque = SearchRoot(V0,RMap,V1);
1030     while (tantque) {
1031       MapVLV(Vi).Append(V1);
1032       NbV++;
1033       // test on NbV required for looping sections 
1034       if (V1.IsSame(Vi) || NbV >= myWork.Length()) {
1035         tantque = Standard_False;
1036       }
1037       else {
1038         V0 = V1;
1039         tantque = SearchRoot(V0,RMap,V1);
1040       }
1041     }
1042   }
1043   
1044   // loop on i
1045   for (i=ideb; i<ifin; i++) {
1046     
1047     const TopoDS_Wire& wire1 = TopoDS::Wire(myWork(i));
1048     
1049     // sequence of vertices of the first wire
1050     SeqOfVertices(wire1,SeqV);
1051     if ( SeqV.Length()>NbMaxV || SeqV.Length()>SizeMap ) 
1052       throw Standard_NoSuchObject("BRepFill::SameNumberByPolarMethod failed");
1053     
1054
1055     // next wire 
1056     const TopoDS_Wire& wire2 = TopoDS::Wire(myWork(i+1));
1057     
1058     // loop on vertices of wire1
1059     for (ii=1;ii<=SeqV.Length();ii++) {
1060       
1061       TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
1062       TopoDS_Vertex VRoot;
1063       VRoot.Nullify();
1064       Standard_Boolean intersect = Standard_True;
1065       if (SearchRoot(Vi,MapVLV,VRoot)) {
1066         const TopTools_ListOfShape& LVi = MapVLV(VRoot);
1067         TopoDS_Vertex VonW;
1068         VonW.Nullify();
1069         intersect = (!SearchVertex(LVi,wire2,VonW));
1070       }
1071       
1072       if (intersect) {
1073         // it is necessary to find intersection Vi - wire2
1074         gp_Pnt Pi = BRep_Tool::Pnt(Vi);
1075         
1076         // return Pi in the current plane
1077         gp_Pnt Pnew;
1078         Transform(WithRotation,Pi,
1079                   Pos->Value(i),Axe->Value(i), 
1080                   Pos->Value(i+1),Axe->Value(i+1),Pnew);
1081         
1082         // calculate the intersection
1083         TopoDS_Shape Support;
1084         Standard_Boolean NewVertex;
1085         TopoDS_Vertex Vsol;
1086         TopoDS_Wire newwire;
1087         if (Pnew.Distance(Pos->Value(i+1))>Precision::Confusion()) {
1088           Standard_Real percent = myPercent;
1089           NewVertex = EdgeIntersectOnWire(Pos->Value(i+1),Pnew,percent,
1090                                           MapVLV,TopoDS::Wire(myWork(i+1)),
1091                                           Vsol,newwire,EdgeNewEdges);
1092           MapVLV(VRoot).Append(Vsol);
1093           if (NewVertex) myWork(i+1) = newwire;
1094         }
1095         
1096       }
1097     } // loop on ii
1098   }   // loop on i
1099   
1100   // regularize wires following MapVLV
1101   TopoDS_Wire wire = TopoDS::Wire(myWork(ideb));
1102
1103   // except for the last if the sections loop 
1104   Standard_Integer ibout = ifin;
1105   if (vClosed) ibout--;
1106
1107   for ( i=ideb+1; i<=ibout; i++) {
1108
1109     BRepLib_MakeWire MW;
1110
1111     anExp.Init(wire);
1112     TopoDS_Edge ECur = anExp.Current();
1113     TopoDS_Vertex VF,VL;
1114     TopExp::Vertices(ECur,VF,VL,Standard_True);
1115     Standard_Real U1 = BRep_Tool::Parameter(VF,ECur);
1116     Standard_Real U2 = BRep_Tool::Parameter(VL,ECur);
1117     BRepAdaptor_Curve Curve(ECur);
1118     gp_Pnt PPs = Curve.Value(0.1*(U1+9*U2));
1119     TopTools_ListIteratorOfListOfShape itF(MapVLV(VF)),itL(MapVLV(VL));
1120     Standard_Integer rang = ideb;
1121     while (rang < i) {
1122       itF.Next();
1123       itL.Next();
1124       rang++;
1125     }
1126     TopoDS_Vertex V1 = TopoDS::Vertex(itF.Value()), V2 = TopoDS::Vertex(itL.Value());
1127     TopoDS_Edge Esol;
1128     Standard_Real scalmax=0.;
1129     TopoDS_Iterator itW( myWork(i) );
1130     
1131     for(; itW.More(); itW.Next())
1132       {
1133         TopoDS_Edge E = TopoDS::Edge(itW.Value());
1134         TopoDS_Vertex VVF,VVL;
1135         TopExp::Vertices(E,VVF,VVL,Standard_True);
1136         
1137         // parse candidate edges
1138         Standard_Real scal1,scal2;
1139         if ( (V1.IsSame(VVF)&&V2.IsSame(VVL)) || (V2.IsSame(VVF)&&V1.IsSame(VVL)) ) {
1140           Standard_Real U1param = BRep_Tool::Parameter(VVF,E);
1141           Standard_Real U2param = BRep_Tool::Parameter(VVL,E);
1142           BRepAdaptor_Curve CurveE(E);
1143           gp_Pnt PP1 = CurveE.Value(0.1*(U1param +9* U2param));
1144           gp_Pnt PP2 = CurveE.Value(0.1*(9* U1param + U2param));
1145   
1146           for (rang=i;rang>ideb;rang--) {
1147             Transform(WithRotation, PP1,
1148                       Pos->Value(rang), Axe->Value(rang),
1149                       Pos->Value(rang-1), Axe->Value(rang-1), PP1);
1150             Transform(WithRotation, PP2,
1151                       Pos->Value(rang), Axe->Value(rang),
1152                       Pos->Value(rang-1), Axe->Value(rang-1), PP2);
1153           }
1154           gp_Vec Ns(Pos->Value(ideb),PPs);
1155           Ns = Ns.Normalized();
1156           gp_Vec N1(Pos->Value(ideb),PP1);
1157           N1 = N1.Normalized();
1158           gp_Vec N2(Pos->Value(ideb),PP2);
1159           N2 = N2.Normalized();
1160           scal1 = N1.Dot(Ns);
1161           if (scal1>scalmax) {
1162             scalmax = scal1;
1163             Esol = E;
1164           }
1165           scal2 = N2.Dot(Ns);
1166           if (scal2>scalmax) {
1167             scalmax = scal2;
1168             TopoDS_Shape aLocalShape = E.Reversed();
1169             Esol = TopoDS::Edge(aLocalShape);
1170           }
1171         }
1172       } //end of for(; itW.More(); itW.Next())
1173     if (Esol.IsNull())
1174       throw Standard_ConstructionError("BRepFill :: profiles are inconsistent");
1175     MW.Add(Esol);
1176
1177     TopTools_ListOfShape ConnectedEdges;
1178     BuildConnectedEdges( TopoDS::Wire(myWork(i)), Esol, V2, ConnectedEdges );
1179
1180     TopTools_ListIteratorOfListOfShape itCE(ConnectedEdges);
1181     for(; anExp.More(), itCE.More(); anExp.Next(), itCE.Next())
1182       {
1183         ECur = anExp.Current();
1184         TopExp::Vertices(ECur,VF,VL,Standard_True);
1185         U1 = BRep_Tool::Parameter(VF,ECur);
1186         U2 = BRep_Tool::Parameter(VL,ECur);
1187         Curve.Initialize(ECur);
1188         PPs = Curve.Value(0.1*(U1+9*U2));
1189         
1190         TopoDS_Edge E = TopoDS::Edge(itCE.Value());
1191         TopoDS_Vertex VVF,VVL;
1192         TopExp::Vertices(E,VVF,VVL,Standard_True);
1193
1194         // parse candidate edges
1195         Standard_Real scal1,scal2;
1196         U1 = BRep_Tool::Parameter(VVF,E);
1197         U2 = BRep_Tool::Parameter(VVL,E);
1198         Curve.Initialize(E);
1199         gp_Pnt PP1 = Curve.Value(0.1*(U1+9*U2));
1200         gp_Pnt PP2 = Curve.Value(0.1*(9*U1+U2));
1201         
1202         for (rang=i;rang>ideb;rang--) {
1203           Transform(WithRotation, PP1,
1204                     Pos->Value(rang), Axe->Value(rang),
1205                     Pos->Value(rang-1), Axe->Value(rang-1), PP1);
1206           Transform(WithRotation, PP2,
1207                     Pos->Value(rang), Axe->Value(rang),
1208                     Pos->Value(rang-1), Axe->Value(rang-1), PP2);
1209         }
1210         gp_Vec Ns(Pos->Value(ideb),PPs);
1211         Ns = Ns.Normalized();
1212         gp_Vec N1(Pos->Value(ideb),PP1);
1213         N1 = N1.Normalized();
1214         gp_Vec N2(Pos->Value(ideb),PP2);
1215         N2 = N2.Normalized();
1216         scal1 = N1.Dot(Ns);
1217         scal2 = N2.Dot(Ns);
1218         if (scal2>scal1)
1219           E.Reverse();
1220         MW.Add(E);
1221       }
1222     myWork(i) = MW.Wire();
1223   }
1224   
1225   // blocking sections?
1226   if (vClosed) myWork(myWork.Length()) = myWork(1);
1227
1228   // check the number of edges for debug
1229   Standard_Integer nbmax=0, nbmin=0;
1230   for ( i=ideb; i<=ifin; i++) {
1231     Standard_Integer nbEdges=0;
1232     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1233       nbEdges++;
1234     }
1235     if (i==ideb) nbmin = nbEdges;
1236     if (nbmax<nbEdges) nbmax = nbEdges;
1237     if (nbmin>nbEdges) nbmin = nbEdges;
1238   }
1239   if (nbmin!=nbmax) {
1240     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SameNumberByPolarMethod failed");
1241   }
1242
1243   //Fill <myMap>
1244   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itmap(myMap);
1245   for (; itmap.More(); itmap.Next())
1246   {
1247     TopoDS_Shape anEdge = itmap.Key();
1248     TopTools_ListOfShape ListOfNewEdges;
1249
1250     //for each edge of <myMap> find all newest edges
1251     //in <EdgeNewEdges> recursively
1252     AddNewEdge(anEdge, EdgeNewEdges, ListOfNewEdges);
1253     
1254     myMap(anEdge) = ListOfNewEdges;
1255   }
1256 }
1257
1258 //=======================================================================
1259 //function : SameNumberByACR
1260 //purpose  : 
1261 //=======================================================================
1262
1263 void BRepFill_CompatibleWires::SameNumberByACR(const  Standard_Boolean  report)
1264 {
1265   // find the dimension
1266   Standard_Integer ideb=1, ifin=myWork.Length();
1267   BRepTools_WireExplorer anExp;
1268
1269   // point sections, blocking  sections?
1270   if (myDegen1) ideb++;
1271   if (myDegen2) ifin--;
1272   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
1273                                 && (myWork(ideb).IsSame(myWork(ifin)));
1274
1275   Standard_Integer nbSects = myWork.Length(), i;
1276   Standard_Integer nbmax=0, nbmin=0;
1277   TColStd_Array1OfInteger nbEdges(1,nbSects);
1278   for (i=1; i<=nbSects; i++) {
1279     nbEdges(i) = 0;
1280     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1281       nbEdges(i)++;
1282     }
1283     if (i==1) nbmin = nbEdges(i);
1284     if (nbmax<nbEdges(i)) nbmax = nbEdges(i);
1285     if (nbmin>nbEdges(i)) nbmin = nbEdges(i);
1286   }
1287
1288   if (nbmax>1) {
1289     // several edges
1290
1291     if (report || nbmin<nbmax) {
1292       // insertion of cuts
1293       Standard_Integer nbdec=(nbmax-1)*nbSects+1;
1294       TColStd_Array1OfReal dec(1,nbdec);
1295       dec.Init(0);
1296       dec(2)=1;
1297
1298       TColStd_Array1OfReal WireLen(1, nbSects);
1299       
1300       // calculate the table of cuts
1301       Standard_Integer j,k,l;
1302       for (i=1; i<=nbSects; i++) {
1303         // current wire
1304         const TopoDS_Wire& wire1 = TopoDS::Wire(myWork(i));
1305         Standard_Integer nbE = 0;
1306         for(anExp.Init(wire1); anExp.More(); anExp.Next()) {
1307           nbE++;
1308         }
1309         // length and ACR of the wire 
1310         TColStd_Array1OfReal ACR(0,nbE);
1311         ACR.Init(0);
1312         BRepFill::ComputeACR(wire1, ACR);
1313         WireLen(i) = ACR(0);
1314         // insertion of ACR of the wire in the table of cuts
1315         for (j=1; j<ACR.Length()-1; j++) {
1316           k=1;
1317           while (dec(k)<ACR(j)) {
1318             k++;
1319             if (k>nbdec) break;
1320           }
1321           if (dec(k-1)<ACR(j)&& ACR(j)<dec(k)) {
1322             for (l=nbdec-1;l>=k;l--) {
1323               dec(l+1)=dec(l);
1324             }
1325             dec(k) = ACR(j);
1326           }
1327         }
1328       }
1329       
1330       // table of cuts
1331       k=1;
1332       while (dec(k)<1) {
1333         k++;
1334         if (k>nbdec) break;
1335       }
1336       nbdec = k-1;
1337       TColStd_Array1OfReal dec2(1,nbdec);
1338       for (k=1;k<=nbdec;k++) {
1339         dec2(k) = dec(k);
1340       }
1341       
1342       //Check of cuts: are all the new edges long enouph or not
1343       TColStd_MapOfInteger CutsToRemove;
1344       for (k = 1; k <= nbdec; k++)
1345       {
1346         Standard_Real Knot1 = dec2(k);
1347         Standard_Real Knot2 = (k == nbdec)? 1. : dec2(k+1);
1348         Standard_Real AllLengthsNull = Standard_True;
1349         for (i = 1; i <= nbSects; i++)
1350         {
1351           Standard_Real EdgeLen = (Knot2 - Knot1) * WireLen(i);
1352           if (EdgeLen > Precision::Confusion())
1353           {
1354             AllLengthsNull = Standard_False;
1355             break;
1356           }
1357         }
1358         if (AllLengthsNull)
1359           CutsToRemove.Add(k);
1360       }
1361       Standard_Integer NewNbDec = nbdec - CutsToRemove.Extent();
1362       TColStd_Array1OfReal dec3(1, NewNbDec);
1363       i = 1;
1364       for (k = 1; k <= nbdec; k++)
1365         if (!CutsToRemove.Contains(k))
1366           dec3(i++) = dec2(k);
1367       ///////////////////
1368       
1369       // insertion of cuts in each wire
1370       for (i=1; i<=nbSects; i++) {
1371         const TopoDS_Wire& oldwire = TopoDS::Wire(myWork(i));
1372         Standard_Real tol = Precision::Confusion() / WireLen(i);
1373         TopoDS_Wire newwire = BRepFill::InsertACR(oldwire, dec3, tol);
1374         BRepTools_WireExplorer anExp1,anExp2;
1375         anExp1.Init(oldwire);
1376         anExp2.Init(newwire);
1377         for (;anExp1.More();anExp1.Next()) {
1378           const TopoDS_Edge& Ecur = anExp1.Current();
1379           if (!Ecur.IsSame(TopoDS::Edge(anExp2.Current()))) {
1380             TopTools_ListOfShape LE;
1381             LE.Clear();
1382             gp_Pnt P1,P2;
1383             const TopoDS_Vertex& V1 = anExp1.CurrentVertex();
1384             TopoDS_Vertex VF,VR;
1385             TopExp::Vertices(Ecur,VF,VR,Standard_True);
1386             if (V1.IsSame(VF)) P1 = BRep_Tool::Pnt(VR);
1387             if (V1.IsSame(VR)) P1 = BRep_Tool::Pnt(VF);
1388             TopoDS_Vertex V2 = anExp2.CurrentVertex();
1389             TopExp::Vertices(TopoDS::Edge(anExp2.Current()),
1390                              VF,VR,Standard_True);
1391             if (V2.IsSame(VF)) P2 = BRep_Tool::Pnt(VR);
1392             if (V2.IsSame(VR)) P2 = BRep_Tool::Pnt(VF);
1393             while (P1.Distance(P2)>1.e-3) {
1394               LE.Append(anExp2.Current());
1395               anExp2.Next();
1396               V2 = anExp2.CurrentVertex();
1397               TopExp::Vertices(TopoDS::Edge(anExp2.Current()),
1398                                VF,VR,Standard_True);
1399               if (V2.IsSame(VF)) P2 = BRep_Tool::Pnt(VR);
1400               if (V2.IsSame(VR)) P2 = BRep_Tool::Pnt(VF);
1401               if (P1.Distance(P2)<=1.e-3) {
1402                 LE.Append(anExp2.Current());
1403                 anExp2.Next();
1404               }
1405             }
1406
1407             TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itmap;
1408             //TopTools_ListIteratorOfListOfShape itlist;
1409             TopoDS_Edge Ancestor;
1410             Standard_Integer nbedge, nblist=0;
1411             Standard_Boolean found = Standard_False;
1412
1413             for (itmap.Initialize(myMap);itmap.More()&&(!found);itmap.Next()) {
1414               nblist++;
1415               TopTools_ListIteratorOfListOfShape itlist(itmap.Value());
1416               nbedge = 0;
1417               while (itlist.More()&&(!found)) {
1418                 nbedge++;
1419                 TopoDS_Edge ECur = TopoDS::Edge(itlist.Value());
1420                     
1421                 if (Ecur.IsSame(ECur)) {
1422                   Ancestor = TopoDS::Edge(itmap.Key());
1423                   found = Standard_True;
1424                   myMap(Ancestor).InsertBefore(LE,itlist);
1425                   myMap(Ancestor).Remove(itlist);
1426                 }
1427                 if (itlist.More()) itlist.Next();
1428               }
1429               
1430             }
1431
1432           }
1433           else {
1434             anExp2.Next();
1435           }
1436           
1437         }
1438         myWork(i) = newwire;
1439       }
1440       
1441     }
1442   }
1443   
1444   // blocking sections ?
1445   if (vClosed) myWork(myWork.Length()) = myWork(1);
1446
1447   // check the number of edges for debug
1448   nbmax = 0;
1449   for (i=ideb; i<=ifin; i++) {
1450     nbEdges(i) = 0;
1451     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1452       nbEdges(i)++;
1453     }
1454     if (i==ideb) nbmin = nbEdges(i);
1455     if (nbmax<nbEdges(i)) nbmax = nbEdges(i);
1456     if (nbmin>nbEdges(i)) nbmin = nbEdges(i);
1457   }
1458   if (nbmax!=nbmin) 
1459     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SameNumberByACR failed");
1460 }
1461
1462 //=======================================================================
1463 //function : ComputeOrigin
1464 //purpose  : 
1465 //=======================================================================
1466
1467 void BRepFill_CompatibleWires::ComputeOrigin(const  Standard_Boolean /*polar*/ )
1468 {
1469   // reorganize the wires respecting orientation and origin
1470   
1471   TopoDS_Vertex Vdeb, Vfin;
1472   gp_Pnt Pdeb, Psuiv, PPs;
1473
1474   BRepTools_WireExplorer anExp;
1475
1476   Standard_Boolean wClosed, allClosed = Standard_True;
1477
1478   Standard_Integer NbSects = myWork.Length();
1479   Standard_Integer i, ideb=1,ifin=NbSects;
1480
1481   // point sections, blocking sections 
1482   if (myDegen1) ideb++;
1483   if (myDegen2) ifin--;
1484   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
1485                                 && (myWork(ideb).IsSame(myWork(ifin)));
1486   
1487   
1488   for (i=ideb; i<=ifin; i++) {
1489     wClosed = myWork(i).Closed();
1490     if (!wClosed) {
1491       // check if the vertices are the same.
1492       TopoDS_Vertex V1, V2;
1493       TopExp::Vertices(TopoDS::Wire(myWork(i)),V1,V2);
1494       if ( V1.IsSame(V2)) wClosed = Standard_True;
1495     }
1496     allClosed = (allClosed && wClosed);
1497   }
1498 /*
1499   for (i=ideb; i<=ifin; i++) {
1500     allClosed = (allClosed && myWork(i).Closed());
1501   }
1502 */
1503   if (!allClosed) 
1504     throw Standard_NoSuchObject("BRepFill_CompatibleWires::ComputeOrigin : the wires must be closed");
1505
1506 /*  
1507   // Max number of possible cuts
1508   Standard_Integer NbMaxV = 0;
1509   for (i=1; i<=NbSects; i++) {
1510     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1511       NbMaxV++;
1512     }
1513   }
1514   
1515   // construction of tables of planes of wires 
1516   gp_Pln P;  
1517   Handle(TColgp_HArray1OfPnt) Pos
1518     = new (TColgp_HArray1OfPnt) (1,NbSects);
1519   Handle(TColgp_HArray1OfVec) Axe
1520     = new (TColgp_HArray1OfVec) (1,NbSects);
1521   for (i=ideb;i<=ifin;i++) {
1522     if (PlaneOfWire(TopoDS::Wire(myWork(i)),P)) {
1523       Pos->SetValue(i,P.Location());
1524       Axe->SetValue(i,gp_Vec(P.Axis().Direction()));
1525     }
1526   }
1527   TopTools_SequenceOfShape SeqV;
1528   if (myDegen1) {
1529     SeqOfVertices(TopoDS::Wire(myWork(1)),SeqV);
1530     Pos->SetValue(1,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
1531     Axe->SetValue(1,Axe->Value(ideb));
1532   }
1533   if (myDegen2) {
1534     SeqOfVertices(TopoDS::Wire(myWork(NbSects)),SeqV);
1535     Pos->SetValue(NbSects,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
1536     Axe->SetValue(NbSects,Axe->Value(ifin));
1537   }
1538 */
1539
1540   //Consider that all wires have same number of edges (polar==Standard_False)
1541   TopTools_SequenceOfShape PrevSeq;
1542   TopTools_SequenceOfShape PrevEseq;
1543   Standard_Integer theLength = 0;
1544   const TopoDS_Wire& wire = TopoDS::Wire( myWork(ideb) );
1545   for (anExp.Init(wire); anExp.More(); anExp.Next())
1546     {
1547       PrevSeq.Append(anExp.CurrentVertex());
1548       PrevEseq.Append(anExp.Current());
1549       theLength++;
1550     }
1551
1552   Standard_Integer nbs, NbSamples = 0;
1553   if (theLength <= 2)
1554     NbSamples = 4;
1555   gp_Pln FirstPlane;
1556   PlaneOfWire(TopoDS::Wire(myWork(ideb)), FirstPlane);
1557   gp_Pnt FirstBary = FirstPlane.Location();
1558   gp_Vec NormalOfFirstPlane = FirstPlane.Axis().Direction();
1559   for (i = ideb+1; i <= ifin; i++)
1560     {
1561       const TopoDS_Wire& aWire = TopoDS::Wire(myWork(i));
1562
1563       //Compute offset vector as current bary center projected on first plane
1564       //to first bary center
1565       gp_Pln CurPlane;
1566       PlaneOfWire(aWire, CurPlane);
1567       gp_Pnt CurBary = CurPlane.Location();
1568       gp_Vec aVec(FirstBary, CurBary);
1569       gp_Vec anOffsetProj = (aVec * NormalOfFirstPlane) * NormalOfFirstPlane;
1570       CurBary.Translate(-anOffsetProj); //projected current bary center
1571       gp_Vec Offset(CurBary, FirstBary);
1572       
1573       TopoDS_Wire newwire;
1574       BRep_Builder BB;
1575       BB.MakeWire(newwire);
1576       
1577       TopTools_SequenceOfShape SeqVertices, SeqEdges;
1578       for (anExp.Init(aWire); anExp.More(); anExp.Next())
1579         {
1580           SeqVertices.Append( anExp.CurrentVertex() );
1581           SeqEdges.Append( anExp.Current() );
1582         }
1583       
1584       Standard_Real MinSumDist = Precision::Infinite();
1585       Standard_Integer jmin = 1, j, k, n;
1586       Standard_Boolean forward = Standard_False;
1587       if (i == myWork.Length() && myDegen2)
1588         {
1589           // last point section
1590           jmin = 1;
1591           forward = Standard_True;
1592         }
1593       else
1594         for (j = 1; j <= theLength; j++)
1595           {
1596             //Forward
1597             Standard_Real SumDist = 0.;
1598             for (k = j, n = 1; k <= theLength; k++, n++)
1599               {
1600                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1601                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1602                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1603                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1604                 SumDist += Pprev.Distance(P);
1605                 if (NbSamples > 0)
1606                 {
1607                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1608                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k));
1609                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1610                   BRepAdaptor_Curve Ecurve(CurEdge);
1611                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1612                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1613                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1614                   {
1615                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1616                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1617                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1618                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1619                       (Ecurve.FirstParameter() + nbs*SampleOnCur) :
1620                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur);
1621                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1622                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1623                     SumDist += PonPrev.Distance(PonCur);
1624                   }
1625                 }
1626               }
1627             for (k = 1; k < j; k++, n++)
1628               {
1629                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1630                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1631                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1632                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1633                 SumDist += Pprev.Distance(P);
1634                 if (NbSamples > 0)
1635                 {
1636                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1637                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k));
1638                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1639                   BRepAdaptor_Curve Ecurve(CurEdge);
1640                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1641                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1642                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1643                   {
1644                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1645                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1646                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1647                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1648                       (Ecurve.FirstParameter() + nbs*SampleOnCur) :
1649                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur);
1650                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1651                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1652                     SumDist += PonPrev.Distance(PonCur);
1653                   }
1654                 }
1655               }
1656             if (SumDist < MinSumDist)
1657               {
1658                 MinSumDist = SumDist;
1659                 jmin = j;
1660                 forward = Standard_True;
1661               }
1662             
1663             //Backward
1664             SumDist = 0.;
1665             for (k = j, n = 1; k >= 1; k--, n++)
1666               {
1667                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1668                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1669                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1670                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1671                 SumDist += Pprev.Distance(P);
1672                 if (NbSamples > 0)
1673                 {
1674                   Standard_Integer k_cur = k-1;
1675                   if (k_cur == 0)
1676                     k_cur = theLength;
1677                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1678                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k_cur));
1679                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1680                   BRepAdaptor_Curve Ecurve(CurEdge);
1681                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1682                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1683                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1684                   {
1685                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1686                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1687                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1688                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1689                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur) :
1690                       (Ecurve.FirstParameter() + nbs*SampleOnCur);
1691                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1692                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1693                     SumDist += PonPrev.Distance(PonCur);
1694                   }
1695                 }
1696               }
1697             for (k = theLength; k > j; k--, n++)
1698               {
1699                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1700                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1701                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1702                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1703                 SumDist += Pprev.Distance(P);
1704                 if (NbSamples > 0)
1705                 {
1706                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1707                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k-1));
1708                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1709                   BRepAdaptor_Curve Ecurve(CurEdge);
1710                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1711                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1712                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1713                   {
1714                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1715                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1716                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1717                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1718                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur) :
1719                       (Ecurve.FirstParameter() + nbs*SampleOnCur);
1720                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1721                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1722                     SumDist += PonPrev.Distance(PonCur);
1723                   }
1724                 }
1725               }
1726             if (SumDist < MinSumDist)
1727               {
1728                 MinSumDist = SumDist;
1729                 jmin = j;
1730                 forward = Standard_False;
1731               }
1732           }
1733       
1734       PrevSeq.Clear();
1735       PrevEseq.Clear();
1736       if (forward)
1737         {
1738           for (j = jmin; j <= theLength; j++)
1739             {
1740               BB.Add( newwire, TopoDS::Edge(SeqEdges(j)) );
1741               PrevSeq.Append( SeqVertices(j) );
1742               PrevEseq.Append( SeqEdges(j) );
1743             }
1744           for (j = 1; j < jmin; j++)
1745             {
1746               BB.Add( newwire, TopoDS::Edge(SeqEdges(j)) );
1747               PrevSeq.Append( SeqVertices(j) );
1748               PrevEseq.Append( SeqEdges(j) );
1749             }
1750         }
1751       else
1752         {
1753           for (j = jmin-1; j >= 1; j--)
1754             {
1755               TopoDS_Shape aLocalShape = SeqEdges(j).Reversed();
1756               BB.Add( newwire, TopoDS::Edge(aLocalShape) );
1757               //PrevSeq.Append( SeqVertices(j) );
1758               PrevEseq.Append( SeqEdges(j).Reversed() );
1759             }
1760           for (j = theLength; j >= jmin; j--)
1761             {
1762               TopoDS_Shape aLocalShape = SeqEdges(j).Reversed();
1763               BB.Add( newwire, TopoDS::Edge(aLocalShape) );
1764               //PrevSeq.Append( SeqVertices(j) );
1765               PrevEseq.Append( SeqEdges(j).Reversed() );
1766             }
1767           for (j = jmin; j >= 1; j--)
1768             PrevSeq.Append( SeqVertices(j) );
1769           for (j = theLength; j > jmin; j--)
1770             PrevSeq.Append( SeqVertices(j) );
1771         }
1772       
1773       newwire.Closed( Standard_True );
1774       newwire.Orientation( TopAbs_FORWARD );
1775       myWork(i) = newwire;
1776     }
1777 #ifdef OCCT_DEBUG_EFV
1778
1779   for ( i=ideb; i<=myWork.Length(); i++) {
1780     
1781     const TopoDS_Wire& wire = TopoDS::Wire(myWork(i));
1782     
1783     Standard_Integer nbEdges=0;
1784     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next())
1785       nbEdges++;
1786     TopExp::Vertices(wire,Vdeb,Vfin);
1787     Standard_Boolean wClosed = wire.Closed();
1788     if (!wClosed) {
1789       // on regarde quand meme si les vertex sont les memes.
1790       if ( Vdeb.IsSame(Vfin)) wClosed = Standard_True;
1791     }
1792     
1793     
1794     TopoDS_Vertex Vsuiv, VF, VR;
1795     TopoDS_Wire newwire;
1796     BRep_Builder BW;
1797     BW.MakeWire(newwire);
1798     if (i==ideb) {
1799       anExp.Init(wire);
1800       const TopoDS_Edge Ecur = TopoDS::Edge(anExp.Current());
1801       TopExp::Vertices(Ecur,VF,VR);
1802       if (Vdeb.IsSame(VF)) Vsuiv=VR;
1803       else if (Vdeb.IsSame(VR)) Vsuiv=VF;
1804       else {
1805         // par defaut on prend l'origine sur cette arete
1806         if (VR.IsSame(TopoDS::Vertex(anExp.CurrentVertex()))) {
1807           Vdeb = VR;
1808           Vsuiv = VF;
1809         }
1810         else {
1811           Vdeb = VF;
1812           Vsuiv = VR;
1813         }
1814       }
1815       Pdeb=BRep_Tool::Pnt(Vdeb);
1816       Psuiv=BRep_Tool::Pnt(Vsuiv);
1817       Standard_Real U1 = BRep_Tool::Parameter(Vdeb,Ecur);
1818       Standard_Real U2 = BRep_Tool::Parameter(Vsuiv,Ecur);
1819       BRepAdaptor_Curve Curve(Ecur);
1820       PPs = Curve.Value(0.25*(U1+3*U2));
1821       myWork(ideb) = wire;
1822     }
1823     else {
1824       // on ramene Pdeb, Psuiv et PPs dans le plan courant
1825       gp_Pnt Pnew,Pnext,PPn; 
1826       Transform(Standard_True,Pdeb,Pos->Value(i-1),Axe->Value(i-1), 
1827                               Pos->Value(i),Axe->Value(i),Pnew);
1828       Transform(Standard_True,Psuiv,Pos->Value(i-1),Axe->Value(i-1), 
1829                               Pos->Value(i),Axe->Value(i),Pnext);
1830       Transform(Standard_True,PPs,Pos->Value(i-1),Axe->Value(i-1), 
1831                               Pos->Value(i),Axe->Value(i),PPn);
1832       
1833       Standard_Real distmini,dist;
1834       Standard_Integer rang=0,rangdeb=0;
1835       TopoDS_Vertex Vmini;
1836       gp_Pnt Pmini,P1,P2;
1837       SeqOfVertices(wire,SeqV);
1838       if (SeqV.Length()>NbMaxV) 
1839         throw Standard_NoSuchObject("BRepFill::ComputeOrigin failed");
1840       if (!polar) {
1841         // choix du vertex le plus proche comme origine
1842         distmini = Precision::Infinite();
1843         for (Standard_Integer ii=1;ii<=SeqV.Length();ii++) {
1844           P1 = BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(ii)));
1845           dist = P1.Distance(Pnew);
1846           if (dist<distmini) {
1847             distmini = dist;
1848             Vmini = TopoDS::Vertex(SeqV.Value(ii));
1849           }
1850         }
1851         if (!Vmini.IsNull()) Pmini = BRep_Tool::Pnt(Vmini);
1852       }
1853       else {
1854         
1855         // recherche du vertex correspondant a la projection conique
1856         Standard_Real angmin, angV, eta = Precision::Angular();
1857         TopoDS_Vertex Vopti;
1858         angmin = M_PI/2;
1859         distmini = Precision::Infinite();
1860         gp_Dir dir0(gp_Vec(Pnew,P.Location()));
1861         for (Standard_Integer ii=1;ii<=SeqV.Length();ii++) {
1862           P1 = BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(ii)));
1863           dist = Pnew.Distance(P1);
1864           if (dist<Precision::Confusion()) {
1865             angV = 0.0;
1866           }
1867           else {
1868             gp_Dir dir1(gp_Vec(Pnew,P1));
1869             angV = dir1.Angle(dir0);
1870           }
1871           if (angV>M_PI/2) angV = M_PI - angV;
1872           if (angmin>angV+eta) {
1873             distmini = dist;
1874             angmin = angV;
1875             Vopti = TopoDS::Vertex(SeqV.Value(ii));
1876           }
1877           else if (Abs(angmin-angV)<eta) {
1878             if (dist<distmini) {
1879               distmini = dist;
1880               angmin = angV;
1881               Vopti = TopoDS::Vertex(SeqV.Value(ii));
1882             }
1883           }
1884         }
1885         gp_Pnt Popti;
1886         if (!Vopti.IsNull()) Popti = BRep_Tool::Pnt(Vopti);
1887         Vmini = Vopti;
1888         
1889       }
1890
1891       distmini = Precision::Infinite();
1892       for (anExp.Init(wire); anExp.More(); anExp.Next()) {
1893         TopoDS_Edge Ecur = anExp.Current();
1894         TopoDS_Vertex Vcur = anExp.CurrentVertex();
1895         TopExp::Vertices(Ecur,VF,VR);
1896         if (VF.IsSame(Vmini)) {
1897           P1 = BRep_Tool::Pnt(VR);
1898           dist = P1.Distance(Pnext);
1899           if (dist<=distmini) {
1900             distmini = dist;
1901             Vsuiv = VR;
1902           }
1903         }
1904         if (VR.IsSame(Vmini)) {
1905           P1 = BRep_Tool::Pnt(VF);
1906           dist = P1.Distance(Pnext);
1907           if (dist<distmini) {
1908             distmini = dist;
1909             Vsuiv = VF;
1910           }
1911         }
1912       }
1913       
1914       // choix du sens de parcours en fonction de Pnext
1915       Standard_Boolean parcours = Standard_False;
1916       if (i==myWork.Length() && myDegen2) {
1917         // derniere section ponctuelle
1918         rangdeb = 1;
1919         parcours = Standard_True;
1920       }
1921       else {
1922         // cas general
1923         gp_Pnt Pbout = Pnext;
1924         TopoDS_Edge E1,E2;
1925         TopoDS_Vertex V1,V2;
1926         EdgesFromVertex(wire,Vmini,E1,E2);
1927         
1928         TopExp::Vertices(E1,V1,V2,Standard_True);
1929 #ifndef OCCT_DEBUG
1930         Standard_Real U1=0, U2=0;
1931 #else
1932         Standard_Real U1, U2;
1933 #endif
1934         if (Vmini.IsSame(V1)) { 
1935           P1 = BRep_Tool::Pnt(V2);
1936           U1 = 0.25*(BRep_Tool::Parameter(V1,E1)+3*BRep_Tool::Parameter(V2,E1));
1937         }
1938         if (Vmini.IsSame(V2)) {
1939           P1 = BRep_Tool::Pnt(V1);
1940           U1 = 0.25*(3*BRep_Tool::Parameter(V1,E1)+BRep_Tool::Parameter(V2,E1));
1941         }
1942         
1943         TopExp::Vertices(E2,V1,V2,Standard_True);
1944         if (Vmini.IsSame(V1)) { 
1945           P2 = BRep_Tool::Pnt(V2);
1946           U2 = 0.25*(BRep_Tool::Parameter(V1,E2)+3*BRep_Tool::Parameter(V2,E2));
1947         }
1948         if (Vmini.IsSame(V2)) {
1949           P2 = BRep_Tool::Pnt(V1);
1950           U2 = 0.25*(3*BRep_Tool::Parameter(V1,E2)+BRep_Tool::Parameter(V2,E2));
1951         }
1952         
1953         if (Abs(Pbout.Distance(P1)-Pbout.Distance(P2))<Precision::Confusion()) {
1954           // cas limite ; on se decale un peu
1955           Pbout = PPn;
1956           BRepAdaptor_Curve Curve1(E1);
1957           P1 = Curve1.Value(U1);
1958           BRepAdaptor_Curve Curve2(E2);
1959           P2 = Curve2.Value(U2);
1960         }
1961         
1962         // calcul de rangdeb
1963         rangdeb = 0;
1964         if (Pbout.Distance(P1)<Pbout.Distance(P2)){
1965           // P1 est plus proche; parcours = False
1966           parcours = Standard_False;
1967           rang = 0;
1968           for (anExp.Init(wire); anExp.More(); anExp.Next()) {
1969             rang++;
1970             TopoDS_Edge Ecur = anExp.Current();
1971             if (E1.IsSame(Ecur)) {
1972               rangdeb = rang;
1973             }
1974           }
1975           BRepAdaptor_Curve Curve(E1);
1976           PPs = Curve.Value(U1);
1977         }
1978         else {
1979           // P2 est plus proche; parcours = True
1980           parcours = Standard_True;
1981           rang = 0;
1982           for (anExp.Init(wire); anExp.More(); anExp.Next()) {
1983             rang++;
1984             TopoDS_Edge Ecur = anExp.Current();
1985             if (E2.IsSame(Ecur)) {
1986               rangdeb = rang;
1987             }
1988           }
1989           BRepAdaptor_Curve Curve(E2);
1990           PPs = Curve.Value(U2);
1991         }
1992       }
1993
1994       // reconstruction du wire a partir de rangdeb
1995       TopTools_SequenceOfShape SeqEdges;
1996       SeqEdges.Clear();
1997       for (anExp.Init(TopoDS::Wire(wire)); anExp.More(); anExp.Next()) {
1998         SeqEdges.Append(anExp.Current());
1999       }
2000       if (parcours) {
2001         for (rang=rangdeb;rang<=nbEdges;rang++) {
2002           BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang)));
2003         }
2004         for (rang=1;rang<rangdeb;rang++) {
2005           BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang)));
2006         }
2007       }
2008       else {
2009         for (rang=rangdeb;rang>=1;rang--) {
2010           TopoDS_Shape aLocalShape = SeqEdges.Value(rang).Reversed();
2011           BW.Add(newwire,TopoDS::Edge(aLocalShape));
2012 //        BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang).Reversed()));
2013         }
2014         for (rang=nbEdges;rang>rangdeb;rang--) {
2015           TopoDS_Shape aLocalShape = SeqEdges.Value(rang).Reversed();
2016           BW.Add(newwire,TopoDS::Edge(aLocalShape));
2017 //        BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang).Reversed()));
2018         }
2019       }
2020       
2021       myWork(i) = newwire.Oriented(TopAbs_FORWARD);
2022       
2023       // on passe au wire suivant
2024       if (!Vmini.IsNull()) Pdeb=BRep_Tool::Pnt(Vmini);
2025       if (!Vsuiv.IsNull()) Psuiv=BRep_Tool::Pnt(Vsuiv);
2026     }
2027   }
2028 #endif
2029   
2030   // blocking sections ?
2031   if (vClosed) myWork(myWork.Length()) = myWork(1);
2032 }
2033
2034 //=======================================================================
2035 //function : SearchOrigin
2036 //purpose  : 
2037 //=======================================================================
2038
2039 void BRepFill_CompatibleWires::SearchOrigin()
2040 {
2041   // reorganize the open wires respecting orientation and origin
2042   
2043   gp_Pln P0,P;  
2044
2045   TopoDS_Vertex Vdeb, Vfin;
2046   gp_Pnt Pdeb,  Pfin;//,Psuiv;
2047
2048   BRepTools_WireExplorer anExp;
2049
2050   Standard_Boolean allOpen = Standard_True;
2051   Standard_Integer ideb=1, ifin=myWork.Length();
2052   if (myDegen1) ideb++;
2053   if (myDegen2) ifin--;
2054   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
2055                                 && (myWork(ideb).IsSame(myWork(ifin)));
2056   
2057 //  for (Standard_Integer i=ideb; i<=ifin; i++) {
2058   Standard_Integer i;
2059   for  (i=ideb; i<=ifin; i++) {
2060     allOpen = (allOpen && !myWork(i).Closed());
2061   }
2062   if (!allOpen)
2063     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SearchOrigin : the wires must be open");
2064
2065   // init
2066
2067   TopoDS_Wire wire1 = TopoDS::Wire(myWork(ideb));
2068   wire1.Orientation(TopAbs_FORWARD);
2069   TopExp::Vertices(wire1,Vdeb,Vfin);
2070   Pdeb = BRep_Tool::Pnt(Vdeb);
2071   Pfin = BRep_Tool::Pnt(Vfin);
2072   Standard_Boolean isline0 = (!PlaneOfWire(wire1,P0)), isline;
2073   myWork(ideb) = wire1;
2074   //OCC86
2075   anExp.Init(wire1);
2076   TopoDS_Edge E0 = anExp.Current(), E;
2077
2078   for ( i=ideb+1; i<=ifin; i++) {
2079
2080     TopoDS_Wire wire = TopoDS::Wire(myWork(i));
2081     wire.Orientation(TopAbs_FORWARD);
2082
2083     TopTools_SequenceOfShape SeqEdges;
2084     SeqEdges.Clear();
2085     Standard_Integer nbEdges=0;
2086     //OCC86  for(anExp.Init(wire); anExp.More(); anExp.Next()) {
2087     for(anExp.Init(wire), E = anExp.Current(); anExp.More(); anExp.Next()) {
2088       SeqEdges.Append(anExp.Current());
2089       nbEdges++;
2090     }
2091     TopExp::Vertices(wire,Vdeb,Vfin);
2092     isline = (!PlaneOfWire(wire,P));
2093
2094     TopoDS_Vertex Vmini;
2095     TopoDS_Wire newwire;
2096     BRep_Builder BW;
2097     BW.MakeWire(newwire);
2098     Standard_Boolean parcours = Standard_True;
2099
2100     if (isline0 || isline) {
2101       
2102       // particular case of straight segments 
2103       gp_Pnt P1 = BRep_Tool::Pnt(Vdeb),
2104              P2 = BRep_Tool::Pnt(Vfin);
2105       Standard_Real dist1, dist2;
2106       dist1 = Pdeb.Distance(P1)+Pfin.Distance(P2);
2107       dist2 = Pdeb.Distance(P2)+Pfin.Distance(P1);
2108       parcours = (dist2>=dist1);
2109     }
2110     
2111     else {
2112       //OCC86
2113       gp_Pnt P1 = BRep_Tool::Pnt(Vdeb), P1o = Pdeb,
2114              P2 = BRep_Tool::Pnt(Vfin), P2o = Pfin;
2115 /*    // return Pdeb in the current plane
2116       gp_Pnt Pnew = Pdeb.Translated (P0.Location(),P.Location());
2117       gp_Ax1 A0 = P0.Axis();
2118       gp_Ax1 A1 = P.Axis();
2119       
2120       if (!A0.IsParallel(A1,1.e-4)) {
2121         gp_Vec vec1(A0.Direction()), vec2(A1.Direction()), 
2122         norm = vec1 ^ vec2;
2123         gp_Ax1 Norm(P.Location(),norm);
2124         Standard_Real ang = vec1.AngleWithRef(vec2,norm);
2125         if (ang > M_PI/2.0)
2126           ang = M_PI - ang;
2127         if (ang < -M_PI/2.0)
2128           ang = -M_PI - ang;
2129         if (Abs(ang-M_PI/2.0)<Precision::Angular()) {
2130           // cas d'ambiguite
2131           gp_Vec Vtrans(P0.Location(),P.Location()),Vsign;
2132           Standard_Real alpha,beta,sign=1;
2133           Vsign.SetLinearForm(Vtrans.Dot(vec1),vec2,-Vtrans.Dot(vec2),vec1);
2134           alpha = Vsign.Dot(vec1);
2135           beta = Vsign.Dot(vec2);
2136           Standard_Boolean pasnul = (Abs(alpha)>1.e-4 && Abs(beta)>1.e-4);
2137           if ( alpha*beta>0.0 && pasnul ) sign=-1;
2138           ang *= sign;
2139         }
2140         Pnew = Pnew.Rotated (Norm,ang);
2141       }
2142       // choix entre Vdeb et Vfin
2143       Standard_Real dist = Pnew.Distance(P1);
2144       parcours = (dist<Pnew.Distance(P2));
2145 */      
2146       if(P1.IsEqual(P2,Precision::Confusion()) || P1o.IsEqual(P2o,Precision::Confusion())){
2147         BRepAdaptor_Curve Curve0(E0), Curve(E);
2148         Curve0.D0(Curve0.FirstParameter() + Precision::Confusion(), P2o);
2149         Curve.D0(Curve.FirstParameter() + Precision::Confusion(), P2);
2150       };
2151       gp_Vec VDebFin0(P1o,P2o), VDebFin(P1,P2);
2152       Standard_Real AStraight = VDebFin0.Angle(VDebFin);
2153       parcours = (AStraight < M_PI/2.0? Standard_True: Standard_False);
2154     }
2155     
2156     // reconstruction of the wire
2157     Standard_Integer rang;
2158     if (parcours) {
2159       for (rang=1;rang<=nbEdges;rang++) {
2160         TopoDS_Shape alocalshape = SeqEdges.Value(rang);
2161         BW.Add(newwire,TopoDS::Edge(alocalshape));
2162 //      BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang)));
2163       }
2164     }
2165     else {
2166       for (rang=nbEdges;rang>=1;rang--) {
2167         TopoDS_Shape alocalshape = SeqEdges.Value(rang).Reversed();
2168         BW.Add(newwire,TopoDS::Edge(alocalshape));
2169 //      BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang).Reversed()));
2170       }
2171     }
2172
2173     // orientation of the wire
2174     newwire.Oriented(TopAbs_FORWARD);
2175     myWork(i) = newwire;
2176
2177     // passe to the next wire 
2178     if (parcours) {
2179       Pdeb = BRep_Tool::Pnt(Vdeb);
2180       Pfin = BRep_Tool::Pnt(Vfin);
2181     }
2182     else {
2183       Pfin = BRep_Tool::Pnt(Vdeb);
2184       Pdeb = BRep_Tool::Pnt(Vfin);
2185     }
2186     P0 = P;
2187     isline0 = isline;
2188     //OCC86
2189     E0 = E;
2190   }
2191   
2192   // blocking sections ?
2193   if (vClosed) myWork(myWork.Length()) = myWork(1);
2194 }