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 <BRepLib_MakeFace.hxx>
  22 #include <BRepTopAdaptor_TopolTool.hxx>
  23 #include <GC_MakeCircle.hxx>
  24 #include <Geom2d_Line.hxx>
  25 #include <GCE2d_MakeLine.hxx>
  26 #include <Geom2d_TrimmedCurve.hxx>
  27 #include <Geom2dConvert.hxx>
  28 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
  29 #include <Geom_BezierCurve.hxx>
  30 #include <Geom_BSplineCurve.hxx>
  31 #include <Geom_Circle.hxx>
  32 #include <Geom_CylindricalSurface.hxx>
  33 #include <Geom_ElementarySurface.hxx>
  34 #include <Geom_Line.hxx>
  35 #include <Geom_OffsetSurface.hxx>
  36 #include <Geom_Plane.hxx>
  37 #include <Geom_RectangularTrimmedSurface.hxx>
  38 #include <Geom_Surface.hxx>
  39 #include <Geom_SurfaceOfLinearExtrusion.hxx>
  40 #include <Geom_SurfaceOfRevolution.hxx>
  41 #include <Geom_SweptSurface.hxx>
  42 #include <Geom_TrimmedCurve.hxx>
  43 #include <GeomAdaptor_HSurface.hxx>
  44 #include <GeomConvert.hxx>
  45 #include <GeomConvert_CompCurveToBSplineCurve.hxx>
  46 #include <GeomLib_IsPlanarSurface.hxx>
  47 #include <gp_Cylinder.hxx>
  48 #include <gp_Dir.hxx>
  49 #include <gp_Lin.hxx>
  50 #include <IntPatch_ImpImpIntersection.hxx>
  51 #include <ShapeAnalysis_Edge.hxx>
  52 #include <ShapeAnalysis_WireOrder.hxx>
  53 #include <ShapeBuild_Edge.hxx>
  54 #include <ShapeBuild_ReShape.hxx>
  55 #include <ShapeFix_Edge.hxx>
  56 #include <ShapeFix_Face.hxx>
  57 #include <ShapeFix_Shell.hxx>
  58 #include <ShapeFix_Wire.hxx>
  59 #include <ShapeUpgrade_UnifySameDomain.hxx>
  60 #include <Standard_Type.hxx>
  61 #include <TColGeom2d_Array1OfBSplineCurve.hxx>
  62 #include <TColGeom2d_HArray1OfBSplineCurve.hxx>
  63 #include <TColGeom2d_SequenceOfBoundedCurve.hxx>
  64 #include <TColGeom2d_SequenceOfCurve.hxx>
  65 #include <TColGeom_Array1OfBSplineCurve.hxx>
  66 #include <TColGeom_HArray1OfBSplineCurve.hxx>
  67 #include <TColGeom_SequenceOfSurface.hxx>
  68 #include <TColStd_Array1OfReal.hxx>
  69 #include <TColStd_MapOfInteger.hxx>
  70 #include <TopExp.hxx>
  71 #include <TopExp_Explorer.hxx>
  72 #include <TopoDS.hxx>
  73 #include <TopoDS_Edge.hxx>
  74 #include <TopoDS_Face.hxx>
  75 #include <TopoDS_Shape.hxx>
  76 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  77 #include <TopTools_IndexedMapOfShape.hxx>
  78 #include <TopTools_ListIteratorOfListOfShape.hxx>
  79 #include <TopTools_MapOfShape.hxx>
  80 #include <TopTools_SequenceOfShape.hxx>
  81 #include <gp_Circ.hxx>
  82 #include <BRepAdaptor_Curve.hxx>
  83 #include <BRepAdaptor_Curve2d.hxx>
  84 #include <BRepAdaptor_Surface.hxx>
  85 #include <gp_Vec2d.hxx>
  86 #include <Extrema_ExtPS.hxx>
  87 #include <BRepTools.hxx>
  88 #include <BRepTopAdaptor_FClass2d.hxx>
  89
  90 IMPLEMENT_STANDARD_RTTIEXT(ShapeUpgrade_UnifySameDomain,Standard_Transient)
  91
  92 struct SubSequenceOfEdges
  93 {
  94   TopTools_SequenceOfShape SeqsEdges;
  95   TopoDS_Edge UnionEdges;
  96 };
  97
  98 static Standard_Real TrueValueOfOffset(const Standard_Real theValue,
  99                                        const Standard_Real thePeriod)
 100 {
 101   if (theValue > 0.)
 102     return thePeriod;
 103
 104   return (-thePeriod);
 105 }
 106
 107 //=======================================================================
 108 //function : UpdateBoundaries
 109 //purpose  : auxilary
 110 //=======================================================================
 111 static void UpdateBoundaries(const Handle(Geom2d_Curve)& thePCurve,
 112                              const Standard_Real         theFirst,
 113                              const Standard_Real         theLast,
 114                              Standard_Real& theUfirst,
 115                              Standard_Real& theUlast)
 116 {
 117   const Standard_Integer NbSamples = 4;
 118   Standard_Real Delta = (theLast - theFirst)/NbSamples;
 119
 120   for (Standard_Integer i = 0; i <= NbSamples; i++)
 121   {
 122     Standard_Real aParam = theFirst + i*Delta;
 123     gp_Pnt2d aPoint = thePCurve->Value(aParam);
 124     if (aPoint.X() < theUfirst)
 125       theUfirst = aPoint.X();
 126     if (aPoint.X() > theUlast)
 127       theUlast  = aPoint.X();
 128   }
 129 }
 130
 131 static void RemoveEdgeFromMap(const TopoDS_Edge& theEdge,
 132                               TopTools_IndexedDataMapOfShapeListOfShape& theVEmap)
 133 {
 134   TopoDS_Vertex VV [2];
 135   TopExp::Vertices(theEdge, VV[0], VV[1]);
 136   for (Standard_Integer i = 0; i < 2; i++)
 137   {
 138     TopTools_ListOfShape& Elist = theVEmap.ChangeFromKey(VV[i]);
 139     TopTools_ListIteratorOfListOfShape itl(Elist);
 140     while (itl.More())
 141     {
 142       const TopoDS_Shape& anEdge = itl.Value();
 143       if (anEdge.IsSame(theEdge))
 144         Elist.Remove(itl);
 145       else
 146         itl.Next();
 147     }
 148   }
 149 }
 150
 151 static Standard_Real ComputeMinEdgeSize(const TopTools_SequenceOfShape& theEdges,
 152                                         const TopoDS_Face&              theRefFace,
 153                                         TopTools_MapOfShape&            theEdgesMap)
 154 {
 155   Standard_Real MinSize = RealLast();
 156
 157   for (Standard_Integer ind = 1; ind <= theEdges.Length(); ind++)
 158   {
 159     const TopoDS_Edge& anEdge = TopoDS::Edge(theEdges(ind));
 160     theEdgesMap.Add(anEdge);
 161     TopoDS_Vertex V1, V2;
 162     TopExp::Vertices(anEdge, V1, V2);
 163     BRepAdaptor_Curve2d BAcurve2d(anEdge, theRefFace);
 164     gp_Pnt2d FirstP2d = BAcurve2d.Value(BAcurve2d.FirstParameter());
 165     gp_Pnt2d LastP2d  = BAcurve2d.Value(BAcurve2d.LastParameter());
 166     Standard_Real aSqDist;
 167     if (V1.IsSame(V2) &&
 168         !BRep_Tool::Degenerated(anEdge))
 169     {
 170       gp_Pnt2d MidP2d = BAcurve2d.Value((BAcurve2d.FirstParameter()+BAcurve2d.LastParameter())/2);
 171       aSqDist = FirstP2d.SquareDistance(MidP2d);
 172     }
 173     else
 174       aSqDist = FirstP2d.SquareDistance(LastP2d);
 175     if (aSqDist < MinSize)
 176       MinSize = aSqDist;
 177   }
 178   MinSize = Sqrt(MinSize);
 179   return MinSize;
 180 }
 181
 182 static void FindFaceWithMaxUbound(const TopTools_SequenceOfShape& theFaces,
 183                                   const TopoDS_Face&              theRefFace,
 184                                   const TopTools_MapOfShape&      theEdgesMap,
 185                                   Standard_Real&                  theUmax,
 186                                   Standard_Integer&               theIndFaceMax)
 187 {
 188   theUmax = RealFirst();
 189   theIndFaceMax = 0;
 190   for (Standard_Integer ii = 1; ii <= theFaces.Length(); ii++)
 191   {
 192     const TopoDS_Face& face_ii = TopoDS::Face(theFaces(ii));
 193     Standard_Real Ufirst = RealLast(), Ulast = RealFirst();
 194     TopExp_Explorer Explo(face_ii, TopAbs_EDGE);
 195     for (; Explo.More(); Explo.Next())
 196     {
 197       const TopoDS_Edge& anEdge = TopoDS::Edge(Explo.Current());
 198       if (!theEdgesMap.Contains(anEdge))
 199         continue;
 200       Standard_Real fpar, lpar;
 201       Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface(anEdge, theRefFace, fpar, lpar);
 202       UpdateBoundaries(aPCurve, fpar, lpar, Ufirst, Ulast);
 203     }
 204     if (Ulast > theUmax)
 205     {
 206       theUmax = Ulast;
 207       theIndFaceMax = ii;
 208     }
 209   }
 210 }
 211
 212 static void RelocatePCurvesToNewUorigin(const TopTools_SequenceOfShape& theEdges,
 213                                         const TopoDS_Shape&             theFirstFace,
 214                                         const TopoDS_Face&              theRefFace,
 215                                         const Standard_Real             theCoordTol,
 216                                         const Standard_Real             theUperiod,
 217                                         TopTools_IndexedDataMapOfShapeListOfShape& theVEmap,
 218                                         NCollection_DataMap<TopoDS_Shape, Handle(Geom2d_Curve)>& theEdgeNewPCurve,
 219                                         TopTools_MapOfShape&      theUsedEdges)
 220 {
 221   TopTools_MapOfShape EdgesOfFirstFace;
 222   TopExp::MapShapes(theFirstFace, EdgesOfFirstFace);
 223
 224   for (;;) //walk by contours
 225   {
 226     //try to find the start edge that:
 227     //1. belongs to outer edges of first face;
 228     //2. has minimum U-coord of its start point
 229     TopoDS_Edge StartEdge;
 230     TopAbs_Orientation anOr = TopAbs_FORWARD;
 231     Standard_Real anUmin = RealLast();
 232     for (Standard_Integer ii = 1; ii <= theEdges.Length(); ii++)
 233     {
 234       const TopoDS_Edge& anEdge = TopoDS::Edge(theEdges(ii));
 235       if (theUsedEdges.Contains(anEdge))
 236         continue;
 237       if (EdgesOfFirstFace.Contains(anEdge))
 238       {
 239         if (StartEdge.IsNull())
 240         {
 241           StartEdge = anEdge;
 242           BRepAdaptor_Curve2d StartBAcurve(StartEdge, theRefFace);
 243           Standard_Real aFirstParam, aLastParam;
 244           if (StartEdge.Orientation() == TopAbs_FORWARD)
 245           {
 246             aFirstParam = StartBAcurve.FirstParameter();
 247             aLastParam  = StartBAcurve.LastParameter();
 248           }
 249           else
 250           {
 251             aFirstParam = StartBAcurve.LastParameter();
 252             aLastParam  = StartBAcurve.FirstParameter();
 253           }
 254           gp_Pnt2d aFirstPoint = StartBAcurve.Value(aFirstParam);
 255           gp_Pnt2d aLastPoint  = StartBAcurve.Value(aLastParam);
 256           if (aFirstPoint.X() < aLastPoint.X())
 257           {
 258             anUmin = aFirstPoint.X();
 259             anOr = TopAbs_FORWARD;
 260           }
 261           else
 262           {
 263             anUmin = aLastPoint.X();
 264             anOr = TopAbs_REVERSED;
 265           }
 266         }
 267         else
 268         {
 269           BRepAdaptor_Curve2d aBAcurve(anEdge, theRefFace);
 270           Standard_Real aFirstParam, aLastParam;
 271           if (anEdge.Orientation() == TopAbs_FORWARD)
 272           {
 273             aFirstParam = aBAcurve.FirstParameter();
 274             aLastParam  = aBAcurve.LastParameter();
 275           }
 276           else
 277           {
 278             aFirstParam = aBAcurve.LastParameter();
 279             aLastParam  = aBAcurve.FirstParameter();
 280           }
 281           gp_Pnt2d aFirstPoint = aBAcurve.Value(aFirstParam);
 282           gp_Pnt2d aLastPoint  = aBAcurve.Value(aLastParam);
 283           if (aFirstPoint.X() < anUmin)
 284           {
 285             StartEdge = anEdge;
 286             anUmin = aFirstPoint.X();
 287             anOr = TopAbs_FORWARD;
 288           }
 289           if (aLastPoint.X() < anUmin)
 290           {
 291             StartEdge = anEdge;
 292             anUmin = aLastPoint.X();
 293             anOr = TopAbs_REVERSED;
 294           }
 295         }
 296       } //if (EdgesOfFirstFace.Contains(anEdge))
 297     } //for (Standard_Integer ii = 1; ii <= edges.Length(); ii++)
 298
 299     if (StartEdge.IsNull()) //all contours are passed
 300       break;
 301
 302     TopoDS_Vertex StartVertex = (anOr == TopAbs_FORWARD)?
 303       TopExp::FirstVertex(StartEdge, Standard_True) : TopExp::LastVertex(StartEdge, Standard_True);
 304     TopoDS_Edge CurEdge = StartEdge;
 305     Standard_Real fpar, lpar;
 306     Handle(Geom2d_Curve) CurPCurve = BRep_Tool::CurveOnSurface(CurEdge, theRefFace, fpar, lpar);
 307     CurPCurve = new Geom2d_TrimmedCurve(CurPCurve, fpar, lpar);
 308     theEdgeNewPCurve.Bind(CurEdge, CurPCurve);
 309     if (CurEdge.Orientation() == TopAbs_REVERSED)
 310     { Standard_Real tmp = fpar; fpar = lpar; lpar = tmp; }
 311     //Standard_Real StartParam = (anOr == TopAbs_FORWARD)? fpar : lpar;
 312     Standard_Real CurParam = (anOr == TopAbs_FORWARD)? lpar : fpar;
 313     //gp_Pnt2d StartPoint = CurPCurve->Value(StartParam);
 314     gp_Pnt2d CurPoint = CurPCurve->Value(CurParam);
 315     for (;;) //collect pcurves of a contour
 316     {
 317       RemoveEdgeFromMap(CurEdge, theVEmap);
 318       theUsedEdges.Add(CurEdge);
 319       TopoDS_Vertex CurVertex = (anOr == TopAbs_FORWARD)?
 320         TopExp::LastVertex(CurEdge, Standard_True) : TopExp::FirstVertex(CurEdge, Standard_True);
 321
 322       const TopTools_ListOfShape& Elist = theVEmap.FindFromKey(CurVertex);
 323       if (Elist.IsEmpty())
 324         break; //end of contour in 3d
 325
 326       TopTools_ListIteratorOfListOfShape itl(Elist);
 327       for (; itl.More(); itl.Next())
 328       {
 329         const TopoDS_Edge& anEdge = TopoDS::Edge(itl.Value());
 330         if (anEdge.IsSame(CurEdge))
 331           continue;
 332         TopoDS_Vertex aFirstVertex = (anOr == TopAbs_FORWARD)?
 333           TopExp::FirstVertex(anEdge, Standard_True) : TopExp::LastVertex(anEdge, Standard_True);
 334         if (!aFirstVertex.IsSame(CurVertex)) //may be if CurVertex is deg.vertex
 335           continue;
 336
 337         Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface(anEdge, theRefFace, fpar, lpar);
 338         aPCurve = new Geom2d_TrimmedCurve(aPCurve, fpar, lpar);
 339         if (anEdge.Orientation() == TopAbs_REVERSED)
 340         { Standard_Real tmp = fpar; fpar = lpar; lpar = tmp; }
 341         Standard_Real aParam = (anOr == TopAbs_FORWARD)? fpar : lpar;
 342         gp_Pnt2d aPoint = aPCurve->Value(aParam);
 343         Standard_Real anOffset = CurPoint.X() - aPoint.X();
 344         if (!(Abs(anOffset) < theCoordTol ||
 345               Abs(Abs(anOffset) - theUperiod) < theCoordTol))
 346           continue; //may be if CurVertex is deg.vertex
 347
 348         if (Abs(anOffset) > theUperiod/2)
 349         {
 350           anOffset = TrueValueOfOffset(anOffset, theUperiod);
 351           gp_Vec2d aVec(anOffset, 0.);
 352           Handle(Geom2d_Curve) aNewPCurve = Handle(Geom2d_Curve)::DownCast(aPCurve->Copy());
 353           aNewPCurve->Translate(aVec);
 354           aPCurve = aNewPCurve;
 355         }
 356         theEdgeNewPCurve.Bind(anEdge, aPCurve);
 357         CurEdge = anEdge;
 358         TopAbs_Orientation CurOr = TopAbs::Compose(anOr, CurEdge.Orientation());
 359         CurParam = (CurOr == TopAbs_FORWARD)?
 360           aPCurve->LastParameter() : aPCurve->FirstParameter();
 361         CurPoint = aPCurve->Value(CurParam);
 362         break;
 363       }
 364     } //for (;;) (collect pcurves of a contour)
 365   } //for (;;) (walk by contours)
 366 }
 367
 368 static void InsertWiresIntoFaces(const TopTools_SequenceOfShape& theWires,
 369                                  const TopTools_SequenceOfShape& theFaces,
 370                                  const TopoDS_Face&              theRefFace)
 371 {
 372   BRep_Builder BB;
 373   for (Standard_Integer ii = 1; ii <= theWires.Length(); ii++)
 374   {
 375     const TopoDS_Wire& aWire = TopoDS::Wire(theWires(ii));
 376     TopoDS_Iterator iter(aWire);
 377     const TopoDS_Edge& anEdge = TopoDS::Edge(iter.Value());
 378     BRepAdaptor_Curve2d BAcurve2d(anEdge, theRefFace);
 379     gp_Pnt2d aPnt2d = BAcurve2d.Value((BAcurve2d.FirstParameter() + BAcurve2d.LastParameter())/2.);
 380     TopoDS_Shape RequiredFace;
 381     for (Standard_Integer jj = 1; jj <= theFaces.Length(); jj++)
 382     {
 383       const TopoDS_Face& aFace = TopoDS::Face(theFaces(jj));
 384       BRepTopAdaptor_FClass2d Classifier(aFace, Precision::Confusion());
 385       TopAbs_State aStatus = Classifier.Perform(aPnt2d);
 386       if (aStatus == TopAbs_IN)
 387       {
 388         RequiredFace = aFace.Oriented (TopAbs_FORWARD);
 389         break;
 390       }
 391     }
 392     if (!RequiredFace.IsNull())
 393     {
 394       BB.Add(RequiredFace, aWire);
 395     }
 396     else
 397     {
 398       Standard_ASSERT_INVOKE ("ShapeUpgrade_UnifySameDomain: wire remains unclassified");
 399     }
 400   }
 401 }
 402
 403 static TopoDS_Face FindCommonFace(const TopoDS_Edge&  theEdge1,
 404                                   const TopoDS_Edge&  theEdge2,
 405                                   const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap,
 406                                   TopAbs_Orientation& theOrOfE1OnFace,
 407                                   TopAbs_Orientation& theOrOfE2OnFace)
 408 {
 409   TopoDS_Vertex aVertex;
 410   TopExp::CommonVertex(theEdge1, theEdge2, aVertex);
 411   const TopTools_ListOfShape& Flist = theVFmap.FindFromKey(aVertex);
 412   TopTools_ListIteratorOfListOfShape itl(Flist);
 413   for (; itl.More(); itl.Next())
 414   {
 415     TopoDS_Face aFace = TopoDS::Face(itl.Value());
 416     aFace.Orientation(TopAbs_FORWARD);
 417     Standard_Boolean e1found = Standard_False, e2found = Standard_False;
 418     TopExp_Explorer Explo(aFace, TopAbs_EDGE);
 419     for (; Explo.More(); Explo.Next())
 420     {
 421       const TopoDS_Shape& anEdge = Explo.Current();
 422       if (anEdge.IsSame(theEdge1))
 423       {
 424         e1found = Standard_True;
 425         theOrOfE1OnFace = anEdge.Orientation();
 426       }
 427       if (anEdge.IsSame(theEdge2))
 428       {
 429         e2found = Standard_True;
 430         theOrOfE2OnFace = anEdge.Orientation();
 431       }
 432       if (e1found && e2found)
 433         return aFace;
 434     }
 435   }
 436
 437   TopoDS_Face NullFace;
 438   return NullFace;
 439 }
 440
 441 static Standard_Boolean FindClosestPoints(const TopoDS_Edge& theEdge1,
 442                                           const TopoDS_Edge& theEdge2,
 443                                           const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap,
 444                                           TopoDS_Face& theCommonFace,
 445                                           Standard_Real& theMinSqDist,
 446                                           TopAbs_Orientation& OrOfE1OnFace,
 447                                           TopAbs_Orientation& OrOfE2OnFace,
 448                                           Standard_Integer& theIndOnE1,
 449                                           Standard_Integer& theIndOnE2,
 450                                           gp_Pnt2d* PointsOnEdge1,
 451                                           gp_Pnt2d* PointsOnEdge2)
 452
 453 {
 454   theCommonFace = FindCommonFace(theEdge1, theEdge2, theVFmap, OrOfE1OnFace, OrOfE2OnFace);
 455   if (theCommonFace.IsNull())
 456     return Standard_False;
 457
 458   Standard_Real fpar1, lpar1, fpar2, lpar2;
 459   Handle(Geom2d_Curve) PCurve1 = BRep_Tool::CurveOnSurface(theEdge1, theCommonFace, fpar1, lpar1);
 460   Handle(Geom2d_Curve) PCurve2 = BRep_Tool::CurveOnSurface(theEdge2, theCommonFace, fpar2, lpar2);
 461   PointsOnEdge1[0] = PCurve1->Value(fpar1);
 462   PointsOnEdge1[1] = PCurve1->Value(lpar1);
 463   PointsOnEdge2[0] = PCurve2->Value(fpar2);
 464   PointsOnEdge2[1] = PCurve2->Value(lpar2);
 465   theMinSqDist = RealLast();
 466   theIndOnE1 = -1;
 467   theIndOnE2 = -1;
 468   for (Standard_Integer ind1 = 0; ind1 < 2; ind1++)
 469     for (Standard_Integer ind2 = 0; ind2 < 2; ind2++)
 470     {
 471       Standard_Real aSqDist = PointsOnEdge1[ind1].SquareDistance(PointsOnEdge2[ind2]);
 472       if (aSqDist < theMinSqDist)
 473       {
 474         theMinSqDist = aSqDist;
 475         theIndOnE1 = ind1; theIndOnE2 = ind2;
 476       }
 477     }
 478   return Standard_True;
 479 }
 480
 481 //=======================================================================
 482 //function : ReconstructMissedSeam
 483 //purpose  : auxilary
 484 //=======================================================================
 485 static void ReconstructMissedSeam(const TopTools_SequenceOfShape& theEdges,
 486                                   const TopTools_SequenceOfShape& theRemovedEdges,
 487                                   const TopTools_MapOfShape&      theUsedEdges,
 488                                   const TopoDS_Face&              theFrefFace,
 489                                   const TopoDS_Vertex&            theCurVertex,
 490                                   const gp_Pnt2d&                 theCurPoint,
 491                                   const Standard_Real             theUperiod,
 492                                   const Standard_Real             theFaceUmin,
 493                                   const Standard_Real             theCoordTol,
 494                                   TopoDS_Edge&                    theNextEdge,
 495                                   TopoDS_Wire&                    theNewWire,
 496                                   gp_Pnt2d&                       theNextPoint,
 497                                   gp_Pnt2d&                       theStartOfNextEdge,
 498                                   TopoDS_Vertex&                  theLastVertexOfSeam,
 499                                   TopTools_IndexedDataMapOfShapeListOfShape& theVEmap)
 500
 501 {
 502   Handle(Geom_Surface) RefSurf = BRep_Tool::Surface(theFrefFace);
 503   GeomAbs_Shape aContinuity = (RefSurf->IsUPeriodic())? GeomAbs_CN : GeomAbs_C0;
 504
 505   Standard_Real Ydir = 1.; //up
 506   if (Abs(theCurPoint.X() - theFaceUmin) <= theCoordTol)
 507     Ydir = -1.; //down
 508
 509   //Consider as the candidate to be next edge:
 510   //only the edge that has first point with X-coordinate close to X-coordinate of theCurPoint
 511   //Choose from candidates the edge that is closest to theCurPoint in the defined direction Ydir
 512   Standard_Real MinDeltaY = RealLast();
 513   for (Standard_Integer ind = 1; ind <= theEdges.Length(); ind++)
 514   {
 515     const TopoDS_Edge& aCandidate = TopoDS::Edge(theEdges(ind));
 516     if (theUsedEdges.Contains(aCandidate))
 517       continue;
 518     BRepAdaptor_Curve2d BAcurve2d(aCandidate, theFrefFace);
 519     Standard_Real CandParam = (aCandidate.Orientation() == TopAbs_FORWARD)?
 520       BAcurve2d.FirstParameter() : BAcurve2d.LastParameter();
 521     gp_Pnt2d CandPoint = BAcurve2d.Value(CandParam);
 522     Standard_Real DeltaX = Abs(CandPoint.X() - theCurPoint.X());
 523     if (DeltaX > theCoordTol)
 524       continue;
 525
 526     Standard_Real DeltaY = CandPoint.Y() - theCurPoint.Y();
 527     DeltaY *= Ydir;
 528     if (DeltaY < 0.) //on the other side from CurPoint
 529       continue;
 530     if (DeltaY < MinDeltaY)
 531     {
 532       MinDeltaY = DeltaY;
 533       theNextEdge = aCandidate;
 534       theStartOfNextEdge = CandPoint;
 535     }
 536   }
 537
 538   //Build missed seam edge
 539   theLastVertexOfSeam = TopExp::FirstVertex(theNextEdge, Standard_True); //with orientation
 540   TopoDS_Vertex V1, V2;
 541   Standard_Real Param1, Param2, anU = 0.;
 542   Handle(Geom_Curve) Uiso;
 543
 544   TopoDS_Edge aRemovedEdge; //try to find it in <RemovedEdges>
 545   for (Standard_Integer i = 1; i <= theRemovedEdges.Length(); i++)
 546   {
 547     const TopoDS_Edge& anEdge = TopoDS::Edge(theRemovedEdges(i));
 548     TopoDS_Vertex aV1, aV2;
 549     TopExp::Vertices(anEdge, aV1, aV2);
 550     if ((aV1.IsSame(theCurVertex) && aV2.IsSame(theLastVertexOfSeam)) ||
 551         (aV1.IsSame(theLastVertexOfSeam) && aV2.IsSame(theCurVertex)))
 552     {
 553       Handle(Geom2d_Curve) aPC = BRep_Tool::CurveOnSurface(anEdge, theFrefFace, Param1, Param2);
 554       if (!aPC.IsNull())
 555       {
 556         aRemovedEdge = anEdge;
 557         break;
 558       }
 559     }
 560   }
 561   if (aRemovedEdge.IsNull())
 562   {
 563     Standard_Real CurTol  = BRep_Tool::Tolerance(theCurVertex);
 564     Standard_Real LastTol = BRep_Tool::Tolerance(theLastVertexOfSeam);
 565     anU = (CurTol < LastTol)? theCurPoint.X() : theStartOfNextEdge.X();
 566     Uiso = RefSurf->UIso(anU);
 567     if (Ydir > 0)
 568     {
 569       V1 = theCurVertex; V2 = theLastVertexOfSeam;
 570       Param1 = theCurPoint.Y(); Param2 = theStartOfNextEdge.Y();
 571     }
 572     else
 573     {
 574       V1 = theLastVertexOfSeam; V2 = theCurVertex;
 575       Param1 = theStartOfNextEdge.Y(); Param2 = theCurPoint.Y();
 576     }
 577   }
 578   else
 579   {
 580     TopExp::Vertices(aRemovedEdge, V1, V2);
 581     Uiso = BRep_Tool::Curve(aRemovedEdge, Param1, Param2);
 582   }
 583
 584   TopoDS_Edge MissedSeam = BRepLib_MakeEdge(Uiso, V1, V2, Param1, Param2);
 585   BRep_Builder BB;
 586
 587   gp_Vec2d Offset(theUperiod, 0.);
 588   if (aRemovedEdge.IsNull())
 589   {
 590     Standard_Real Vorigin = 0.;
 591     //Correct Param1 and Param2 if needed:
 592     //when Uiso-curve is periodic and Param1 and Param2 do not fit into V-range of surface,
 593     //BRepLib_MakeEdge may shift Param1 and Param2
 594     Standard_Real InitialParam1 = Param1, InitialParam2 = Param2;
 595     Handle(Geom_Curve) MissedCurve = BRep_Tool::Curve(MissedSeam, Param1, Param2);
 596     if ((Param1 != InitialParam1 || Param2 != InitialParam2) &&
 597         MissedCurve->IsPeriodic())
 598     {
 599       //Vorigin = -(MissedCurve->Period());
 600       Vorigin = -(Param1 - InitialParam1);
 601     }
 602     /////////////////////////////////////
 603     Handle(Geom2d_Line) PC1 = new Geom2d_Line(gp_Pnt2d(anU, Vorigin), gp_Dir2d(0., 1.));
 604     Handle(Geom2d_Curve) PC2 = Handle(Geom2d_Curve)::DownCast(PC1->Copy());
 605     if (Ydir > 0)
 606       Offset *= -1;
 607     PC2->Translate(Offset);
 608
 609     if (Ydir > 0)
 610       BB.UpdateEdge(MissedSeam, PC1, PC2, theFrefFace, 0.);
 611     else
 612       BB.UpdateEdge(MissedSeam, PC2, PC1, theFrefFace, 0.);
 613
 614     if (Ydir < 0)
 615       MissedSeam.Reverse();
 616   }
 617   else
 618   {
 619     TopoDS_Edge aSeam = aRemovedEdge;
 620     aSeam.Orientation(TopAbs_FORWARD);
 621     Handle(Geom2d_Curve) PC1 = BRep_Tool::CurveOnSurface(aSeam, theFrefFace, Param1, Param2);
 622     aSeam.Reverse();
 623     Handle(Geom2d_Curve) PC2 = BRep_Tool::CurveOnSurface(aSeam, theFrefFace, Param1, Param2);
 624     Standard_Boolean IsSeam = (PC1 != PC2);
 625     if (!IsSeam) //it was not a seam
 626     {
 627       anU = theCurPoint.X();
 628       gp_Pnt2d PointOnRemovedEdge = PC1->Value(Param1);
 629       Standard_Real Uremovededge = PointOnRemovedEdge.X();
 630       if (Abs(anU - Uremovededge) > theUperiod/2)
 631       {
 632         Standard_Real Sign = (anU > Uremovededge)? 1 : -1;
 633         Offset *= Sign;
 634         PC1 = Handle(Geom2d_Curve)::DownCast(PC2->Copy());
 635         PC1->Translate(Offset);
 636       }
 637       else
 638       {
 639         if (Ydir > 0)
 640           Offset *= -1;
 641         PC2 = Handle(Geom2d_Curve)::DownCast(PC1->Copy());
 642         PC2->Translate(Offset);
 643       }
 644     }
 645     if (theCurVertex.IsSame(V1))
 646       BB.UpdateEdge(MissedSeam, PC1, PC2, theFrefFace, 0.);
 647     else
 648     {
 649       if (IsSeam)
 650         BB.UpdateEdge(MissedSeam, PC1, PC2, theFrefFace, 0.);
 651       else
 652         BB.UpdateEdge(MissedSeam, PC2, PC1, theFrefFace, 0.);
 653
 654       MissedSeam.Reverse();
 655     }
 656   }
 657
 658   BB.Continuity(MissedSeam, theFrefFace, theFrefFace, aContinuity);
 659   BB.Add(theNewWire, MissedSeam);
 660   //add newly created edge into VEmap
 661   MissedSeam.Reverse();
 662   TopExp::MapShapesAndUniqueAncestors(MissedSeam, TopAbs_VERTEX, TopAbs_EDGE, theVEmap);
 663
 664   BRepAdaptor_Curve2d BAcurve2d(theNextEdge, theFrefFace);
 665   Standard_Real ParamOfNextPoint = (theNextEdge.Orientation() == TopAbs_FORWARD)?
 666     BAcurve2d.LastParameter() : BAcurve2d.FirstParameter();
 667   theNextPoint = BAcurve2d.Value(ParamOfNextPoint);
 668 }
 669
 670 //=======================================================================
 671 //function : TransformPCurves
 672 //purpose  : auxilary
 673 //=======================================================================
 674 static void TransformPCurves(const TopoDS_Face& theRefFace,
 675                              const TopoDS_Face& theFace,
 676                              TopTools_MapOfShape& theMapEdgesWithTemporaryPCurves)
 677 {
 678   BRepAdaptor_Surface BAsurf(theFace, Standard_True); //with real bounds of face
 679
 680   Standard_Real Uperiod = 0., Vperiod = 0.;
 681   Handle(Geom_Surface) RefSurf = BRep_Tool::Surface(theRefFace);
 682   if (RefSurf->IsKind(STANDARD_TYPE(Geom_RectangularTrimmedSurface)))
 683     RefSurf = (Handle(Geom_RectangularTrimmedSurface)::DownCast(RefSurf))->BasisSurface();
 684   if (RefSurf->IsUPeriodic())
 685     Uperiod = RefSurf->UPeriod();
 686   if (RefSurf->IsVPeriodic())
 687     Vperiod = RefSurf->VPeriod();
 688
 689   GeomAdaptor_Surface RefGAsurf(RefSurf);
 690
 691   Standard_Real Ufirst = BAsurf.FirstUParameter(),
 692     Ulast = BAsurf.LastUParameter(),
 693     Vfirst = BAsurf.FirstVParameter(),
 694     Vlast = BAsurf.LastVParameter();
 695
 696   Standard_Real u_mid = (Ufirst + Ulast)/2, v_mid = (Vfirst + Vlast)/2;
 697   gp_Pnt MidPoint = BAsurf.Value(u_mid, v_mid);
 698   Extrema_ExtPS ProjPS(MidPoint, RefGAsurf,
 699                        Precision::PConfusion(), Precision::PConfusion());
 700   Standard_Integer indmin = 1;
 701   for (Standard_Integer iext = 2; iext <= ProjPS.NbExt(); iext++)
 702     if (ProjPS.SquareDistance(iext) < ProjPS.SquareDistance(indmin))
 703       indmin = iext;
 704
 705   Standard_Real uu, vv;
 706   ProjPS.Point(indmin).Parameter(uu,vv);
 707   //Check uu and vv
 708   if (Abs(u_mid + Uperiod - uu) <= Precision::PConfusion())
 709     uu = u_mid;
 710   if (Abs(u_mid - uu) <= Precision::PConfusion())
 711     uu = u_mid;
 712   if (Abs(v_mid + Vperiod - vv) <= Precision::PConfusion())
 713     vv = v_mid;
 714   if (Abs(v_mid - vv) <= Precision::PConfusion())
 715     vv = v_mid;
 716   gp_Vec2d Translation(uu - u_mid, vv - v_mid);
 717
 718   Standard_Boolean X_Reverse = Standard_False, Y_Reverse = Standard_False;
 719   Standard_Real u_dx, v_dx, u_dy, v_dy;
 720
 721   Standard_Real Delta = (Precision::IsInfinite(Ufirst) || Precision::IsInfinite(Ulast))?
 722     1. : (Ulast - Ufirst)/4;
 723   Standard_Real Offset = (Uperiod == 0.)? Delta : Min(Uperiod/8, Delta);
 724   Standard_Real u1 = u_mid + Offset, v1 = v_mid;
 725   gp_Pnt DX = BAsurf.Value(u1, v1);
 726   ProjPS.Perform(DX);
 727   indmin = 1;
 728   for (Standard_Integer iext = 2; iext <= ProjPS.NbExt(); iext++)
 729     if (ProjPS.SquareDistance(iext) < ProjPS.SquareDistance(indmin))
 730       indmin = iext;
 731
 732   ProjPS.Point(indmin).Parameter(u_dx, v_dx);
 733   if (Uperiod != 0. &&
 734       Abs(uu - u_dx) > Uperiod/2)
 735   {
 736     if (uu   < Uperiod/2 &&
 737         u_dx > Uperiod/2)
 738       X_Reverse = Standard_True;
 739   }
 740   else if (u_dx < uu)
 741     X_Reverse = Standard_True;
 742
 743   Delta = (Precision::IsInfinite(Vfirst) || Precision::IsInfinite(Vlast))?
 744     1. : (Vlast - Vfirst)/4;
 745   Offset = (Vperiod == 0.)? Delta : Min(Vperiod/8, Delta);
 746   Standard_Real u2 = u_mid, v2 = v_mid + Offset;
 747   gp_Pnt DY = BAsurf.Value(u2, v2);
 748   ProjPS.Perform(DY);
 749   indmin = 1;
 750   for (Standard_Integer iext = 2; iext <= ProjPS.NbExt(); iext++)
 751     if (ProjPS.SquareDistance(iext) < ProjPS.SquareDistance(indmin))
 752       indmin = iext;
 753
 754   ProjPS.Point(indmin).Parameter(u_dy, v_dy);
 755   if (Vperiod != 0. &&
 756       Abs(vv - v_dy) > Vperiod/2)
 757   {
 758     if (vv   < Vperiod/2 &&
 759         v_dy > Vperiod/2)
 760       Y_Reverse = Standard_True;
 761   }
 762   else if (v_dy < vv)
 763     Y_Reverse = Standard_True;
 764
 765   gp_Trsf2d aTrsf;
 766   if (X_Reverse && Y_Reverse)
 767     aTrsf.SetMirror(gp::Origin2d());
 768   else if (X_Reverse)
 769     aTrsf.SetMirror(gp::OY2d());
 770   else if (Y_Reverse)
 771     aTrsf.SetMirror(gp::OX2d());
 772
 773   aTrsf.SetTranslationPart(Translation);
 774
 775   BRep_Builder BB;
 776   TopExp_Explorer Explo(theFace, TopAbs_EDGE);
 777   for (; Explo.More(); Explo.Next())
 778   {
 779     const TopoDS_Edge& anEdge = TopoDS::Edge(Explo.Current());
 780     if (BRep_Tool::Degenerated(anEdge) &&
 781         aTrsf.Form() != gp_Identity)
 782       continue;
 783     if (BRepTools::IsReallyClosed(anEdge, theFace))
 784       continue;
 785
 786     Standard_Real fpar, lpar;
 787     Handle(Geom2d_Curve) PCurveOnRef = BRep_Tool::CurveOnSurface(anEdge, theRefFace, fpar, lpar);
 788     if (!PCurveOnRef.IsNull())
 789       continue;
 790
 791     Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface(anEdge, theFace, fpar, lpar);
 792     Handle(Geom2d_Curve) aNewPCurve = Handle(Geom2d_Curve)::DownCast(aPCurve->Copy());
 793     if (aTrsf.Form() != gp_Identity)
 794       aNewPCurve->Transform(aTrsf);
 795
 796     Standard_Real tmp_first, tmp_last;
 797     Handle(Geom2d_Curve) aPCurveOnRefFace = BRep_Tool::CurveOnSurface(anEdge, theRefFace,
 798                                                                       tmp_first, tmp_last);
 799     if (aPCurveOnRefFace.IsNull())
 800       theMapEdgesWithTemporaryPCurves.Add(anEdge);
 801
 802     BB.UpdateEdge(anEdge, aNewPCurve, theRefFace, 0.);
 803     BB.Range(anEdge, fpar, lpar);
 804   }
 805 }
 806
 807 //=======================================================================
 808 //function : AddPCurves
 809 //purpose  : auxilary
 810 //=======================================================================
 811 static void AddPCurves(const TopTools_SequenceOfShape& theFaces,
 812                        const TopoDS_Face&              theRefFace,
 813                        TopTools_MapOfShape& theMapEdgesWithTemporaryPCurves)
 814 {
 815   BRepAdaptor_Surface RefBAsurf(theRefFace, Standard_False);
 816
 817   GeomAbs_SurfaceType aType = RefBAsurf.GetType();
 818   if (aType == GeomAbs_Plane)
 819     return;
 820
 821   for (Standard_Integer i = 1; i <= theFaces.Length(); i++)
 822   {
 823     const TopoDS_Face& aFace = TopoDS::Face(theFaces(i));
 824     if (aFace.IsSame(theRefFace))
 825       continue;
 826
 827     TransformPCurves(theRefFace, aFace, theMapEdgesWithTemporaryPCurves);
 828   }
 829 }
 830
 831 //=======================================================================
 832 //function : AddOrdinaryEdges
 833 //purpose  : auxilary
 834 //=======================================================================
 835 // adds edges from the shape to the sequence
 836 // seams and equal edges are dropped
 837 // Returns true if one of original edges dropped
 838 static Standard_Boolean AddOrdinaryEdges(TopTools_SequenceOfShape& edges,
 839                                          const TopoDS_Shape aShape,
 840                                          Standard_Integer& anIndex,
 841                                          TopTools_SequenceOfShape& theRemovedEdges)
 842 {
 843   //map of edges
 844   TopTools_IndexedMapOfShape aNewEdges;
 845   //add edges without seams
 846   for(TopExp_Explorer exp(aShape,TopAbs_EDGE); exp.More(); exp.Next()) {
 847     TopoDS_Shape edge = exp.Current();
 848     if(aNewEdges.Contains(edge))
 849     {
 850       aNewEdges.RemoveKey(edge);
 851       theRemovedEdges.Append(edge);
 852     }
 853     else
 854       aNewEdges.Add(edge);
 855   }
 856
 857   Standard_Boolean isDropped = Standard_False;
 858   //merge edges and drop seams
 859   Standard_Integer i;
 860   for (i = 1; i <= edges.Length(); i++) {
 861     TopoDS_Shape current = edges(i);
 862     if(aNewEdges.Contains(current)) {
 863
 864       aNewEdges.RemoveKey(current);
 865       edges.Remove(i);
 866       theRemovedEdges.Append(current);
 867       i--;
 868
 869       if(!isDropped) {
 870         isDropped = Standard_True;
 871         anIndex = i;
 872       }
 873     }
 874   }
 875
 876   //add edges to the sequence
 877   for (i = 1; i <= aNewEdges.Extent(); i++)
 878     edges.Append(aNewEdges(i));
 879
 880   return isDropped;
 881 }
 882
 883 //=======================================================================
 884 //function : getCylinder
 885 //purpose  : auxilary
 886 //=======================================================================
 887 static Standard_Boolean getCylinder(Handle(Geom_Surface)& theInSurface,
 888                                     gp_Cylinder& theOutCylinder)
 889 {
 890   Standard_Boolean isCylinder = Standard_False;
 891
 892   if (theInSurface->IsKind(STANDARD_TYPE(Geom_CylindricalSurface))) {
 893     Handle(Geom_CylindricalSurface) aGC = Handle(Geom_CylindricalSurface)::DownCast(theInSurface);
 894
 895     theOutCylinder = aGC->Cylinder();
 896     isCylinder = Standard_True;
 897   }
 898   else if (theInSurface->IsKind(STANDARD_TYPE(Geom_SurfaceOfRevolution))) {
 899     Handle(Geom_SurfaceOfRevolution) aRS =
 900       Handle(Geom_SurfaceOfRevolution)::DownCast(theInSurface);
 901     Handle(Geom_Curve) aBasis = aRS->BasisCurve();
 902     if (aBasis->IsKind(STANDARD_TYPE(Geom_Line))) {
 903       Handle(Geom_Line) aBasisLine = Handle(Geom_Line)::DownCast(aBasis);
 904       gp_Dir aDir = aRS->Direction();
 905       gp_Dir aBasisDir = aBasisLine->Position().Direction();
 906       if (aBasisDir.IsParallel(aDir, Precision::Angular())) {
 907         // basis line is parallel to the revolution axis: it is a cylinder
 908         gp_Pnt aLoc = aRS->Location();
 909         Standard_Real aR = aBasisLine->Lin().Distance(aLoc);
 910         gp_Ax3 aCylAx (aLoc, aDir);
 911
 912         theOutCylinder = gp_Cylinder(aCylAx, aR);
 913         isCylinder = Standard_True;
 914       }
 915     }
 916   }
 917   else if (theInSurface->IsKind(STANDARD_TYPE(Geom_SurfaceOfLinearExtrusion))) {
 918     Handle(Geom_SurfaceOfLinearExtrusion) aLES =
 919       Handle(Geom_SurfaceOfLinearExtrusion)::DownCast(theInSurface);
 920     Handle(Geom_Curve) aBasis = aLES->BasisCurve();
 921     if (aBasis->IsKind(STANDARD_TYPE(Geom_Circle))) {
 922       Handle(Geom_Circle) aBasisCircle = Handle(Geom_Circle)::DownCast(aBasis);
 923       gp_Dir aDir = aLES->Direction();
 924       gp_Dir aBasisDir = aBasisCircle->Position().Direction();
 925       if (aBasisDir.IsParallel(aDir, Precision::Angular())) {
 926         // basis circle is normal to the extrusion axis: it is a cylinder
 927         gp_Pnt aLoc = aBasisCircle->Location();
 928         Standard_Real aR = aBasisCircle->Radius();
 929         gp_Ax3 aCylAx (aLoc, aDir);
 930
 931         theOutCylinder = gp_Cylinder(aCylAx, aR);
 932         isCylinder = Standard_True;
 933       }
 934     }
 935   }
 936   else {
 937   }
 938
 939   return isCylinder;
 940 }
 941
 942 //=======================================================================
 943 //function : ClearRts
 944 //purpose  : auxilary
 945 //=======================================================================
 946 static Handle(Geom_Surface) ClearRts(const Handle(Geom_Surface)& aSurface)
 947 {
 948   if(aSurface->IsKind(STANDARD_TYPE(Geom_RectangularTrimmedSurface))) {
 949     Handle(Geom_RectangularTrimmedSurface) rts =
 950       Handle(Geom_RectangularTrimmedSurface)::DownCast(aSurface);
 951     return rts->BasisSurface();
 952   }
 953   return aSurface;
 954 }
 955
 956 //=======================================================================
 957 //function : GetNormalToSurface
 958 //purpose  : Gets the normal to surface by the given parameter on edge.
 959 //           Returns True if normal was computed.
 960 //=======================================================================
 961 static Standard_Boolean GetNormalToSurface(const TopoDS_Face& theFace,
 962                                            const TopoDS_Edge& theEdge,
 963                                            const Standard_Real theP,
 964                                            gp_Dir& theNormal)
 965 {
 966   Standard_Real f, l;
 967   // get 2d curve to get point in 2d
 968   const Handle(Geom2d_Curve)& aC2d = BRep_Tool::CurveOnSurface(theEdge, theFace, f, l);
 969   if (aC2d.IsNull()) {
 970     return Standard_False;
 971   }
 972   //
 973   // 2d point
 974   gp_Pnt2d aP2d;
 975   aC2d->D0(theP, aP2d);
 976   //
 977   // get D1
 978   gp_Vec aDU, aDV;
 979   gp_Pnt aP3d;
 980   TopLoc_Location aLoc;
 981   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(theFace, aLoc);
 982   aS->D1(aP2d.X(), aP2d.Y(), aP3d, aDU, aDV);
 983   //
 984   // compute normal
 985   gp_Vec aVNormal = aDU.Crossed(aDV);
 986   if (aVNormal.Magnitude() < Precision::Confusion()) {
 987     return Standard_False;
 988   }
 989   //
 990   if (theFace.Orientation() == TopAbs_REVERSED) {
 991     aVNormal.Reverse();
 992   }
 993   //
 994   aVNormal.Transform(aLoc.Transformation());
 995   theNormal = gp_Dir(aVNormal);
 996   return Standard_True;
 997 }
 998
 999 //=======================================================================
1000 //function : IsSameDomain
1001 //purpose  :
1002 //=======================================================================
1003 static Standard_Boolean IsSameDomain(const TopoDS_Face& aFace,
1004                                      const TopoDS_Face& aCheckedFace,
1005                                      const Standard_Real theLinTol,
1006                                      const Standard_Real theAngTol)
1007 {
1008   //checking the same handles
1009   TopLoc_Location L1, L2;
1010   Handle(Geom_Surface) S1, S2;
1011
1012   S1 = BRep_Tool::Surface(aFace,L1);
1013   S2 = BRep_Tool::Surface(aCheckedFace,L2);
1014
1015   if (S1 == S2 && L1 == L2)
1016     return Standard_True;
1017
1018   S1 = BRep_Tool::Surface(aFace);
1019   S2 = BRep_Tool::Surface(aCheckedFace);
1020
1021   S1 = ClearRts(S1);
1022   S2 = ClearRts(S2);
1023
1024   //Handle(Geom_OffsetSurface) aGOFS1, aGOFS2;
1025   //aGOFS1 = Handle(Geom_OffsetSurface)::DownCast(S1);
1026   //aGOFS2 = Handle(Geom_OffsetSurface)::DownCast(S2);
1027   //if (!aGOFS1.IsNull()) S1 = aGOFS1->BasisSurface();
1028   //if (!aGOFS2.IsNull()) S2 = aGOFS2->BasisSurface();
1029
1030   // case of two planar surfaces:
1031   // all kinds of surfaces checked, including b-spline and bezier
1032   GeomLib_IsPlanarSurface aPlanarityChecker1(S1, theLinTol);
1033   if (aPlanarityChecker1.IsPlanar()) {
1034     GeomLib_IsPlanarSurface aPlanarityChecker2(S2, theLinTol);
1035     if (aPlanarityChecker2.IsPlanar()) {
1036       gp_Pln aPln1 = aPlanarityChecker1.Plan();
1037       gp_Pln aPln2 = aPlanarityChecker2.Plan();
1038
1039       if (aPln1.Position().Direction().IsParallel(aPln2.Position().Direction(), theAngTol) &&
1040         aPln1.Distance(aPln2) < theLinTol) {
1041         return Standard_True;
1042       }
1043     }
1044   }
1045
1046   // case of two elementary surfaces: use OCCT tool
1047   // elementary surfaces: ConicalSurface, CylindricalSurface,
1048   //                      Plane, SphericalSurface and ToroidalSurface
1049   if (S1->IsKind(STANDARD_TYPE(Geom_ElementarySurface)) &&
1050       S2->IsKind(STANDARD_TYPE(Geom_ElementarySurface)))
1051   {
1052     Handle(GeomAdaptor_HSurface) aGA1 = new GeomAdaptor_HSurface(S1);
1053     Handle(GeomAdaptor_HSurface) aGA2 = new GeomAdaptor_HSurface(S2);
1054
1055     Handle(BRepTopAdaptor_TopolTool) aTT1 = new BRepTopAdaptor_TopolTool();
1056     Handle(BRepTopAdaptor_TopolTool) aTT2 = new BRepTopAdaptor_TopolTool();
1057
1058     try {
1059       IntPatch_ImpImpIntersection anIIInt(aGA1, aTT1, aGA2, aTT2, theLinTol, theLinTol);
1060       if (!anIIInt.IsDone() || anIIInt.IsEmpty())
1061         return Standard_False;
1062
1063       return anIIInt.TangentFaces();
1064     }
1065     catch (Standard_Failure const&) {
1066       return Standard_False;
1067     }
1068   }
1069
1070   // case of two cylindrical surfaces, at least one of which is a swept surface
1071   // swept surfaces: SurfaceOfLinearExtrusion, SurfaceOfRevolution
1072   if ((S1->IsKind(STANDARD_TYPE(Geom_CylindricalSurface)) ||
1073        S1->IsKind(STANDARD_TYPE(Geom_SweptSurface))) &&
1074       (S2->IsKind(STANDARD_TYPE(Geom_CylindricalSurface)) ||
1075        S2->IsKind(STANDARD_TYPE(Geom_SweptSurface))))
1076   {
1077     gp_Cylinder aCyl1, aCyl2;
1078     if (getCylinder(S1, aCyl1) && getCylinder(S2, aCyl2)) {
1079       if (fabs(aCyl1.Radius() - aCyl2.Radius()) < theLinTol) {
1080         gp_Dir aDir1 = aCyl1.Position().Direction();
1081         gp_Dir aDir2 = aCyl2.Position().Direction();
1082         if (aDir1.IsParallel(aDir2, Precision::Angular())) {
1083           gp_Pnt aLoc1 = aCyl1.Location();
1084           gp_Pnt aLoc2 = aCyl2.Location();
1085           gp_Vec aVec12 (aLoc1, aLoc2);
1086           if (aVec12.SquareMagnitude() < theLinTol*theLinTol ||
1087               aVec12.IsParallel(aDir1, Precision::Angular())) {
1088             return Standard_True;
1089           }
1090         }
1091       }
1092     }
1093   }
1094
1095   return Standard_False;
1096 }
1097
1098 //=======================================================================
1099 //function : UpdateMapOfShapes
1100 //purpose  :
1101 //=======================================================================
1102 static void UpdateMapOfShapes(TopTools_MapOfShape& theMapOfShapes,
1103                               Handle(ShapeBuild_ReShape)& theContext)
1104 {
1105   for (TopTools_MapIteratorOfMapOfShape it(theMapOfShapes); it.More(); it.Next()) {
1106     const TopoDS_Shape& aShape = it.Value();
1107     TopoDS_Shape aContextShape = theContext->Apply(aShape);
1108     if (!aContextShape.IsSame(aShape))
1109       theMapOfShapes.Add(aContextShape);
1110   }
1111 }
1112
1113 //=======================================================================
1114 //function : GlueEdgesWithPCurves
1115 //purpose  : Glues the pcurves of the sequence of edges
1116 //           and glues their 3d curves
1117 //=======================================================================
1118 static TopoDS_Edge GlueEdgesWithPCurves(const TopTools_SequenceOfShape& aChain,
1119                                         const TopoDS_Vertex& FirstVertex,
1120                                         const TopoDS_Vertex& LastVertex)
1121 {
1122   Standard_Integer i, j;
1123
1124   TopoDS_Edge FirstEdge = TopoDS::Edge(aChain(1));
1125   TColGeom_SequenceOfSurface SurfSeq;
1126   NCollection_Sequence<TopLoc_Location> LocSeq;
1127
1128   for (int aCurveIndex = 0;; aCurveIndex++)
1129   {
1130     Handle(Geom2d_Curve) aCurve;
1131     Handle(Geom_Surface) aSurface;
1132     TopLoc_Location aLocation;
1133     Standard_Real aFirst, aLast;
1134     BRep_Tool::CurveOnSurface (FirstEdge, aCurve, aSurface, aLocation, aFirst, aLast, aCurveIndex);
1135     if (aCurve.IsNull())
1136       break;
1137
1138     SurfSeq.Append(aSurface);
1139     LocSeq.Append(aLocation);
1140   }
1141
1142   Standard_Real fpar, lpar;
1143   BRep_Tool::Range(FirstEdge, fpar, lpar);
1144   TopoDS_Edge PrevEdge = FirstEdge;
1145   TopoDS_Vertex CV;
1146   Standard_Real MaxTol = 0.;
1147
1148   TopoDS_Edge ResEdge;
1149   BRep_Builder BB;
1150
1151   Standard_Integer nb_curve = aChain.Length();   //number of curves
1152   TColGeom_Array1OfBSplineCurve tab_c3d(0,nb_curve-1);                    //array of the curves
1153   TColStd_Array1OfReal tabtolvertex(0,nb_curve-1); //(0,nb_curve-2);  //array of the tolerances
1154
1155   TopoDS_Vertex PrevVertex = FirstVertex;
1156   for (i = 1; i <= nb_curve; i++)
1157   {
1158     TopoDS_Edge anEdge = TopoDS::Edge(aChain(i));
1159     TopoDS_Vertex VF, VL;
1160     TopExp::Vertices(anEdge, VF, VL);
1161     Standard_Boolean ToReverse = (!VF.IsSame(PrevVertex));
1162
1163     Standard_Real Tol1 = BRep_Tool::Tolerance(VF);
1164     Standard_Real Tol2 = BRep_Tool::Tolerance(VL);
1165     if (Tol1 > MaxTol)
1166       MaxTol = Tol1;
1167     if (Tol2 > MaxTol)
1168       MaxTol = Tol2;
1169
1170     if (i > 1)
1171     {
1172       TopExp::CommonVertex(PrevEdge, anEdge, CV);
1173       Standard_Real Tol = BRep_Tool::Tolerance(CV);
1174       tabtolvertex(i-2) = Tol;
1175     }
1176
1177     Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
1178     Handle(Geom_TrimmedCurve) aTrCurve = new Geom_TrimmedCurve(aCurve, fpar, lpar);
1179     tab_c3d(i-1) = GeomConvert::CurveToBSplineCurve(aTrCurve);
1180     GeomConvert::C0BSplineToC1BSplineCurve(tab_c3d(i-1), Precision::Confusion());
1181     if (ToReverse)
1182       tab_c3d(i-1)->Reverse();
1183     PrevVertex = (ToReverse)? VF : VL;
1184     PrevEdge = anEdge;
1185   }
1186   Handle(TColGeom_HArray1OfBSplineCurve)  concatcurve;     //array of the concatenated curves
1187   Handle(TColStd_HArray1OfInteger)        ArrayOfIndices;  //array of the remining Vertex
1188   Standard_Boolean closed_flag = Standard_False;
1189   GeomConvert::ConcatC1(tab_c3d,
1190                         tabtolvertex,
1191                         ArrayOfIndices,
1192                         concatcurve,
1193                         closed_flag,
1194                         Precision::Confusion());   //C1 concatenation
1195
1196   if (concatcurve->Length() > 1)
1197   {
1198     GeomConvert_CompCurveToBSplineCurve Concat(concatcurve->Value(concatcurve->Lower()));
1199
1200     for (i = concatcurve->Lower()+1; i <= concatcurve->Upper(); i++)
1201       Concat.Add( concatcurve->Value(i), MaxTol, Standard_True );
1202
1203     concatcurve->SetValue(concatcurve->Lower(), Concat.BSplineCurve());
1204   }
1205   Handle(Geom_BSplineCurve) ResCurve = concatcurve->Value(concatcurve->Lower());
1206
1207   TColGeom2d_SequenceOfBoundedCurve ResPCurves;
1208   for (j = 1; j <= SurfSeq.Length(); j++)
1209   {
1210     TColGeom2d_Array1OfBSplineCurve tab_c2d(0,nb_curve-1); //array of the pcurves
1211
1212     PrevVertex = FirstVertex;
1213     PrevEdge = FirstEdge;
1214     for (i = 1; i <= nb_curve; i++)
1215     {
1216       TopoDS_Edge anEdge = TopoDS::Edge(aChain(i));
1217       TopoDS_Vertex VF, VL;
1218       TopExp::Vertices(anEdge, VF, VL);
1219       Standard_Boolean ToReverse = (!VF.IsSame(PrevVertex));
1220
1221       Handle(Geom2d_Curve) aPCurve =
1222         BRep_Tool::CurveOnSurface(anEdge, SurfSeq(j), LocSeq(j), fpar, lpar);
1223       if (aPCurve.IsNull())
1224         continue;
1225       Handle(Geom2d_TrimmedCurve) aTrPCurve = new Geom2d_TrimmedCurve(aPCurve, fpar, lpar);
1226       tab_c2d(i-1) = Geom2dConvert::CurveToBSplineCurve(aTrPCurve);
1227       Geom2dConvert::C0BSplineToC1BSplineCurve(tab_c2d(i-1), Precision::Confusion());
1228       if (ToReverse)
1229         tab_c2d(i-1)->Reverse();
1230       PrevVertex = (ToReverse)? VF : VL;
1231       PrevEdge = anEdge;
1232     }
1233     Handle(TColGeom2d_HArray1OfBSplineCurve)  concatc2d;     //array of the concatenated curves
1234     Handle(TColStd_HArray1OfInteger)        ArrayOfInd2d;  //array of the remining Vertex
1235     closed_flag = Standard_False;
1236     Geom2dConvert::ConcatC1(tab_c2d,
1237                             tabtolvertex,
1238                             ArrayOfInd2d,
1239                             concatc2d,
1240                             closed_flag,
1241                             Precision::Confusion());   //C1 concatenation
1242
1243     if (concatc2d->Length() > 1)
1244     {
1245       Geom2dConvert_CompCurveToBSplineCurve Concat2d(concatc2d->Value(concatc2d->Lower()));
1246
1247       for (i = concatc2d->Lower()+1; i <= concatc2d->Upper(); i++)
1248         Concat2d.Add( concatc2d->Value(i), MaxTol, Standard_True );
1249
1250       concatc2d->SetValue(concatc2d->Lower(), Concat2d.BSplineCurve());
1251     }
1252     Handle(Geom2d_BSplineCurve) aResPCurve = concatc2d->Value(concatc2d->Lower());
1253     ResPCurves.Append(aResPCurve);
1254   }
1255
1256   ResEdge = BRepLib_MakeEdge(ResCurve,
1257                              FirstVertex, LastVertex,
1258                              ResCurve->FirstParameter(), ResCurve->LastParameter());
1259   BB.SameRange(ResEdge, Standard_False);
1260   BB.SameParameter(ResEdge, Standard_False);
1261   for (j = 1; j <= ResPCurves.Length(); j++)
1262   {
1263     BB.UpdateEdge(ResEdge, ResPCurves(j), SurfSeq(j), LocSeq(j), MaxTol);
1264     BB.Range(ResEdge, SurfSeq(j), LocSeq(j), ResPCurves(j)->FirstParameter(), ResPCurves(j)->LastParameter());
1265   }
1266
1267   BRepLib::SameParameter(ResEdge, MaxTol, Standard_True);
1268
1269   return ResEdge;
1270 }
1271
1272 //=======================================================================
1273 //function : MergeSubSeq
1274 //purpose  : Merges a sequence of edges into one edge if possible
1275 //=======================================================================
1276
1277 static Standard_Boolean MergeSubSeq(const TopTools_SequenceOfShape& theChain,
1278                                     const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap,
1279                                     TopoDS_Edge& OutEdge,
1280                                     double theAngTol,
1281                                     Standard_Boolean ConcatBSplines,
1282                                     Standard_Boolean isSafeInputMode,
1283                                     Handle(ShapeBuild_ReShape)& theContext)
1284 {
1285   ShapeAnalysis_Edge sae;
1286   BRep_Builder B;
1287   // union edges in chain
1288   int j;
1289   Standard_Real fp1,lp1,fp2,lp2;
1290   Standard_Boolean IsUnionOfLinesPossible = Standard_True;
1291   Standard_Boolean IsUnionOfCirclesPossible = Standard_True;
1292   Handle(Geom_Curve) c3d1, c3d2;
1293   for(j = 1; j < theChain.Length(); j++)
1294   {
1295     TopoDS_Edge edge1 = TopoDS::Edge(theChain.Value(j));
1296     TopoDS_Edge edge2 = TopoDS::Edge(theChain.Value(j+1));
1297
1298     if (BRep_Tool::Degenerated(edge1) &&
1299         BRep_Tool::Degenerated(edge2))
1300     {
1301       //Find the closest points in 2d
1302       TopoDS_Edge edgeFirst = TopoDS::Edge(theChain.First());
1303       TopoDS_Edge edgeLast  = TopoDS::Edge(theChain.Last());
1304       TopoDS_Face CommonFace;
1305       Standard_Real MinSqDist;
1306       TopAbs_Orientation OrOfE1OnFace, OrOfE2OnFace;
1307       Standard_Integer IndOnE1, IndOnE2;
1308       gp_Pnt2d PointsOnEdge1 [2], PointsOnEdge2 [2];
1309       if (!FindClosestPoints(edgeFirst, edgeLast, theVFmap, CommonFace,
1310                              MinSqDist, OrOfE1OnFace, OrOfE2OnFace,
1311                              IndOnE1, IndOnE2, PointsOnEdge1, PointsOnEdge2))
1312         return Standard_False;
1313
1314       //Define indices corresponding to extremities of future edge
1315       IndOnE1 = 1 - IndOnE1;
1316       IndOnE2 = 1 - IndOnE2;
1317
1318       //Construct new degenerated edge
1319       gp_Pnt2d StartPoint = PointsOnEdge1[IndOnE1];
1320       gp_Pnt2d EndPoint   = PointsOnEdge2[IndOnE2];
1321       if ((OrOfE1OnFace == TopAbs_FORWARD  && IndOnE1 == 1) ||
1322           (OrOfE1OnFace == TopAbs_REVERSED && IndOnE1 == 0))
1323       { gp_Pnt2d Tmp = StartPoint; StartPoint = EndPoint; EndPoint = Tmp; }
1324
1325       Handle(Geom2d_Line) aLine = GCE2d_MakeLine(StartPoint, EndPoint);
1326
1327       TopoDS_Vertex aVertex = TopExp::FirstVertex(edgeFirst);
1328       TopoDS_Vertex StartVertex = aVertex, EndVertex = aVertex;
1329       StartVertex.Orientation(TopAbs_FORWARD);
1330       EndVertex.Orientation(TopAbs_REVERSED);
1331
1332       TopoDS_Edge NewEdge;
1333       B.MakeEdge(NewEdge);
1334       B.UpdateEdge(NewEdge, aLine, CommonFace, Precision::Confusion());
1335       B.Range(NewEdge, 0., StartPoint.Distance(EndPoint));
1336       B.Add (NewEdge, StartVertex);
1337       B.Add (NewEdge, EndVertex);
1338       B.Degenerated(NewEdge, Standard_True);
1339       OutEdge = NewEdge;
1340       return Standard_True;
1341     }
1342
1343     c3d1 = BRep_Tool::Curve(edge1,fp1,lp1);
1344     c3d2 = BRep_Tool::Curve(edge2,fp2,lp2);
1345
1346     if(c3d1.IsNull() || c3d2.IsNull())
1347       return Standard_False;
1348
1349     while(c3d1->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
1350       Handle(Geom_TrimmedCurve) tc =
1351         Handle(Geom_TrimmedCurve)::DownCast(c3d1);
1352       c3d1 = tc->BasisCurve();
1353     }
1354     while(c3d2->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
1355       Handle(Geom_TrimmedCurve) tc =
1356         Handle(Geom_TrimmedCurve)::DownCast(c3d2);
1357       c3d2 = tc->BasisCurve();
1358     }
1359     if( c3d1->IsKind(STANDARD_TYPE(Geom_Line)) && c3d2->IsKind(STANDARD_TYPE(Geom_Line)) ) {
1360       Handle(Geom_Line) L1 = Handle(Geom_Line)::DownCast(c3d1);
1361       Handle(Geom_Line) L2 = Handle(Geom_Line)::DownCast(c3d2);
1362       gp_Dir Dir1 = L1->Position().Direction();
1363       gp_Dir Dir2 = L2->Position().Direction();
1364       if(!Dir1.IsParallel(Dir2,theAngTol))
1365         IsUnionOfLinesPossible = Standard_False;
1366     }
1367     else
1368       IsUnionOfLinesPossible = Standard_False;
1369     if( c3d1->IsKind(STANDARD_TYPE(Geom_Circle)) && c3d2->IsKind(STANDARD_TYPE(Geom_Circle)) ) {
1370       Handle(Geom_Circle) C1 = Handle(Geom_Circle)::DownCast(c3d1);
1371       Handle(Geom_Circle) C2 = Handle(Geom_Circle)::DownCast(c3d2);
1372       gp_Pnt P01 = C1->Location();
1373       gp_Pnt P02 = C2->Location();
1374       if (P01.Distance(P02) > Precision::Confusion())
1375         IsUnionOfCirclesPossible = Standard_False;
1376     }
1377     else
1378       IsUnionOfCirclesPossible = Standard_False;
1379   }
1380   if (IsUnionOfLinesPossible && IsUnionOfCirclesPossible)
1381     return Standard_False;
1382
1383   //union of lines is possible
1384   if (IsUnionOfLinesPossible)
1385   {
1386     TopoDS_Vertex V[2];
1387     V[0] = sae.FirstVertex(TopoDS::Edge(theChain.First()));
1388     gp_Pnt PV1 = BRep_Tool::Pnt(V[0]);
1389     V[1] = sae.LastVertex(TopoDS::Edge(theChain.Last()));
1390     gp_Pnt PV2 = BRep_Tool::Pnt(V[1]);
1391     gp_Vec Vec(PV1, PV2);
1392     if (isSafeInputMode) {
1393       for (int k = 0; k < 2; k++) {
1394         if (!theContext->IsRecorded(V[k])) {
1395           TopoDS_Vertex Vcopy = TopoDS::Vertex(V[k].EmptyCopied());
1396           theContext->Replace(V[k], Vcopy);
1397           V[k] = Vcopy;
1398         }
1399         else
1400           V[k] = TopoDS::Vertex(theContext->Apply(V[k]));
1401       }
1402     }
1403     Handle(Geom_Line) L = new Geom_Line(gp_Ax1(PV1,Vec));
1404     Standard_Real dist = PV1.Distance(PV2);
1405     Handle(Geom_TrimmedCurve) tc = new Geom_TrimmedCurve(L,0.0,dist);
1406     TopoDS_Edge E;
1407     B.MakeEdge (E, tc ,Precision::Confusion());
1408     B.Add (E,V[0]);  B.Add (E,V[1]);
1409     B.UpdateVertex(V[0], 0., E, 0.);
1410     B.UpdateVertex(V[1], dist, E, 0.);
1411     OutEdge = E;
1412     return Standard_True;
1413   }
1414
1415   if (IsUnionOfCirclesPossible)
1416   {
1417     double f,l;
1418     TopoDS_Edge FE = TopoDS::Edge(theChain.First());
1419     Handle(Geom_Curve) c3d = BRep_Tool::Curve(FE,f,l);
1420
1421     while(c3d->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
1422       Handle(Geom_TrimmedCurve) tc =
1423         Handle(Geom_TrimmedCurve)::DownCast(c3d);
1424       c3d = tc->BasisCurve();
1425     }
1426     Handle(Geom_Circle) Cir = Handle(Geom_Circle)::DownCast(c3d);
1427
1428     TopoDS_Vertex V[2];
1429     V[0] = sae.FirstVertex(FE);
1430     V[1] = sae.LastVertex(TopoDS::Edge(theChain.Last()));
1431     TopoDS_Edge E;
1432     if (V[0].IsSame(V[1])) {
1433       // closed chain
1434       BRepAdaptor_Curve adef(FE);
1435       Handle(Geom_Circle) Cir1;
1436       double FP, LP;
1437       if ( FE.Orientation() == TopAbs_FORWARD)
1438       {
1439         FP = adef.FirstParameter();
1440         LP = adef.LastParameter();
1441       }
1442       else
1443       {
1444         FP = adef.LastParameter();
1445         LP = adef.FirstParameter();
1446       }
1447       if (Abs(FP) < Precision::PConfusion())
1448       {
1449         B.MakeEdge (E,Cir, Precision::Confusion());
1450         B.Add(E,V[0]);
1451         B.Add(E,V[1]);
1452         E.Orientation(FE.Orientation());
1453       }
1454       else
1455       {
1456         GC_MakeCircle MC1 (adef.Value(FP), adef.Value((FP + LP) * 0.5), adef.Value(LP));
1457         if (MC1.IsDone())
1458           Cir1 = MC1.Value();
1459         else
1460           return Standard_False;
1461         B.MakeEdge (E, Cir1, Precision::Confusion());
1462         B.Add(E,V[0]);
1463         B.Add(E,V[1]);
1464       }
1465     }
1466     else {
1467       if (isSafeInputMode) {
1468         for (int k = 0; k < 2; k++) {
1469           if (!theContext->IsRecorded(V[k])) {
1470             TopoDS_Vertex Vcopy = TopoDS::Vertex(V[k].EmptyCopied());
1471             theContext->Replace(V[k], Vcopy);
1472             V[k] = Vcopy;
1473           }
1474           else
1475             V[k] = TopoDS::Vertex(theContext->Apply(V[k]));
1476         }
1477       }
1478       gp_Pnt PV1 = BRep_Tool::Pnt(V[0]);
1479       gp_Pnt PV2 = BRep_Tool::Pnt(V[1]);
1480       TopoDS_Vertex VM = sae.LastVertex(FE);
1481       gp_Pnt PVM = BRep_Tool::Pnt(VM);
1482       GC_MakeCircle MC (PV1,PVM,PV2);
1483       Handle(Geom_Circle) C = MC.Value();
1484       gp_Pnt P0 = C->Location();
1485       gp_Dir D1(gp_Vec(P0,PV1));
1486       gp_Dir D2(gp_Vec(P0,PV2));
1487       Standard_Real fpar = C->XAxis().Direction().Angle(D1);
1488       if(fabs(fpar)>Precision::Confusion()) {
1489         // check orientation
1490         gp_Dir ND =  C->XAxis().Direction().Crossed(D1);
1491         if(ND.IsOpposite(C->Axis().Direction(),Precision::Confusion())) {
1492           fpar = -fpar;
1493         }
1494       }
1495       Standard_Real lpar = C->XAxis().Direction().Angle(D2);
1496       if(fabs(lpar)>Precision::Confusion()) {
1497         // check orientation
1498         gp_Dir ND =  C->XAxis().Direction().Crossed(D2);
1499         if(ND.IsOpposite(C->Axis().Direction(),Precision::Confusion())) {
1500           lpar = -lpar;
1501         }
1502       }
1503       if (lpar < fpar) lpar += 2*M_PI;
1504       Handle(Geom_TrimmedCurve) tc = new Geom_TrimmedCurve(C,fpar,lpar);
1505       B.MakeEdge (E,tc,Precision::Confusion());
1506       B.Add(E,V[0]);
1507       B.Add(E,V[1]);
1508       B.UpdateVertex(V[0], fpar, E, 0.);
1509       B.UpdateVertex(V[1], lpar, E, 0.);
1510     }
1511     OutEdge = E;
1512     return Standard_True;
1513   }
1514   if (theChain.Length() > 1 && ConcatBSplines) {
1515     // second step: union edges with various curves
1516     // skl for bug 0020052 from Mantis: perform such unions
1517     // only if curves are bspline or bezier
1518
1519     TopoDS_Vertex VF = sae.FirstVertex(TopoDS::Edge(theChain.First()));
1520     TopoDS_Vertex VL = sae.LastVertex(TopoDS::Edge(theChain.Last()));
1521     Standard_Boolean NeedUnion = Standard_True;
1522     for(j = 1; j <= theChain.Length(); j++) {
1523       TopoDS_Edge edge = TopoDS::Edge(theChain.Value(j));
1524       TopLoc_Location Loc;
1525       Handle(Geom_Curve) c3d = BRep_Tool::Curve(edge,Loc,fp1,lp1);
1526       if(c3d.IsNull()) continue;
1527       while(c3d->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
1528         Handle(Geom_TrimmedCurve) tc =
1529           Handle(Geom_TrimmedCurve)::DownCast(c3d);
1530         c3d = tc->BasisCurve();
1531       }
1532       if( ( c3d->IsKind(STANDARD_TYPE(Geom_BSplineCurve)) ||
1533             c3d->IsKind(STANDARD_TYPE(Geom_BezierCurve)) ) ) continue;
1534       NeedUnion = Standard_False;
1535       break;
1536     }
1537     if(NeedUnion) {
1538 #ifdef OCCT_DEBUG
1539       std::cout<<"can not make analitical union => make approximation"<<std::endl;
1540 #endif
1541       TopoDS_Edge E = GlueEdgesWithPCurves(theChain, VF, VL);
1542       OutEdge = E;
1543       return Standard_True;
1544     }
1545     else {
1546 #ifdef OCCT_DEBUG
1547       std::cout<<"can not make approximation for such types of curves"<<std::endl;
1548 #endif
1549       return Standard_False;
1550     }
1551   }
1552   return Standard_False;
1553 }
1554
1555 //=======================================================================
1556 //function : IsMergingPossible
1557 //purpose  : Checks if merging of two edges is possible
1558 //=======================================================================
1559
1560 static Standard_Boolean IsMergingPossible(const TopoDS_Edge& edge1, const TopoDS_Edge& edge2,
1561                                           double theAngTol, double theLinTol,
1562                                           const TopTools_MapOfShape& AvoidEdgeVrt, const bool theLineDirectionOk,
1563                                           const gp_Pnt& theFirstPoint, const gp_Vec& theDirectionVec,
1564                                           const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap)
1565 {
1566   Standard_Boolean IsDegE1 = BRep_Tool::Degenerated(edge1);
1567   Standard_Boolean IsDegE2 = BRep_Tool::Degenerated(edge2);
1568
1569   if (IsDegE1 && IsDegE2)
1570   {
1571     //Find connstion point in 2d
1572     TopoDS_Face CommonFace;
1573     Standard_Real MinSqDist;
1574     TopAbs_Orientation OrOfE1OnFace, OrOfE2OnFace;
1575     Standard_Integer IndOnE1, IndOnE2;
1576     gp_Pnt2d PointsOnEdge1 [2], PointsOnEdge2 [2];
1577     if (!FindClosestPoints(edge1, edge2, theVFmap, CommonFace,
1578                            MinSqDist, OrOfE1OnFace, OrOfE2OnFace,
1579                            IndOnE1, IndOnE2, PointsOnEdge1, PointsOnEdge2))
1580       return Standard_False;
1581
1582     if (MinSqDist <= Precision::SquareConfusion())
1583       return Standard_True;
1584
1585     return Standard_False;
1586   }
1587   else if (IsDegE1 || IsDegE2)
1588     return Standard_False;
1589
1590   TopoDS_Vertex CV = TopExp::LastVertex(edge1, Standard_True);
1591   if (CV.IsNull() || AvoidEdgeVrt.Contains(CV))
1592     return Standard_False;
1593
1594   BRepAdaptor_Curve ade1(edge1);
1595   BRepAdaptor_Curve ade2(edge2);
1596
1597   GeomAbs_CurveType t1 = ade1.GetType();
1598   GeomAbs_CurveType t2 = ade2.GetType();
1599
1600   if( t1 == GeomAbs_Circle && t2 == GeomAbs_Circle)
1601   {
1602     if (ade1.Circle().Location().Distance(ade2.Circle().Location()) > Precision::Confusion())
1603       return Standard_False;
1604   }
1605
1606   if( ( (t1 != GeomAbs_BezierCurve && t1 != GeomAbs_BSplineCurve) ||
1607       (t2 != GeomAbs_BezierCurve && t2 != GeomAbs_BSplineCurve)) && t1 != t2)
1608     return Standard_False;
1609
1610   gp_Vec Diff1, Diff2;
1611   gp_Pnt P1, P2;
1612   if (edge1.Orientation() == TopAbs_FORWARD)
1613     ade1.D1(ade1.LastParameter(), P1, Diff1);
1614   else
1615   {
1616     ade1.D1(ade1.FirstParameter(), P1, Diff1);
1617     Diff1 = -Diff1;
1618   }
1619
1620   if (edge2.Orientation() == TopAbs_FORWARD)
1621     ade2.D1(ade2.FirstParameter(), P2, Diff2);
1622   else
1623   {
1624     ade2.D1(ade2.LastParameter(), P2, Diff2);
1625     Diff2 = -Diff2;
1626   }
1627
1628   if (Diff1.Angle(Diff2) > theAngTol)
1629     return Standard_False;
1630
1631   if (theLineDirectionOk && t2 == GeomAbs_Line)
1632   {
1633     // Check that the accumulated deflection does not exceed the linear tolerance
1634     Standard_Real aLast = (edge2.Orientation() == TopAbs_FORWARD) ?
1635       ade2.LastParameter() : ade2.FirstParameter();
1636     gp_Vec aCurV(theFirstPoint, ade2.Value(aLast));
1637     Standard_Real aDD = theDirectionVec.CrossSquareMagnitude(aCurV);
1638     if (aDD > theLinTol*theLinTol)
1639       return Standard_False;
1640
1641     // Check that the accumulated angle does not exceed the angular tolerance.
1642     // For symmetry, check the angle between vectors of:
1643     // - first edge and resulting curve, and
1644     // - the last edge and resulting curve.
1645     if (theDirectionVec.Angle(aCurV) > theAngTol || Diff2.Angle(aCurV) > theAngTol)
1646       return Standard_False;
1647   }
1648
1649   return Standard_True;
1650 }
1651
1652 //=======================================================================
1653 //function : GetLineEdgePoints
1654 //purpose  :
1655 //=======================================================================
1656 static Standard_Boolean GetLineEdgePoints(const TopoDS_Edge& theInpEdge, gp_Pnt& theFirstPoint, gp_Vec& theDirectionVec)
1657 {
1658   double f, l;
1659   Handle(Geom_Curve) aCur = BRep_Tool::Curve(theInpEdge, f, l);
1660   if(aCur.IsNull())
1661     return Standard_False;
1662
1663   Handle(Geom_TrimmedCurve) aTC = Handle(Geom_TrimmedCurve)::DownCast(aCur);
1664   if (!aTC.IsNull())
1665     aCur = aTC->BasisCurve();
1666
1667   if (aCur->DynamicType() != STANDARD_TYPE(Geom_Line))
1668     return Standard_False;
1669
1670   if (theInpEdge.Orientation() == TopAbs_REVERSED) {
1671     Standard_Real tmp = f;
1672     f = l;
1673     l = tmp;
1674   }
1675   theFirstPoint = aCur->Value(f);
1676   gp_Pnt aLP = aCur->Value(l);
1677   theDirectionVec = aLP.XYZ().Subtracted(theFirstPoint.XYZ());
1678   theDirectionVec.Normalize();
1679   return Standard_True;
1680 }
1681
1682 //=======================================================================
1683 //function : GenerateSubSeq
1684 //purpose  : Generates sub-sequences of edges from sequence of edges
1685 //Edges from each subsequences can be merged into the one edge
1686 //=======================================================================
1687
1688 static void GenerateSubSeq (const TopTools_SequenceOfShape& anInpEdgeSeq,
1689                             NCollection_Sequence<SubSequenceOfEdges>& SeqOfSubSeqOfEdges,
1690                             Standard_Boolean IsClosed, double theAngTol, double theLinTol,
1691                             const TopTools_MapOfShape& AvoidEdgeVrt,
1692                             const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap)
1693 {
1694   Standard_Boolean isOk = Standard_False;
1695   TopoDS_Edge edge1, edge2;
1696
1697   SubSequenceOfEdges SubSeq;
1698   TopoDS_Edge RefEdge = TopoDS::Edge(anInpEdgeSeq(1));
1699   SubSeq.SeqsEdges.Append(RefEdge);
1700   SeqOfSubSeqOfEdges.Append(SubSeq);
1701
1702   gp_Pnt aFirstPoint;
1703   gp_Vec aDirectionVec;
1704   Standard_Boolean isLineDirectionOk = GetLineEdgePoints(RefEdge, aFirstPoint, aDirectionVec);
1705
1706   for (int i = 1; i < anInpEdgeSeq.Length(); i++)
1707   {
1708     edge1 = TopoDS::Edge(anInpEdgeSeq(i));
1709     edge2 = TopoDS::Edge(anInpEdgeSeq(i+1));
1710     isOk = IsMergingPossible(edge1, edge2, theAngTol, theLinTol,
1711                              AvoidEdgeVrt, isLineDirectionOk, aFirstPoint, aDirectionVec, theVFmap);
1712     if (!isOk)
1713     {
1714       SubSequenceOfEdges aSubSeq;
1715       aSubSeq.SeqsEdges.Append(edge2);
1716       SeqOfSubSeqOfEdges.Append(aSubSeq);
1717       isLineDirectionOk = GetLineEdgePoints(edge2, aFirstPoint, aDirectionVec);
1718     }
1719     else
1720       SeqOfSubSeqOfEdges.ChangeLast().SeqsEdges.Append(edge2);
1721   }
1722   /// check first and last chain segments
1723   if (IsClosed && SeqOfSubSeqOfEdges.Length() > 1)
1724   {
1725     edge1 = TopoDS::Edge(anInpEdgeSeq.Last());
1726     edge2 = TopoDS::Edge(anInpEdgeSeq.First());
1727     if (IsMergingPossible(edge1, edge2, theAngTol, theLinTol,
1728                           AvoidEdgeVrt, Standard_False, aFirstPoint, aDirectionVec, theVFmap))
1729     {
1730       SeqOfSubSeqOfEdges.ChangeLast().SeqsEdges.Append(SeqOfSubSeqOfEdges.ChangeFirst().SeqsEdges);
1731       SeqOfSubSeqOfEdges.Remove(1);
1732     }
1733   }
1734 }
1735
1736 //=======================================================================
1737 //function : MergeEdges
1738 //purpose  : auxilary
1739 //=======================================================================
1740 static Standard_Boolean MergeEdges(TopTools_SequenceOfShape& SeqEdges,
1741                                    const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap,
1742                                    const Standard_Real theAngTol,
1743                                    const Standard_Real theLinTol,
1744                                    const Standard_Boolean ConcatBSplines,
1745                                    const Standard_Boolean isSafeInputMode,
1746                                    Handle(ShapeBuild_ReShape)& theContext,
1747                                    NCollection_Sequence<SubSequenceOfEdges>& SeqOfSubSeqOfEdges,
1748                                    const TopTools_MapOfShape& NonMergVrt)
1749 {
1750   TopTools_IndexedDataMapOfShapeListOfShape aMapVE;
1751   Standard_Integer j;
1752   TopTools_MapOfShape VerticesToAvoid;
1753   const Standard_Integer aNbE = SeqEdges.Length();
1754   for (j = 1; j <= aNbE; j++)
1755   {
1756     TopoDS_Edge anEdge = TopoDS::Edge(SeqEdges(j));
1757     // fill in the map V-E
1758     for (TopoDS_Iterator it(anEdge.Oriented(TopAbs_FORWARD)); it.More(); it.Next())
1759     {
1760       TopoDS_Shape aV = it.Value();
1761       if (aV.Orientation() == TopAbs_FORWARD || aV.Orientation() == TopAbs_REVERSED)
1762       {
1763         if (!aMapVE.Contains(aV))
1764           aMapVE.Add(aV, TopTools_ListOfShape());
1765         aMapVE.ChangeFromKey(aV).Append(anEdge);
1766       }
1767     }
1768   }
1769   VerticesToAvoid.Unite(NonMergVrt);
1770
1771   // do loop while there are unused edges
1772   TopTools_MapOfShape aUsedEdges;
1773
1774   for (Standard_Integer iE = 1; iE <= aNbE; ++iE)
1775   {
1776     TopoDS_Edge edge = TopoDS::Edge (SeqEdges (iE));
1777     if (!aUsedEdges.Add (edge))
1778       continue;
1779
1780     // make chain for unite
1781     TopTools_SequenceOfShape aChain;
1782     aChain.Append(edge);
1783     TopoDS_Vertex V[2];
1784     TopExp::Vertices(edge, V[0], V[1], Standard_True);
1785
1786     // connect more edges to the chain in both directions
1787     for (j = 0; j < 2; j++)
1788     {
1789       Standard_Boolean isAdded = Standard_True;
1790       while (isAdded)
1791       {
1792         isAdded = Standard_False;
1793         if (V[j].IsNull())
1794           break;
1795         const TopTools_ListOfShape& aLE = aMapVE.FindFromKey(V[j]);
1796         for (TopTools_ListIteratorOfListOfShape itL(aLE); itL.More(); itL.Next())
1797         {
1798           edge = TopoDS::Edge(itL.Value());
1799           if (!aUsedEdges.Contains(edge))
1800           {
1801             TopoDS_Vertex V2[2];
1802             TopExp::Vertices(edge, V2[0], V2[1], Standard_True);
1803             // the neighboring edge must have V[j] reversed and located on the opposite end
1804             if (V2[1 - j].IsEqual(V[j].Reversed()))
1805             {
1806               if (j == 0)
1807                 aChain.Prepend(edge);
1808               else
1809                 aChain.Append(edge);
1810               aUsedEdges.Add(edge);
1811               V[j] = V2[j];
1812               isAdded = Standard_True;
1813               break;
1814             }
1815           }
1816         }
1817       }
1818     }
1819
1820     if (aChain.Length() < 2)
1821       continue;
1822
1823     Standard_Boolean IsClosed = Standard_False;
1824     if (V[0].IsSame ( V[1] ))
1825       IsClosed = Standard_True;
1826
1827     // split chain by vertices at which merging is not possible
1828     NCollection_Sequence<SubSequenceOfEdges> aOneSeq;
1829     GenerateSubSeq(aChain, aOneSeq, IsClosed, theAngTol, theLinTol, VerticesToAvoid, theVFmap);
1830
1831     // put sub-chains in the result
1832     SeqOfSubSeqOfEdges.Append(aOneSeq);
1833   }
1834
1835   for (int i = 1; i <= SeqOfSubSeqOfEdges.Length(); i++)
1836   {
1837     TopoDS_Edge UE;
1838     if (SeqOfSubSeqOfEdges(i).SeqsEdges.Length() < 2)
1839       continue;
1840     if (MergeSubSeq(SeqOfSubSeqOfEdges(i).SeqsEdges, theVFmap,
1841                     UE, theAngTol,
1842                     ConcatBSplines, isSafeInputMode, theContext))
1843       SeqOfSubSeqOfEdges(i).UnionEdges = UE;
1844   }
1845   return Standard_True;
1846 }
1847
1848 //=======================================================================
1849 //function : MergeSeq
1850 //purpose  : Tries to unify the sequence of edges with the set of
1851 //           another edges which lies on the same geometry
1852 //=======================================================================
1853 static Standard_Boolean MergeSeq (TopTools_SequenceOfShape& SeqEdges,
1854                                   const TopTools_IndexedDataMapOfShapeListOfShape& theVFmap,
1855                                   const Standard_Real theAngTol,
1856                                   const Standard_Real theLinTol,
1857                                   const Standard_Boolean ConcatBSplines,
1858                                   const Standard_Boolean isSafeInputMode,
1859                                   Handle(ShapeBuild_ReShape)& theContext,
1860                                   const TopTools_MapOfShape& nonMergVert)
1861 {
1862   NCollection_Sequence<SubSequenceOfEdges> SeqOfSubsSeqOfEdges;
1863   if (MergeEdges(SeqEdges, theVFmap, theAngTol, theLinTol, ConcatBSplines, isSafeInputMode,
1864                  theContext, SeqOfSubsSeqOfEdges, nonMergVert))
1865   {
1866     for (Standard_Integer i = 1; i <= SeqOfSubsSeqOfEdges.Length(); i++ )
1867     {
1868       if (SeqOfSubsSeqOfEdges(i).UnionEdges.IsNull())
1869         continue;
1870
1871       theContext->Merge(SeqOfSubsSeqOfEdges(i).SeqsEdges,
1872         SeqOfSubsSeqOfEdges(i).UnionEdges);
1873     }
1874     return Standard_True;
1875   }
1876   return Standard_False;
1877 }
1878
1879 //=======================================================================
1880 //function : CheckSharedVertices
1881 //purpose  : Checks the sequence of edges on the presence of shared vertex
1882 //=======================================================================
1883
1884 static void CheckSharedVertices(const TopTools_SequenceOfShape& theSeqEdges,
1885                                 const TopTools_IndexedDataMapOfShapeListOfShape& theMapEdgesVertex,
1886                                 const TopTools_MapOfShape& theMapKeepShape,
1887                                 TopTools_MapOfShape& theShareVertMap)
1888 {
1889   ShapeAnalysis_Edge sae;
1890   TopTools_SequenceOfShape SeqVertexes;
1891   TopTools_MapOfShape MapVertexes;
1892   for (Standard_Integer k = 1; k <= theSeqEdges.Length(); k++ )
1893   {
1894     TopoDS_Vertex aV1 = sae.FirstVertex(TopoDS::Edge(theSeqEdges(k)));
1895     TopoDS_Vertex aV2 = sae.LastVertex(TopoDS::Edge(theSeqEdges(k)));
1896     if (!MapVertexes.Add(aV1))
1897       SeqVertexes.Append(aV1);
1898     if (!MapVertexes.Add(aV2))
1899       SeqVertexes.Append(aV2);
1900   }
1901
1902   for (Standard_Integer k = 1; k <= SeqVertexes.Length()/* && !IsSharedVertexPresent*/; k++ )
1903   {
1904     const TopTools_ListOfShape& ListEdgesV1 = theMapEdgesVertex.FindFromKey(SeqVertexes(k));
1905     if (ListEdgesV1.Extent() > 2 || theMapKeepShape.Contains(SeqVertexes(k)))
1906       theShareVertMap.Add(SeqVertexes(k));
1907   }
1908   //return theShareVertMap.IsEmpty() ? false : true;
1909 }
1910
1911 //=======================================================================
1912 //function : ShapeUpgrade_UnifySameDomain
1913 //purpose  : Constructor
1914 //=======================================================================
1915
1916 ShapeUpgrade_UnifySameDomain::ShapeUpgrade_UnifySameDomain()
1917   : myLinTol(Precision::Confusion()),
1918     myAngTol(Precision::Angular()),
1919     myUnifyFaces(Standard_True),
1920     myUnifyEdges (Standard_True),
1921     myConcatBSplines (Standard_False),
1922     myAllowInternal (Standard_False),
1923     mySafeInputMode(Standard_True),
1924     myHistory(new BRepTools_History)
1925 {
1926   myContext = new ShapeBuild_ReShape;
1927 }
1928
1929 //=======================================================================
1930 //function : ShapeUpgrade_UnifySameDomain
1931 //purpose  : Constructor
1932 //=======================================================================
1933
1934 ShapeUpgrade_UnifySameDomain::ShapeUpgrade_UnifySameDomain(const TopoDS_Shape& aShape,
1935                                                            const Standard_Boolean UnifyEdges,
1936                                                            const Standard_Boolean UnifyFaces,
1937                                                            const Standard_Boolean ConcatBSplines)
1938   : myInitShape (aShape),
1939     myLinTol(Precision::Confusion()),
1940     myAngTol(Precision::Angular()),
1941     myUnifyFaces(UnifyFaces),
1942     myUnifyEdges (UnifyEdges),
1943     myConcatBSplines (ConcatBSplines),
1944     myAllowInternal (Standard_False),
1945     mySafeInputMode (Standard_True),
1946     myShape (aShape),
1947     myHistory(new BRepTools_History)
1948 {
1949   myContext = new ShapeBuild_ReShape;
1950 }
1951
1952 //=======================================================================
1953 //function : Initialize
1954 //purpose  :
1955 //=======================================================================
1956
1957 void ShapeUpgrade_UnifySameDomain::Initialize(const TopoDS_Shape& aShape,
1958                                               const Standard_Boolean UnifyEdges,
1959                                               const Standard_Boolean UnifyFaces,
1960                                               const Standard_Boolean ConcatBSplines)
1961 {
1962   myInitShape = aShape;
1963   myShape = aShape;
1964   myUnifyEdges = UnifyEdges;
1965   myUnifyFaces = UnifyFaces;
1966   myConcatBSplines = ConcatBSplines;
1967
1968   myContext->Clear();
1969   myKeepShapes.Clear();
1970   myHistory->Clear();
1971 }
1972
1973 //=======================================================================
1974 //function : AllowInternalEdges
1975 //purpose  :
1976 //=======================================================================
1977
1978 void ShapeUpgrade_UnifySameDomain::AllowInternalEdges (const Standard_Boolean theValue)
1979 {
1980   myAllowInternal = theValue;
1981 }
1982
1983 //=======================================================================
1984 //function : SetSafeInputMode
1985 //purpose  :
1986 //=======================================================================
1987
1988 void ShapeUpgrade_UnifySameDomain::SetSafeInputMode(Standard_Boolean theValue)
1989 {
1990   mySafeInputMode = theValue;
1991 }
1992
1993 //=======================================================================
1994 //function : KeepShape
1995 //purpose  :
1996 //=======================================================================
1997
1998 void ShapeUpgrade_UnifySameDomain::KeepShape(const TopoDS_Shape& theShape)
1999 {
2000   if (theShape.ShapeType() == TopAbs_EDGE || theShape.ShapeType() == TopAbs_VERTEX)
2001     myKeepShapes.Add(theShape);
2002 }
2003
2004 //=======================================================================
2005 //function : KeepShapes
2006 //purpose  :
2007 //=======================================================================
2008
2009 void ShapeUpgrade_UnifySameDomain::KeepShapes(const TopTools_MapOfShape& theShapes)
2010 {
2011   for (TopTools_MapIteratorOfMapOfShape it(theShapes); it.More(); it.Next()) {
2012     if (it.Value().ShapeType() == TopAbs_EDGE || it.Value().ShapeType() == TopAbs_VERTEX)
2013       myKeepShapes.Add(it.Value());
2014   }
2015 }
2016
2017 //=======================================================================
2018 //function : UnifyFaces
2019 //purpose  :
2020 //=======================================================================
2021
2022 void ShapeUpgrade_UnifySameDomain::UnifyFaces()
2023 {
2024   // creating map of edge faces for the whole shape
2025   TopTools_IndexedDataMapOfShapeListOfShape aGMapEdgeFaces;
2026   TopExp::MapShapesAndAncestors(myShape, TopAbs_EDGE, TopAbs_FACE, aGMapEdgeFaces);
2027
2028   // unify faces in each shell separately
2029   TopExp_Explorer exps;
2030   for (exps.Init(myShape, TopAbs_SHELL); exps.More(); exps.Next())
2031     IntUnifyFaces(exps.Current(), aGMapEdgeFaces);
2032
2033   // gather all faces out of shells in one compound and unify them at once
2034   BRep_Builder aBB;
2035   TopoDS_Compound aCmp;
2036   aBB.MakeCompound(aCmp);
2037   Standard_Integer nbf = 0;
2038   for (exps.Init(myShape, TopAbs_FACE, TopAbs_SHELL); exps.More(); exps.Next(), nbf++)
2039     aBB.Add(aCmp, exps.Current());
2040
2041   if (nbf > 0)
2042     IntUnifyFaces(aCmp, aGMapEdgeFaces);
2043
2044   myShape = myContext->Apply(myShape);
2045 }
2046
2047 //=======================================================================
2048 //function : SetFixWireModes
2049 //purpose  :
2050 //=======================================================================
2051
2052 static void SetFixWireModes(ShapeFix_Face& theSff)
2053 {
2054   Handle(ShapeFix_Wire) aFixWire = theSff.FixWireTool();
2055   aFixWire->FixSelfIntersectionMode() = 0;
2056   aFixWire->FixNonAdjacentIntersectingEdgesMode() = 0;
2057   aFixWire->FixLackingMode() = 0;
2058   aFixWire->FixNotchedEdgesMode() = 0;
2059   aFixWire->ModifyTopologyMode() = Standard_False;
2060   aFixWire->ModifyRemoveLoopMode() = 0;
2061   aFixWire->FixGapsByRangesMode() = Standard_False;
2062   aFixWire->FixSmallMode() = 0;
2063 }
2064
2065 //=======================================================================
2066 //function : IntUnifyFaces
2067 //purpose  :
2068 //=======================================================================
2069
2070 void ShapeUpgrade_UnifySameDomain::IntUnifyFaces(const TopoDS_Shape& theInpShape,
2071    TopTools_IndexedDataMapOfShapeListOfShape& theGMapEdgeFaces)
2072 {
2073   // creating map of edge faces for the shape
2074   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgeFaces;
2075   TopExp::MapShapesAndAncestors(theInpShape, TopAbs_EDGE, TopAbs_FACE, aMapEdgeFaces);
2076
2077   // map of processed shapes
2078   TopTools_MapOfShape aProcessed;
2079
2080   // processing each face
2081   TopExp_Explorer exp;
2082   for (exp.Init(theInpShape, TopAbs_FACE); exp.More(); exp.Next()) {
2083
2084     TopoDS_Face aFace = TopoDS::Face(exp.Current());
2085
2086     if (aProcessed.Contains(aFace))
2087       continue;
2088
2089     // Boundary edges for the new face
2090     TopTools_SequenceOfShape edges;
2091     TopTools_SequenceOfShape RemovedEdges;
2092
2093     Standard_Integer dummy;
2094     AddOrdinaryEdges(edges, aFace, dummy, RemovedEdges);
2095
2096     // Faces to get unified with the current faces
2097     TopTools_SequenceOfShape faces;
2098
2099     // Add the current face for unification
2100     faces.Append(aFace);
2101
2102     // surface and location to construct result
2103     TopLoc_Location aBaseLocation;
2104     Handle(Geom_Surface) aBaseSurface = BRep_Tool::Surface(aFace,aBaseLocation);
2105     aBaseSurface = ClearRts(aBaseSurface);
2106     TopAbs_Orientation RefFaceOrientation = aFace.Orientation();
2107
2108     //Take original surface
2109     TopoDS_Face RefFace;
2110     BRep_Builder BB;
2111     BB.MakeFace(RefFace, aBaseSurface, aBaseLocation, 0.);
2112     RefFace.Orientation(RefFaceOrientation);
2113     TopTools_MapOfShape MapEdgesWithTemporaryPCurves; //map of edges not lying on RefFace
2114     //these edges may be updated by temporary pcurves
2115
2116     Standard_Real Uperiod = (aBaseSurface->IsUPeriodic())? aBaseSurface->UPeriod() : 0.;
2117
2118     // find adjacent faces to union
2119     Standard_Integer i;
2120     for (i = 1; i <= edges.Length(); i++) {
2121       TopoDS_Edge edge = TopoDS::Edge(edges(i));
2122       if (BRep_Tool::Degenerated(edge))
2123         continue;
2124
2125       // get connectivity of the edge in the global shape
2126       const TopTools_ListOfShape& aGList = theGMapEdgeFaces.FindFromKey(edge);
2127       if (!myAllowInternal && (aGList.Extent() != 2 || myKeepShapes.Contains(edge))) {
2128         // non manifold case is not processed unless myAllowInternal
2129         continue;
2130       }
2131       //
2132       // Get the faces connected through the edge in the current shape
2133       const TopTools_ListOfShape& aList = aMapEdgeFaces.FindFromKey(edge);
2134       if (aList.Extent() < 2) {
2135         continue;
2136       }
2137
2138       // for a planar face create and store pcurve of edge on face
2139       // to speed up all operations
2140       if (!mySafeInputMode && aBaseSurface->IsKind(STANDARD_TYPE(Geom_Plane)))
2141         BRepLib::BuildPCurveForEdgeOnPlane(edge, aFace);
2142
2143       // get normal of the face to compare it with normals of other faces
2144       gp_Dir aDN1;
2145       //
2146       // take intermediate point on edge to compute the normal
2147       Standard_Real f, l;
2148       BRep_Tool::Range(edge, f, l);
2149       Standard_Real aTMid = (f + l) * .5;
2150       //
2151       Standard_Boolean bCheckNormals = GetNormalToSurface(aFace, edge, aTMid, aDN1);
2152       //
2153       // Process the faces
2154       TopTools_ListIteratorOfListOfShape anIter(aList);
2155       for (; anIter.More(); anIter.Next()) {
2156
2157         TopoDS_Face aCheckedFace = TopoDS::Face(anIter.Value());
2158         if (aCheckedFace.IsSame(aFace))
2159           continue;
2160
2161         if (aProcessed.Contains(aCheckedFace))
2162           continue;
2163
2164         if (bCheckNormals) {
2165           // get normal of checked face using the same parameter on edge
2166           gp_Dir aDN2;
2167           if (GetNormalToSurface(aCheckedFace, edge, aTMid, aDN2)) {
2168             // and check if the adjacent faces are having approximately same normals
2169             Standard_Real anAngle = aDN1.Angle(aDN2);
2170             if (anAngle > myAngTol) {
2171               continue;
2172             }
2173           }
2174         }
2175         //
2176         if (IsSameDomain(aFace,aCheckedFace, myLinTol, myAngTol)) {
2177
2178           if (AddOrdinaryEdges(edges, aCheckedFace, dummy, RemovedEdges)) {
2179             // sequence edges is modified
2180             i = dummy;
2181           }
2182
2183           faces.Append(aCheckedFace);
2184           aProcessed.Add(aCheckedFace);
2185           break;
2186         }
2187       }
2188     }
2189
2190     if (faces.Length() > 1) {
2191       //Add correct pcurves for the reference surface to the edges of other faces
2192       AddPCurves(faces, RefFace, MapEdgesWithTemporaryPCurves);
2193
2194       // fill in the connectivity map for selected faces
2195       TopTools_IndexedDataMapOfShapeListOfShape aMapEF;
2196       for (i = 1; i <= faces.Length(); i++) {
2197         TopExp::MapShapesAndAncestors(faces(i), TopAbs_EDGE, TopAbs_FACE, aMapEF);
2198       }
2199       // Collect keep edges and multi-connected edges, i.e. edges that are internal to
2200       // the set of selected faces and have connections to other faces.
2201       TopTools_ListOfShape aKeepEdges;
2202       for (i = 1; i <= aMapEF.Extent(); i++) {
2203         const TopTools_ListOfShape& aLF = aMapEF(i);
2204         if (aLF.Extent() == 2) {
2205           const TopoDS_Shape& aE = aMapEF.FindKey(i);
2206           const TopTools_ListOfShape& aGLF = theGMapEdgeFaces.FindFromKey(aE);
2207           if (aGLF.Extent() > 2 || myKeepShapes.Contains(aE)) {
2208             aKeepEdges.Append(aE);
2209           }
2210         }
2211       }
2212       if (!aKeepEdges.IsEmpty()) {
2213         if  (!myAllowInternal) {
2214           // Remove from the selection the faces which have no other connect edges
2215           // and contain multi-connected edges and/or keep edges.
2216           TopTools_MapOfShape anAvoidFaces;
2217           TopTools_ListIteratorOfListOfShape it(aKeepEdges);
2218           for (; it.More(); it.Next()) {
2219             const TopoDS_Shape& aE = it.Value();
2220             const TopTools_ListOfShape& aLF = aMapEF.FindFromKey(aE);
2221             anAvoidFaces.Add(aLF.First());
2222             anAvoidFaces.Add(aLF.Last());
2223           }
2224           for (i = 1; i <= faces.Length(); i++) {
2225             if (anAvoidFaces.Contains(faces(i))) {
2226               // update the boundaries of merged area, for that
2227               // remove from 'edges' the edges of this face and add to 'edges'
2228               // the edges of this face that were not present in 'edges' before
2229               Standard_Boolean hasConnectAnotherFaces = Standard_False;
2230               TopExp_Explorer ex(faces(i), TopAbs_EDGE);
2231               for (; ex.More() && !hasConnectAnotherFaces; ex.Next()) {
2232                 TopoDS_Shape aE = ex.Current();
2233                 const TopTools_ListOfShape& aLF = aMapEF.FindFromKey(aE);
2234                 if (aLF.Extent() > 1) {
2235                   for (it.Init(aLF); it.More() && !hasConnectAnotherFaces; it.Next()) {
2236                     if (!anAvoidFaces.Contains(it.Value()))
2237                       hasConnectAnotherFaces = Standard_True;
2238                   }
2239                 }
2240               }
2241               if (!hasConnectAnotherFaces) {
2242                 AddOrdinaryEdges(edges, faces(i), dummy, RemovedEdges);
2243                 faces.Remove(i);
2244                 i--;
2245               }
2246             }
2247           }
2248           // check if the faces with keep edges contained in
2249           // already updated the boundaries of merged area
2250           if (!faces.IsEmpty()) {
2251             TopTools_MapOfShape aMapFaces;
2252             for (i = 1; i <= faces.Length(); i++) {
2253               aMapFaces.Add(faces(i));
2254             }
2255             for (it.Init(aKeepEdges); it.More(); it.Next()) {
2256               const TopoDS_Shape& aE = it.Value();
2257               const TopTools_ListOfShape& aLF = aMapEF.FindFromKey(aE);
2258               if (aLF.Extent() < 2)
2259                 continue;
2260               if (aMapFaces.Contains(aLF.First()) &&
2261                   aMapFaces.Contains(aLF.Last())) {
2262                 for (i = 1; i <= faces.Length(); i++) {
2263                   if (faces(i).IsEqual(aLF.First()) ||
2264                       faces(i).IsEqual(aLF.Last())) {
2265                     AddOrdinaryEdges(edges, faces(i), dummy, RemovedEdges);
2266                     faces.Remove(i);
2267                     i--;
2268                   }
2269                 }
2270               }
2271             }
2272           }
2273         } //if (!myAllowInternal)
2274         else { //internal edges are allowed
2275           // add multi-connected and keep edges as internal in new face
2276           TopTools_ListIteratorOfListOfShape it(aKeepEdges);
2277           for (; it.More(); it.Next()) {
2278             const TopoDS_Shape& aE = it.Value();
2279             edges.Append(aE.Oriented(TopAbs_INTERNAL));
2280           }
2281         }
2282       } //if (!aKeepEdges.IsEmpty())
2283     } //if (faces.Length() > 1)
2284
2285     TopTools_IndexedDataMapOfShapeListOfShape aMapEF;
2286     for (i = 1; i <= faces.Length(); i++)
2287       TopExp::MapShapesAndUniqueAncestors(faces(i), TopAbs_EDGE, TopAbs_FACE, aMapEF);
2288
2289     //Correct orientation of edges
2290     for (Standard_Integer ii = 1; ii <= edges.Length(); ii++)
2291     {
2292       const TopoDS_Shape& anEdge = edges (ii);
2293       Standard_Integer indE = aMapEF.FindIndex (anEdge);
2294       const TopTools_ListOfShape& aLF = aMapEF (indE);
2295       if (myAllowInternal &&
2296           myKeepShapes.Contains(anEdge) &&
2297           aLF.Extent() == 2)
2298         edges(ii).Orientation(TopAbs_INTERNAL);
2299
2300       if (anEdge.Orientation() != TopAbs_INTERNAL)
2301         edges (ii) = aMapEF.FindKey (indE);
2302     }
2303
2304     //Exclude internal edges
2305     TopTools_IndexedMapOfShape InternalEdges;
2306     Standard_Integer ind_e = 1;
2307     while (ind_e <= edges.Length())
2308     {
2309       const TopoDS_Shape& anEdge = edges(ind_e);
2310       if (anEdge.Orientation() == TopAbs_INTERNAL)
2311       {
2312         InternalEdges.Add(anEdge);
2313         edges.Remove(ind_e);
2314       }
2315       else
2316         ind_e++;
2317     }
2318
2319     if (RefFaceOrientation == TopAbs_REVERSED)
2320       for (Standard_Integer ii = 1; ii <= edges.Length(); ii++)
2321         edges(ii).Reverse();
2322     TopoDS_Face F_RefFace = RefFace;
2323     F_RefFace.Orientation(TopAbs_FORWARD);
2324
2325     // all faces collected in the sequence. Perform union of faces
2326     if (faces.Length() > 1)
2327     {
2328       Standard_Real CoordTol = Precision::Confusion();
2329
2330       TopTools_IndexedDataMapOfShapeListOfShape VEmap;
2331       for (Standard_Integer ind = 1; ind <= edges.Length(); ind++)
2332         TopExp::MapShapesAndUniqueAncestors(edges(ind), TopAbs_VERTEX, TopAbs_EDGE, VEmap);
2333
2334       //Perform relocating to new U-origin
2335       //Define boundaries in 2d space of RefFace
2336       if (Uperiod != 0.)
2337       {
2338         TopTools_MapOfShape edgesMap;
2339         CoordTol = ComputeMinEdgeSize(edges, F_RefFace, edgesMap);
2340         CoordTol /= 10.;
2341         CoordTol = Max(CoordTol, Precision::Confusion());
2342
2343         //try to find a real seam edge - if it exists, do nothing
2344         Standard_Boolean SeamFound = Standard_False;
2345         for (Standard_Integer ii = 1; ii <= faces.Length(); ii++)
2346         {
2347           const TopoDS_Face& face_ii = TopoDS::Face(faces(ii));
2348           TopoDS_Wire anOuterWire = BRepTools::OuterWire(face_ii);
2349           TopoDS_Iterator itw(anOuterWire);
2350           for (; itw.More(); itw.Next())
2351           {
2352             const TopoDS_Edge& anEdge = TopoDS::Edge(itw.Value());
2353             if (BRepTools::IsReallyClosed(anEdge, face_ii))
2354             {
2355               SeamFound = Standard_True;
2356               break;
2357             }
2358           }
2359         }
2360
2361         if (!SeamFound)
2362         {
2363           //try to find the origin of U in 2d space
2364           //so that all the faces are in [origin, origin + Uperiod]
2365           Standard_Real Umax;
2366           Standard_Integer i_face_max;
2367           FindFaceWithMaxUbound(faces, F_RefFace, edgesMap, Umax, i_face_max);
2368
2369           TopTools_MapOfShape UsedEdges;
2370           NCollection_DataMap<TopoDS_Shape, Handle(Geom2d_Curve)> EdgeNewPCurve;
2371
2372           //Relocate pcurves to new U-origin
2373           RelocatePCurvesToNewUorigin(edges, faces(i_face_max), F_RefFace, CoordTol, Uperiod,
2374                                       VEmap, EdgeNewPCurve, UsedEdges);
2375
2376           //PCurves from unused edges (may be degenerated edges)
2377           for (Standard_Integer ind = 1; ind <= edges.Length(); ind++)
2378           {
2379             const TopoDS_Edge& anEdge = TopoDS::Edge(edges(ind));
2380             if (!UsedEdges.Contains(anEdge))
2381             {
2382               Standard_Real fpar, lpar;
2383               Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface(anEdge, F_RefFace, fpar, lpar);
2384               aPCurve = new Geom2d_TrimmedCurve(aPCurve, fpar, lpar);
2385               EdgeNewPCurve.Bind(anEdge, aPCurve);
2386             }
2387           }
2388
2389           //Restore VEmap
2390           VEmap.Clear();
2391           for (Standard_Integer ind = 1; ind <= edges.Length(); ind++)
2392             TopExp::MapShapesAndUniqueAncestors(edges(ind), TopAbs_VERTEX, TopAbs_EDGE, VEmap);
2393
2394           //Find NewUmin and NewUmax
2395           Standard_Real NewUmin = RealLast(), NewUmax = RealFirst();
2396           for (Standard_Integer ii = 1; ii <= edges.Length(); ii++)
2397           {
2398             const Handle(Geom2d_Curve)& aPCurve = EdgeNewPCurve(edges(ii));
2399             UpdateBoundaries(aPCurve, aPCurve->FirstParameter(), aPCurve->LastParameter(),
2400                              NewUmin, NewUmax);
2401           }
2402
2403           if (NewUmax - NewUmin < Uperiod - CoordTol &&
2404               !(-Precision::Confusion() < NewUmin && NewUmin < Uperiod+Precision::Confusion() &&
2405                 -Precision::Confusion() < NewUmax && NewUmax < Uperiod+Precision::Confusion()))
2406           {
2407             //we can build a face without seam edge:
2408             //update the edges with earlier computed relocated pcurves
2409             //fitting into (NewUorigin, NewUorigin + Uperiod)
2410             Standard_Real umin, umax, vmin, vmax;
2411             aBaseSurface->Bounds(umin, umax, vmin, vmax);
2412             Standard_Real RestSpaceInU = Uperiod - (NewUmax - NewUmin);
2413             Standard_Real NewUorigin = NewUmin - RestSpaceInU/2;
2414             if (NewUorigin < umin)
2415               NewUorigin = umin;
2416             Handle(Geom_Surface) NewSurf;
2417             if (NewUorigin == umin)
2418               NewSurf = aBaseSurface;
2419             else
2420               NewSurf = new Geom_RectangularTrimmedSurface(aBaseSurface,
2421                                                            NewUorigin, NewUorigin + Uperiod,
2422                                                            Standard_True); //trim U
2423             TopoDS_Face OldRefFace = RefFace;
2424             Handle(Geom2d_Curve) NullPCurve;
2425             RefFace.Nullify();
2426             BB.MakeFace(RefFace, NewSurf, aBaseLocation, 0.);
2427             for (Standard_Integer ii = 1; ii <= edges.Length(); ii++)
2428             {
2429               TopoDS_Edge anEdge = TopoDS::Edge(edges(ii));
2430               if (MapEdgesWithTemporaryPCurves.Contains(anEdge))
2431                 BB.UpdateEdge(anEdge, NullPCurve, OldRefFace, 0.);
2432               const Handle(Geom2d_Curve)& aPCurve = EdgeNewPCurve(anEdge);
2433               BB.UpdateEdge(anEdge, aPCurve, RefFace, 0.);
2434             }
2435           }
2436         } //if (!SeamFound)
2437       } //if (Uperiod != 0.)
2438       ////////////////////////////////////
2439       F_RefFace = RefFace;
2440       F_RefFace.Orientation(TopAbs_FORWARD);
2441
2442       TopTools_SequenceOfShape NewFaces, NewWires;
2443
2444       if (Uperiod == 0)
2445       {
2446         //Set the "period" for closed non-periodic surface
2447         TopLoc_Location aLoc;
2448         Handle(Geom_Surface) aSurf = BRep_Tool::Surface(RefFace, aLoc);
2449         if (aSurf->IsKind(STANDARD_TYPE(Geom_RectangularTrimmedSurface)))
2450           aSurf = (Handle(Geom_RectangularTrimmedSurface)::DownCast(aSurf))->BasisSurface();
2451         Standard_Real Ufirst, Ulast, Vfirst, Vlast;
2452         aSurf->Bounds(Ufirst, Ulast, Vfirst, Vlast);
2453         if (aSurf->IsUClosed())
2454           Uperiod = Ulast - Ufirst;
2455       }
2456
2457       TopTools_MapOfShape UsedEdges;
2458
2459       Standard_Real FaceUmin = RealLast();
2460       for (Standard_Integer ii = 1; ii <= edges.Length(); ii++)
2461       {
2462         const TopoDS_Edge& anEdge = TopoDS::Edge(edges(ii));
2463         BRepAdaptor_Curve2d aBAcurve(anEdge, F_RefFace);
2464         gp_Pnt2d aFirstPoint = aBAcurve.Value(aBAcurve.FirstParameter());
2465         gp_Pnt2d aLastPoint  = aBAcurve.Value(aBAcurve.LastParameter());
2466         if (aFirstPoint.X() < FaceUmin)
2467           FaceUmin = aFirstPoint.X();
2468         if (aLastPoint.X() < FaceUmin)
2469           FaceUmin = aLastPoint.X();
2470       }
2471
2472       //Building new wires from <edges>
2473       //and build faces
2474       while (!edges.IsEmpty())
2475       {
2476         //try to find non-degenerated edge
2477         TopoDS_Edge StartEdge = TopoDS::Edge(edges(1));
2478         Standard_Integer istart = 1;
2479         while (BRep_Tool::Degenerated(StartEdge) &&
2480                istart < edges.Length())
2481         {
2482           istart++;
2483           StartEdge = TopoDS::Edge(edges(istart));
2484         }
2485
2486         TopoDS_Wire aNewWire;
2487         BB.MakeWire(aNewWire);
2488         BB.Add(aNewWire, StartEdge);
2489         RemoveEdgeFromMap(StartEdge, VEmap);
2490
2491         Standard_Real fpar, lpar;
2492         Handle(Geom2d_Curve) StartPCurve = BRep_Tool::CurveOnSurface(StartEdge, F_RefFace, fpar, lpar);
2493         TopoDS_Vertex StartVertex, CurVertex;
2494         TopExp::Vertices(StartEdge, StartVertex, CurVertex, Standard_True); //with orientation
2495         Standard_Real StartParam, CurParam;
2496         if (StartEdge.Orientation() == TopAbs_FORWARD)
2497         {
2498           StartParam = fpar; CurParam = lpar;
2499         }
2500         else
2501         {
2502           StartParam = lpar; CurParam = fpar;
2503         }
2504         gp_Pnt2d StartPoint = StartPCurve->Value(StartParam);
2505         gp_Pnt2d CurPoint   = StartPCurve->Value(CurParam);
2506
2507         TopoDS_Edge CurEdge = StartEdge;
2508         for (;;) //loop till the end of current new wire
2509         {
2510           TopoDS_Edge NextEdge;
2511           gp_Pnt2d NextPoint;
2512
2513           const TopTools_ListOfShape& Elist = VEmap.FindFromKey(CurVertex);
2514           TopTools_ListIteratorOfListOfShape itl(Elist);
2515           if (Elist.IsEmpty())
2516           {
2517             if (CurVertex.IsSame(StartVertex))
2518             {
2519               //Points of two vertices coincide in 3d but may be not in 2d
2520               if (Uperiod != 0. &&
2521                   Abs(StartPoint.X() - CurPoint.X()) > Uperiod/2) //end of parametric space
2522               {
2523                 //<edges> do not contain seams => we must reconstruct the seam up to <NextEdge>
2524                 gp_Pnt2d StartOfNextEdge;
2525                 TopoDS_Vertex LastVertexOfSeam;
2526                 ReconstructMissedSeam(edges, RemovedEdges, UsedEdges, F_RefFace, CurVertex,
2527                                       CurPoint, Uperiod, FaceUmin, CoordTol,
2528                                       NextEdge, aNewWire, NextPoint,
2529                                       StartOfNextEdge, LastVertexOfSeam, VEmap);
2530               }
2531               else
2532               {
2533                 break; //end of wire
2534               }
2535             }
2536           }
2537
2538           if (NextEdge.IsNull())
2539           {
2540             Standard_Boolean EndOfWire = Standard_False;
2541
2542             TopTools_ListOfShape TmpElist, TrueElist;
2543             //<TrueElist> will be the list of candidates to become <NextEdge>
2544             for (itl.Initialize(Elist); itl.More(); itl.Next())
2545             {
2546               const TopoDS_Edge& anEdge = TopoDS::Edge(itl.Value());
2547               if (UsedEdges.Contains(anEdge))
2548                 continue;
2549               TopoDS_Vertex aFirstVertex = TopExp::FirstVertex(anEdge, Standard_True);
2550               if (!aFirstVertex.IsSame(CurVertex))
2551                 continue;
2552               TmpElist.Append(anEdge);
2553             }
2554             if (TmpElist.Extent() <= 1 ||
2555                 Uperiod != 0.)
2556               TrueElist.Assign(TmpElist);
2557             else
2558             {
2559               //we must choose the closest direction - the biggest angle
2560               Standard_Real MaxAngle = RealFirst();
2561               TopoDS_Edge TrueEdge;
2562               Handle(Geom2d_Curve) CurPCurve = BRep_Tool::CurveOnSurface(CurEdge, F_RefFace, fpar, lpar);
2563               CurParam = (CurEdge.Orientation() == TopAbs_FORWARD)? lpar : fpar;
2564               gp_Vec2d CurDir;
2565               CurPCurve->D1(CurParam, CurPoint, CurDir);
2566               CurDir.Normalize();
2567               if (CurEdge.Orientation() == TopAbs_REVERSED)
2568                 CurDir.Reverse();
2569               for (itl.Initialize(TmpElist); itl.More(); itl.Next())
2570               {
2571                 const TopoDS_Edge& anEdge = TopoDS::Edge(itl.Value());
2572                 Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface(anEdge, F_RefFace, fpar, lpar);
2573                 Standard_Real aParam = (anEdge.Orientation() == TopAbs_FORWARD)? fpar : lpar;
2574                 gp_Pnt2d aPoint;
2575                 gp_Vec2d aDir;
2576                 aPCurve->D1(aParam, aPoint, aDir);
2577                 aDir.Normalize();
2578                 if (anEdge.Orientation() == TopAbs_REVERSED)
2579                   aDir.Reverse();
2580                 Standard_Real anAngle = CurDir.Angle(aDir);
2581                 if (anAngle > MaxAngle)
2582                 {
2583                   MaxAngle = anAngle;
2584                   TrueEdge = anEdge;
2585                 }
2586               }
2587               TrueElist.Append(TrueEdge);
2588             }
2589
2590             //Find next edge in TrueElist
2591             for (itl.Initialize(TrueElist); itl.More(); itl.Next())
2592             {
2593               const TopoDS_Edge& anEdge = TopoDS::Edge(itl.Value());
2594
2595               Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface(anEdge, F_RefFace, fpar, lpar);
2596               Standard_Real aParam = (anEdge.Orientation() == TopAbs_FORWARD)? fpar : lpar;
2597               gp_Pnt2d aPoint = aPCurve->Value(aParam);
2598               Standard_Real Diff = Abs(aPoint.X() - CurPoint.X());
2599               if (Uperiod != 0. &&
2600                   Diff > CoordTol &&
2601                   Abs(Diff - Uperiod) > CoordTol) //may be is is a deg.vertex
2602                 continue;
2603
2604               //Check: may be <CurPoint> and <aPoint> are on Period from each other
2605               if (Uperiod != 0. && Diff > Uperiod/2) //end of parametric space
2606               {
2607                 //<edges> do not contain seams => we must reconstruct the seam up to <NextEdge>
2608                 gp_Pnt2d StartOfNextEdge;
2609                 TopoDS_Vertex LastVertexOfSeam;
2610                 ReconstructMissedSeam(edges, RemovedEdges, UsedEdges, F_RefFace, CurVertex,
2611                                       CurPoint, Uperiod, FaceUmin, CoordTol,
2612                                       NextEdge, aNewWire, NextPoint,
2613                                       StartOfNextEdge, LastVertexOfSeam, VEmap);
2614
2615                 //Check: may be it is the end
2616                 if (LastVertexOfSeam.IsSame(StartVertex) &&
2617                     Abs(StartPoint.X() - StartOfNextEdge.X()) < Uperiod/2)
2618                   EndOfWire = Standard_True;
2619
2620                 break;
2621               } //if (Uperiod != 0. && Abs(aPoint.X() - CurPoint.X()) > Uperiod/2)
2622               else
2623               {
2624                 NextEdge = anEdge;
2625                 Standard_Real LastParam = (NextEdge.Orientation() == TopAbs_FORWARD)? lpar : fpar;
2626                 NextPoint = aPCurve->Value(LastParam);
2627                 break;
2628               }
2629             } //for (itl.Initialize(TrueElist); itl.More(); itl.Next())
2630
2631             if (EndOfWire)
2632               break;
2633           }
2634
2635           if (NextEdge.IsNull())
2636           {
2637             //throw Standard_ConstructionError("Construction of unified wire failed: no proper edge found");
2638             return;
2639           }
2640           else
2641           {
2642             CurPoint = NextPoint;
2643             CurEdge = NextEdge;
2644             CurVertex = TopExp::LastVertex(CurEdge, Standard_True); //with orientation
2645             BB.Add(aNewWire, CurEdge);
2646             UsedEdges.Add(CurEdge);
2647             RemoveEdgeFromMap(CurEdge, VEmap);
2648           }
2649         } //for (;;)
2650         aNewWire.Closed(Standard_True);
2651         UsedEdges.Add(StartEdge);
2652
2653         //Remove used edges from sequence
2654         Standard_Integer ind = 1;
2655         while (ind <= edges.Length())
2656         {
2657           if (UsedEdges.Contains(edges(ind)))
2658             edges.Remove(ind);
2659           else
2660             ind++;
2661         }
2662
2663         //add just built wire to current face or save it in the sequence of wires
2664         Standard_Boolean EdgeOnBoundOfSurfFound = Standard_False;
2665         TopoDS_Iterator itw(aNewWire);
2666         for (; itw.More(); itw.Next())
2667         {
2668           const TopoDS_Edge& anEdge = TopoDS::Edge(itw.Value());
2669           if (BRep_Tool::IsClosed(anEdge, RefFace))
2670           {
2671             EdgeOnBoundOfSurfFound = Standard_True;
2672             break;
2673           }
2674         }
2675         if (EdgeOnBoundOfSurfFound) //this wire can not be a hole
2676         {
2677           TopLoc_Location aLoc;
2678           Handle(Geom_Surface) aSurf = BRep_Tool::Surface(RefFace, aLoc);
2679           TopoDS_Face aResult;
2680           BB.MakeFace(aResult,aSurf,aLoc,0);
2681           BB.Add(aResult, aNewWire);
2682           aResult.Orientation(RefFaceOrientation);
2683           NewFaces.Append(aResult);
2684         }
2685         else //may be this wire is a hole
2686         {
2687           NewWires.Append(aNewWire);
2688         }
2689       } //while (!edges.IsEmpty())
2690
2691       //Build wires from internal edges
2692       TopTools_IndexedDataMapOfShapeListOfShape IntVEmap;
2693       for (Standard_Integer ii = 1; ii <= InternalEdges.Extent(); ii++)
2694         TopExp::MapShapesAndAncestors(InternalEdges(ii), TopAbs_VERTEX, TopAbs_EDGE, IntVEmap);
2695       TopTools_SequenceOfShape InternalWires;
2696       while (!InternalEdges.IsEmpty())
2697       {
2698         TopoDS_Edge aFirstEdge = TopoDS::Edge(InternalEdges(1));
2699         InternalEdges.RemoveFromIndex(1);
2700         TopoDS_Wire anInternalWire;
2701         BB.MakeWire(anInternalWire);
2702         BB.Add(anInternalWire, aFirstEdge);
2703         TopoDS_Edge EndEdges [2];
2704         EndEdges[0] = EndEdges[1] = aFirstEdge;
2705         TopoDS_Vertex VV [2];
2706         TopExp::Vertices(aFirstEdge, VV[0], VV[1]);
2707         for (;;)
2708         {
2709           if (VV[0].IsSame(VV[1])) //closed wire
2710             break;
2711           Standard_Boolean found = Standard_False;
2712           for (Standard_Integer ii = 0; ii < 2; ii++)
2713           {
2714             const TopTools_ListOfShape& Elist = IntVEmap.FindFromKey(VV[ii]);
2715             TopTools_ListIteratorOfListOfShape itl(Elist);
2716             for (; itl.More(); itl.Next())
2717             {
2718               TopoDS_Edge anEdge = TopoDS::Edge(itl.Value());
2719               if (anEdge.IsSame(EndEdges[ii]))
2720                 continue;
2721               found = Standard_True;
2722               InternalEdges.RemoveKey(anEdge);
2723               BB.Add(anInternalWire, anEdge);
2724               TopoDS_Vertex V1, V2;
2725               TopExp::Vertices(anEdge, V1, V2);
2726               VV[ii] = (V1.IsSame(VV[ii]))? V2 : V1;
2727               EndEdges[ii] = anEdge;
2728               break;
2729             }
2730           }
2731           if (!found) //end of open wire
2732             break;
2733         }
2734         InternalWires.Append(anInternalWire);
2735       }
2736
2737       //Insert new faces instead of old ones
2738       if (NewFaces.IsEmpty())
2739       {
2740         //one face without seam
2741         TopLoc_Location aLoc;
2742         Handle(Geom_Surface) aSurf = BRep_Tool::Surface(RefFace, aLoc);
2743         TopoDS_Face aResult;
2744         BB.MakeFace(aResult,aSurf,aLoc,0.);
2745         for (Standard_Integer ii = 1; ii <= NewWires.Length(); ii++)
2746           BB.Add(aResult, NewWires(ii));
2747         for (Standard_Integer ii = 1; ii <= InternalWires.Length(); ii++)
2748           BB.Add(aResult, InternalWires(ii));
2749         aResult.Orientation(RefFaceOrientation);
2750         myContext->Merge(faces, aResult);
2751       }
2752       else if (NewFaces.Length() == 1)
2753       {
2754         TopoDS_Shape aNewFace = NewFaces(1).Oriented (TopAbs_FORWARD);
2755         for (Standard_Integer ii = 1; ii <= NewWires.Length(); ii++)
2756           BB.Add(aNewFace, NewWires(ii));
2757         for (Standard_Integer ii = 1; ii <= InternalWires.Length(); ii++)
2758           BB.Add(aNewFace, InternalWires(ii));
2759         myContext->Merge(faces, NewFaces(1));
2760       }
2761       else
2762       {
2763         //Insert new wires and internal wires into correspondent faces
2764         InsertWiresIntoFaces(NewWires, NewFaces, RefFace);
2765         InsertWiresIntoFaces(InternalWires, NewFaces, RefFace);
2766
2767         NCollection_Sequence<TopTools_MapOfShape> Emaps;
2768         for (Standard_Integer ii = 1; ii <= faces.Length(); ii++)
2769         {
2770           TopTools_MapOfShape aEmap;
2771           TopExp::MapShapes(faces(ii), aEmap);
2772           Emaps.Append(aEmap);
2773         }
2774         for (Standard_Integer ii = 1; ii <= NewFaces.Length(); ii++)
2775         {
2776           TopTools_SequenceOfShape facesForThisFace;
2777           TopTools_MapOfShape UsedFaces;
2778           TopExp_Explorer Explo(NewFaces(ii), TopAbs_EDGE);
2779           for (; Explo.More(); Explo.Next())
2780           {
2781             const TopoDS_Edge& anEdge = TopoDS::Edge(Explo.Current());
2782             if (BRep_Tool::Degenerated(anEdge) ||
2783                 BRep_Tool::IsClosed(anEdge, RefFace))
2784               continue;
2785             Standard_Integer jj;
2786             for (jj = 1; jj <= Emaps.Length(); jj++)
2787               if (Emaps(jj).Contains(anEdge))
2788                 break;
2789             if (UsedFaces.Add(faces(jj)))
2790               facesForThisFace.Append(faces(jj));
2791           }
2792           myContext->Merge(facesForThisFace, NewFaces(ii));
2793         }
2794       }
2795     } //if (faces.Length() > 1)
2796   } // end processing each face
2797 }
2798
2799 //=======================================================================
2800 //function : UnifyEdges
2801 //purpose  :
2802 //=======================================================================
2803 void ShapeUpgrade_UnifySameDomain::UnifyEdges()
2804 {
2805   TopoDS_Shape aRes = myContext->Apply(myShape);
2806   // creating map of edge faces
2807   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgeFaces;
2808   TopExp::MapShapesAndAncestors(aRes, TopAbs_EDGE, TopAbs_FACE, aMapEdgeFaces);
2809   // creating map of vertex edges
2810   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgesVertex;
2811   TopExp::MapShapesAndUniqueAncestors(aRes, TopAbs_VERTEX, TopAbs_EDGE, aMapEdgesVertex);
2812   // creating map of vertex faces
2813   TopTools_IndexedDataMapOfShapeListOfShape aVFmap;
2814   TopExp::MapShapesAndUniqueAncestors(aRes, TopAbs_VERTEX, TopAbs_FACE, aVFmap);
2815
2816   if (mySafeInputMode)
2817     UpdateMapOfShapes(myKeepShapes, myContext);
2818
2819   // Sequence of the edges of the shape
2820   TopTools_SequenceOfShape aSeqEdges;
2821   const Standard_Integer aNbE = aMapEdgeFaces.Extent();
2822   for (Standard_Integer i = 1; i <= aNbE; ++i)
2823     aSeqEdges.Append(aMapEdgeFaces.FindKey(i));
2824
2825   // Prepare map of shared vertices (with the number of connected edges greater then 2)
2826   TopTools_MapOfShape aSharedVert;
2827   CheckSharedVertices(aSeqEdges, aMapEdgesVertex, myKeepShapes, aSharedVert);
2828   // Merge the edges avoiding removal of the shared vertices
2829   Standard_Boolean isMerged = MergeSeq(aSeqEdges, aVFmap, myAngTol, myLinTol, myConcatBSplines,
2830                                        mySafeInputMode, myContext, aSharedVert);
2831   // Collect faces to rebuild
2832   TopTools_IndexedMapOfShape aChangedFaces;
2833   if (isMerged)
2834   {
2835     for (Standard_Integer i = 1; i <= aNbE; ++i)
2836     {
2837       const TopoDS_Shape& aE = aMapEdgeFaces.FindKey(i);
2838       if (myContext->IsRecorded(aE))
2839       {
2840         TopTools_ListIteratorOfListOfShape it(aMapEdgeFaces(i));
2841         for (; it.More(); it.Next())
2842           aChangedFaces.Add(it.Value());
2843       }
2844     }
2845   }
2846
2847   // fix changed faces and replace them in the local context
2848   Standard_Real aPrec = Precision::Confusion();
2849   for (Standard_Integer i = 1; i <= aChangedFaces.Extent(); i++) {
2850     TopoDS_Face aFace = TopoDS::Face(myContext->Apply(aChangedFaces.FindKey(i)));
2851     if (aFace.IsNull())
2852       continue;
2853
2854     // for a planar face create and store pcurve of edge on face
2855     // to speed up all operations; but this is allowed only when non-safe mode in force
2856     if (!mySafeInputMode)
2857     {
2858       TopLoc_Location aLoc;
2859       Handle(Geom_Surface) aSurface = BRep_Tool::Surface(aFace, aLoc);
2860       aSurface = ClearRts(aSurface);
2861       if (aSurface->IsKind(STANDARD_TYPE(Geom_Plane)))
2862       {
2863         TopTools_ListOfShape aLE;
2864         for (TopExp_Explorer anEx(aFace, TopAbs_EDGE); anEx.More(); anEx.Next())
2865           aLE.Append(anEx.Current());
2866         BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFace);
2867       }
2868     }
2869
2870     ShapeFix_Face sff(aFace);
2871     if (mySafeInputMode)
2872       sff.SetContext(myContext);
2873     sff.SetPrecision(aPrec);
2874     sff.SetMinTolerance(aPrec);
2875     sff.SetMaxTolerance(Max(1., aPrec*1000.));
2876     sff.FixOrientationMode() = 0;
2877     sff.FixAddNaturalBoundMode() = 0;
2878     sff.FixIntersectingWiresMode() = 0;
2879     sff.FixLoopWiresMode() = 0;
2880     sff.FixSplitFaceMode() = 0;
2881     sff.FixPeriodicDegeneratedMode() = 0;
2882     SetFixWireModes(sff);
2883     sff.Perform();
2884     TopoDS_Shape aNewFace = sff.Face();
2885     myContext->Replace(aFace,aNewFace);
2886   }
2887
2888   if (aChangedFaces.Extent() > 0) {
2889     // fix changed shell and replace it in the local context
2890     TopoDS_Shape aRes1 = myContext->Apply(aRes);
2891     Standard_Boolean isChanged = Standard_False;
2892     TopExp_Explorer expsh;
2893     for (expsh.Init(aRes1, TopAbs_SHELL); expsh.More(); expsh.Next()) {
2894       TopoDS_Shell aShell = TopoDS::Shell(expsh.Current());
2895       Handle(ShapeFix_Shell) sfsh = new ShapeFix_Shell;
2896       sfsh->FixFaceOrientation(aShell);
2897       TopoDS_Shape aNewShell = sfsh->Shell();
2898       if (!aNewShell.IsSame(aShell)) {
2899         myContext->Replace(aShell, aNewShell);
2900         isChanged = Standard_True;
2901       }
2902     }
2903     if (isChanged)
2904       aRes1 = myContext->Apply(aRes1);
2905     myContext->Replace(myShape, aRes1);
2906   }
2907
2908   myShape = myContext->Apply(myShape);
2909 }
2910
2911 //=======================================================================
2912 //function : Build
2913 //purpose  : builds the resulting shape
2914 //=======================================================================
2915 void ShapeUpgrade_UnifySameDomain::Build()
2916 {
2917   if (myUnifyFaces)
2918     UnifyFaces();
2919   if (myUnifyEdges)
2920     UnifyEdges();
2921
2922   // Fill the history of modifications during the operation
2923   FillHistory();
2924 }
2925
2926 //=======================================================================
2927 //function : FillHistory
2928 //purpose  : Fill the history of modifications during the operation
2929 //=======================================================================
2930 void ShapeUpgrade_UnifySameDomain::FillHistory()
2931 {
2932   if (myHistory.IsNull())
2933     // History is not requested
2934     return;
2935
2936   // Only Vertices, Edges and Faces can be modified during unification.
2937   // Thus, only these kind of shapes should be checked.
2938
2939   // Get history from the context.
2940   // It contains all modifications of the operation. Some of these
2941   // modifications become not relevant and should be filtered.
2942   Handle(BRepTools_History) aCtxHistory = myContext->History();
2943
2944   // Explore the history of the context and fill
2945   // the history of UnifySameDomain algorithm
2946   Handle(BRepTools_History) aUSDHistory = new BRepTools_History();
2947
2948   // Map all Vertices, Edges, Faces and Solids in the input shape
2949   TopTools_IndexedMapOfShape aMapInputShape;
2950   TopExp::MapShapes(myInitShape, TopAbs_VERTEX, aMapInputShape);
2951   TopExp::MapShapes(myInitShape, TopAbs_EDGE  , aMapInputShape);
2952   TopExp::MapShapes(myInitShape, TopAbs_FACE  , aMapInputShape);
2953   TopExp::MapShapes(myInitShape, TopAbs_SOLID , aMapInputShape);
2954
2955   // Map all Vertices, Edges, Faces and Solids in the result shape
2956   TopTools_IndexedMapOfShape aMapResultShapes;
2957   TopExp::MapShapes(myShape, TopAbs_VERTEX, aMapResultShapes);
2958   TopExp::MapShapes(myShape, TopAbs_EDGE  , aMapResultShapes);
2959   TopExp::MapShapes(myShape, TopAbs_FACE  , aMapResultShapes);
2960   TopExp::MapShapes(myShape, TopAbs_SOLID , aMapResultShapes);
2961
2962   // Iterate on all input shapes and get their modifications
2963   Standard_Integer i, aNb = aMapInputShape.Extent();
2964   for (i = 1; i <= aNb; ++i)
2965   {
2966     const TopoDS_Shape& aS = aMapInputShape(i);
2967
2968     // Check the shape itself to be present in the result
2969     if (aMapResultShapes.Contains(aS))
2970     {
2971       // The shape is present in the result as is, thus has not been modified
2972       continue;
2973     }
2974
2975     // Check if the shape has been modified during the operation
2976     const TopTools_ListOfShape& aLSImages = aCtxHistory->Modified(aS);
2977     if (aLSImages.IsEmpty())
2978     {
2979       // The shape has not been modified and not present in the result,
2980       // thus it has been removed
2981       aUSDHistory->Remove(aS);
2982       continue;
2983     }
2984
2985     // Check the images of the shape to be present in the result
2986     Standard_Boolean bRemoved = Standard_True;
2987     TopTools_ListIteratorOfListOfShape aItLSIm(aLSImages);
2988     for (; aItLSIm.More(); aItLSIm.Next())
2989     {
2990       const TopoDS_Shape& aSIm = aItLSIm.Value();
2991       if (aMapResultShapes.Contains(aSIm))
2992       {
2993         if (!aSIm.IsSame(aS))
2994           // Image is found in the result, thus the shape has been modified
2995           aUSDHistory->AddModified(aS, aSIm);
2996         bRemoved = Standard_False;
2997       }
2998     }
2999
3000     if (bRemoved)
3001     {
3002       // No images are found in the result, thus the shape has been removed
3003       aUSDHistory->Remove(aS);
3004     }
3005   }
3006
3007   // Merge the history of the operation into global history
3008   myHistory->Merge(aUSDHistory);
3009 }