0026150: BRepOffsetAPI_ThruSections doesn't implement history method Generated().
[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 //function : IsDegeneratedFirstSection
750 //purpose  : 
751 //==========================================================================
752 Standard_Boolean BRepFill_CompatibleWires::IsDegeneratedFirstSection() const
753 {
754   return myDegen1;
755 }
756
757 //=========================================================================
758 //function : IsDegeneratedLastSection
759 //purpose  : 
760 //=========================================================================
761 Standard_Boolean BRepFill_CompatibleWires::IsDegeneratedLastSection() const
762 {
763   return myDegen2;
764 }
765
766
767 //=======================================================================
768 //function : Perform
769 //purpose  : 
770 //=======================================================================
771
772 void BRepFill_CompatibleWires::Perform (const Standard_Boolean WithRotation)
773 {
774   // compute origin and orientation on wires to avoid twisted results
775   // and update wires to have same number of edges
776
777   // determination of report:
778   // if the number of elements is the same and if the wires have discontinuities
779   // by tangency, the report is not carried out by curvilinear abscissa
780   Standard_Integer nbSects = myWork.Length(), i;
781   BRepTools_WireExplorer anExp;
782   Standard_Integer nbmax=0, nbmin=0;
783   TColStd_Array1OfInteger nbEdges(1,nbSects);
784   Standard_Boolean report;
785   GeomAbs_Shape contS=GeomAbs_CN;
786   GeomAbs_Shape cont;
787   for (i=1; i<=nbSects; i++) {
788     TopoDS_Shape aLocalShape = myWork(i).Oriented(TopAbs_FORWARD);
789     myWork(i) = TopoDS::Wire(aLocalShape);
790 //    myWork(i) = TopoDS::Wire(myWork(i).Oriented(TopAbs_FORWARD));
791     TopoDS_Wire W = TopoDS::Wire(myWork(i));
792     WireContinuity(W,cont);
793     if (cont<contS) contS=cont;
794     nbEdges(i) = 0;
795     for(anExp.Init(W); anExp.More(); anExp.Next() ) nbEdges(i)++;
796     if (i==1) nbmin = nbEdges(i);
797     if (nbmax<nbEdges(i)) nbmax = nbEdges(i);
798     if (nbmin>nbEdges(i)) nbmin = nbEdges(i);
799   } 
800   // if the number of elements is not the same or if all wires are at least
801   // C1, the report is carried out by curvilinear abscissa of cuts, otherwise 
802   // a report vertex / Vertex is done
803   report = (nbmax != nbmin || contS >= GeomAbs_C1 );
804   
805   // initialization of the map
806   Standard_Integer nbE = 0;
807   TopTools_ListOfShape Empty;
808   for (i=1; i<=nbSects; i++) {
809     TopoDS_Wire W = TopoDS::Wire(myWork(i));
810     for(anExp.Init(W); anExp.More(); anExp.Next() ) {
811       TopoDS_Edge E = TopoDS::Edge(anExp.Current());
812       myMap.Bind(E,Empty);
813       myMap(E).Append(E);
814       nbE++;
815     }
816   } 
817   
818   // open/closed sections
819   // initialisation of myDegen1, myDegen2
820   Standard_Integer ideb=1, ifin=myWork.Length();
821   // check if the first wire is punctual
822   myDegen1 = Standard_True;
823   for(anExp.Init(TopoDS::Wire(myWork(ideb))); anExp.More(); anExp.Next()) {
824     myDegen1 = myDegen1 && (BRep_Tool::Degenerated(anExp.Current()));
825   }
826   if (myDegen1) ideb++;
827   // check if the last wire is punctual
828   myDegen2 = Standard_True;
829   for(anExp.Init(TopoDS::Wire(myWork(ifin))); anExp.More(); anExp.Next()) {
830     myDegen2 = myDegen2 && (BRep_Tool::Degenerated(anExp.Current()));
831   }
832   if (myDegen2) ifin--;
833   
834   Standard_Boolean wClosed, allClosed = Standard_True, allOpen = Standard_True;
835   for (i=ideb; i<=ifin; i++) {
836     wClosed = myWork(i).Closed();
837     if (!wClosed) {
838       // check if the vertices are the same.
839       TopoDS_Vertex V1, V2;
840       TopExp::Vertices(TopoDS::Wire(myWork(i)),V1,V2);
841       if ( V1.IsSame(V2)) wClosed = Standard_True;
842     }
843     allClosed = (allClosed && wClosed);
844     allOpen = (allOpen && !wClosed);
845   }
846   
847   if (allClosed) {
848     // All sections are closed 
849     if (report) {
850       // same number of elements  
851       SameNumberByPolarMethod(WithRotation);
852     }
853     else {
854       // origin
855       ComputeOrigin(Standard_False);
856     }
857     myIsDone = Standard_True;
858   }
859   else if (allOpen) {
860     // All sections are open
861     // origin
862     SearchOrigin();
863     // same number of elements
864     if (report) {
865       SameNumberByACR(report);
866     }
867     myIsDone = Standard_True;
868   }
869   else {
870     // There are open and closed sections :
871     // not processed
872     throw Standard_DomainError("Sections must be all closed or all open");
873   }
874   
875 }
876
877
878
879
880 //=======================================================================
881 //function : Generated
882 //purpose  : 
883 //=======================================================================
884
885 const TopTools_DataMapOfShapeListOfShape&  BRepFill_CompatibleWires::Generated() const 
886 {
887   return myMap;
888 }
889
890
891 //=======================================================================
892 //function : SameNumberByPolarMethod
893 //purpose  : 
894 //=======================================================================
895
896 void BRepFill_CompatibleWires::
897               SameNumberByPolarMethod(const Standard_Boolean WithRotation)
898 {
899
900   // initialisation 
901   Standard_Integer NbSects=myWork.Length();
902   BRepTools_WireExplorer anExp;
903   TopTools_DataMapOfShapeSequenceOfShape EdgeNewEdges;
904
905   Standard_Boolean allClosed = Standard_True;
906   Standard_Integer i,ii,ideb=1,ifin=NbSects;
907
908   for (i=1; i<=NbSects; i++) {
909     Handle(BRepCheck_Wire) Checker = new BRepCheck_Wire(TopoDS::Wire(myWork(i)));
910     allClosed = (allClosed && (Checker->Closed() == BRepCheck_NoError));
911     //allClosed = (allClosed && myWork(i).Closed());
912   }
913   if (!allClosed)
914     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SameNumberByPolarMethod : the wires must be closed");
915   
916   // sections ponctuelles, sections bouclantes ?
917   if (myDegen1) ideb++;
918   if (myDegen2) ifin--;
919   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
920                                 && (myWork(ideb).IsSame(myWork(ifin)));
921
922   //Removing degenerated edges
923   for (i = ideb; i <= ifin; i++)
924   {
925     Standard_Boolean hasDegEdge = Standard_False;
926     TopoDS_Iterator anItw(myWork(i));
927     for (; anItw.More(); anItw.Next())
928     {
929       const TopoDS_Edge& anEdge = TopoDS::Edge(anItw.Value());
930       if (BRep_Tool::Degenerated(anEdge))
931       {
932         hasDegEdge = Standard_True;
933         break;
934       }
935     }
936     if (hasDegEdge)
937     {
938       TopoDS_Wire aNewWire;
939       BRep_Builder aBBuilder;
940       aBBuilder.MakeWire(aNewWire);
941       for (anItw.Initialize(myWork(i)); anItw.More(); anItw.Next())
942       {
943         const TopoDS_Edge& anEdge = TopoDS::Edge(anItw.Value());
944         if (!BRep_Tool::Degenerated(anEdge))
945           aBBuilder.Add(aNewWire, anEdge);
946       }
947       myWork(i) = aNewWire;
948     }
949   }
950   
951   // Nombre max de decoupes possibles
952   Standard_Integer NbMaxV = 0;
953   for (i=1; i<=NbSects; i++) {
954     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
955       NbMaxV++;
956     }
957   }
958   
959   // construction of tables of planes of wires 
960   gp_Pln P;
961   Handle(TColgp_HArray1OfPnt) Pos
962     = new (TColgp_HArray1OfPnt) (1,NbSects);
963   Handle(TColgp_HArray1OfVec) Axe
964     = new (TColgp_HArray1OfVec) (1,NbSects);
965   for (i=ideb;i<=ifin;i++) {
966     if (PlaneOfWire(TopoDS::Wire(myWork(i)),P)) {
967       Pos->SetValue(i,P.Location());
968       Axe->SetValue(i,gp_Vec(P.Axis().Direction()));
969     }
970   }
971   TopTools_SequenceOfShape SeqV;
972   if (myDegen1) {
973     SeqOfVertices(TopoDS::Wire(myWork(1)),SeqV);
974     Pos->SetValue(1,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
975     Axe->SetValue(1,Axe->Value(ideb));
976   }
977   if (myDegen2) {
978     SeqOfVertices(TopoDS::Wire(myWork(NbSects)),SeqV);
979     Pos->SetValue(NbSects,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
980     Axe->SetValue(NbSects,Axe->Value(ifin));
981   }
982   
983   // construction of RMap, map of reports of wire i to wire i-1
984   TopTools_DataMapOfShapeListOfShape RMap;
985   RMap.Clear();
986   
987   // loop on i
988   for (i=ifin; i>ideb; i--) {
989     
990     const TopoDS_Wire& wire1 = TopoDS::Wire(myWork(i));
991     
992     // sequence of vertices of the first wire
993     SeqOfVertices(wire1,SeqV);
994     if (SeqV.Length()>NbMaxV) 
995       throw Standard_NoSuchObject("BRepFill::SameNumberByPolarMethod failed");
996     
997     // loop on vertices of wire1
998     for (ii=1;ii<=SeqV.Length();ii++) {
999       
1000       TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
1001       
1002       // init of RMap for Vi
1003       TopTools_ListOfShape Init;
1004       Init.Clear();
1005       RMap.Bind(Vi,Init);
1006       
1007       // it is required to find intersection Vi - wire2
1008       gp_Pnt Pi = BRep_Tool::Pnt(Vi);
1009       
1010       // return Pi in the current plane
1011       gp_Pnt Pnew;
1012       Transform(WithRotation,Pi,
1013                 Pos->Value(i),Axe->Value(i), 
1014                 Pos->Value(i-1),Axe->Value(i-1),Pnew);
1015       
1016       // calculate the intersection
1017       TopoDS_Shape Support;
1018       Standard_Boolean NewVertex;
1019       TopoDS_Vertex Vsol;
1020       TopoDS_Wire newwire;
1021       if (Pnew.Distance(Pos->Value(i-1))>Precision::Confusion()) {
1022         Standard_Real percent = myPercent;
1023         NewVertex = EdgeIntersectOnWire(Pos->Value(i-1),Pnew,percent,
1024                                         RMap,TopoDS::Wire(myWork(i-1)),
1025                                         Vsol,newwire,EdgeNewEdges);
1026         if (NewVertex) myWork(i-1) = newwire;
1027         RMap(Vi).Append(Vsol);
1028       }
1029       
1030     } // loop on  ii
1031   }   // loop on  i
1032   
1033   // initialisation of MapVLV, map of correspondences vertex - list of vertices
1034   TopTools_DataMapOfShapeListOfShape MapVLV;
1035   SeqOfVertices(TopoDS::Wire(myWork(ideb)),SeqV);
1036   Standard_Integer SizeMap = SeqV.Length();
1037   MapVLV.Clear();
1038   for (ii=1;ii<=SizeMap;ii++) {
1039     TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
1040     TopTools_ListOfShape Init;
1041     Init.Clear();
1042     Init.Append(Vi);
1043     MapVLV.Bind(Vi,Init);
1044     Standard_Integer NbV = 1;
1045     TopoDS_Vertex V0,V1;
1046     V0 = Vi;
1047     Standard_Boolean tantque = SearchRoot(V0,RMap,V1);
1048     while (tantque) {
1049       MapVLV(Vi).Append(V1);
1050       NbV++;
1051       // test on NbV required for looping sections 
1052       if (V1.IsSame(Vi) || NbV >= myWork.Length()) {
1053         tantque = Standard_False;
1054       }
1055       else {
1056         V0 = V1;
1057         tantque = SearchRoot(V0,RMap,V1);
1058       }
1059     }
1060   }
1061   
1062   // loop on i
1063   for (i=ideb; i<ifin; i++) {
1064     
1065     const TopoDS_Wire& wire1 = TopoDS::Wire(myWork(i));
1066     
1067     // sequence of vertices of the first wire
1068     SeqOfVertices(wire1,SeqV);
1069     if ( SeqV.Length()>NbMaxV || SeqV.Length()>SizeMap ) 
1070       throw Standard_NoSuchObject("BRepFill::SameNumberByPolarMethod failed");
1071     
1072
1073     // next wire 
1074     const TopoDS_Wire& wire2 = TopoDS::Wire(myWork(i+1));
1075     
1076     // loop on vertices of wire1
1077     for (ii=1;ii<=SeqV.Length();ii++) {
1078       
1079       TopoDS_Vertex Vi = TopoDS::Vertex(SeqV.Value(ii));
1080       TopoDS_Vertex VRoot;
1081       VRoot.Nullify();
1082       Standard_Boolean intersect = Standard_True;
1083       if (SearchRoot(Vi,MapVLV,VRoot)) {
1084         const TopTools_ListOfShape& LVi = MapVLV(VRoot);
1085         TopoDS_Vertex VonW;
1086         VonW.Nullify();
1087         intersect = (!SearchVertex(LVi,wire2,VonW));
1088       }
1089       
1090       if (intersect) {
1091         // it is necessary to find intersection Vi - wire2
1092         gp_Pnt Pi = BRep_Tool::Pnt(Vi);
1093         
1094         // return Pi in the current plane
1095         gp_Pnt Pnew;
1096         Transform(WithRotation,Pi,
1097                   Pos->Value(i),Axe->Value(i), 
1098                   Pos->Value(i+1),Axe->Value(i+1),Pnew);
1099         
1100         // calculate the intersection
1101         TopoDS_Shape Support;
1102         Standard_Boolean NewVertex;
1103         TopoDS_Vertex Vsol;
1104         TopoDS_Wire newwire;
1105         if (Pnew.Distance(Pos->Value(i+1))>Precision::Confusion()) {
1106           Standard_Real percent = myPercent;
1107           NewVertex = EdgeIntersectOnWire(Pos->Value(i+1),Pnew,percent,
1108                                           MapVLV,TopoDS::Wire(myWork(i+1)),
1109                                           Vsol,newwire,EdgeNewEdges);
1110           MapVLV(VRoot).Append(Vsol);
1111           if (NewVertex) myWork(i+1) = newwire;
1112         }
1113         
1114       }
1115     } // loop on ii
1116   }   // loop on i
1117   
1118   // regularize wires following MapVLV
1119   TopoDS_Wire wire = TopoDS::Wire(myWork(ideb));
1120
1121   // except for the last if the sections loop 
1122   Standard_Integer ibout = ifin;
1123   if (vClosed) ibout--;
1124
1125   for ( i=ideb+1; i<=ibout; i++) {
1126
1127     BRepLib_MakeWire MW;
1128
1129     anExp.Init(wire);
1130     TopoDS_Edge ECur = anExp.Current();
1131     TopoDS_Vertex VF,VL;
1132     TopExp::Vertices(ECur,VF,VL,Standard_True);
1133     Standard_Real U1 = BRep_Tool::Parameter(VF,ECur);
1134     Standard_Real U2 = BRep_Tool::Parameter(VL,ECur);
1135     BRepAdaptor_Curve Curve(ECur);
1136     gp_Pnt PPs = Curve.Value(0.1*(U1+9*U2));
1137     TopTools_ListIteratorOfListOfShape itF(MapVLV(VF)),itL(MapVLV(VL));
1138     Standard_Integer rang = ideb;
1139     while (rang < i) {
1140       itF.Next();
1141       itL.Next();
1142       rang++;
1143     }
1144     TopoDS_Vertex V1 = TopoDS::Vertex(itF.Value()), V2 = TopoDS::Vertex(itL.Value());
1145     TopoDS_Edge Esol;
1146     Standard_Real scalmax=0.;
1147     TopoDS_Iterator itW( myWork(i) );
1148     
1149     for(; itW.More(); itW.Next())
1150       {
1151         TopoDS_Edge E = TopoDS::Edge(itW.Value());
1152         TopoDS_Vertex VVF,VVL;
1153         TopExp::Vertices(E,VVF,VVL,Standard_True);
1154         
1155         // parse candidate edges
1156         Standard_Real scal1,scal2;
1157         if ( (V1.IsSame(VVF)&&V2.IsSame(VVL)) || (V2.IsSame(VVF)&&V1.IsSame(VVL)) ) {
1158           Standard_Real U1param = BRep_Tool::Parameter(VVF,E);
1159           Standard_Real U2param = BRep_Tool::Parameter(VVL,E);
1160           BRepAdaptor_Curve CurveE(E);
1161           gp_Pnt PP1 = CurveE.Value(0.1*(U1param +9* U2param));
1162           gp_Pnt PP2 = CurveE.Value(0.1*(9* U1param + U2param));
1163   
1164           for (rang=i;rang>ideb;rang--) {
1165             Transform(WithRotation, PP1,
1166                       Pos->Value(rang), Axe->Value(rang),
1167                       Pos->Value(rang-1), Axe->Value(rang-1), PP1);
1168             Transform(WithRotation, PP2,
1169                       Pos->Value(rang), Axe->Value(rang),
1170                       Pos->Value(rang-1), Axe->Value(rang-1), PP2);
1171           }
1172           gp_Vec Ns(Pos->Value(ideb),PPs);
1173           Ns = Ns.Normalized();
1174           gp_Vec N1(Pos->Value(ideb),PP1);
1175           N1 = N1.Normalized();
1176           gp_Vec N2(Pos->Value(ideb),PP2);
1177           N2 = N2.Normalized();
1178           scal1 = N1.Dot(Ns);
1179           if (scal1>scalmax) {
1180             scalmax = scal1;
1181             Esol = E;
1182           }
1183           scal2 = N2.Dot(Ns);
1184           if (scal2>scalmax) {
1185             scalmax = scal2;
1186             TopoDS_Shape aLocalShape = E.Reversed();
1187             Esol = TopoDS::Edge(aLocalShape);
1188           }
1189         }
1190       } //end of for(; itW.More(); itW.Next())
1191     if (Esol.IsNull())
1192       throw Standard_ConstructionError("BRepFill :: profiles are inconsistent");
1193     MW.Add(Esol);
1194
1195     TopTools_ListOfShape ConnectedEdges;
1196     BuildConnectedEdges( TopoDS::Wire(myWork(i)), Esol, V2, ConnectedEdges );
1197
1198     TopTools_ListIteratorOfListOfShape itCE(ConnectedEdges);
1199     for(; anExp.More(), itCE.More(); anExp.Next(), itCE.Next())
1200       {
1201         ECur = anExp.Current();
1202         TopExp::Vertices(ECur,VF,VL,Standard_True);
1203         U1 = BRep_Tool::Parameter(VF,ECur);
1204         U2 = BRep_Tool::Parameter(VL,ECur);
1205         Curve.Initialize(ECur);
1206         PPs = Curve.Value(0.1*(U1+9*U2));
1207         
1208         TopoDS_Edge E = TopoDS::Edge(itCE.Value());
1209         TopoDS_Vertex VVF,VVL;
1210         TopExp::Vertices(E,VVF,VVL,Standard_True);
1211
1212         // parse candidate edges
1213         Standard_Real scal1,scal2;
1214         U1 = BRep_Tool::Parameter(VVF,E);
1215         U2 = BRep_Tool::Parameter(VVL,E);
1216         Curve.Initialize(E);
1217         gp_Pnt PP1 = Curve.Value(0.1*(U1+9*U2));
1218         gp_Pnt PP2 = Curve.Value(0.1*(9*U1+U2));
1219         
1220         for (rang=i;rang>ideb;rang--) {
1221           Transform(WithRotation, PP1,
1222                     Pos->Value(rang), Axe->Value(rang),
1223                     Pos->Value(rang-1), Axe->Value(rang-1), PP1);
1224           Transform(WithRotation, PP2,
1225                     Pos->Value(rang), Axe->Value(rang),
1226                     Pos->Value(rang-1), Axe->Value(rang-1), PP2);
1227         }
1228         gp_Vec Ns(Pos->Value(ideb),PPs);
1229         Ns = Ns.Normalized();
1230         gp_Vec N1(Pos->Value(ideb),PP1);
1231         N1 = N1.Normalized();
1232         gp_Vec N2(Pos->Value(ideb),PP2);
1233         N2 = N2.Normalized();
1234         scal1 = N1.Dot(Ns);
1235         scal2 = N2.Dot(Ns);
1236         if (scal2>scal1)
1237           E.Reverse();
1238         MW.Add(E);
1239       }
1240     myWork(i) = MW.Wire();
1241   }
1242   
1243   // blocking sections?
1244   if (vClosed)
1245   {
1246     TopoDS_Iterator iter1(myWork(myWork.Length())), iter2(myWork(1));
1247     for (; iter1.More(); iter1.Next(), iter2.Next())
1248     {
1249       const TopoDS_Shape& anEdge = iter1.Value();
1250       const TopoDS_Shape& aNewEdge = iter2.Value();
1251       if (!anEdge.IsSame(aNewEdge))
1252       {
1253         TopTools_SequenceOfShape aSeq;
1254         aSeq.Append(aNewEdge);
1255         EdgeNewEdges.Bind(anEdge, aSeq);
1256       }
1257     }
1258     myWork(myWork.Length()) = myWork(1);
1259   }
1260
1261   // check the number of edges for debug
1262   Standard_Integer nbmax=0, nbmin=0;
1263   for ( i=ideb; i<=ifin; i++) {
1264     Standard_Integer nbEdges=0;
1265     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1266       nbEdges++;
1267     }
1268     if (i==ideb) nbmin = nbEdges;
1269     if (nbmax<nbEdges) nbmax = nbEdges;
1270     if (nbmin>nbEdges) nbmin = nbEdges;
1271   }
1272   if (nbmin!=nbmax) {
1273     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SameNumberByPolarMethod failed");
1274   }
1275
1276   //Fill <myMap>
1277   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itmap(myMap);
1278   for (; itmap.More(); itmap.Next())
1279   {
1280     TopoDS_Shape anEdge = itmap.Key();
1281     TopTools_ListOfShape ListOfNewEdges;
1282
1283     //for each edge of <myMap> find all newest edges
1284     //in <EdgeNewEdges> recursively
1285     AddNewEdge(anEdge, EdgeNewEdges, ListOfNewEdges);
1286     
1287     myMap(anEdge) = ListOfNewEdges;
1288   }
1289 }
1290
1291 //=======================================================================
1292 //function : SameNumberByACR
1293 //purpose  : 
1294 //=======================================================================
1295
1296 void BRepFill_CompatibleWires::SameNumberByACR(const  Standard_Boolean  report)
1297 {
1298   // find the dimension
1299   Standard_Integer ideb=1, ifin=myWork.Length();
1300   BRepTools_WireExplorer anExp;
1301
1302   // point sections, blocking  sections?
1303   if (myDegen1) ideb++;
1304   if (myDegen2) ifin--;
1305   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
1306                                 && (myWork(ideb).IsSame(myWork(ifin)));
1307
1308   Standard_Integer nbSects = myWork.Length(), i;
1309   Standard_Integer nbmax=0, nbmin=0;
1310   TColStd_Array1OfInteger nbEdges(1,nbSects);
1311   for (i=1; i<=nbSects; i++) {
1312     nbEdges(i) = 0;
1313     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1314       nbEdges(i)++;
1315     }
1316     if (i==1) nbmin = nbEdges(i);
1317     if (nbmax<nbEdges(i)) nbmax = nbEdges(i);
1318     if (nbmin>nbEdges(i)) nbmin = nbEdges(i);
1319   }
1320
1321   if (nbmax>1) {
1322     // several edges
1323
1324     if (report || nbmin<nbmax) {
1325       // insertion of cuts
1326       Standard_Integer nbdec=(nbmax-1)*nbSects+1;
1327       TColStd_Array1OfReal dec(1,nbdec);
1328       dec.Init(0);
1329       dec(2)=1;
1330
1331       TColStd_Array1OfReal WireLen(1, nbSects);
1332       
1333       // calculate the table of cuts
1334       Standard_Integer j,k,l;
1335       for (i=1; i<=nbSects; i++) {
1336         // current wire
1337         const TopoDS_Wire& wire1 = TopoDS::Wire(myWork(i));
1338         Standard_Integer nbE = 0;
1339         for(anExp.Init(wire1); anExp.More(); anExp.Next()) {
1340           nbE++;
1341         }
1342         // length and ACR of the wire 
1343         TColStd_Array1OfReal ACR(0,nbE);
1344         ACR.Init(0);
1345         BRepFill::ComputeACR(wire1, ACR);
1346         WireLen(i) = ACR(0);
1347         // insertion of ACR of the wire in the table of cuts
1348         for (j=1; j<ACR.Length()-1; j++) {
1349           k=1;
1350           while (dec(k)<ACR(j)) {
1351             k++;
1352             if (k>nbdec) break;
1353           }
1354           if (dec(k-1)<ACR(j)&& ACR(j)<dec(k)) {
1355             for (l=nbdec-1;l>=k;l--) {
1356               dec(l+1)=dec(l);
1357             }
1358             dec(k) = ACR(j);
1359           }
1360         }
1361       }
1362       
1363       // table of cuts
1364       k=1;
1365       while (dec(k)<1) {
1366         k++;
1367         if (k>nbdec) break;
1368       }
1369       nbdec = k-1;
1370       TColStd_Array1OfReal dec2(1,nbdec);
1371       for (k=1;k<=nbdec;k++) {
1372         dec2(k) = dec(k);
1373       }
1374       
1375       //Check of cuts: are all the new edges long enouph or not
1376       TColStd_MapOfInteger CutsToRemove;
1377       for (k = 1; k <= nbdec; k++)
1378       {
1379         Standard_Real Knot1 = dec2(k);
1380         Standard_Real Knot2 = (k == nbdec)? 1. : dec2(k+1);
1381         Standard_Real AllLengthsNull = Standard_True;
1382         for (i = 1; i <= nbSects; i++)
1383         {
1384           Standard_Real EdgeLen = (Knot2 - Knot1) * WireLen(i);
1385           if (EdgeLen > Precision::Confusion())
1386           {
1387             AllLengthsNull = Standard_False;
1388             break;
1389           }
1390         }
1391         if (AllLengthsNull)
1392           CutsToRemove.Add(k);
1393       }
1394       Standard_Integer NewNbDec = nbdec - CutsToRemove.Extent();
1395       TColStd_Array1OfReal dec3(1, NewNbDec);
1396       i = 1;
1397       for (k = 1; k <= nbdec; k++)
1398         if (!CutsToRemove.Contains(k))
1399           dec3(i++) = dec2(k);
1400       ///////////////////
1401       
1402       // insertion of cuts in each wire
1403       for (i=1; i<=nbSects; i++) {
1404         const TopoDS_Wire& oldwire = TopoDS::Wire(myWork(i));
1405         Standard_Real tol = Precision::Confusion() / WireLen(i);
1406         TopoDS_Wire newwire = BRepFill::InsertACR(oldwire, dec3, tol);
1407         BRepTools_WireExplorer anExp1,anExp2;
1408         anExp1.Init(oldwire);
1409         anExp2.Init(newwire);
1410         for (;anExp1.More();anExp1.Next()) {
1411           const TopoDS_Edge& Ecur = anExp1.Current();
1412           if (!Ecur.IsSame(TopoDS::Edge(anExp2.Current()))) {
1413             TopTools_ListOfShape LE;
1414             LE.Clear();
1415             gp_Pnt P1,P2;
1416             const TopoDS_Vertex& V1 = anExp1.CurrentVertex();
1417             TopoDS_Vertex VF,VR;
1418             TopExp::Vertices(Ecur,VF,VR,Standard_True);
1419             if (V1.IsSame(VF)) P1 = BRep_Tool::Pnt(VR);
1420             if (V1.IsSame(VR)) P1 = BRep_Tool::Pnt(VF);
1421             TopoDS_Vertex V2 = anExp2.CurrentVertex();
1422             TopExp::Vertices(TopoDS::Edge(anExp2.Current()),
1423                              VF,VR,Standard_True);
1424             if (V2.IsSame(VF)) P2 = BRep_Tool::Pnt(VR);
1425             if (V2.IsSame(VR)) P2 = BRep_Tool::Pnt(VF);
1426             while (P1.Distance(P2)>1.e-3) {
1427               LE.Append(anExp2.Current());
1428               anExp2.Next();
1429               V2 = anExp2.CurrentVertex();
1430               TopExp::Vertices(TopoDS::Edge(anExp2.Current()),
1431                                VF,VR,Standard_True);
1432               if (V2.IsSame(VF)) P2 = BRep_Tool::Pnt(VR);
1433               if (V2.IsSame(VR)) P2 = BRep_Tool::Pnt(VF);
1434               if (P1.Distance(P2)<=1.e-3) {
1435                 LE.Append(anExp2.Current());
1436                 anExp2.Next();
1437               }
1438             }
1439
1440             TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itmap;
1441             //TopTools_ListIteratorOfListOfShape itlist;
1442             TopoDS_Edge Ancestor;
1443             Standard_Integer nbedge, nblist=0;
1444             Standard_Boolean found = Standard_False;
1445
1446             for (itmap.Initialize(myMap);itmap.More()&&(!found);itmap.Next()) {
1447               nblist++;
1448               TopTools_ListIteratorOfListOfShape itlist(itmap.Value());
1449               nbedge = 0;
1450               while (itlist.More()&&(!found)) {
1451                 nbedge++;
1452                 TopoDS_Edge ECur = TopoDS::Edge(itlist.Value());
1453                     
1454                 if (Ecur.IsSame(ECur)) {
1455                   Ancestor = TopoDS::Edge(itmap.Key());
1456                   found = Standard_True;
1457                   myMap(Ancestor).InsertBefore(LE,itlist);
1458                   myMap(Ancestor).Remove(itlist);
1459                 }
1460                 if (itlist.More()) itlist.Next();
1461               }
1462               
1463             }
1464
1465           }
1466           else {
1467             anExp2.Next();
1468           }
1469           
1470         }
1471         myWork(i) = newwire;
1472       }
1473       
1474     }
1475   }
1476   
1477   // blocking sections ?
1478   if (vClosed)
1479     myWork(myWork.Length()) = myWork(1);
1480
1481   // check the number of edges for debug
1482   nbmax = 0;
1483   for (i=ideb; i<=ifin; i++) {
1484     nbEdges(i) = 0;
1485     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1486       nbEdges(i)++;
1487     }
1488     if (i==ideb) nbmin = nbEdges(i);
1489     if (nbmax<nbEdges(i)) nbmax = nbEdges(i);
1490     if (nbmin>nbEdges(i)) nbmin = nbEdges(i);
1491   }
1492   if (nbmax!=nbmin) 
1493     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SameNumberByACR failed");
1494 }
1495
1496 //=======================================================================
1497 //function : ComputeOrigin
1498 //purpose  : 
1499 //=======================================================================
1500
1501 void BRepFill_CompatibleWires::ComputeOrigin(const  Standard_Boolean /*polar*/ )
1502 {
1503   // reorganize the wires respecting orientation and origin
1504   
1505   TopoDS_Vertex Vdeb, Vfin;
1506   gp_Pnt Pdeb, Psuiv, PPs;
1507
1508   BRepTools_WireExplorer anExp;
1509
1510   Standard_Boolean wClosed, allClosed = Standard_True;
1511
1512   Standard_Integer NbSects = myWork.Length();
1513   Standard_Integer i, ideb=1,ifin=NbSects;
1514
1515   // point sections, blocking sections 
1516   if (myDegen1) ideb++;
1517   if (myDegen2) ifin--;
1518   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
1519                                 && (myWork(ideb).IsSame(myWork(ifin)));
1520   
1521   
1522   for (i=ideb; i<=ifin; i++) {
1523     wClosed = myWork(i).Closed();
1524     if (!wClosed) {
1525       // check if the vertices are the same.
1526       TopoDS_Vertex V1, V2;
1527       TopExp::Vertices(TopoDS::Wire(myWork(i)),V1,V2);
1528       if ( V1.IsSame(V2)) wClosed = Standard_True;
1529     }
1530     allClosed = (allClosed && wClosed);
1531   }
1532 /*
1533   for (i=ideb; i<=ifin; i++) {
1534     allClosed = (allClosed && myWork(i).Closed());
1535   }
1536 */
1537   if (!allClosed) 
1538     throw Standard_NoSuchObject("BRepFill_CompatibleWires::ComputeOrigin : the wires must be closed");
1539
1540 /*  
1541   // Max number of possible cuts
1542   Standard_Integer NbMaxV = 0;
1543   for (i=1; i<=NbSects; i++) {
1544     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next()) {
1545       NbMaxV++;
1546     }
1547   }
1548   
1549   // construction of tables of planes of wires 
1550   gp_Pln P;  
1551   Handle(TColgp_HArray1OfPnt) Pos
1552     = new (TColgp_HArray1OfPnt) (1,NbSects);
1553   Handle(TColgp_HArray1OfVec) Axe
1554     = new (TColgp_HArray1OfVec) (1,NbSects);
1555   for (i=ideb;i<=ifin;i++) {
1556     if (PlaneOfWire(TopoDS::Wire(myWork(i)),P)) {
1557       Pos->SetValue(i,P.Location());
1558       Axe->SetValue(i,gp_Vec(P.Axis().Direction()));
1559     }
1560   }
1561   TopTools_SequenceOfShape SeqV;
1562   if (myDegen1) {
1563     SeqOfVertices(TopoDS::Wire(myWork(1)),SeqV);
1564     Pos->SetValue(1,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
1565     Axe->SetValue(1,Axe->Value(ideb));
1566   }
1567   if (myDegen2) {
1568     SeqOfVertices(TopoDS::Wire(myWork(NbSects)),SeqV);
1569     Pos->SetValue(NbSects,BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(1))));
1570     Axe->SetValue(NbSects,Axe->Value(ifin));
1571   }
1572 */
1573
1574   //Consider that all wires have same number of edges (polar==Standard_False)
1575   TopTools_SequenceOfShape PrevSeq;
1576   TopTools_SequenceOfShape PrevEseq;
1577   Standard_Integer theLength = 0;
1578   const TopoDS_Wire& wire = TopoDS::Wire( myWork(ideb) );
1579   for (anExp.Init(wire); anExp.More(); anExp.Next())
1580     {
1581       PrevSeq.Append(anExp.CurrentVertex());
1582       PrevEseq.Append(anExp.Current());
1583       theLength++;
1584     }
1585
1586   Standard_Integer nbs, NbSamples = 0;
1587   if (theLength <= 2)
1588     NbSamples = 4;
1589   gp_Pln FirstPlane;
1590   PlaneOfWire(TopoDS::Wire(myWork(ideb)), FirstPlane);
1591   gp_Pnt FirstBary = FirstPlane.Location();
1592   gp_Vec NormalOfFirstPlane = FirstPlane.Axis().Direction();
1593   for (i = ideb+1; i <= ifin; i++)
1594     {
1595       const TopoDS_Wire& aWire = TopoDS::Wire(myWork(i));
1596
1597       //Compute offset vector as current bary center projected on first plane
1598       //to first bary center
1599       gp_Pln CurPlane;
1600       PlaneOfWire(aWire, CurPlane);
1601       gp_Pnt CurBary = CurPlane.Location();
1602       gp_Vec aVec(FirstBary, CurBary);
1603       gp_Vec anOffsetProj = (aVec * NormalOfFirstPlane) * NormalOfFirstPlane;
1604       CurBary.Translate(-anOffsetProj); //projected current bary center
1605       gp_Vec Offset(CurBary, FirstBary);
1606       
1607       TopoDS_Wire newwire;
1608       BRep_Builder BB;
1609       BB.MakeWire(newwire);
1610       
1611       TopTools_SequenceOfShape SeqVertices, SeqEdges;
1612       for (anExp.Init(aWire); anExp.More(); anExp.Next())
1613         {
1614           SeqVertices.Append( anExp.CurrentVertex() );
1615           SeqEdges.Append( anExp.Current() );
1616         }
1617       
1618       Standard_Real MinSumDist = Precision::Infinite();
1619       Standard_Integer jmin = 1, j, k, n;
1620       Standard_Boolean forward = Standard_False;
1621       if (i == myWork.Length() && myDegen2)
1622         {
1623           // last point section
1624           jmin = 1;
1625           forward = Standard_True;
1626         }
1627       else
1628         for (j = 1; j <= theLength; j++)
1629           {
1630             //Forward
1631             Standard_Real SumDist = 0.;
1632             for (k = j, n = 1; k <= theLength; k++, n++)
1633               {
1634                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1635                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1636                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1637                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1638                 SumDist += Pprev.Distance(P);
1639                 if (NbSamples > 0)
1640                 {
1641                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1642                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k));
1643                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1644                   BRepAdaptor_Curve Ecurve(CurEdge);
1645                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1646                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1647                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1648                   {
1649                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1650                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1651                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1652                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1653                       (Ecurve.FirstParameter() + nbs*SampleOnCur) :
1654                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur);
1655                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1656                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1657                     SumDist += PonPrev.Distance(PonCur);
1658                   }
1659                 }
1660               }
1661             for (k = 1; k < j; k++, n++)
1662               {
1663                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1664                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1665                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1666                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1667                 SumDist += Pprev.Distance(P);
1668                 if (NbSamples > 0)
1669                 {
1670                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1671                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k));
1672                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1673                   BRepAdaptor_Curve Ecurve(CurEdge);
1674                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1675                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1676                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1677                   {
1678                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1679                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1680                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1681                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1682                       (Ecurve.FirstParameter() + nbs*SampleOnCur) :
1683                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur);
1684                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1685                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1686                     SumDist += PonPrev.Distance(PonCur);
1687                   }
1688                 }
1689               }
1690             if (SumDist < MinSumDist)
1691               {
1692                 MinSumDist = SumDist;
1693                 jmin = j;
1694                 forward = Standard_True;
1695               }
1696             
1697             //Backward
1698             SumDist = 0.;
1699             for (k = j, n = 1; k >= 1; k--, n++)
1700               {
1701                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1702                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1703                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1704                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1705                 SumDist += Pprev.Distance(P);
1706                 if (NbSamples > 0)
1707                 {
1708                   Standard_Integer k_cur = k-1;
1709                   if (k_cur == 0)
1710                     k_cur = theLength;
1711                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1712                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k_cur));
1713                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1714                   BRepAdaptor_Curve Ecurve(CurEdge);
1715                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1716                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1717                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1718                   {
1719                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1720                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1721                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1722                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1723                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur) :
1724                       (Ecurve.FirstParameter() + nbs*SampleOnCur);
1725                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1726                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1727                     SumDist += PonPrev.Distance(PonCur);
1728                   }
1729                 }
1730               }
1731             for (k = theLength; k > j; k--, n++)
1732               {
1733                 const TopoDS_Vertex& Vprev = TopoDS::Vertex( PrevSeq(n) );
1734                 gp_Pnt Pprev = BRep_Tool::Pnt(Vprev);
1735                 const TopoDS_Vertex& V = TopoDS::Vertex( SeqVertices(k) );
1736                 gp_Pnt P = BRep_Tool::Pnt(V).XYZ() + Offset.XYZ();
1737                 SumDist += Pprev.Distance(P);
1738                 if (NbSamples > 0)
1739                 {
1740                   const TopoDS_Edge& PrevEdge = TopoDS::Edge(PrevEseq(n));
1741                   const TopoDS_Edge& CurEdge = TopoDS::Edge(SeqEdges(k-1));
1742                   BRepAdaptor_Curve PrevEcurve(PrevEdge);
1743                   BRepAdaptor_Curve Ecurve(CurEdge);
1744                   Standard_Real SampleOnPrev = (PrevEcurve.LastParameter()-PrevEcurve.FirstParameter())/NbSamples;
1745                   Standard_Real SampleOnCur = (Ecurve.LastParameter()-Ecurve.FirstParameter())/NbSamples;
1746                   for (nbs = 1; nbs <= NbSamples-1; nbs++)
1747                   {
1748                     Standard_Real ParOnPrev = (PrevEdge.Orientation() == TopAbs_FORWARD)?
1749                       (PrevEcurve.FirstParameter() + nbs*SampleOnPrev) :
1750                       (PrevEcurve.FirstParameter() + (NbSamples-nbs)*SampleOnPrev);
1751                     Standard_Real ParOnCur = (CurEdge.Orientation() == TopAbs_FORWARD)?
1752                       (Ecurve.FirstParameter() + (NbSamples-nbs)*SampleOnCur) :
1753                       (Ecurve.FirstParameter() + nbs*SampleOnCur);
1754                     gp_Pnt PonPrev = PrevEcurve.Value(ParOnPrev);
1755                     gp_Pnt PonCur = Ecurve.Value(ParOnCur).XYZ() + Offset.XYZ();
1756                     SumDist += PonPrev.Distance(PonCur);
1757                   }
1758                 }
1759               }
1760             if (SumDist < MinSumDist)
1761               {
1762                 MinSumDist = SumDist;
1763                 jmin = j;
1764                 forward = Standard_False;
1765               }
1766           }
1767       
1768       PrevSeq.Clear();
1769       PrevEseq.Clear();
1770       if (forward)
1771         {
1772           for (j = jmin; j <= theLength; j++)
1773             {
1774               BB.Add( newwire, TopoDS::Edge(SeqEdges(j)) );
1775               PrevSeq.Append( SeqVertices(j) );
1776               PrevEseq.Append( SeqEdges(j) );
1777             }
1778           for (j = 1; j < jmin; j++)
1779             {
1780               BB.Add( newwire, TopoDS::Edge(SeqEdges(j)) );
1781               PrevSeq.Append( SeqVertices(j) );
1782               PrevEseq.Append( SeqEdges(j) );
1783             }
1784         }
1785       else
1786         {
1787           for (j = jmin-1; j >= 1; j--)
1788             {
1789               TopoDS_Shape aLocalShape = SeqEdges(j).Reversed();
1790               BB.Add( newwire, TopoDS::Edge(aLocalShape) );
1791               //PrevSeq.Append( SeqVertices(j) );
1792               PrevEseq.Append( SeqEdges(j).Reversed() );
1793             }
1794           for (j = theLength; j >= jmin; j--)
1795             {
1796               TopoDS_Shape aLocalShape = SeqEdges(j).Reversed();
1797               BB.Add( newwire, TopoDS::Edge(aLocalShape) );
1798               //PrevSeq.Append( SeqVertices(j) );
1799               PrevEseq.Append( SeqEdges(j).Reversed() );
1800             }
1801           for (j = jmin; j >= 1; j--)
1802             PrevSeq.Append( SeqVertices(j) );
1803           for (j = theLength; j > jmin; j--)
1804             PrevSeq.Append( SeqVertices(j) );
1805         }
1806       
1807       newwire.Closed( Standard_True );
1808       newwire.Orientation( TopAbs_FORWARD );
1809       myWork(i) = newwire;
1810     }
1811 #ifdef OCCT_DEBUG_EFV
1812
1813   for ( i=ideb; i<=myWork.Length(); i++) {
1814     
1815     const TopoDS_Wire& wire = TopoDS::Wire(myWork(i));
1816     
1817     Standard_Integer nbEdges=0;
1818     for(anExp.Init(TopoDS::Wire(myWork(i))); anExp.More(); anExp.Next())
1819       nbEdges++;
1820     TopExp::Vertices(wire,Vdeb,Vfin);
1821     Standard_Boolean wClosed = wire.Closed();
1822     if (!wClosed) {
1823       // on regarde quand meme si les vertex sont les memes.
1824       if ( Vdeb.IsSame(Vfin)) wClosed = Standard_True;
1825     }
1826     
1827     
1828     TopoDS_Vertex Vsuiv, VF, VR;
1829     TopoDS_Wire newwire;
1830     BRep_Builder BW;
1831     BW.MakeWire(newwire);
1832     if (i==ideb) {
1833       anExp.Init(wire);
1834       const TopoDS_Edge Ecur = TopoDS::Edge(anExp.Current());
1835       TopExp::Vertices(Ecur,VF,VR);
1836       if (Vdeb.IsSame(VF)) Vsuiv=VR;
1837       else if (Vdeb.IsSame(VR)) Vsuiv=VF;
1838       else {
1839         // par defaut on prend l'origine sur cette arete
1840         if (VR.IsSame(TopoDS::Vertex(anExp.CurrentVertex()))) {
1841           Vdeb = VR;
1842           Vsuiv = VF;
1843         }
1844         else {
1845           Vdeb = VF;
1846           Vsuiv = VR;
1847         }
1848       }
1849       Pdeb=BRep_Tool::Pnt(Vdeb);
1850       Psuiv=BRep_Tool::Pnt(Vsuiv);
1851       Standard_Real U1 = BRep_Tool::Parameter(Vdeb,Ecur);
1852       Standard_Real U2 = BRep_Tool::Parameter(Vsuiv,Ecur);
1853       BRepAdaptor_Curve Curve(Ecur);
1854       PPs = Curve.Value(0.25*(U1+3*U2));
1855       myWork(ideb) = wire;
1856     }
1857     else {
1858       // on ramene Pdeb, Psuiv et PPs dans le plan courant
1859       gp_Pnt Pnew,Pnext,PPn; 
1860       Transform(Standard_True,Pdeb,Pos->Value(i-1),Axe->Value(i-1), 
1861                               Pos->Value(i),Axe->Value(i),Pnew);
1862       Transform(Standard_True,Psuiv,Pos->Value(i-1),Axe->Value(i-1), 
1863                               Pos->Value(i),Axe->Value(i),Pnext);
1864       Transform(Standard_True,PPs,Pos->Value(i-1),Axe->Value(i-1), 
1865                               Pos->Value(i),Axe->Value(i),PPn);
1866       
1867       Standard_Real distmini,dist;
1868       Standard_Integer rang=0,rangdeb=0;
1869       TopoDS_Vertex Vmini;
1870       gp_Pnt Pmini,P1,P2;
1871       SeqOfVertices(wire,SeqV);
1872       if (SeqV.Length()>NbMaxV) 
1873         throw Standard_NoSuchObject("BRepFill::ComputeOrigin failed");
1874       if (!polar) {
1875         // choix du vertex le plus proche comme origine
1876         distmini = Precision::Infinite();
1877         for (Standard_Integer ii=1;ii<=SeqV.Length();ii++) {
1878           P1 = BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(ii)));
1879           dist = P1.Distance(Pnew);
1880           if (dist<distmini) {
1881             distmini = dist;
1882             Vmini = TopoDS::Vertex(SeqV.Value(ii));
1883           }
1884         }
1885         if (!Vmini.IsNull()) Pmini = BRep_Tool::Pnt(Vmini);
1886       }
1887       else {
1888         
1889         // recherche du vertex correspondant a la projection conique
1890         Standard_Real angmin, angV, eta = Precision::Angular();
1891         TopoDS_Vertex Vopti;
1892         angmin = M_PI/2;
1893         distmini = Precision::Infinite();
1894         gp_Dir dir0(gp_Vec(Pnew,P.Location()));
1895         for (Standard_Integer ii=1;ii<=SeqV.Length();ii++) {
1896           P1 = BRep_Tool::Pnt(TopoDS::Vertex(SeqV.Value(ii)));
1897           dist = Pnew.Distance(P1);
1898           if (dist<Precision::Confusion()) {
1899             angV = 0.0;
1900           }
1901           else {
1902             gp_Dir dir1(gp_Vec(Pnew,P1));
1903             angV = dir1.Angle(dir0);
1904           }
1905           if (angV>M_PI/2) angV = M_PI - angV;
1906           if (angmin>angV+eta) {
1907             distmini = dist;
1908             angmin = angV;
1909             Vopti = TopoDS::Vertex(SeqV.Value(ii));
1910           }
1911           else if (Abs(angmin-angV)<eta) {
1912             if (dist<distmini) {
1913               distmini = dist;
1914               angmin = angV;
1915               Vopti = TopoDS::Vertex(SeqV.Value(ii));
1916             }
1917           }
1918         }
1919         gp_Pnt Popti;
1920         if (!Vopti.IsNull()) Popti = BRep_Tool::Pnt(Vopti);
1921         Vmini = Vopti;
1922         
1923       }
1924
1925       distmini = Precision::Infinite();
1926       for (anExp.Init(wire); anExp.More(); anExp.Next()) {
1927         TopoDS_Edge Ecur = anExp.Current();
1928         TopoDS_Vertex Vcur = anExp.CurrentVertex();
1929         TopExp::Vertices(Ecur,VF,VR);
1930         if (VF.IsSame(Vmini)) {
1931           P1 = BRep_Tool::Pnt(VR);
1932           dist = P1.Distance(Pnext);
1933           if (dist<=distmini) {
1934             distmini = dist;
1935             Vsuiv = VR;
1936           }
1937         }
1938         if (VR.IsSame(Vmini)) {
1939           P1 = BRep_Tool::Pnt(VF);
1940           dist = P1.Distance(Pnext);
1941           if (dist<distmini) {
1942             distmini = dist;
1943             Vsuiv = VF;
1944           }
1945         }
1946       }
1947       
1948       // choix du sens de parcours en fonction de Pnext
1949       Standard_Boolean parcours = Standard_False;
1950       if (i==myWork.Length() && myDegen2) {
1951         // derniere section ponctuelle
1952         rangdeb = 1;
1953         parcours = Standard_True;
1954       }
1955       else {
1956         // cas general
1957         gp_Pnt Pbout = Pnext;
1958         TopoDS_Edge E1,E2;
1959         TopoDS_Vertex V1,V2;
1960         EdgesFromVertex(wire,Vmini,E1,E2);
1961         
1962         TopExp::Vertices(E1,V1,V2,Standard_True);
1963 #ifndef OCCT_DEBUG
1964         Standard_Real U1=0, U2=0;
1965 #else
1966         Standard_Real U1, U2;
1967 #endif
1968         if (Vmini.IsSame(V1)) { 
1969           P1 = BRep_Tool::Pnt(V2);
1970           U1 = 0.25*(BRep_Tool::Parameter(V1,E1)+3*BRep_Tool::Parameter(V2,E1));
1971         }
1972         if (Vmini.IsSame(V2)) {
1973           P1 = BRep_Tool::Pnt(V1);
1974           U1 = 0.25*(3*BRep_Tool::Parameter(V1,E1)+BRep_Tool::Parameter(V2,E1));
1975         }
1976         
1977         TopExp::Vertices(E2,V1,V2,Standard_True);
1978         if (Vmini.IsSame(V1)) { 
1979           P2 = BRep_Tool::Pnt(V2);
1980           U2 = 0.25*(BRep_Tool::Parameter(V1,E2)+3*BRep_Tool::Parameter(V2,E2));
1981         }
1982         if (Vmini.IsSame(V2)) {
1983           P2 = BRep_Tool::Pnt(V1);
1984           U2 = 0.25*(3*BRep_Tool::Parameter(V1,E2)+BRep_Tool::Parameter(V2,E2));
1985         }
1986         
1987         if (Abs(Pbout.Distance(P1)-Pbout.Distance(P2))<Precision::Confusion()) {
1988           // cas limite ; on se decale un peu
1989           Pbout = PPn;
1990           BRepAdaptor_Curve Curve1(E1);
1991           P1 = Curve1.Value(U1);
1992           BRepAdaptor_Curve Curve2(E2);
1993           P2 = Curve2.Value(U2);
1994         }
1995         
1996         // calcul de rangdeb
1997         rangdeb = 0;
1998         if (Pbout.Distance(P1)<Pbout.Distance(P2)){
1999           // P1 est plus proche; parcours = False
2000           parcours = Standard_False;
2001           rang = 0;
2002           for (anExp.Init(wire); anExp.More(); anExp.Next()) {
2003             rang++;
2004             TopoDS_Edge Ecur = anExp.Current();
2005             if (E1.IsSame(Ecur)) {
2006               rangdeb = rang;
2007             }
2008           }
2009           BRepAdaptor_Curve Curve(E1);
2010           PPs = Curve.Value(U1);
2011         }
2012         else {
2013           // P2 est plus proche; parcours = True
2014           parcours = Standard_True;
2015           rang = 0;
2016           for (anExp.Init(wire); anExp.More(); anExp.Next()) {
2017             rang++;
2018             TopoDS_Edge Ecur = anExp.Current();
2019             if (E2.IsSame(Ecur)) {
2020               rangdeb = rang;
2021             }
2022           }
2023           BRepAdaptor_Curve Curve(E2);
2024           PPs = Curve.Value(U2);
2025         }
2026       }
2027
2028       // reconstruction du wire a partir de rangdeb
2029       TopTools_SequenceOfShape SeqEdges;
2030       SeqEdges.Clear();
2031       for (anExp.Init(TopoDS::Wire(wire)); anExp.More(); anExp.Next()) {
2032         SeqEdges.Append(anExp.Current());
2033       }
2034       if (parcours) {
2035         for (rang=rangdeb;rang<=nbEdges;rang++) {
2036           BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang)));
2037         }
2038         for (rang=1;rang<rangdeb;rang++) {
2039           BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang)));
2040         }
2041       }
2042       else {
2043         for (rang=rangdeb;rang>=1;rang--) {
2044           TopoDS_Shape aLocalShape = SeqEdges.Value(rang).Reversed();
2045           BW.Add(newwire,TopoDS::Edge(aLocalShape));
2046 //        BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang).Reversed()));
2047         }
2048         for (rang=nbEdges;rang>rangdeb;rang--) {
2049           TopoDS_Shape aLocalShape = SeqEdges.Value(rang).Reversed();
2050           BW.Add(newwire,TopoDS::Edge(aLocalShape));
2051 //        BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang).Reversed()));
2052         }
2053       }
2054       
2055       myWork(i) = newwire.Oriented(TopAbs_FORWARD);
2056       
2057       // on passe au wire suivant
2058       if (!Vmini.IsNull()) Pdeb=BRep_Tool::Pnt(Vmini);
2059       if (!Vsuiv.IsNull()) Psuiv=BRep_Tool::Pnt(Vsuiv);
2060     }
2061   }
2062 #endif
2063   
2064   // blocking sections ?
2065   if (vClosed)
2066     myWork(myWork.Length()) = myWork(1);
2067 }
2068
2069 //=======================================================================
2070 //function : SearchOrigin
2071 //purpose  : 
2072 //=======================================================================
2073
2074 void BRepFill_CompatibleWires::SearchOrigin()
2075 {
2076   // reorganize the open wires respecting orientation and origin
2077   
2078   gp_Pln P0,P;  
2079
2080   TopoDS_Vertex Vdeb, Vfin;
2081   gp_Pnt Pdeb,  Pfin;//,Psuiv;
2082
2083   BRepTools_WireExplorer anExp;
2084
2085   Standard_Boolean allOpen = Standard_True;
2086   Standard_Integer ideb=1, ifin=myWork.Length();
2087   if (myDegen1) ideb++;
2088   if (myDegen2) ifin--;
2089   Standard_Boolean vClosed = (!myDegen1) && (!myDegen2)
2090                                 && (myWork(ideb).IsSame(myWork(ifin)));
2091   
2092 //  for (Standard_Integer i=ideb; i<=ifin; i++) {
2093   Standard_Integer i;
2094   for  (i=ideb; i<=ifin; i++) {
2095     allOpen = (allOpen && !myWork(i).Closed());
2096   }
2097   if (!allOpen)
2098     throw Standard_NoSuchObject("BRepFill_CompatibleWires::SearchOrigin : the wires must be open");
2099
2100   // init
2101
2102   TopoDS_Wire wire1 = TopoDS::Wire(myWork(ideb));
2103   wire1.Orientation(TopAbs_FORWARD);
2104   TopExp::Vertices(wire1,Vdeb,Vfin);
2105   Pdeb = BRep_Tool::Pnt(Vdeb);
2106   Pfin = BRep_Tool::Pnt(Vfin);
2107   Standard_Boolean isline0 = (!PlaneOfWire(wire1,P0)), isline;
2108   myWork(ideb) = wire1;
2109   //OCC86
2110   anExp.Init(wire1);
2111   TopoDS_Edge E0 = anExp.Current(), E;
2112
2113   for ( i=ideb+1; i<=ifin; i++) {
2114
2115     TopoDS_Wire wire = TopoDS::Wire(myWork(i));
2116     wire.Orientation(TopAbs_FORWARD);
2117
2118     TopTools_SequenceOfShape SeqEdges;
2119     SeqEdges.Clear();
2120     Standard_Integer nbEdges=0;
2121     //OCC86  for(anExp.Init(wire); anExp.More(); anExp.Next()) {
2122     for(anExp.Init(wire), E = anExp.Current(); anExp.More(); anExp.Next()) {
2123       SeqEdges.Append(anExp.Current());
2124       nbEdges++;
2125     }
2126     TopExp::Vertices(wire,Vdeb,Vfin);
2127     isline = (!PlaneOfWire(wire,P));
2128
2129     TopoDS_Vertex Vmini;
2130     TopoDS_Wire newwire;
2131     BRep_Builder BW;
2132     BW.MakeWire(newwire);
2133     Standard_Boolean parcours = Standard_True;
2134
2135     if (isline0 || isline) {
2136       
2137       // particular case of straight segments 
2138       gp_Pnt P1 = BRep_Tool::Pnt(Vdeb),
2139              P2 = BRep_Tool::Pnt(Vfin);
2140       Standard_Real dist1, dist2;
2141       dist1 = Pdeb.Distance(P1)+Pfin.Distance(P2);
2142       dist2 = Pdeb.Distance(P2)+Pfin.Distance(P1);
2143       parcours = (dist2>=dist1);
2144     }
2145     
2146     else {
2147       //OCC86
2148       gp_Pnt P1 = BRep_Tool::Pnt(Vdeb), P1o = Pdeb,
2149              P2 = BRep_Tool::Pnt(Vfin), P2o = Pfin;
2150 /*    // return Pdeb in the current plane
2151       gp_Pnt Pnew = Pdeb.Translated (P0.Location(),P.Location());
2152       gp_Ax1 A0 = P0.Axis();
2153       gp_Ax1 A1 = P.Axis();
2154       
2155       if (!A0.IsParallel(A1,1.e-4)) {
2156         gp_Vec vec1(A0.Direction()), vec2(A1.Direction()), 
2157         norm = vec1 ^ vec2;
2158         gp_Ax1 Norm(P.Location(),norm);
2159         Standard_Real ang = vec1.AngleWithRef(vec2,norm);
2160         if (ang > M_PI/2.0)
2161           ang = M_PI - ang;
2162         if (ang < -M_PI/2.0)
2163           ang = -M_PI - ang;
2164         if (Abs(ang-M_PI/2.0)<Precision::Angular()) {
2165           // cas d'ambiguite
2166           gp_Vec Vtrans(P0.Location(),P.Location()),Vsign;
2167           Standard_Real alpha,beta,sign=1;
2168           Vsign.SetLinearForm(Vtrans.Dot(vec1),vec2,-Vtrans.Dot(vec2),vec1);
2169           alpha = Vsign.Dot(vec1);
2170           beta = Vsign.Dot(vec2);
2171           Standard_Boolean pasnul = (Abs(alpha)>1.e-4 && Abs(beta)>1.e-4);
2172           if ( alpha*beta>0.0 && pasnul ) sign=-1;
2173           ang *= sign;
2174         }
2175         Pnew = Pnew.Rotated (Norm,ang);
2176       }
2177       // choix entre Vdeb et Vfin
2178       Standard_Real dist = Pnew.Distance(P1);
2179       parcours = (dist<Pnew.Distance(P2));
2180 */      
2181       if(P1.IsEqual(P2,Precision::Confusion()) || P1o.IsEqual(P2o,Precision::Confusion())){
2182         BRepAdaptor_Curve Curve0(E0), Curve(E);
2183         Curve0.D0(Curve0.FirstParameter() + Precision::Confusion(), P2o);
2184         Curve.D0(Curve.FirstParameter() + Precision::Confusion(), P2);
2185       };
2186       gp_Vec VDebFin0(P1o,P2o), VDebFin(P1,P2);
2187       Standard_Real AStraight = VDebFin0.Angle(VDebFin);
2188       parcours = (AStraight < M_PI/2.0? Standard_True: Standard_False);
2189     }
2190     
2191     // reconstruction of the wire
2192     Standard_Integer rang;
2193     if (parcours) {
2194       for (rang=1;rang<=nbEdges;rang++) {
2195         TopoDS_Shape alocalshape = SeqEdges.Value(rang);
2196         BW.Add(newwire,TopoDS::Edge(alocalshape));
2197 //      BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang)));
2198       }
2199     }
2200     else {
2201       for (rang=nbEdges;rang>=1;rang--) {
2202         TopoDS_Shape alocalshape = SeqEdges.Value(rang).Reversed();
2203         BW.Add(newwire,TopoDS::Edge(alocalshape));
2204 //      BW.Add(newwire,TopoDS::Edge(SeqEdges.Value(rang).Reversed()));
2205       }
2206     }
2207
2208     // orientation of the wire
2209     newwire.Oriented(TopAbs_FORWARD);
2210     myWork(i) = newwire;
2211
2212     // passe to the next wire 
2213     if (parcours) {
2214       Pdeb = BRep_Tool::Pnt(Vdeb);
2215       Pfin = BRep_Tool::Pnt(Vfin);
2216     }
2217     else {
2218       Pfin = BRep_Tool::Pnt(Vdeb);
2219       Pdeb = BRep_Tool::Pnt(Vfin);
2220     }
2221     P0 = P;
2222     isline0 = isline;
2223     //OCC86
2224     E0 = E;
2225   }
2226   
2227   // blocking sections ?
2228   if (vClosed)
2229     myWork(myWork.Length()) = myWork(1);
2230 }