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