src/ShapeUpgrade/ShapeUpgrade_UnifySameDomain.cxx

   1 // Created on: 2012-06-09
   2 // Created by: jgv@ROLEX
   3 // Copyright (c) 2012-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16
  17 #include <BRep_Builder.hxx>
  18 #include <BRep_Tool.hxx>
  19 #include <BRepLib.hxx>
  20 #include <BRepLib_MakeEdge.hxx>
  21 #include <BRepTopAdaptor_TopolTool.hxx>
  22 #include <GC_MakeCircle.hxx>
  23 #include <Geom2d_Line.hxx>
  24 #include <Geom2d_TrimmedCurve.hxx>
  25 #include <Geom2dConvert.hxx>
  26 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
  27 #include <Geom_BezierCurve.hxx>
  28 #include <Geom_BSplineCurve.hxx>
  29 #include <Geom_Circle.hxx>
  30 #include <Geom_CylindricalSurface.hxx>
  31 #include <Geom_ElementarySurface.hxx>
  32 #include <Geom_Line.hxx>
  33 #include <Geom_OffsetSurface.hxx>
  34 #include <Geom_Plane.hxx>
  35 #include <Geom_RectangularTrimmedSurface.hxx>
  36 #include <Geom_Surface.hxx>
  37 #include <Geom_SurfaceOfLinearExtrusion.hxx>
  38 #include <Geom_SurfaceOfRevolution.hxx>
  39 #include <Geom_SweptSurface.hxx>
  40 #include <Geom_TrimmedCurve.hxx>
  41 #include <GeomAdaptor_HSurface.hxx>
  42 #include <GeomConvert.hxx>
  43 #include <GeomConvert_CompCurveToBSplineCurve.hxx>
  44 #include <GeomLib_IsPlanarSurface.hxx>
  45 #include <gp_Cylinder.hxx>
  46 #include <gp_Dir.hxx>
  47 #include <gp_Lin.hxx>
  48 #include <IntPatch_ImpImpIntersection.hxx>
  49 #include <ShapeAnalysis_Edge.hxx>
  50 #include <ShapeAnalysis_WireOrder.hxx>
  51 #include <ShapeBuild_Edge.hxx>
  52 #include <ShapeBuild_ReShape.hxx>
  53 #include <ShapeFix_Edge.hxx>
  54 #include <ShapeFix_Face.hxx>
  55 #include <ShapeFix_Shell.hxx>
  56 #include <ShapeFix_Wire.hxx>
  57 #include <ShapeUpgrade_UnifySameDomain.hxx>
  58 #include <Standard_Type.hxx>
  59 #include <TColGeom2d_Array1OfBSplineCurve.hxx>
  60 #include <TColGeom2d_HArray1OfBSplineCurve.hxx>
  61 #include <TColGeom2d_SequenceOfBoundedCurve.hxx>
  62 #include <TColGeom_Array1OfBSplineCurve.hxx>
  63 #include <TColGeom_HArray1OfBSplineCurve.hxx>
  64 #include <TColGeom_SequenceOfSurface.hxx>
  65 #include <TColStd_Array1OfReal.hxx>
  66 #include <TColStd_MapOfInteger.hxx>
  67 #include <TopExp.hxx>
  68 #include <TopExp_Explorer.hxx>
  69 #include <TopoDS.hxx>
  70 #include <TopoDS_Edge.hxx>
  71 #include <TopoDS_Face.hxx>
  72 #include <TopoDS_Shape.hxx>
  73 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  74 #include <TopTools_IndexedMapOfShape.hxx>
  75 #include <TopTools_ListIteratorOfListOfShape.hxx>
  76 #include <TopTools_MapOfShape.hxx>
  77 #include <TopTools_SequenceOfShape.hxx>
  78 #include <gp_Circ.hxx>
  79 #include <BRepAdaptor_Curve.hxx>
  80 #include <BRepAdaptor_Curve2d.hxx>
  81 #include <gp_Vec2d.hxx>
  82
  83 IMPLEMENT_STANDARD_RTTIEXT(ShapeUpgrade_UnifySameDomain,Standard_Transient)
  84
  85 struct SubSequenceOfEdges
  86 {
  87   TopTools_SequenceOfShape SeqsEdges;
  88   TopoDS_Edge UnionEdges;
  89 };
  90
  91 //=======================================================================
  92 //function : AddOrdinaryEdges
  93 //purpose  : auxilary
  94 //=======================================================================
  95 // adds edges from the shape to the sequence
  96 // seams and equal edges are dropped
  97 // Returns true if one of original edges dropped
  98 static Standard_Boolean AddOrdinaryEdges(TopTools_SequenceOfShape& edges,
  99                                          const TopoDS_Shape aShape,
 100                                          Standard_Integer& anIndex)
 101 {
 102   //map of edges
 103   TopTools_IndexedMapOfShape aNewEdges;
 104   //add edges without seams
 105   for(TopExp_Explorer exp(aShape,TopAbs_EDGE); exp.More(); exp.Next()) {
 106     TopoDS_Shape edge = exp.Current();
 107     if(aNewEdges.Contains(edge))
 108       aNewEdges.RemoveKey(edge);
 109     else
 110       aNewEdges.Add(edge);
 111   }
 112
 113   Standard_Boolean isDropped = Standard_False;
 114   //merge edges and drop seams
 115   Standard_Integer i;
 116   for (i = 1; i <= edges.Length(); i++) {
 117     TopoDS_Shape current = edges(i);
 118     if(aNewEdges.Contains(current)) {
 119
 120       aNewEdges.RemoveKey(current);
 121       edges.Remove(i);
 122       i--;
 123
 124       if(!isDropped) {
 125         isDropped = Standard_True;
 126         anIndex = i;
 127       }
 128     }
 129   }
 130
 131   //add edges to the sequence
 132   for (i = 1; i <= aNewEdges.Extent(); i++)
 133     edges.Append(aNewEdges(i));
 134
 135   return isDropped;
 136 }
 137
 138 //=======================================================================
 139 //function : getCylinder
 140 //purpose  : auxilary
 141 //=======================================================================
 142 static Standard_Boolean getCylinder(Handle(Geom_Surface)& theInSurface,
 143                                     gp_Cylinder& theOutCylinder)
 144 {
 145   Standard_Boolean isCylinder = Standard_False;
 146
 147   if (theInSurface->IsKind(STANDARD_TYPE(Geom_CylindricalSurface))) {
 148     Handle(Geom_CylindricalSurface) aGC = Handle(Geom_CylindricalSurface)::DownCast(theInSurface);
 149
 150     theOutCylinder = aGC->Cylinder();
 151     isCylinder = Standard_True;
 152   }
 153   else if (theInSurface->IsKind(STANDARD_TYPE(Geom_SurfaceOfRevolution))) {
 154     Handle(Geom_SurfaceOfRevolution) aRS =
 155       Handle(Geom_SurfaceOfRevolution)::DownCast(theInSurface);
 156     Handle(Geom_Curve) aBasis = aRS->BasisCurve();
 157     if (aBasis->IsKind(STANDARD_TYPE(Geom_Line))) {
 158       Handle(Geom_Line) aBasisLine = Handle(Geom_Line)::DownCast(aBasis);
 159       gp_Dir aDir = aRS->Direction();
 160       gp_Dir aBasisDir = aBasisLine->Position().Direction();
 161       if (aBasisDir.IsParallel(aDir, Precision::Angular())) {
 162         // basis line is parallel to the revolution axis: it is a cylinder
 163         gp_Pnt aLoc = aRS->Location();
 164         Standard_Real aR = aBasisLine->Lin().Distance(aLoc);
 165         gp_Ax3 aCylAx (aLoc, aDir);
 166
 167         theOutCylinder = gp_Cylinder(aCylAx, aR);
 168         isCylinder = Standard_True;
 169       }
 170     }
 171   }
 172   else if (theInSurface->IsKind(STANDARD_TYPE(Geom_SurfaceOfLinearExtrusion))) {
 173     Handle(Geom_SurfaceOfLinearExtrusion) aLES =
 174       Handle(Geom_SurfaceOfLinearExtrusion)::DownCast(theInSurface);
 175     Handle(Geom_Curve) aBasis = aLES->BasisCurve();
 176     if (aBasis->IsKind(STANDARD_TYPE(Geom_Circle))) {
 177       Handle(Geom_Circle) aBasisCircle = Handle(Geom_Circle)::DownCast(aBasis);
 178       gp_Dir aDir = aLES->Direction();
 179       gp_Dir aBasisDir = aBasisCircle->Position().Direction();
 180       if (aBasisDir.IsParallel(aDir, Precision::Angular())) {
 181         // basis circle is normal to the extrusion axis: it is a cylinder
 182         gp_Pnt aLoc = aBasisCircle->Location();
 183         Standard_Real aR = aBasisCircle->Radius();
 184         gp_Ax3 aCylAx (aLoc, aDir);
 185
 186         theOutCylinder = gp_Cylinder(aCylAx, aR);
 187         isCylinder = Standard_True;
 188       }
 189     }
 190   }
 191   else {
 192   }
 193
 194   return isCylinder;
 195 }
 196
 197 //=======================================================================
 198 //function : ClearRts
 199 //purpose  : auxilary
 200 //=======================================================================
 201 static Handle(Geom_Surface) ClearRts(const Handle(Geom_Surface)& aSurface)
 202 {
 203   if(aSurface->IsKind(STANDARD_TYPE(Geom_RectangularTrimmedSurface))) {
 204     Handle(Geom_RectangularTrimmedSurface) rts =
 205       Handle(Geom_RectangularTrimmedSurface)::DownCast(aSurface);
 206     return rts->BasisSurface();
 207   }
 208   return aSurface;
 209 }
 210
 211 //=======================================================================
 212 //function : GetNormalToSurface
 213 //purpose  : Gets the normal to surface by the given parameter on edge.
 214 //           Returns True if normal was computed.
 215 //=======================================================================
 216 static Standard_Boolean GetNormalToSurface(const TopoDS_Face& theFace,
 217                                            const TopoDS_Edge& theEdge,
 218                                            const Standard_Real theP,
 219                                            gp_Dir& theNormal)
 220 {
 221   Standard_Real f, l;
 222   // get 2d curve to get point in 2d
 223   const Handle(Geom2d_Curve)& aC2d = BRep_Tool::CurveOnSurface(theEdge, theFace, f, l);
 224   if (aC2d.IsNull()) {
 225     return Standard_False;
 226   }
 227   //
 228   // 2d point
 229   gp_Pnt2d aP2d;
 230   aC2d->D0(theP, aP2d);
 231   //
 232   // get D1
 233   gp_Vec aDU, aDV;
 234   gp_Pnt aP3d;
 235   TopLoc_Location aLoc;
 236   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(theFace, aLoc);
 237   aS->D1(aP2d.X(), aP2d.Y(), aP3d, aDU, aDV);
 238   //
 239   // compute normal
 240   gp_Vec aVNormal = aDU.Crossed(aDV);
 241   if (aVNormal.Magnitude() < Precision::Confusion()) {
 242     return Standard_False;
 243   }
 244   //
 245   if (theFace.Orientation() == TopAbs_REVERSED) {
 246     aVNormal.Reverse();
 247   }
 248   //
 249   aVNormal.Transform(aLoc.Transformation());
 250   theNormal = gp_Dir(aVNormal);
 251   return Standard_True;
 252 }
 253
 254 //=======================================================================
 255 //function : IsSameDomain
 256 //purpose  :
 257 //=======================================================================
 258 static Standard_Boolean IsSameDomain(const TopoDS_Face& aFace,
 259                                      const TopoDS_Face& aCheckedFace,
 260                                      const Standard_Real theLinTol,
 261                                      const Standard_Real theAngTol)
 262 {
 263   //checking the same handles
 264   TopLoc_Location L1, L2;
 265   Handle(Geom_Surface) S1, S2;
 266
 267   S1 = BRep_Tool::Surface(aFace,L1);
 268   S2 = BRep_Tool::Surface(aCheckedFace,L2);
 269
 270   if (S1 == S2 && L1 == L2)
 271     return Standard_True;
 272
 273   S1 = BRep_Tool::Surface(aFace);
 274   S2 = BRep_Tool::Surface(aCheckedFace);
 275
 276   S1 = ClearRts(S1);
 277   S2 = ClearRts(S2);
 278
 279   //Handle(Geom_OffsetSurface) aGOFS1, aGOFS2;
 280   //aGOFS1 = Handle(Geom_OffsetSurface)::DownCast(S1);
 281   //aGOFS2 = Handle(Geom_OffsetSurface)::DownCast(S2);
 282   //if (!aGOFS1.IsNull()) S1 = aGOFS1->BasisSurface();
 283   //if (!aGOFS2.IsNull()) S2 = aGOFS2->BasisSurface();
 284
 285   // case of two planar surfaces:
 286   // all kinds of surfaces checked, including b-spline and bezier
 287   GeomLib_IsPlanarSurface aPlanarityChecker1(S1, theLinTol);
 288   if (aPlanarityChecker1.IsPlanar()) {
 289     GeomLib_IsPlanarSurface aPlanarityChecker2(S2, theLinTol);
 290     if (aPlanarityChecker2.IsPlanar()) {
 291       gp_Pln aPln1 = aPlanarityChecker1.Plan();
 292       gp_Pln aPln2 = aPlanarityChecker2.Plan();
 293
 294       if (aPln1.Position().Direction().IsParallel(aPln2.Position().Direction(), theAngTol) &&
 295         aPln1.Distance(aPln2) < theLinTol) {
 296         return Standard_True;
 297       }
 298     }
 299   }
 300
 301   // case of two elementary surfaces: use OCCT tool
 302   // elementary surfaces: ConicalSurface, CylindricalSurface,
 303   //                      Plane, SphericalSurface and ToroidalSurface
 304   if (S1->IsKind(STANDARD_TYPE(Geom_ElementarySurface)) &&
 305       S2->IsKind(STANDARD_TYPE(Geom_ElementarySurface)))
 306   {
 307     Handle(GeomAdaptor_HSurface) aGA1 = new GeomAdaptor_HSurface(S1);
 308     Handle(GeomAdaptor_HSurface) aGA2 = new GeomAdaptor_HSurface(S2);
 309
 310     Handle(BRepTopAdaptor_TopolTool) aTT1 = new BRepTopAdaptor_TopolTool();
 311     Handle(BRepTopAdaptor_TopolTool) aTT2 = new BRepTopAdaptor_TopolTool();
 312
 313     try {
 314       IntPatch_ImpImpIntersection anIIInt(aGA1, aTT1, aGA2, aTT2, theLinTol, theLinTol);
 315       if (!anIIInt.IsDone() || anIIInt.IsEmpty())
 316         return Standard_False;
 317
 318       return anIIInt.TangentFaces();
 319     }
 320     catch (Standard_Failure) {
 321       return Standard_False;
 322     }
 323   }
 324
 325   // case of two cylindrical surfaces, at least one of which is a swept surface
 326   // swept surfaces: SurfaceOfLinearExtrusion, SurfaceOfRevolution
 327   if ((S1->IsKind(STANDARD_TYPE(Geom_CylindricalSurface)) ||
 328        S1->IsKind(STANDARD_TYPE(Geom_SweptSurface))) &&
 329       (S2->IsKind(STANDARD_TYPE(Geom_CylindricalSurface)) ||
 330        S2->IsKind(STANDARD_TYPE(Geom_SweptSurface))))
 331   {
 332     gp_Cylinder aCyl1, aCyl2;
 333     if (getCylinder(S1, aCyl1) && getCylinder(S2, aCyl2)) {
 334       if (fabs(aCyl1.Radius() - aCyl2.Radius()) < theLinTol) {
 335         gp_Dir aDir1 = aCyl1.Position().Direction();
 336         gp_Dir aDir2 = aCyl2.Position().Direction();
 337         if (aDir1.IsParallel(aDir2, Precision::Angular())) {
 338           gp_Pnt aLoc1 = aCyl1.Location();
 339           gp_Pnt aLoc2 = aCyl2.Location();
 340           gp_Vec aVec12 (aLoc1, aLoc2);
 341           if (aVec12.SquareMagnitude() < theLinTol*theLinTol ||
 342               aVec12.IsParallel(aDir1, Precision::Angular())) {
 343             return Standard_True;
 344           }
 345         }
 346       }
 347     }
 348   }
 349
 350   return Standard_False;
 351 }
 352
 353 //=======================================================================
 354 //function : UpdateMapOfShapes
 355 //purpose  :
 356 //=======================================================================
 357 static void UpdateMapOfShapes(TopTools_MapOfShape& theMapOfShapes,
 358                               Handle(ShapeBuild_ReShape)& theContext)
 359 {
 360   for (TopTools_MapIteratorOfMapOfShape it(theMapOfShapes); it.More(); it.Next()) {
 361     const TopoDS_Shape& aShape = it.Value();
 362     TopoDS_Shape aContextShape = theContext->Apply(aShape);
 363     if (!aContextShape.IsSame(aShape))
 364       theMapOfShapes.Add(aContextShape);
 365   }
 366 }
 367
 368 //=======================================================================
 369 //function : GlueEdgesWithPCurves
 370 //purpose  : Glues the pcurves of the sequence of edges
 371 //           and glues their 3d curves
 372 //=======================================================================
 373 static TopoDS_Edge GlueEdgesWithPCurves(const TopTools_SequenceOfShape& aChain,
 374                                         const TopoDS_Vertex& FirstVertex,
 375                                         const TopoDS_Vertex& LastVertex)
 376 {
 377   Standard_Integer i, j;
 378
 379   TopoDS_Edge FirstEdge = TopoDS::Edge(aChain(1));
 380   TColGeom_SequenceOfSurface SurfSeq;
 381   NCollection_Sequence<TopLoc_Location> LocSeq;
 382
 383   for (int aCurveIndex = 0;; aCurveIndex++)
 384   {
 385     Handle(Geom2d_Curve) aCurve;
 386     Handle(Geom_Surface) aSurface;
 387     TopLoc_Location aLocation;
 388     Standard_Real aFirst, aLast;
 389     BRep_Tool::CurveOnSurface (FirstEdge, aCurve, aSurface, aLocation, aFirst, aLast, aCurveIndex);
 390     if (aCurve.IsNull())
 391       break;
 392
 393     SurfSeq.Append(aSurface);
 394     LocSeq.Append(aLocation);
 395   }
 396
 397   Standard_Real fpar, lpar;
 398   BRep_Tool::Range(FirstEdge, fpar, lpar);
 399   TopoDS_Edge PrevEdge = FirstEdge;
 400   TopoDS_Vertex CV;
 401   Standard_Real MaxTol = 0.;
 402
 403   TopoDS_Edge ResEdge;
 404   BRep_Builder BB;
 405
 406   Standard_Integer nb_curve = aChain.Length();   //number of curves
 407   TColGeom_Array1OfBSplineCurve tab_c3d(0,nb_curve-1);                    //array of the curves
 408   TColStd_Array1OfReal tabtolvertex(0,nb_curve-1); //(0,nb_curve-2);  //array of the tolerances
 409
 410   TopoDS_Vertex PrevVertex = FirstVertex;
 411   for (i = 1; i <= nb_curve; i++)
 412   {
 413     TopoDS_Edge anEdge = TopoDS::Edge(aChain(i));
 414     TopoDS_Vertex VF, VL;
 415     TopExp::Vertices(anEdge, VF, VL);
 416     Standard_Boolean ToReverse = (!VF.IsSame(PrevVertex));
 417
 418     Standard_Real Tol1 = BRep_Tool::Tolerance(VF);
 419     Standard_Real Tol2 = BRep_Tool::Tolerance(VL);
 420     if (Tol1 > MaxTol)
 421       MaxTol = Tol1;
 422     if (Tol2 > MaxTol)
 423       MaxTol = Tol2;
 424
 425     if (i > 1)
 426     {
 427       TopExp::CommonVertex(PrevEdge, anEdge, CV);
 428       Standard_Real Tol = BRep_Tool::Tolerance(CV);
 429       tabtolvertex(i-2) = Tol;
 430     }
 431
 432     Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
 433     Handle(Geom_TrimmedCurve) aTrCurve = new Geom_TrimmedCurve(aCurve, fpar, lpar);
 434     tab_c3d(i-1) = GeomConvert::CurveToBSplineCurve(aTrCurve);
 435     GeomConvert::C0BSplineToC1BSplineCurve(tab_c3d(i-1), Precision::Confusion());
 436     if (ToReverse)
 437       tab_c3d(i-1)->Reverse();
 438     PrevVertex = (ToReverse)? VF : VL;
 439     PrevEdge = anEdge;
 440   }
 441   Handle(TColGeom_HArray1OfBSplineCurve)  concatcurve;     //array of the concatenated curves
 442   Handle(TColStd_HArray1OfInteger)        ArrayOfIndices;  //array of the remining Vertex
 443   Standard_Boolean closed_flag = Standard_False;
 444   GeomConvert::ConcatC1(tab_c3d,
 445                         tabtolvertex,
 446                         ArrayOfIndices,
 447                         concatcurve,
 448                         closed_flag,
 449                         Precision::Confusion());   //C1 concatenation
 450
 451   if (concatcurve->Length() > 1)
 452   {
 453     GeomConvert_CompCurveToBSplineCurve Concat(concatcurve->Value(concatcurve->Lower()));
 454
 455     for (i = concatcurve->Lower()+1; i <= concatcurve->Upper(); i++)
 456       Concat.Add( concatcurve->Value(i), MaxTol, Standard_True );
 457
 458     concatcurve->SetValue(concatcurve->Lower(), Concat.BSplineCurve());
 459   }
 460   Handle(Geom_BSplineCurve) ResCurve = concatcurve->Value(concatcurve->Lower());
 461
 462   TColGeom2d_SequenceOfBoundedCurve ResPCurves;
 463   for (j = 1; j <= SurfSeq.Length(); j++)
 464   {
 465     TColGeom2d_Array1OfBSplineCurve tab_c2d(0,nb_curve-1); //array of the pcurves
 466
 467     PrevVertex = FirstVertex;
 468     PrevEdge = FirstEdge;
 469     for (i = 1; i <= nb_curve; i++)
 470     {
 471       TopoDS_Edge anEdge = TopoDS::Edge(aChain(i));
 472       TopoDS_Vertex VF, VL;
 473       TopExp::Vertices(anEdge, VF, VL);
 474       Standard_Boolean ToReverse = (!VF.IsSame(PrevVertex));
 475
 476       Handle(Geom2d_Curve) aPCurve =
 477         BRep_Tool::CurveOnSurface(anEdge, SurfSeq(j), LocSeq(j), fpar, lpar);
 478       if (aPCurve.IsNull())
 479         continue;
 480       Handle(Geom2d_TrimmedCurve) aTrPCurve = new Geom2d_TrimmedCurve(aPCurve, fpar, lpar);
 481       tab_c2d(i-1) = Geom2dConvert::CurveToBSplineCurve(aTrPCurve);
 482       Geom2dConvert::C0BSplineToC1BSplineCurve(tab_c2d(i-1), Precision::Confusion());
 483       if (ToReverse)
 484         tab_c2d(i-1)->Reverse();
 485       PrevVertex = (ToReverse)? VF : VL;
 486       PrevEdge = anEdge;
 487     }
 488     Handle(TColGeom2d_HArray1OfBSplineCurve)  concatc2d;     //array of the concatenated curves
 489     Handle(TColStd_HArray1OfInteger)        ArrayOfInd2d;  //array of the remining Vertex
 490     closed_flag = Standard_False;
 491     Geom2dConvert::ConcatC1(tab_c2d,
 492                             tabtolvertex,
 493                             ArrayOfInd2d,
 494                             concatc2d,
 495                             closed_flag,
 496                             Precision::Confusion());   //C1 concatenation
 497
 498     if (concatc2d->Length() > 1)
 499     {
 500       Geom2dConvert_CompCurveToBSplineCurve Concat2d(concatc2d->Value(concatc2d->Lower()));
 501
 502       for (i = concatc2d->Lower()+1; i <= concatc2d->Upper(); i++)
 503         Concat2d.Add( concatc2d->Value(i), MaxTol, Standard_True );
 504
 505       concatc2d->SetValue(concatc2d->Lower(), Concat2d.BSplineCurve());
 506     }
 507     Handle(Geom2d_BSplineCurve) aResPCurve = concatc2d->Value(concatc2d->Lower());
 508     ResPCurves.Append(aResPCurve);
 509   }
 510
 511   ResEdge = BRepLib_MakeEdge(ResCurve,
 512                              FirstVertex, LastVertex,
 513                              ResCurve->FirstParameter(), ResCurve->LastParameter());
 514   BB.SameRange(ResEdge, Standard_False);
 515   BB.SameParameter(ResEdge, Standard_False);
 516   for (j = 1; j <= ResPCurves.Length(); j++)
 517   {
 518     BB.UpdateEdge(ResEdge, ResPCurves(j), SurfSeq(j), LocSeq(j), MaxTol);
 519     BB.Range(ResEdge, SurfSeq(j), LocSeq(j), ResPCurves(j)->FirstParameter(), ResPCurves(j)->LastParameter());
 520   }
 521
 522   BRepLib::SameParameter(ResEdge, MaxTol, Standard_True);
 523
 524   return ResEdge;
 525 }
 526
 527 //=======================================================================
 528 //function : MergeSubSeq
 529 //purpose  : Merges a sequence of edges into one edge if possible
 530 //=======================================================================
 531
 532 static Standard_Boolean MergeSubSeq(const TopTools_SequenceOfShape& aChain,
 533                                     TopoDS_Edge& OutEdge,
 534                                     double theAngTol,
 535                                     Standard_Boolean ConcatBSplines,
 536                                     Standard_Boolean isSafeInputMode,
 537                                     Handle(ShapeBuild_ReShape)& theContext)
 538 {
 539   ShapeAnalysis_Edge sae;
 540   BRep_Builder B;
 541   // union edges in chain
 542   int j;
 543   Standard_Real fp1,lp1,fp2,lp2;
 544   Standard_Boolean IsUnionOfLinesPossible = Standard_True;
 545   Standard_Boolean IsUnionOfCirclesPossible = Standard_True;
 546   Handle(Geom_Curve) c3d1, c3d2;
 547   for(j=1; j<aChain.Length(); j++)
 548   {
 549     TopoDS_Edge edge1 = TopoDS::Edge(aChain.Value(j));
 550     c3d1 = BRep_Tool::Curve(edge1,fp1,lp1);
 551
 552     TopoDS_Edge edge2 = TopoDS::Edge(aChain.Value(j+1));
 553     c3d2 = BRep_Tool::Curve(edge2,fp2,lp2);
 554
 555     if(c3d1.IsNull() || c3d2.IsNull())
 556       return Standard_False;
 557
 558     while(c3d1->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 559       Handle(Geom_TrimmedCurve) tc =
 560         Handle(Geom_TrimmedCurve)::DownCast(c3d1);
 561       c3d1 = tc->BasisCurve();
 562     }
 563     while(c3d2->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 564       Handle(Geom_TrimmedCurve) tc =
 565         Handle(Geom_TrimmedCurve)::DownCast(c3d2);
 566       c3d2 = tc->BasisCurve();
 567     }
 568     if( c3d1->IsKind(STANDARD_TYPE(Geom_Line)) && c3d2->IsKind(STANDARD_TYPE(Geom_Line)) ) {
 569       Handle(Geom_Line) L1 = Handle(Geom_Line)::DownCast(c3d1);
 570       Handle(Geom_Line) L2 = Handle(Geom_Line)::DownCast(c3d2);
 571       gp_Dir Dir1 = L1->Position().Direction();
 572       gp_Dir Dir2 = L2->Position().Direction();
 573       if(!Dir1.IsParallel(Dir2,theAngTol))
 574         IsUnionOfLinesPossible = Standard_False;
 575     }
 576     else
 577       IsUnionOfLinesPossible = Standard_False;
 578     if( c3d1->IsKind(STANDARD_TYPE(Geom_Circle)) && c3d2->IsKind(STANDARD_TYPE(Geom_Circle)) ) {
 579       Handle(Geom_Circle) C1 = Handle(Geom_Circle)::DownCast(c3d1);
 580       Handle(Geom_Circle) C2 = Handle(Geom_Circle)::DownCast(c3d2);
 581       gp_Pnt P01 = C1->Location();
 582       gp_Pnt P02 = C2->Location();
 583       if (P01.Distance(P02) > Precision::Confusion())
 584         IsUnionOfCirclesPossible = Standard_False;
 585     }
 586     else
 587       IsUnionOfCirclesPossible = Standard_False;
 588   }
 589   if (IsUnionOfLinesPossible && IsUnionOfCirclesPossible)
 590     return Standard_False;
 591
 592   //union of lines is possible
 593   if (IsUnionOfLinesPossible)
 594   {
 595     TopoDS_Vertex V[2];
 596     V[0] = sae.FirstVertex(TopoDS::Edge(aChain.First()));
 597     gp_Pnt PV1 = BRep_Tool::Pnt(V[0]);
 598     V[1] = sae.LastVertex(TopoDS::Edge(aChain.Last()));
 599     gp_Pnt PV2 = BRep_Tool::Pnt(V[1]);
 600     gp_Vec Vec(PV1, PV2);
 601     if (isSafeInputMode) {
 602       for (int k = 0; k < 2; k++) {
 603         if (!theContext->IsRecorded(V[k])) {
 604           TopoDS_Vertex Vcopy = TopoDS::Vertex(V[k].EmptyCopied());
 605           theContext->Replace(V[k], Vcopy);
 606           V[k] = Vcopy;
 607         }
 608         else
 609           V[k] = TopoDS::Vertex(theContext->Apply(V[k]));
 610       }
 611     }
 612     Handle(Geom_Line) L = new Geom_Line(gp_Ax1(PV1,Vec));
 613     Standard_Real dist = PV1.Distance(PV2);
 614     Handle(Geom_TrimmedCurve) tc = new Geom_TrimmedCurve(L,0.0,dist);
 615     TopoDS_Edge E;
 616     B.MakeEdge (E, tc ,Precision::Confusion());
 617     B.Add (E,V[0]);  B.Add (E,V[1]);
 618     B.UpdateVertex(V[0], 0., E, 0.);
 619     B.UpdateVertex(V[1], dist, E, 0.);
 620     OutEdge = E;
 621     return Standard_True;
 622   }
 623
 624   if (IsUnionOfCirclesPossible)
 625   {
 626     double f,l;
 627     TopoDS_Edge FE = TopoDS::Edge(aChain.First());
 628     Handle(Geom_Curve) c3d = BRep_Tool::Curve(FE,f,l);
 629
 630     while(c3d->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 631       Handle(Geom_TrimmedCurve) tc =
 632         Handle(Geom_TrimmedCurve)::DownCast(c3d);
 633       c3d = tc->BasisCurve();
 634     }
 635     Handle(Geom_Circle) Cir = Handle(Geom_Circle)::DownCast(c3d);
 636
 637     TopoDS_Vertex V[2];
 638     V[0] = sae.FirstVertex(FE);
 639     V[1] = sae.LastVertex(TopoDS::Edge(aChain.Last()));
 640     TopoDS_Edge E;
 641     if (V[0].IsSame(V[1])) {
 642       // closed chain
 643       BRepAdaptor_Curve adef(FE);
 644       Handle(Geom_Circle) Cir1;
 645       double FP, LP;
 646       if ( FE.Orientation() == TopAbs_FORWARD)
 647       {
 648         FP = adef.FirstParameter();
 649         LP = adef.LastParameter();
 650       }
 651       else
 652       {
 653         FP = adef.LastParameter();
 654         LP = adef.FirstParameter();
 655       }
 656       if (Abs(FP) < Precision::PConfusion())
 657       {
 658         B.MakeEdge (E,Cir, Precision::Confusion());
 659         B.Add(E,V[0]);
 660         B.Add(E,V[1]);
 661         E.Orientation(FE.Orientation());
 662       }
 663       else
 664       {
 665         GC_MakeCircle MC1 (adef.Value(FP), adef.Value((FP + LP) * 0.5), adef.Value(LP));
 666         if (MC1.IsDone())
 667           Cir1 = MC1.Value();
 668         else
 669           return Standard_False;
 670         B.MakeEdge (E, Cir1, Precision::Confusion());
 671         B.Add(E,V[0]);
 672         B.Add(E,V[1]);
 673       }
 674     }
 675     else {
 676       if (isSafeInputMode) {
 677         for (int k = 0; k < 2; k++) {
 678           if (!theContext->IsRecorded(V[k])) {
 679             TopoDS_Vertex Vcopy = TopoDS::Vertex(V[k].EmptyCopied());
 680             theContext->Replace(V[k], Vcopy);
 681             V[k] = Vcopy;
 682           }
 683           else
 684             V[k] = TopoDS::Vertex(theContext->Apply(V[k]));
 685         }
 686       }
 687       gp_Pnt PV1 = BRep_Tool::Pnt(V[0]);
 688       gp_Pnt PV2 = BRep_Tool::Pnt(V[1]);
 689       TopoDS_Vertex VM = sae.LastVertex(FE);
 690       gp_Pnt PVM = BRep_Tool::Pnt(VM);
 691       GC_MakeCircle MC (PV1,PVM,PV2);
 692       Handle(Geom_Circle) C = MC.Value();
 693       gp_Pnt P0 = C->Location();
 694       gp_Dir D1(gp_Vec(P0,PV1));
 695       gp_Dir D2(gp_Vec(P0,PV2));
 696       Standard_Real fpar = C->XAxis().Direction().Angle(D1);
 697       if(fabs(fpar)>Precision::Confusion()) {
 698         // check orientation
 699         gp_Dir ND =  C->XAxis().Direction().Crossed(D1);
 700         if(ND.IsOpposite(C->Axis().Direction(),Precision::Confusion())) {
 701           fpar = -fpar;
 702         }
 703       }
 704       Standard_Real lpar = C->XAxis().Direction().Angle(D2);
 705       if(fabs(lpar)>Precision::Confusion()) {
 706         // check orientation
 707         gp_Dir ND =  C->XAxis().Direction().Crossed(D2);
 708         if(ND.IsOpposite(C->Axis().Direction(),Precision::Confusion())) {
 709           lpar = -lpar;
 710         }
 711       }
 712       if (lpar < fpar) lpar += 2*M_PI;
 713       Handle(Geom_TrimmedCurve) tc = new Geom_TrimmedCurve(C,fpar,lpar);
 714       B.MakeEdge (E,tc,Precision::Confusion());
 715       B.Add(E,V[0]);
 716       B.Add(E,V[1]);
 717       B.UpdateVertex(V[0], fpar, E, 0.);
 718       B.UpdateVertex(V[1], lpar, E, 0.);
 719     }
 720     OutEdge = E;
 721     return Standard_True;
 722   }
 723   if (aChain.Length() > 1 && ConcatBSplines) {
 724     // second step: union edges with various curves
 725     // skl for bug 0020052 from Mantis: perform such unions
 726     // only if curves are bspline or bezier
 727
 728     TopoDS_Vertex VF = sae.FirstVertex(TopoDS::Edge(aChain.First()));
 729     TopoDS_Vertex VL = sae.LastVertex(TopoDS::Edge(aChain.Last()));
 730     Standard_Boolean NeedUnion = Standard_True;
 731     for(j=1; j<=aChain.Length(); j++) {
 732       TopoDS_Edge edge = TopoDS::Edge(aChain.Value(j));
 733       TopLoc_Location Loc;
 734       Handle(Geom_Curve) c3d = BRep_Tool::Curve(edge,Loc,fp1,lp1);
 735       if(c3d.IsNull()) continue;
 736       while(c3d->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 737         Handle(Geom_TrimmedCurve) tc =
 738           Handle(Geom_TrimmedCurve)::DownCast(c3d);
 739         c3d = tc->BasisCurve();
 740       }
 741       if( ( c3d->IsKind(STANDARD_TYPE(Geom_BSplineCurve)) ||
 742             c3d->IsKind(STANDARD_TYPE(Geom_BezierCurve)) ) ) continue;
 743       NeedUnion = Standard_False;
 744       break;
 745     }
 746     if(NeedUnion) {
 747 #ifdef OCCT_DEBUG
 748       cout<<"can not make analitical union => make approximation"<<endl;
 749 #endif
 750       TopoDS_Edge E = GlueEdgesWithPCurves(aChain, VF, VL);
 751       OutEdge = E;
 752       return Standard_True;
 753     }
 754     else {
 755 #ifdef OCCT_DEBUG
 756       cout<<"can not make approximation for such types of curves"<<endl;
 757 #endif
 758       return Standard_False;
 759     }
 760   }
 761   return Standard_False;
 762 }
 763
 764 //=======================================================================
 765 //function : IsMergingPossible
 766 //purpose  : Checks if merging of two edges is possible
 767 //=======================================================================
 768
 769 static Standard_Boolean IsMergingPossible(const TopoDS_Edge& edge1, const TopoDS_Edge& edge2,
 770                                           double theAngTol, double theLinTol,
 771                                           const TopTools_MapOfShape& AvoidEdgeVrt, const bool theLineDirectionOk,
 772                                           const gp_Pnt& theFirstPoint, const gp_Vec& theDirectionVec)
 773 {
 774   TopoDS_Vertex CV = TopExp::LastVertex(edge1, Standard_True);
 775   if (CV.IsNull() || AvoidEdgeVrt.Contains(CV))
 776     return Standard_False;
 777
 778   BRepAdaptor_Curve ade1(edge1);
 779   BRepAdaptor_Curve ade2(edge2);
 780
 781   GeomAbs_CurveType t1 = ade1.GetType();
 782   GeomAbs_CurveType t2 = ade2.GetType();
 783
 784   if( t1 == GeomAbs_Circle && t2 == GeomAbs_Circle)
 785   {
 786     if (ade1.Circle().Location().Distance(ade2.Circle().Location()) > Precision::Confusion())
 787       return Standard_False;
 788   }
 789
 790   if( ( (t1 != GeomAbs_BezierCurve && t1 != GeomAbs_BSplineCurve) ||
 791       (t2 != GeomAbs_BezierCurve && t2 != GeomAbs_BSplineCurve)) && t1 != t2)
 792     return Standard_False;
 793
 794   gp_Vec Diff1, Diff2;
 795   gp_Pnt P1, P2;
 796   if (edge1.Orientation() == TopAbs_FORWARD)
 797     ade1.D1(ade1.LastParameter(), P1, Diff1);
 798   else
 799   {
 800     ade1.D1(ade1.FirstParameter(), P1, Diff1);
 801     Diff1 = -Diff1;
 802   }
 803
 804   if (edge2.Orientation() == TopAbs_FORWARD)
 805     ade2.D1(ade2.FirstParameter(), P2, Diff2);
 806   else
 807   {
 808     ade2.D1(ade2.LastParameter(), P2, Diff2);
 809     Diff2 = -Diff2;
 810   }
 811
 812   if (Diff1.Angle(Diff2) > theAngTol)
 813     return Standard_False;
 814
 815   if (theLineDirectionOk && t2 == GeomAbs_Line)
 816   {
 817     // Check that the accumulated deflection does not exceed the linear tolerance
 818     Standard_Real aLast = (edge2.Orientation() == TopAbs_FORWARD) ?
 819       ade2.LastParameter() : ade2.FirstParameter();
 820     gp_Vec aCurV(theFirstPoint, ade2.Value(aLast));
 821     Standard_Real aDD = theDirectionVec.CrossSquareMagnitude(aCurV);
 822     if (aDD > theLinTol*theLinTol)
 823       return Standard_False;
 824
 825     // Check that the accumulated angle does not exceed the angular tolerance.
 826     // For symmetry, check the angle between vectors of:
 827     // - first edge and resulting curve, and
 828     // - the last edge and resulting curve.
 829     if (theDirectionVec.Angle(aCurV) > theAngTol || Diff2.Angle(aCurV) > theAngTol)
 830       return Standard_False;
 831   }
 832
 833   return Standard_True;
 834 }
 835
 836 //=======================================================================
 837 //function : GetLineEdgePoints
 838 //purpose  :
 839 //=======================================================================
 840 static Standard_Boolean GetLineEdgePoints(const TopoDS_Edge& theInpEdge, gp_Pnt& theFirstPoint, gp_Vec& theDirectionVec)
 841 {
 842   double f, l;
 843   Handle(Geom_Curve) aCur = BRep_Tool::Curve(theInpEdge, f, l);
 844   if(aCur.IsNull())
 845     return Standard_False;
 846
 847   Handle(Geom_TrimmedCurve) aTC = Handle(Geom_TrimmedCurve)::DownCast(aCur);
 848   if (!aTC.IsNull())
 849     aCur = aTC->BasisCurve();
 850
 851   if (aCur->DynamicType() != STANDARD_TYPE(Geom_Line))
 852     return Standard_False;
 853
 854   if (theInpEdge.Orientation() == TopAbs_REVERSED) {
 855     Standard_Real tmp = f;
 856     f = l;
 857     l = tmp;
 858   }
 859   theFirstPoint = aCur->Value(f);
 860   gp_Pnt aLP = aCur->Value(l);
 861   theDirectionVec = aLP.XYZ().Subtracted(theFirstPoint.XYZ());
 862   theDirectionVec.Normalize();
 863   return Standard_True;
 864 }
 865
 866 //=======================================================================
 867 //function : GenerateSubSeq
 868 //purpose  : Generates sub-sequences of edges from sequence of edges
 869 //Edges from each subsequences can be merged into the one edge
 870 //=======================================================================
 871
 872 static void GenerateSubSeq (const TopTools_SequenceOfShape& anInpEdgeSeq,
 873                             NCollection_Sequence<SubSequenceOfEdges>& SeqOfSubSeqOfEdges,
 874                             Standard_Boolean IsClosed, double theAngTol, double theLinTol,
 875                             const TopTools_MapOfShape& AvoidEdgeVrt)
 876 {
 877   Standard_Boolean isOk = Standard_False;
 878   TopoDS_Edge edge1, edge2;
 879
 880   SubSequenceOfEdges SubSeq;
 881   TopoDS_Edge RefEdge = TopoDS::Edge(anInpEdgeSeq(1));
 882   SubSeq.SeqsEdges.Append(RefEdge);
 883   SeqOfSubSeqOfEdges.Append(SubSeq);
 884
 885   gp_Pnt aFirstPoint;
 886   gp_Vec aDirectionVec;
 887   Standard_Boolean isLineDirectionOk = GetLineEdgePoints(RefEdge, aFirstPoint, aDirectionVec);
 888
 889   for (int i = 1; i < anInpEdgeSeq.Length(); i++)
 890   {
 891     edge1 = TopoDS::Edge(anInpEdgeSeq(i));
 892     edge2 = TopoDS::Edge(anInpEdgeSeq(i+1));
 893     isOk = IsMergingPossible(edge1, edge2, theAngTol, theLinTol, AvoidEdgeVrt, isLineDirectionOk, aFirstPoint, aDirectionVec);
 894     if (!isOk)
 895     {
 896       SubSequenceOfEdges aSubSeq;
 897       aSubSeq.SeqsEdges.Append(edge2);
 898       SeqOfSubSeqOfEdges.Append(aSubSeq);
 899       isLineDirectionOk = GetLineEdgePoints(edge2, aFirstPoint, aDirectionVec);
 900     }
 901     else
 902       SeqOfSubSeqOfEdges.ChangeLast().SeqsEdges.Append(edge2);
 903   }
 904   /// check first and last chain segments
 905   if (IsClosed && SeqOfSubSeqOfEdges.Length() > 1)
 906   {
 907     edge1 = TopoDS::Edge(anInpEdgeSeq.Last());
 908     edge2 = TopoDS::Edge(anInpEdgeSeq.First());
 909     if (IsMergingPossible(edge1, edge2, theAngTol, theLinTol, AvoidEdgeVrt, Standard_False, aFirstPoint, aDirectionVec))
 910     {
 911       SeqOfSubSeqOfEdges.ChangeLast().SeqsEdges.Append(SeqOfSubSeqOfEdges.ChangeFirst().SeqsEdges);
 912       SeqOfSubSeqOfEdges.Remove(1);
 913     }
 914   }
 915 }
 916
 917 //=======================================================================
 918 //function : MergeEdges
 919 //purpose  : auxilary
 920 //=======================================================================
 921 static Standard_Boolean MergeEdges(TopTools_SequenceOfShape& SeqEdges,
 922                                    const Standard_Real theAngTol,
 923                                    const Standard_Real theLinTol,
 924                                    const Standard_Boolean ConcatBSplines,
 925                                    const Standard_Boolean isSafeInputMode,
 926                                    Handle(ShapeBuild_ReShape)& theContext,
 927                                    NCollection_Sequence<SubSequenceOfEdges>& SeqOfSubSeqOfEdges,
 928                                    const TopTools_MapOfShape& NonMergVrt)
 929 {
 930   // skip degenerated edges, and forbid merging through them
 931   TopTools_IndexedDataMapOfShapeListOfShape aMapVE;
 932   Standard_Integer j;
 933   TopTools_MapOfShape VerticesToAvoid;
 934   for (j = 1; j <= SeqEdges.Length(); j++)
 935   {
 936     TopoDS_Edge anEdge = TopoDS::Edge(SeqEdges(j));
 937     if (BRep_Tool::Degenerated(anEdge))
 938     {
 939       TopoDS_Vertex V1, V2;
 940       TopExp::Vertices(anEdge, V1, V2);
 941       VerticesToAvoid.Add(V1);
 942       VerticesToAvoid.Add(V2);
 943       SeqEdges.Remove(j--);
 944     }
 945     else
 946     {
 947       // fill in the map V-E
 948       for (TopoDS_Iterator it(anEdge.Oriented(TopAbs_FORWARD)); it.More(); it.Next())
 949       {
 950         TopoDS_Shape aV = it.Value();
 951         if (aV.Orientation() == TopAbs_FORWARD || aV.Orientation() == TopAbs_REVERSED)
 952         {
 953           if (!aMapVE.Contains(aV))
 954             aMapVE.Add(aV, TopTools_ListOfShape());
 955           aMapVE.ChangeFromKey(aV).Append(anEdge);
 956         }
 957       }
 958     }
 959   }
 960   VerticesToAvoid.Unite(NonMergVrt);
 961
 962   // do loop while there are unused edges
 963   TopTools_MapOfShape aUsedEdges;
 964   for (;;)
 965   {
 966     TopoDS_Edge edge;
 967     for(j=1; j <= SeqEdges.Length(); j++)
 968     {
 969       edge = TopoDS::Edge(SeqEdges.Value(j));
 970       if (!aUsedEdges.Contains(edge))
 971         break;
 972     }
 973     if (j > SeqEdges.Length())
 974       break; // all edges have been used
 975
 976     // make chain for unite
 977     TopTools_SequenceOfShape aChain;
 978     aChain.Append(edge);
 979     aUsedEdges.Add(edge);
 980     TopoDS_Vertex V[2];
 981     TopExp::Vertices(edge, V[0], V[1], Standard_True);
 982
 983     // connect more edges to the chain in both directions
 984     for (j = 0; j < 2; j++)
 985     {
 986       Standard_Boolean isAdded = Standard_True;
 987       while (isAdded)
 988       {
 989         isAdded = Standard_False;
 990         if (V[j].IsNull())
 991           break;
 992         const TopTools_ListOfShape& aLE = aMapVE.FindFromKey(V[j]);
 993         for (TopTools_ListIteratorOfListOfShape itL(aLE); itL.More(); itL.Next())
 994         {
 995           edge = TopoDS::Edge(itL.Value());
 996           if (!aUsedEdges.Contains(edge))
 997           {
 998             TopoDS_Vertex V2[2];
 999             TopExp::Vertices(edge, V2[0], V2[1], Standard_True);
1000             // the neighboring edge must have V[j] reversed and located on the opposite end
1001             if (V2[1 - j].IsEqual(V[j].Reversed()))
1002             {
1003               if (j == 0)
1004                 aChain.Prepend(edge);
1005               else
1006                 aChain.Append(edge);
1007               aUsedEdges.Add(edge);
1008               V[j] = V2[j];
1009               isAdded = Standard_True;
1010               break;
1011             }
1012           }
1013         }
1014       }
1015     }
1016
1017     if (aChain.Length() < 2)
1018       continue;
1019
1020     Standard_Boolean IsClosed = Standard_False;
1021     if (V[0].IsSame ( V[1] ))
1022       IsClosed = Standard_True;
1023
1024     // split chain by vertices at which merging is not possible
1025     NCollection_Sequence<SubSequenceOfEdges> aOneSeq;
1026     GenerateSubSeq(aChain, aOneSeq, IsClosed, theAngTol, theLinTol, VerticesToAvoid);
1027
1028     // put sub-chains in the result
1029     SeqOfSubSeqOfEdges.Append(aOneSeq);
1030   }
1031
1032   for (int i = 1; i <= SeqOfSubSeqOfEdges.Length(); i++)
1033   {
1034     TopoDS_Edge UE;
1035     if (SeqOfSubSeqOfEdges(i).SeqsEdges.Length() < 2)
1036       continue;
1037     if (MergeSubSeq(SeqOfSubSeqOfEdges(i).SeqsEdges, UE, theAngTol,
1038                     ConcatBSplines, isSafeInputMode, theContext))
1039       SeqOfSubSeqOfEdges(i).UnionEdges = UE;
1040   }
1041   return Standard_True;
1042 }
1043
1044 //=======================================================================
1045 //function : MergeSeq
1046 //purpose  : Tries to unify the sequence of edges with the set of
1047 //           another edges which lies on the same geometry
1048 //=======================================================================
1049 static Standard_Boolean MergeSeq (TopTools_SequenceOfShape& SeqEdges,
1050                                   const Standard_Real theAngTol,
1051                                   const Standard_Real theLinTol,
1052                                   const Standard_Boolean ConcatBSplines,
1053                                   const Standard_Boolean isSafeInputMode,
1054                                   Handle(ShapeBuild_ReShape)& theContext,
1055                                   const TopTools_MapOfShape& nonMergVert)
1056 {
1057   NCollection_Sequence<SubSequenceOfEdges> SeqOfSubsSeqOfEdges;
1058   if (MergeEdges(SeqEdges, theAngTol, theLinTol, ConcatBSplines, isSafeInputMode,
1059                  theContext, SeqOfSubsSeqOfEdges, nonMergVert))
1060   {
1061     for (Standard_Integer i = 1; i <= SeqOfSubsSeqOfEdges.Length(); i++ )
1062     {
1063       if (SeqOfSubsSeqOfEdges(i).UnionEdges.IsNull())
1064         continue;
1065
1066       theContext->Merge(SeqOfSubsSeqOfEdges(i).SeqsEdges,
1067         SeqOfSubsSeqOfEdges(i).UnionEdges);
1068     }
1069     return Standard_True;
1070   }
1071   return Standard_False;
1072 }
1073
1074 //=======================================================================
1075 //function : CheckSharedVertices
1076 //purpose  : Checks the sequence of edges on the presence of shared vertex
1077 //=======================================================================
1078
1079 static void CheckSharedVertices(const TopTools_SequenceOfShape& theSeqEdges,
1080                                 const TopTools_IndexedDataMapOfShapeListOfShape& theMapEdgesVertex,
1081                                 const TopTools_MapOfShape& theMapKeepShape,
1082                                 TopTools_MapOfShape& theShareVertMap)
1083 {
1084   ShapeAnalysis_Edge sae;
1085   TopTools_SequenceOfShape SeqVertexes;
1086   TopTools_MapOfShape MapVertexes;
1087   for (Standard_Integer k = 1; k <= theSeqEdges.Length(); k++ )
1088   {
1089     TopoDS_Vertex aV1 = sae.FirstVertex(TopoDS::Edge(theSeqEdges(k)));
1090     TopoDS_Vertex aV2 = sae.LastVertex(TopoDS::Edge(theSeqEdges(k)));
1091     if (!MapVertexes.Add(aV1))
1092       SeqVertexes.Append(aV1);
1093     if (!MapVertexes.Add(aV2))
1094       SeqVertexes.Append(aV2);
1095   }
1096
1097   for (Standard_Integer k = 1; k <= SeqVertexes.Length()/* && !IsSharedVertexPresent*/; k++ )
1098   {
1099     const TopTools_ListOfShape& ListEdgesV1 = theMapEdgesVertex.FindFromKey(SeqVertexes(k));
1100     if (ListEdgesV1.Extent() > 2 || theMapKeepShape.Contains(SeqVertexes(k)))
1101       theShareVertMap.Add(SeqVertexes(k));
1102   }
1103   //return theShareVertMap.IsEmpty() ? false : true;
1104 }
1105
1106 //=======================================================================
1107 //function : ShapeUpgrade_UnifySameDomain
1108 //purpose  : Constructor
1109 //=======================================================================
1110
1111 ShapeUpgrade_UnifySameDomain::ShapeUpgrade_UnifySameDomain()
1112   : myLinTol(Precision::Confusion()),
1113     myAngTol(Precision::Angular()),
1114     myUnifyFaces(Standard_True),
1115     myUnifyEdges (Standard_True),
1116     myConcatBSplines (Standard_False),
1117     myAllowInternal (Standard_False),
1118     mySafeInputMode(Standard_True),
1119     myHistory(new BRepTools_History)
1120 {
1121   myContext = new ShapeBuild_ReShape;
1122 }
1123
1124 //=======================================================================
1125 //function : ShapeUpgrade_UnifySameDomain
1126 //purpose  : Constructor
1127 //=======================================================================
1128
1129 ShapeUpgrade_UnifySameDomain::ShapeUpgrade_UnifySameDomain(const TopoDS_Shape& aShape,
1130                                                            const Standard_Boolean UnifyEdges,
1131                                                            const Standard_Boolean UnifyFaces,
1132                                                            const Standard_Boolean ConcatBSplines)
1133   : myInitShape (aShape),
1134     myLinTol(Precision::Confusion()),
1135     myAngTol(Precision::Angular()),
1136     myUnifyFaces(UnifyFaces),
1137     myUnifyEdges (UnifyEdges),
1138     myConcatBSplines (ConcatBSplines),
1139     myAllowInternal (Standard_False),
1140     mySafeInputMode (Standard_True),
1141     myShape (aShape),
1142     myHistory(new BRepTools_History)
1143 {
1144   myContext = new ShapeBuild_ReShape;
1145 }
1146
1147 //=======================================================================
1148 //function : Initialize
1149 //purpose  :
1150 //=======================================================================
1151
1152 void ShapeUpgrade_UnifySameDomain::Initialize(const TopoDS_Shape& aShape,
1153                                               const Standard_Boolean UnifyEdges,
1154                                               const Standard_Boolean UnifyFaces,
1155                                               const Standard_Boolean ConcatBSplines)
1156 {
1157   myInitShape = aShape;
1158   myShape = aShape;
1159   myUnifyEdges = UnifyEdges;
1160   myUnifyFaces = UnifyFaces;
1161   myConcatBSplines = ConcatBSplines;
1162
1163   myContext->Clear();
1164   myKeepShapes.Clear();
1165   myHistory->Clear();
1166 }
1167
1168 //=======================================================================
1169 //function : AllowInternalEdges
1170 //purpose  :
1171 //=======================================================================
1172
1173 void ShapeUpgrade_UnifySameDomain::AllowInternalEdges (const Standard_Boolean theValue)
1174 {
1175   myAllowInternal = theValue;
1176 }
1177
1178 //=======================================================================
1179 //function : SetSafeInputMode
1180 //purpose  :
1181 //=======================================================================
1182
1183 void ShapeUpgrade_UnifySameDomain::SetSafeInputMode(Standard_Boolean theValue)
1184 {
1185   mySafeInputMode = theValue;
1186 }
1187
1188 //=======================================================================
1189 //function : KeepShape
1190 //purpose  :
1191 //=======================================================================
1192
1193 void ShapeUpgrade_UnifySameDomain::KeepShape(const TopoDS_Shape& theShape)
1194 {
1195   if (theShape.ShapeType() == TopAbs_EDGE || theShape.ShapeType() == TopAbs_VERTEX)
1196     myKeepShapes.Add(theShape);
1197 }
1198
1199 //=======================================================================
1200 //function : KeepShapes
1201 //purpose  :
1202 //=======================================================================
1203
1204 void ShapeUpgrade_UnifySameDomain::KeepShapes(const TopTools_MapOfShape& theShapes)
1205 {
1206   for (TopTools_MapIteratorOfMapOfShape it(theShapes); it.More(); it.Next()) {
1207     if (it.Value().ShapeType() == TopAbs_EDGE || it.Value().ShapeType() == TopAbs_VERTEX)
1208       myKeepShapes.Add(it.Value());
1209   }
1210 }
1211
1212 //=======================================================================
1213 //function : UnifyFaces
1214 //purpose  :
1215 //=======================================================================
1216
1217 void ShapeUpgrade_UnifySameDomain::UnifyFaces()
1218 {
1219   // creating map of edge faces for the whole shape
1220   TopTools_IndexedDataMapOfShapeListOfShape aGMapEdgeFaces;
1221   TopExp::MapShapesAndAncestors(myShape, TopAbs_EDGE, TopAbs_FACE, aGMapEdgeFaces);
1222
1223   // unify faces in each shell separately
1224   TopExp_Explorer exps;
1225   for (exps.Init(myShape, TopAbs_SHELL); exps.More(); exps.Next())
1226     IntUnifyFaces(exps.Current(), aGMapEdgeFaces);
1227
1228   // gather all faces out of shells in one compound and unify them at once
1229   BRep_Builder aBB;
1230   TopoDS_Compound aCmp;
1231   aBB.MakeCompound(aCmp);
1232   Standard_Integer nbf = 0;
1233   for (exps.Init(myShape, TopAbs_FACE, TopAbs_SHELL); exps.More(); exps.Next(), nbf++)
1234     aBB.Add(aCmp, exps.Current());
1235
1236   if (nbf > 0)
1237     IntUnifyFaces(aCmp, aGMapEdgeFaces);
1238
1239   myShape = myContext->Apply(myShape);
1240 }
1241
1242 //=======================================================================
1243 //function : SetFixWireModes
1244 //purpose  :
1245 //=======================================================================
1246
1247 static void SetFixWireModes(ShapeFix_Face& theSff)
1248 {
1249   Handle(ShapeFix_Wire) aFixWire = theSff.FixWireTool();
1250   aFixWire->FixSelfIntersectionMode() = 0;
1251   aFixWire->FixNonAdjacentIntersectingEdgesMode() = 0;
1252   aFixWire->FixLackingMode() = 0;
1253   aFixWire->FixNotchedEdgesMode() = 0;
1254   aFixWire->ModifyTopologyMode() = Standard_False;
1255   aFixWire->ModifyRemoveLoopMode() = 0;
1256   aFixWire->FixGapsByRangesMode() = Standard_False;
1257   aFixWire->FixSmallMode() = 0;
1258 }
1259
1260 //=======================================================================
1261 //function : IntUnifyFaces
1262 //purpose  :
1263 //=======================================================================
1264
1265 void ShapeUpgrade_UnifySameDomain::IntUnifyFaces(const TopoDS_Shape& theInpShape,
1266    TopTools_IndexedDataMapOfShapeListOfShape& theGMapEdgeFaces)
1267 {
1268   // creating map of edge faces for the shape
1269   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgeFaces;
1270   TopExp::MapShapesAndAncestors(theInpShape, TopAbs_EDGE, TopAbs_FACE, aMapEdgeFaces);
1271
1272   // map of processed shapes
1273   TopTools_MapOfShape aProcessed;
1274
1275   // processing each face
1276   TopExp_Explorer exp;
1277   for (exp.Init(theInpShape, TopAbs_FACE); exp.More(); exp.Next()) {
1278     const TopoDS_Face& aFaceOriginal = TopoDS::Face(exp.Current());
1279     TopoDS_Face aFace = TopoDS::Face(aFaceOriginal.Oriented(TopAbs_FORWARD));
1280
1281     if (aProcessed.Contains(aFace))
1282       continue;
1283
1284     // Boundary edges for the new face
1285     TopTools_SequenceOfShape edges;
1286
1287     Standard_Integer dummy;
1288     AddOrdinaryEdges(edges, aFace, dummy);
1289
1290     // Faces to get unified with the current faces
1291     TopTools_SequenceOfShape faces;
1292
1293     // Add the current face for unification
1294     faces.Append(aFace);
1295
1296     // surface and location to construct result
1297     TopLoc_Location aBaseLocation;
1298     Handle(Geom_Surface) aBaseSurface = BRep_Tool::Surface(aFace,aBaseLocation);
1299     aBaseSurface = ClearRts(aBaseSurface);
1300
1301     // find adjacent faces to union
1302     Standard_Integer i;
1303     for (i = 1; i <= edges.Length(); i++) {
1304       TopoDS_Edge edge = TopoDS::Edge(edges(i));
1305       if (BRep_Tool::Degenerated(edge))
1306         continue;
1307
1308       // get connectivity of the edge in the global shape
1309       const TopTools_ListOfShape& aGList = theGMapEdgeFaces.FindFromKey(edge);
1310       if (!myAllowInternal && (aGList.Extent() != 2 || myKeepShapes.Contains(edge))) {
1311         // non manifold case is not processed unless myAllowInternal
1312         continue;
1313       }
1314       //
1315       // Get the faces connected through the edge in the current shape
1316       const TopTools_ListOfShape& aList = aMapEdgeFaces.FindFromKey(edge);
1317       if (aList.Extent() < 2) {
1318         continue;
1319       }
1320
1321       // for a planar face create and store pcurve of edge on face
1322       // to speed up all operations
1323       if (!mySafeInputMode && aBaseSurface->IsKind(STANDARD_TYPE(Geom_Plane)))
1324         BRepLib::BuildPCurveForEdgeOnPlane(edge, aFace);
1325
1326       // get normal of the face to compare it with normals of other faces
1327       gp_Dir aDN1;
1328       //
1329       // take intermediate point on edge to compute the normal
1330       Standard_Real f, l;
1331       BRep_Tool::Range(edge, f, l);
1332       Standard_Real aTMid = (f + l) * .5;
1333       //
1334       Standard_Boolean bCheckNormals = GetNormalToSurface(aFaceOriginal, edge, aTMid, aDN1);
1335       //
1336       // Process the faces
1337       TopTools_ListIteratorOfListOfShape anIter(aList);
1338       for (; anIter.More(); anIter.Next()) {
1339         const TopoDS_Face& aCheckedFaceOriginal = TopoDS::Face(anIter.Value());
1340         TopoDS_Face anCheckedFace = TopoDS::Face(aCheckedFaceOriginal.Oriented(TopAbs_FORWARD));
1341         if (anCheckedFace.IsSame(aFace))
1342           continue;
1343
1344         if (aProcessed.Contains(anCheckedFace))
1345           continue;
1346
1347         if (bCheckNormals) {
1348           // get normal of checked face using the same parameter on edge
1349           gp_Dir aDN2;
1350           if (GetNormalToSurface(aCheckedFaceOriginal, edge, aTMid, aDN2)) {
1351             // and check if the adjacent faces are having approximately same normals
1352             Standard_Real anAngle = aDN1.Angle(aDN2);
1353             if (anAngle > myAngTol) {
1354               continue;
1355             }
1356           }
1357         }
1358         //
1359         if (IsSameDomain(aFace,anCheckedFace, myLinTol, myAngTol)) {
1360
1361           if (AddOrdinaryEdges(edges,anCheckedFace,dummy)) {
1362             // sequence edges is modified
1363             i = dummy;
1364           }
1365
1366           faces.Append(anCheckedFace);
1367           aProcessed.Add(anCheckedFace);
1368           break;
1369         }
1370       }
1371     }
1372
1373     if (faces.Length() > 1) {
1374       // fill in the connectivity map for selected faces
1375       TopTools_IndexedDataMapOfShapeListOfShape aMapEF;
1376       for (i = 1; i <= faces.Length(); i++) {
1377         TopExp::MapShapesAndAncestors(faces(i), TopAbs_EDGE, TopAbs_FACE, aMapEF);
1378       }
1379       // Collect keep edges and multi-connected edges, i.e. edges that are internal to
1380       // the set of selected faces and have connections to other faces.
1381       TopTools_ListOfShape aKeepEdges;
1382       for (i = 1; i <= aMapEF.Extent(); i++) {
1383         const TopTools_ListOfShape& aLF = aMapEF(i);
1384         if (aLF.Extent() == 2) {
1385           const TopoDS_Shape& aE = aMapEF.FindKey(i);
1386           const TopTools_ListOfShape& aGLF = theGMapEdgeFaces.FindFromKey(aE);
1387           if (aGLF.Extent() > 2 || myKeepShapes.Contains(aE)) {
1388             aKeepEdges.Append(aE);
1389           }
1390         }
1391       }
1392       if (!aKeepEdges.IsEmpty()) {
1393         if  (!myAllowInternal) {
1394           // Remove from the selection the faces which have no other connect edges
1395           // and contain multi-connected edges and/or keep edges.
1396           TopTools_MapOfShape anAvoidFaces;
1397           TopTools_ListIteratorOfListOfShape it(aKeepEdges);
1398           for (; it.More(); it.Next()) {
1399             const TopoDS_Shape& aE = it.Value();
1400             const TopTools_ListOfShape& aLF = aMapEF.FindFromKey(aE);
1401             anAvoidFaces.Add(aLF.First());
1402             anAvoidFaces.Add(aLF.Last());
1403           }
1404           for (i = 1; i <= faces.Length(); i++) {
1405             if (anAvoidFaces.Contains(faces(i))) {
1406               // update the boundaries of merged area, for that
1407               // remove from 'edges' the edges of this face and add to 'edges'
1408               // the edges of this face that were not present in 'edges' before
1409               Standard_Boolean hasConnectAnotherFaces = Standard_False;
1410               TopExp_Explorer ex(faces(i), TopAbs_EDGE);
1411               for (; ex.More() && !hasConnectAnotherFaces; ex.Next()) {
1412                 TopoDS_Shape aE = ex.Current();
1413                 const TopTools_ListOfShape& aLF = aMapEF.FindFromKey(aE);
1414                 if (aLF.Extent() > 1) {
1415                   for (it.Init(aLF); it.More() && !hasConnectAnotherFaces; it.Next()) {
1416                     if (!anAvoidFaces.Contains(it.Value()))
1417                       hasConnectAnotherFaces = Standard_True;
1418                   }
1419                 }
1420               }
1421               if (!hasConnectAnotherFaces) {
1422                 AddOrdinaryEdges(edges, faces(i), dummy);
1423                 faces.Remove(i);
1424                 i--;
1425               }
1426             }
1427           }
1428           // check if the faces with keep edges contained in
1429           // already updated the boundaries of merged area
1430           if (!faces.IsEmpty()) {
1431             TopTools_MapOfShape aMapFaces;
1432             for (i = 1; i <= faces.Length(); i++) {
1433               aMapFaces.Add(faces(i));
1434             }
1435             for (it.Init(aKeepEdges); it.More(); it.Next()) {
1436               const TopoDS_Shape& aE = it.Value();
1437               const TopTools_ListOfShape& aLF = aMapEF.FindFromKey(aE);
1438               if (aLF.Extent() < 2)
1439                 continue;
1440               if (aMapFaces.Contains(aLF.First()) &&
1441                   aMapFaces.Contains(aLF.Last())) {
1442                 for (i = 1; i <= faces.Length(); i++) {
1443                   if (faces(i).IsEqual(aLF.First()) ||
1444                       faces(i).IsEqual(aLF.Last())) {
1445                     AddOrdinaryEdges(edges, faces(i), dummy);
1446                     faces.Remove(i);
1447                     i--;
1448                   }
1449                 }
1450               }
1451             }
1452           }
1453         }
1454         else {
1455           // add multi-connected and keep edges as internal in new face
1456           TopTools_ListIteratorOfListOfShape it(aKeepEdges);
1457           for (; it.More(); it.Next()) {
1458             const TopoDS_Shape& aE = it.Value();
1459             edges.Append(aE.Oriented(TopAbs_INTERNAL));
1460           }
1461         }
1462       }
1463     }
1464
1465     // all faces collected in the sequence. Perform union of faces
1466     if (faces.Length() > 1) {
1467       TopoDS_Face aResult;
1468       BRep_Builder B;
1469       B.MakeFace(aResult,aBaseSurface,aBaseLocation,0);
1470       Standard_Integer nbWires = 0;
1471
1472       TopoDS_Face tmpF = TopoDS::Face(faces(1).Oriented(TopAbs_FORWARD));
1473
1474       // connecting wires
1475       while (edges.Length()>0) {
1476
1477         Standard_Boolean isEdge3d = Standard_False;
1478         nbWires++;
1479         TopTools_MapOfShape aVertices;
1480         TopoDS_Wire aWire;
1481         B.MakeWire(aWire);
1482
1483         TopoDS_Edge anEdge = TopoDS::Edge(edges(1));
1484         edges.Remove(1);
1485         // collect internal edges in separate wires
1486         Standard_Boolean isInternal = (anEdge.Orientation() == TopAbs_INTERNAL);
1487
1488         isEdge3d |= !BRep_Tool::Degenerated(anEdge);
1489         B.Add(aWire,anEdge);
1490         TopoDS_Vertex V1,V2;
1491         TopExp::Vertices(anEdge,V1,V2);
1492         aVertices.Add(V1);
1493         aVertices.Add(V2);
1494
1495         Standard_Boolean isNewFound = Standard_False;
1496         do {
1497           isNewFound = Standard_False;
1498           for(Standard_Integer j = 1; j <= edges.Length(); j++) {
1499             anEdge = TopoDS::Edge(edges(j));
1500             // check if the current edge orientation corresponds to the first one
1501             Standard_Boolean isCurrInternal = (anEdge.Orientation() == TopAbs_INTERNAL);
1502             if (isCurrInternal != isInternal)
1503               continue;
1504             TopExp::Vertices(anEdge,V1,V2);
1505             if(aVertices.Contains(V1) || aVertices.Contains(V2)) {
1506               isEdge3d |= !BRep_Tool::Degenerated(anEdge);
1507               aVertices.Add(V1);
1508               aVertices.Add(V2);
1509               B.Add(aWire,anEdge);
1510               edges.Remove(j);
1511               j--;
1512               isNewFound = Standard_True;
1513             }
1514           }
1515         } while (isNewFound);
1516
1517         // sorting any type of edges
1518         aWire.Closed (BRep_Tool::IsClosed (aWire));
1519
1520         Handle(ShapeFix_Wire) sfw = new ShapeFix_Wire(aWire,tmpF,Precision::Confusion());
1521         if (mySafeInputMode)
1522           sfw->SetContext(myContext);
1523         sfw->FixReorder();
1524         Standard_Boolean isDegRemoved = Standard_False;
1525         if(!sfw->StatusReorder ( ShapeExtend_FAIL )) {
1526           // clear degenerated edges if at least one with 3d curve exist
1527           if(isEdge3d) {
1528             Handle(ShapeExtend_WireData) sewd = sfw->WireData();
1529             for(Standard_Integer j = 1; j<=sewd->NbEdges();j++) {
1530               TopoDS_Edge E = sewd->Edge(j);
1531               if(BRep_Tool::Degenerated(E)) {
1532                 sewd->Remove(j);
1533                 isDegRemoved = Standard_True;
1534                 j--;
1535               }
1536             }
1537           }
1538           sfw->FixShifted();
1539           if(isDegRemoved)
1540             sfw->FixDegenerated();
1541         }
1542         aWire = sfw->Wire();
1543
1544         // add resulting wire
1545         if(isEdge3d) {
1546           B.Add(aResult,aWire);
1547         }
1548         else  {
1549           // sorting edges
1550           Handle(ShapeExtend_WireData) sbwd = sfw->WireData();
1551           Standard_Integer nbEdges = sbwd->NbEdges();
1552           // sort degenerated edges and create one edge instead of several ones
1553           ShapeAnalysis_WireOrder sawo(Standard_False, 0);
1554           ShapeAnalysis_Edge sae;
1555           Standard_Integer aLastEdge = nbEdges;
1556           for(Standard_Integer j = 1; j <= nbEdges; j++) {
1557             Standard_Real f,l;
1558             //smh protection on NULL pcurve
1559             Handle(Geom2d_Curve) c2d;
1560             if(!sae.PCurve(sbwd->Edge(j),tmpF,c2d,f,l)) {
1561               aLastEdge--;
1562               continue;
1563             }
1564             sawo.Add(c2d->Value(f).XY(),c2d->Value(l).XY());
1565           }
1566           if (sawo.NbEdges() == 0)
1567             continue;
1568           sawo.Perform();
1569
1570           // constructind one degenerative edge
1571           gp_XY aStart, anEnd, tmp;
1572           Standard_Integer nbFirst = sawo.Ordered(1);
1573           TopoDS_Edge anOrigE = TopoDS::Edge(sbwd->Edge(nbFirst).Oriented(TopAbs_FORWARD));
1574           ShapeBuild_Edge sbe;
1575           TopoDS_Vertex aDummyV;
1576           TopoDS_Edge E = sbe.CopyReplaceVertices(anOrigE,aDummyV,aDummyV);
1577           sawo.XY(nbFirst,aStart,tmp);
1578           sawo.XY(sawo.Ordered(aLastEdge),tmp,anEnd);
1579
1580           gp_XY aVec = anEnd-aStart;
1581           Handle(Geom2d_Line) aLine = new Geom2d_Line(aStart,gp_Dir2d(anEnd-aStart));
1582
1583           B.UpdateEdge(E,aLine,tmpF,0.);
1584           B.Range(E,tmpF,0.,aVec.Modulus());
1585           Handle(Geom_Curve) C3d;
1586           B.UpdateEdge(E,C3d,0.);
1587           B.Degenerated(E,Standard_True);
1588           TopoDS_Wire aW;
1589           B.MakeWire(aW);
1590           B.Add(aW,E);
1591           aW.Closed (Standard_True);
1592           B.Add(aResult,aW);
1593         }
1594       }
1595
1596       ShapeFix_Face sff (aResult);
1597       //Initializing by tolerances
1598       sff.SetPrecision(Precision::Confusion());
1599       sff.SetMinTolerance(Precision::Confusion());
1600       sff.SetMaxTolerance(1.);
1601       //Setting modes
1602       SetFixWireModes(sff);
1603       if (mySafeInputMode)
1604         sff.SetContext(myContext);
1605       // Applying the fixes
1606       sff.Perform();
1607       if(!sff.Status(ShapeExtend_FAIL))
1608       {
1609         // perform substitution of faces
1610         aResult = sff.Face();
1611         myContext->Merge(faces, aResult);
1612       }
1613     }
1614   } // end processing each face
1615 }
1616
1617 //=======================================================================
1618 //function : UnifyEdges
1619 //purpose  :
1620 //=======================================================================
1621 void ShapeUpgrade_UnifySameDomain::UnifyEdges()
1622 {
1623   TopoDS_Shape aRes = myContext->Apply(myShape);
1624   // creating map of edge faces
1625   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgeFaces;
1626   TopExp::MapShapesAndAncestors(aRes, TopAbs_EDGE, TopAbs_FACE, aMapEdgeFaces);
1627   // creating map of vertex edges
1628   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgesVertex;
1629   TopExp::MapShapesAndUniqueAncestors(aRes, TopAbs_VERTEX, TopAbs_EDGE, aMapEdgesVertex);
1630
1631   if (mySafeInputMode)
1632     UpdateMapOfShapes(myKeepShapes, myContext);
1633
1634   // Sequence of the edges of the shape
1635   TopTools_SequenceOfShape aSeqEdges;
1636   const Standard_Integer aNbE = aMapEdgeFaces.Extent();
1637   for (Standard_Integer i = 1; i <= aNbE; ++i)
1638     aSeqEdges.Append(aMapEdgeFaces.FindKey(i));
1639
1640   // Prepare map of shared vertices (with the number of connected edges greater then 2)
1641   TopTools_MapOfShape aSharedVert;
1642   CheckSharedVertices(aSeqEdges, aMapEdgesVertex, myKeepShapes, aSharedVert);
1643   // Merge the edges avoiding removal of the shared vertices
1644   Standard_Boolean isMerged = MergeSeq(aSeqEdges, myAngTol, myLinTol, myConcatBSplines,
1645                                        mySafeInputMode, myContext, aSharedVert);
1646   // Collect faces to rebuild
1647   TopTools_IndexedMapOfShape aChangedFaces;
1648   if (isMerged)
1649   {
1650     for (Standard_Integer i = 1; i <= aNbE; ++i)
1651     {
1652       const TopoDS_Shape& aE = aMapEdgeFaces.FindKey(i);
1653       if (myContext->IsRecorded(aE))
1654       {
1655         TopTools_ListIteratorOfListOfShape it(aMapEdgeFaces(i));
1656         for (; it.More(); it.Next())
1657           aChangedFaces.Add(it.Value());
1658       }
1659     }
1660   }
1661
1662   // fix changed faces and replace them in the local context
1663   Standard_Real aPrec = Precision::Confusion();
1664   for (Standard_Integer i = 1; i <= aChangedFaces.Extent(); i++) {
1665     TopoDS_Face aFace = TopoDS::Face(myContext->Apply(aChangedFaces.FindKey(i)));
1666     if (aFace.IsNull())
1667       continue;
1668
1669     // for a planar face create and store pcurve of edge on face
1670     // to speed up all operations; but this is allowed only when non-safe mode in force
1671     if (!mySafeInputMode)
1672     {
1673       TopLoc_Location aLoc;
1674       Handle(Geom_Surface) aSurface = BRep_Tool::Surface(aFace, aLoc);
1675       aSurface = ClearRts(aSurface);
1676       if (aSurface->IsKind(STANDARD_TYPE(Geom_Plane)))
1677       {
1678         TopTools_ListOfShape aLE;
1679         for (TopExp_Explorer anEx(aFace, TopAbs_EDGE); anEx.More(); anEx.Next())
1680           aLE.Append(anEx.Current());
1681         BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFace);
1682       }
1683     }
1684
1685     ShapeFix_Face sff(aFace);
1686     if (mySafeInputMode)
1687       sff.SetContext(myContext);
1688     sff.SetPrecision(aPrec);
1689     sff.SetMinTolerance(aPrec);
1690     sff.SetMaxTolerance(Max(1., aPrec*1000.));
1691     sff.FixOrientationMode() = 0;
1692     sff.FixAddNaturalBoundMode() = 0;
1693     sff.FixIntersectingWiresMode() = 0;
1694     sff.FixLoopWiresMode() = 0;
1695     sff.FixSplitFaceMode() = 0;
1696     sff.FixPeriodicDegeneratedMode() = 0;
1697     SetFixWireModes(sff);
1698     sff.Perform();
1699     TopoDS_Shape aNewFace = sff.Face();
1700     myContext->Replace(aFace,aNewFace);
1701   }
1702
1703   if (aChangedFaces.Extent() > 0) {
1704     // fix changed shell and replace it in the local context
1705     TopoDS_Shape aRes1 = myContext->Apply(aRes);
1706     Standard_Boolean isChanged = Standard_False;
1707     TopExp_Explorer expsh;
1708     for (expsh.Init(aRes1, TopAbs_SHELL); expsh.More(); expsh.Next()) {
1709       TopoDS_Shell aShell = TopoDS::Shell(expsh.Current());
1710       Handle(ShapeFix_Shell) sfsh = new ShapeFix_Shell;
1711       sfsh->FixFaceOrientation(aShell);
1712       TopoDS_Shape aNewShell = sfsh->Shell();
1713       if (!aNewShell.IsSame(aShell)) {
1714         myContext->Replace(aShell, aNewShell);
1715         isChanged = Standard_True;
1716       }
1717     }
1718     if (isChanged)
1719       aRes1 = myContext->Apply(aRes1);
1720     myContext->Replace(myShape, aRes1);
1721   }
1722
1723   myShape = myContext->Apply(myShape);
1724 }
1725
1726 //=======================================================================
1727 //function : Build
1728 //purpose  : builds the resulting shape
1729 //=======================================================================
1730 void ShapeUpgrade_UnifySameDomain::Build()
1731 {
1732   if (myUnifyFaces)
1733     UnifyFaces();
1734   if (myUnifyEdges)
1735     UnifyEdges();
1736
1737   // Fill the history of modifications during the operation
1738   FillHistory();
1739 }
1740
1741 //=======================================================================
1742 //function : FillHistory
1743 //purpose  : Fill the history of modifications during the operation
1744 //=======================================================================
1745 void ShapeUpgrade_UnifySameDomain::FillHistory()
1746 {
1747   if (myHistory.IsNull())
1748     // History is not requested
1749     return;
1750
1751   // Only Vertices, Edges and Faces can be modified during unification.
1752   // Thus, only these kind of shapes should be checked.
1753
1754   // Get history from the context.
1755   // It contains all modifications of the operation. Some of these
1756   // modifications become not relevant and should be filtered.
1757   Handle(BRepTools_History) aCtxHistory = myContext->History();
1758
1759   // Explore the history of the context and fill
1760   // the history of UnifySameDomain algorithm
1761   Handle(BRepTools_History) aUSDHistory = new BRepTools_History();
1762
1763   // Map all Vertices, Edges, Faces and Solids in the input shape
1764   TopTools_IndexedMapOfShape aMapInputShape;
1765   TopExp::MapShapes(myInitShape, TopAbs_VERTEX, aMapInputShape);
1766   TopExp::MapShapes(myInitShape, TopAbs_EDGE  , aMapInputShape);
1767   TopExp::MapShapes(myInitShape, TopAbs_FACE  , aMapInputShape);
1768   TopExp::MapShapes(myInitShape, TopAbs_SOLID , aMapInputShape);
1769
1770   // Map all Vertices, Edges, Faces and Solids in the result shape
1771   TopTools_IndexedMapOfShape aMapResultShapes;
1772   TopExp::MapShapes(myShape, TopAbs_VERTEX, aMapResultShapes);
1773   TopExp::MapShapes(myShape, TopAbs_EDGE  , aMapResultShapes);
1774   TopExp::MapShapes(myShape, TopAbs_FACE  , aMapResultShapes);
1775   TopExp::MapShapes(myShape, TopAbs_SOLID , aMapResultShapes);
1776
1777   // Iterate on all input shapes and get their modifications
1778   Standard_Integer i, aNb = aMapInputShape.Extent();
1779   for (i = 1; i <= aNb; ++i)
1780   {
1781     const TopoDS_Shape& aS = aMapInputShape(i);
1782
1783     // Check the shape itself to be present in the result
1784     if (aMapResultShapes.Contains(aS))
1785     {
1786       // The shape is present in the result as is, thus has not been modified
1787       continue;
1788     }
1789
1790     // Check if the shape has been modified during the operation
1791     const TopTools_ListOfShape& aLSImages = aCtxHistory->Modified(aS);
1792     if (aLSImages.IsEmpty())
1793     {
1794       // The shape has not been modified and not present in the result,
1795       // thus it has been removed
1796       aUSDHistory->Remove(aS);
1797       continue;
1798     }
1799
1800     // Check the images of the shape to be present in the result
1801     Standard_Boolean bRemoved = Standard_True;
1802     TopTools_ListIteratorOfListOfShape aItLSIm(aLSImages);
1803     for (; aItLSIm.More(); aItLSIm.Next())
1804     {
1805       const TopoDS_Shape& aSIm = aItLSIm.Value();
1806       if (aMapResultShapes.Contains(aSIm))
1807       {
1808         if (!aSIm.IsSame(aS))
1809           // Image is found in the result, thus the shape has been modified
1810           aUSDHistory->AddModified(aS, aSIm);
1811         bRemoved = Standard_False;
1812       }
1813     }
1814
1815     if (bRemoved)
1816     {
1817       // No images are found in the result, thus the shape has been removed
1818       aUSDHistory->Remove(aS);
1819     }
1820   }
1821
1822   // Merge the history of the operation into global history
1823   myHistory->Merge(aUSDHistory);
1824 }