src/IntTools/IntTools_BeanFaceIntersector.cxx

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