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