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