src/IntTools/IntTools_BeanBeanIntersector.cxx

   1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   2 //
   3 // This file is part of Open CASCADE Technology software library.
   4 //
   5 // This library is free software; you can redistribute it and / or modify it
   6 // under the terms of the GNU Lesser General Public version 2.1 as published
   7 // by the Free Software Foundation, with special exception defined in the file
   8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
   9 // distribution for complete text of the license and disclaimer of any warranty.
  10 //
  11 // Alternatively, this file may be used under the terms of Open CASCADE
  12 // commercial license or contractual agreement.
  13
  14 #include <IntTools_BeanBeanIntersector.ixx>
  15
  16 #include <IntTools_Root.hxx>
  17 #include <Precision.hxx>
  18 #include <Extrema_POnCurv.hxx>
  19 #include <BRep_Tool.hxx>
  20 #include <Geom_Curve.hxx>
  21 #include <TColStd_Array1OfReal.hxx>
  22 #include <TColStd_Array1OfInteger.hxx>
  23 #include <IntTools_CArray1OfReal.hxx>
  24 #include <gp_Lin.hxx>
  25 #include <Intf_Array1OfLin.hxx>
  26 #include <Bnd_Box.hxx>
  27 #include <Extrema_ExtCC.hxx>
  28 #include <Extrema_ExtElC.hxx>
  29 #include <Extrema_LocateExtPC.hxx>
  30 #include <gp_Circ.hxx>
  31 #include <gp_Elips.hxx>
  32 #include <IntTools.hxx>
  33 #include <ElCLib.hxx>
  34 #include <Geom_Line.hxx>
  35 #include <GeomAdaptor_HCurve.hxx>
  36
  37 static
  38   void LocalPrepareArgs(BRepAdaptor_Curve& theCurve,
  39                         const Standard_Real      theFirstParameter,
  40                         const Standard_Real      theLastParameter,
  41                         Standard_Real&           theDeflection,
  42                         IntTools_CArray1OfReal&  theArgs);
  43
  44 static
  45   Standard_Boolean SetEmptyResultRange(const Standard_Real      theParameter,
  46                                        IntTools_MarkedRangeSet& theMarkedRange);
  47 static
  48   Standard_Integer CheckCoincidence(const Standard_Real aT11,
  49                                     const Standard_Real aT12,
  50                                     const Handle(Geom_Curve)& aC1,
  51                                     const Standard_Real aT21,
  52                                     const Standard_Real aT22,
  53                                     const Handle(Geom_Curve)& aC2,
  54                                     const Standard_Real aCriteria,
  55                                     const Standard_Real aCurveResolution1,
  56                                     GeomAPI_ProjectPointOnCurve& aProjector);
  57
  58
  59 // ==================================================================================
  60 // function: IntTools_BeanBeanIntersector
  61 // purpose:
  62 // ==================================================================================
  63 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector() :
  64
  65 myFirstParameter1(0.),
  66 myLastParameter1(0.),
  67 myFirstParameter2(0.),
  68 myLastParameter2(0.),
  69 myBeanTolerance1(0.),
  70 myBeanTolerance2(0.),
  71 myCurveResolution1(0.),
  72 myCriteria(0.),
  73 myIsDone(Standard_False)
  74 {
  75 }
  76
  77 // ==================================================================================
  78 // function: IntTools_BeanBeanIntersector
  79 // purpose:
  80 // ==================================================================================
  81 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const TopoDS_Edge& theEdge1,
  82                                                            const TopoDS_Edge& theEdge2) :
  83
  84 myFirstParameter1(0.),
  85 myLastParameter1(0.),
  86 myFirstParameter2(0.),
  87 myLastParameter2(0.),
  88 myBeanTolerance1(0.),
  89 myBeanTolerance2(0.),
  90 myCurveResolution1(0.),
  91 myCriteria(0.),
  92 myIsDone(Standard_False)
  93 {
  94   Init(theEdge1, theEdge2);
  95 }
  96
  97 // ==================================================================================
  98 // function: IntTools_BeanBeanIntersector
  99 // purpose:
 100 // ==================================================================================
 101 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const BRepAdaptor_Curve& theCurve1,
 102                                                            const BRepAdaptor_Curve& theCurve2,
 103                                                            const Standard_Real      theBeanTolerance1,
 104                                                            const Standard_Real      theBeanTolerance2) :
 105
 106 myFirstParameter1(0.),
 107 myLastParameter1(0.),
 108 myFirstParameter2(0.),
 109 myLastParameter2(0.),
 110 myBeanTolerance1(0.),
 111 myBeanTolerance2(0.),
 112 myCurveResolution1(0.),
 113 myCriteria(0.),
 114 myIsDone(Standard_False)
 115 {
 116   Init(theCurve1, theCurve2, theBeanTolerance1, theBeanTolerance2);
 117 }
 118
 119 // ==================================================================================
 120 // function: IntTools_BeanBeanIntersector
 121 // purpose:
 122 // ==================================================================================
 123 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const BRepAdaptor_Curve& theCurve1,
 124                                                            const BRepAdaptor_Curve& theCurve2,
 125                                                            const Standard_Real       theFirstParOnCurve1,
 126                                                            const Standard_Real       theLastParOnCurve1,
 127                                                            const Standard_Real       theFirstParOnCurve2,
 128                                                            const Standard_Real       theLastParOnCurve2,
 129                                                            const Standard_Real       theBeanTolerance1,
 130                                                            const Standard_Real       theBeanTolerance2) :
 131
 132 myFirstParameter1(0.),
 133 myLastParameter1(0.),
 134 myFirstParameter2(0.),
 135 myLastParameter2(0.),
 136 myBeanTolerance1(0.),
 137 myBeanTolerance2(0.),
 138 myCurveResolution1(0.),
 139 myCriteria(0.),
 140 myIsDone(Standard_False)
 141 {
 142   Init(theCurve1, theCurve2, theFirstParOnCurve1, theLastParOnCurve1,
 143        theFirstParOnCurve2, theLastParOnCurve2,
 144        theBeanTolerance1, theBeanTolerance2);
 145 }
 146
 147 // ==================================================================================
 148 // function: Init
 149 // purpose:
 150 // ==================================================================================
 151 void IntTools_BeanBeanIntersector::Init(const TopoDS_Edge& theEdge1,
 152                                         const TopoDS_Edge& theEdge2)
 153 {
 154   myCurve1.Initialize(theEdge1);
 155   myCurve2.Initialize(theEdge2);
 156
 157   myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
 158   myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
 159
 160   SetBeanParameters(Standard_True, myCurve1.FirstParameter(), myCurve1.LastParameter());
 161   SetBeanParameters(Standard_False, myCurve2.FirstParameter(), myCurve2.LastParameter());
 162
 163   myBeanTolerance1 = BRep_Tool::Tolerance(theEdge1);
 164   myBeanTolerance2 = BRep_Tool::Tolerance(theEdge2);
 165   myCriteria = myBeanTolerance1 + myBeanTolerance2;
 166   myCurveResolution1 = myCurve1.Resolution(myCriteria);
 167 }
 168
 169 // ==================================================================================
 170 // function: Init
 171 // purpose:
 172 // ==================================================================================
 173 void IntTools_BeanBeanIntersector::Init(const BRepAdaptor_Curve& theCurve1,
 174                                         const BRepAdaptor_Curve& theCurve2,
 175                                         const Standard_Real      theBeanTolerance1,
 176                                         const Standard_Real      theBeanTolerance2)
 177 {
 178   myCurve1 = theCurve1;
 179   myCurve2 = theCurve2;
 180
 181   SetBeanParameters(Standard_True, myCurve1.FirstParameter(), myCurve1.LastParameter());
 182   SetBeanParameters(Standard_False, myCurve2.FirstParameter(), myCurve2.LastParameter());
 183
 184   myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
 185   myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
 186
 187   myBeanTolerance1 = theBeanTolerance1;
 188   myBeanTolerance2 = theBeanTolerance2;
 189   myCriteria = myBeanTolerance1 + myBeanTolerance2;
 190   myCurveResolution1 = myCurve1.Resolution(myCriteria);
 191 }
 192
 193 // ==================================================================================
 194 // function: Init
 195 // purpose:
 196 // ==================================================================================
 197 void IntTools_BeanBeanIntersector::Init(const BRepAdaptor_Curve& theCurve1,
 198                                         const BRepAdaptor_Curve& theCurve2,
 199                                         const Standard_Real      theFirstParOnCurve1,
 200                                         const Standard_Real      theLastParOnCurve1,
 201                                         const Standard_Real      theFirstParOnCurve2,
 202                                         const Standard_Real      theLastParOnCurve2,
 203                                         const Standard_Real      theBeanTolerance1,
 204                                         const Standard_Real      theBeanTolerance2)
 205 {
 206   myCurve1 = theCurve1;
 207   myCurve2 = theCurve2;
 208
 209   myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
 210   myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
 211
 212   SetBeanParameters(Standard_True, theFirstParOnCurve1, theLastParOnCurve1);
 213   SetBeanParameters(Standard_False, theFirstParOnCurve2, theLastParOnCurve2);
 214
 215   myBeanTolerance1 = theBeanTolerance1;
 216   myBeanTolerance2 = theBeanTolerance2;
 217   myCriteria = myBeanTolerance1 + myBeanTolerance2;
 218   myCurveResolution1 = myCurve1.Resolution(myCriteria);
 219 }
 220
 221 // ==================================================================================
 222 // function: SetBeanParameters
 223 // purpose:
 224 // ==================================================================================
 225 void IntTools_BeanBeanIntersector::SetBeanParameters(const Standard_Boolean IsFirstBean,
 226                                                      const Standard_Real    theFirstParOnCurve,
 227                                                      const Standard_Real    theLastParOnCurve)
 228 {
 229   if(IsFirstBean) {
 230     myFirstParameter1 = theFirstParOnCurve;
 231     myLastParameter1  = theLastParOnCurve;
 232   }
 233   else {
 234     myFirstParameter2 = theFirstParOnCurve;
 235     myLastParameter2  = theLastParOnCurve;
 236   }
 237 }
 238 // ==================================================================================
 239 // function: Result
 240 // purpose:
 241 // ==================================================================================
 242 const IntTools_SequenceOfRanges& IntTools_BeanBeanIntersector::Result() const
 243 {
 244   return myResults;
 245 }
 246
 247 // ==================================================================================
 248 // function: Result
 249 // purpose:
 250 // ==================================================================================
 251  void IntTools_BeanBeanIntersector::Result(IntTools_SequenceOfRanges& theResults) const
 252 {
 253   theResults = myResults;
 254 }
 255 // ==================================================================================
 256 // function: Perform
 257 // purpose:
 258 // ==================================================================================
 259 void IntTools_BeanBeanIntersector::Perform()
 260 {
 261   Standard_Boolean bFastComputed;
 262   Standard_Integer k, i, iFlag, aNbRanges, aNbResults;
 263   Standard_Real aMidParameter, aCoeff, aParamDist, aPPC;
 264   Standard_Real aCriteria2, aD2;
 265   gp_Pnt aPi, aPh;
 266   IntTools_CArray1OfReal aParams;
 267   IntTools_Range aRange2, aRange;
 268   //
 269   myIsDone = Standard_False;
 270   myResults.Clear();
 271   //
 272   LocalPrepareArgs(myCurve1, myFirstParameter1, myLastParameter1, myDeflection, aParams);
 273   //
 274   myRangeManager.SetRanges(aParams, 0);
 275   //
 276   aNbRanges=myRangeManager.Length();
 277   if(!aNbRanges) {
 278     return;
 279   }
 280   //
 281   bFastComputed=FastComputeIntersection();
 282   if(bFastComputed) {
 283     aRange.SetFirst(myFirstParameter1);
 284     aRange.SetLast (myLastParameter1);
 285     myResults.Append(aRange);
 286     myIsDone = Standard_True;
 287     return;
 288   }
 289   //
 290   ComputeRoughIntersection();
 291
 292   //Standard_Real aMidParameter = (myFirstParameter2 + myLastParameter2) * 0.5;
 293   aCoeff=0.5753;
 294   aMidParameter = myFirstParameter2+(myLastParameter2-myFirstParameter2)*aCoeff;
 295   //
 296   for(k = 0; k < 2; ++k) {
 297     if(!k) {
 298       aRange2.SetFirst(myFirstParameter2);
 299       aRange2.SetLast(aMidParameter);
 300     }
 301     else {
 302       aRange2.SetFirst(aMidParameter);
 303       aRange2.SetLast(myLastParameter2);
 304     }
 305
 306     ComputeUsingExtrema(aRange2);
 307
 308     ComputeNearRangeBoundaries(aRange2);
 309   }
 310   //
 311   //  Legend iFlag
 312   //
 313   // 0 - just initialized
 314   // 1 - non-intersected
 315   // 2 - roughly intersected
 316   // 3 - intersection is not done
 317   // 4 - coincided range
 318   //
 319   aPPC=Precision::PConfusion();
 320   aCriteria2=myCriteria*myCriteria;
 321   aNbRanges=myRangeManager.Length();
 322   //
 323   for(i=1; i<=aNbRanges; ++i) {
 324     iFlag=myRangeManager.Flag(i);
 325     //
 326     if(iFlag==4) {
 327       aRange=myRangeManager.Range(i);
 328       aNbResults=myResults.Length();
 329       if(aNbResults>0) {
 330         const IntTools_Range& aLastRange = myResults.Last();
 331         //
 332         aParamDist = Abs(aRange.First() - aLastRange.Last());
 333         if(aParamDist > myCurveResolution1) {
 334           myResults.Append(aRange);
 335         }
 336         else {
 337           aPi=myCurve1.Value(aRange.First());
 338           aPh=myCurve1.Value(aLastRange.Last());
 339           aD2=aPi.SquareDistance(aPh);
 340           if(aParamDist<aPPC || aD2<aCriteria2) {
 341             myResults.ChangeValue(aNbResults).SetLast(aRange.Last());
 342           }
 343           else {
 344             myResults.Append(aRange);
 345           }
 346         }
 347       }// if(aNbR>0) {
 348       else {
 349         myResults.Append(aRange);
 350       }
 351     } //if(iFlag==4) {
 352   } // for(i = 1; i <= myRangeManager.Length(); i++) {
 353   myIsDone = Standard_True;
 354 }
 355 // ==================================================================================
 356 // function: FastComputeIntersection
 357 // purpose:
 358 // ==================================================================================
 359 Standard_Boolean IntTools_BeanBeanIntersector::FastComputeIntersection()
 360 {
 361   Standard_Boolean aresult;
 362   GeomAbs_CurveType aCT1, aCT2;
 363   //
 364   aresult = Standard_False;
 365   //
 366   aCT1=myCurve1.GetType();
 367   aCT2=myCurve2.GetType();
 368   //
 369   if(aCT1 != aCT2) {
 370     return aresult;
 371   }
 372   //
 373   // Line
 374   if(aCT1==GeomAbs_Line) {
 375     Standard_Real par1, par2;
 376
 377     if((Distance(myFirstParameter1, par1) < myCriteria) &&
 378        (Distance(myLastParameter1, par2) < myCriteria)) {
 379
 380       if((par1  >= myFirstParameter2) && (par1 <= myLastParameter2) &&
 381          (par2  >= myFirstParameter2) && (par2 <= myLastParameter2)) {
 382         myRangeManager.InsertRange(myFirstParameter1, myLastParameter1, 4);
 383         aresult = Standard_True;
 384       }
 385     }
 386     return aresult;
 387   }
 388   //
 389   // Circle
 390   if(aCT1==GeomAbs_Circle) {
 391     Standard_Real anAngle, aPA, aDistLoc, aDist, aDiff, aR1, aR2;
 392     gp_Circ aCirc1, aCirc2;
 393     gp_Dir aDir1, aDir2;
 394     //
 395     aCirc1=myCurve1.Circle();
 396     aCirc2=myCurve2.Circle();
 397     aR1=aCirc1.Radius();
 398     aR2=aCirc2.Radius();
 399     //
 400     aPA=Precision::Angular();
 401     aDir1 = aCirc1.Axis().Direction();
 402     aDir2 = aCirc2.Axis().Direction();
 403     //
 404     anAngle = aDir1.Angle(aDir2);
 405     if(anAngle > aPA) {
 406       return aresult; //->
 407     }
 408     //
 409     const gp_Pnt& aPLoc1=aCirc1.Location();
 410     const gp_Pnt& aPLoc2=aCirc2.Location();
 411     aDistLoc = aPLoc1.Distance(aPLoc2);
 412     aDist=aDistLoc;
 413     aDiff=aR1 - aR2;
 414     aDist+=Abs(aDiff);
 415     if(Abs(aDist) > myCriteria) {
 416       return aresult; //->
 417     }
 418     //
 419     Standard_Real aSinPA, atmpvalue, aprojectedradius;
 420     //
 421     aSinPA=sin(aPA);
 422     atmpvalue = aR1*aSinPA;
 423     atmpvalue *= atmpvalue;
 424     aprojectedradius = sqrt(aR1*aR1 - atmpvalue);
 425
 426     aDiff = aprojectedradius - aR2;
 427     aDist = aDistLoc + sqrt((aDiff * aDiff) + atmpvalue);
 428     if(Abs(aDist) > myCriteria) {
 429       return aresult; //->
 430     }
 431     //
 432     Standard_Boolean newparfound;
 433     Standard_Integer i;
 434     Standard_Real afirstpar, alastpar, par1, par2, apar;
 435     //
 436     afirstpar = myFirstParameter1;
 437     alastpar  = myLastParameter1;
 438
 439     for(i = 0; i < 2; i++) {
 440       if((Distance(afirstpar, par1) < myCriteria) &&
 441          (Distance(alastpar , par2) < myCriteria)) {
 442
 443         if(i || Distance((myFirstParameter1 + myLastParameter2) * 0.5, apar) < myCriteria) {
 444           myRangeManager.InsertRange(afirstpar, alastpar, 4);
 445
 446           if(!i) {
 447             aresult = Standard_True;
 448           }
 449         }
 450         break;
 451       }
 452       //
 453       if(i) {
 454         break;
 455       }
 456       // i=0 :
 457       newparfound = Standard_False;
 458
 459       if(Distance((myFirstParameter1 + myLastParameter2) * 0.5, apar) < myCriteria) {
 460         afirstpar = myFirstParameter1 + myCriteria;
 461         alastpar  = myLastParameter1  - myCriteria;
 462         newparfound = Standard_True;
 463
 464         if(alastpar <= afirstpar) {
 465           newparfound = Standard_False;
 466         }
 467       }
 468       //
 469       if(!newparfound) {
 470         break;
 471       }
 472     }// for(i = 0; i < 2; i++) {
 473   } // if(aCT1==GeomAbs_Circle)
 474   //modified by NIZNHY-PKV Mon Oct 08 14:08:19 2012f
 475   if (aCT1==GeomAbs_BSplineCurve || aCT1==GeomAbs_BezierCurve) {
 476     Standard_Integer iFlag;
 477     //
 478     iFlag=CheckCoincidence(myFirstParameter1,
 479                            myLastParameter1,
 480                            myTrsfCurve1,
 481                            myFirstParameter2,
 482                            myLastParameter2,
 483                            myTrsfCurve2,
 484                            myCriteria,
 485                            myCurveResolution1,
 486                            myProjector);
 487     if (!iFlag) {
 488       aresult=!aresult;
 489     }
 490   }
 491   //modified by NIZNHY-PKV Mon Oct 08 14:08:23 2012t
 492   return aresult;
 493 }
 494 // ==================================================================================
 495 // function: Distance
 496 // purpose:
 497 // ==================================================================================
 498 Standard_Real IntTools_BeanBeanIntersector::Distance(const Standard_Real theArg,
 499                                                      Standard_Real& theArgOnOtherBean)
 500 {
 501   Standard_Real aDistance;
 502   Standard_Integer aNbPoints;
 503   gp_Pnt aPoint;
 504   //
 505   aDistance=RealLast();
 506   //
 507   aPoint=myCurve1.Value(theArg);
 508   myProjector.Init(myTrsfCurve2, myFirstParameter2, myLastParameter2);
 509   myProjector.Perform(aPoint);
 510   //
 511   aNbPoints=myProjector.NbPoints();
 512   if(aNbPoints > 0) {
 513     theArgOnOtherBean = myProjector.LowerDistanceParameter();
 514     aDistance=myProjector.LowerDistance();
 515   }
 516   //
 517   else {
 518     Standard_Real aDistance1, aDistance2;
 519     //
 520     aDistance1 = aPoint.Distance(myCurve2.Value(myFirstParameter2));
 521     aDistance2 = aPoint.Distance(myCurve2.Value(myLastParameter2));
 522     //
 523     theArgOnOtherBean = myLastParameter2;
 524     aDistance=aDistance2;
 525     if(aDistance1 < aDistance2) {
 526       theArgOnOtherBean = myFirstParameter2;
 527       aDistance=aDistance1;
 528     }
 529   }
 530   return aDistance;
 531 }
 532 // ==================================================================================
 533 // function: ComputeRoughIntersection
 534 // purpose:
 535 // ==================================================================================
 536 void IntTools_BeanBeanIntersector::ComputeRoughIntersection()
 537 {
 538   Standard_Boolean isintersection;
 539   Standard_Integer i, aNbArgs, aNbArgs1, aNbRanges, j, aNbLines, k, pIt, extIt, iFlag;
 540   Standard_Real aDeflection, aGPR, aCurDeflection, aT1, aT2, aD;
 541   Standard_Real aMaxDistance, aDistance, aPPC, aPrm1, aPrm2, aPPA;
 542   GeomAbs_CurveType aCT1, aCT2;
 543   gp_Pnt aPoint1, aPoint2, aMidPOnCurve, aMidPOnLine, aP1, aP2;
 544   IntTools_CArray1OfReal anArgs;
 545   LocalPrepareArgs(myCurve2, myFirstParameter2, myLastParameter2, aDeflection, anArgs);
 546   //
 547   aNbArgs=anArgs.Length();
 548   if(!aNbArgs) {
 549     return;
 550   }
 551   //
 552   aCT1=myCurve1.GetType();
 553   aCT2=myCurve2.GetType();
 554   aGPR=gp::Resolution();
 555   aPPC=Precision::PConfusion();
 556   aPPA=Precision::Angular();
 557   aNbArgs1=aNbArgs-1;
 558   //
 559   Intf_Array1OfLin aLines(1, aNbArgs1);
 560   TColStd_Array1OfInteger aLineFlags(1, aNbArgs1);
 561   TColStd_Array1OfReal aDistances(1, aNbArgs1);
 562   //
 563   aT1=anArgs(0);
 564   aPoint1 = myCurve2.Value(aT1);
 565   for(i=1; i<aNbArgs; ++i) {
 566     aT2=anArgs(i);
 567     aPoint2 = myCurve2.Value(aT2);
 568     gp_Vec aVec(aPoint1, aPoint2);
 569     aD=aVec.Magnitude();
 570     aDistances.SetValue(i, aD);
 571     //
 572     if(aD<=aGPR) {
 573       aLineFlags.SetValue(i, 0);
 574     }
 575     else {
 576       aLineFlags.SetValue(i, 1);
 577       gp_Lin aLine(aPoint1, gp_Dir(aVec));
 578       aLines.SetValue(i, aLine);
 579       //
 580       if((aCT2 == GeomAbs_BezierCurve) ||
 581          (aCT2 == GeomAbs_BSplineCurve)) {
 582         aMidPOnCurve = myCurve2.Value((aT1+aT2) * 0.5);
 583         aMidPOnLine = ElCLib::Value((aDistances(i)*0.5), aLine);
 584         aCurDeflection = aMidPOnCurve.Distance(aMidPOnLine);
 585         if(aCurDeflection > aDeflection) {
 586           aDeflection = aCurDeflection;
 587         }
 588       }
 589     }
 590     aT1=aT2;
 591     aPoint1 = aPoint2;
 592   }
 593   //
 594   aNbLines=aLines.Upper();
 595   aMaxDistance = myCriteria + myDeflection + aDeflection;
 596
 597   aT1=myRangeManager.Range(1).First();
 598   aPoint1 = myCurve1.Value(aT1);
 599   aNbRanges=myRangeManager.Length();
 600   for(i = 1; i <= aNbRanges; ++i) {
 601     const IntTools_Range& aRange = myRangeManager.Range(i);
 602     aT2=aRange.Last();
 603     aPoint2 = myCurve1.Value(aT2);
 604     //
 605     iFlag=myRangeManager.Flag(i);
 606     if(iFlag==4) {// coincided
 607       aT1=aT2;
 608       aPoint1 = aPoint2;
 609       continue;
 610     }
 611     //
 612     myRangeManager.SetFlag(i, 1); // not intersected
 613
 614     Bnd_Box aBox1;
 615     aBox1.Add(aPoint1);
 616     aBox1.Add(aPoint2);
 617     aBox1.Enlarge(myBeanTolerance1 + myDeflection);
 618
 619     gp_Vec aVec(aPoint1, aPoint2);
 620
 621     aDistance=aVec.Magnitude();
 622     if(aDistance <= aGPR) {
 623       myRangeManager.SetFlag(i, 0);
 624       continue;
 625     }
 626     //
 627     gp_Lin aLine(aPoint1, gp_Dir(aVec));
 628     //
 629     if((aCT1 == GeomAbs_BezierCurve) ||
 630        (aCT1 == GeomAbs_BSplineCurve)) {
 631       aMidPOnCurve = myCurve1.Value((aRange.First() + aRange.Last()) * 0.5);
 632       aMidPOnLine = ElCLib::Value((aDistance*0.5), aLine);
 633       aCurDeflection = aMidPOnCurve.Distance(aMidPOnLine);
 634       if(myDeflection < aCurDeflection) {
 635         aMaxDistance += aCurDeflection - myDeflection;
 636         myDeflection = aCurDeflection;
 637       }
 638     }
 639     //
 640     for(j=1; j<=aNbLines; ++j) {
 641       if(!aLineFlags(j)) {
 642         myRangeManager.SetFlag(i, 0);
 643         continue;
 644       }
 645       //
 646       const gp_Lin& aL2=aLines(j);
 647       //Handle(Geom_Line) aC2=new Geom_Line(aL2); // DEB ft
 648       aD=aDistances(j);
 649       aP1=ElCLib::Value(0., aL2);
 650       aP2=ElCLib::Value(aD, aL2);
 651       //
 652       Extrema_ExtElC anExtrema(aLine, aL2, aPPA);
 653       if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
 654         isintersection = Standard_False;
 655
 656         if(anExtrema.IsParallel()) {
 657           isintersection = (anExtrema.SquareDistance(1) < aMaxDistance * aMaxDistance);
 658         }
 659         else { //1
 660           for(k = 1; !isintersection && k <= anExtrema.NbExt(); ++k) {
 661             if(anExtrema.SquareDistance(k) < aMaxDistance * aMaxDistance) {
 662               Extrema_POnCurv P1, P2;
 663               anExtrema.Points(k, P1, P2);
 664               aPrm1=P1.Parameter();
 665               aPrm2=P2.Parameter();
 666               if((aPrm1 >= -aMaxDistance) && (aPrm1 <= aDistance+aMaxDistance) &&
 667                  (aPrm2 >= -aMaxDistance) && (aPrm2 <= aD+aMaxDistance)) {
 668                 isintersection = Standard_True;
 669               }
 670               else { // 2
 671                 Extrema_ExtPElC aPointProjector;
 672
 673                 for(pIt = 0; !isintersection && (pIt < 4); ++pIt) {
 674                   switch (pIt) {
 675                     case 0: {
 676                       aPointProjector =
 677                         //Extrema_ExtPElC(aPoint1, aLines(j), aPPC, 0., aDistances(j));
 678                         Extrema_ExtPElC(aPoint1, aL2, aPPC, -aMaxDistance, aD+aMaxDistance);
 679                       break;
 680                     }
 681                     case 1: {
 682                       aPointProjector =
 683                         //Extrema_ExtPElC(aPoint2, aLines(j), aPPC, 0., aD);
 684                         Extrema_ExtPElC(aPoint2, aL2, aPPC, -aMaxDistance, aD+aMaxDistance);
 685                       break;
 686                     }
 687                     case 2: {
 688                       aPointProjector =
 689                         //Extrema_ExtPElC(ElCLib::Value(0., aLines(j)), aLine, aPPC, 0., aDistance);
 690                         Extrema_ExtPElC(aP1, aLine, aPPC, -aMaxDistance, aDistance+aMaxDistance);
 691                       break;
 692                     }
 693                     case 3: {
 694                       aPointProjector =
 695                         //Extrema_ExtPElC(ElCLib::Value(aDistances(j), aLines(j)), aLine, aPPC, 0., aDistance);
 696                         Extrema_ExtPElC(aP2, aLine, aPPC, -aMaxDistance, aDistance+aMaxDistance);
 697                       break;
 698                     }
 699                     default: {
 700                       break;
 701                     }
 702                   }
 703                   //
 704                   if(aPointProjector.IsDone()) {
 705             Standard_Real aMaxDistance2 = aMaxDistance * aMaxDistance;
 706                     for(extIt = 1; extIt <= aPointProjector.NbExt(); extIt++) {
 707                       if(aPointProjector.SquareDistance(extIt) < aMaxDistance2) {
 708                         isintersection = Standard_True;
 709                       }
 710                     }
 711                   }
 712                 } // end for
 713               }// else { // 2
 714             }//if(anExtrema.Value(k) < aMaxDistance) {
 715           }//for(k = 1; !isintersection && k <= anExtrema.NbExt(); k++) {
 716         }//else { //1
 717
 718         if(isintersection) {
 719           myRangeManager.SetFlag(i, 2); // roughly intersected
 720           break;
 721         }
 722       }//if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
 723       else {
 724         Bnd_Box aBox2;
 725         aBox2.Add(myCurve2.Value(anArgs(j-1)));
 726         aBox2.Add(myCurve2.Value(anArgs(j)));
 727         aBox2.Enlarge(myBeanTolerance2 + aDeflection);
 728         //
 729         if(!aBox1.IsOut(aBox2)) {
 730           myRangeManager.SetFlag(i, 2); // roughly intersected
 731           break;
 732         }
 733       }
 734     }
 735     aT1=aT2;
 736     aPoint1 = aPoint2;
 737   }
 738 }
 739
 740 // ==================================================================================
 741 // function: ComputeUsingExtrema
 742 // purpose:
 743 // ==================================================================================
 744 void IntTools_BeanBeanIntersector::ComputeUsingExtrema(const IntTools_Range& theRange2)
 745 {
 746   //rln Dec 2008.
 747   //Extrema_ExtCC is reused throughout this method to store caches computed on
 748   //theRange2. However it is actually used only in a few calls of
 749   //ComputeUsingExtrema(), so using a default constructor would add unnecessary overhead
 750   //of initialization its internal fields. Since it is not manipulated by Handle then
 751   //we will use a pointer to it and initialize it only when needed.
 752   Extrema_ExtCC *apExtrema = 0;
 753   Handle(GeomAdaptor_HCurve) aHCurve1, aHCurve2; //will be initialized later, only if needed
 754   //handles are used to guard pointers to GeomAdaptor_Curve inside Extrema
 755   Standard_Real aCriteria2 = myCriteria * myCriteria;
 756   for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
 757
 758     if(myRangeManager.Flag(i) == 2 || myRangeManager.Flag(i) == 0) {
 759       const IntTools_Range& aParamRange = myRangeManager.Range(i);
 760
 761       if(aParamRange.Last() - aParamRange.First() < Precision::PConfusion()) {
 762
 763         if(((i > 1) && (myRangeManager.Flag(i-1) == 4)) ||
 764            ((i <  myRangeManager.Length()) && (myRangeManager.Flag(i+1) == 4))) {
 765           myRangeManager.SetFlag(i, 4);
 766           continue;
 767         }
 768       }
 769       if (aHCurve2.IsNull()) {
 770         //initialize only once
 771         apExtrema = new Extrema_ExtCC;
 772         Standard_Real ftmp = theRange2.First() - Precision::PConfusion();
 773         Standard_Real ltmp = theRange2.Last()  + Precision::PConfusion();
 774         ftmp = (ftmp < myFirstParameter2) ? myFirstParameter2 : ftmp;
 775         ltmp = (ltmp > myLastParameter2)  ? myLastParameter2  : ltmp;
 776         aHCurve2 = new GeomAdaptor_HCurve (myTrsfCurve2, ftmp, ltmp);
 777         apExtrema->SetCurve (2, aHCurve2->Curve(), theRange2.First(), theRange2.Last());
 778       }
 779       Extrema_ExtCC& anExtrema = *apExtrema;
 780
 781       Standard_Real ftmp = aParamRange.First() - Precision::PConfusion();
 782       Standard_Real ltmp = aParamRange.Last()  + Precision::PConfusion();
 783       ftmp = (ftmp < myFirstParameter1) ? myFirstParameter1 : ftmp;
 784       ltmp = (ltmp > myLastParameter1)  ? myLastParameter1  : ltmp;
 785       aHCurve1 = new GeomAdaptor_HCurve (myTrsfCurve1, ftmp, ltmp);
 786       anExtrema.SetCurve (1, aHCurve1->Curve(), aParamRange.First(), aParamRange.Last());
 787
 788       anExtrema.Perform();
 789
 790       if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
 791         Standard_Integer anOldNbRanges = myRangeManager.Length();
 792
 793         if (anExtrema.IsParallel()) {
 794           if(anExtrema.SquareDistance(1) < aCriteria2) {
 795             Standard_Real theParameter1, theParameter2;
 796             Standard_Real adistance1 = Distance(aParamRange.First(), theParameter1);
 797             Standard_Real adistance2 = Distance(aParamRange.Last(),  theParameter2);
 798             Standard_Boolean validdistance1 = (adistance1 < myCriteria);
 799             Standard_Boolean validdistance2 = (adistance2 < myCriteria);
 800
 801             if (validdistance1 && validdistance2) {
 802               myRangeManager.InsertRange(aParamRange.First(), aParamRange.Last(), 4);
 803               continue;
 804             }
 805             else {
 806               if(validdistance1) {
 807                 ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), i, theParameter1, theRange2);
 808               }
 809               else {
 810                 if(validdistance2) {
 811                   ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), i, theParameter2, theRange2);
 812                 }
 813                 else {
 814                   Standard_Real a  = aParamRange.First();
 815                   Standard_Real b  = aParamRange.Last();
 816                   Standard_Real da = adistance1;
 817                   Standard_Real db = adistance2;
 818                   Standard_Real asolution = a;
 819                   Standard_Boolean found = Standard_False;
 820
 821                   while(((b - a) > myCurveResolution1) && !found) {
 822                     asolution = (a+b)*0.5;
 823                     Standard_Real adist = Distance(asolution, theParameter1);
 824
 825                     if(adist < myCriteria) {
 826                       found = Standard_True;
 827                     }
 828                     else {
 829                       if(da < db) {
 830                         b = asolution;
 831                         db = adist;
 832                       }
 833                       else {
 834                         a = asolution;
 835                         da = adist;
 836                       }
 837                     }
 838                   } // end while
 839
 840                   if(found) {
 841                     ComputeRangeFromStartPoint(Standard_False, asolution, i, theParameter1, theRange2);
 842                     ComputeRangeFromStartPoint(Standard_True,  asolution, i, theParameter1, theRange2);
 843                   }
 844                   else {
 845                     myRangeManager.SetFlag(i, 2);
 846                   }
 847                 }
 848               }
 849             }
 850           }
 851         }
 852         else {
 853
 854           for(Standard_Integer j = 1 ; j <= anExtrema.NbExt(); j++) {
 855             if(anExtrema.SquareDistance(j) < aCriteria2) {
 856               Extrema_POnCurv p1, p2;
 857               anExtrema.Points(j, p1, p2);
 858
 859               Standard_Integer aNbRanges = myRangeManager.Length();
 860
 861               Standard_Integer anIndex = myRangeManager.GetIndex(p1.Parameter(), Standard_False);
 862               if(anIndex > 0) {
 863                 ComputeRangeFromStartPoint(Standard_False, p1.Parameter(), anIndex, p2.Parameter(), theRange2);
 864               }
 865
 866               anIndex = myRangeManager.GetIndex(p1.Parameter(), Standard_True);
 867
 868               if(anIndex > 0) {
 869                 ComputeRangeFromStartPoint(Standard_True, p1.Parameter(), anIndex, p2.Parameter(), theRange2);
 870               }
 871
 872               if(aNbRanges == myRangeManager.Length()) {
 873                 SetEmptyResultRange(p1.Parameter(), myRangeManager);
 874               }
 875             }
 876           } // end for
 877         }
 878         Standard_Integer adifference = myRangeManager.Length() - anOldNbRanges;
 879
 880         if(adifference > 0) {
 881           i+=adifference;
 882         }
 883       }
 884       else {
 885         myRangeManager.SetFlag(i, 3); // intersection not done.
 886       }
 887     }
 888   }
 889   if (apExtrema) delete apExtrema;
 890 }
 891
 892 // ==================================================================================
 893 // function: ComputeNearRangeBoundaries
 894 // purpose:
 895 // ==================================================================================
 896 void IntTools_BeanBeanIntersector::ComputeNearRangeBoundaries(const IntTools_Range& theRange2)
 897 {
 898   Standard_Real theParameter = theRange2.First();
 899
 900   for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
 901     if(myRangeManager.Flag(i) != 3)
 902       continue;
 903
 904     if((i > 1) && ((myRangeManager.Flag(i-1) == 1) || (myRangeManager.Flag(i-1) == 4))) {
 905       myRangeManager.SetFlag(i, 2);
 906       continue;
 907     }
 908
 909     const IntTools_Range& aParamRange = myRangeManager.Range(i);
 910
 911     if(Distance(aParamRange.First(), theParameter) < myCriteria) {
 912       Standard_Integer aNbRanges = myRangeManager.Length();
 913
 914       if(i > 1) {
 915         ComputeRangeFromStartPoint(Standard_False, aParamRange.First(), i-1, theParameter, theRange2);
 916       }
 917       ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), i + (myRangeManager.Length() - aNbRanges), theParameter, theRange2);
 918
 919       if(aNbRanges == myRangeManager.Length()) {
 920         SetEmptyResultRange(aParamRange.First(), myRangeManager);
 921       }
 922     }
 923     else {
 924       myRangeManager.SetFlag(i, 2);
 925     }
 926   }
 927
 928   if((myRangeManager.Flag(myRangeManager.Length()) == 3) ||
 929      (myRangeManager.Flag(myRangeManager.Length()) == 2)) {
 930     const IntTools_Range& aParamRange = myRangeManager.Range(myRangeManager.Length());
 931
 932     if(Distance(aParamRange.Last(), theParameter) < myCriteria) {
 933       Standard_Integer aNbRanges = myRangeManager.Length();
 934       myRangeManager.SetFlag(myRangeManager.Length(), 2);
 935
 936       ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), myRangeManager.Length(), theParameter, theRange2);
 937
 938       if(aNbRanges == myRangeManager.Length()) {
 939         SetEmptyResultRange(aParamRange.Last(), myRangeManager);
 940       }
 941     }
 942     else {
 943       myRangeManager.SetFlag(myRangeManager.Length(), 2);
 944     }
 945   }
 946 }
 947
 948 // ==================================================================================
 949 // function: ComputeRangeFromStartPoint
 950 // purpose:
 951 // ==================================================================================
 952 void IntTools_BeanBeanIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
 953                                                               const Standard_Real    theParameter,
 954                                                               const Standard_Integer theIndex,
 955                                                               const Standard_Real    theParameter2,
 956                                                               const IntTools_Range&  theRange2)
 957 {
 958
 959   if(myRangeManager.Flag(theIndex) == 4 ||
 960      myRangeManager.Flag(theIndex) == 1)
 961     return;
 962
 963   Standard_Integer aValidIndex = theIndex;
 964   Standard_Real aMinDelta        = myCurveResolution1 * 0.5;
 965   Standard_Real aDeltaRestrictor = myLastParameter1 - myFirstParameter1;
 966
 967   if(Abs(aDeltaRestrictor) < Precision::PConfusion()) {
 968     return;
 969   }
 970
 971   if(aMinDelta > aDeltaRestrictor) {
 972     aMinDelta = aDeltaRestrictor;
 973   }
 974   Standard_Real tenOfMinDelta    = aMinDelta * 10.;
 975   Standard_Real aDelta           = myCurveResolution1;
 976   Standard_Real aCurPar  = (ToIncreaseParameter) ? (theParameter + aDelta) : (theParameter - aDelta);
 977   Standard_Real aPrevPar = theParameter;
 978   IntTools_Range aCurrentRange = myRangeManager.Range(aValidIndex);
 979
 980   Standard_Boolean BoundaryCondition  = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
 981
 982   if(BoundaryCondition) {
 983     aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
 984     BoundaryCondition = Standard_False;
 985   }
 986
 987   Standard_Integer loopcounter = 0; // neccesary to have no infinite loop
 988   Standard_Real aParameter = theParameter2;
 989   Standard_Boolean anotherSolutionFound = Standard_False;
 990
 991   Standard_Boolean isboundaryindex = Standard_False;
 992   Standard_Boolean isvalidindex = Standard_True;
 993
 994   Standard_Real aCriteria2 = myCriteria * myCriteria;
 995
 996   while((aDelta >= aMinDelta) && (loopcounter <= 10)) {
 997     Standard_Boolean pointfound = Standard_False;
 998
 999     gp_Pnt aPoint = myCurve1.Value(aCurPar);
1000     GeomAdaptor_Curve aCurve2(myTrsfCurve2, theRange2.First(), theRange2.Last());
1001
1002     Extrema_LocateExtPC anExtrema(aPoint, aCurve2, aParameter, theRange2.First(), theRange2.Last(), 1.e-10);
1003
1004     if(anExtrema.IsDone()) {
1005       if(anExtrema.SquareDistance() < aCriteria2) {
1006         Extrema_POnCurv aPOnCurv = anExtrema.Point();
1007         aParameter = aPOnCurv.Parameter();
1008         pointfound = Standard_True;
1009       }
1010     }
1011     else {
1012       //       pointfound = (Distance(aCurPar, aParameter) < myCriteria);
1013       Standard_Real afoundparam = aParameter;
1014
1015       if(Distance(aCurPar, afoundparam) < myCriteria) {
1016         aParameter = afoundparam;
1017         pointfound = Standard_True;
1018       }
1019     }
1020
1021     if(pointfound) {
1022       aPrevPar = aCurPar;
1023       anotherSolutionFound = Standard_True;
1024
1025       if(BoundaryCondition && (isboundaryindex || !isvalidindex))
1026         break;
1027     }
1028     else {
1029       aDeltaRestrictor = aDelta;
1030     }
1031
1032     // if pointfound decide to increase aDelta using derivative of distance function
1033     //
1034
1035     aDelta = (pointfound) ? (aDelta * 2.) : (aDelta * 0.5);
1036     aDelta = (aDelta < aDeltaRestrictor) ? aDelta : aDeltaRestrictor;
1037     aCurPar = (ToIncreaseParameter) ? (aPrevPar + aDelta) : (aPrevPar - aDelta);
1038
1039     BoundaryCondition  = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1040
1041     isboundaryindex = Standard_False;
1042     isvalidindex = Standard_True;
1043
1044     if(BoundaryCondition) {
1045       isboundaryindex = ((!ToIncreaseParameter && (aValidIndex == 1)) ||
1046                          (ToIncreaseParameter && (aValidIndex == myRangeManager.Length())));
1047
1048       if(!isboundaryindex) {
1049         if(pointfound) {
1050           Standard_Integer aFlag = (ToIncreaseParameter) ? myRangeManager.Flag(aValidIndex + 1) : myRangeManager.Flag(aValidIndex - 1);
1051
1052           if(aFlag != 1 && aFlag != 4) {
1053             aValidIndex = (ToIncreaseParameter) ? (aValidIndex + 1) : (aValidIndex - 1);
1054             aCurrentRange = myRangeManager.Range(aValidIndex);
1055
1056             if((ToIncreaseParameter && (aCurPar > aCurrentRange.Last())) ||
1057                (!ToIncreaseParameter && (aCurPar < aCurrentRange.First()))) {
1058               aCurPar = (aCurrentRange.First() + aCurrentRange.Last()) * 0.5;
1059               aDelta*=0.5;
1060             }
1061           }
1062           else {
1063             isvalidindex = Standard_False;
1064             aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1065           }
1066         }
1067       }
1068       else {
1069         aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1070       }
1071
1072       if(aDelta < tenOfMinDelta) {
1073         loopcounter++;
1074       }
1075       else {
1076         loopcounter = 0;
1077       }
1078     } // end if(BoundaryCondition)
1079   }
1080
1081   if(anotherSolutionFound) {
1082     if(ToIncreaseParameter)
1083       myRangeManager.InsertRange(theParameter, aPrevPar, 4);
1084     else
1085       myRangeManager.InsertRange(aPrevPar, theParameter, 4);
1086   }
1087 }
1088
1089 // ---------------------------------------------------------------------------------
1090 // static function: LocalPrepareArgs
1091 // purpose:
1092 // ---------------------------------------------------------------------------------
1093 static void LocalPrepareArgs(BRepAdaptor_Curve& theCurve,
1094                              const Standard_Real      theFirstParameter,
1095                              const Standard_Real      theLastParameter,
1096                              Standard_Real&           theDeflection,
1097                              IntTools_CArray1OfReal&  theArgs) {
1098   Standard_Integer aDiscretization = 30;
1099   Standard_Real aRelativeDeflection = 0.01;
1100   theDeflection = aRelativeDeflection;
1101   Standard_Boolean prepareargs = Standard_True;
1102
1103   switch(theCurve.GetType()) {
1104   case GeomAbs_Line: {
1105     prepareargs = Standard_False;
1106     aDiscretization = 3;
1107     theArgs.Append(theFirstParameter);
1108
1109     if((theLastParameter - theFirstParameter) > Precision::PConfusion()) {
1110       theArgs.Append((theFirstParameter + theLastParameter)*0.5);
1111     }
1112     theArgs.Append(theLastParameter);
1113     theDeflection = Precision::Confusion();
1114     break;
1115   }
1116   case GeomAbs_Circle: {
1117     aDiscretization = 23;
1118     theDeflection = aRelativeDeflection * theCurve.Circle().Radius();
1119     break;
1120   }
1121   case GeomAbs_Ellipse: {
1122     aDiscretization = 40;
1123     theDeflection = 2 * aRelativeDeflection * theCurve.Ellipse().MajorRadius();
1124     break;
1125   }
1126   case GeomAbs_Hyperbola:
1127   case GeomAbs_Parabola: {
1128     aDiscretization = 40;
1129     theDeflection = aRelativeDeflection;
1130     break;
1131   }
1132   case GeomAbs_BezierCurve: {
1133     aDiscretization = 30;
1134     theDeflection = aRelativeDeflection;
1135     break;
1136   }
1137   case GeomAbs_BSplineCurve: {
1138     aDiscretization = 30;
1139     theDeflection = aRelativeDeflection;
1140     break;
1141   }
1142   default: {
1143     aDiscretization = 30;
1144     theDeflection = aRelativeDeflection;
1145   }
1146   }
1147
1148   if(prepareargs) {
1149     IntTools::PrepareArgs(theCurve, theLastParameter, theFirstParameter, aDiscretization, aRelativeDeflection, theArgs);
1150   }
1151 }
1152 // ---------------------------------------------------------------------------------
1153 // static function: SetEmptyResultRange
1154 // purpose:
1155 // ---------------------------------------------------------------------------------
1156 static Standard_Boolean SetEmptyResultRange(const Standard_Real      theParameter,
1157                                             IntTools_MarkedRangeSet& theMarkedRange) {
1158
1159   const TColStd_SequenceOfInteger& anIndices = theMarkedRange.GetIndices(theParameter);
1160   Standard_Boolean add = (anIndices.Length() > 0);
1161
1162   for(Standard_Integer k = 1; k <= anIndices.Length(); k++) {
1163     if(theMarkedRange.Flag(anIndices(k)) == 4) {
1164       add = Standard_False;
1165       break;
1166     }
1167   }
1168
1169   if(add) {
1170     theMarkedRange.InsertRange(theParameter, theParameter, 4);
1171   }
1172
1173   return add;
1174 }
1175 //modified by NIZNHY-PKV Fri Oct 12 09:34:10 2012f
1176 static
1177  Standard_Integer DistPC(const Standard_Real aT1,
1178                         const Handle(Geom_Curve)& aC1,
1179                         const Standard_Real aCriteria,
1180                         GeomAPI_ProjectPointOnCurve& aProjector,
1181                         Standard_Real& aD,
1182                         Standard_Real& aT2);
1183
1184
1185 static
1186  Standard_Integer DistPC(const Standard_Real aT1,
1187                         const Handle(Geom_Curve)& aC1,
1188                         const Standard_Real aCriteria,
1189                         GeomAPI_ProjectPointOnCurve& aProjector,
1190                         Standard_Real& aD,
1191                         Standard_Real& aT2,
1192                         Standard_Real& aDmax,
1193                         Standard_Real& aTmax);
1194
1195 static
1196   Standard_Integer FindMaxDistPC(const Standard_Real aT1A,
1197                                  const Standard_Real aT1B,
1198                                  const Handle(Geom_Curve)& aC1,
1199                                  const Standard_Real aCriteria,
1200                                  const Standard_Real aEps1,
1201                                  GeomAPI_ProjectPointOnCurve& aProjector,
1202                                  Standard_Real& aDmax,
1203                                  Standard_Real& aT1max);
1204
1205 //=======================================================================
1206 //function : CheckCoincidence
1207 //purpose  :
1208 //=======================================================================
1209 Standard_Integer CheckCoincidence(const Standard_Real aT11,
1210                                   const Standard_Real aT12,
1211                                   const Handle(Geom_Curve)& aC1,
1212                                   const Standard_Real aT21,
1213                                   const Standard_Real aT22,
1214                                   const Handle(Geom_Curve)& aC2,
1215                                   const Standard_Real aCriteria,
1216                                   const Standard_Real aEps1,
1217                                   GeomAPI_ProjectPointOnCurve& aProjector)
1218 {
1219   Standard_Integer iErr, aNb1, i, aNbX;
1220   Standard_Real dT1, aT1, aT2, aD, aDmax, aTmax;
1221   Standard_Real aT1A, aT1B, aD1max,aT1max;
1222   //
1223   iErr=0; // the patches are coincided
1224   //
1225   //
1226   aProjector.Init(aC2, aT21, aT22);
1227   //
1228   aDmax=-1.;
1229   //
1230   // 1. Express evaluation
1231   //
1232   aNb1=10; // Number of intervals on the curve #1
1233   dT1=(aT12-aT11)/aNb1;
1234   for (i=1; i<aNb1; ++i) {
1235     aT1=aT11+i*dT1;
1236     //
1237     iErr=DistPC(aT1, aC1, aCriteria, aProjector, aD, aT2, aDmax, aTmax);
1238     if (iErr) {
1239       iErr=1;// a point from aC1 can not be projected on aC2
1240       return iErr;
1241     }
1242     //
1243     if (aDmax>aCriteria) {
1244       iErr=2; // the distance is too big
1245       return iErr;
1246     }
1247   }
1248   //
1249   // 2. Deep evaluation
1250   aD1max=aDmax;
1251   //
1252   aNbX=aNb1-1;
1253   for (i=1; i<aNbX; ++i) {
1254     aT1A=aT11+i*dT1;
1255     aT1B=aT1A+dT1;
1256     //
1257     iErr=FindMaxDistPC(aT1A, aT1B, aC1, aCriteria, aEps1, aProjector, aD1max, aT1max);
1258     if (iErr) {
1259       iErr=1;
1260       return iErr;
1261     }
1262   }
1263   //
1264   return iErr;
1265 }
1266 //
1267 //=======================================================================
1268 //function : FindMaxDistPC
1269 //purpose  :
1270 //=======================================================================
1271 Standard_Integer FindMaxDistPC(const Standard_Real aT1A,
1272                                const Standard_Real aT1B,
1273                                const Handle(Geom_Curve)& aC1,
1274                                const Standard_Real aCriteria,
1275                                const Standard_Real aEps1,
1276                                GeomAPI_ProjectPointOnCurve& aProjector,
1277                                Standard_Real& aDmax,
1278                                Standard_Real& aT1max)
1279 {
1280   Standard_Integer iErr;
1281   Standard_Real aGS, aXP, aA, aB, aXL, aYP, aYL, aT2P, aT2L;
1282   //
1283   iErr=0;
1284   aDmax=0.;
1285   //
1286   aGS=0.6180339887498948482045868343656;// =0.5*(1.+sqrt(5.))-1.;
1287   aA=aT1A;
1288   aB=aT1B;
1289   //
1290   aXP=aA+(aB-aA)*aGS;
1291   aXL=aB-(aB-aA)*aGS;
1292   //
1293   iErr=DistPC(aXP, aC1, aCriteria, aProjector, aYP, aT2P, aDmax, aT1max);
1294   if(iErr){
1295     return iErr;
1296   }
1297   //
1298   iErr=DistPC(aXL, aC1, aCriteria, aProjector, aYL, aT2L, aDmax, aT1max);
1299   if(iErr){
1300     return iErr;
1301   }
1302   //
1303   for(;;) {
1304     if (aYP>aYL) {
1305       aA=aXL;
1306       aXL=aXP;
1307       aYL=aYP;
1308       aXP=aA+(aB-aA)*aGS;
1309       iErr=DistPC(aXP, aC1, aCriteria, aProjector, aYP, aT2P, aDmax, aT1max);
1310       if(iErr){
1311         return iErr;
1312       }
1313     }
1314     else {
1315       aB=aXP;
1316       aXP=aXL;
1317       aYP=aYL;
1318       aXL=aB-(aB-aA)*aGS;
1319       iErr=DistPC(aXL, aC1, aCriteria, aProjector, aYL, aT2L, aDmax, aT1max);
1320       if(iErr){
1321         return iErr;
1322       }
1323     }
1324     //
1325     if ((aB-aA)<aEps1) {
1326       break;
1327     }
1328   }// while(1) {
1329   //
1330   return iErr;
1331 }
1332 //=======================================================================
1333 //function : DistPC
1334 //purpose  :
1335 //=======================================================================
1336 Standard_Integer DistPC(const Standard_Real aT1,
1337                         const Handle(Geom_Curve)& aC1,
1338                         const Standard_Real aCriteria,
1339                         GeomAPI_ProjectPointOnCurve& aProjector,
1340                         Standard_Real& aD,
1341                         Standard_Real& aT2,
1342                         Standard_Real& aDmax,
1343                         Standard_Real& aTmax)
1344 {
1345   Standard_Integer iErr;
1346   //
1347   iErr=DistPC(aT1, aC1, aCriteria, aProjector, aD, aT2);
1348   if (iErr) {
1349     return iErr;
1350   }
1351   //
1352   if (aD>aDmax) {
1353     aDmax=aD;
1354     aTmax=aT2;
1355   }
1356   //
1357   return iErr;
1358 }
1359 //=======================================================================
1360 //function : DistPC
1361 //purpose  :
1362 //=======================================================================
1363 Standard_Integer DistPC(const Standard_Real aT1,
1364                         const Handle(Geom_Curve)& aC1,
1365                         const Standard_Real aCriteria,
1366                         GeomAPI_ProjectPointOnCurve& aProjector,
1367                         Standard_Real& aD,
1368                         Standard_Real& aT2)
1369 {
1370   Standard_Integer iErr, aNbP2;
1371   gp_Pnt aP1;
1372   //
1373   iErr=0;
1374   aC1->D0(aT1, aP1);
1375   //
1376   aProjector.Perform(aP1);
1377   aNbP2=aProjector.NbPoints();
1378   if (!aNbP2) {
1379     iErr=1;// the point from aC1 can not be projected on aC2
1380     return iErr;
1381   }
1382   //
1383   aD=aProjector.LowerDistance();
1384   aT2=aProjector.LowerDistanceParameter();
1385   if (aD>aCriteria) {
1386     iErr=2;// the distance is too big
1387   }
1388   //
1389   return iErr;
1390 }
1391 //modified by NIZNHY-PKV Fri Oct 12 09:34:12 2012t