src/BlockFix/BlockFix_UnionEdges.cxx

   1 // Copyright (C) 2007-2021  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License, or (at your option) any later version.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22
  23 // File:      BlockFix_UnionEdges.cxx
  24 // Created:   07.12.04 15:27:30
  25 // Author:    Sergey KUUL
  26
  27 #include <BlockFix_UnionEdges.hxx>
  28
  29 #include <ShapeAnalysis_Edge.hxx>
  30
  31 #include <ShapeBuild_ReShape.hxx>
  32
  33 #include <ShapeFix_Face.hxx>
  34 #include <ShapeFix_Shell.hxx>
  35
  36 #include <BRep_Builder.hxx>
  37 #include <BRep_CurveRepresentation.hxx>
  38 #include <BRep_ListIteratorOfListOfCurveRepresentation.hxx>
  39 #include <BRep_TEdge.hxx>
  40 #include <BRep_Tool.hxx>
  41 #include <BRepLib.hxx>
  42 #include <BRepLib_MakeEdge.hxx>
  43 #include <BRepTools_WireExplorer.hxx>
  44
  45 #include <TopExp.hxx>
  46 #include <TopExp_Explorer.hxx>
  47
  48 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  49 #include <TopTools_ListOfShape.hxx>
  50 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  51 #include <TopTools_MapOfShape.hxx>
  52 #include <TopTools_ListIteratorOfListOfShape.hxx>
  53 #include <TopTools_SequenceOfShape.hxx>
  54
  55 #include <TopoDS.hxx>
  56 #include <TopoDS_Edge.hxx>
  57 #include <TopoDS_Face.hxx>
  58 #include <TopoDS_Shell.hxx>
  59 #include <TopoDS_Vertex.hxx>
  60 #include <TopoDS_Shape.hxx>
  61
  62 #include <GC_MakeCircle.hxx>
  63
  64 #include <Geom_BezierCurve.hxx>
  65 #include <Geom_BSplineCurve.hxx>
  66 #include <Geom_Circle.hxx>
  67 #include <Geom_Curve.hxx>
  68 #include <Geom_Line.hxx>
  69 #include <Geom_TrimmedCurve.hxx>
  70 #include <GeomConvert.hxx>
  71 #include <GeomConvert_CompCurveToBSplineCurve.hxx>
  72
  73 #include <Geom2dConvert.hxx>
  74 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
  75 #include <Geom2d_TrimmedCurve.hxx>
  76 #include <Geom2d_BSplineCurve.hxx>
  77
  78 #include <TColGeom_SequenceOfSurface.hxx>
  79 #include <TColGeom_Array1OfBSplineCurve.hxx>
  80 #include <TColGeom_HArray1OfBSplineCurve.hxx>
  81 #include <TColGeom2d_Array1OfBSplineCurve.hxx>
  82 #include <TColGeom2d_HArray1OfBSplineCurve.hxx>
  83 #include <TColGeom2d_SequenceOfBoundedCurve.hxx>
  84 #include <TColStd_Array1OfReal.hxx>
  85 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  86 #include <TColStd_ListOfInteger.hxx>
  87 #include <TColStd_MapOfInteger.hxx>
  88
  89 #include "utilities.h"
  90
  91 //=======================================================================
  92 //function : IsToMerge
  93 //purpose  : This method return Standard_True if two edges have common
  94 //           vertex. This vertex is returned by output parameter. The
  95 //           difference with the method TopExp::CommonVertex is only in
  96 //           the case if there are two common vertices. In this case
  97 //           this method returns the last vertex of theEdge1, not the first
  98 //           one that TopExp::CommonVertex does.
  99 //=======================================================================
 100 static Standard_Boolean GetCommonVertex(const TopoDS_Edge   &theEdge1,
 101                                         const TopoDS_Edge   &theEdge2,
 102                                               TopoDS_Vertex &theCommon)
 103 {
 104   Standard_Boolean   isFound = Standard_True;
 105   ShapeAnalysis_Edge aSae;
 106   TopoDS_Vertex      aVF1 = aSae.FirstVertex(theEdge1);
 107   TopoDS_Vertex      aVL1 = aSae.LastVertex(theEdge1);
 108   TopoDS_Vertex      aVF2 = aSae.FirstVertex(theEdge2);
 109   TopoDS_Vertex      aVL2 = aSae.LastVertex(theEdge2);
 110
 111   if (aVL1.IsSame(aVF2) || aVL1.IsSame(aVL2)) {
 112     theCommon = aVL1;
 113   } else if (aVF1.IsSame(aVL2) || aVF1.IsSame(aVF2)) {
 114     theCommon = aVF1;
 115   } else {
 116     theCommon.Nullify();
 117     isFound = Standard_False;
 118   }
 119
 120   return isFound;
 121 }
 122
 123 //=======================================================================
 124 //function : IsToMerge
 125 //purpose  : This method return Standard_True if two consequent edges can
 126 //           be merged. The edges can be merged if:
 127 //             1. They belong to same faces.
 128 //             2. They either both seam or both not seam on each face.
 129 //             3. There are no another edges (e.g. seam) on each common face
 130 //                that are connected to the common vertex of two edges.
 131 //             4. They are based on coincident lines, or:
 132 //             5. They are based on coincident circles, or:
 133 //             6. They are based on either Bezier of BSplines.
 134 //=======================================================================
 135 static Standard_Boolean IsToMerge
 136     (const TopoDS_Edge                               &theEdge1,
 137      const TopoDS_Edge                               &theEdge2,
 138      const TopTools_IndexedDataMapOfShapeListOfShape &theMapEdgeFaces,
 139      const Standard_Real                              theTolerance)
 140 {
 141   Standard_Boolean aResult  = Standard_False;
 142   Standard_Boolean isDegen1 = BRep_Tool::Degenerated(theEdge1);
 143   Standard_Boolean isDegen2 = BRep_Tool::Degenerated(theEdge2);
 144
 145   if (isDegen1 && isDegen2) {
 146     // Both of edges are degenerated.
 147     aResult = Standard_True;
 148   } else if (!isDegen1 && !isDegen2) {
 149     // Both of edges are not degenerated.
 150     // Check if they belong to the same faces.
 151     Standard_Boolean isSame = Standard_False;
 152     Standard_Boolean has1   = theMapEdgeFaces.Contains(theEdge1);
 153     Standard_Boolean has2   = theMapEdgeFaces.Contains(theEdge2);
 154
 155     if (has1 && has2) {
 156       const TopTools_ListOfShape &aLst1 = theMapEdgeFaces.FindFromKey(theEdge1);
 157       const TopTools_ListOfShape &aLst2 = theMapEdgeFaces.FindFromKey(theEdge2);
 158
 159       if (aLst1.Extent() == aLst2.Extent()) {
 160         TopTools_ListIteratorOfListOfShape anIter1(aLst1);
 161
 162         isSame = Standard_True;
 163
 164         for (; anIter1.More() && isSame; anIter1.Next()) {
 165           TopoDS_Face aFace1 = TopoDS::Face(anIter1.Value());
 166           TopTools_ListIteratorOfListOfShape  anIter2(aLst2);
 167
 168           for (; anIter2.More(); anIter2.Next()) {
 169             if (aFace1.IsSame(anIter2.Value())) {
 170               // Same face is detected. Break the loop.
 171               // Check if edges either both seam or both not seam on this face.
 172               Standard_Boolean isSeam1 = BRep_Tool::IsClosed(theEdge1, aFace1);
 173               Standard_Boolean isSeam2 = BRep_Tool::IsClosed(theEdge2, aFace1);
 174
 175               isSame = (isSeam1 && isSeam2) || (isSeam1 == isSeam2);
 176
 177               if (isSame) {
 178                 // Check if there are no other edges (e.g. seam) on this face
 179                 // that are connected to the common vertex.
 180                 TopoDS_Vertex aVCommon;
 181
 182                 if (GetCommonVertex(theEdge1, theEdge2, aVCommon)) {
 183                   TopTools_IndexedDataMapOfShapeListOfShape aMapVE;
 184
 185                   TopExp::MapShapesAndAncestors
 186                     (aFace1, TopAbs_VERTEX, TopAbs_EDGE, aMapVE);
 187
 188                   if (aMapVE.Contains(aVCommon)) {
 189                     TopTools_ListIteratorOfListOfShape
 190                       anItE(aMapVE.FindFromKey(aVCommon));
 191
 192                     for (; anItE.More(); anItE.Next()) {
 193                       const TopoDS_Shape &anEdge = anItE.Value();
 194
 195                       if (!theEdge1.IsSame(anEdge) &&
 196                           !theEdge2.IsSame(anEdge)) {
 197                         // There is another edge that shares the common vertex.
 198                         // Nothing to merge.
 199                         isSame = Standard_False;
 200                         break;
 201                       }
 202                     }
 203                   } else {
 204                     // Common vertex doesn't belong to the face.
 205                     // Nothing to merge. NEVERREACHED.
 206                     isSame = Standard_False;
 207                   }
 208                 } else {
 209                   // No common vertex. Nothing to merge. NEVERREACHED.
 210                   isSame = Standard_False;
 211                 }
 212               }
 213
 214               break;
 215             }
 216           }
 217
 218           if (isSame && !anIter2.More()) {
 219             // No same face is detected. Break the loop.
 220             isSame = Standard_False;
 221             break;
 222           }
 223         }
 224       }
 225     } else {
 226       isSame = (has1 == has2); // True if the both of has are negative.
 227     }
 228
 229     if (isSame) {
 230       // Check edges geometry.
 231       Standard_Real aFP1;
 232       Standard_Real aFP2;
 233       Standard_Real aLP1;
 234       Standard_Real aLP2;
 235       Handle(Geom_Curve) aC3d1 = BRep_Tool::Curve(theEdge1, aFP1, aLP1);
 236       Handle(Geom_Curve) aC3d2 = BRep_Tool::Curve(theEdge2, aFP2, aLP2);
 237
 238       if (aC3d1.IsNull() == Standard_False &&
 239           aC3d2.IsNull() == Standard_False) {
 240         // Get the basis curves.
 241         while(aC3d1->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 242           Handle(Geom_TrimmedCurve) aTc =
 243             Handle(Geom_TrimmedCurve)::DownCast(aC3d1);
 244           aC3d1 = aTc->BasisCurve();
 245         }
 246
 247         while(aC3d2->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 248           Handle(Geom_TrimmedCurve) aTc =
 249             Handle(Geom_TrimmedCurve)::DownCast(aC3d2);
 250           aC3d2 = aTc->BasisCurve();
 251         }
 252
 253         if(aC3d1->IsKind(STANDARD_TYPE(Geom_Line)) &&
 254            aC3d2->IsKind(STANDARD_TYPE(Geom_Line))) {
 255           // Two curves are lines.
 256           Handle(Geom_Line) aL1 = Handle(Geom_Line)::DownCast(aC3d1);
 257           Handle(Geom_Line) aL2 = Handle(Geom_Line)::DownCast(aC3d2);
 258           gp_Dir aDir1 = aL1->Position().Direction();
 259           gp_Dir aDir2 = aL2->Position().Direction();
 260
 261           if(aDir1.IsParallel(aDir2, theTolerance)) {
 262             // Two coincident lines.
 263             aResult = Standard_True;
 264           }
 265         } else if(aC3d1->IsKind(STANDARD_TYPE(Geom_Circle)) &&
 266                   aC3d2->IsKind(STANDARD_TYPE(Geom_Circle))) {
 267           // Two curves are circles.
 268           Handle(Geom_Circle) aC1 = Handle(Geom_Circle)::DownCast(aC3d1);
 269           Handle(Geom_Circle) aC2 = Handle(Geom_Circle)::DownCast(aC3d2);
 270           gp_Pnt aP01 = aC1->Location();
 271           gp_Pnt aP02 = aC2->Location();
 272
 273           if (aP01.Distance(aP02) <= Precision::Confusion()) {
 274             // Two coincident circles.
 275             aResult = Standard_True;
 276           }
 277         } else if (aC3d1->IsKind(STANDARD_TYPE(Geom_BSplineCurve)) ||
 278                    aC3d1->IsKind(STANDARD_TYPE(Geom_BezierCurve))) {
 279           if (aC3d2->IsKind(STANDARD_TYPE(Geom_BSplineCurve)) ||
 280               aC3d2->IsKind(STANDARD_TYPE(Geom_BezierCurve))) {
 281             // Both of the curves are either bezier or BSplines.
 282             aResult = Standard_True;
 283           }
 284         }
 285       }
 286     }
 287   }
 288
 289   return aResult;
 290 }
 291
 292 //=======================================================================
 293 //function : BlockFix_UnionEdges()
 294 //purpose  : Constructor
 295 //=======================================================================
 296 BlockFix_UnionEdges::BlockFix_UnionEdges (  )
 297 {
 298 }
 299
 300 //=======================================================================
 301 //function : GlueEdgesWithPCurves
 302 //purpose  : Glues the pcurves of the sequence of edges
 303 //           and glues their 3d curves
 304 //=======================================================================
 305 static TopoDS_Edge GlueEdgesWithPCurves(const TopTools_SequenceOfShape& aChain,
 306                                         const TopoDS_Vertex& FirstVertex,
 307                                         const TopoDS_Vertex& LastVertex)
 308 {
 309   Standard_Integer i, j;
 310
 311   TopoDS_Edge FirstEdge = TopoDS::Edge(aChain(1));
 312   //TColGeom2d_SequenceOfCurve PCurveSeq;
 313   TColGeom_SequenceOfSurface SurfSeq;
 314   //TopTools_SequenceOfShape LocSeq;
 315
 316   BRep_ListIteratorOfListOfCurveRepresentation itr( (Handle(BRep_TEdge)::DownCast(FirstEdge.TShape()))->Curves() );
 317   for (; itr.More(); itr.Next())
 318   {
 319     Handle(BRep_CurveRepresentation) CurveRep = itr.Value();
 320     if (CurveRep->IsCurveOnSurface())
 321     {
 322       //PCurveSeq.Append(CurveRep->PCurve());
 323       SurfSeq.Append(CurveRep->Surface());
 324       /*
 325       TopoDS_Shape aLocShape;
 326       aLocShape.Location(CurveRep->Location());
 327       LocSeq.Append(aLocShape);
 328       */
 329     }
 330   }
 331
 332   Standard_Real fpar, lpar;
 333   BRep_Tool::Range(FirstEdge, fpar, lpar);
 334   TopoDS_Edge PrevEdge = FirstEdge;
 335   TopoDS_Vertex CV;
 336   Standard_Real MaxTol = 0.;
 337
 338   TopoDS_Edge ResEdge;
 339   BRep_Builder BB;
 340
 341   Standard_Integer nb_curve = aChain.Length();   //number of curves
 342   TColGeom_Array1OfBSplineCurve tab_c3d(0,nb_curve-1);                    //array of the curves
 343   TColStd_Array1OfReal tabtolvertex(0,nb_curve-1); //(0,nb_curve-2);  //array of the tolerances
 344
 345   TopoDS_Vertex PrevVertex = FirstVertex;
 346   for (i = 1; i <= nb_curve; i++)
 347   {
 348     TopoDS_Edge anEdge = TopoDS::Edge(aChain(i));
 349     TopoDS_Vertex VF, VL;
 350     TopExp::Vertices(anEdge, VF, VL);
 351     Standard_Boolean ToReverse = (!VF.IsSame(PrevVertex));
 352
 353     Standard_Real Tol1 = BRep_Tool::Tolerance(VF);
 354     Standard_Real Tol2 = BRep_Tool::Tolerance(VL);
 355     if (Tol1 > MaxTol)
 356       MaxTol = Tol1;
 357     if (Tol2 > MaxTol)
 358       MaxTol = Tol2;
 359
 360     if (i > 1)
 361     {
 362       GetCommonVertex(PrevEdge, anEdge, CV);
 363       Standard_Real Tol = BRep_Tool::Tolerance(CV);
 364       tabtolvertex(i-2) = Tol;
 365     }
 366
 367     Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anEdge, fpar, lpar);
 368     Handle(Geom_TrimmedCurve) aTrCurve = new Geom_TrimmedCurve(aCurve, fpar, lpar);
 369     tab_c3d(i-1) = GeomConvert::CurveToBSplineCurve(aTrCurve);
 370     GeomConvert::C0BSplineToC1BSplineCurve(tab_c3d(i-1), Precision::Confusion());
 371     if (ToReverse)
 372       tab_c3d(i-1)->Reverse();
 373     PrevVertex = (ToReverse)? VF : VL;
 374     PrevEdge = anEdge;
 375   }
 376   Handle(TColGeom_HArray1OfBSplineCurve)  concatcurve;     //array of the concatenated curves
 377   Handle(TColStd_HArray1OfInteger)        ArrayOfIndices;  //array of the remining Vertex
 378   Standard_Boolean ClosedFlag = Standard_False;
 379   GeomConvert::ConcatC1(tab_c3d,
 380                         tabtolvertex,
 381                         ArrayOfIndices,
 382                         concatcurve,
 383                         ClosedFlag,
 384                         Precision::Confusion());   //C1 concatenation
 385
 386   if (concatcurve->Length() > 1)
 387   {
 388     GeomConvert_CompCurveToBSplineCurve Concat(concatcurve->Value(concatcurve->Lower()));
 389
 390     for (i = concatcurve->Lower()+1; i <= concatcurve->Upper(); i++)
 391       Concat.Add( concatcurve->Value(i), MaxTol, Standard_True );
 392
 393     concatcurve->SetValue(concatcurve->Lower(), Concat.BSplineCurve());
 394   }
 395   Handle(Geom_BSplineCurve) ResCurve = concatcurve->Value(concatcurve->Lower());
 396
 397   TColGeom2d_SequenceOfBoundedCurve ResPCurves;
 398   TopLoc_Location aLoc;
 399   for (j = 1; j <= SurfSeq.Length(); j++)
 400   {
 401     TColGeom2d_Array1OfBSplineCurve tab_c2d(0,nb_curve-1); //array of the pcurves
 402
 403     PrevVertex = FirstVertex;
 404     PrevEdge = FirstEdge;
 405     //TopLoc_Location theLoc = LocSeq(j).Location();
 406     for (i = 1; i <= nb_curve; i++)
 407     {
 408       TopoDS_Edge anEdge = TopoDS::Edge(aChain(i));
 409       TopoDS_Vertex VF, VL;
 410       TopExp::Vertices(anEdge, VF, VL);
 411       Standard_Boolean ToReverse = (!VF.IsSame(PrevVertex));
 412
 413       /*
 414       Handle(Geom2d_Curve) aPCurve =
 415         BRep_Tool::CurveOnSurface(anEdge, SurfSeq(j), anEdge.Location()*theLoc, fpar, lpar);
 416       */
 417       Handle(Geom2d_Curve) aPCurve =
 418         BRep_Tool::CurveOnSurface(anEdge, SurfSeq(j), aLoc, fpar, lpar);
 419       Handle(Geom2d_TrimmedCurve) aTrPCurve = new Geom2d_TrimmedCurve(aPCurve, fpar, lpar);
 420       tab_c2d(i-1) = Geom2dConvert::CurveToBSplineCurve(aTrPCurve);
 421       Geom2dConvert::C0BSplineToC1BSplineCurve(tab_c2d(i-1), Precision::Confusion());
 422       if (ToReverse)
 423         tab_c2d(i-1)->Reverse();
 424       PrevVertex = (ToReverse)? VF : VL;
 425       PrevEdge = anEdge;
 426     }
 427     Handle(TColGeom2d_HArray1OfBSplineCurve)  concatc2d;     //array of the concatenated curves
 428     Handle(TColStd_HArray1OfInteger)        ArrayOfInd2d;  //array of the remining Vertex
 429     Standard_Boolean ClosedFlag = Standard_False;
 430     Geom2dConvert::ConcatC1(tab_c2d,
 431                             tabtolvertex,
 432                             ArrayOfInd2d,
 433                             concatc2d,
 434                             ClosedFlag,
 435                             Precision::Confusion());   //C1 concatenation
 436
 437     if (concatc2d->Length() > 1)
 438     {
 439       Geom2dConvert_CompCurveToBSplineCurve Concat2d(concatc2d->Value(concatc2d->Lower()));
 440
 441       for (i = concatc2d->Lower()+1; i <= concatc2d->Upper(); i++)
 442         Concat2d.Add( concatc2d->Value(i), MaxTol, Standard_True );
 443
 444       concatc2d->SetValue(concatc2d->Lower(), Concat2d.BSplineCurve());
 445     }
 446     Handle(Geom2d_BSplineCurve) aResPCurve = concatc2d->Value(concatc2d->Lower());
 447     ResPCurves.Append(aResPCurve);
 448   }
 449
 450   ResEdge = BRepLib_MakeEdge(ResCurve,
 451                              FirstVertex, LastVertex,
 452                              ResCurve->FirstParameter(), ResCurve->LastParameter());
 453   BB.SameRange(ResEdge, Standard_False);
 454   BB.SameParameter(ResEdge, Standard_False);
 455   for (j = 1; j <= ResPCurves.Length(); j++)
 456   {
 457     BB.UpdateEdge(ResEdge, ResPCurves(j), SurfSeq(j), aLoc, MaxTol);
 458     BB.Range(ResEdge, SurfSeq(j), aLoc, ResPCurves(j)->FirstParameter(), ResPCurves(j)->LastParameter());
 459   }
 460
 461   BRepLib::SameParameter(ResEdge, MaxTol, Standard_True);
 462
 463   return ResEdge;
 464 }
 465
 466 //=======================================================================
 467 //function : MergeEdges
 468 //purpose  : auxiliary
 469 //=======================================================================
 470 static Standard_Boolean MergeEdges(const TopTools_SequenceOfShape& SeqEdges,
 471                                    const Standard_Real Tol,
 472                                    TopoDS_Edge& anEdge)
 473 {
 474   // make chain for union
 475   BRep_Builder B;
 476   ShapeAnalysis_Edge sae;
 477   TopoDS_Edge FirstE = TopoDS::Edge(SeqEdges.Value(1));
 478   TopoDS_Edge LastE = FirstE;
 479   TopoDS_Vertex VF = sae.FirstVertex(FirstE);
 480   TopoDS_Vertex VL = sae.LastVertex(LastE);
 481   TopTools_SequenceOfShape aChain;
 482   aChain.Append(FirstE);
 483   TColStd_MapOfInteger IndUsedEdges;
 484   IndUsedEdges.Add(1);
 485   Standard_Integer j;
 486   for(j=2; j<=SeqEdges.Length(); j++) {
 487     for(Standard_Integer k=2; k<=SeqEdges.Length(); k++) {
 488       if(IndUsedEdges.Contains(k)) continue;
 489       TopoDS_Edge edge = TopoDS::Edge(SeqEdges.Value(k));
 490       TopoDS_Vertex VF2 = sae.FirstVertex(edge);
 491       TopoDS_Vertex VL2 = sae.LastVertex(edge);
 492       if(sae.FirstVertex(edge).IsSame(VL)) {
 493         aChain.Append(edge);
 494         LastE = edge;
 495         VL = sae.LastVertex(LastE);
 496         IndUsedEdges.Add(k);
 497       }
 498       else if(sae.LastVertex(edge).IsSame(VF)) {
 499         aChain.Prepend(edge);
 500         FirstE = edge;
 501         VF = sae.FirstVertex(FirstE);
 502         IndUsedEdges.Add(k);
 503       }
 504     }
 505   }
 506   if(aChain.Length()<SeqEdges.Length()) {
 507     MESSAGE ("can not create correct chain...");
 508     return Standard_False;
 509   }
 510
 511   // union edges in chain
 512   // first step: union lines and circles
 513   TopLoc_Location Loc;
 514   Standard_Real fp1,lp1,fp2,lp2;
 515   for(j=1; j<aChain.Length(); j++) {
 516     TopoDS_Edge edge1 = TopoDS::Edge(aChain.Value(j));
 517     Handle(Geom_Curve) c3d1 = BRep_Tool::Curve(edge1,Loc,fp1,lp1);
 518     if(c3d1.IsNull()) break;
 519     while(c3d1->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 520       Handle(Geom_TrimmedCurve) tc =
 521         Handle(Geom_TrimmedCurve)::DownCast(c3d1);
 522       c3d1 = tc->BasisCurve();
 523     }
 524     TopoDS_Edge edge2 = TopoDS::Edge(aChain.Value(j+1));
 525     Handle(Geom_Curve) c3d2 = BRep_Tool::Curve(edge2,Loc,fp2,lp2);
 526     if(c3d2.IsNull()) break;
 527     while(c3d2->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 528       Handle(Geom_TrimmedCurve) tc =
 529         Handle(Geom_TrimmedCurve)::DownCast(c3d2);
 530       c3d2 = tc->BasisCurve();
 531     }
 532     if( c3d1->IsKind(STANDARD_TYPE(Geom_Line)) && c3d2->IsKind(STANDARD_TYPE(Geom_Line)) ) {
 533       // union lines
 534       Handle(Geom_Line) L1 = Handle(Geom_Line)::DownCast(c3d1);
 535       Handle(Geom_Line) L2 = Handle(Geom_Line)::DownCast(c3d2);
 536       gp_Dir Dir1 = L1->Position().Direction();
 537       gp_Dir Dir2 = L2->Position().Direction();
 538       //if(!Dir1.IsEqual(Dir2,Precision::Angular())) {
 539       //if(!Dir1.IsParallel(Dir2,Precision::Angular())) {
 540       if(!Dir1.IsParallel(Dir2,Tol)) {
 541         continue;
 542       }
 543       // can union lines => create new edge
 544       TopoDS_Vertex V1 = sae.FirstVertex(edge1);
 545       gp_Pnt PV1 = BRep_Tool::Pnt(V1);
 546       TopoDS_Vertex V2 = sae.LastVertex(edge2);
 547       gp_Pnt PV2 = BRep_Tool::Pnt(V2);
 548       gp_Vec Vec(PV1,PV2);
 549       Handle(Geom_Line) L = new Geom_Line(gp_Ax1(PV1,Vec));
 550       Standard_Real dist = PV1.Distance(PV2);
 551       Handle(Geom_TrimmedCurve) tc = new Geom_TrimmedCurve(L,0.0,dist);
 552       TopoDS_Edge E;
 553       B.MakeEdge (E,tc,Precision::Confusion());
 554       B.Add (E,V1);  B.Add (E,V2);
 555       B.UpdateVertex(V1, 0., E, 0.);
 556       B.UpdateVertex(V2, dist, E, 0.);
 557       aChain.Remove(j);
 558       aChain.SetValue(j,E);
 559       j--;
 560     }
 561     if( c3d1->IsKind(STANDARD_TYPE(Geom_Circle)) && c3d2->IsKind(STANDARD_TYPE(Geom_Circle)) ) {
 562       // union circles
 563       Handle(Geom_Circle) C1 = Handle(Geom_Circle)::DownCast(c3d1);
 564       Handle(Geom_Circle) C2 = Handle(Geom_Circle)::DownCast(c3d2);
 565       gp_Pnt P01 = C1->Location();
 566       gp_Pnt P02 = C2->Location();
 567       if (P01.Distance(P02) > Precision::Confusion()) continue;
 568       // can union circles => create new edge
 569       TopoDS_Vertex V1 = sae.FirstVertex(edge1);
 570       gp_Pnt PV1 = BRep_Tool::Pnt(V1);
 571       TopoDS_Vertex V2 = sae.LastVertex(edge2);
 572       gp_Pnt PV2 = BRep_Tool::Pnt(V2);
 573       TopoDS_Vertex VM = sae.LastVertex(edge1);
 574       gp_Pnt PVM = BRep_Tool::Pnt(VM);
 575       GC_MakeCircle MC (PV1,PVM,PV2);
 576       Handle(Geom_Circle) C;
 577       TopoDS_Edge E;
 578
 579       if (MC.IsDone()) {
 580         C = MC.Value();
 581       }
 582
 583       if (C.IsNull()) {
 584         // jfa for Mantis issue 0020228
 585         if (PV1.Distance(PV2) > Precision::Confusion()) continue;
 586         // closed chain. Make a closed circular edge starting from V1.
 587         gp_Ax1 anAxis = C1->Axis();
 588
 589         if (edge1.Orientation() == TopAbs_REVERSED) {
 590           anAxis.Reverse();
 591         }
 592
 593         const gp_Pnt &aP0 = anAxis.Location();
 594         gp_Dir        aDX(PV1.XYZ().Subtracted(aP0.XYZ()));
 595         gp_Ax2        aNewAxis(aP0, anAxis.Direction(), aDX);
 596
 597         C = new Geom_Circle(aNewAxis, C1->Radius());
 598
 599         B.MakeEdge (E,C,Precision::Confusion());
 600         B.Add(E,V1);
 601         B.Add(E,V2);
 602         B.UpdateVertex(V1, 0., E, 0.);
 603         B.UpdateVertex(V2, 2.*M_PI, E, 0.);
 604       }
 605       else {
 606         gp_Pnt P0 = C->Location();
 607         gp_Dir D1(gp_Vec(P0,PV1));
 608         gp_Dir D2(gp_Vec(P0,PV2));
 609         Standard_Real fpar = C->XAxis().Direction().Angle(D1);
 610         if(fabs(fpar)>Precision::Confusion()) {
 611           // check orientation
 612           gp_Dir ND =  C->XAxis().Direction().Crossed(D1);
 613           if(ND.IsOpposite(C->Axis().Direction(),Precision::Confusion())) {
 614             fpar = -fpar;
 615           }
 616         }
 617         Standard_Real lpar = C->XAxis().Direction().Angle(D2);
 618         if(fabs(lpar)>Precision::Confusion()) {
 619           // check orientation
 620           gp_Dir ND =  C->XAxis().Direction().Crossed(D2);
 621           if(ND.IsOpposite(C->Axis().Direction(),Precision::Confusion())) {
 622             lpar = -lpar;
 623           }
 624         }
 625         if (lpar < fpar) lpar += 2*M_PI;
 626         Handle(Geom_TrimmedCurve) tc = new Geom_TrimmedCurve(C,fpar,lpar);
 627         B.MakeEdge (E,tc,Precision::Confusion());
 628         B.Add(E,V1);
 629         B.Add(E,V2);
 630         B.UpdateVertex(V1, fpar, E, 0.);
 631         B.UpdateVertex(V2, lpar, E, 0.);
 632       }
 633       aChain.Remove(j);
 634       aChain.SetValue(j,E);
 635       j--;
 636     }
 637   }
 638   if (j < aChain.Length()) {
 639     MESSAGE ("null curve3d in edge...");
 640     return Standard_False;
 641   }
 642   if (aChain.Length() > 1) {
 643     // second step: union edges with various curves
 644     // skl for bug 0020052 from Mantis: perform such unions
 645     // only if curves are bspline or bezier
 646     bool NeedUnion = true;
 647     for(j=1; j<=aChain.Length(); j++) {
 648       TopoDS_Edge edge = TopoDS::Edge(aChain.Value(j));
 649       Handle(Geom_Curve) c3d = BRep_Tool::Curve(edge,Loc,fp1,lp1);
 650       if(c3d.IsNull()) continue;
 651       while(c3d->IsKind(STANDARD_TYPE(Geom_TrimmedCurve))) {
 652         Handle(Geom_TrimmedCurve) tc =
 653           Handle(Geom_TrimmedCurve)::DownCast(c3d);
 654         c3d = tc->BasisCurve();
 655       }
 656       if( ( c3d->IsKind(STANDARD_TYPE(Geom_BSplineCurve)) ||
 657             c3d->IsKind(STANDARD_TYPE(Geom_BezierCurve)) ) ) continue;
 658       NeedUnion = false;
 659       break;
 660     }
 661     if(NeedUnion) {
 662       MESSAGE ("can not make analytical union => make approximation");
 663       TopoDS_Edge E = GlueEdgesWithPCurves(aChain, VF, VL);
 664       aChain.SetValue(1,E);
 665     }
 666     else {
 667       MESSAGE ("can not make approximation for such types of curves");
 668       return Standard_False;
 669     }
 670   }
 671
 672   anEdge = TopoDS::Edge(aChain.Value(1));
 673   return Standard_True;
 674 }
 675
 676 //=======================================================================
 677 //function : Perform
 678 //purpose  :
 679 //=======================================================================
 680 TopoDS_Shape BlockFix_UnionEdges::Perform(const TopoDS_Shape& theShape,
 681                                           const Standard_Real theTol)
 682 {
 683   // Fill Map of edges as keys and list of faces as items.
 684   TopTools_IndexedDataMapOfShapeListOfShape aMapEdgeFaces;
 685   Standard_Boolean isModified = Standard_False;
 686
 687   TopExp::MapShapesAndAncestors
 688     (theShape, TopAbs_EDGE, TopAbs_FACE, aMapEdgeFaces);
 689
 690   // processing each face
 691   Handle(ShapeBuild_ReShape) aContext = new ShapeBuild_ReShape;
 692   TopTools_MapOfShape        aProcessed;
 693   TopTools_MapOfShape        aModifiedFaces;
 694   TopExp_Explorer            anExpF(theShape, TopAbs_FACE);
 695
 696   for (; anExpF.More(); anExpF.Next()) {
 697     // Processing of each wire of the face
 698     TopoDS_Face aFace = TopoDS::Face(anExpF.Current());
 699
 700     if (!aProcessed.Add(aFace)) {
 701       continue;
 702     }
 703
 704     TopExp_Explorer anExpW(aFace, TopAbs_WIRE);
 705
 706     for (; anExpW.More(); anExpW.Next()) {
 707       // Get the ordered list of edges in the wire.
 708       TopoDS_Wire            aWire = TopoDS::Wire(anExpW.Current());
 709       BRepTools_WireExplorer aWExp(aWire, aFace);
 710       TopTools_ListOfShape   aChainEdges;
 711       Standard_Integer       aNbEdges = 0;
 712
 713       for (; aWExp.More(); aWExp.Next(), aNbEdges++) {
 714         aChainEdges.Append(aWExp.Current());
 715       }
 716
 717       if (aNbEdges < 2) {
 718         // Nothing to merge.
 719         continue;
 720       }
 721
 722       // Fill the list of flags that neighbour edges can be merged.
 723       TColStd_ListOfInteger aChainCanMerged;
 724       TopoDS_Edge           anEdge1 = TopoDS::Edge(aChainEdges.Last());
 725       TopoDS_Edge           anEdge2;
 726       Standard_Boolean      isToMerge;
 727       TopTools_ListIteratorOfListOfShape anIter(aChainEdges);
 728       Standard_Boolean      isFirstMerge = Standard_False;
 729       Standard_Boolean      isFirst = Standard_True;
 730       Standard_Boolean      isReorder = Standard_False;
 731
 732       // The first element is the flag between last and first edges.
 733       for (; anIter.More(); anIter.Next()) {
 734         anEdge2 = TopoDS::Edge(anIter.Value());
 735
 736         if (aProcessed.Contains(anEdge1) || aProcessed.Contains(anEdge2)) {
 737           // No need to merge already processed edges.
 738           isToMerge = Standard_False;
 739         } else {
 740           isToMerge = IsToMerge(anEdge1, anEdge2, aMapEdgeFaces, theTol);
 741         }
 742
 743         aChainCanMerged.Append(isToMerge);
 744         anEdge1 = anEdge2;
 745
 746         if (isFirst) {
 747           isFirstMerge = isToMerge;
 748           isFirst      = Standard_False;
 749         } else if (isFirstMerge && !isToMerge) {
 750           isReorder = Standard_True;
 751         }
 752       }
 753
 754       // Fill the map of processed shape by the edges.
 755       for (anIter.Initialize(aChainEdges); anIter.More(); anIter.Next()) {
 756         aProcessed.Add(anIter.Value());
 757       }
 758
 759       // Reorder edges in the chain.
 760       if (isReorder) {
 761         // Find the first edge that can't be merged.
 762         while (aChainCanMerged.First()) {
 763           TopoDS_Shape aTmpShape = aChainEdges.First();
 764
 765           isToMerge = aChainCanMerged.First();
 766           aChainCanMerged.RemoveFirst();
 767           aChainCanMerged.Append(isToMerge);
 768           aChainEdges.RemoveFirst();
 769           aChainEdges.Append(aTmpShape);
 770         }
 771       }
 772
 773       // Merge parts of chain to be merged.
 774       TColStd_ListIteratorOfListOfInteger aFlagIter(aChainCanMerged);
 775       anIter.Initialize(aChainEdges);
 776
 777       while (anIter.More()) {
 778         TopTools_SequenceOfShape aSeqEdges;
 779
 780         aSeqEdges.Append(anIter.Value());
 781         aFlagIter.Next();
 782         anIter.Next();
 783
 784         for (; anIter.More(); anIter.Next(), aFlagIter.Next()) {
 785           if (aFlagIter.Value()) {
 786             // Continue the chain.
 787             aSeqEdges.Append(anIter.Value());
 788           } else {
 789             // Stop the chain.
 790             break;
 791           }
 792         }
 793
 794         const Standard_Integer aNbEdges = aSeqEdges.Length();
 795
 796         if (aNbEdges > 1) {
 797           // There are several edges to be merged.
 798           TopoDS_Edge aMergedEdge;
 799
 800           if (MergeEdges(aSeqEdges, theTol, aMergedEdge)) {
 801             isModified = Standard_True;
 802             // now we have only one edge - aMergedEdge.
 803             // we have to replace old ListEdges with this new edge
 804             const TopoDS_Shape &anEdge = aSeqEdges.Value(1);
 805
 806             aContext->Replace(anEdge, aMergedEdge);
 807
 808             for (Standard_Integer j = 2; j <= aNbEdges; j++) {
 809               aContext->Remove(aSeqEdges(j));
 810             }
 811
 812             // Fix affected faces.
 813             if (aMapEdgeFaces.Contains(anEdge)) {
 814               const TopTools_ListOfShape &aList =
 815                 aMapEdgeFaces.FindFromKey(anEdge);
 816               TopTools_ListIteratorOfListOfShape anIter(aList);
 817
 818               for (; anIter.More(); anIter.Next()) {
 819                 aModifiedFaces.Add(anIter.Value());
 820               }
 821             }
 822           }
 823         }
 824       }
 825     }
 826   }
 827
 828   if (isModified) {
 829     // Fix modified faces.
 830     TopTools_MapIteratorOfMapOfShape aModifIt(aModifiedFaces);
 831
 832     for (; aModifIt.More(); aModifIt.Next()) {
 833       TopoDS_Face aModifiedFace =
 834         TopoDS::Face(aContext->Apply(aModifIt.Key()));
 835       Handle(ShapeFix_Face) aSff = new ShapeFix_Face(aModifiedFace);
 836
 837       aSff->SetContext(aContext);
 838       aSff->SetPrecision(theTol);
 839       aSff->SetMinTolerance(theTol);
 840       aSff->SetMaxTolerance(Max(1., theTol*1000.));
 841       aSff->Perform();
 842       aContext->Replace(aModifiedFace, aSff->Face());
 843     }
 844
 845     // Check if the result shape contains shells.
 846     // If yes, fix the faces orientation in the shell.
 847     TopoDS_Shape    aModifShape = aContext->Apply(theShape);
 848     TopExp_Explorer anExpSh(aModifShape, TopAbs_SHELL);
 849
 850     for (; anExpSh.More(); anExpSh.Next()) {
 851       TopoDS_Shell           aShell = TopoDS::Shell(anExpSh.Current());
 852       Handle(ShapeFix_Shell) aSfsh = new ShapeFix_Shell;
 853
 854       aSfsh->FixFaceOrientation(aShell);
 855       aContext->Replace(aShell, aSfsh->Shell());
 856     }
 857   }
 858
 859   const TopoDS_Shape aResult = aContext->Apply(theShape);
 860
 861   return aResult;
 862 }