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