src/BRepLib/BRepLib_FuseEdges.cxx

   1 // Created on: 1998-11-26
   2 // Created by: Jean-Michel BOULCOURT
   3 // Copyright (c) 1998-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 // Modif : Wed Jan 20 15:40:50 1999. In BuildListResultEdges, we
  18 // in UpdatePcurve, problem with location of pcurve (mix between loc and locbid)
  19 // Modif : Thu Jan 21 11:40:20 1999. Add trace context #if DEB
  20 //           add test to avoid loop while in NextConnexEdge (in case of a closed connex wire)
  21
  22 #include <BRep_Builder.hxx>
  23 #include <BRep_Tool.hxx>
  24 #include <BRepLib.hxx>
  25 #include <BRepLib_FuseEdges.hxx>
  26 #include <BRepLib_MakeEdge.hxx>
  27 #include <BRepTools_Substitution.hxx>
  28 #include <BSplCLib.hxx>
  29 #include <ElCLib.hxx>
  30 #include <ElSLib.hxx>
  31 #include <Extrema_LocateExtPC.hxx>
  32 #include <Geom2d_BoundedCurve.hxx>
  33 #include <Geom2d_BSplineCurve.hxx>
  34 #include <Geom2d_Curve.hxx>
  35 #include <Geom2d_TrimmedCurve.hxx>
  36 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
  37 #include <Geom_BezierCurve.hxx>
  38 #include <Geom_BoundedCurve.hxx>
  39 #include <Geom_BSplineCurve.hxx>
  40 #include <Geom_Circle.hxx>
  41 #include <Geom_Curve.hxx>
  42 #include <Geom_Ellipse.hxx>
  43 #include <Geom_Line.hxx>
  44 #include <Geom_Plane.hxx>
  45 #include <Geom_TrimmedCurve.hxx>
  46 #include <GeomAdaptor_Curve.hxx>
  47 #include <GeomConvert.hxx>
  48 #include <GeomConvert_CompCurveToBSplineCurve.hxx>
  49 #include <GeomLib.hxx>
  50 #include <gp_Dir2d.hxx>
  51 #include <gp_Pnt2d.hxx>
  52 #include <gp_Trsf2d.hxx>
  53 #include <gp_Vec2d.hxx>
  54 #include <Precision.hxx>
  55 #include <Standard_ConstructionError.hxx>
  56 #include <Standard_NullObject.hxx>
  57 #include <TColgp_Array1OfPnt.hxx>
  58 #include <TColStd_Array1OfInteger.hxx>
  59 #include <TColStd_Array1OfReal.hxx>
  60 #include <TopExp.hxx>
  61 #include <TopExp_Explorer.hxx>
  62 #include <TopoDS.hxx>
  63 #include <TopoDS_Edge.hxx>
  64 #include <TopoDS_Face.hxx>
  65 #include <TopoDS_Shape.hxx>
  66 #include <TopoDS_Vertex.hxx>
  67 #include <TopoDS_Wire.hxx>
  68 #include <TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape.hxx>
  69 #include <TopTools_DataMapOfIntegerListOfShape.hxx>
  70 #include <TopTools_ListIteratorOfListOfShape.hxx>
  71 #include <TopTools_ListOfShape.hxx>
  72 #include <TopTools_MapOfShape.hxx>
  73
  74 //#ifdef OCCT_DEBUG
  75 //Standard_IMPORT Standard_Boolean TopOpeBRepBuild_GettraceFE();
  76 //#endif
  77 static void BCSmoothing(Handle(Geom_BSplineCurve)& theC,
  78                         const Standard_Integer theCont,
  79                         const Standard_Real theTol)
  80 {
  81
  82   Standard_Integer aNbIter = 5;
  83   Standard_Boolean bContinue = Standard_True;
  84   Standard_Integer iter = 1;
  85   TColStd_SequenceOfInteger aKnotIndex;
  86   TColStd_SequenceOfReal aKnotIns;
  87
  88   while (bContinue && iter <= aNbIter) {
  89
  90     Standard_Integer aNbKnots = theC->NbKnots();
  91     TColStd_Array1OfInteger aMults(1, aNbKnots);
  92     TColStd_Array1OfReal aKnots(1, aNbKnots);
  93
  94     theC->Multiplicities(aMults);
  95     theC->Knots(aKnots);
  96     Standard_Integer i, m = theC->Degree();
  97     m = m - theCont;
  98
  99     if(m < 1) return;
 100
 101     aKnotIndex.Clear();
 102
 103     for(i = 2; i < aNbKnots; i++) {
 104       if(aMults(i) > m) {
 105         if(!(theC->RemoveKnot(i, m, theTol))) {
 106           aKnotIndex.Append(i);
 107         }
 108       }
 109     }
 110
 111     //Prepare knots for inserting;
 112
 113     Standard_Integer aNbAdd = aKnotIndex.Length();
 114
 115     if(aNbAdd == 0) return;
 116
 117     aKnotIns.Clear();
 118
 119     Standard_Real aLastKnot = aKnots(1);
 120     for(i = 1; i <= aNbAdd; i++) {
 121
 122       Standard_Integer anInd = aKnotIndex(i);
 123
 124       Standard_Real aK1 = 0.5*(aKnots(anInd) + aKnots(anInd-1));
 125       if(Abs(aK1 - aLastKnot) > 1.e-3) {
 126         aKnotIns.Append(aK1);
 127         aLastKnot = aK1;
 128       }
 129
 130       Standard_Real aK2 = 0.5*(aKnots(anInd+1) + aKnots(anInd));
 131
 132       if(Abs(aK2 - aLastKnot) > 1.e-3) {
 133         aKnotIns.Append(aK2);
 134         aLastKnot = aK2;
 135       }
 136
 137     }
 138
 139     aNbAdd = aKnotIns.Length();
 140
 141     for(i = 1; i <= aNbAdd; i++) {
 142       theC->InsertKnot(aKnotIns(i), m, 1.e-3);
 143     }
 144
 145     iter++;
 146
 147   }
 148
 149   if(iter > aNbIter) BCSmoothing(theC, theCont, 1.e10);
 150
 151   return;
 152 }
 153
 154 static void MakeClosedCurve(Handle(Geom_Curve)& C, const gp_Pnt& PF,
 155                             Standard_Real& f, Standard_Real& l)
 156 {
 157   Handle(Geom_BSplineCurve) aBC = Handle(Geom_BSplineCurve)::DownCast (C);
 158   GeomAbs_Shape aCont = aBC->Continuity();
 159   //Find new origin
 160   aBC->SetPeriodic();
 161   Standard_Integer fk = aBC->FirstUKnotIndex();
 162   Standard_Integer lk = aBC->LastUKnotIndex();
 163   Standard_Integer k;
 164   Standard_Real eps = Precision::Confusion();
 165   eps *= eps;
 166   Standard_Real porig = 2.*l;
 167   Standard_Real dmin = 1.e100, pmin = f;
 168   for(k = fk; k <= lk; k++) {
 169     gp_Pnt aP = aBC->Value(aBC->Knot(k));
 170     Standard_Real d = PF.SquareDistance(aP);
 171     if(PF.SquareDistance(aP) > eps) {
 172       if(d < dmin) {
 173         pmin = aBC->Knot(k);
 174         dmin = d;
 175       }
 176       continue;
 177     }
 178
 179     porig = aBC->Knot(k);
 180     break;
 181   }
 182   if(porig > l) {
 183     //try to project
 184     GeomAdaptor_Curve aGAC(aBC);
 185     Extrema_LocateExtPC aPrj(PF, aGAC, pmin, Precision::PConfusion());
 186     if(aPrj.IsDone()) {
 187       porig = aPrj.Point().Parameter();
 188     }
 189     else {
 190       throw Standard_ConstructionError("FuseEdges : Projection failed for closed curve");
 191     }
 192   }
 193
 194   aBC->SetOrigin(porig, Precision::PConfusion());
 195   f = aBC->FirstParameter();
 196   l = aBC->LastParameter();
 197   aBC->Segment(f, l);
 198   if(aCont > GeomAbs_C0 && aBC->Continuity() == GeomAbs_C0) {
 199     BCSmoothing(aBC, 1, Precision::Confusion());
 200   }
 201   C = aBC;
 202   f = C->FirstParameter();
 203   l = C->LastParameter();
 204 }
 205
 206
 207
 208 //=======================================================================
 209 //function : BRepLib_FuseEdges
 210 //purpose  :
 211 //=======================================================================
 212
 213 BRepLib_FuseEdges::BRepLib_FuseEdges(const TopoDS_Shape& theShape,
 214 //                                                   const Standard_Boolean PerformNow)
 215                                                    const Standard_Boolean )
 216 :myShape(theShape),myShapeDone(Standard_False),myEdgesDone(Standard_False),
 217  myResultEdgesDone(Standard_False),myNbConnexEdge(0), myConcatBSpl(Standard_False)
 218 {
 219 //  if (theShape.ShapeType() != TopAbs_SHELL && theShape.ShapeType() != TopAbs_SOLID)
 220 //    throw Standard_ConstructionError("FuseEdges");
 221   Standard_NullObject_Raise_if(theShape.IsNull(),"FuseEdges");
 222   myMapFaces.Clear();
 223
 224 }
 225
 226 //=======================================================================
 227 //function : AvoidEdges
 228 //purpose  : set edges to avoid being fused
 229 //=======================================================================
 230
 231 void BRepLib_FuseEdges::AvoidEdges(const TopTools_IndexedMapOfShape& theMapEdg)
 232 {
 233   myAvoidEdg = theMapEdg;
 234 }
 235
 236 //=======================================================================
 237 //function : SetConcatBSpl
 238 //purpose  :
 239 //=======================================================================
 240
 241 void BRepLib_FuseEdges::SetConcatBSpl(const Standard_Boolean theConcatBSpl)
 242 {
 243   myConcatBSpl = theConcatBSpl;
 244 }
 245
 246 //=======================================================================
 247 //function : Edges
 248 //purpose  : returns  all the list of edges to be fused each list of the
 249 //           map represent a set of connex edges that can be fused.
 250 //=======================================================================
 251
 252 void BRepLib_FuseEdges::Edges(TopTools_DataMapOfIntegerListOfShape& theMapLstEdg)
 253 {
 254
 255   if (!myEdgesDone) {
 256     BuildListEdges();
 257   }
 258
 259   theMapLstEdg = myMapLstEdg;
 260 }
 261
 262
 263 //=======================================================================
 264 //function : ResultEdges
 265 //purpose  : returns  all the fused edges
 266 //=======================================================================
 267
 268 void BRepLib_FuseEdges::ResultEdges(TopTools_DataMapOfIntegerShape& theMapEdg)
 269 {
 270
 271   if (!myEdgesDone) {
 272     BuildListEdges();
 273   }
 274
 275   if (!myResultEdgesDone) {
 276     BuildListResultEdges();
 277   }
 278
 279   theMapEdg = myMapEdg;
 280 }
 281
 282 //=======================================================================
 283 //function : Faces
 284 //purpose  : returns  all the faces that have been modified after perform
 285 //=======================================================================
 286
 287 void BRepLib_FuseEdges::Faces(TopTools_DataMapOfShapeShape& theMapFac)
 288 {
 289
 290   if (!myEdgesDone) {
 291     BuildListEdges();
 292   }
 293
 294   if (!myResultEdgesDone) {
 295     BuildListResultEdges();
 296   }
 297
 298   if (!myShapeDone) {
 299     Perform();
 300   }
 301
 302   theMapFac = myMapFaces;
 303 }
 304
 305
 306 //=======================================================================
 307 //function : NbVertices
 308 //purpose  :
 309 //=======================================================================
 310
 311 Standard_Integer BRepLib_FuseEdges::NbVertices()
 312 {
 313
 314   Standard_NullObject_Raise_if(myShape.IsNull(),"FuseEdges : No Shape");
 315   Standard_Integer nbedges, nbvertices = 0;
 316
 317   if (!myEdgesDone) {
 318     BuildListEdges();
 319   }
 320
 321   if ((nbedges = myMapLstEdg.Extent()) > 0) {
 322
 323     TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape itEdg;
 324     for (itEdg.Initialize(myMapLstEdg); itEdg.More(); itEdg.Next()) {
 325       const Standard_Integer& iLst = itEdg.Key();
 326       const TopTools_ListOfShape& LmapEdg = myMapLstEdg.Find(iLst);
 327       nbvertices += LmapEdg.Extent() - 1;
 328     }
 329   }
 330
 331   return nbvertices;
 332
 333 }
 334
 335
 336 //=======================================================================
 337 //function : Shape
 338 //purpose  :
 339 //=======================================================================
 340
 341 TopoDS_Shape& BRepLib_FuseEdges::Shape()
 342 {
 343   Standard_NullObject_Raise_if(myShape.IsNull(),"FuseEdges : No Shape");
 344
 345   if (!myEdgesDone) {
 346     BuildListEdges();
 347   }
 348
 349   if (!myResultEdgesDone) {
 350     BuildListResultEdges();
 351   }
 352
 353   if (!myShapeDone) {
 354     Perform();
 355   }
 356
 357   return myShape;
 358 }
 359
 360
 361
 362 //=======================================================================
 363 //function : BuildListEdges
 364 //purpose  : Build the all the lists of edges that are to be fused
 365 //=======================================================================
 366
 367 void BRepLib_FuseEdges::BuildListEdges()
 368 {
 369
 370 //#ifdef OCCT_DEBUG
 371   //Standard_Boolean tFE = TopOpeBRepBuild_GettraceFE();
 372 //#endif
 373
 374   //--------------------------------------------------------
 375   // Step One : Build the map ancestors
 376   //--------------------------------------------------------
 377
 378   // Clear the maps
 379   myMapLstEdg.Clear();
 380   myMapVerLstEdg.Clear();
 381   myMapEdgLstFac.Clear();
 382
 383   TopExp::MapShapesAndUniqueAncestors(myShape,TopAbs_VERTEX,TopAbs_EDGE,myMapVerLstEdg);
 384   TopExp::MapShapesAndAncestors(myShape,TopAbs_EDGE,TopAbs_FACE,myMapEdgLstFac);
 385
 386   Standard_Integer iEdg;
 387   TopTools_MapOfShape mapUniqEdg;
 388
 389   // for each edge of myMapEdgLstFac
 390   for (iEdg = 1; iEdg <= myMapEdgLstFac.Extent(); iEdg++) {
 391     const TopoDS_Shape& edgecur = myMapEdgLstFac.FindKey(iEdg);
 392     TopTools_ListOfShape LstEdg;
 393
 394     // if edge not already treated
 395     if (!mapUniqEdg.Contains(edgecur)
 396         && (edgecur.Orientation() == TopAbs_FORWARD ||edgecur.Orientation() == TopAbs_REVERSED) ) {
 397       if (myAvoidEdg.Contains(edgecur))
 398         continue;       // edge is not allowed to be fused
 399       BuildListConnexEdge(edgecur, mapUniqEdg, LstEdg);
 400       if (LstEdg.Extent() > 1) {
 401         myNbConnexEdge++;
 402         myMapLstEdg.Bind(myNbConnexEdge,LstEdg);
 403       }
 404     }
 405   }
 406
 407   myEdgesDone = Standard_True;
 408   myResultEdgesDone = Standard_False;
 409 }
 410
 411
 412 //=======================================================================
 413 //function : BuildListResultEdges
 414 //purpose  : Build the result fused edges
 415 //=======================================================================
 416
 417 void BRepLib_FuseEdges::BuildListResultEdges()
 418 {
 419
 420 //#ifdef OCCT_DEBUG
 421   //Standard_Boolean tFE = TopOpeBRepBuild_GettraceFE();
 422 //#endif
 423
 424   // if we have edges to fuse
 425   if (myMapLstEdg.Extent() > 0) {
 426     TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape itLstEdg;
 427     TopoDS_Vertex VF,VL;
 428     Handle(Geom_Curve) C;
 429     TopLoc_Location loc;
 430     Standard_Real f,l;
 431     TopoDS_Edge NewEdge;
 432
 433     myMapEdg.Clear();
 434
 435     for (itLstEdg.Initialize(myMapLstEdg); itLstEdg.More(); itLstEdg.Next()) {
 436       const Standard_Integer& iLst = itLstEdg.Key();
 437       const TopTools_ListOfShape& LmapEdg = myMapLstEdg.Find(iLst);
 438
 439       TopoDS_Edge OldEdge = TopoDS::Edge(LmapEdg.First());
 440
 441       // the first edge of the list will be replaced by the result fusion edge
 442       if (OldEdge.Orientation()==TopAbs_REVERSED) {
 443         VL = TopExp::FirstVertex(TopoDS::Edge(LmapEdg.First()),Standard_True);
 444         VF = TopExp::LastVertex(TopoDS::Edge(LmapEdg.Last()),Standard_True);
 445       }
 446       else {
 447         VF = TopExp::FirstVertex(TopoDS::Edge(LmapEdg.First()),Standard_True);
 448         VL = TopExp::LastVertex(TopoDS::Edge(LmapEdg.Last()),Standard_True);
 449       }
 450       C = BRep_Tool::Curve(OldEdge,loc,f,l);
 451
 452       if (!loc.IsIdentity()) {
 453         C = Handle(Geom_Curve)::DownCast(C->Transformed(loc.Transformation()));
 454       }
 455       // if the curve is trimmed we get the basis curve to fit the new vertices
 456       // otherwise the makeedge will fail.
 457       if (C->DynamicType() == STANDARD_TYPE(Geom_TrimmedCurve)) {
 458         C = Handle(Geom_TrimmedCurve)::DownCast (C)->BasisCurve();
 459       }
 460
 461       if(myConcatBSpl) {
 462         //Prepare common BSpline curve
 463         if(C->DynamicType() == STANDARD_TYPE(Geom_BSplineCurve)) {
 464           TopTools_ListIteratorOfListOfShape anEdgIter(LmapEdg);
 465           Handle(Geom_TrimmedCurve) aTC = new Geom_TrimmedCurve(C, f, l);
 466           GeomConvert_CompCurveToBSplineCurve Concat( aTC );
 467
 468           anEdgIter.Next();
 469           for(; anEdgIter.More(); anEdgIter.Next()) {
 470             Handle(Geom_Curve) aC = BRep_Tool::Curve(TopoDS::Edge(anEdgIter.Value()), f, l);
 471             aTC = new Geom_TrimmedCurve(aC, f, l);
 472             if (!Concat.Add(aTC, Precision::Confusion())) {
 473                   // cannot merge curves
 474               throw Standard_ConstructionError("FuseEdges : Concatenation failed");
 475             }
 476           }
 477           C = Concat.BSplineCurve();
 478         }
 479       }
 480
 481
 482       BRepLib_MakeEdge ME;
 483
 484       Standard_Boolean isBSpline = C->DynamicType() == STANDARD_TYPE(Geom_BSplineCurve);
 485
 486       if(VF.IsSame(VL) && isBSpline) {
 487         //closed edge
 488         f = C->FirstParameter();
 489         l = C->LastParameter();
 490         gp_Pnt aPf = C->Value(f);
 491         gp_Pnt aPl = C->Value(l);
 492         if(aPf.Distance(aPl) > Precision::Confusion()) {
 493             throw Standard_ConstructionError("FuseEdges : Curve must be closed");
 494         }
 495         gp_Pnt PF = BRep_Tool::Pnt(VF);
 496         if(PF.Distance(aPf) > Precision::Confusion()) {
 497           MakeClosedCurve(C, PF, f, l);
 498         }
 499         //
 500         ME.Init(C, VF, VL, f, l);
 501         if (!ME.IsDone()) {
 502           throw Standard_ConstructionError("FuseEdges : MakeEdge failed for closed curve");
 503         }
 504       }
 505       else {
 506         ME.Init(C,VF,VL);
 507       }
 508 //      BRepLib_MakeEdge ME(C,VF,VL);
 509
 510       if (!ME.IsDone()) {
 511         // the MakeEdge has fails, one reason could be that the new Vertices are outside
 512         // the curve which is not infinite and limited to old vertices
 513         // we try to use ExtendCurveToPoint, then rebuild the NewEdge
 514
 515         Handle(Geom_BoundedCurve) ExtC = Handle(Geom_BoundedCurve)::DownCast(C->Copy());
 516         if (!ExtC.IsNull()) {
 517           gp_Pnt PF = BRep_Tool::Pnt(VF);
 518           gp_Pnt PL = BRep_Tool::Pnt(VL);
 519           GeomLib::ExtendCurveToPoint(ExtC,PF,1,0);
 520           GeomLib::ExtendCurveToPoint(ExtC,PL,1,1);
 521
 522           ME.Init(ExtC,VF,VL);
 523           if (!ME.IsDone())
 524             throw Standard_ConstructionError("FuseEdges : Fusion failed");
 525         }
 526         else
 527           throw Standard_ConstructionError("FuseEdges : Fusion failed");
 528       }
 529
 530       NewEdge = ME.Edge();
 531
 532       if (UpdatePCurve(OldEdge,NewEdge,LmapEdg))
 533         myMapEdg.Bind(iLst,NewEdge);
 534     }
 535
 536     myResultEdgesDone = Standard_True;
 537
 538   }
 539 }
 540
 541 //=======================================================================
 542 //function : Perform
 543 //purpose  :
 544 //=======================================================================
 545
 546 void BRepLib_FuseEdges::Perform()
 547 {
 548
 549 //#ifdef OCCT_DEBUG
 550   //Standard_Boolean tFE = TopOpeBRepBuild_GettraceFE();
 551 //#endif
 552
 553   if (!myResultEdgesDone) {
 554     BuildListResultEdges();
 555   }
 556
 557   // if we have fused edges
 558   if (myMapEdg.Extent() > 0) {
 559     TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape itLstEdg;
 560     TopTools_ListOfShape EmptyList,EdgeToSubs;
 561     BRepTools_Substitution Bsub;
 562
 563     for (itLstEdg.Initialize(myMapLstEdg); itLstEdg.More(); itLstEdg.Next()) {
 564       const Standard_Integer& iLst = itLstEdg.Key();
 565       if (!myMapEdg.IsBound(iLst))
 566         continue;
 567       const TopTools_ListOfShape& LmapEdg = myMapLstEdg.Find(iLst);
 568       TopTools_ListIteratorOfListOfShape itEdg;
 569
 570       EdgeToSubs.Clear();
 571       TopoDS_Edge OldEdge = TopoDS::Edge(LmapEdg.First());
 572
 573       EdgeToSubs.Append(myMapEdg(iLst));
 574       Bsub.Substitute(OldEdge,EdgeToSubs);
 575
 576       itEdg.Initialize(LmapEdg);
 577
 578       // the other edges of the list will be removed
 579       while (itEdg.More() ) {
 580         if (!OldEdge.IsSame(TopoDS::Edge(itEdg.Value()))) {
 581           Bsub.Substitute(itEdg.Value(),EmptyList);
 582         }
 583         itEdg.Next();
 584       }
 585     }
 586
 587     // perform the effective substitution
 588     Bsub.Build(myShape);
 589
 590     // before copying the resulting shape, map the modified faces into myMapFaces
 591     TopExp_Explorer exp(myShape,TopAbs_FACE);
 592
 593     for (; exp.More(); exp.Next()) {
 594       const TopoDS_Shape& facecur = exp.Current();
 595       if (Bsub.IsCopied(facecur)) {
 596         myMapFaces.Bind(facecur,(Bsub.Copy(facecur)).First());
 597       }
 598     }
 599
 600     if (Bsub.IsCopied(myShape)) {
 601       myShape=(Bsub.Copy(myShape)).First();
 602     }
 603
 604   }
 605
 606
 607   myShapeDone = Standard_True;
 608 }
 609
 610
 611
 612 //=======================================================================
 613 //function : BuildListConnexEdge
 614 //purpose  : giving one edge, build the list of connex edges which have
 615 // vertices that have only two connex edges. All the edges that are addes
 616 // to the list must be added also to the mapUniq, in order for the caller
 617 // to not treat again theses edges.
 618 // This list is always oriented in the "Forward" direction.
 619 //=======================================================================
 620
 621 void BRepLib_FuseEdges::BuildListConnexEdge(const TopoDS_Shape& theEdge,
 622                                                    TopTools_MapOfShape& theMapUniq,
 623                                                    TopTools_ListOfShape& theLstEdg)
 624 {
 625
 626   TopoDS_Vertex VF,VL;
 627
 628
 629   VL = TopExp::LastVertex(TopoDS::Edge(theEdge),Standard_True);
 630   TopoDS_Shape edgeconnex;
 631   TopoDS_Shape edgecur = theEdge;
 632   theLstEdg.Clear();
 633   theLstEdg.Append(edgecur);
 634   theMapUniq.Add(edgecur);
 635   TopAbs_Orientation ori2;
 636
 637   // we first build the list of edges connex to edgecur by looking from the last Vertex VL
 638   while (NextConnexEdge(VL,edgecur,edgeconnex)) {
 639     if (theMapUniq.Contains(edgeconnex)) {
 640       break;
 641     }
 642     theLstEdg.Append(edgeconnex);
 643     edgecur = edgeconnex;
 644     // here take care about internal or external edges. It is non-sense to build
 645     // the connex list with such edges.
 646     ori2 = edgecur.Orientation();
 647     if (ori2 == TopAbs_EXTERNAL || ori2 == TopAbs_INTERNAL) {
 648       break;
 649     }
 650     VL = TopExp::LastVertex(TopoDS::Edge(edgecur),Standard_True);
 651     theMapUniq.Add(edgecur);
 652   }
 653
 654   edgecur = theEdge;
 655   VF = TopExp::FirstVertex(TopoDS::Edge(theEdge),Standard_True);
 656
 657   // then we build the list of edges connex to edgecur by looking from the first Vertex VF
 658   while (NextConnexEdge(VF,edgecur,edgeconnex)) {
 659     if (theMapUniq.Contains(edgeconnex)) {
 660       break;
 661     }
 662     theLstEdg.Prepend(edgeconnex);
 663     edgecur = edgeconnex;
 664     // here take care about internal or external edges. It is non-sense to build
 665     // the connex list with such edges.
 666     ori2 = edgecur.Orientation();
 667     if (ori2 == TopAbs_EXTERNAL || ori2 == TopAbs_INTERNAL) {
 668       break;
 669     }
 670     VF = TopExp::FirstVertex(TopoDS::Edge(edgecur),Standard_True);
 671     theMapUniq.Add(edgecur);
 672   }
 673
 674 }
 675
 676
 677 //=======================================================================
 678 //function : NextConnexEdge
 679 //purpose  : Look for an edge connex to theEdge at theVertex.
 680 // the connex edge must satisfies the following criteria :
 681 //   * theVertex must have exactly 2 connex edges.
 682 //   * the 2 connex edges must have exactly the 2 same connex faces
 683 //   * the 2 connex edges must lie on the same support.
 684 //=======================================================================
 685
 686 Standard_Boolean BRepLib_FuseEdges::NextConnexEdge(const TopoDS_Vertex& theVertex,
 687                                                           const TopoDS_Shape& theEdge,
 688                                                           TopoDS_Shape& theEdgeConnex) const
 689 {
 690
 691   const TopTools_ListOfShape& LmapEdg = myMapVerLstEdg.FindFromKey(theVertex);
 692   Standard_Boolean HasConnex = Standard_True;
 693   TopTools_ListIteratorOfListOfShape itEdg,itFac1,itFac2;
 694
 695   // 1st condition
 696   if (LmapEdg.Extent() == 2) {
 697     itEdg.Initialize(LmapEdg);
 698     theEdgeConnex = itEdg.Value();
 699     if (theEdge.IsSame(theEdgeConnex) ) {
 700       itEdg.Next();
 701       theEdgeConnex = itEdg.Value();
 702     }
 703
 704     if (myAvoidEdg.Contains(theEdgeConnex))
 705       HasConnex = Standard_False;  // edge is not allowed to be fused
 706
 707     // 2nd condition
 708     if (HasConnex) {
 709       const TopTools_ListOfShape& LmapFac1 = myMapEdgLstFac.FindFromKey(theEdge);
 710       const TopTools_ListOfShape& LmapFac2 = myMapEdgLstFac.FindFromKey(theEdgeConnex);
 711
 712       if (LmapFac1.Extent() ==  LmapFac2.Extent() && LmapFac1.Extent() < 3) {
 713         itFac1.Initialize(LmapFac1);
 714
 715         // for each face in LmapFac1 we look in LmapFac2 if it exists
 716         while (itFac1.More() && HasConnex) {
 717           const TopoDS_Shape& face1 = itFac1.Value();
 718           for (itFac2.Initialize(LmapFac2); itFac2.More(); itFac2.Next()) {
 719             const TopoDS_Shape& face2 = itFac2.Value();
 720             HasConnex = Standard_False;
 721             if (face1.IsSame(face2)) {
 722               HasConnex = Standard_True;
 723               break;
 724             }
 725           }
 726           itFac1.Next();
 727         }
 728
 729         // 3rd condition : same suport
 730         if (HasConnex) {
 731           HasConnex = SameSupport(TopoDS::Edge(theEdge),TopoDS::Edge(theEdgeConnex));
 732         }
 733       }
 734       else
 735         HasConnex = Standard_False;
 736     }
 737   }
 738   else
 739     HasConnex = Standard_False;
 740
 741   return HasConnex;
 742 }
 743
 744
 745
 746 //=======================================================================
 747 //function : SameSupport
 748 //purpose  : Edges SameSupport ou pas
 749 //=======================================================================
 750
 751 Standard_Boolean BRepLib_FuseEdges::SameSupport(const TopoDS_Edge& E1,
 752                                                        const TopoDS_Edge& E2) const
 753 {
 754
 755   if (E1.IsNull() || E2.IsNull()) {
 756     return Standard_False;
 757   }
 758
 759
 760   Handle(Geom_Curve) C1,C2;
 761   TopLoc_Location loc;
 762   Standard_Real f1,l1,f2,l2;
 763   Handle(Standard_Type) typC1,typC2;
 764
 765   C1 = BRep_Tool::Curve(E1,loc,f1,l1);
 766   //modified by NIZNHY-PKV Mon Nov 15 16:24:10 1999
 767   //degenerated edges has no 3D curve
 768   if(C1.IsNull()) return Standard_False;
 769
 770   if (!loc.IsIdentity()) {
 771     Handle(Geom_Geometry) GG1 = C1->Transformed(loc.Transformation());
 772     C1 = Handle(Geom_Curve)::DownCast (GG1);
 773   }
 774   C2 = BRep_Tool::Curve(E2,loc,f2,l2);
 775   //modified by NIZNHY-PKV Mon Nov 15 16:24:38 1999
 776   //degenerated edges has no 3D curve
 777   if(C2.IsNull()) return Standard_False;
 778
 779   if (!loc.IsIdentity()) {
 780     Handle(Geom_Geometry) GG2 = C2->Transformed(loc.Transformation());
 781     C2 = Handle(Geom_Curve)::DownCast (GG2);
 782   }
 783
 784   typC1 = C1->DynamicType();
 785   typC2 = C2->DynamicType();
 786
 787   if (typC1 == STANDARD_TYPE(Geom_TrimmedCurve)) {
 788     C1 =  Handle(Geom_TrimmedCurve)::DownCast (C1)->BasisCurve();
 789     typC1 = C1->DynamicType();
 790   }
 791
 792   if (typC2 == STANDARD_TYPE(Geom_TrimmedCurve)) {
 793     C2 =  Handle(Geom_TrimmedCurve)::DownCast (C2)->BasisCurve();
 794     typC2 = C2->DynamicType();
 795   }
 796
 797   if (typC1 != typC2) {
 798     return Standard_False;
 799   }
 800
 801   if (typC1 != STANDARD_TYPE(Geom_Line) &&
 802       typC1 != STANDARD_TYPE(Geom_Circle) &&
 803       typC1 != STANDARD_TYPE(Geom_Ellipse) &&
 804       typC1 != STANDARD_TYPE(Geom_BSplineCurve) &&
 805       typC1 != STANDARD_TYPE(Geom_BezierCurve)) {
 806 #ifdef OCCT_DEBUG
 807     cout << " TopOpeBRepTool_FuseEdge : Type de Support non traite" << endl;
 808 #endif
 809     return Standard_False;
 810   }
 811
 812   // On a presomption de confusion
 813   const Standard_Real tollin = Precision::Confusion();
 814   const Standard_Real tolang = Precision::Angular();
 815   if (typC1 == STANDARD_TYPE(Geom_Line)) {
 816     gp_Lin li1( Handle(Geom_Line)::DownCast (C1)->Lin());
 817     gp_Lin li2( Handle(Geom_Line)::DownCast (C2)->Lin());
 818     gp_Dir dir1(li1.Direction());
 819     gp_Dir dir2(li2.Direction());
 820
 821     if ( dir1.IsParallel(dir2,tolang) ) {
 822       // on verifie que l'on n'a pas de cas degenere. Par exemple E1 et E2 connexes
 823       // mais bouclant l'un sur l'autre (cas tres rare)
 824       gp_Pnt pf1 = BRep_Tool::Pnt(TopExp::FirstVertex(E1,Standard_True));
 825       gp_Pnt pl1 = BRep_Tool::Pnt(TopExp::LastVertex(E1,Standard_True));
 826       gp_Pnt pf2 = BRep_Tool::Pnt(TopExp::FirstVertex(E2,Standard_True));
 827       gp_Pnt pl2 = BRep_Tool::Pnt(TopExp::LastVertex(E2,Standard_True));
 828       if ( pl1.Distance(pf2) < tollin && pl2.Distance(pf1) < tollin)
 829         return Standard_False;
 830       else
 831         return Standard_True;
 832     }
 833     return Standard_False;
 834   }
 835   else if (typC1 == STANDARD_TYPE(Geom_Circle)) {
 836     gp_Circ ci1 = Handle(Geom_Circle)::DownCast (C1)->Circ();
 837     gp_Circ ci2 = Handle(Geom_Circle)::DownCast (C2)->Circ();
 838     if (Abs(ci1.Radius()-ci2.Radius()) <= tollin &&
 839         ci1.Location().SquareDistance(ci2.Location()) <= tollin*tollin &&
 840         ci1.Axis().IsParallel(ci2.Axis(),tolang) ) {
 841       // Point debut, calage dans periode, et detection meme sens
 842       return Standard_True;
 843     }
 844     return Standard_False;
 845   }
 846   else if (typC1 == STANDARD_TYPE(Geom_Ellipse)) {
 847     gp_Elips ci1 = Handle(Geom_Ellipse)::DownCast (C1)->Elips();
 848     gp_Elips ci2 = Handle(Geom_Ellipse)::DownCast (C2)->Elips();
 849
 850     if (Abs(ci1.MajorRadius()-ci2.MajorRadius()) <= tollin &&
 851         Abs(ci1.MinorRadius()-ci2.MinorRadius()) <= tollin &&
 852         ci1.Location().SquareDistance(ci2.Location()) <= tollin*tollin &&
 853         ci1.Axis().IsParallel(ci2.Axis(),tolang) ) {
 854       // Point debut, calage dans periode, et detection meme sens
 855       return Standard_True;
 856     }
 857     return Standard_False;
 858   }
 859   else if (typC1 == STANDARD_TYPE(Geom_BSplineCurve)) {
 860
 861     if(myConcatBSpl) {
 862       //Check G1 continuity
 863       gp_Pnt aPf1, aPl1, aPf2, aPl2;
 864       gp_Vec aDf1, aDl1, aDf2, aDl2;
 865
 866       C1->D1(f1, aPf1, aDf1);
 867       C1->D1(l1, aPl1, aDl1);
 868
 869       C2->D1(f2, aPf2, aDf2);
 870       C2->D1(l2, aPl2, aDl2);
 871
 872       if(aPl1.Distance(aPf2) <= tollin && aDl1.IsParallel(aDf2, tolang)) return Standard_True;
 873       if(aPl2.Distance(aPf1) <= tollin && aDl2.IsParallel(aDf1, tolang)) return Standard_True;
 874       if(aPf1.Distance(aPf2) <= tollin && aDf1.IsParallel(aDf2, tolang)) return Standard_True;
 875       if(aPl1.Distance(aPl2) <= tollin && aDl1.IsParallel(aDl2, tolang)) return Standard_True;
 876
 877     }
 878     // we must ensure that before fuse two bsplines, the end of one curve does not
 879     // corresponds to the beginning of the second.
 880     // we could add a special treatment for periodic bspline. This is not done for the moment.
 881     if (Abs(f2-l1) > tollin && Abs(f1-l2) > tollin ) {
 882       return Standard_False;
 883     }
 884
 885     Handle(Geom_BSplineCurve) B1 = Handle(Geom_BSplineCurve)::DownCast (C1);
 886     Handle(Geom_BSplineCurve) B2 = Handle(Geom_BSplineCurve)::DownCast (C2);
 887
 888     Standard_Integer nbpoles = B1->NbPoles();
 889     if (nbpoles != B2->NbPoles()) {
 890       return Standard_False;
 891     }
 892
 893     Standard_Integer nbknots = B1->NbKnots();
 894     if (nbknots != B2->NbKnots()) {
 895       return Standard_False;
 896     }
 897
 898     TColgp_Array1OfPnt P1(1, nbpoles), P2(1, nbpoles);
 899     B1->Poles(P1);
 900     B2->Poles(P2);
 901
 902     Standard_Real tol3d = BRep_Tool::Tolerance(E1);
 903     for (Standard_Integer p = 1; p <= nbpoles; p++) {
 904       if ( (P1(p)).Distance(P2(p)) > tol3d) {
 905         return Standard_False;
 906       }
 907     }
 908
 909     TColStd_Array1OfReal K1(1, nbknots), K2(1, nbknots);
 910     B1->Knots(K1);
 911     B2->Knots(K2);
 912
 913     TColStd_Array1OfInteger M1(1, nbknots), M2(1, nbknots);
 914     B1->Multiplicities(M1);
 915     B2->Multiplicities(M2);
 916
 917     for (Standard_Integer k = 1; k <= nbknots; k++) {
 918       if ((K1(k)-K2(k)) > tollin) {
 919         return Standard_False;
 920       }
 921       if (Abs(M1(k)-M2(k)) > tollin) {
 922         return Standard_False;
 923       }
 924     }
 925
 926     if (!B1->IsRational()) {
 927       if (B2->IsRational()) {
 928         return Standard_False;
 929       }
 930     }
 931     else {
 932       if (!B2->IsRational()) {
 933         return Standard_False;
 934       }
 935     }
 936
 937     if (B1->IsRational()) {
 938       TColStd_Array1OfReal W1(1, nbpoles), W2(1, nbpoles);
 939       B1->Weights(W1);
 940       B2->Weights(W2);
 941
 942       for (Standard_Integer w = 1; w <= nbpoles; w++) {
 943         if (Abs(W1(w)-W2(w)) > tollin) {
 944           return Standard_False;
 945         }
 946       }
 947     }
 948     return Standard_True;
 949   }
 950   else if (typC1 == STANDARD_TYPE(Geom_BezierCurve)) {
 951
 952     // we must ensure that before fuse two bezier, the end of one curve does not
 953     // corresponds to the beginning of the second.
 954     if (Abs(f2-l1) > tollin && Abs(f1-l2) > tollin ) {
 955       return Standard_False;
 956     }
 957
 958     Handle(Geom_BezierCurve) B1 = Handle(Geom_BezierCurve)::DownCast (C1);
 959     Handle(Geom_BezierCurve) B2 = Handle(Geom_BezierCurve)::DownCast (C2);
 960
 961     Standard_Integer nbpoles = B1->NbPoles();
 962     if (nbpoles != B2->NbPoles()) {
 963       return Standard_False;
 964     }
 965
 966     TColgp_Array1OfPnt P1(1, nbpoles), P2(1, nbpoles);
 967     B1->Poles(P1);
 968     B2->Poles(P2);
 969
 970     for (Standard_Integer p = 1; p <= nbpoles; p++) {
 971       if ( (P1(p)).Distance(P2(p)) > tollin) {
 972         return Standard_False;
 973       }
 974     }
 975
 976     if (!B1->IsRational()) {
 977       if (B2->IsRational()) {
 978         return Standard_False;
 979       }
 980     }
 981     else {
 982       if (!B2->IsRational()) {
 983         return Standard_False;
 984       }
 985     }
 986
 987     if (B1->IsRational()) {
 988       TColStd_Array1OfReal W1(1, nbpoles), W2(1, nbpoles);
 989       B1->Weights(W1);
 990       B2->Weights(W2);
 991
 992       for (Standard_Integer w = 1; w <= nbpoles; w++) {
 993         if (Abs(W1(w)-W2(w)) > tollin) {
 994           return Standard_False;
 995         }
 996       }
 997     }
 998     return Standard_True;
 999   }
1000   return Standard_False;
1001 }
1002
1003 //=======================================================================
1004 //function : UpdatePCurve
1005 //purpose  :
1006 //=======================================================================
1007
1008 Standard_Boolean BRepLib_FuseEdges::UpdatePCurve(const TopoDS_Edge& theOldEdge,
1009                                             TopoDS_Edge& theNewEdge,
1010                                             const TopTools_ListOfShape& theLstEdg) const
1011 {
1012
1013
1014 // get the pcurve of edge to substitute (theOldEdge)
1015 // using CurveOnSurface with Index syntax, so we can update the pcurve
1016 // on all the faces
1017   BRep_Builder B;
1018   Handle(Geom2d_Curve) Curv2d;
1019   Handle(Geom_Surface) Surf;
1020   TopLoc_Location loc,locbid;
1021   Standard_Real ef,el,cf,cl;
1022   Standard_Integer iedg = 1;
1023
1024   // take care that we want only Pcurve that maps on the surface where the 3D edges lies.
1025   const TopTools_ListOfShape& LmapFac = myMapEdgLstFac.FindFromKey(theOldEdge);
1026
1027
1028   BRep_Tool::CurveOnSurface(theOldEdge,Curv2d,Surf,loc,cf,cl,iedg);
1029
1030   Standard_Boolean pcurveRebuilt = Standard_False;
1031
1032   while (!Curv2d.IsNull()) {
1033
1034     // we look for a face that contains the same surface as the one that cames
1035     // from CurveOnSurface
1036     Standard_Boolean SameSurf = Standard_False;
1037     TopTools_ListIteratorOfListOfShape itFac;
1038
1039     for (itFac.Initialize(LmapFac); itFac.More(); itFac.Next() ) {
1040       const TopoDS_Shape& face = itFac.Value();
1041       Handle (Geom_Surface) S = BRep_Tool::Surface(TopoDS::Face(face),locbid);
1042       if (S == Surf) {
1043         SameSurf = Standard_True;
1044         break;
1045       }
1046     }
1047
1048     if (SameSurf) {
1049
1050       BRep_Tool::Range(theNewEdge,ef,el);
1051
1052         //modified by NIZNHY-PKV Mon Nov 15 14:59:48 1999 _from
1053       TopoDS_Edge aFEdge = theOldEdge;
1054       aFEdge.Orientation(TopAbs_FORWARD);
1055
1056       // take care if the edge is on the closing curve of a closed surface. In that case
1057       // we get the second pcurve by reversing the edge and calling again CurveOnSurface method
1058
1059       BRep_Tool::CurveOnSurface(aFEdge,Curv2d,Surf,loc,cf,cl,iedg);
1060       if (BRep_Tool::IsClosed(theOldEdge,Surf,loc))  {
1061         aFEdge.Reverse();
1062         TopoDS_Face aFFace = TopoDS::Face(itFac.Value());
1063         aFFace.Orientation(TopAbs_FORWARD);
1064         Handle(Geom2d_Curve) Curv2dR = BRep_Tool::CurveOnSurface(aFEdge,
1065                                                                  aFFace,cf,cl);
1066         if (Curv2d->DynamicType() == STANDARD_TYPE(Geom2d_TrimmedCurve))
1067           Curv2d = Handle(Geom2d_TrimmedCurve)::DownCast (Curv2d)->BasisCurve();
1068         if (Curv2dR->DynamicType() == STANDARD_TYPE(Geom2d_TrimmedCurve))
1069           Curv2dR = Handle(Geom2d_TrimmedCurve)::DownCast (Curv2dR)->BasisCurve();
1070
1071         B.UpdateEdge (theNewEdge,Curv2d,Curv2dR,Surf,loc,BRep_Tool::Tolerance(theNewEdge));
1072       }
1073       else {
1074         // update the new edge
1075         if (Curv2d->DynamicType() == STANDARD_TYPE(Geom2d_TrimmedCurve))
1076           Curv2d = Handle(Geom2d_TrimmedCurve)::DownCast (Curv2d)->BasisCurve();
1077         Standard_Real f, l;
1078         f = Curv2d->FirstParameter();
1079         l = Curv2d->LastParameter();
1080         if (l-f + 2.* Epsilon(l-f) < el-ef)
1081           {
1082             Handle(Geom2d_BoundedCurve) bcurve = Handle(Geom2d_BoundedCurve)::DownCast(Curv2d);
1083             if (bcurve.IsNull())
1084               bcurve = new Geom2d_TrimmedCurve( Curv2d, cf, cl );
1085             Geom2dConvert_CompCurveToBSplineCurve Concat( bcurve );
1086             TopTools_ListIteratorOfListOfShape iter( theLstEdg );
1087             iter.Next();
1088             for (; iter.More(); iter.Next())
1089               {
1090                 TopoDS_Edge& E = TopoDS::Edge(iter.Value());
1091                 Standard_Real first, last;
1092                 Handle(Geom2d_Curve) C = BRep_Tool::CurveOnSurface( E, Surf, loc, first, last );
1093                 Handle(Geom2d_BoundedCurve) BC = Handle(Geom2d_BoundedCurve)::DownCast(C);
1094                 if (BC.IsNull())
1095                   BC = new Geom2d_TrimmedCurve( C, first, last );
1096                 if (!Concat.Add( BC, Precision::PConfusion() ))
1097                   // cannot merge pcurves
1098                   return Standard_False;
1099               }
1100             Curv2d = Concat.BSplineCurve();
1101
1102             // check that new curve 2d is same range
1103             Standard_Real first = Curv2d->FirstParameter();
1104             Standard_Real last = Curv2d->LastParameter();
1105             if (Abs (first - ef) > Precision::PConfusion() ||
1106                 Abs (last - el) > Precision::PConfusion())
1107             {
1108               Handle(Geom2d_BSplineCurve) bc = Handle(Geom2d_BSplineCurve)::DownCast(Curv2d);
1109               TColStd_Array1OfReal Knots (1, bc->NbKnots());
1110               bc->Knots(Knots);
1111               BSplCLib::Reparametrize (ef, el, Knots);
1112               bc->SetKnots(Knots);
1113             }
1114             pcurveRebuilt = Standard_True;
1115           }
1116
1117         B.UpdateEdge (theNewEdge,Curv2d,Surf,loc,BRep_Tool::Tolerance(theNewEdge));
1118       }
1119
1120       // the old pcurve range is cf,cl. The new 3d edge range is ef,el. if we want
1121       // the pcurve to be samerange we must adapt the parameter of the edge. In general
1122       // cases cf=ef and cl=el expect for periodic curve if the new edge is going over
1123       // the value 0.
1124       if(!pcurveRebuilt) {
1125         if (theOldEdge.Orientation()== TopAbs_REVERSED) {
1126           B.Range(theNewEdge,cl-el+ef,cl);
1127         }
1128         else {
1129           B.Range(theNewEdge,cf,cf+el-ef);
1130         }
1131       }
1132      }
1133
1134     // get next pcurve
1135     iedg++;
1136     BRep_Tool::CurveOnSurface(theOldEdge,Curv2d,Surf,loc,cf,cl,iedg);
1137   }
1138
1139   if (pcurveRebuilt)
1140   {
1141     // force same parameter
1142     B.SameParameter (theNewEdge, Standard_False);
1143     BRepLib::SameParameter (theNewEdge, BRep_Tool::Tolerance(theNewEdge));
1144   }
1145
1146   return Standard_True;
1147 }
1148
1149