src/BRepFill/BRepFill_CompatibleWires.cxx

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