src/IntTools/IntTools_BeanFaceIntersector.cxx

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