src/IntTools/IntTools_BeanFaceIntersector.cxx

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