src/IntTools/IntTools_BeanFaceIntersector.cxx

   1 // Copyright (c) 1999-2012 OPEN CASCADE SAS
   2 //
   3 // The content of this file is subject to the Open CASCADE Technology Public
   4 // License Version 6.5 (the "License"). You may not use the content of this file
   5 // except in compliance with the License. Please obtain a copy of the License
   6 // at http://www.opencascade.org and read it completely before using this file.
   7 //
   8 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
   9 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  10 //
  11 // The Original Code and all software distributed under the License is
  12 // distributed on an "AS IS" basis, without warranty of any kind, and the
  13 // Initial Developer hereby disclaims all such warranties, including without
  14 // limitation, any warranties of merchantability, fitness for a particular
  15 // purpose or non-infringement. Please see the License for the specific terms
  16 // and conditions governing the rights and limitations under the License.
  17
  18
  19 #include <IntTools_BeanFaceIntersector.ixx>
  20
  21 #include <IntTools_Root.hxx>
  22 #include <Precision.hxx>
  23 #include <Extrema_POnCurv.hxx>
  24 #include <Extrema_POnSurf.hxx>
  25 #include <BRep_Tool.hxx>
  26 #include <Geom_Surface.hxx>
  27 #include <TColStd_Array1OfReal.hxx>
  28 #include <TColStd_Array1OfBoolean.hxx>
  29 #include <TColStd_ListOfInteger.hxx>
  30 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  31 #include <IntTools_EdgeFace.hxx>
  32 #include <IntTools_ListOfCurveRangeSample.hxx>
  33 #include <IntTools_ListOfSurfaceRangeSample.hxx>
  34 #include <IntTools_ListOfBox.hxx>
  35 #include <IntTools_ListIteratorOfListOfBox.hxx>
  36 #include <IntTools_ListIteratorOfListOfCurveRangeSample.hxx>
  37 #include <IntTools_ListIteratorOfListOfSurfaceRangeSample.hxx>
  38 #include <IntTools_MapIteratorOfMapOfCurveSample.hxx>
  39 #include <TColgp_Array1OfPnt2d.hxx>
  40
  41 #include <Geom_Curve.hxx>
  42 #include <Geom_Surface.hxx>
  43 #include <Geom_BSplineSurface.hxx>
  44 #include <GeomAdaptor_Curve.hxx>
  45 #include <GeomAdaptor_Surface.hxx>
  46 #include <Extrema_ExtCS.hxx>
  47 #include <Extrema_ExtPS.hxx>
  48 #include <IntTools.hxx>
  49 #include <BOPInt_Context.hxx>
  50 #include <IntTools_Tools.hxx>
  51 #include <GeomAPI_ProjectPointOnCurve.hxx>
  52 #include <IntCurveSurface_HInter.hxx>
  53 #include <IntCurveSurface_IntersectionPoint.hxx>
  54 #include <IntCurveSurface_IntersectionSegment.hxx>
  55 #include <IntAna_QuadQuadGeo.hxx>
  56 #include <BRepAdaptor_HCurve.hxx>
  57 #include <BRepAdaptor_HSurface.hxx>
  58 #include <Extrema_GenLocateExtPS.hxx>
  59 #include <Extrema_GenExtCS.hxx>
  60 #include <Bnd_Box.hxx>
  61 #include <BndLib_AddSurface.hxx>
  62 #include <BndLib_Add3dCurve.hxx>
  63 #include <ElCLib.hxx>
  64 #include <ElSLib.hxx>
  65
  66 static Standard_Boolean AdjustPeriodic(const Standard_Real U,
  67                                        const Standard_Real UFirst,
  68                                        const Standard_Real ULast,
  69                                        const Standard_Real Period,
  70                                        Standard_Real&      UResult);
  71
  72 static Standard_Boolean SetEmptyResultRange(const Standard_Real      theParameter,
  73                                             IntTools_MarkedRangeSet& theMarkedRange);
  74
  75 // static Standard_Boolean TestCoinside(const BRepAdaptor_Curve&   theCurve,
  76 //                                      const BRepAdaptor_Surface& theSurface);
  77
  78 //  Modified by skv - Wed Nov  2 15:21:11 2005 Optimization Begin
  79 static Bnd_Box GetSurfaceBox
  80                (const Handle(Geom_BSplineSurface)        &theSurf,
  81                 const Standard_Real                       theFirstU,
  82                 const Standard_Real                       theLastU,
  83                 const Standard_Real                       theFirstV,
  84                 const Standard_Real                       theLastV,
  85                 const Standard_Real                       theTolerance,
  86                       IntTools_SurfaceRangeLocalizeData  &theSurfaceData);
  87
  88 static void ComputeGridPoints
  89                (const Handle(Geom_BSplineSurface)       &theSurf,
  90                 const Standard_Real                      theFirstU,
  91                 const Standard_Real                      theLastU,
  92                 const Standard_Real                      theFirstV,
  93                 const Standard_Real                      theLastV,
  94                 const Standard_Real                      theTolerance,
  95                       IntTools_SurfaceRangeLocalizeData &theSurfaceData);
  96
  97 static void BuildBox(const Handle(Geom_BSplineSurface)       &theSurf,
  98                      const Standard_Real                      theFirstU,
  99                      const Standard_Real                      theLastU,
 100                      const Standard_Real                      theFirstV,
 101                      const Standard_Real                      theLastV,
 102                            IntTools_SurfaceRangeLocalizeData &theSurfaceData,
 103                            Bnd_Box                           &theBox);
 104 //  Modified by skv - Wed Nov  2 15:21:11 2005 Optimization End
 105
 106 static void MergeSolutions(const IntTools_ListOfCurveRangeSample& theListCurveRange,
 107                            const IntTools_ListOfSurfaceRangeSample& theListSurfaceRange,
 108                            IntTools_ListOfCurveRangeSample& theListCurveRangeSort,
 109                            IntTools_ListOfSurfaceRangeSample& theListSurfaceRangeSort);
 110
 111 static void CheckSampling(const IntTools_CurveRangeSample& theCurveRange,
 112                           const IntTools_SurfaceRangeSample& theSurfaceRange,
 113                           const IntTools_CurveRangeLocalizeData& theCurveData,
 114                           const IntTools_SurfaceRangeLocalizeData& theSurfaceData,
 115                           const Standard_Real DiffC,
 116                           const Standard_Real DiffU,
 117                           const Standard_Real DiffV,
 118                           Standard_Boolean& bAllowSamplingC,
 119                           Standard_Boolean& bAllowSamplingU,
 120                           Standard_Boolean& bAllowSamplingV);
 121 // ==================================================================================
 122 // function: IntTools_BeanFaceIntersector
 123 // purpose:
 124 // ==================================================================================
 125 IntTools_BeanFaceIntersector::IntTools_BeanFaceIntersector() :
 126 myFirstParameter(0.),
 127 myLastParameter(0.),
 128 myUMinParameter(0.),
 129 myUMaxParameter(0.),
 130 myVMinParameter(0.),
 131 myVMaxParameter(0.),
 132 myBeanTolerance(0.),
 133 myFaceTolerance(0.),
 134 myDeflection(0.01),
 135 myIsDone(Standard_False)
 136 {
 137   myCriteria        = Precision::Confusion();
 138   myCurveResolution = Precision::PConfusion();
 139
 140 }
 141
 142 // ==================================================================================
 143 // function: IntTools_BeanFaceIntersector
 144 // purpose:
 145 // ==================================================================================
 146 IntTools_BeanFaceIntersector::IntTools_BeanFaceIntersector(const TopoDS_Edge& theEdge,
 147                                                            const TopoDS_Face& theFace) :
 148 myFirstParameter(0.),
 149 myLastParameter(0.),
 150 myUMinParameter(0.),
 151 myUMaxParameter(0.),
 152 myVMinParameter(0.),
 153 myVMaxParameter(0.),
 154 myBeanTolerance(0.),
 155 myFaceTolerance(0.),
 156 myDeflection(0.01),
 157 myIsDone(Standard_False)
 158 {
 159   Init(theEdge, theFace);
 160 }
 161
 162 // ==================================================================================
 163 // function: IntTools_BeanFaceIntersector
 164 // purpose:
 165 // ==================================================================================
 166 IntTools_BeanFaceIntersector::IntTools_BeanFaceIntersector(const BRepAdaptor_Curve&   theCurve,
 167                                                            const BRepAdaptor_Surface& theSurface,
 168                                                            const Standard_Real        theBeanTolerance,
 169                                                            const Standard_Real        theFaceTolerance) :
 170 myFirstParameter(0.),
 171 myLastParameter(0.),
 172 myUMinParameter(0.),
 173 myUMaxParameter(0.),
 174 myVMinParameter(0.),
 175 myVMaxParameter(0.),
 176 myDeflection(0.01),
 177 myIsDone(Standard_False)
 178 {
 179   Init(theCurve, theSurface, theBeanTolerance, theFaceTolerance);
 180 }
 181
 182 // ==================================================================================
 183 // function: IntTools_BeanFaceIntersector
 184 // purpose:
 185 // ==================================================================================
 186 IntTools_BeanFaceIntersector::IntTools_BeanFaceIntersector(const BRepAdaptor_Curve&   theCurve,
 187                                                            const BRepAdaptor_Surface& theSurface,
 188                                                            const Standard_Real        theFirstParOnCurve,
 189                                                            const Standard_Real        theLastParOnCurve,
 190                                                            const Standard_Real        theUMinParameter,
 191                                                            const Standard_Real        theUMaxParameter,
 192                                                            const Standard_Real        theVMinParameter,
 193                                                            const Standard_Real        theVMaxParameter,
 194                                                            const Standard_Real        theBeanTolerance,
 195                                                            const Standard_Real        theFaceTolerance) :
 196 myFirstParameter(theFirstParOnCurve),
 197 myLastParameter(theLastParOnCurve),
 198 myUMinParameter(theUMinParameter),
 199 myUMaxParameter(theUMaxParameter),
 200 myVMinParameter(theVMinParameter),
 201 myVMaxParameter(theVMaxParameter),
 202 myBeanTolerance(theBeanTolerance),
 203 myFaceTolerance(theFaceTolerance),
 204 myDeflection(0.01),
 205 myIsDone(Standard_False)
 206 {
 207   myCurve = theCurve;
 208
 209   myCriteria = myBeanTolerance + myFaceTolerance;
 210   myCurveResolution = myCurve.Resolution(myCriteria);
 211
 212   mySurface = theSurface;
 213   myTrsfSurface = Handle(Geom_Surface)::DownCast(mySurface.Surface().Surface()->Transformed(mySurface.Trsf()));
 214 }
 215
 216 // ==================================================================================
 217 // function: Init
 218 // purpose:
 219 // ==================================================================================
 220 void IntTools_BeanFaceIntersector::Init(const TopoDS_Edge& theEdge,
 221                                         const TopoDS_Face& theFace)
 222 {
 223   myCurve.Initialize(theEdge);
 224   mySurface.Initialize(theFace);
 225   myTrsfSurface = Handle(Geom_Surface)::DownCast(mySurface.Surface().Surface()->Transformed(mySurface.Trsf()));
 226   myBeanTolerance = BRep_Tool::Tolerance(theEdge);
 227   myFaceTolerance = BRep_Tool::Tolerance(theFace);
 228
 229   myCriteria = myBeanTolerance + myFaceTolerance;
 230   myCurveResolution = myCurve.Resolution(myCriteria);
 231
 232   SetSurfaceParameters(mySurface.FirstUParameter(), mySurface.LastUParameter(),
 233                        mySurface.FirstVParameter(), mySurface.LastVParameter());
 234   myResults.Clear();
 235 }
 236
 237 // ==================================================================================
 238 // function: Init
 239 // purpose:
 240 // ==================================================================================
 241 void IntTools_BeanFaceIntersector::Init(const BRepAdaptor_Curve&   theCurve,
 242                                         const BRepAdaptor_Surface& theSurface,
 243                                         const Standard_Real        theBeanTolerance,
 244                                         const Standard_Real        theFaceTolerance)
 245 {
 246   myCurve = theCurve;
 247   mySurface = theSurface;
 248   myTrsfSurface = Handle(Geom_Surface)::DownCast(mySurface.Surface().Surface()->Transformed(mySurface.Trsf()));
 249   myBeanTolerance = theBeanTolerance;
 250   myFaceTolerance = theFaceTolerance;
 251
 252   myCriteria = myBeanTolerance + myFaceTolerance;
 253   myCurveResolution = myCurve.Resolution(myCriteria);
 254
 255   SetSurfaceParameters(mySurface.FirstUParameter(), mySurface.LastUParameter(),
 256                        mySurface.FirstVParameter(), mySurface.LastVParameter());
 257   myResults.Clear();
 258 }
 259
 260 // ==================================================================================
 261 // function: Init
 262 // purpose:
 263 // ==================================================================================
 264 void IntTools_BeanFaceIntersector::Init(const BRepAdaptor_Curve&   theCurve,
 265                                         const BRepAdaptor_Surface& theSurface,
 266                                         const Standard_Real        theFirstParOnCurve,
 267                                         const Standard_Real        theLastParOnCurve,
 268                                         const Standard_Real        theUMinParameter,
 269                                         const Standard_Real        theUMaxParameter,
 270                                         const Standard_Real        theVMinParameter,
 271                                         const Standard_Real        theVMaxParameter,
 272                                         const Standard_Real        theBeanTolerance,
 273                                         const Standard_Real        theFaceTolerance)
 274 {
 275   Init(theCurve, theSurface, theBeanTolerance, theFaceTolerance);
 276   SetBeanParameters(theFirstParOnCurve, theLastParOnCurve);
 277   SetSurfaceParameters(theUMinParameter, theUMaxParameter, theVMinParameter, theVMaxParameter);
 278 }
 279
 280 // ==================================================================================
 281 // function: SetContext
 282 // purpose:
 283 // ==================================================================================
 284 void IntTools_BeanFaceIntersector::SetContext(const Handle(BOPInt_Context)& theContext)
 285 {
 286   myContext = theContext;
 287 }
 288 // ==================================================================================
 289 // function: Context
 290 // purpose:
 291 // ==================================================================================
 292 const Handle(BOPInt_Context)& IntTools_BeanFaceIntersector::Context()const
 293 {
 294   return myContext;
 295 }
 296
 297 // ==================================================================================
 298 // function: SetBeanParameters
 299 // purpose:
 300 // ==================================================================================
 301 void IntTools_BeanFaceIntersector::SetBeanParameters(const Standard_Real theFirstParOnCurve,
 302                                                      const Standard_Real theLastParOnCurve)
 303 {
 304   myFirstParameter = theFirstParOnCurve;
 305   myLastParameter  = theLastParOnCurve;
 306 }
 307
 308 // ==================================================================================
 309 // function: SetSurfaceParameters
 310 // purpose:
 311 // ==================================================================================
 312 void IntTools_BeanFaceIntersector::SetSurfaceParameters(const Standard_Real theUMinParameter,
 313                                                         const Standard_Real theUMaxParameter,
 314                                                         const Standard_Real theVMinParameter,
 315                                                         const Standard_Real theVMaxParameter)
 316 {
 317   myUMinParameter  = theUMinParameter;
 318   myUMaxParameter  = theUMaxParameter;
 319   myVMinParameter  = theVMinParameter;
 320   myVMaxParameter  = theVMaxParameter;
 321 }
 322
 323 // ==================================================================================
 324 // function: Perform
 325 // purpose:
 326 // ==================================================================================
 327 void IntTools_BeanFaceIntersector::Perform()
 328 {
 329   myIsDone = Standard_False;
 330   myResults.Clear();
 331   Standard_Integer bRet;
 332   Standard_Integer aDiscretization = 30;
 333   Standard_Real aRelativeDeflection = 0.01;
 334   myDeflection = aRelativeDeflection;
 335   //
 336   if (myContext.IsNull()) {
 337     myContext=new BOPInt_Context;
 338   }
 339   //
 340   if(myCurve.GetType()==GeomAbs_Line && mySurface.GetType()==GeomAbs_Plane) {
 341     ComputeLinePlane();
 342     return;
 343   }
 344
 345   if(myCurve.GetType()==GeomAbs_Line) {
 346     aDiscretization = 3;
 347     myDeflection = Precision::Confusion();
 348   }
 349   else {
 350     if(myCurve.GetType()==GeomAbs_Circle) {
 351       aDiscretization = 23;
 352       Standard_Real R = myCurve.Circle().Radius();
 353       myDeflection = aRelativeDeflection * R;
 354     }
 355     if(myCurve.GetType() == GeomAbs_Ellipse) {
 356       aDiscretization = 23;
 357       Standard_Real R = myCurve.Ellipse().MajorRadius();
 358       myDeflection = 2 * aRelativeDeflection * R;
 359     }
 360   }
 361 // modified by NIZHNY-MKK  Wed Oct 19 12:15:21 2005
 362   Standard_Boolean bLocalize = Standard_False;
 363
 364   if(((mySurface.GetType() == GeomAbs_BSplineSurface) &&
 365       ((mySurface.UDegree() > 2) || (mySurface.VDegree() > 2)) &&
 366       //modified by NIZNHY-PKV Wed Feb 25 15:02:00 2009f
 367       //((mySurface.NbUKnots() > 2) || (mySurface.NbVKnots() > 2))) ||
 368       ((mySurface.NbUKnots() > 2) && (mySurface.NbVKnots() > 2))) ||
 369      //modified by NIZNHY-PKV Wed Feb 25 15:02:13 2009t
 370      (mySurface.GetType() == GeomAbs_BezierSurface) ||
 371      (mySurface.GetType() == GeomAbs_OtherSurface)) {
 372     bLocalize = Standard_True;
 373   }
 374
 375   if(bLocalize) {
 376     if(Precision::IsInfinite(myUMinParameter) ||
 377        Precision::IsInfinite(myUMaxParameter) ||
 378        Precision::IsInfinite(myVMinParameter) ||
 379        Precision::IsInfinite(myVMaxParameter))
 380       bLocalize = Standard_False;
 381   }
 382   Standard_Boolean bSuccessLocalize = Standard_False;
 383
 384   if( bLocalize) {
 385     myRangeManager.SetBoundaries(myFirstParameter, myLastParameter, 0);
 386     Standard_Boolean coinside = TestComputeCoinside();
 387
 388     if(!coinside)
 389       bSuccessLocalize = ComputeLocalized();
 390   }
 391
 392   if(!bLocalize || !bSuccessLocalize) {
 393 // modified by NIZHNY-MKK  Wed Oct 19 12:15:26 2005.END
 394
 395     IntTools_CArray1OfReal aParams;
 396
 397     if(IntTools::PrepareArgs(myCurve,
 398                              myLastParameter,
 399                              myFirstParameter,
 400                              aDiscretization,
 401                              aRelativeDeflection,
 402                              aParams)) {
 403       return;
 404     }
 405
 406     myRangeManager.SetRanges(aParams, 0);
 407
 408     if(myRangeManager.Length()==0) {
 409       return;
 410     }
 411     //
 412     bRet=FastComputeExactIntersection();
 413     if(bRet == 1) {
 414       IntTools_Range aRange(myFirstParameter, myLastParameter);
 415       myResults.Append(aRange);
 416       myIsDone = Standard_True;
 417       return;
 418     }
 419     //modified by NIZHNY-EMV Fri Apr 20 09:38:08 2012
 420     else if (bRet == 2) {
 421       myIsDone = Standard_True;
 422       return;
 423     }
 424     //modified by NIZHNY-EMV Fri Apr 20 09:38:10 2012
 425
 426
 427 //     Standard_Boolean coinside = TestCoinside(myCurve,mySurface);
 428     Standard_Boolean coinside = TestComputeCoinside();
 429 //     if(coinside) {
 430 //       myRangeManager.InsertRange(myFirstParameter, myLastParameter, 2);
 431 //     }
 432 //     else {
 433     if(!coinside) {
 434       ComputeAroundExactIntersection();
 435
 436       ComputeUsingExtremum();
 437
 438       ComputeNearRangeBoundaries();
 439     }
 440   }
 441
 442   myIsDone = Standard_True;
 443
 444   for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
 445
 446     if(myRangeManager.Flag(i) == 2) {
 447       IntTools_Range aRange = myRangeManager.Range(i);
 448
 449       if(myResults.Length() > 0) {
 450         const IntTools_Range& aLastRange = myResults.Last();
 451
 452         if(Abs(aRange.First() - aLastRange.Last()) > Precision::PConfusion()) {
 453           myResults.Append(aRange);
 454         }
 455         else {
 456           myResults.ChangeValue(myResults.Length()).SetLast(aRange.Last());
 457         }
 458       }
 459       else {
 460         myResults.Append(aRange);
 461       }
 462     }
 463   }
 464 }
 465
 466 // ==================================================================================
 467 // function: Result
 468 // purpose:
 469 // ==================================================================================
 470 const IntTools_SequenceOfRanges& IntTools_BeanFaceIntersector::Result() const
 471 {
 472   return myResults;
 473 }
 474
 475 // ==================================================================================
 476 // function: Result
 477 // purpose:
 478 // ==================================================================================
 479 void IntTools_BeanFaceIntersector::Result(IntTools_SequenceOfRanges& theResults) const
 480 {
 481   theResults = myResults;
 482 }
 483
 484 // ==================================================================================
 485 // function: Distance
 486 // purpose:
 487 // ==================================================================================
 488 Standard_Real IntTools_BeanFaceIntersector::Distance(const Standard_Real theArg)
 489 {
 490   gp_Pnt aPoint = myCurve.Value(theArg);
 491
 492   GeomAPI_ProjectPointOnSurf& aProjector = myContext->ProjPS(mySurface.Face());
 493   aProjector.Perform(aPoint);
 494
 495   if(aProjector.IsDone() && aProjector.NbPoints() > 0) {
 496     return aProjector.LowerDistance();
 497   }
 498   //
 499   Standard_Real aDistance = RealLast();
 500
 501   for(Standard_Integer i=0; i < 4; i++) {
 502     Standard_Real anIsoParameter = (i==0) ? myUMinParameter : ((i==1) ? myUMaxParameter : ((i==2) ? myVMinParameter : myVMaxParameter));
 503     Standard_Real aMinParameter  = (i < 2) ? myVMinParameter : myUMinParameter;
 504     Standard_Real aMaxParameter  = (i < 2) ? myVMaxParameter : myUMaxParameter;
 505     Standard_Real aMidParameter = (aMinParameter + aMaxParameter) * 0.5;
 506     gp_Pnt aPointMin = (i < 2) ? mySurface.Value(anIsoParameter, aMinParameter) : mySurface.Value(aMinParameter, anIsoParameter);
 507     gp_Pnt aPointMax = (i < 2) ? mySurface.Value(anIsoParameter, aMaxParameter) : mySurface.Value(aMaxParameter, anIsoParameter);
 508     gp_Pnt aPointMid = (i < 2) ? mySurface.Value(anIsoParameter, aMidParameter) : mySurface.Value(aMidParameter, anIsoParameter);
 509
 510     Standard_Boolean useMinMaxPoints = Standard_True;
 511     Standard_Boolean computeisoline = Standard_True;
 512
 513     if(aPointMin.IsEqual(aPointMax, myCriteria) &&
 514        aPointMin.IsEqual(aPointMid, myCriteria) &&
 515        aPointMax.IsEqual(aPointMid, myCriteria)) {
 516       computeisoline = Standard_False;
 517     }
 518
 519     if(computeisoline) {
 520       Handle(Geom_Curve) aCurve = (i < 2) ? myTrsfSurface->UIso(anIsoParameter) : myTrsfSurface->VIso(anIsoParameter);
 521       GeomAPI_ProjectPointOnCurve aProjectorOnCurve(aPoint, aCurve, aMinParameter, aMaxParameter);
 522
 523       if(aProjectorOnCurve.NbPoints() > 0) {
 524         useMinMaxPoints = Standard_False;
 525
 526         if(aDistance > aProjectorOnCurve.LowerDistance())
 527           aDistance = aProjectorOnCurve.LowerDistance();
 528       }
 529     }
 530
 531     if(useMinMaxPoints) {
 532       Standard_Real aPPDistance = aPoint.Distance(aPointMin);
 533       aDistance = (aPPDistance < aDistance) ? aPPDistance : aDistance;
 534       aPPDistance = aPoint.Distance(aPointMax);
 535       aDistance = (aPPDistance < aDistance) ? aPPDistance : aDistance;
 536     }
 537   }
 538   return aDistance;
 539 }
 540
 541
 542 // ==================================================================================
 543 // function: Distance
 544 // purpose:
 545 // ==================================================================================
 546 Standard_Real IntTools_BeanFaceIntersector::Distance(const Standard_Real theArg,
 547                                                      Standard_Real&      theUParameter,
 548                                                      Standard_Real&      theVParameter)
 549 {
 550   gp_Pnt aPoint = myCurve.Value(theArg);
 551
 552   theUParameter = myUMinParameter;
 553   theVParameter = myVMinParameter;
 554   //
 555   Standard_Real aDistance = RealLast();
 556   Standard_Boolean projectionfound = Standard_False;
 557
 558   GeomAPI_ProjectPointOnSurf& aProjector = myContext->ProjPS(mySurface.Face());
 559   aProjector.Perform(aPoint);
 560
 561   if(aProjector.IsDone() && aProjector.NbPoints() > 0) {
 562     aProjector.LowerDistanceParameters(theUParameter, theVParameter);
 563     aDistance = aProjector.LowerDistance();
 564     projectionfound = Standard_True;
 565   }
 566
 567   if(!projectionfound) {
 568   //
 569     for(Standard_Integer i = 0; i < 4; i++) {
 570       Standard_Real anIsoParameter = (i==0) ? myUMinParameter : ((i==1) ? myUMaxParameter : ((i==2) ? myVMinParameter : myVMaxParameter));
 571       Standard_Real aMinParameter = (i < 2) ? myVMinParameter : myUMinParameter;
 572       Standard_Real aMaxParameter = (i < 2) ? myVMaxParameter : myUMaxParameter;
 573       Standard_Real aMidParameter = (aMinParameter + aMaxParameter) * 0.5;
 574       gp_Pnt aPointMin = (i < 2) ? mySurface.Value(anIsoParameter, aMinParameter) : mySurface.Value(aMinParameter, anIsoParameter);
 575       gp_Pnt aPointMax = (i < 2) ? mySurface.Value(anIsoParameter, aMaxParameter) : mySurface.Value(aMaxParameter, anIsoParameter);
 576       gp_Pnt aPointMid = (i < 2) ? mySurface.Value(anIsoParameter, aMidParameter) : mySurface.Value(aMidParameter, anIsoParameter);
 577
 578       Standard_Boolean useMinMaxPoints = Standard_True;
 579       Standard_Boolean computeisoline = Standard_True;
 580
 581       if(aPointMin.IsEqual(aPointMax, myCriteria) &&
 582          aPointMin.IsEqual(aPointMid, myCriteria) &&
 583          aPointMax.IsEqual(aPointMid, myCriteria)) {
 584         computeisoline = Standard_False;
 585       }
 586
 587       if(computeisoline) {
 588         Handle(Geom_Curve) aCurve = (i < 2) ? myTrsfSurface->UIso(anIsoParameter) : myTrsfSurface->VIso(anIsoParameter);
 589         GeomAPI_ProjectPointOnCurve aProjectorOnCurve(aPoint, aCurve, aMinParameter, aMaxParameter);
 590
 591         if(aProjectorOnCurve.NbPoints() > 0) {
 592           useMinMaxPoints = Standard_False;
 593
 594           if(aDistance > aProjectorOnCurve.LowerDistance()) {
 595             theUParameter = (i<=1) ? anIsoParameter : aProjectorOnCurve.LowerDistanceParameter();
 596             theVParameter = (i>=2) ? anIsoParameter : aProjectorOnCurve.LowerDistanceParameter();
 597             aDistance = aProjectorOnCurve.LowerDistance();
 598           }
 599         }
 600       }
 601
 602       if(useMinMaxPoints) {
 603         Standard_Real aPPDistance = aPoint.Distance(aPointMin);
 604
 605         if(aPPDistance < aDistance) {
 606           theUParameter = (i<=1) ? anIsoParameter : aMinParameter;
 607           theVParameter = (i>=2) ? anIsoParameter : aMinParameter;
 608           aDistance = aPPDistance;
 609         }
 610         aPPDistance = aPoint.Distance(aPointMax);
 611
 612         if(aPPDistance < aDistance) {
 613           theUParameter = (i<=1) ? anIsoParameter : aMaxParameter;
 614           theVParameter = (i>=2) ? anIsoParameter : aMaxParameter;
 615           aDistance = aPPDistance;
 616         }
 617       }
 618     }
 619   }
 620   theUParameter = (myUMinParameter > theUParameter) ? myUMinParameter : theUParameter;
 621   theUParameter = (myUMaxParameter < theUParameter) ? myUMaxParameter : theUParameter;
 622   theVParameter = (myVMinParameter > theVParameter) ? myVMinParameter : theVParameter;
 623   theVParameter = (myVMaxParameter < theVParameter) ? myVMaxParameter : theVParameter;
 624
 625   return aDistance;
 626 }
 627
 628 // ==================================================================================
 629 // function: ComputeAroundExactIntersection
 630 // purpose:
 631 // ==================================================================================
 632 void IntTools_BeanFaceIntersector::ComputeAroundExactIntersection()
 633 {
 634   IntCurveSurface_HInter anExactIntersector;
 635
 636   Handle(BRepAdaptor_HCurve) aCurve     = new BRepAdaptor_HCurve(myCurve);
 637   Handle(BRepAdaptor_HSurface) aSurface = new BRepAdaptor_HSurface(mySurface);
 638
 639   anExactIntersector.Perform(aCurve, aSurface);
 640
 641   if(anExactIntersector.IsDone()) {
 642     Standard_Integer i = 0;
 643
 644     for(i = 1; i <= anExactIntersector.NbPoints(); i++) {
 645       const IntCurveSurface_IntersectionPoint& aPoint = anExactIntersector.Point(i);
 646
 647       if((aPoint.W() >= myFirstParameter) && (aPoint.W() <= myLastParameter)) {
 648         Standard_Boolean UIsNotValid = ((myUMinParameter > aPoint.U()) || (aPoint.U() > myUMaxParameter));
 649         Standard_Boolean VIsNotValid = ((myVMinParameter > aPoint.V()) || (aPoint.V() > myVMaxParameter));
 650         Standard_Boolean solutionIsValid = !UIsNotValid && !VIsNotValid;
 651         Standard_Real U = aPoint.U();
 652         Standard_Real V = aPoint.V();
 653
 654         if(UIsNotValid || VIsNotValid) {
 655 // modified by NIZHNY-MKK  Thu Jun 17 12:50:39 2004
 656           Standard_Boolean bUCorrected = Standard_True;
 657
 658           if(UIsNotValid) {
 659 // modified by NIZHNY-MKK  Thu Jun 17 12:50:37 2004
 660             bUCorrected = Standard_False;
 661             solutionIsValid = Standard_False;
 662
 663             if(mySurface.IsUPeriodic()) {
 664               Standard_Real aNewU = U;
 665
 666               if(AdjustPeriodic(U, myUMinParameter, myUMaxParameter, mySurface.UPeriod(), aNewU)) {
 667                 solutionIsValid = Standard_True;
 668 // modified by NIZHNY-MKK  Thu Jun 17 12:51:01 2004
 669                 bUCorrected = Standard_True;
 670                 U = aNewU;
 671               }
 672             }
 673           }
 674           // modified by NIZHNY-MKK  Thu Jun 17 12:51:03 2004
 675 //        if(solutionIsValid && VIsNotValid) {
 676           if(bUCorrected && VIsNotValid) {
 677             solutionIsValid = Standard_False;
 678
 679             if(mySurface.IsVPeriodic()) {
 680               Standard_Real aNewV = V;
 681
 682               if(AdjustPeriodic(V, myVMinParameter, myVMaxParameter, mySurface.VPeriod(), aNewV)) {
 683                 solutionIsValid = Standard_True;
 684                 V = aNewV;
 685               }
 686             }
 687           }
 688         }
 689
 690         if(!solutionIsValid)
 691           continue;
 692
 693         Standard_Integer aNbRanges = myRangeManager.Length();
 694
 695         ComputeRangeFromStartPoint(Standard_False, aPoint.W(), U, V);
 696         ComputeRangeFromStartPoint(Standard_True, aPoint.W(), U, V);
 697
 698         if(aNbRanges == myRangeManager.Length()) {
 699           SetEmptyResultRange(aPoint.W(), myRangeManager);
 700         } // end if(aNbRanges == myRangeManager.Length())
 701       }
 702     }
 703
 704     for(i = 1; i <= anExactIntersector.NbSegments(); i++) {
 705       const IntCurveSurface_IntersectionSegment& aSegment = anExactIntersector.Segment(i);
 706       IntCurveSurface_IntersectionPoint aPoint1, aPoint2;
 707       aSegment.Values(aPoint1, aPoint2);
 708
 709       Standard_Real aFirstParameter = (aPoint1.W() < myFirstParameter) ? myFirstParameter : aPoint1.W();
 710       Standard_Real aLastParameter = (myLastParameter < aPoint2.W())   ? myLastParameter  : aPoint2.W();
 711
 712       myRangeManager.InsertRange(aFirstParameter, aLastParameter, 2);
 713
 714       ComputeRangeFromStartPoint(Standard_False, aPoint1.W(), aPoint1.U(), aPoint1.V());
 715       ComputeRangeFromStartPoint(Standard_True,  aPoint2.W(), aPoint2.U(), aPoint2.V());
 716     }
 717   }
 718 }
 719
 720 // ==================================================================================
 721 // function: FastComputeExactIntersection
 722 // purpose:
 723 // ==================================================================================
 724 Standard_Integer IntTools_BeanFaceIntersector::FastComputeExactIntersection()
 725 {
 726   Standard_Integer aresult;
 727   GeomAbs_CurveType aCT;
 728   GeomAbs_SurfaceType aST;
 729   //
 730   aresult = 0;
 731   aCT=myCurve.GetType();
 732   aST=mySurface.GetType();
 733   //
 734   if((aCT==GeomAbs_BezierCurve) ||
 735      (aCT==GeomAbs_BSplineCurve) ||
 736      (aCT==GeomAbs_OtherCurve)) {
 737     return aresult;
 738   }
 739
 740   if(aST==GeomAbs_Plane) {
 741     gp_Pln surfPlane = mySurface.Plane();
 742
 743     if(aCT==GeomAbs_Line) {
 744       if((surfPlane.Distance(myCurve.Value(myFirstParameter)) < myCriteria) &&
 745          (surfPlane.Distance(myCurve.Value(myLastParameter)) < myCriteria)) {
 746         aresult = 1;
 747       }
 748     }
 749     else { // else 1
 750       gp_Dir aDir;
 751
 752       switch(aCT) {
 753         case GeomAbs_Circle: {
 754           aDir = myCurve.Circle().Axis().Direction();
 755           break;
 756         }
 757         case GeomAbs_Ellipse: {
 758           aDir = myCurve.Ellipse().Axis().Direction();
 759           break;
 760         }
 761         case GeomAbs_Hyperbola: {
 762           aDir = myCurve.Hyperbola().Axis().Direction();
 763           break;
 764         }
 765         case GeomAbs_Parabola: {
 766           aDir = myCurve.Parabola().Axis().Direction();
 767           break;
 768         }
 769         default: {
 770           return aresult;
 771         }
 772       }
 773       //
 774       Standard_Real anAngle = aDir.Angle(surfPlane.Axis().Direction());
 775
 776       if(anAngle < Precision::Angular()) {
 777         Standard_Boolean insertRange = Standard_False;
 778
 779         switch(aCT) {
 780           case GeomAbs_Circle: {
 781             Standard_Real adist =
 782               surfPlane.Distance(myCurve.Circle().Location()) +
 783                 myCurve.Circle().Radius() * Precision::Angular();
 784
 785             if(adist < myCriteria) {
 786               insertRange = Standard_True;
 787             }
 788             break;
 789           }
 790           case GeomAbs_Ellipse: {
 791             Standard_Real adist =
 792               surfPlane.Distance(myCurve.Ellipse().Location()) +
 793                 myCurve.Ellipse().MajorRadius() * Precision::Angular();
 794
 795             if(adist < myCriteria) {
 796               insertRange = Standard_True;
 797             }
 798             break;
 799           }
 800           case GeomAbs_Hyperbola:
 801           case GeomAbs_Parabola: {
 802             Standard_Real aMaxPar =
 803               (Abs(myFirstParameter)  > Abs(myLastParameter)) ?
 804                 Abs(myFirstParameter) : Abs(myLastParameter);
 805
 806             gp_Pnt aLoc = (aCT == GeomAbs_Parabola) ?
 807               myCurve.Parabola().Location() :
 808                 myCurve.Hyperbola().Location();
 809             Standard_Real adist = aLoc.Distance(myCurve.Value(aMaxPar));
 810             adist = surfPlane.Distance(aLoc) + adist * Precision::Angular();
 811
 812             if(adist < myCriteria) {
 813               insertRange = Standard_True;
 814             }
 815             break;
 816           }
 817           default: {
 818             break;
 819           }
 820         }
 821         //
 822         if(insertRange) {
 823           aresult = 1;
 824         }
 825       }//if(anAngle < Precision::Angular()) {
 826     }//else { // else 1
 827   }// if(aST==GeomAbs_Plane) {
 828
 829   if(aCT==GeomAbs_Circle) {
 830     gp_Circ aCircle = myCurve.Circle();
 831
 832     if(aST==GeomAbs_Cylinder) {
 833       gp_Cylinder aCylinder = mySurface.Cylinder();
 834       gp_Dir aDir1(aCylinder.Axis().Direction());
 835       gp_Dir aDir2(aCircle.Axis().Direction());
 836       Standard_Real anAngle = aDir1.Angle(aDir2);
 837
 838       if(anAngle < Precision::Angular()) {
 839         gp_Pnt aLoc = aCircle.Location();
 840         gp_Lin anCylAxis(aCylinder.Axis());
 841         Standard_Real alocdist = anCylAxis.Distance(aLoc);
 842         Standard_Real adist = alocdist;
 843         Standard_Real adiff = aCircle.Radius() - aCylinder.Radius();
 844         adist += Abs(adiff);
 845
 846         if(adist < myCriteria) {
 847           Standard_Real acylradius = aCylinder.Radius();
 848           Standard_Real atmpvalue = aCircle.Radius() * sin(Precision::Angular());
 849           Standard_Real aprojectedradius = atmpvalue;
 850           aprojectedradius =
 851             sqrt((aCircle.Radius() * aCircle.Radius())
 852                  - (aprojectedradius * aprojectedradius));
 853           adiff = aprojectedradius - acylradius;
 854           adist = alocdist + Abs(adiff);
 855
 856           if(adist < myCriteria) { // Abs is important function here
 857             aresult = 1;
 858           }
 859         }
 860       }
 861     }// if(aST==GeomAbs_Cylinder)
 862
 863     if(aST==GeomAbs_Sphere) {
 864       gp_Pln aCirclePln(aCircle.Location(), aCircle.Axis().Direction());
 865       IntAna_QuadQuadGeo anInter(aCirclePln, mySurface.Sphere());
 866
 867       if(anInter.IsDone()) {
 868         if(anInter.TypeInter() == IntAna_Circle) {
 869           gp_Circ aCircleToCompare = anInter.Circle(1);
 870           Standard_Real adist =
 871             aCircleToCompare.Location().Distance(aCircle.Location());
 872           Standard_Real adiff = aCircle.Radius() - aCircleToCompare.Radius();
 873           adist += Abs(adiff);
 874
 875           if(adist < myCriteria) {
 876             aresult = 1;
 877           }
 878         }
 879       }
 880     }// if(aST==GeomAbs_Sphere) {
 881   }// if(aCT==GeomAbs_Circle) {
 882   //
 883   //modified by NIZNHY-PKV Thu Mar 01 11:54:04 2012f
 884   if(aST==GeomAbs_Cylinder) {
 885     Standard_Real aRC;
 886     gp_Cylinder aCyl;
 887     //
 888     aCyl=mySurface.Cylinder();
 889     aRC=aCyl.Radius();
 890     const gp_Ax1& aAx1C=aCyl.Axis();
 891     const gp_Dir& aDirC=aAx1C.Direction();
 892     //
 893     if(aCT==GeomAbs_Line) {
 894       Standard_Real aCos, aAng2, aTolang2;
 895       gp_Lin aLin;
 896       //
 897       aTolang2=1.e-16;
 898       aLin=myCurve.Line();
 899       const gp_Dir& aDirL=aLin.Direction();
 900       //
 901       aCos=aDirC.Dot(aDirL);
 902       if(aCos >= 0.) {
 903         aAng2 = 2.*(1. - aCos);
 904       }
 905       else {
 906         aAng2 = 2.*(1. + aCos);
 907       }
 908       //
 909       if(aAng2<=aTolang2) {// IsParallel = Standard_True;
 910         Standard_Boolean bFlag = Standard_False;
 911         Standard_Integer i;
 912         Standard_Real aD;
 913         gp_Pnt aPL[2];
 914         gp_Lin aLC(aAx1C);
 915         //
 916         aPL[0]=myCurve.Value(myFirstParameter);
 917         aPL[1]=myCurve.Value(myLastParameter);
 918         //
 919         for (i=0; i<2; ++i) {
 920           aD=aLC.Distance(aPL[i]);
 921           aD=fabs(aD-aRC);
 922           bFlag=(aD > myCriteria);
 923           if (bFlag) {
 924             break;
 925           }
 926         }
 927         if (!bFlag){
 928           aresult = 1;
 929         }
 930       }
 931
 932     }//if(aCT==GeomAbs_Line) {
 933   }
 934   //modified by NIZNHY-PKV Thu Mar 01 11:54:06 2012t
 935   //
 936   if (aresult==1) {
 937     //check intermediate point
 938     Standard_Real aTm;
 939     Standard_Boolean bValid;
 940     //
 941     const TopoDS_Face& aF = mySurface.Face();
 942     aTm = IntTools_Tools::IntermediatePoint(myFirstParameter, myLastParameter);
 943     const gp_Pnt& aPm = myCurve.Value(aTm);
 944     //
 945     bValid = myContext->IsValidPointForFace(aPm, aF, myCriteria);
 946     if (bValid) {
 947       IntTools_Range aRange(myFirstParameter, myLastParameter);
 948       myRangeManager.InsertRange(aRange, 2);
 949     } else {
 950       aresult=2;
 951     }
 952   }
 953   //
 954   return aresult;
 955 }
 956
 957 // ==================================================================================
 958 // function: ComputeLinePlane
 959 // purpose:
 960 // ==================================================================================
 961 void IntTools_BeanFaceIntersector::ComputeLinePlane()
 962 {
 963   Standard_Real Tolang = 1.e-9;
 964   gp_Pln P = mySurface.Plane();
 965   gp_Lin L = myCurve.Line();
 966
 967   myIsDone = Standard_True;
 968
 969   Standard_Real A,B,C,D;
 970   Standard_Real Al,Bl,Cl;
 971   Standard_Real Dis,Direc;
 972
 973   P.Coefficients(A,B,C,D);
 974   gp_Pnt Orig(L.Location());
 975   L.Direction().Coord(Al,Bl,Cl);
 976
 977   Direc=A*Al+B*Bl+C*Cl;
 978   Dis = A*Orig.X() + B*Orig.Y() + C*Orig.Z() + D;
 979
 980   Standard_Boolean parallel = Standard_False, inplane = Standard_False;
 981   if (Abs(Direc) < Tolang) {
 982     parallel= Standard_True;
 983     if (Abs(Dis) < myCriteria) {
 984       inplane=Standard_True;
 985     }
 986     else {
 987       inplane=Standard_False;
 988     }
 989   }
 990   else {
 991     gp_Pnt p1 = ElCLib::Value(myFirstParameter, L);
 992     gp_Pnt p2 = ElCLib::Value(myLastParameter, L);
 993     Standard_Real d1 = A*p1.X() + B*p1.Y() + C*p1.Z() + D;
 994     if(d1 < 0) d1 = -d1;
 995     Standard_Real d2 = A*p2.X() + B*p2.Y() + C*p2.Z() + D;
 996     if(d2 < 0) d2 = -d2;
 997     if(d1 <= myCriteria && d2 <= myCriteria) {
 998       inplane=Standard_True;
 999     }
1000   }
1001
1002   if(inplane) {
1003     IntTools_Range aRange(myFirstParameter, myLastParameter);
1004     myResults.Append(aRange);
1005     return;
1006   }
1007
1008   if(parallel) {
1009     return;
1010   }
1011
1012   Standard_Real t = - Dis/Direc;
1013   if(t < myFirstParameter || t > myLastParameter) {
1014     return;
1015   }
1016
1017   gp_Pnt pint(Orig.X()+t*Al, Orig.Y()+t*Bl, Orig.Z()+t*Cl);
1018
1019   Standard_Real u, v;
1020   ElSLib::Parameters(P, pint, u, v);
1021   if(myUMinParameter > u || u > myUMaxParameter || myVMinParameter > v || v > myVMaxParameter) {
1022     return;
1023   }
1024
1025   Standard_Real t1 = Max(myFirstParameter, t-myCriteria);
1026   Standard_Real t2 = Min(myLastParameter, t+myCriteria);
1027   IntTools_Range aRange(t1, t2);
1028   myResults.Append(aRange);
1029
1030   return;
1031
1032 }
1033
1034
1035 // ==================================================================================
1036 // function: ComputeUsingExtremum
1037 // purpose:
1038 // ==================================================================================
1039 void IntTools_BeanFaceIntersector::ComputeUsingExtremum()
1040 {
1041   Standard_Real Tol, af, al;
1042   Tol = Precision::PConfusion();
1043   Handle(Geom_Curve) aCurve = BRep_Tool::Curve  (myCurve.Edge(), af, al);
1044   GeomAdaptor_Surface aGASurface (myTrsfSurface,
1045                                   myUMinParameter,
1046                                   myUMaxParameter,
1047                                   myVMinParameter,
1048                                   myVMaxParameter);
1049
1050   Bnd_Box FBox;
1051   BndLib_AddSurface::Add(mySurface, 0., FBox);
1052   FBox.Enlarge(myFaceTolerance);
1053
1054   for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1055
1056     if(myRangeManager.Flag(i) > 0)
1057       continue;
1058
1059     IntTools_Range aParamRange = myRangeManager.Range(i);
1060     Standard_Real anarg1 = aParamRange.First();
1061     Standard_Real anarg2 = aParamRange.Last();
1062
1063     if(anarg2 - anarg1 < Precision::PConfusion()) {
1064
1065       if(((i > 1) && (myRangeManager.Flag(i-1) == 2)) ||
1066          ((i <  myRangeManager.Length()) && (myRangeManager.Flag(i+1) == 2))) {
1067         myRangeManager.SetFlag(i, 1);
1068         continue;
1069       }
1070     }
1071
1072     // check bounding boxes
1073     Bnd_Box EBox;
1074     EBox.Add(myCurve.Value(anarg1));
1075     EBox.Add(myCurve.Value(anarg2));
1076     EBox.Enlarge(myBeanTolerance + myDeflection);
1077
1078     if(EBox.IsOut(FBox)) {
1079       myRangeManager.SetFlag(i, 1);
1080       continue;
1081     }
1082
1083     GeomAdaptor_Curve aGACurve(aCurve, anarg1, anarg2);
1084     Extrema_ExtCS theExtCS(aGACurve, aGASurface, Tol, Tol);
1085     myExtrema = theExtCS;
1086
1087     if(myExtrema.IsDone() && (myExtrema.NbExt() || myExtrema.IsParallel())) {
1088       Standard_Integer anOldNbRanges = myRangeManager.Length();
1089
1090       if (myExtrema.IsParallel()) {
1091
1092         if(myExtrema.SquareDistance(1) < myCriteria * myCriteria) {
1093           Standard_Real U1, V1, U2, V2;
1094           Standard_Real adistance1 = Distance(anarg1, U1, V1);
1095           Standard_Real adistance2 = Distance(anarg2, U2, V2);
1096           Standard_Boolean validdistance1 = (adistance1 < myCriteria);
1097           Standard_Boolean validdistance2 = (adistance2 < myCriteria);
1098
1099           if (validdistance1 && validdistance2) {
1100             myRangeManager.InsertRange(anarg1, anarg2, 2);
1101             continue;
1102           }
1103           else {
1104             if(validdistance1) {
1105               ComputeRangeFromStartPoint(Standard_True, anarg1, U1, V1);
1106             }
1107             else {
1108               if(validdistance2) {
1109                 ComputeRangeFromStartPoint(Standard_False, anarg2, U2, V2);
1110               }
1111               else {
1112                 Standard_Real a  = anarg1;
1113                 Standard_Real b  = anarg2;
1114                 Standard_Real da = adistance1;
1115                 Standard_Real db = adistance2;
1116                 Standard_Real asolution = a;
1117                 Standard_Boolean found = Standard_False;
1118
1119                 while(((b - a) > myCurveResolution) && !found) {
1120                   asolution = (a+b)*0.5;
1121                   Standard_Real adist = Distance(asolution, U1, V1);
1122
1123                   if(adist < myCriteria) {
1124                     found = Standard_True;
1125                   }
1126                   else {
1127                     if(da < db) {
1128                       b = asolution;
1129                       db = adist;
1130                     }
1131                     else {
1132                       a = asolution;
1133                       da = adist;
1134                     }
1135                   }
1136                 } // end while
1137
1138                 if(found) {
1139                   ComputeRangeFromStartPoint(Standard_False, asolution, U1, V1);
1140                   ComputeRangeFromStartPoint(Standard_True, asolution, U1, V1);
1141                 }
1142                 else {
1143                   myRangeManager.SetFlag(i, 1);
1144                 }
1145               }
1146             }
1147           }
1148         }
1149         else {
1150           myRangeManager.SetFlag(i, 1);
1151         }
1152       }
1153       else {
1154         Standard_Boolean solutionfound = Standard_False;
1155
1156         for(Standard_Integer j = 1 ; j <= myExtrema.NbExt(); j++) {
1157
1158           if(myExtrema.SquareDistance(j) < myCriteria * myCriteria) {
1159             Extrema_POnCurv p1;
1160             Extrema_POnSurf p2;
1161             myExtrema.Points(j, p1, p2);
1162             Standard_Real U, V;
1163             p2.Parameter(U, V);
1164
1165             Standard_Integer aNbRanges = myRangeManager.Length();
1166             ComputeRangeFromStartPoint(Standard_False, p1.Parameter(), U, V);
1167             ComputeRangeFromStartPoint(Standard_True, p1.Parameter(), U, V);
1168             solutionfound = Standard_True;
1169
1170             if(aNbRanges == myRangeManager.Length()) {
1171               SetEmptyResultRange(p1.Parameter(), myRangeManager);
1172             }
1173           }
1174         } //end for
1175
1176         if(!solutionfound) {
1177           myRangeManager.SetFlag(i, 1);
1178         }
1179       }
1180       Standard_Integer adifference = myRangeManager.Length() - anOldNbRanges;
1181
1182       if(adifference > 0) {
1183         i+=adifference;
1184       }
1185     } // end if(myExtrema.IsDone() && (myExtrema.NbExt() || myExtrema.IsParallel()))
1186   }
1187 }
1188
1189 // ==================================================================================
1190 // function: ComputeNearRangeBoundaries
1191 // purpose:
1192 // ==================================================================================
1193 void IntTools_BeanFaceIntersector::ComputeNearRangeBoundaries()
1194 {
1195   Standard_Real U = myUMinParameter;
1196   Standard_Real V = myVMinParameter;
1197
1198   for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1199
1200     if(myRangeManager.Flag(i) > 0)
1201       continue;
1202
1203     if((i > 1) && (myRangeManager.Flag(i-1) > 0))
1204       continue;
1205
1206     IntTools_Range aParamRange = myRangeManager.Range(i);
1207
1208     if(Distance(aParamRange.First(), U, V) < myCriteria) {
1209       Standard_Integer aNbRanges = myRangeManager.Length();
1210
1211       if(i > 1) {
1212         ComputeRangeFromStartPoint(Standard_False, aParamRange.First(), U, V, i-1);
1213       }
1214       ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), U, V, i + (myRangeManager.Length() - aNbRanges));
1215
1216       if(aNbRanges == myRangeManager.Length()) {
1217         SetEmptyResultRange(aParamRange.First(), myRangeManager);
1218       }
1219     }
1220   }
1221
1222   if(myRangeManager.Flag(myRangeManager.Length()) == 0) {
1223     IntTools_Range aParamRange = myRangeManager.Range(myRangeManager.Length());
1224
1225     if(Distance(aParamRange.Last(), U, V) < myCriteria) {
1226       Standard_Integer aNbRanges = myRangeManager.Length();
1227
1228       ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), U, V, myRangeManager.Length());
1229
1230       if(aNbRanges == myRangeManager.Length()) {
1231         SetEmptyResultRange(aParamRange.Last(), myRangeManager);
1232       }
1233     }
1234   }
1235 }
1236
1237 // ==================================================================================
1238 // function: ComputeRangeFromStartPoint
1239 // purpose:  Compute range using start point according to parameter theParameter,
1240 //           increasing parameter on curve if ToIncreaseParameter == Standard_True or
1241 //           decreasing parameter on curve if ToIncreaseParameter == Standard_False
1242 // ==================================================================================
1243 void IntTools_BeanFaceIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
1244                                                               const Standard_Real    theParameter,
1245                                                               const Standard_Real    theUParameter,
1246                                                               const Standard_Real    theVParameter)
1247 {
1248   Standard_Integer aFoundIndex = myRangeManager.GetIndex(theParameter, ToIncreaseParameter);
1249
1250   if(aFoundIndex == 0) {
1251     return;
1252   }
1253
1254   ComputeRangeFromStartPoint(ToIncreaseParameter, theParameter, theUParameter, theVParameter, aFoundIndex);
1255 }
1256
1257 // ==================================================================================
1258 // function: ComputeRangeFromStartPoint
1259 // purpose:  Compute range using start point according to parameter theParameter,
1260 //           increasing parameter on curve if ToIncreaseParameter == Standard_True or
1261 //           decreasing parameter on curve if ToIncreaseParameter == Standard_False.
1262 //           theIndex indicate that theParameter belong the range number theIndex.
1263 // ==================================================================================
1264 void IntTools_BeanFaceIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
1265                                                               const Standard_Real    theParameter,
1266                                                               const Standard_Real    theUParameter,
1267                                                               const Standard_Real    theVParameter,
1268                                                               const Standard_Integer theIndex)
1269 {
1270   if(myRangeManager.Flag(theIndex) > 0)
1271     return;
1272
1273     Standard_Integer aValidIndex = theIndex;
1274
1275   Standard_Real aMinDelta        = myCurveResolution * 0.5;
1276   Standard_Real aDeltaRestrictor = myLastParameter - myFirstParameter;
1277
1278   if(aMinDelta > aDeltaRestrictor)
1279     aMinDelta = aDeltaRestrictor * 0.5;
1280
1281   Standard_Real tenOfMinDelta    = aMinDelta * 10.;
1282   Standard_Real aDelta           = myCurveResolution;
1283
1284   Standard_Real aCurPar  = (ToIncreaseParameter) ? (theParameter + aDelta) : (theParameter - aDelta);
1285   Standard_Real aPrevPar = theParameter;
1286   IntTools_Range aCurrentRange = myRangeManager.Range(aValidIndex);
1287
1288   Standard_Boolean BoundaryCondition  = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1289
1290   if(BoundaryCondition) {
1291     aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1292     BoundaryCondition = Standard_False;
1293   }
1294
1295   Standard_Integer loopcounter = 0; // neccesary as infinite loop restricter
1296   Standard_Real U = theUParameter;
1297   Standard_Real V = theVParameter;
1298   Standard_Boolean anotherSolutionFound = Standard_False;
1299
1300   Standard_Boolean isboundaryindex = Standard_False;
1301   Standard_Boolean isvalidindex = Standard_True;
1302
1303   while((aDelta >= aMinDelta) && (loopcounter <= 10)) {
1304     Standard_Boolean pointfound = Standard_False;
1305
1306     //
1307     gp_Pnt aPoint = myCurve.Value(aCurPar);
1308     Extrema_GenLocateExtPS anExtrema(aPoint, mySurface, U, V, 1.e-10, 1.e-10);
1309
1310     if(anExtrema.IsDone()) {
1311       if(anExtrema.SquareDistance() < myCriteria * myCriteria) {
1312         Extrema_POnSurf aPOnSurf = anExtrema.Point();
1313         aPOnSurf.Parameter(U, V);
1314         pointfound = Standard_True;
1315       }
1316     }
1317     else {
1318       pointfound = (Distance(aCurPar) < myCriteria);
1319     }
1320
1321     if(pointfound) {
1322       aPrevPar = aCurPar;
1323       anotherSolutionFound = Standard_True;
1324
1325       if(BoundaryCondition && (isboundaryindex || !isvalidindex))
1326         break;
1327     }
1328     else {
1329       aDeltaRestrictor = aDelta;
1330     }
1331
1332     // if point found decide to increase aDelta using derivative of distance function
1333     //
1334
1335     aDelta = (pointfound) ? (aDelta * 2.) : (aDelta * 0.5);
1336     aDelta = (aDelta < aDeltaRestrictor) ? aDelta : aDeltaRestrictor;
1337
1338     aCurPar = (ToIncreaseParameter) ? (aPrevPar + aDelta) : (aPrevPar - aDelta);
1339
1340
1341     // prevent infinite loop when (aPrevPar +/- aDelta) == aPrevPar == 0.
1342     //
1343
1344     if( aCurPar == aPrevPar )
1345       break;
1346
1347     BoundaryCondition  = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1348
1349     isboundaryindex = Standard_False;
1350     isvalidindex = Standard_True;
1351
1352     if(BoundaryCondition) {
1353       isboundaryindex = ((!ToIncreaseParameter && (aValidIndex == 1)) ||
1354                          (ToIncreaseParameter && (aValidIndex == myRangeManager.Length())));
1355
1356       if(!isboundaryindex) {
1357
1358         if(pointfound) {
1359           Standard_Integer aFlag = (ToIncreaseParameter) ? myRangeManager.Flag(aValidIndex + 1) : myRangeManager.Flag(aValidIndex - 1);
1360
1361           if(aFlag==0) {
1362             aValidIndex = (ToIncreaseParameter) ? (aValidIndex + 1) : (aValidIndex - 1);
1363             aCurrentRange = myRangeManager.Range(aValidIndex);
1364
1365             if((ToIncreaseParameter && (aCurPar > aCurrentRange.Last())) ||
1366                (!ToIncreaseParameter && (aCurPar < aCurrentRange.First()))) {
1367               aCurPar = (aCurrentRange.First() + aCurrentRange.Last()) * 0.5;
1368               aDelta*=0.5;
1369             }
1370           }
1371           else {
1372             isvalidindex = Standard_False;
1373             aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1374           }
1375         }
1376       }
1377       else {
1378         aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1379       }
1380
1381       if(aDelta < tenOfMinDelta) {
1382         loopcounter++;
1383       }
1384       else {
1385         loopcounter = 0;
1386       }
1387     } // if(BoundaryCondition)
1388   }
1389
1390   if(anotherSolutionFound) {
1391     if(ToIncreaseParameter)
1392       myRangeManager.InsertRange(theParameter, aPrevPar, 2);
1393     else
1394       myRangeManager.InsertRange(aPrevPar, theParameter, 2);
1395   }
1396 }
1397
1398 // ---------------------------------------------------------------------------------
1399 // static function: AdjustPeriodic
1400 // purpose:
1401 // ---------------------------------------------------------------------------------
1402 static Standard_Boolean AdjustPeriodic(const Standard_Real U,
1403                                        const Standard_Real UFirst,
1404                                        const Standard_Real ULast,
1405                                        const Standard_Real Period,
1406                                        Standard_Real&      UResult) {
1407   UResult = U;
1408   Standard_Real u = U;
1409   Standard_Real Eps = Epsilon(Period);
1410   while (Eps < (UFirst-u)) u += Period;
1411   while (Eps > (ULast -u)) u -= Period;
1412   if ( u < UFirst)
1413     return Standard_False;
1414
1415   UResult = u;
1416   return Standard_True;
1417 }
1418
1419 // ---------------------------------------------------------------------------------
1420 // static function: SetEmptyResultRange
1421 // purpose:
1422 // ---------------------------------------------------------------------------------
1423 static Standard_Boolean SetEmptyResultRange(const Standard_Real      theParameter,
1424                                             IntTools_MarkedRangeSet& theMarkedRange) {
1425
1426   const TColStd_SequenceOfInteger& anIndices = theMarkedRange.GetIndices(theParameter);
1427   Standard_Boolean add = (anIndices.Length() > 0);
1428
1429   for(Standard_Integer k = 1; k <= anIndices.Length(); k++) {
1430     if(theMarkedRange.Flag(anIndices(k)) == 2) {
1431       add = Standard_False;
1432       break;
1433     }
1434   }
1435
1436   if(add) {
1437     theMarkedRange.InsertRange(theParameter, theParameter, 2);
1438   }
1439
1440   return add;
1441 }
1442
1443 // ---------------------------------------------------------------------------------
1444 // static function: TestCoinside
1445 // purpose:
1446 // ---------------------------------------------------------------------------------
1447 // static Standard_Boolean TestClose(const Extrema_ExtPS & theExt,
1448 //                                   const Standard_Real   theDist)
1449 // {
1450 //   Standard_Boolean close = Standard_False;
1451 //   if(!theExt.IsDone() || theExt.NbExt() == 0)
1452 //     return close;
1453 //   else {
1454 //     Standard_Integer ie;
1455 //     for(ie = 1; ie <= theExt.NbExt(); ie++) {
1456 //       Standard_Real dist = theExt.Value(ie);
1457 //       if(dist <= theDist) {
1458 //         close = Standard_True;
1459 //         break;
1460 //       }
1461 //     }
1462 //   }
1463 //   return close;
1464 // }
1465
1466 // Standard_Boolean TestCoinside(const BRepAdaptor_Curve&   theCurve,
1467 //                               const BRepAdaptor_Surface& theSurface)
1468 // {
1469 //   Standard_Real cfp = theCurve.FirstParameter(), clp = theCurve.LastParameter();
1470 //   Standard_Real cdp = fabs(clp - cfp) / 23.;
1471
1472 //   Standard_Integer i = 0;
1473 //   Standard_Real tolE = theCurve.Tolerance(), tolF = theSurface.Tolerance();
1474 //   Standard_Real tolT = tolE + tolF, tolU = 1.e-9, tolV = 1.e-9;
1475 //   gp_Pnt aP;
1476
1477 //   theCurve.D0(cfp,aP);
1478 //   Extrema_ExtPS eps(aP,theSurface,tolU,tolV);
1479
1480 //   if(!TestClose(eps,tolT))
1481 //     return Standard_False;
1482
1483 //   theCurve.D0(clp,aP);
1484 //   eps.Perform(aP);
1485
1486 //   if(!TestClose(eps,tolT))
1487 //     return Standard_False;
1488
1489 //   Standard_Boolean close = Standard_True;
1490
1491 //   for(i = 1; i <= 22; i++) {
1492 //     theCurve.D0((cfp+((Standard_Real)i)*cdp),aP);
1493 //     eps.Perform(aP);
1494 //     if(!TestClose(eps,tolT)) {
1495 //       close = Standard_False;
1496 //       break;
1497 //     }
1498 //   }
1499 //   return close;
1500 // }
1501
1502 // ======================================================================================================================
1503 // function: LocalizeSolutions
1504 // purpose:
1505 // ======================================================================================================================
1506 Standard_Boolean IntTools_BeanFaceIntersector::LocalizeSolutions(const IntTools_CurveRangeSample& theCurveRange,
1507                                                                  const Bnd_Box& theBoxCurve,
1508                                                                  const IntTools_SurfaceRangeSample& theSurfaceRange,
1509                                                                  const Bnd_Box& theBoxSurface,
1510                                                                  IntTools_CurveRangeLocalizeData& theCurveData,
1511                                                                  IntTools_SurfaceRangeLocalizeData& theSurfaceData,
1512                                                                  IntTools_ListOfCurveRangeSample& theListCurveRange,
1513                                                                  IntTools_ListOfSurfaceRangeSample& theListSurfaceRange)
1514 {
1515   Standard_Integer tIt = 0, uIt = 0, vIt = 0;
1516
1517   //
1518   IntTools_CurveRangeSample aRootRangeC(0);
1519   aRootRangeC.SetDepth(0);
1520   IntTools_SurfaceRangeSample aRootRangeS(0, 0, 0, 0);
1521
1522   Bnd_Box aMainBoxC = theBoxCurve;
1523   Bnd_Box aMainBoxS = theBoxSurface;
1524   Standard_Boolean bMainBoxFoundS = Standard_False;
1525   Standard_Boolean bMainBoxFoundC = Standard_False;
1526   //
1527   IntTools_ListOfCurveRangeSample aListCurveRangeFound;
1528   IntTools_ListOfSurfaceRangeSample aListSurfaceRangeFound;
1529
1530
1531   IntTools_Range aRangeC = theCurveRange.GetRange(myFirstParameter, myLastParameter, theCurveData.GetNbSample());
1532   Standard_Real localdiffC = (aRangeC.Last() - aRangeC.First()) / theCurveData.GetNbSample();
1533
1534   Standard_Real aCurPar = aRangeC.First();
1535   Standard_Real aPrevPar = aRangeC.First();
1536   Standard_Integer aCurIndexInit = theCurveRange.GetRangeIndexDeeper(theCurveData.GetNbSample());
1537
1538
1539   TColStd_ListOfInteger aListCToAvoid;
1540   Standard_Boolean bGlobalCheckDone = Standard_False;
1541   //
1542
1543   //
1544
1545   Standard_Integer aCurIndexU = theSurfaceRange.GetRangeIndexUDeeper(theSurfaceData.GetNbSampleU());
1546
1547   Standard_Integer aCurIndexVInit = theSurfaceRange.GetRangeIndexVDeeper(theSurfaceData.GetNbSampleV());
1548   IntTools_Range aRangeV = theSurfaceRange.GetRangeV(myVMinParameter, myVMaxParameter, theSurfaceData.GetNbSampleV());
1549
1550   //
1551   IntTools_Range aRangeU = theSurfaceRange.GetRangeU(myUMinParameter, myUMaxParameter, theSurfaceData.GetNbSampleU());
1552   Standard_Real aCurParU = aRangeU.First();
1553   Standard_Real aLocalDiffU = (aRangeU.Last() - aRangeU.First()) / theSurfaceData.GetNbSampleU();
1554
1555   Standard_Real aPrevParU = aCurParU;
1556   Standard_Real aLocalDiffV = (aRangeV.Last() - aRangeV.First()) / theSurfaceData.GetNbSampleV();
1557
1558
1559   // ranges check.begin
1560   Standard_Boolean bAllowSamplingC = Standard_True;
1561   Standard_Boolean bAllowSamplingU = Standard_True;
1562   Standard_Boolean bAllowSamplingV = Standard_True;
1563
1564   // check
1565   CheckSampling(theCurveRange, theSurfaceRange, theCurveData, theSurfaceData,
1566                 localdiffC, aLocalDiffU, aLocalDiffV,
1567                 bAllowSamplingC, bAllowSamplingU, bAllowSamplingV);
1568   //
1569
1570   if(!bAllowSamplingC && !bAllowSamplingU && !bAllowSamplingV) {
1571     theListCurveRange.Append(theCurveRange);
1572     theListSurfaceRange.Append(theSurfaceRange);
1573     return Standard_True;
1574   }
1575   // ranges check.end
1576
1577   // init template. begin
1578   IntTools_CurveRangeSample aNewRangeCTemplate;
1579
1580   if(!bAllowSamplingC) {
1581     aNewRangeCTemplate = theCurveRange;
1582     aCurIndexInit = theCurveRange.GetRangeIndex();
1583     localdiffC = (aRangeC.Last() - aRangeC.First());
1584   }
1585   else {
1586     aNewRangeCTemplate.SetDepth(theCurveRange.GetDepth() + 1);
1587     aNewRangeCTemplate.SetRangeIndex(aCurIndexInit);
1588   }
1589
1590   IntTools_SurfaceRangeSample aNewRangeSTemplate = theSurfaceRange;
1591
1592   if(bAllowSamplingU) {
1593     aNewRangeSTemplate.SetDepthU(theSurfaceRange.GetDepthU() + 1);
1594   }
1595   else {
1596     aCurIndexU = aNewRangeSTemplate.GetIndexU();
1597     aLocalDiffU = aRangeU.Last() - aRangeU.First();
1598   }
1599
1600   if(bAllowSamplingV) {
1601     aNewRangeSTemplate.SetDepthV(theSurfaceRange.GetDepthV() + 1);
1602   }
1603   else {
1604     aCurIndexVInit = theSurfaceRange.GetIndexV();
1605     aLocalDiffV = aRangeV.Last() - aRangeV.First();
1606   }
1607   // init template. end
1608
1609
1610   Standard_Boolean bHasOut = Standard_False;
1611   const Standard_Integer nbU = (bAllowSamplingU) ? theSurfaceData.GetNbSampleU() : 1;
1612   const Standard_Integer nbV = (bAllowSamplingV) ? theSurfaceData.GetNbSampleV() : 1;
1613   const Standard_Integer nbC = (bAllowSamplingC) ? theCurveData.GetNbSample() : 1;
1614
1615   for(uIt = 1; uIt <= nbU; uIt++, aCurIndexU++, aPrevParU = aCurParU) {
1616     aCurParU += aLocalDiffU;
1617
1618
1619     Standard_Real aCurParV = aRangeV.First();
1620     Standard_Real aPrevParV = aCurParV;
1621     Standard_Integer aCurIndexV = aCurIndexVInit;
1622
1623     Standard_Boolean bHasOutV = Standard_False;
1624
1625     // ///////
1626     for(vIt = 1; vIt <= nbV; vIt++, aCurIndexV++, aPrevParV = aCurParV) {
1627
1628       aCurParV += aLocalDiffV;
1629
1630
1631       // //////////////
1632       //
1633       IntTools_SurfaceRangeSample aNewRangeS = aNewRangeSTemplate;
1634
1635       if(bAllowSamplingU) {
1636         aNewRangeS.SetIndexU(aCurIndexU);
1637       }
1638
1639       if(bAllowSamplingV) {
1640         aNewRangeS.SetIndexV(aCurIndexV);
1641       }
1642
1643       if(theSurfaceData.IsRangeOut(aNewRangeS)) {
1644         bHasOutV = Standard_True;
1645         continue;
1646       }
1647
1648       // ///////
1649
1650       Bnd_Box aBoxS;
1651
1652       if(!theSurfaceData.FindBox(aNewRangeS, aBoxS)) {
1653
1654         if(mySurface.GetType() == GeomAbs_BSplineSurface) {
1655 //      if(Standard_False ) {
1656           Handle(Geom_BSplineSurface) aSurfBspl = Handle(Geom_BSplineSurface)::DownCast(myTrsfSurface);
1657           aBoxS = GetSurfaceBox(aSurfBspl, aPrevParU, aCurParU, aPrevParV, aCurParV, myCriteria, theSurfaceData);
1658         }
1659         else {
1660           BndLib_AddSurface::Add(mySurface, aPrevParU, aCurParU, aPrevParV, aCurParV, myCriteria, aBoxS);
1661         }
1662 //      Bnd_Box aMainBoxC;
1663
1664         if(!bMainBoxFoundC && theCurveData.FindBox(aRootRangeC, aMainBoxC)) {
1665           bMainBoxFoundC = Standard_True;
1666         }
1667
1668           if(aBoxS.IsOut(aMainBoxC)) {
1669             theSurfaceData.AddOutRange(aNewRangeS);
1670             bHasOutV = Standard_True;
1671             continue;
1672           }
1673 //      }
1674         theSurfaceData.AddBox(aNewRangeS, aBoxS);
1675       }
1676
1677       if(aBoxS.IsOut(theBoxCurve)) {
1678         bHasOutV = Standard_True;
1679         continue;
1680       }
1681
1682       IntTools_ListOfBox aListOfBox;
1683       TColStd_ListOfInteger aListOfIndex;
1684
1685       Standard_Boolean bHasOutC = Standard_False;
1686       Standard_Integer aCurIndex = aCurIndexInit;
1687
1688       // ////////////////////////////
1689       aCurPar = aRangeC.First();
1690       aPrevPar = aRangeC.First();
1691       IntTools_CurveRangeSample aCurRangeC = aNewRangeCTemplate;
1692
1693       for (tIt = 1; tIt <= nbC; tIt++, aCurIndex++, aPrevPar = aCurPar) {
1694
1695         aCurPar += localdiffC;
1696
1697         // ignore already computed. begin
1698         Standard_Boolean bFound = Standard_False;
1699         TColStd_ListIteratorOfListOfInteger anItToAvoid(aListCToAvoid);
1700
1701         for(; anItToAvoid.More(); anItToAvoid.Next()) {
1702           if(tIt == anItToAvoid.Value()) {
1703             bFound = Standard_True;
1704             break;
1705           }
1706         }
1707
1708         if(!bFound) {
1709           if(bAllowSamplingC) {
1710             aCurRangeC.SetRangeIndex(aCurIndex);
1711           }
1712           bFound = theCurveData.IsRangeOut(aCurRangeC);
1713         }
1714
1715         if(bFound) {
1716           bHasOutC = Standard_True;
1717           continue;
1718         }
1719         // ignore already computed. end
1720
1721         // compute Box
1722         Bnd_Box aBoxC;
1723
1724         if(!theCurveData.FindBox(aCurRangeC, aBoxC)) {
1725           BndLib_Add3dCurve::Add(myCurve, aPrevPar, aCurPar, myCriteria, aBoxC);
1726
1727 //        Bnd_Box aMainBoxS;
1728
1729           if(!bMainBoxFoundS && theSurfaceData.FindBox(aRootRangeS, aMainBoxS)) {
1730             bMainBoxFoundS = Standard_True;
1731           }
1732             if(aBoxC.IsOut(aMainBoxS)) {
1733               theCurveData.AddOutRange(aCurRangeC);
1734               bHasOutC = Standard_True;
1735               continue;
1736             }
1737 //        }
1738           theCurveData.AddBox(aCurRangeC, aBoxC);
1739         }
1740
1741         if(!bGlobalCheckDone && aBoxC.IsOut(theBoxSurface)) {
1742           aListCToAvoid.Append(tIt);
1743           bHasOutC = Standard_True;
1744           continue;
1745         }
1746
1747         if(aBoxC.IsOut(aBoxS)) {
1748           bHasOutV = Standard_True;
1749           bHasOutC = Standard_True;
1750           continue;
1751         }
1752         //
1753
1754         aListOfIndex.Append(tIt);
1755         aListOfBox.Append(aBoxC);
1756       } // end for(tIt...)
1757
1758       bGlobalCheckDone = Standard_True;
1759
1760       if(bHasOutC) {
1761         bHasOutV = Standard_True;
1762       }
1763
1764       // //////////////
1765       //
1766
1767       IntTools_CurveRangeSample aNewRangeC = aNewRangeCTemplate;
1768
1769       aCurIndex = aCurIndexInit;
1770       TColStd_ListIteratorOfListOfInteger anItI(aListOfIndex);
1771       IntTools_ListIteratorOfListOfBox anItBox(aListOfBox);
1772       Standard_Boolean bUseOldC = Standard_False;
1773       Standard_Boolean bUseOldS = Standard_False;
1774       Standard_Boolean bCheckSize = !bHasOutC;
1775
1776       for(; anItI.More() && anItBox.More(); anItI.Next(), anItBox.Next()) {
1777         aCurIndex = aCurIndexInit + anItI.Value() - 1;
1778
1779         bUseOldS = Standard_False;
1780
1781         if(bAllowSamplingC) {
1782           aNewRangeC.SetRangeIndex(aCurIndex);
1783         }
1784
1785
1786         if(bCheckSize) {
1787
1788           if((theCurveRange.GetDepth() == 0) ||
1789              (theSurfaceRange.GetDepthU() == 0) ||
1790              (theSurfaceRange.GetDepthV() == 0)) {
1791             bHasOutC = Standard_True;
1792             bHasOutV = Standard_True;
1793           }
1794           else if((theCurveRange.GetDepth() < 4) &&
1795                   (theSurfaceRange.GetDepthU() < 4) &&
1796                   (theSurfaceRange.GetDepthV() < 4)) {
1797             Bnd_Box aBoxC = anItBox.Value();
1798
1799             if(!aBoxC.IsWhole() && !aBoxS.IsWhole()) {
1800               Standard_Real aDiagC = aBoxC.SquareExtent();
1801               Standard_Real aDiagS = aBoxS.SquareExtent();
1802
1803               if(aDiagC < aDiagS) {
1804                 if((aDiagC * 10.) < aDiagS) {
1805                   bUseOldC = Standard_True;
1806                   bHasOutC = Standard_True;
1807                   bHasOutV = Standard_True;
1808                   break;
1809                 }
1810               }
1811               else {
1812                 if((aDiagS * 10.) < aDiagC) {
1813                   bUseOldS = Standard_True;
1814                   bHasOutC = Standard_True;
1815                   bHasOutV = Standard_True;
1816                 }
1817               }
1818             }
1819           }
1820         }
1821
1822
1823         if(!bHasOutC) {
1824           aListCurveRangeFound.Append(aNewRangeC);
1825           aListSurfaceRangeFound.Append(aNewRangeS);
1826         }
1827         else {
1828
1829 //        if(bUseOldS || bAllowSamplingU || bAllowSamplingV) {
1830 //          theSurfaceData.AddBox(aNewRangeS, aBoxS);
1831 //        }
1832
1833           if(bUseOldS && aNewRangeC.IsEqual(theCurveRange)) {
1834             return Standard_False;
1835           }
1836
1837           if(!LocalizeSolutions(aNewRangeC, anItBox.Value(),
1838                                 ((bUseOldS) ? theSurfaceRange : aNewRangeS),
1839                                 ((bUseOldS) ? theBoxSurface : aBoxS),
1840                                 theCurveData, theSurfaceData,
1841                                 theListCurveRange, theListSurfaceRange))
1842             return Standard_False;
1843         }
1844       }
1845       // end (tIt...)
1846       aListOfIndex.Clear();
1847       aListOfBox.Clear();
1848
1849       if(bHasOutV) {
1850 //      theSurfaceData.AddBox(aNewRangeS, aBoxS);
1851
1852         if(bUseOldC && bAllowSamplingC && (bAllowSamplingU || bAllowSamplingV)) {
1853           if(!LocalizeSolutions(theCurveRange, theBoxCurve,
1854                                 aNewRangeS, aBoxS,
1855                                 theCurveData, theSurfaceData,
1856                                 theListCurveRange, theListSurfaceRange))
1857             return Standard_False;
1858         }
1859       }
1860     } // end for (vIt...)
1861
1862     if(bHasOutV) {
1863       bHasOut = Standard_True;
1864     }
1865   }
1866
1867   if(!bHasOut) {
1868     theListCurveRange.Append(theCurveRange);
1869     theListSurfaceRange.Append(theSurfaceRange);
1870   }
1871   else {
1872     IntTools_ListIteratorOfListOfCurveRangeSample anIt1(aListCurveRangeFound);
1873     IntTools_ListIteratorOfListOfSurfaceRangeSample anIt2(aListSurfaceRangeFound);
1874
1875     for(; anIt1.More() && anIt2.More(); anIt1.Next(), anIt2.Next()) {
1876       theListCurveRange.Append(anIt1.Value());
1877       theListSurfaceRange.Append(anIt2.Value());
1878     }
1879   }
1880   return Standard_True;
1881 }
1882
1883
1884 // ======================================================================================================================
1885 // function: ComputeLocalized
1886 // purpose:
1887 // ======================================================================================================================
1888 Standard_Boolean IntTools_BeanFaceIntersector::ComputeLocalized() {
1889   Standard_Real Tol = Precision::PConfusion();
1890
1891   IntTools_SurfaceRangeSample aSurfaceRange(0, 0, 0, 0);
1892   Standard_Real dMinU = 10. * Precision::PConfusion();
1893   Standard_Real dMinV = dMinU;
1894   IntTools_SurfaceRangeLocalizeData aSurfaceDataInit(3, 3, dMinU, dMinV);
1895   IntTools_SurfaceRangeLocalizeData& aSurfaceData = myContext->SurfaceData(mySurface.Face());
1896   aSurfaceData.RemoveRangeOutAll();
1897   aSurfaceData.ClearGrid();
1898
1899   Bnd_Box FBox;
1900   Standard_Boolean bFBoxFound = aSurfaceData.FindBox(aSurfaceRange, FBox);
1901
1902   if(mySurface.GetType() == GeomAbs_BSplineSurface) {
1903     Handle(Geom_BSplineSurface) aSurfBspl = Handle(Geom_BSplineSurface)::DownCast(myTrsfSurface);
1904
1905     ComputeGridPoints(aSurfBspl, myUMinParameter, myUMaxParameter,
1906                       myVMinParameter, myVMaxParameter, myFaceTolerance,
1907                       aSurfaceData);
1908
1909     if(!bFBoxFound) {
1910       FBox = GetSurfaceBox(aSurfBspl, myUMinParameter, myUMaxParameter,
1911                            myVMinParameter, myVMaxParameter, myCriteria,
1912                            aSurfaceData);
1913       aSurfaceData.AddBox(aSurfaceRange, FBox);
1914     }
1915
1916   } else if(!bFBoxFound) {
1917
1918     BndLib_AddSurface::Add(mySurface, myUMinParameter, myUMaxParameter, myVMinParameter, myVMaxParameter, myFaceTolerance, FBox);
1919     aSurfaceData.AddBox(aSurfaceRange, FBox);
1920   }
1921
1922   Bnd_Box EBox;
1923
1924   BndLib_Add3dCurve::Add(myCurve.Trim(myFirstParameter, myLastParameter, Precision::PConfusion())->Curve(), myBeanTolerance, EBox);
1925
1926   if(EBox.IsOut(FBox)) {
1927     for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1928       myRangeManager.SetFlag(i, 1);
1929     }
1930     aSurfaceData.ClearGrid();
1931
1932     return Standard_True;
1933   }
1934
1935   IntTools_ListOfCurveRangeSample aListCurveRange;
1936   IntTools_ListOfSurfaceRangeSample aListSurfaceRange;
1937
1938   IntTools_CurveRangeSample aCurveRange(0);
1939   aCurveRange.SetDepth(0);
1940   Standard_Integer nbSampleC = 3;
1941   Standard_Integer nbSampleU = aSurfaceData.GetNbSampleU();
1942   Standard_Integer nbSampleV = aSurfaceData.GetNbSampleV();
1943   Standard_Real dMinC = 10. * myCurveResolution;
1944   IntTools_ListOfCurveRangeSample aListOut;
1945
1946   // check
1947   Standard_Boolean bAllowSamplingC = Standard_True;
1948   Standard_Boolean bAllowSamplingU = Standard_True;
1949   Standard_Boolean bAllowSamplingV = Standard_True;
1950   IntTools_CurveRangeLocalizeData aCurveDataTmp(nbSampleC, dMinC);
1951   IntTools_SurfaceRangeLocalizeData aSurfaceDataTmp(nbSampleU, nbSampleV, dMinU, dMinV);
1952
1953   CheckSampling(aCurveRange, aSurfaceRange, aCurveDataTmp, aSurfaceDataTmp,
1954                 myLastParameter - myFirstParameter,
1955                 myUMaxParameter - myUMinParameter,
1956                 myVMaxParameter - myVMinParameter,
1957                 bAllowSamplingC, bAllowSamplingU, bAllowSamplingV);
1958
1959
1960   {
1961     IntTools_CurveRangeLocalizeData aCurveData(nbSampleC, dMinC);
1962
1963     aCurveData.AddBox(aCurveRange, EBox);
1964
1965     if(!LocalizeSolutions(aCurveRange, EBox, aSurfaceRange, FBox,
1966                           aCurveData, aSurfaceData,
1967                           aListCurveRange, aListSurfaceRange)) {
1968       aSurfaceData.ClearGrid();
1969
1970       return Standard_False;
1971     }
1972
1973     IntTools_ListOfCurveRangeSample aListCurveRangeSort;
1974     IntTools_ListOfSurfaceRangeSample aListSurfaceRangeSort;
1975
1976     MergeSolutions(aListCurveRange, aListSurfaceRange, aListCurveRangeSort, aListSurfaceRangeSort);
1977
1978     IntTools_ListIteratorOfListOfCurveRangeSample anItC(aListCurveRangeSort);
1979     IntTools_ListIteratorOfListOfSurfaceRangeSample anItS(aListSurfaceRangeSort);
1980     IntTools_SurfaceRangeSample aRangeSPrev;
1981
1982     Extrema_GenExtCS anExtremaGen;
1983
1984     for(; anItC.More() && anItS.More(); anItC.Next(), anItS.Next()) {
1985
1986       IntTools_Range aRangeC(myFirstParameter, myLastParameter);
1987
1988       if(bAllowSamplingC)
1989         aRangeC = anItC.Value().GetRange(myFirstParameter, myLastParameter, nbSampleC);
1990
1991       IntTools_Range aRangeU(myUMinParameter, myUMaxParameter);
1992
1993       if(bAllowSamplingU)
1994         aRangeU = anItS.Value().GetRangeU(myUMinParameter, myUMaxParameter, nbSampleU);
1995
1996       IntTools_Range aRangeV(myVMinParameter, myVMaxParameter);
1997
1998       if(bAllowSamplingV)
1999         aRangeV = anItS.Value().GetRangeV(myVMinParameter, myVMaxParameter, nbSampleV);
2000
2001       Standard_Real anarg1 = aRangeC.First(), anarg2 = aRangeC.Last();
2002
2003       Standard_Boolean bFound = Standard_False;
2004
2005       Standard_Integer nMinIndex = myRangeManager.Length();
2006       Standard_Integer nMaxIndex = -1;
2007       const TColStd_SequenceOfInteger& anInds1 = myRangeManager.GetIndices(anarg1);
2008       Standard_Integer indIt = 1;
2009
2010       for(indIt = 1 ; indIt <= anInds1.Length(); indIt++) {
2011         Standard_Integer nIndex = anInds1.Value(indIt);
2012         nMinIndex = (nMinIndex > nIndex) ? nIndex : nMinIndex;
2013         nMaxIndex = (nMaxIndex < nIndex) ? nIndex : nMaxIndex;
2014       }
2015
2016       for(indIt = nMinIndex ; indIt <= nMaxIndex; indIt++) {
2017         if(myRangeManager.Flag(indIt) == 2) {
2018           bFound = Standard_True;
2019           break;
2020         }
2021       }
2022
2023       if(bFound)
2024         continue;
2025       nMinIndex = (nMaxIndex >= 0) ? nMaxIndex : nMinIndex;
2026       const TColStd_SequenceOfInteger& anInds2 = myRangeManager.GetIndices(anarg2);
2027
2028       for(indIt = 1 ; indIt <= anInds2.Length(); indIt++) {
2029         Standard_Integer nIndex = anInds2.Value(indIt);
2030         nMinIndex = (nMinIndex > nIndex) ? nIndex : nMinIndex;
2031         nMaxIndex = (nMaxIndex < nIndex) ? nIndex : nMaxIndex;
2032       }
2033
2034       for(indIt = nMinIndex ; indIt <= nMaxIndex; indIt++) {
2035         if(myRangeManager.Flag(indIt) == 2) {
2036           bFound = Standard_True;
2037           break;
2038         }
2039       }
2040
2041       if(bFound)
2042         continue;
2043
2044       Standard_Real parUF = aRangeU.First(), parUL = aRangeU.Last();
2045       Standard_Real parVF = aRangeV.First(), parVL = aRangeV.Last();
2046
2047       if(aRangeSPrev.IsEqual(anItS.Value())) {
2048         anExtremaGen.Perform(myCurve, 10, anarg1, anarg2, Tol);
2049       }
2050       else {
2051         anExtremaGen.Initialize(mySurface, 10, 10, parUF, parUL, parVF, parVL, Tol);
2052         anExtremaGen.Perform(myCurve, 10, anarg1, anarg2, Tol);
2053       }
2054
2055       if(anExtremaGen.IsDone() && (anExtremaGen.NbExt() > 0)) {
2056
2057         for(Standard_Integer j = 1 ; j <= anExtremaGen.NbExt(); j++) {
2058
2059           if(anExtremaGen.SquareDistance(j) < myCriteria * myCriteria) {
2060
2061             Extrema_POnCurv p1;
2062             Extrema_POnSurf p2;
2063             p1 = anExtremaGen.PointOnCurve(j);
2064             p2 = anExtremaGen.PointOnSurface(j);
2065             Standard_Real U, V, T;
2066             T = p1.Parameter();
2067             p2.Parameter(U, V);
2068
2069             if (myCurve.IsPeriodic())
2070               T = ElCLib::InPeriod(T, anarg1, anarg1 + myCurve.Period());
2071             if (mySurface.IsUPeriodic())
2072               U = ElCLib::InPeriod(U, parUF, parUF + mySurface.UPeriod());
2073             if (mySurface.IsVPeriodic())
2074               V = ElCLib::InPeriod(V, parVF, parVF + mySurface.VPeriod());
2075
2076             //To avoid occasional going out of boundaries because of numerical
2077             //problem
2078             if(U < myUMinParameter) U = myUMinParameter;
2079             if(U > myUMaxParameter) U = myUMaxParameter;
2080             if(V < myVMinParameter) V = myVMinParameter;
2081             if(V > myVMaxParameter) V = myVMaxParameter;
2082
2083             Standard_Integer aNbRanges = myRangeManager.Length();
2084             ComputeRangeFromStartPoint(Standard_False, T, U, V);
2085             ComputeRangeFromStartPoint(Standard_True, T, U, V);
2086
2087             if(aNbRanges == myRangeManager.Length()) {
2088               SetEmptyResultRange(T, myRangeManager);
2089             }
2090           }
2091         } //end for
2092       }
2093       else {
2094         myRangeManager.InsertRange(anarg1, anarg2, 0);
2095       }
2096
2097       aRangeSPrev = anItS.Value();
2098     }
2099
2100     //
2101     aCurveData.ListRangeOut(aListOut);
2102   }
2103
2104   //
2105   if(bAllowSamplingC) {
2106     IntTools_ListIteratorOfListOfCurveRangeSample anItC(aListOut);
2107
2108     for(; anItC.More(); anItC.Next()) {
2109       IntTools_Range aRangeC =anItC.Value().GetRange(myFirstParameter, myLastParameter, nbSampleC);
2110       myRangeManager.InsertRange(aRangeC.First(), aRangeC.Last(), 1);
2111     }
2112   }
2113   ComputeNearRangeBoundaries();
2114
2115   aSurfaceData.ClearGrid();
2116
2117   return Standard_True;
2118 }
2119
2120 // ======================================================================================================================
2121 // function: TestComputeCoinside
2122 // purpose:
2123 // ======================================================================================================================
2124 Standard_Boolean IntTools_BeanFaceIntersector::TestComputeCoinside()
2125 {
2126   Standard_Real cfp = myFirstParameter, clp = myLastParameter;
2127   const Standard_Integer nbSeg = 23;
2128   Standard_Real cdp = (clp - cfp) / (Standard_Real )nbSeg;
2129
2130   Standard_Integer i = 0;
2131
2132   Standard_Real U, V;
2133
2134   if(Distance(cfp, U, V) > myCriteria)
2135     return Standard_False;
2136
2137   //
2138   ComputeRangeFromStartPoint(Standard_True, cfp, U, V);
2139   //
2140
2141   Standard_Integer aFoundIndex = myRangeManager.GetIndex(clp, Standard_False );
2142
2143   if(aFoundIndex != 0) {
2144     if(myRangeManager.Flag(aFoundIndex) == 2)
2145       return Standard_True;
2146   }
2147
2148   if(Distance(clp, U, V) > myCriteria)
2149     return Standard_False;
2150
2151   //
2152   ComputeRangeFromStartPoint(Standard_False, clp, U, V);
2153   //
2154
2155   for(i = 1; i < nbSeg; i++) {
2156     Standard_Real aPar = (cfp+((Standard_Real)i)*cdp);
2157
2158     if(Distance(aPar, U, V) > myCriteria)
2159       return Standard_False;
2160
2161     Standard_Integer aNbRanges = myRangeManager.Length();
2162     ComputeRangeFromStartPoint(Standard_False, aPar, U, V);
2163     ComputeRangeFromStartPoint(Standard_True, aPar, U, V);
2164
2165     if(aNbRanges == myRangeManager.Length()) {
2166       SetEmptyResultRange(aPar, myRangeManager);
2167     }
2168   }
2169
2170   return Standard_True;
2171 }
2172
2173 //  Modified by skv - Wed Nov  2 15:21:11 2005 Optimization Begin
2174 // ---------------------------------------------------------------------------------
2175 // static function: GetSurfaceBox
2176 // purpose:
2177 // ---------------------------------------------------------------------------------
2178 Bnd_Box GetSurfaceBox(const Handle(Geom_BSplineSurface)        &theSurf,
2179                       const Standard_Real                       theFirstU,
2180                       const Standard_Real                       theLastU,
2181                       const Standard_Real                       theFirstV,
2182                       const Standard_Real                       theLastV,
2183                       const Standard_Real                       theTolerance,
2184                             IntTools_SurfaceRangeLocalizeData  &theSurfaceData)
2185 {
2186   Bnd_Box              aTotalBox;
2187
2188   BuildBox(theSurf, theFirstU, theLastU, theFirstV, theLastV,
2189            theSurfaceData, aTotalBox);
2190
2191   aTotalBox.Enlarge(theTolerance);
2192   return aTotalBox;
2193 }
2194
2195
2196 // ---------------------------------------------------------------------------------
2197 // static function: ComputeGridPoints
2198 // purpose:
2199 // ---------------------------------------------------------------------------------
2200 void ComputeGridPoints
2201                (const Handle(Geom_BSplineSurface)       &theSurf,
2202                 const Standard_Real                      theFirstU,
2203                 const Standard_Real                      theLastU,
2204                 const Standard_Real                      theFirstV,
2205                 const Standard_Real                      theLastV,
2206                 const Standard_Real                      theTolerance,
2207                       IntTools_SurfaceRangeLocalizeData &theSurfaceData)
2208 {
2209   Standard_Integer     i;
2210   Standard_Integer     j;
2211   Standard_Integer     k;
2212   Standard_Integer     aNbSamples[2] = { theSurf->UDegree(),
2213                                          theSurf->VDegree() };
2214   Standard_Integer     aNbKnots[2]   = { theSurf->NbUKnots(),
2215                                          theSurf->NbVKnots() };
2216   TColStd_Array1OfReal aKnotsU(1, aNbKnots[0]);
2217   TColStd_Array1OfReal aKnotsV(1, aNbKnots[1]);
2218
2219   theSurf->UKnots(aKnotsU);
2220   theSurf->VKnots(aKnotsV);
2221
2222   Standard_Integer iLmI;
2223   Standard_Integer iMin[2]   = { -1, -1 };
2224   Standard_Integer iMax[2]   = { -1, -1 };
2225   Standard_Integer aNbGridPnts[2];
2226   Standard_Real    aFPar[2]  = { theFirstU, theFirstV};
2227   Standard_Real    aLPar[2]  = { theLastU,  theLastV};
2228   Standard_Real    aFpTol[2] = { aFPar[0] + theTolerance,
2229                                  aFPar[1] + theTolerance };
2230   Standard_Real    aFmTol[2] = { aFPar[0] - theTolerance,
2231                                  aFPar[1] - theTolerance };
2232   Standard_Real    aLpTol[2] = { aLPar[0] + theTolerance,
2233                                  aLPar[1] + theTolerance };
2234   Standard_Real    aLmTol[2] = { aLPar[0] - theTolerance,
2235                                  aLPar[1] - theTolerance };
2236
2237
2238   // Compute number of U and V grid points.
2239   for (j = 0; j < 2; j++) {
2240     const TColStd_Array1OfReal &aKnots = (j == 0) ? aKnotsU : aKnotsV;
2241
2242     for (i = 1; i <= aNbKnots[j] && (iMin[j] == -1 || iMax[j] == -1); i++) {
2243       if (iMin[j] == -1 && aFpTol[j] < aKnots.Value(i))
2244         iMin[j] = i - 1;
2245
2246       iLmI = aNbKnots[j] - i + 1;
2247
2248       if (iMax[j] == -1 && aLmTol[j] > aKnots.Value(iLmI))
2249         iMax[j] = iLmI + 1;
2250     }
2251
2252     // If indices are not found, return.
2253     //if (iMin[j] == -1 || iMax[j] == -1)
2254       //return;
2255     if(iMin[j] == -1)
2256       iMin[j] = 1;
2257
2258     if (iMax[j] == -1)
2259       iMax[j] = aNbKnots[j];
2260
2261     if (iMin[j] == 0)
2262       iMin[j] = 1;
2263
2264     if (iMax[j] > aNbKnots[j])
2265       iMax[j] = aNbKnots[j];
2266
2267     if (iMax[j] < iMin[j])
2268       return;
2269
2270     if (iMax[j] == iMin[j]) {
2271       iMax[j]++;
2272       iMin[j]--;
2273       if (iMin[j] == 0)
2274         iMin[j] = 1;
2275       if (iMax[j] > aNbKnots[j])
2276         iMax[j] = aNbKnots[j];
2277
2278     }
2279
2280     aNbGridPnts[j] = (iMax[j] - iMin[j])*aNbSamples[j] + 1;
2281
2282   // Setting the number of grid points.
2283     if (j == 0)
2284       theSurfaceData.SetRangeUGrid(aNbGridPnts[j]);
2285     else // j == 1
2286       theSurfaceData.SetRangeVGrid(aNbGridPnts[j]);
2287
2288     // Setting the first and last parameters.
2289     Standard_Integer iAbs    = 1;
2290     Standard_Real    aMinPar;
2291     Standard_Real    aMaxPar = (j == 0) ? theLastU : theLastV;
2292
2293     for (i = iMin[j]; i < iMax[j]; i++) {
2294       // Get the first parameter.
2295       if (i == iMin[j]) {
2296         // The first knot.
2297         if (aFmTol[j] > aKnots.Value(iMin[j]))
2298           aMinPar = aFPar[j];
2299         else
2300           aMinPar = aKnots.Value(iMin[j]);
2301       } else {
2302         aMinPar = aKnots.Value(i);
2303       }
2304
2305       // Get the last parameter.
2306       if (i == iMax[j] - 1) {
2307         // The last knot.
2308         if (aLpTol[j] < aKnots.Value(iMax[j]))
2309           aMaxPar = aLPar[j];
2310         else
2311           aMaxPar = aKnots.Value(iMax[j]);
2312       } else {
2313         aMaxPar = aKnots.Value(i + 1);
2314       }
2315
2316       // Compute grid parameters.
2317       Standard_Real aDelta = (aMaxPar - aMinPar)/aNbSamples[j];
2318
2319       for (k = 0; k < aNbSamples[j]; k++, aMinPar += aDelta) {
2320         if (j == 0)
2321           theSurfaceData.SetUParam(iAbs++, aMinPar);
2322         else
2323           theSurfaceData.SetVParam(iAbs++, aMinPar);
2324       }
2325     }
2326
2327     // Add the last parameter
2328     if (j == 0)
2329       theSurfaceData.SetUParam(iAbs++, aMaxPar);
2330     else
2331       theSurfaceData.SetVParam(iAbs++, aMaxPar);
2332   }
2333
2334   // Compute of grid points.
2335   gp_Pnt        aPnt;
2336   Standard_Real aParU;
2337   Standard_Real aParV;
2338
2339   for (i = 1; i <= aNbGridPnts[0]; i++) {
2340     aParU = theSurfaceData.GetUParam(i);
2341
2342     for (j = 1; j <= aNbGridPnts[1]; j++) {
2343       aParV = theSurfaceData.GetVParam(j);
2344
2345       theSurf->D0(aParU, aParV, aPnt);
2346       theSurfaceData.SetGridPoint(i, j, aPnt);
2347     }
2348   }
2349
2350   // Compute deflection.
2351   Standard_Real aDef = 0.;
2352 //   Standard_Real aDefLin;
2353 //   Standard_Real aParMid;
2354 //   Standard_Real aParConst;
2355 //   Standard_Real aDistPP;
2356 //   gp_Pnt        aPntMid;
2357 //   gp_Vec        aVec;
2358 //   gp_XYZ        aCoord;
2359
2360 //   // Compute DU deflection.
2361 //   for (i = 1; i < aNbGridPnts[0]; i++) {
2362 //     aParMid = 0.5*(theSurfaceData.GetUParam(i + 1) +
2363 //                 theSurfaceData.GetUParam(i));
2364
2365 //     for (j = 1; j <= aNbGridPnts[1]; j++) {
2366 //       const gp_Pnt &thePnt1 = theSurfaceData.GetGridPoint(i,     j);
2367 //       const gp_Pnt &thePnt2 = theSurfaceData.GetGridPoint(i + 1, j);
2368
2369 //       aVec.SetXYZ(thePnt2.XYZ().Subtracted(thePnt1.XYZ()));
2370 //       aDistPP = aVec.Magnitude();
2371
2372 //       if (aDistPP > theTolerance) {
2373 //      // Computation of a distance of a middle point from the line P1 - P2.
2374 //      aParConst = theSurfaceData.GetVParam(j);
2375 //      theSurf->D0(aParMid, aParConst, aPntMid);
2376 //      aCoord = aPntMid.XYZ();
2377 //      aCoord.Subtract(thePnt1.XYZ());
2378 //      aCoord.Cross (aVec.XYZ());
2379 //      aCoord.Divide(aDistPP);
2380 //      aDefLin = aCoord.Modulus();
2381
2382 //      if (aDefLin > aDef)
2383 //        aDef = aDefLin;
2384 //       }
2385 //     }
2386 //   }
2387
2388 //   // Compute DV deflection.
2389 //   for (j = 1; j < aNbGridPnts[1]; j++) {
2390 //     aParMid = 0.5*(theSurfaceData.GetVParam(j + 1) +
2391 //                 theSurfaceData.GetVParam(j));
2392
2393 //     for (i = 1; i <= aNbGridPnts[0]; i++) {
2394 //       const gp_Pnt &thePnt1 = theSurfaceData.GetGridPoint(i, j);
2395 //       const gp_Pnt &thePnt2 = theSurfaceData.GetGridPoint(i, j + 1);
2396
2397 //       aVec.SetXYZ(thePnt2.XYZ().Subtracted(thePnt1.XYZ()));
2398 //       aDistPP = aVec.Magnitude();
2399
2400 //       if (aDistPP > theTolerance) {
2401 //      // Computation of a distance of a middle point from the line P1 - P2.
2402 //      aParConst = theSurfaceData.GetUParam(i);
2403 //      theSurf->D0(aParConst, aParMid, aPntMid);
2404 //      aCoord = aPntMid.XYZ();
2405 //      aCoord.Subtract(thePnt1.XYZ());
2406 //      aCoord.Cross (aVec.XYZ());
2407 //      aCoord.Divide(aDistPP);
2408 //      aDefLin = aCoord.Modulus();
2409
2410 //      if (aDefLin > aDef)
2411 //        aDef = aDefLin;
2412 //       }
2413 //     }
2414 //   }
2415
2416   if (theTolerance > aDef)
2417     aDef = theTolerance;
2418
2419   aDef *= 2.;
2420   theSurfaceData.SetGridDeflection(aDef);
2421 }
2422
2423 // ---------------------------------------------------------------------------------
2424 // static function: BuildBox
2425 // purpose:  Compute bounding box.
2426 // ---------------------------------------------------------------------------------
2427 void BuildBox(const Handle(Geom_BSplineSurface)       &theSurf,
2428               const Standard_Real                      theFirstU,
2429               const Standard_Real                      theLastU,
2430               const Standard_Real                      theFirstV,
2431               const Standard_Real                      theLastV,
2432                     IntTools_SurfaceRangeLocalizeData &theSurfaceData,
2433                     Bnd_Box                           &theBox)
2434 {
2435   Standard_Integer i;
2436   Standard_Integer j;
2437   Standard_Integer aNbUPnts;
2438   Standard_Integer aNbVPnts;
2439   Standard_Real    aParam;
2440   gp_Pnt           aPnt;
2441
2442   theSurfaceData.SetFrame(theFirstU, theLastU, theFirstV, theLastV);
2443   aNbUPnts = theSurfaceData.GetNBUPointsInFrame();
2444   aNbVPnts = theSurfaceData.GetNBVPointsInFrame();
2445
2446   // Add corner points.
2447   theSurf->D0(theFirstU, theFirstV, aPnt);
2448   theBox.Add(aPnt);
2449   theSurf->D0(theLastU,  theFirstV, aPnt);
2450   theBox.Add(aPnt);
2451   theSurf->D0(theFirstU, theLastV, aPnt);
2452   theBox.Add(aPnt);
2453   theSurf->D0(theLastU,  theLastV, aPnt);
2454   theBox.Add(aPnt);
2455
2456   for (i = 1; i <= aNbUPnts; i++) {
2457     // Add top and bottom points.
2458     aParam = theSurfaceData.GetUParamInFrame(i);
2459     theSurf->D0(aParam, theFirstV, aPnt);
2460     theBox.Add(aPnt);
2461     theSurf->D0(aParam, theLastV, aPnt);
2462     theBox.Add(aPnt);
2463
2464     // Add internal points.
2465     for (j = 1; j <= aNbVPnts; j++) {
2466       const gp_Pnt &aGridPnt = theSurfaceData.GetPointInFrame(i, j);
2467
2468       theBox.Add(aGridPnt);
2469     }
2470   }
2471
2472   // Add left and right points.
2473   for (j = 1; j <= aNbVPnts; j++) {
2474     aParam = theSurfaceData.GetVParamInFrame(j);
2475     theSurf->D0(theFirstU, aParam, aPnt);
2476     theBox.Add(aPnt);
2477     theSurf->D0(theLastU,  aParam, aPnt);
2478     theBox.Add(aPnt);
2479   }
2480
2481   theBox.Enlarge(theSurfaceData.GetGridDeflection());
2482 }
2483 //  Modified by skv - Wed Nov  2 15:21:11 2005 Optimization End
2484
2485
2486 // ---------------------------------------------------------------------------------
2487 // static function: MergeSolutions
2488 // purpose:
2489 // ---------------------------------------------------------------------------------
2490 static void MergeSolutions(const IntTools_ListOfCurveRangeSample& theListCurveRange,
2491                            const IntTools_ListOfSurfaceRangeSample& theListSurfaceRange,
2492                            IntTools_ListOfCurveRangeSample& theListCurveRangeSort,
2493                            IntTools_ListOfSurfaceRangeSample& theListSurfaceRangeSort) {
2494
2495   IntTools_ListIteratorOfListOfCurveRangeSample anItC2;
2496   IntTools_ListIteratorOfListOfSurfaceRangeSample anItS1(theListSurfaceRange), anItS2;
2497   IntTools_MapOfSurfaceSample aMapToAvoid;
2498
2499   for(; anItS1.More(); anItS1.Next()) {
2500     const IntTools_SurfaceRangeSample& aRangeS = anItS1.Value();
2501
2502     if(aMapToAvoid.Contains(aRangeS))
2503       continue;
2504     aMapToAvoid.Add(aRangeS);
2505
2506     anItC2.Initialize(theListCurveRange);
2507     anItS2.Initialize(theListSurfaceRange);
2508
2509     for(; anItS2.More() && anItC2.More(); anItS2.Next(), anItC2.Next()) {
2510       if(aRangeS.IsEqual(anItS2.Value())) {
2511         theListCurveRangeSort.Append(anItC2.Value());
2512         theListSurfaceRangeSort.Append(anItS2.Value());
2513       }
2514     }
2515   }
2516 }
2517
2518 // ---------------------------------------------------------------------------------
2519 // static function: CheckSampling
2520 // purpose:
2521 // ---------------------------------------------------------------------------------
2522 static void CheckSampling(const IntTools_CurveRangeSample& theCurveRange,
2523                           const IntTools_SurfaceRangeSample& theSurfaceRange,
2524                           const IntTools_CurveRangeLocalizeData& theCurveData,
2525                           const IntTools_SurfaceRangeLocalizeData& theSurfaceData,
2526                           const Standard_Real DiffC,
2527                           const Standard_Real DiffU,
2528                           const Standard_Real DiffV,
2529                           Standard_Boolean& bAllowSamplingC,
2530                           Standard_Boolean& bAllowSamplingU,
2531                           Standard_Boolean& bAllowSamplingV) {
2532
2533   const Standard_Real dLimit = 1000;
2534   bAllowSamplingC = Standard_True;
2535   bAllowSamplingU = Standard_True;
2536   bAllowSamplingV = Standard_True;
2537
2538   // check
2539   if((pow((Standard_Real)theCurveData.GetNbSample(), (Standard_Real )(theCurveRange.GetDepth() + 1)) > dLimit) ||
2540      ((DiffC / theCurveData.GetNbSample()) < theCurveData.GetMinRange())) {
2541     bAllowSamplingC = Standard_False;
2542   }
2543
2544   if((pow((Standard_Real )theSurfaceData.GetNbSampleU(), (Standard_Real )(theSurfaceRange.GetDepthU() + 1)) > dLimit) ||
2545      ((DiffU / theSurfaceData.GetNbSampleU()) < theSurfaceData.GetMinRangeU())) {
2546     bAllowSamplingU = Standard_False;
2547   }
2548
2549
2550   if((pow((Standard_Real )theSurfaceData.GetNbSampleV(), (Standard_Real )(theSurfaceRange.GetDepthV() + 1)) > dLimit) ||
2551      ((DiffV / theSurfaceData.GetNbSampleV()) < theSurfaceData.GetMinRangeV())) {
2552     bAllowSamplingV = Standard_False;
2553   }
2554 }