src/IntTools/IntTools_EdgeEdge.cxx

   1 // Created by: Eugeny MALTCHIKOV
   2 // Copyright (c) 2013-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15 #include <IntTools_EdgeEdge.ixx>
  16
  17 #include <NCollection_UBTreeFiller.hxx>
  18
  19 #include <gp_Dir.hxx>
  20 #include <gp_Lin.hxx>
  21
  22 #include <ElCLib.hxx>
  23
  24 #include <TopoDS_Iterator.hxx>
  25
  26 #include <Bnd_Box.hxx>
  27 #include <BndLib_Add3dCurve.hxx>
  28
  29 #include <GeomAPI_ProjectPointOnCurve.hxx>
  30
  31 #include <BRep_Tool.hxx>
  32 #include <BRepAdaptor_Curve.hxx>
  33
  34 #include <BOPCol_MapOfInteger.hxx>
  35 #include <BOPCol_BoxBndTree.hxx>
  36
  37 #include <IntTools_Tools.hxx>
  38 #include <IntTools_CommonPrt.hxx>
  39
  40 static
  41   Standard_Boolean BndCommon(const Bnd_Box& theB1,
  42                              const Bnd_Box& theB2,
  43                              Bnd_Box& theBOut);
  44 static
  45   void BndBuildBox(const BRepAdaptor_Curve& theBAC,
  46                    const Standard_Real aT1,
  47                    const Standard_Real aT2,
  48                    const Standard_Real theTol,
  49                    Bnd_Box& theBox);
  50 static
  51   Standard_Boolean SplitRangeOnSegments(const Standard_Real aT1,
  52                                         const Standard_Real aT2,
  53                                         const Standard_Real theResolution,
  54                                         const Standard_Integer theNbSeg,
  55                                         IntTools_SequenceOfRanges& theSegments);
  56 static
  57   void SplitRangeOnTwo(const Standard_Real aT1,
  58                        const Standard_Real aT2,
  59                        IntTools_SequenceOfRanges& theSegments);
  60 static
  61  Standard_Integer DistPC(const Standard_Real aT1,
  62                          const Handle(Geom_Curve)& theC1,
  63                          const Standard_Real theCriteria,
  64                          GeomAPI_ProjectPointOnCurve& theProjector,
  65                          Standard_Real& aD,
  66                          Standard_Real& aT2,
  67                          const Standard_Integer iC = 1);
  68 static
  69  Standard_Integer DistPC(const Standard_Real aT1,
  70                          const Handle(Geom_Curve)& theC1,
  71                          const Standard_Real theCriteria,
  72                          GeomAPI_ProjectPointOnCurve& theProjector,
  73                          Standard_Real& aD,
  74                          Standard_Real& aT2,
  75                          Standard_Real& aDmax,
  76                          Standard_Real& aT1max,
  77                          Standard_Real& aT2max,
  78                          const Standard_Integer iC = 1);
  79 static
  80   Standard_Integer FindDistPC(const Standard_Real aT1A,
  81                               const Standard_Real aT1B,
  82                               const Handle(Geom_Curve)& theC1,
  83                               const Standard_Real theCriteria,
  84                               const Standard_Real theEps,
  85                               GeomAPI_ProjectPointOnCurve& theProjector,
  86                               Standard_Real& aDmax,
  87                               Standard_Real& aT1max,
  88                               Standard_Real& aT2max,
  89                               const Standard_Boolean bMaxDist = Standard_True);
  90 static
  91   Standard_Integer TypeToInteger(const GeomAbs_CurveType theCType);
  92
  93 //=======================================================================
  94 //function : Prepare
  95 //purpose  :
  96 //=======================================================================
  97 void IntTools_EdgeEdge::Prepare()
  98 {
  99   GeomAbs_CurveType aCT1, aCT2;
 100   Standard_Integer iCT1, iCT2;
 101   //
 102   myCurve1.Initialize(myEdge1);
 103   myCurve2.Initialize(myEdge2);
 104   //
 105   if (myRange1.First() == 0. && myRange1.Last() == 0.) {
 106     myRange1.SetFirst(myCurve1.FirstParameter());
 107     myRange1.SetLast (myCurve1.LastParameter());
 108   }
 109   //
 110   if (myRange2.First() == 0. && myRange2.Last() == 0.) {
 111     myRange2.SetFirst(myCurve2.FirstParameter());
 112     myRange2.SetLast (myCurve2.LastParameter());
 113   }
 114   //
 115   aCT1 = myCurve1.GetType();
 116   aCT2 = myCurve2.GetType();
 117   //
 118   iCT1 = TypeToInteger(aCT1);
 119   iCT2 = TypeToInteger(aCT2);
 120   //
 121   if (iCT1 == iCT2) {
 122     if (iCT1 != 0) {
 123       //compute deflection
 124       Standard_Integer i;
 125       Standard_Real aDt, aT, aT1, aT2;
 126       gp_Vec aV1, aV2;
 127       gp_Pnt aP;
 128       //
 129       Standard_Real aC1(0.), aC2(0.);
 130       for (i = 0; i < 2; ++i) {
 131         Standard_Real &aC = !i ? aC1 : aC2;
 132         IntTools_Range aR = !i ? myRange1 : myRange2;
 133         const BRepAdaptor_Curve& aBAC = !i ? myCurve1 : myCurve2;
 134         aR.Range(aT1, aT2);
 135         aDt = (aT2 - aT1) / 10.;
 136         aT = aT1;
 137         aBAC.D1(aT, aP, aV1);
 138         while (aT < aT2) {
 139           aT += aDt;
 140           aBAC.D1(aT, aP, aV2);
 141           if (aV1.Magnitude() > gp::Resolution() &&
 142               aV2.Magnitude() > gp::Resolution()) {
 143             gp_Dir aD1(aV1), aD2(aV2);
 144             aC += aD1.Angle(aD2);
 145           }
 146           aV1 = aV2;
 147         }
 148       }
 149       //
 150       if (aC1 < aC2) {
 151         --iCT1;
 152       }
 153     }
 154   }
 155   //
 156   if (iCT1 < iCT2) {
 157     TopoDS_Edge tmpE = myEdge1;
 158     myEdge1 = myEdge2;
 159     myEdge2 = tmpE;
 160     //
 161     BRepAdaptor_Curve tmpC = myCurve1;
 162     myCurve1 = myCurve2;
 163     myCurve2 = tmpC;
 164     //
 165     IntTools_Range tmpR = myRange1;
 166     myRange1 = myRange2;
 167     myRange2 = tmpR;
 168     //
 169     mySwap = Standard_True;
 170   }
 171   //
 172   myTol1 = myCurve1.Tolerance();
 173   myTol2 = myCurve2.Tolerance();
 174   myTol = myTol1 + myTol2;
 175   //
 176   myRes1 = myCurve1.Resolution(myTol);
 177   myRes2 = myCurve2.Resolution(myTol);
 178   //
 179   if (iCT1 != 0 || iCT2 != 0) {
 180     Standard_Real f, l;
 181     myGeom1 = BRep_Tool::Curve(myEdge1, f, l);
 182     myGeom2 = BRep_Tool::Curve(myEdge2, f, l);
 183   }
 184 }
 185
 186 //=======================================================================
 187 //function : Perform
 188 //purpose  :
 189 //=======================================================================
 190 void IntTools_EdgeEdge::Perform()
 191 {
 192   //1. Check data
 193   CheckData();
 194   if (myErrorStatus) {
 195     return;
 196   }
 197   //
 198   //2. Prepare Data
 199   Prepare();
 200   //
 201   //3.1. Check Line/Line case
 202   if (myCurve1.GetType() == GeomAbs_Line &&
 203       myCurve2.GetType() == GeomAbs_Line) {
 204     ComputeLineLine();
 205     return;
 206   }
 207   //
 208   //3.2. Find solutions
 209   IntTools_SequenceOfRanges aRanges1, aRanges2;
 210   //
 211   FindSolutions(aRanges1, aRanges2);
 212   //
 213   //4. Merge solutions and save common parts
 214   MergeSolutions(aRanges1, aRanges2);
 215 }
 216
 217 //=======================================================================
 218 //function : FindSolutions
 219 //purpose  :
 220 //=======================================================================
 221 void IntTools_EdgeEdge::FindSolutions(IntTools_SequenceOfRanges& theRanges1,
 222                                       IntTools_SequenceOfRanges& theRanges2)
 223 {
 224   // According to the common box of the edges decide which method to use
 225   Standard_Real aT11, aT12, aT21, aT22;
 226   Bnd_Box aB1, aB2, aBC;
 227   //
 228   myRange1.Range(aT11, aT12);
 229   myRange2.Range(aT21, aT22);
 230   //
 231   BndBuildBox(myCurve1, aT11, aT12, myTol1, aB1);
 232   BndBuildBox(myCurve2, aT21, aT22, myTol2, aB2);
 233   //
 234   if (!BndCommon(aB1, aB2, aBC)) {
 235     // No intersections at all
 236     return;
 237   }
 238   //
 239   if (aBC.IsThin(10*myTol)) {
 240     // As soon as the common box of the edges is thin,
 241     // find exact solution at once
 242     FindSolutions(myRange1, myRange2, aBC, theRanges1, theRanges2);
 243   }
 244   else {
 245     // First find the rough ranges containing solutions,
 246     // than find exact ranges
 247     IntTools_SequenceOfRanges aSegments1;
 248     Standard_Integer i, aNb;
 249     //
 250     // Find rough ranges
 251     FindRoughRanges(myRange1, myRange2, aSegments1);
 252     aNb = aSegments1.Length();
 253     // Find exact ranges
 254     for (i = 1; i <= aNb; ++i) {
 255       const IntTools_Range& aR1 = aSegments1(i);
 256       aR1.Range(aT11, aT12);
 257       BndBuildBox(myCurve1, aT11, aT12, myTol1, aB1);
 258       if (BndCommon(aB1, aB2, aBC)) {
 259         FindSolutions(aR1, myRange2, aBC, theRanges1, theRanges2);
 260       }
 261     }
 262   }
 263 }
 264
 265 //=======================================================================
 266 //function : FindSolutions
 267 //purpose  :
 268 //=======================================================================
 269 void IntTools_EdgeEdge::FindSolutions(const IntTools_Range& theR1,
 270                                       const IntTools_Range& theR2,
 271                                       const Bnd_Box& theBC,
 272                                       IntTools_SequenceOfRanges& theRanges1,
 273                                       IntTools_SequenceOfRanges& theRanges2)
 274 {
 275   Standard_Boolean bOut, bStop, bThin;
 276   Standard_Real aT11, aT12, aT21, aT22;
 277   Standard_Real aTB11, aTB12, aTB21, aTB22;
 278   Standard_Real aTol, aSmallStep1, aSmallStep2;
 279   Standard_Integer iCom;
 280   Bnd_Box aB1, aB2;
 281   //
 282   theR1.Range(aT11, aT12);
 283   theR2.Range(aT21, aT22);
 284   aB1 = theBC;
 285   //
 286   bOut  = Standard_False;
 287   bThin = Standard_False;
 288   bStop = Standard_False;
 289   aTol  = 2*myTol;
 290   iCom  = 1;
 291   //
 292   do {
 293     bOut = !FindParameters(myCurve2, aT21, aT22, myRes2, aB1, aTB21, aTB22);
 294     if (bOut) {
 295       break;
 296     }
 297     //
 298     bThin = (aTB22 - aTB21) < myRes2;
 299     if (bThin) {
 300       bOut = !FindParameters(myCurve1, aT11, aT12, myRes1, aB1, aTB11, aTB12);
 301       break;
 302     }
 303     //
 304     BndBuildBox(myCurve2, aTB21, aTB22, myTol2, aB2);
 305     BndCommon(aB1, aB2, aB2);
 306     //
 307     bOut = !FindParameters(myCurve1, aT11, aT12, myRes1, aB2, aTB11, aTB12);
 308     if (bOut) {
 309       break;
 310     }
 311     //
 312     bThin = ((aTB12 - aTB11) < myRes1) ||
 313       (aB2.IsXThin(aTol) && aB2.IsYThin(aTol) && aB2.IsZThin(aTol));
 314     //
 315     if (!bThin) {
 316       aSmallStep1 = (aT12 - aT11) / 250.;
 317       aSmallStep2 = (aT22 - aT21) / 250.;
 318       //
 319       if (aSmallStep1 < myRes1) {
 320         aSmallStep1 = myRes1;
 321       }
 322       if (aSmallStep2 < myRes2) {
 323         aSmallStep2 = myRes2;
 324       }
 325       //
 326       if (((aTB11 - aT11) < aSmallStep1) && ((aT12 - aTB12) < aSmallStep1) &&
 327           ((aTB21 - aT21) < aSmallStep2) && ((aT22 - aTB22) < aSmallStep2)) {
 328         bStop = Standard_True;
 329       } else {
 330         BndBuildBox(myCurve1, aTB11, aTB12, myTol1, aB1);
 331         bOut = !BndCommon(aB1, aB2, aB1);
 332         if (bOut) {
 333           break;
 334         }
 335       }
 336     }
 337     //
 338     aT11 = aTB11;
 339     aT12 = aTB12;
 340     aT21 = aTB21;
 341     aT22 = aTB22;
 342   } while (!bThin && !bStop);
 343   //
 344   if (bOut) {
 345     //no intersection;
 346     return;
 347   }
 348   //
 349   if (!bThin) {
 350     //check curves for coincidence on the ranges
 351     iCom = CheckCoincidence(aT11, aT12, aT21, aT22, myTol, myRes1);
 352     if (!iCom) {
 353       bThin = Standard_True;
 354     }
 355   }
 356   //
 357   if (bThin) {
 358     if (iCom != 0) {
 359       //check intermediate points
 360       Standard_Real aT1, aT2, aDist;
 361       gp_Pnt aP1, aP2;
 362       //
 363       aT1 = IntTools_Tools::IntermediatePoint(aT11, aT12);
 364       aT2 = IntTools_Tools::IntermediatePoint(aT21, aT22);
 365       //
 366       aP1 = myGeom1->Value(aT1);
 367       aP2 = myGeom2->Value(aT2);
 368       //
 369       aDist = aP1.Distance(aP2);
 370       if (aDist > myTol) {
 371         return;
 372       }
 373     }
 374     //add common part
 375     IntTools_Range aR1(aT11, aT12), aR2(aT21, aT22);
 376     //
 377     theRanges1.Append(aR1);
 378     theRanges2.Append(aR2);
 379     return;
 380   }
 381   //
 382   if (!IsIntersection(aT11, aT12, aT21, aT22)) {
 383     return;
 384   }
 385   //
 386   //split ranges on segments and repeat
 387   Standard_Integer i, aNb1;
 388   IntTools_SequenceOfRanges aSegments1;
 389   //
 390   IntTools_Range aR2(aT21, aT22);
 391   BndBuildBox(myCurve2, aT21, aT22, myTol2, aB2);
 392   //
 393   SplitRangeOnSegments(aT11, aT12, myRes1, 3, aSegments1);
 394   aNb1 = aSegments1.Length();
 395   for (i = 1; i <= aNb1; ++i) {
 396     const IntTools_Range& aR1 = aSegments1(i);
 397     aR1.Range(aT11, aT12);
 398     BndBuildBox(myCurve1, aT11, aT12, myTol1, aB1);
 399     if (BndCommon(aB1, aB2, aB1)) {
 400       FindSolutions(aR1, aR2, aB1, theRanges1, theRanges2);
 401     }
 402   }
 403 }
 404
 405 //=======================================================================
 406 //function : FindParameters
 407 //purpose  :
 408 //=======================================================================
 409 Standard_Boolean IntTools_EdgeEdge::FindParameters(const BRepAdaptor_Curve& theBAC,
 410                                                    const Standard_Real aT1,
 411                                                    const Standard_Real aT2,
 412                                                    const Standard_Real theRes,
 413                                                    const Bnd_Box& theCBox,
 414                                                    Standard_Real& aTB1,
 415                                                    Standard_Real& aTB2)
 416 {
 417   Standard_Boolean bRet;
 418   Standard_Integer aC, i, k;
 419   Standard_Real aCf, aDiff, aDt, aT, aTB, aTOut, aTIn, aPTol, aTol,
 420                 aDist, aDistP;
 421   gp_Pnt aP;
 422   Bnd_Box aCBx;
 423   //
 424   bRet = Standard_False;
 425   aCf = 0.6180339887498948482045868343656;// =0.5*(1.+sqrt(5.))/2.;
 426   aDt = theRes;
 427   aPTol = theRes * 0.001;
 428   aTol = theBAC.Tolerance();
 429   aDistP = 0.;
 430   aCBx = theCBox;
 431   aCBx.Enlarge(aTol);
 432   //
 433   for (i = 0; i < 2; ++i) {
 434     aTB = !i ? aT1 : aT2;
 435     aT = !i ? aT2 : aTB1;
 436     aC = !i ? 1 : -1;
 437     bRet = Standard_False;
 438     k = 0;
 439     //looking for the point on the edge which is in the box;
 440     while (aC*(aT-aTB) >= 0) {
 441       aP = theBAC.Value(aTB);
 442       Bnd_Box aBP;
 443       aBP.Add(aP);
 444       aDist = aBP.Distance(theCBox);
 445       k = (fabs(aDist - aDistP) < Precision::PConfusion()) ? k+1 : 0;
 446       if (aDist > aTol) {
 447         aDt = theBAC.Resolution(aDist*Max(k, 1));
 448         aTB += aC*aDt;
 449       } else {
 450         bRet = Standard_True;
 451         break;
 452       }
 453       aDistP = aDist;
 454     }
 455     //
 456     if (!bRet) {
 457       if (!i) {
 458         //edge is out of the box;
 459         return bRet;
 460       } else {
 461         bRet = !bRet;
 462         aTB = aTB1;
 463         aDt = aT2 - aTB1;
 464       }
 465     }
 466     //
 467     aT = !i ? aT1 : aT2;
 468     if (aTB != aT) {
 469       //one point IN, one point OUT; looking for the bounding point;
 470       aTIn = aTB;
 471       aTOut = aTB - aC*aDt;
 472       aDiff = aTIn - aTOut;
 473       while (fabs(aDiff) > aPTol) {
 474         aTB = aTOut + aDiff*aCf;
 475         aP = theBAC.Value(aTB);
 476         if (aCBx.IsOut(aP)) {
 477           aTOut = aTB;
 478         } else {
 479           aTIn = aTB;
 480         }
 481         aDiff = aTIn - aTOut;
 482       }
 483     }
 484     if (!i) {
 485       aTB1 = aTB;
 486     } else {
 487       aTB2 = aTB;
 488     }
 489   }
 490   return bRet;
 491 }
 492
 493 //=======================================================================
 494 //function : MergeSolutions
 495 //purpose  :
 496 //=======================================================================
 497 void IntTools_EdgeEdge::MergeSolutions(const IntTools_SequenceOfRanges& theRanges1,
 498                                        const IntTools_SequenceOfRanges& theRanges2)
 499 {
 500   IntTools_Range aRi1, aRi2, aRj1, aRj2;
 501   Standard_Integer aNbCP, i, j;
 502   TopAbs_ShapeEnum aType;
 503   Standard_Real aTi11, aTi12, aTi21, aTi22,
 504                 aTj11, aTj12, aTj21, aTj22;
 505   //
 506   aNbCP = theRanges1.Length();
 507   aType = TopAbs_VERTEX;
 508   //
 509   for (i = 1; i <= aNbCP; ) {
 510     aRi1 = theRanges1(i);
 511     aRi2 = theRanges2(i);
 512     //
 513     aRi1.Range(aTi11, aTi12);
 514     aRi2.Range(aTi21, aTi22);
 515     //
 516     for (j = i+1; j <= aNbCP; ++j) {
 517       aRj1 = theRanges1(j);
 518       aRj2 = theRanges2(j);
 519       //
 520       aRj1.Range(aTj11, aTj12);
 521       aRj2.Range(aTj21, aTj22);
 522       if (fabs(aTi12 - aTj11) < 10*myRes1 ||
 523           fabs(aTi22 - aTj21) < 10*myRes2) {
 524         aTi11 = Min(aTi11, aTj11);
 525         aTi12 = Max(aTi12, aTj12);
 526         aTi21 = Min(aTi21, aTj21);
 527         aTi22 = Max(aTi22, aTj22);
 528       } else {
 529         break;
 530       }
 531     }
 532     i = j;
 533     //
 534     if (aTi11 == myRange1.First() && aTi12 == myRange1.Last() &&
 535         aTi21 == myRange2.First() && aTi22 == myRange2.Last()) {
 536       aType = TopAbs_EDGE;
 537     }
 538     //
 539     AddSolution(aTi11, aTi12, aTi21, aTi22, aType);
 540   }
 541 }
 542
 543 //=======================================================================
 544 //function : AddSolution
 545 //purpose  :
 546 //=======================================================================
 547 void IntTools_EdgeEdge::AddSolution(const Standard_Real aT11,
 548                                     const Standard_Real aT12,
 549                                     const Standard_Real aT21,
 550                                     const Standard_Real aT22,
 551                                     const TopAbs_ShapeEnum theType)
 552 {
 553   IntTools_CommonPrt aCPart;
 554   //
 555   aCPart.SetType(theType);
 556   if (!mySwap) {
 557     aCPart.SetEdge1(myEdge1);
 558     aCPart.SetEdge2(myEdge2);
 559     aCPart.SetRange1(aT11, aT12);
 560     aCPart.AppendRange2(aT21, aT22);
 561   } else {
 562     aCPart.SetEdge1(myEdge2);
 563     aCPart.SetEdge2(myEdge1);
 564     aCPart.SetRange1(aT21, aT22);
 565     aCPart.AppendRange2(aT11, aT12);
 566   }
 567   //
 568   if (theType == TopAbs_VERTEX) {
 569     Standard_Real aT1, aT2;
 570     //
 571     FindBestSolution(aT11, aT12, aT21, aT22, aT1, aT2);
 572     //
 573     if (!mySwap) {
 574       aCPart.SetVertexParameter1(aT1);
 575       aCPart.SetVertexParameter2(aT2);
 576     } else {
 577       aCPart.SetVertexParameter1(aT2);
 578       aCPart.SetVertexParameter2(aT1);
 579     }
 580   }
 581   myCommonParts.Append(aCPart);
 582 }
 583
 584 //=======================================================================
 585 //function : FindBestSolution
 586 //purpose  :
 587 //=======================================================================
 588 void IntTools_EdgeEdge::FindBestSolution(const Standard_Real aT11,
 589                                          const Standard_Real aT12,
 590                                          const Standard_Real aT21,
 591                                          const Standard_Real aT22,
 592                                          Standard_Real& aT1,
 593                                          Standard_Real& aT2)
 594 {
 595   Standard_Integer i, aNbS, iErr;
 596   Standard_Real aDMin, aD, aCrit, aMinStep, aTMax;
 597   Standard_Real aT1x, aT2x, aT1p, aT2p;
 598   GeomAPI_ProjectPointOnCurve aProj;
 599   IntTools_SequenceOfRanges aSeg1;
 600   //
 601   aT1 = IntTools_Tools::IntermediatePoint(aT11, aT12);
 602   aT2 = IntTools_Tools::IntermediatePoint(aT21, aT22);
 603   //
 604   aDMin = 100.;
 605   aD = 100.;
 606   aCrit = 1.e-16;
 607   aMinStep = 5.e-13;
 608   aTMax = Max(fabs(aT11), fabs(aT12));
 609   if (aTMax > 999.) {
 610     aMinStep = 5.e-16 * aTMax;
 611   }
 612   //
 613   aNbS = 10;
 614   SplitRangeOnSegments(aT11, aT12, 3*myRes1, aNbS, aSeg1);
 615   aNbS = aSeg1.Length();
 616   //
 617   aProj.Init(myGeom2, aT21, aT22);
 618   for (i = 1; i <= aNbS; ++i) {
 619     const IntTools_Range& aR1 = aSeg1(i);
 620     aR1.Range(aT1x, aT2x);
 621     //
 622     iErr = FindDistPC(aT1x, aT2x, myGeom1, aCrit, aMinStep,
 623                       aProj, aD, aT1p, aT2p, Standard_False);
 624     if (iErr != 1 && aD < aDMin) {
 625       aT1 = aT1p;
 626       aT2 = aT2p;
 627       aDMin = aD;
 628       if (aDMin < aCrit) {
 629         break;
 630       }
 631     }
 632   }
 633 }
 634
 635 //=======================================================================
 636 //function : ComputeLineLine
 637 //purpose  :
 638 //=======================================================================
 639 void IntTools_EdgeEdge::ComputeLineLine()
 640 {
 641   Standard_Boolean IsParallel, IsCoincide;
 642   Standard_Real aSin, aCos, aAng, aTol;
 643   Standard_Real aT1, aT2, aT11, aT12, aT21, aT22;
 644   gp_Pnt aP11, aP12;
 645   gp_Lin aL1, aL2;
 646   gp_Dir aD1, aD2;
 647   IntTools_CommonPrt aCommonPrt;
 648   //
 649   IsParallel = Standard_False;
 650   IsCoincide = Standard_False;
 651   aTol = myTol*myTol;
 652   aL1 = myCurve1.Line();
 653   aL2 = myCurve2.Line();
 654   aD1 = aL1.Position().Direction();
 655   aD2 = aL2.Position().Direction();
 656   myRange1.Range(aT11, aT12);
 657   myRange2.Range(aT21, aT22);
 658   //
 659   aCommonPrt.SetEdge1(myEdge1);
 660   aCommonPrt.SetEdge2(myEdge2);
 661   //
 662   aCos = aD1.Dot(aD2);
 663   aAng = (aCos >= 0.) ? 2.*(1. - aCos) : 2.*(1. + aCos);
 664   //
 665   if(aAng <= Precision::Angular()) {
 666     IsParallel = Standard_True;
 667     if(aL1.SquareDistance(aL2.Location()) <= aTol) {
 668       IsCoincide = Standard_True;
 669       aP11 = ElCLib::Value(aT11, aL1);
 670       aP12 = ElCLib::Value(aT12, aL1);
 671     }
 672   }
 673   else {
 674     aP11 = ElCLib::Value(aT11, aL1);
 675     aP12 = ElCLib::Value(aT12, aL1);
 676     if(aL2.SquareDistance(aP11) <= aTol && aL2.SquareDistance(aP12) <= aTol) {
 677       IsCoincide = Standard_True;
 678     }
 679   }
 680   //
 681   if (IsCoincide) {
 682     Standard_Real t21, t22;
 683     //
 684     t21 = ElCLib::Parameter(aL2, aP11);
 685     t22 = ElCLib::Parameter(aL2, aP12);
 686     if((t21 > aT22 && t22 > aT22) || (t21 < aT21 && t22 < aT21)) {
 687       return;
 688     }
 689     //
 690     Standard_Real temp;
 691     if(t21 > t22) {
 692       temp = t21;
 693       t21 = t22;
 694       t22 = temp;
 695     }
 696     //
 697     if(t21 >= aT21) {
 698       if(t22 <= aT22) {
 699         aCommonPrt.SetRange1(aT11, aT12);
 700         aCommonPrt.SetAllNullFlag(Standard_True);
 701         aCommonPrt.AppendRange2(t21, t22);
 702       }
 703       else {
 704         aCommonPrt.SetRange1(aT11, aT12 - (t22 - aT22));
 705         aCommonPrt.AppendRange2(t21, aT22);
 706       }
 707     }
 708     else {
 709       aCommonPrt.SetRange1(aT11 + (aT21 - t21), aT12);
 710       aCommonPrt.AppendRange2(aT21, t22);
 711     }
 712     aCommonPrt.SetType(TopAbs_EDGE);
 713     myCommonParts.Append(aCommonPrt);
 714     return;
 715   }
 716   //
 717   if (IsParallel) {
 718     return;
 719   }
 720   //
 721   {
 722     TopoDS_Iterator aIt1, aIt2;
 723     aIt1.Initialize(myEdge1);
 724     for (; aIt1.More(); aIt1.Next()) {
 725       const TopoDS_Shape& aV1 = aIt1.Value();
 726       aIt2.Initialize(myEdge2);
 727       for (; aIt2.More(); aIt2.Next()) {
 728         const TopoDS_Shape& aV2 = aIt2.Value();
 729         if (aV2.IsSame(aV1)) {
 730           return;
 731         }
 732       }
 733     }
 734   }
 735   //
 736   aSin = 1. - aCos*aCos;
 737   gp_Pnt O1 = aL1.Location();
 738   gp_Pnt O2 = aL2.Location();
 739   gp_Vec O1O2 (O1, O2);
 740   //
 741   aT2 = (aD1.XYZ()*(O1O2.Dot(aD1))-(O1O2.XYZ())).Dot(aD2.XYZ());
 742   aT2 /= aSin;
 743   //
 744   if(aT2 < aT21 || aT2 > aT22) {
 745     return;
 746   }
 747   //
 748   gp_Pnt aP2(ElCLib::Value(aT2, aL2));
 749   aT1 = (gp_Vec(O1, aP2)).Dot(aD1);
 750   //
 751   if(aT1 < aT11 || aT1 > aT12) {
 752     return;
 753   }
 754   //
 755   gp_Pnt aP1(ElCLib::Value(aT1, aL1));
 756   Standard_Real aDist = aP1.SquareDistance(aP2);
 757   //
 758   if (aDist > aTol) {
 759     return;
 760   }
 761   //
 762   aCommonPrt.SetRange1(aT1 - myTol, aT1 + myTol);
 763   aCommonPrt.AppendRange2(aT2 - myTol, aT2 + myTol);
 764   aCommonPrt.SetType(TopAbs_VERTEX);
 765   aCommonPrt.SetVertexParameter1(aT1);
 766   aCommonPrt.SetVertexParameter2(aT2);
 767   myCommonParts.Append(aCommonPrt);
 768 }
 769
 770 //=======================================================================
 771 //function : FindRoughRanges
 772 //purpose  :
 773 //=======================================================================
 774 Standard_Integer IntTools_EdgeEdge::FindRoughRanges(const IntTools_Range& theR1,
 775                                                     const IntTools_Range& theR2,
 776                                                     IntTools_SequenceOfRanges& theSegments1)
 777 {
 778   Standard_Integer iRet, i, j, aNbi, aNbj, aNbSD;
 779   Standard_Real aTi1, aTi2, aTj1, aTj2, aDi, aDj;
 780   IntTools_SequenceOfRanges aSi, aSj, aNewSi, aNewSj;
 781   BOPCol_MapOfInteger aMj;
 782   BOPCol_ListIteratorOfListOfInteger aItLI;
 783   Bnd_Box aBi, aBj;
 784   BOPCol_BoxBndTreeSelector aSelector;
 785   BOPCol_BoxBndTree aBBTree;
 786   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
 787   //
 788   theR1.Range(aTi1, aTi2);
 789   theR2.Range(aTj1, aTj2);
 790   aDi = (aTi2 - aTi1) / 2.;
 791   aDj = (aTj2 - aTj1) / 2.;
 792   aNbi = 2;
 793   aNbj = 2;
 794   //
 795   SplitRangeOnTwo(aTi1, aTi2, aSi);
 796   SplitRangeOnTwo(aTj1, aTj2, aSj);
 797   //
 798   while (aDi > myRes1 || aDj > myRes2) {
 799     aDi /= 2.;
 800     aDj /= 2.;
 801     //
 802     aBBTree.Clear();
 803     aTreeFiller.Reset();
 804     for (j = 1; j <= aNbj; ++j) {
 805       const IntTools_Range& aRj = aSj(j);
 806       aRj.Range(aTj1, aTj2);
 807       //
 808       BndBuildBox(myCurve2, aTj1, aTj2, myTol2, aBj);
 809       //
 810       aTreeFiller.Add(j, aBj);
 811     }
 812     //
 813     aTreeFiller.Fill();
 814     //
 815     for (i = 1; i <= aNbi; ++i) {
 816       const IntTools_Range& aRi = aSi(i);
 817       aRi.Range(aTi1, aTi2);
 818       //
 819       BndBuildBox(myCurve1, aTi1, aTi2, myTol1, aBi);
 820       //
 821       aSelector.Clear();
 822       aSelector.SetBox(aBi);
 823       //
 824       aNbSD = aBBTree.Select(aSelector);
 825       if (!aNbSD){
 826         continue;
 827       }
 828       //
 829       SplitRangeOnTwo(aTi1, aTi2, aNewSi);
 830       //
 831       const BOPCol_ListOfInteger& aLI = aSelector.Indices();
 832       aItLI.Initialize(aLI);
 833       for (; aItLI.More(); aItLI.Next()) {
 834         j = aItLI.Value();
 835         if (aMj.Add(j)) {
 836           const IntTools_Range& aRj = aSj(j);
 837           aRj.Range(aTj1, aTj2);
 838           SplitRangeOnTwo(aTj1, aTj2, aNewSj);
 839         }
 840       }
 841     }
 842     //
 843     aSi.Assign(aNewSi);
 844     aSj.Assign(aNewSj);
 845     aNbi = aSi.Length();
 846     aNbj = aSj.Length();
 847     //
 848     if ((aNbi == 0) || (aNbj == 0) || (aNbi > 500) || (aNbj > 500)) {
 849       break;
 850     }
 851     //
 852     aNewSi.Clear();
 853     aNewSj.Clear();
 854     aMj.Clear();
 855   }
 856   //
 857   iRet = (aNbi && aNbj) ? 1 : 0;
 858   if (iRet) {
 859     //collect ranges
 860     IntTools_Range aRi1 = aSi(1), aRi2;
 861     Standard_Real aT1 = aRi1.First();
 862     for (i = 2; i <= aNbi; ++i) {
 863       aRi2 = aSi(i);
 864       if ((aRi2.First() - aRi1.Last()) > myRes1) {
 865         theSegments1.Append(IntTools_Range(aT1, aRi1.Last()));
 866         aT1 = aRi2.First();
 867       }
 868       aRi1 = aRi2;
 869     }
 870     theSegments1.Append(IntTools_Range(aT1, aRi2.Last()));
 871   }
 872   //
 873   return iRet;
 874 }
 875
 876 //=======================================================================
 877 //function : IsIntersection
 878 //purpose  :
 879 //=======================================================================
 880 Standard_Boolean IntTools_EdgeEdge::IsIntersection(const Standard_Real aT11,
 881                                                    const Standard_Real aT12,
 882                                                    const Standard_Real aT21,
 883                                                    const Standard_Real aT22)
 884 {
 885   Standard_Boolean bRet;
 886   gp_Pnt aP11, aP12, aP21, aP22;
 887   gp_Vec aV11, aV12, aV21, aV22;
 888   Standard_Real aD11_21, aD11_22, aD12_21, aD12_22, aCriteria, aCoef;
 889   Standard_Boolean bSmall_11_21, bSmall_11_22, bSmall_12_21, bSmall_12_22;
 890   //
 891   bRet = Standard_True;
 892   aCoef = 1.e+5;
 893   if (((aT12 - aT11) > aCoef*myRes1) && ((aT22 - aT21) > aCoef*myRes2)) {
 894     aCoef = 5000;
 895   } else {
 896     Standard_Real aTRMin = Min((aT12 - aT11)/myRes1, (aT22 - aT21)/myRes2);
 897     aCoef = aTRMin / 100.;
 898     if (aCoef < 1.) {
 899       aCoef = 1.;
 900     }
 901   }
 902   aCriteria = aCoef * myTol;
 903   aCriteria *= aCriteria;
 904   //
 905   myGeom1->D1(aT11, aP11, aV11);
 906   myGeom1->D1(aT12, aP12, aV12);
 907   myGeom2->D1(aT21, aP21, aV21);
 908   myGeom2->D1(aT22, aP22, aV22);
 909   //
 910   aD11_21 = aP11.SquareDistance(aP21);
 911   aD11_22 = aP11.SquareDistance(aP22);
 912   aD12_21 = aP12.SquareDistance(aP21);
 913   aD12_22 = aP12.SquareDistance(aP22);
 914   //
 915   bSmall_11_21 = aD11_21 < aCriteria;
 916   bSmall_11_22 = aD11_22 < aCriteria;
 917   bSmall_12_21 = aD12_21 < aCriteria;
 918   bSmall_12_22 = aD12_22 < aCriteria;
 919   //
 920   if ((bSmall_11_21 && bSmall_12_22) ||
 921       (bSmall_11_22 && bSmall_12_21)) {
 922     if (aCoef == 1.) {
 923       return bRet;
 924     }
 925     //
 926     Standard_Real anAngleCriteria;
 927     Standard_Real anAngle1, anAngle2;
 928     //
 929     anAngleCriteria = 5.e-3;
 930     if (bSmall_11_21 && bSmall_12_22) {
 931       anAngle1 = aV11.Angle(aV21);
 932       anAngle2 = aV12.Angle(aV22);
 933     } else {
 934       anAngle1 = aV11.Angle(aV22);
 935       anAngle2 = aV12.Angle(aV21);
 936     }
 937     //
 938     if (((anAngle1 < anAngleCriteria) || ((M_PI - anAngle1) < anAngleCriteria)) ||
 939         ((anAngle2 < anAngleCriteria) || ((M_PI - anAngle2) < anAngleCriteria))) {
 940       GeomAPI_ProjectPointOnCurve aProj;
 941       Standard_Integer iErr;
 942       Standard_Real aD, aT1p, aT2p;
 943       //
 944       aD = 100.;
 945       aProj.Init(myGeom2, aT21, aT22);
 946       iErr = FindDistPC(aT11, aT12, myGeom1, myTol, myRes1, aProj, aD, aT1p, aT2p, Standard_False);
 947       bRet = (iErr == 2);
 948     }
 949   }
 950   return bRet;
 951 }
 952
 953 //=======================================================================
 954 //function : CheckCoincidence
 955 //purpose  :
 956 //=======================================================================
 957 Standard_Integer IntTools_EdgeEdge::CheckCoincidence(const Standard_Real aT11,
 958                                                      const Standard_Real aT12,
 959                                                      const Standard_Real aT21,
 960                                                      const Standard_Real aT22,
 961                                                      const Standard_Real theCriteria,
 962                                                      const Standard_Real theCurveRes1)
 963 {
 964   Standard_Boolean bSmall;
 965   Standard_Integer iErr, aNb, i;
 966   Standard_Real aT1A, aT1B, aT1max, aT2max, aDmax;
 967   GeomAPI_ProjectPointOnCurve aProjPC;
 968   IntTools_SequenceOfRanges aSeg1;
 969   //
 970   iErr  = 0;
 971   aDmax = -1.;
 972   aProjPC.Init(myGeom2, aT21, aT22);
 973   //
 974   // 1. Express evaluation
 975   aNb = 10; // Number of intervals on the curve #1
 976   bSmall = !SplitRangeOnSegments(aT11, aT12, theCurveRes1, aNb, aSeg1);
 977   aNb = aSeg1.Length();
 978   for (i = 1; i < aNb; ++i) {
 979     const IntTools_Range& aR1 = aSeg1(i);
 980     aR1.Range(aT1A, aT1B);
 981     //
 982     iErr = DistPC(aT1B, myGeom1, theCriteria, aProjPC, aDmax, aT2max);
 983     if (iErr) {
 984       return iErr;
 985     }
 986   }
 987   //
 988   // if the ranges in aSeg1 are less than theCurveRes1,
 989   // there is no need to do step 2 (deep evaluation)
 990   if (bSmall) {
 991     return iErr;
 992   }
 993   //
 994   // 2. Deep evaluation
 995   for (i = 2; i < aNb; ++i) {
 996     const IntTools_Range& aR1 = aSeg1(i);
 997     aR1.Range(aT1A, aT1B);
 998     //
 999     iErr = FindDistPC(aT1A, aT1B, myGeom1, theCriteria, theCurveRes1,
1000                       aProjPC, aDmax, aT1max, aT2max);
1001     if (iErr) {
1002       return iErr;
1003     }
1004   }
1005   // Possible values:
1006   // iErr == 0 - the patches are coincided
1007   // iErr == 1 - a point from aC1 can not be projected on aC2
1008   // iErr == 2 - the distance is too big
1009   return iErr;
1010 }
1011
1012 //=======================================================================
1013 //function : FindDistPC
1014 //purpose  :
1015 //=======================================================================
1016 Standard_Integer FindDistPC(const Standard_Real aT1A,
1017                             const Standard_Real aT1B,
1018                             const Handle(Geom_Curve)& theC1,
1019                             const Standard_Real theCriteria,
1020                             const Standard_Real theEps,
1021                             GeomAPI_ProjectPointOnCurve& theProjPC,
1022                             Standard_Real& aDmax,
1023                             Standard_Real& aT1max,
1024                             Standard_Real& aT2max,
1025                             const Standard_Boolean bMaxDist)
1026 {
1027   Standard_Integer iErr, iC;
1028   Standard_Real aGS, aXP, aA, aB, aXL, aYP, aYL, aT2P, aT2L;
1029   //
1030   iC = bMaxDist ? 1 : -1;
1031   iErr = 0;
1032   //
1033   aGS = 0.6180339887498948482045868343656;// =0.5*(1.+sqrt(5.))-1.;
1034   aA = aT1A;
1035   aB = aT1B;
1036   //
1037   // check bounds
1038   iErr = DistPC(aA, theC1, theCriteria, theProjPC, aYP, aT2P, aDmax, aT1max, aT2max, iC);
1039   if (iErr == 2) {
1040     return iErr;
1041   }
1042   //
1043   iErr = DistPC(aB, theC1, theCriteria, theProjPC, aYL, aT2L, aDmax, aT1max, aT2max, iC);
1044   if (iErr == 2) {
1045     return iErr;
1046   }
1047   //
1048   aXP = aA + (aB - aA)*aGS;
1049   aXL = aB - (aB - aA)*aGS;
1050   //
1051   iErr = DistPC(aXP, theC1, theCriteria, theProjPC, aYP, aT2P, aDmax, aT1max, aT2max, iC);
1052   if (iErr) {
1053     return iErr;
1054   }
1055   //
1056   iErr = DistPC(aXL, theC1, theCriteria, theProjPC, aYL, aT2L, aDmax, aT1max, aT2max, iC);
1057   if (iErr) {
1058     return iErr;
1059   }
1060   //
1061   for (;;) {
1062     if (iC*(aYP - aYL) > 0) {
1063       aA = aXL;
1064       aXL = aXP;
1065       aYL = aYP;
1066       aXP = aA + (aB - aA)*aGS;
1067       iErr = DistPC(aXP, theC1, theCriteria, theProjPC, aYP, aT2P, aDmax, aT1max, aT2max, iC);
1068       if (iErr) {
1069         return iErr;
1070       }
1071     }
1072     else {
1073       aB = aXP;
1074       aXP = aXL;
1075       aYP = aYL;
1076       aXL = aB - (aB - aA)*aGS;
1077       iErr = DistPC(aXL, theC1, theCriteria, theProjPC, aYL, aT2L, aDmax, aT1max, aT2max, iC);
1078       if (iErr) {
1079         return iErr;
1080       }
1081     }
1082     //
1083     if ((aB - aA) < theEps) {
1084       break;
1085     }
1086   }// for (;;) {
1087   //
1088   return iErr;
1089 }
1090 //=======================================================================
1091 //function : DistPC
1092 //purpose  :
1093 //=======================================================================
1094 Standard_Integer DistPC(const Standard_Real aT1,
1095                         const Handle(Geom_Curve)& theC1,
1096                         const Standard_Real theCriteria,
1097                         GeomAPI_ProjectPointOnCurve& theProjPC,
1098                         Standard_Real& aD,
1099                         Standard_Real& aT2,
1100                         Standard_Real& aDmax,
1101                         Standard_Real& aT1max,
1102                         Standard_Real& aT2max,
1103                         const Standard_Integer iC)
1104 {
1105   Standard_Integer iErr;
1106   //
1107   iErr = DistPC(aT1, theC1, theCriteria, theProjPC, aD, aT2, iC);
1108   if (iErr) {
1109     return iErr;
1110   }
1111   //
1112   if (iC*(aD - aDmax) > 0) {
1113     aDmax = aD;
1114     aT1max = aT1;
1115     aT2max = aT2;
1116   }
1117   //
1118   return iErr;
1119 }
1120 //=======================================================================
1121 //function : DistPC
1122 //purpose  :
1123 //=======================================================================
1124 Standard_Integer DistPC(const Standard_Real aT1,
1125                         const Handle(Geom_Curve)& theC1,
1126                         const Standard_Real theCriteria,
1127                         GeomAPI_ProjectPointOnCurve& theProjPC,
1128                         Standard_Real& aD,
1129                         Standard_Real& aT2,
1130                         const Standard_Integer iC)
1131 {
1132   Standard_Integer iErr, aNbP2;
1133   gp_Pnt aP1;
1134   //
1135   iErr = 0;
1136   theC1->D0(aT1, aP1);
1137   //
1138   theProjPC.Perform(aP1);
1139   aNbP2 = theProjPC.NbPoints();
1140   if (!aNbP2) {
1141     iErr = 1;// the point from aC1 can not be projected on aC2
1142     return iErr;
1143   }
1144   //
1145   aD  = theProjPC.LowerDistance();
1146   aT2 = theProjPC.LowerDistanceParameter();
1147   if (iC*(aD - theCriteria) > 0) {
1148     iErr = 2;// the distance is too big or small
1149   }
1150   //
1151   return iErr;
1152 }
1153
1154 //=======================================================================
1155 //function : SplitRangeOnSegments
1156 //purpose  :
1157 //=======================================================================
1158 Standard_Boolean SplitRangeOnSegments(const Standard_Real aT1,
1159                                       const Standard_Real aT2,
1160                                       const Standard_Real theResolution,
1161                                       const Standard_Integer theNbSeg,
1162                                       IntTools_SequenceOfRanges& theSegments)
1163 {
1164   if ((aT2 - aT1) < theResolution) {
1165     theSegments.Append(IntTools_Range(aT1, aT2));
1166     return Standard_False;
1167   }
1168   //
1169   Standard_Real aDt, aT1x, aT2x, aSeg;
1170   Standard_Integer aNbSegments, i;
1171   Standard_Boolean bRet;
1172   //
1173   bRet = Standard_True;
1174   aNbSegments = theNbSeg;
1175   aDt = (aT2 - aT1) / aNbSegments;
1176   if (aDt < theResolution) {
1177     aSeg = (aT2 - aT1) / theResolution;
1178     aNbSegments = Standard_Integer(aSeg) + 1;
1179     bRet = Standard_False;
1180   }
1181   //
1182   aDt /= aNbSegments;
1183   aT1x = aT1;
1184   for (i = 1; i <= aNbSegments; ++i) {
1185     aT2x = aT1x + aDt;
1186     if (i==aNbSegments) {
1187       aT2x = aT2;
1188     }
1189     //
1190     IntTools_Range aR(aT1x, aT2x);
1191     theSegments.Append(aR);
1192     //
1193     aT1x = aT2x;
1194   }
1195   //
1196   return bRet;
1197 }
1198
1199 //=======================================================================
1200 //function : SplitRangeOnTwo
1201 //purpose  :
1202 //=======================================================================
1203 void SplitRangeOnTwo(const Standard_Real aT1,
1204                      const Standard_Real aT2,
1205                      IntTools_SequenceOfRanges& theSegments)
1206 {
1207   Standard_Real aCf, aT;
1208   //
1209   aCf=0.5;
1210   aT = aT1 + (aT2-aT1)*aCf;
1211   //
1212   IntTools_Range aR1(aT1, aT), aR2(aT, aT2);
1213   //
1214   theSegments.Append(aR1);
1215   theSegments.Append(aR2);
1216 }
1217
1218 //=======================================================================
1219 //function : BndCommon
1220 //purpose  :
1221 //=======================================================================
1222 Standard_Boolean BndCommon(const Bnd_Box& theB1,
1223                            const Bnd_Box& theB2,
1224                            Bnd_Box& theBOut)
1225 {
1226   Standard_Boolean bRet;
1227   //
1228   bRet = !theB1.IsOut(theB2);
1229   if (bRet) {
1230     Standard_Real aXmin1, aYmin1, aZmin1, aXmax1, aYmax1, aZmax1,
1231                   aXmin2, aYmin2, aZmin2, aXmax2, aYmax2, aZmax2;
1232     Bnd_Box aBCom;
1233     //
1234     theB1.Get(aXmin1, aYmin1, aZmin1, aXmax1, aYmax1, aZmax1);
1235     theB2.Get(aXmin2, aYmin2, aZmin2, aXmax2, aYmax2, aZmax2);
1236     //
1237     aBCom.Update(Max(aXmin1, aXmin2), Max(aYmin1, aYmin2), Max(aZmin1, aZmin2),
1238                  Min(aXmax1, aXmax2), Min(aYmax1, aYmax2), Min(aZmax1, aZmax2));
1239     //
1240     aBCom.Get(aXmin1, aYmin1, aZmin1, aXmax1, aYmax1, aZmax1);
1241     theBOut = aBCom;
1242   }
1243   return bRet;
1244 }
1245
1246 //=======================================================================
1247 //function : BndBuildBox
1248 //purpose  :
1249 //=======================================================================
1250 void BndBuildBox(const BRepAdaptor_Curve& theBAC,
1251                  const Standard_Real aT1,
1252                  const Standard_Real aT2,
1253                  const Standard_Real theTol,
1254                  Bnd_Box& theBox)
1255 {
1256   Bnd_Box aB;
1257   BndLib_Add3dCurve::Add(theBAC, aT1, aT2, theTol, aB);
1258   theBox = aB;
1259 }
1260
1261 //=======================================================================
1262 //function : TypeToInteger
1263 //purpose  :
1264 //=======================================================================
1265 Standard_Integer TypeToInteger(const GeomAbs_CurveType theCType)
1266 {
1267   Standard_Integer iRet;
1268   //
1269   switch(theCType) {
1270   case GeomAbs_Line:
1271     iRet=0;
1272     break;
1273   case GeomAbs_Circle:
1274     iRet=1;
1275     break;
1276   case GeomAbs_Ellipse:
1277   case GeomAbs_Hyperbola:
1278   case GeomAbs_Parabola:
1279     iRet=2;
1280     break;
1281   case GeomAbs_BezierCurve:
1282   case GeomAbs_BSplineCurve:
1283     iRet=3;
1284     break;
1285   default:
1286     iRet=4;
1287     break;
1288   }
1289   return iRet;
1290 }
1291