src/IntTools/IntTools_BeanFaceIntersector.cxx

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