0027087: [Regression to OCCT 6.7.1] BRepExtrema_DistShapeShape gives wrong result
[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;
917     theExtCS.Initialize(aGASurface, myUMinParameter, myUMaxParameter,
918                                     myVMinParameter, myVMaxParameter,  Tol, Tol);
919     Standard_Real first = aCurve->FirstParameter(), last = aCurve->LastParameter();
920     if (aCurve->IsPeriodic() || 
921        (anarg1 >= first - Precision::PConfusion() && anarg2 <= last + Precision::PConfusion()))
922     {
923       //Extrema_ExtCS theExtCS(aGACurve, aGASurface, Tol, Tol);
924       theExtCS.Perform(aGACurve, anarg1, anarg2);
925     }
926
927     myExtrema = theExtCS; 
928     
929     if(myExtrema.IsDone() && (myExtrema.NbExt() || myExtrema.IsParallel())) {
930       Standard_Integer anOldNbRanges = myRangeManager.Length();
931       
932       if (myExtrema.IsParallel()) {
933         
934         if(myExtrema.SquareDistance(1) < myCriteria * myCriteria) {
935           Standard_Real U1, V1, U2, V2;
936           Standard_Real adistance1 = Distance(anarg1, U1, V1);
937           Standard_Real adistance2 = Distance(anarg2, U2, V2);
938           Standard_Boolean validdistance1 = (adistance1 < myCriteria);
939           Standard_Boolean validdistance2 = (adistance2 < myCriteria);
940           
941           if (validdistance1 && validdistance2) {
942             myRangeManager.InsertRange(anarg1, anarg2, 2);
943             continue;
944           }
945           else {
946             if(validdistance1) {
947               ComputeRangeFromStartPoint(Standard_True, anarg1, U1, V1);
948             }
949             else {
950               if(validdistance2) {
951                 ComputeRangeFromStartPoint(Standard_False, anarg2, U2, V2);
952               }
953               else {
954                 Standard_Real a  = anarg1;
955                 Standard_Real b  = anarg2;
956                 Standard_Real da = adistance1;
957                 Standard_Real db = adistance2;
958                 Standard_Real asolution = a;
959                 Standard_Boolean found = Standard_False;
960                 
961                 while(((b - a) > myCurveResolution) && !found) {
962                   asolution = (a+b)*0.5;
963                   Standard_Real adist = Distance(asolution, U1, V1);
964                   
965                   if(adist < myCriteria) {
966                     found = Standard_True;
967                   }
968                   else {
969                     if(da < db) {
970                       b = asolution;
971                       db = adist;
972                     }
973                     else {
974                       a = asolution;
975                       da = adist;
976                     }
977                   }
978                 } // end while
979                 
980                 if(found) {
981                   ComputeRangeFromStartPoint(Standard_False, asolution, U1, V1);
982                   ComputeRangeFromStartPoint(Standard_True, asolution, U1, V1);
983                 }
984                 else {
985                   myRangeManager.SetFlag(i, 1);
986                 }
987               }
988             }
989           }
990         }
991         else {
992           myRangeManager.SetFlag(i, 1);
993         }
994       }
995       else {
996         Standard_Boolean solutionfound = Standard_False;
997         
998         for(Standard_Integer j = 1 ; j <= myExtrema.NbExt(); j++) {
999           
1000           if(myExtrema.SquareDistance(j) < myCriteria * myCriteria) {
1001             Extrema_POnCurv p1;
1002             Extrema_POnSurf p2;
1003             myExtrema.Points(j, p1, p2);
1004             Standard_Real U, V;
1005             p2.Parameter(U, V);
1006             
1007             Standard_Integer aNbRanges = myRangeManager.Length();
1008             ComputeRangeFromStartPoint(Standard_False, p1.Parameter(), U, V);
1009             ComputeRangeFromStartPoint(Standard_True, p1.Parameter(), U, V);
1010             solutionfound = Standard_True;
1011             
1012             if(aNbRanges == myRangeManager.Length()) {
1013               SetEmptyResultRange(p1.Parameter(), myRangeManager);
1014             }
1015           }
1016         } //end for
1017         
1018         if(!solutionfound) {
1019           myRangeManager.SetFlag(i, 1);
1020         }
1021       }
1022       Standard_Integer adifference = myRangeManager.Length() - anOldNbRanges;
1023       
1024       if(adifference > 0) {
1025         i+=adifference;
1026       }
1027     } // end if(myExtrema.IsDone() && (myExtrema.NbExt() || myExtrema.IsParallel()))
1028   }
1029 }
1030
1031 // ==================================================================================
1032 // function: ComputeNearRangeBoundaries
1033 // purpose: 
1034 // ==================================================================================
1035 void IntTools_BeanFaceIntersector::ComputeNearRangeBoundaries() 
1036 {
1037   Standard_Real U = myUMinParameter;
1038   Standard_Real V = myVMinParameter;
1039   
1040   for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1041
1042     if(myRangeManager.Flag(i) > 0)
1043       continue;
1044     
1045     if((i > 1) && (myRangeManager.Flag(i-1) > 0))
1046       continue;
1047     
1048     IntTools_Range aParamRange = myRangeManager.Range(i);
1049     
1050     if(Distance(aParamRange.First(), U, V) < myCriteria) {
1051       Standard_Integer aNbRanges = myRangeManager.Length();
1052       
1053       if(i > 1) {
1054         ComputeRangeFromStartPoint(Standard_False, aParamRange.First(), U, V, i-1);
1055       }
1056       ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), U, V, i + (myRangeManager.Length() - aNbRanges));
1057       
1058       if(aNbRanges == myRangeManager.Length()) {
1059         SetEmptyResultRange(aParamRange.First(), myRangeManager);
1060       }
1061     }
1062   }
1063   
1064   if(myRangeManager.Flag(myRangeManager.Length()) == 0) {
1065     IntTools_Range aParamRange = myRangeManager.Range(myRangeManager.Length());
1066     
1067     if(Distance(aParamRange.Last(), U, V) < myCriteria) {
1068       Standard_Integer aNbRanges = myRangeManager.Length();
1069       
1070       ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), U, V, myRangeManager.Length());
1071       
1072       if(aNbRanges == myRangeManager.Length()) {
1073         SetEmptyResultRange(aParamRange.Last(), myRangeManager);
1074       }
1075     }
1076   }
1077 }
1078
1079 // ==================================================================================
1080 // function: ComputeRangeFromStartPoint
1081 // purpose:  Compute range using start point according to parameter theParameter,
1082 //           increasing parameter on curve if ToIncreaseParameter == Standard_True or
1083 //           decreasing parameter on curve if ToIncreaseParameter == Standard_False
1084 // ==================================================================================
1085 void IntTools_BeanFaceIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
1086          const Standard_Real    theParameter,
1087          const Standard_Real    theUParameter,
1088          const Standard_Real    theVParameter) 
1089 {
1090   Standard_Integer aFoundIndex = myRangeManager.GetIndex(theParameter, ToIncreaseParameter);
1091   
1092   if(aFoundIndex == 0) {
1093     return;
1094   }
1095   
1096   ComputeRangeFromStartPoint(ToIncreaseParameter, theParameter, theUParameter, theVParameter, aFoundIndex);
1097 }
1098
1099 // ==================================================================================
1100 // function: ComputeRangeFromStartPoint
1101 // purpose:  Compute range using start point according to parameter theParameter,
1102 //           increasing parameter on curve if ToIncreaseParameter == Standard_True or
1103 //           decreasing parameter on curve if ToIncreaseParameter == Standard_False.
1104 //           theIndex indicate that theParameter belong the range number theIndex.
1105 // ==================================================================================
1106 void IntTools_BeanFaceIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
1107          const Standard_Real    theParameter,
1108          const Standard_Real    theUParameter,
1109          const Standard_Real    theVParameter,
1110          const Standard_Integer theIndex) 
1111 {
1112   if(myRangeManager.Flag(theIndex) > 0)
1113     return;
1114   
1115   Standard_Integer aValidIndex = theIndex;
1116   
1117   Standard_Real aMinDelta        = myCurveResolution * 0.5;
1118   Standard_Real aDeltaRestrictor = myLastParameter - myFirstParameter;
1119
1120   if(aMinDelta > aDeltaRestrictor)
1121     aMinDelta = aDeltaRestrictor * 0.5;
1122
1123   Standard_Real tenOfMinDelta    = aMinDelta * 10.;
1124   Standard_Real aDelta           = myCurveResolution;
1125
1126   Standard_Real aCurPar  = (ToIncreaseParameter) ? (theParameter + aDelta) : (theParameter - aDelta);
1127   Standard_Real aPrevPar = theParameter;
1128   IntTools_Range aCurrentRange = myRangeManager.Range(aValidIndex);
1129
1130   Standard_Boolean BoundaryCondition  = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1131   
1132   if(BoundaryCondition) {
1133     aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1134     BoundaryCondition = Standard_False;
1135   }
1136
1137   Standard_Integer loopcounter = 0; // neccesary as infinite loop restricter
1138   Standard_Real U = theUParameter;
1139   Standard_Real V = theVParameter;
1140   Standard_Boolean anotherSolutionFound = Standard_False;
1141
1142   Standard_Boolean isboundaryindex = Standard_False;
1143   Standard_Boolean isvalidindex = Standard_True;
1144   
1145   while((aDelta >= aMinDelta) && (loopcounter <= 10)) {
1146     Standard_Boolean pointfound = Standard_False;
1147
1148     // 
1149     gp_Pnt aPoint = myCurve.Value(aCurPar);
1150     Extrema_GenLocateExtPS anExtrema(mySurface, 1.e-10, 1.e-10);
1151     anExtrema.Perform(aPoint, U, V);
1152
1153     if(anExtrema.IsDone()) {
1154       if(anExtrema.SquareDistance() < myCriteria * myCriteria) {
1155         Extrema_POnSurf aPOnSurf = anExtrema.Point();
1156         aPOnSurf.Parameter(U, V);
1157         pointfound = Standard_True;
1158       }
1159     }
1160     else {
1161       pointfound = (Distance(aCurPar) < myCriteria);
1162     }
1163     
1164     if(pointfound) {
1165       aPrevPar = aCurPar;
1166       anotherSolutionFound = Standard_True;
1167       
1168       if(BoundaryCondition && (isboundaryindex || !isvalidindex))
1169         break;
1170     }
1171     else {
1172       aDeltaRestrictor = aDelta;
1173     }
1174     
1175     // if point found decide to increase aDelta using derivative of distance function
1176     //
1177     
1178     aDelta = (pointfound) ? (aDelta * 2.) : (aDelta * 0.5);
1179     aDelta = (aDelta < aDeltaRestrictor) ? aDelta : aDeltaRestrictor;
1180     
1181     aCurPar = (ToIncreaseParameter) ? (aPrevPar + aDelta) : (aPrevPar - aDelta);
1182     
1183     
1184     // prevent infinite loop when (aPrevPar +/- aDelta) == aPrevPar == 0.
1185     //
1186     
1187     if( aCurPar == aPrevPar )
1188       break;
1189     
1190     BoundaryCondition  = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1191     
1192     isboundaryindex = Standard_False;
1193     isvalidindex = Standard_True;
1194     
1195     if(BoundaryCondition) {
1196       isboundaryindex = ((!ToIncreaseParameter && (aValidIndex == 1)) ||
1197                          (ToIncreaseParameter && (aValidIndex == myRangeManager.Length())));
1198       
1199       if(!isboundaryindex) {
1200         
1201         if(pointfound) {
1202           Standard_Integer aFlag = (ToIncreaseParameter) ? myRangeManager.Flag(aValidIndex + 1) : myRangeManager.Flag(aValidIndex - 1);
1203           
1204           if(aFlag==0) {    
1205             aValidIndex = (ToIncreaseParameter) ? (aValidIndex + 1) : (aValidIndex - 1);
1206             aCurrentRange = myRangeManager.Range(aValidIndex);
1207             
1208             if((ToIncreaseParameter && (aCurPar > aCurrentRange.Last())) ||
1209                (!ToIncreaseParameter && (aCurPar < aCurrentRange.First()))) {
1210               aCurPar = (aCurrentRange.First() + aCurrentRange.Last()) * 0.5;
1211               aDelta*=0.5;
1212             }
1213           }
1214           else {
1215             isvalidindex = Standard_False;
1216             aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1217           }
1218         }
1219       }
1220       else {
1221         aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1222       }      
1223       
1224       if(aDelta < tenOfMinDelta) {
1225         loopcounter++;
1226       }
1227       else {
1228         loopcounter = 0;
1229       }
1230     } // if(BoundaryCondition)
1231   }
1232   
1233   if(anotherSolutionFound) {
1234     if(ToIncreaseParameter)
1235       myRangeManager.InsertRange(theParameter, aPrevPar, 2);
1236     else
1237       myRangeManager.InsertRange(aPrevPar, theParameter, 2);
1238   }
1239 }
1240
1241 // ---------------------------------------------------------------------------------
1242 // static function: SetEmptyResultRange
1243 // purpose:  
1244 // ---------------------------------------------------------------------------------
1245 static Standard_Boolean SetEmptyResultRange(const Standard_Real      theParameter, 
1246                                             IntTools_MarkedRangeSet& theMarkedRange) {
1247   
1248   const TColStd_SequenceOfInteger& anIndices = theMarkedRange.GetIndices(theParameter);
1249   Standard_Boolean add = (anIndices.Length() > 0);
1250   
1251   for(Standard_Integer k = 1; k <= anIndices.Length(); k++) {
1252     if(theMarkedRange.Flag(anIndices(k)) == 2) {
1253       add = Standard_False;
1254       break;
1255     }
1256   }
1257   
1258   if(add) {
1259     theMarkedRange.InsertRange(theParameter, theParameter, 2);
1260   }
1261   
1262   return add;
1263 }
1264
1265 // ---------------------------------------------------------------------------------
1266 // static function: TestCoinside
1267 // purpose:  
1268 // ---------------------------------------------------------------------------------
1269 // static Standard_Boolean TestClose(const Extrema_ExtPS & theExt,
1270 //                                   const Standard_Real   theDist)
1271 // {
1272 //   Standard_Boolean close = Standard_False;
1273 //   if(!theExt.IsDone() || theExt.NbExt() == 0)
1274 //     return close;
1275 //   else {
1276 //     Standard_Integer ie;
1277 //     for(ie = 1; ie <= theExt.NbExt(); ie++) {
1278 //       Standard_Real dist = theExt.Value(ie);
1279 //       if(dist <= theDist) {
1280 //         close = Standard_True;
1281 //         break;
1282 //       }
1283 //     }
1284 //   }
1285 //   return close;
1286 // }
1287
1288 // Standard_Boolean TestCoinside(const BRepAdaptor_Curve&   theCurve,
1289 //                               const BRepAdaptor_Surface& theSurface)
1290 // {
1291 //   Standard_Real cfp = theCurve.FirstParameter(), clp = theCurve.LastParameter();
1292 //   Standard_Real cdp = fabs(clp - cfp) / 23.;
1293
1294 //   Standard_Integer i = 0;
1295 //   Standard_Real tolE = theCurve.Tolerance(), tolF = theSurface.Tolerance();
1296 //   Standard_Real tolT = tolE + tolF, tolU = 1.e-9, tolV = 1.e-9;
1297 //   gp_Pnt aP;
1298
1299 //   theCurve.D0(cfp,aP);
1300 //   Extrema_ExtPS eps(aP,theSurface,tolU,tolV);
1301
1302 //   if(!TestClose(eps,tolT))
1303 //     return Standard_False;
1304
1305 //   theCurve.D0(clp,aP);
1306 //   eps.Perform(aP);
1307
1308 //   if(!TestClose(eps,tolT))
1309 //     return Standard_False;
1310
1311 //   Standard_Boolean close = Standard_True;
1312
1313 //   for(i = 1; i <= 22; i++) {
1314 //     theCurve.D0((cfp+((Standard_Real)i)*cdp),aP);
1315 //     eps.Perform(aP);
1316 //     if(!TestClose(eps,tolT)) {
1317 //       close = Standard_False;
1318 //       break;
1319 //     }
1320 //   }
1321 //   return close;
1322 // }
1323
1324 // ======================================================================================================================
1325 // function: LocalizeSolutions
1326 // purpose: 
1327 // ======================================================================================================================
1328 Standard_Boolean IntTools_BeanFaceIntersector::LocalizeSolutions(const IntTools_CurveRangeSample& theCurveRange,
1329             const Bnd_Box& theBoxCurve,
1330             const IntTools_SurfaceRangeSample& theSurfaceRange,
1331             const Bnd_Box& theBoxSurface,
1332             IntTools_CurveRangeLocalizeData& theCurveData,
1333             IntTools_SurfaceRangeLocalizeData& theSurfaceData,
1334             IntTools_ListOfCurveRangeSample& theListCurveRange,
1335             IntTools_ListOfSurfaceRangeSample& theListSurfaceRange) 
1336 {
1337   Standard_Integer tIt = 0, uIt = 0, vIt = 0;
1338   
1339   // 
1340   IntTools_CurveRangeSample aRootRangeC(0);
1341   aRootRangeC.SetDepth(0);
1342   IntTools_SurfaceRangeSample aRootRangeS(0, 0, 0, 0);
1343
1344   Bnd_Box aMainBoxC = theBoxCurve;
1345   Bnd_Box aMainBoxS = theBoxSurface;
1346   Standard_Boolean bMainBoxFoundS = Standard_False;
1347   Standard_Boolean bMainBoxFoundC = Standard_False;
1348   //
1349   IntTools_ListOfCurveRangeSample aListCurveRangeFound;
1350   IntTools_ListOfSurfaceRangeSample aListSurfaceRangeFound;
1351
1352
1353   IntTools_Range aRangeC = theCurveRange.GetRange(myFirstParameter, myLastParameter, theCurveData.GetNbSample());
1354   Standard_Real localdiffC = (aRangeC.Last() - aRangeC.First()) / theCurveData.GetNbSample();
1355
1356   Standard_Real aCurPar = aRangeC.First();
1357   Standard_Real aPrevPar = aRangeC.First();
1358   Standard_Integer aCurIndexInit = theCurveRange.GetRangeIndexDeeper(theCurveData.GetNbSample());
1359
1360
1361   TColStd_ListOfInteger aListCToAvoid;
1362   Standard_Boolean bGlobalCheckDone = Standard_False;
1363   //
1364
1365   //
1366
1367   Standard_Integer aCurIndexU = theSurfaceRange.GetRangeIndexUDeeper(theSurfaceData.GetNbSampleU());
1368
1369   Standard_Integer aCurIndexVInit = theSurfaceRange.GetRangeIndexVDeeper(theSurfaceData.GetNbSampleV());
1370   IntTools_Range aRangeV = theSurfaceRange.GetRangeV(myVMinParameter, myVMaxParameter, theSurfaceData.GetNbSampleV());
1371
1372   //
1373   IntTools_Range aRangeU = theSurfaceRange.GetRangeU(myUMinParameter, myUMaxParameter, theSurfaceData.GetNbSampleU());
1374   Standard_Real aCurParU = aRangeU.First();
1375   Standard_Real aLocalDiffU = (aRangeU.Last() - aRangeU.First()) / theSurfaceData.GetNbSampleU();
1376
1377   Standard_Real aPrevParU = aCurParU;
1378   Standard_Real aLocalDiffV = (aRangeV.Last() - aRangeV.First()) / theSurfaceData.GetNbSampleV();
1379
1380
1381   // ranges check.begin
1382   Standard_Boolean bAllowSamplingC = Standard_True;
1383   Standard_Boolean bAllowSamplingU = Standard_True;
1384   Standard_Boolean bAllowSamplingV = Standard_True;
1385
1386   // check
1387   CheckSampling(theCurveRange, theSurfaceRange, theCurveData, theSurfaceData,
1388                 localdiffC, aLocalDiffU, aLocalDiffV,
1389                 bAllowSamplingC, bAllowSamplingU, bAllowSamplingV);
1390   //
1391   
1392   if(!bAllowSamplingC && !bAllowSamplingU && !bAllowSamplingV) {
1393     theListCurveRange.Append(theCurveRange);
1394     theListSurfaceRange.Append(theSurfaceRange);
1395     return Standard_True;
1396   }
1397   // ranges check.end
1398   
1399   // init template. begin
1400   IntTools_CurveRangeSample aNewRangeCTemplate;
1401
1402   if(!bAllowSamplingC) {
1403     aNewRangeCTemplate = theCurveRange;
1404     aCurIndexInit = theCurveRange.GetRangeIndex();
1405     localdiffC = (aRangeC.Last() - aRangeC.First());
1406   }
1407   else {
1408     aNewRangeCTemplate.SetDepth(theCurveRange.GetDepth() + 1);
1409     aNewRangeCTemplate.SetRangeIndex(aCurIndexInit);
1410   }
1411
1412   IntTools_SurfaceRangeSample aNewRangeSTemplate = theSurfaceRange;
1413
1414   if(bAllowSamplingU) {
1415     aNewRangeSTemplate.SetDepthU(theSurfaceRange.GetDepthU() + 1);
1416   }
1417   else {
1418     aCurIndexU = aNewRangeSTemplate.GetIndexU();
1419     aLocalDiffU = aRangeU.Last() - aRangeU.First();
1420   }
1421
1422   if(bAllowSamplingV) {
1423     aNewRangeSTemplate.SetDepthV(theSurfaceRange.GetDepthV() + 1);
1424   }
1425   else {
1426     aCurIndexVInit = theSurfaceRange.GetIndexV();
1427     aLocalDiffV = aRangeV.Last() - aRangeV.First();
1428   }
1429   // init template. end  
1430
1431
1432   Standard_Boolean bHasOut = Standard_False;
1433   const Standard_Integer nbU = (bAllowSamplingU) ? theSurfaceData.GetNbSampleU() : 1;
1434   const Standard_Integer nbV = (bAllowSamplingV) ? theSurfaceData.GetNbSampleV() : 1;
1435   const Standard_Integer nbC = (bAllowSamplingC) ? theCurveData.GetNbSample() : 1;
1436
1437   for(uIt = 1; uIt <= nbU; uIt++, aCurIndexU++, aPrevParU = aCurParU) {
1438     aCurParU += aLocalDiffU;
1439     
1440
1441     Standard_Real aCurParV = aRangeV.First();
1442     Standard_Real aPrevParV = aCurParV;
1443     Standard_Integer aCurIndexV = aCurIndexVInit;
1444
1445     Standard_Boolean bHasOutV = Standard_False;
1446
1447     // ///////
1448     for(vIt = 1; vIt <= nbV; vIt++, aCurIndexV++, aPrevParV = aCurParV) {
1449
1450       aCurParV += aLocalDiffV;
1451
1452
1453       // //////////////
1454       //
1455       IntTools_SurfaceRangeSample aNewRangeS = aNewRangeSTemplate;
1456
1457       if(bAllowSamplingU) {
1458         aNewRangeS.SetIndexU(aCurIndexU);
1459       }
1460       
1461       if(bAllowSamplingV) {
1462         aNewRangeS.SetIndexV(aCurIndexV);
1463       }
1464       
1465       if(theSurfaceData.IsRangeOut(aNewRangeS)) {
1466         bHasOutV = Standard_True;
1467         continue;
1468       }
1469       
1470       // ///////
1471       
1472       Bnd_Box aBoxS;
1473       
1474       if(!theSurfaceData.FindBox(aNewRangeS, aBoxS)) {
1475         
1476         if(mySurface.GetType() == GeomAbs_BSplineSurface) {
1477           //    if(Standard_False ) {
1478           Handle(Geom_BSplineSurface) aSurfBspl = Handle(Geom_BSplineSurface)::DownCast(myTrsfSurface);
1479           aBoxS = GetSurfaceBox(aSurfBspl, aPrevParU, aCurParU, aPrevParV, aCurParV, myCriteria, theSurfaceData);
1480         }
1481         else {
1482           BndLib_AddSurface::Add(mySurface, aPrevParU, aCurParU, aPrevParV, aCurParV, myCriteria, aBoxS);
1483           }
1484         //      Bnd_Box aMainBoxC;
1485         
1486         if(!bMainBoxFoundC && theCurveData.FindBox(aRootRangeC, aMainBoxC)) {
1487           bMainBoxFoundC = Standard_True;
1488         }
1489         
1490         if(aBoxS.IsOut(aMainBoxC)) {
1491           theSurfaceData.AddOutRange(aNewRangeS);
1492           bHasOutV = Standard_True;
1493           continue;
1494         }
1495         //      }
1496         theSurfaceData.AddBox(aNewRangeS, aBoxS);
1497       }
1498       
1499       if(aBoxS.IsOut(theBoxCurve)) {
1500         bHasOutV = Standard_True;
1501         continue;
1502       }
1503       
1504       IntTools_ListOfBox aListOfBox;
1505       TColStd_ListOfInteger aListOfIndex;
1506       
1507       Standard_Boolean bHasOutC = Standard_False;
1508       Standard_Integer aCurIndex = aCurIndexInit;
1509       
1510       // ////////////////////////////
1511       aCurPar = aRangeC.First();
1512       aPrevPar = aRangeC.First();
1513       IntTools_CurveRangeSample aCurRangeC = aNewRangeCTemplate;
1514       
1515       for (tIt = 1; tIt <= nbC; tIt++, aCurIndex++, aPrevPar = aCurPar) {
1516         
1517         aCurPar += localdiffC;
1518         
1519         // ignore already computed. begin
1520         Standard_Boolean bFound = Standard_False;
1521         TColStd_ListIteratorOfListOfInteger anItToAvoid(aListCToAvoid);
1522
1523         for(; anItToAvoid.More(); anItToAvoid.Next()) {
1524           if(tIt == anItToAvoid.Value()) {
1525             bFound = Standard_True;
1526             break;
1527           }
1528         }
1529         
1530         if(!bFound) {
1531           if(bAllowSamplingC) {
1532             aCurRangeC.SetRangeIndex(aCurIndex);
1533           }
1534           bFound = theCurveData.IsRangeOut(aCurRangeC);
1535         }
1536         
1537         if(bFound) {
1538           bHasOutC = Standard_True;
1539           continue;
1540         }
1541         // ignore already computed. end
1542         
1543         // compute Box
1544         Bnd_Box aBoxC;
1545         
1546         if(!theCurveData.FindBox(aCurRangeC, aBoxC)) {
1547           BndLib_Add3dCurve::Add(myCurve, aPrevPar, aCurPar, myCriteria, aBoxC);
1548             
1549             //   Bnd_Box aMainBoxS;
1550             
1551             if(!bMainBoxFoundS && theSurfaceData.FindBox(aRootRangeS, aMainBoxS)) {
1552               bMainBoxFoundS = Standard_True;
1553             }
1554             if(aBoxC.IsOut(aMainBoxS)) {
1555               theCurveData.AddOutRange(aCurRangeC);
1556               bHasOutC = Standard_True;
1557               continue;
1558             }
1559             //   }
1560             theCurveData.AddBox(aCurRangeC, aBoxC);
1561           }
1562         
1563         if(!bGlobalCheckDone && aBoxC.IsOut(theBoxSurface)) {
1564           aListCToAvoid.Append(tIt);
1565           bHasOutC = Standard_True;
1566           continue;
1567         }
1568         
1569         if(aBoxC.IsOut(aBoxS)) {
1570           bHasOutV = Standard_True;
1571           bHasOutC = Standard_True;
1572           continue;
1573         }
1574         //
1575         
1576         aListOfIndex.Append(tIt);
1577         aListOfBox.Append(aBoxC);
1578       } // end for(tIt...)
1579       
1580       bGlobalCheckDone = Standard_True;
1581       
1582       if(bHasOutC) {
1583         bHasOutV = Standard_True;
1584       }
1585       
1586       // //////////////
1587       //
1588       
1589       IntTools_CurveRangeSample aNewRangeC = aNewRangeCTemplate;
1590       
1591       aCurIndex = aCurIndexInit;
1592       TColStd_ListIteratorOfListOfInteger anItI(aListOfIndex);
1593       IntTools_ListIteratorOfListOfBox anItBox(aListOfBox);
1594       Standard_Boolean bUseOldC = Standard_False;
1595       Standard_Boolean bUseOldS = Standard_False;
1596       Standard_Boolean bCheckSize = !bHasOutC;
1597       
1598       for(; anItI.More() && anItBox.More(); anItI.Next(), anItBox.Next()) {
1599         aCurIndex = aCurIndexInit + anItI.Value() - 1;
1600
1601         bUseOldS = Standard_False;
1602         
1603         if(bAllowSamplingC) {
1604           aNewRangeC.SetRangeIndex(aCurIndex);
1605         }
1606         
1607         
1608         if(bCheckSize) {
1609           
1610           if((theCurveRange.GetDepth() == 0) ||
1611              (theSurfaceRange.GetDepthU() == 0) ||
1612              (theSurfaceRange.GetDepthV() == 0)) {
1613             bHasOutC = Standard_True;
1614             bHasOutV = Standard_True;
1615           }
1616           else if((theCurveRange.GetDepth() < 4) &&
1617                   (theSurfaceRange.GetDepthU() < 4) &&
1618                   (theSurfaceRange.GetDepthV() < 4)) {
1619             Bnd_Box aBoxC = anItBox.Value();
1620             
1621             if(!aBoxC.IsWhole() && !aBoxS.IsWhole()) {
1622               Standard_Real aDiagC = aBoxC.SquareExtent();
1623               Standard_Real aDiagS = aBoxS.SquareExtent();
1624               
1625               if(aDiagC < aDiagS) {
1626                 if((aDiagC * 10.) < aDiagS) {
1627                   bUseOldC = Standard_True;
1628                   bHasOutC = Standard_True;
1629                   bHasOutV = Standard_True;
1630                   break;
1631                 }
1632               }
1633               else {
1634                 if((aDiagS * 10.) < aDiagC) {
1635                   bUseOldS = Standard_True;
1636                   bHasOutC = Standard_True;
1637                   bHasOutV = Standard_True;
1638                 }
1639               }
1640             }
1641           }
1642         }
1643         
1644         
1645         if(!bHasOutC) {
1646           aListCurveRangeFound.Append(aNewRangeC);
1647           aListSurfaceRangeFound.Append(aNewRangeS);
1648         }
1649         else {
1650           
1651           //   if(bUseOldS || bAllowSamplingU || bAllowSamplingV) {
1652           //     theSurfaceData.AddBox(aNewRangeS, aBoxS);
1653           //   }
1654           
1655           if(bUseOldS && aNewRangeC.IsEqual(theCurveRange)) {
1656             return Standard_False;
1657           }
1658           
1659           if(!LocalizeSolutions(aNewRangeC, anItBox.Value(), 
1660                                 ((bUseOldS) ? theSurfaceRange : aNewRangeS), 
1661                                 ((bUseOldS) ? theBoxSurface : aBoxS),
1662                                 theCurveData, theSurfaceData,
1663                                 theListCurveRange, theListSurfaceRange))
1664             return Standard_False;
1665         }
1666       }
1667       // end (tIt...)
1668       aListOfIndex.Clear();
1669       aListOfBox.Clear();
1670       
1671       if(bHasOutV) {
1672         //      theSurfaceData.AddBox(aNewRangeS, aBoxS);
1673         
1674         if(bUseOldC && bAllowSamplingC && (bAllowSamplingU || bAllowSamplingV)) {
1675           if(!LocalizeSolutions(theCurveRange, theBoxCurve,
1676                                 aNewRangeS, aBoxS, 
1677                                 theCurveData, theSurfaceData,
1678                                 theListCurveRange, theListSurfaceRange))
1679             return Standard_False;
1680         }
1681       }
1682     } // end for (vIt...)
1683     
1684     if(bHasOutV) {
1685       bHasOut = Standard_True;
1686     }
1687   }
1688
1689   if(!bHasOut) {
1690     theListCurveRange.Append(theCurveRange);
1691     theListSurfaceRange.Append(theSurfaceRange);    
1692   }
1693   else {
1694     IntTools_ListIteratorOfListOfCurveRangeSample anIt1(aListCurveRangeFound);
1695     IntTools_ListIteratorOfListOfSurfaceRangeSample anIt2(aListSurfaceRangeFound);
1696
1697     for(; anIt1.More() && anIt2.More(); anIt1.Next(), anIt2.Next()) {
1698       theListCurveRange.Append(anIt1.Value());
1699       theListSurfaceRange.Append(anIt2.Value());
1700     }
1701   }
1702   return Standard_True;
1703 }
1704
1705
1706 // ======================================================================================================================
1707 // function: ComputeLocalized
1708 // purpose: 
1709 // ======================================================================================================================
1710 Standard_Boolean IntTools_BeanFaceIntersector::ComputeLocalized() {
1711   Standard_Real Tol = Precision::PConfusion();
1712   
1713   IntTools_SurfaceRangeSample aSurfaceRange(0, 0, 0, 0);
1714   Standard_Real dMinU = 10. * Precision::PConfusion();
1715   Standard_Real dMinV = dMinU;
1716   IntTools_SurfaceRangeLocalizeData aSurfaceDataInit(3, 3, dMinU, dMinV);
1717   IntTools_SurfaceRangeLocalizeData& aSurfaceData = myContext->SurfaceData(mySurface.Face());
1718   aSurfaceData.RemoveRangeOutAll();
1719   aSurfaceData.ClearGrid();
1720   
1721   Bnd_Box FBox;
1722   Standard_Boolean bFBoxFound = aSurfaceData.FindBox(aSurfaceRange, FBox);
1723   
1724   if(mySurface.GetType() == GeomAbs_BSplineSurface) {
1725     Handle(Geom_BSplineSurface) aSurfBspl = Handle(Geom_BSplineSurface)::DownCast(myTrsfSurface);
1726     
1727     ComputeGridPoints(aSurfBspl, myUMinParameter, myUMaxParameter,
1728                       myVMinParameter, myVMaxParameter, myFaceTolerance,
1729                       aSurfaceData);
1730     
1731     if(!bFBoxFound) {
1732       FBox = GetSurfaceBox(aSurfBspl, myUMinParameter, myUMaxParameter,
1733                            myVMinParameter, myVMaxParameter, myCriteria,
1734                            aSurfaceData);
1735       aSurfaceData.AddBox(aSurfaceRange, FBox);
1736     }
1737     
1738   } else if(!bFBoxFound) {
1739     
1740     BndLib_AddSurface::Add(mySurface, myUMinParameter, myUMaxParameter, myVMinParameter, myVMaxParameter, myFaceTolerance, FBox);
1741       aSurfaceData.AddBox(aSurfaceRange, FBox);
1742     }
1743   
1744   Bnd_Box EBox;
1745   
1746   BndLib_Add3dCurve::Add(myCurve.Trim(myFirstParameter, myLastParameter, Precision::PConfusion())->Curve(), myBeanTolerance, EBox);
1747   
1748   if(EBox.IsOut(FBox)) {
1749     for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1750       myRangeManager.SetFlag(i, 1);
1751     }
1752     aSurfaceData.ClearGrid();
1753
1754     return Standard_True;
1755   }
1756   
1757   IntTools_ListOfCurveRangeSample aListCurveRange;
1758   IntTools_ListOfSurfaceRangeSample aListSurfaceRange;
1759   
1760   IntTools_CurveRangeSample aCurveRange(0);
1761   aCurveRange.SetDepth(0);
1762   Standard_Integer nbSampleC = 3;
1763   Standard_Integer nbSampleU = aSurfaceData.GetNbSampleU();
1764   Standard_Integer nbSampleV = aSurfaceData.GetNbSampleV();
1765   Standard_Real dMinC = 10. * myCurveResolution;
1766   IntTools_ListOfCurveRangeSample aListOut;
1767   
1768   // check
1769   Standard_Boolean bAllowSamplingC = Standard_True;
1770   Standard_Boolean bAllowSamplingU = Standard_True;
1771   Standard_Boolean bAllowSamplingV = Standard_True;
1772   IntTools_CurveRangeLocalizeData aCurveDataTmp(nbSampleC, dMinC);
1773   IntTools_SurfaceRangeLocalizeData aSurfaceDataTmp(nbSampleU, nbSampleV, dMinU, dMinV);
1774   
1775   CheckSampling(aCurveRange, aSurfaceRange, aCurveDataTmp, aSurfaceDataTmp,
1776                 myLastParameter - myFirstParameter,
1777                 myUMaxParameter - myUMinParameter,
1778                 myVMaxParameter - myVMinParameter,
1779                 bAllowSamplingC, bAllowSamplingU, bAllowSamplingV);
1780   
1781   
1782   {
1783     IntTools_CurveRangeLocalizeData aCurveData(nbSampleC, dMinC);
1784     
1785     aCurveData.AddBox(aCurveRange, EBox);
1786     
1787     if(!LocalizeSolutions(aCurveRange, EBox, aSurfaceRange, FBox, 
1788                           aCurveData, aSurfaceData,
1789                           aListCurveRange, aListSurfaceRange)) {
1790       aSurfaceData.ClearGrid();
1791       
1792       return Standard_False;
1793     }
1794     
1795     IntTools_ListOfCurveRangeSample aListCurveRangeSort;
1796     IntTools_ListOfSurfaceRangeSample aListSurfaceRangeSort;
1797     
1798     MergeSolutions(aListCurveRange, aListSurfaceRange, aListCurveRangeSort, aListSurfaceRangeSort);
1799     
1800     IntTools_ListIteratorOfListOfCurveRangeSample anItC(aListCurveRangeSort);
1801     IntTools_ListIteratorOfListOfSurfaceRangeSample anItS(aListSurfaceRangeSort);
1802     IntTools_SurfaceRangeSample aRangeSPrev;
1803     
1804     Extrema_GenExtCS anExtremaGen;
1805     
1806     for(; anItC.More() && anItS.More(); anItC.Next(), anItS.Next()) {
1807       
1808       IntTools_Range aRangeC(myFirstParameter, myLastParameter);
1809
1810       if(bAllowSamplingC) 
1811         aRangeC = anItC.Value().GetRange(myFirstParameter, myLastParameter, nbSampleC);
1812       
1813       IntTools_Range aRangeU(myUMinParameter, myUMaxParameter);
1814
1815       if(bAllowSamplingU) 
1816         aRangeU = anItS.Value().GetRangeU(myUMinParameter, myUMaxParameter, nbSampleU);
1817       
1818       IntTools_Range aRangeV(myVMinParameter, myVMaxParameter);
1819       
1820       if(bAllowSamplingV) 
1821         aRangeV = anItS.Value().GetRangeV(myVMinParameter, myVMaxParameter, nbSampleV);
1822       
1823       Standard_Real anarg1 = aRangeC.First(), anarg2 = aRangeC.Last();
1824       
1825       Standard_Boolean bFound = Standard_False;
1826       
1827       Standard_Integer nMinIndex = myRangeManager.Length();
1828       Standard_Integer nMaxIndex = -1;
1829       const TColStd_SequenceOfInteger& anInds1 = myRangeManager.GetIndices(anarg1);
1830       Standard_Integer indIt = 1;
1831
1832       for(indIt = 1 ; indIt <= anInds1.Length(); indIt++) {
1833         Standard_Integer nIndex = anInds1.Value(indIt);
1834         nMinIndex = (nMinIndex > nIndex) ? nIndex : nMinIndex;
1835         nMaxIndex = (nMaxIndex < nIndex) ? nIndex : nMaxIndex;
1836       }
1837       
1838       for(indIt = nMinIndex ; indIt <= nMaxIndex; indIt++) {
1839         if(myRangeManager.Flag(indIt) == 2) {
1840           bFound = Standard_True;
1841   break;
1842         }
1843       }
1844       
1845       if(bFound)
1846         continue;
1847       nMinIndex = (nMaxIndex >= 0) ? nMaxIndex : nMinIndex;
1848       const TColStd_SequenceOfInteger& anInds2 = myRangeManager.GetIndices(anarg2);
1849       
1850       for(indIt = 1 ; indIt <= anInds2.Length(); indIt++) {
1851         Standard_Integer nIndex = anInds2.Value(indIt);
1852         nMinIndex = (nMinIndex > nIndex) ? nIndex : nMinIndex;
1853         nMaxIndex = (nMaxIndex < nIndex) ? nIndex : nMaxIndex;
1854       }
1855
1856       for(indIt = nMinIndex ; indIt <= nMaxIndex; indIt++) {
1857         if(myRangeManager.Flag(indIt) == 2) {
1858           bFound = Standard_True;
1859           break;
1860         }
1861       }
1862       
1863       if(bFound)
1864         continue;
1865       
1866       Standard_Real parUF = aRangeU.First(), parUL = aRangeU.Last();
1867       Standard_Real parVF = aRangeV.First(), parVL = aRangeV.Last();
1868       
1869       if(aRangeSPrev.IsEqual(anItS.Value())) {
1870         anExtremaGen.Perform(myCurve, 10, anarg1, anarg2, Tol);
1871       }
1872       else {
1873         anExtremaGen.Initialize(mySurface, 10, 10, parUF, parUL, parVF, parVL, Tol);
1874         anExtremaGen.Perform(myCurve, 10, anarg1, anarg2, Tol);
1875       }
1876       
1877       if(anExtremaGen.IsDone() && (anExtremaGen.NbExt() > 0)) {
1878         
1879         for(Standard_Integer j = 1 ; j <= anExtremaGen.NbExt(); j++) {
1880
1881           if(anExtremaGen.SquareDistance(j) < myCriteria * myCriteria) {
1882             
1883             Extrema_POnCurv p1;
1884             Extrema_POnSurf p2;
1885             p1 = anExtremaGen.PointOnCurve(j);
1886             p2 = anExtremaGen.PointOnSurface(j);
1887             Standard_Real U, V, T;
1888             T = p1.Parameter();
1889             p2.Parameter(U, V);
1890             
1891             if (myCurve.IsPeriodic())
1892               T = ElCLib::InPeriod(T, anarg1, anarg1 + myCurve.Period());
1893             if (mySurface.IsUPeriodic())
1894               U = ElCLib::InPeriod(U, parUF, parUF + mySurface.UPeriod());
1895             if (mySurface.IsVPeriodic())
1896               V = ElCLib::InPeriod(V, parVF, parVF + mySurface.VPeriod());
1897             
1898             //To avoid occasional going out of boundaries because of numerical
1899             //problem
1900             if(U < myUMinParameter) U = myUMinParameter;
1901             if(U > myUMaxParameter) U = myUMaxParameter;
1902             if(V < myVMinParameter) V = myVMinParameter;
1903             if(V > myVMaxParameter) V = myVMaxParameter;
1904             
1905             Standard_Integer aNbRanges = myRangeManager.Length();
1906             ComputeRangeFromStartPoint(Standard_False, T, U, V);
1907             ComputeRangeFromStartPoint(Standard_True, T, U, V);
1908             
1909             if(aNbRanges == myRangeManager.Length()) {
1910               SetEmptyResultRange(T, myRangeManager);
1911             }
1912           }
1913         } //end for
1914       }
1915       else {
1916         myRangeManager.InsertRange(anarg1, anarg2, 0);
1917       }
1918       
1919       aRangeSPrev = anItS.Value();
1920     }
1921     
1922     //
1923     aCurveData.ListRangeOut(aListOut);
1924   }
1925   
1926   //
1927   if(bAllowSamplingC) {
1928     IntTools_ListIteratorOfListOfCurveRangeSample anItC(aListOut);
1929     
1930     for(; anItC.More(); anItC.Next()) {
1931       IntTools_Range aRangeC =anItC.Value().GetRange(myFirstParameter, myLastParameter, nbSampleC);
1932       myRangeManager.InsertRange(aRangeC.First(), aRangeC.Last(), 1);
1933     }
1934   }
1935   ComputeNearRangeBoundaries();
1936   
1937   aSurfaceData.ClearGrid();
1938
1939   return Standard_True;
1940 }
1941
1942 // ======================================================================================================================
1943 // function: TestComputeCoinside
1944 // purpose: 
1945 // ======================================================================================================================
1946 Standard_Boolean IntTools_BeanFaceIntersector::TestComputeCoinside()
1947 {
1948   Standard_Real cfp = myFirstParameter, clp = myLastParameter;
1949   const Standard_Integer nbSeg = 23;
1950   Standard_Real cdp = (clp - cfp) / (Standard_Real )nbSeg;
1951
1952   Standard_Integer i = 0;
1953
1954   Standard_Real U, V;
1955
1956   if(Distance(cfp, U, V) > myCriteria)
1957     return Standard_False;
1958
1959   //
1960   ComputeRangeFromStartPoint(Standard_True, cfp, U, V);
1961   //
1962
1963   Standard_Integer aFoundIndex = myRangeManager.GetIndex(clp, Standard_False );
1964
1965   if(aFoundIndex != 0) {
1966     if(myRangeManager.Flag(aFoundIndex) == 2)
1967       return Standard_True;
1968   }
1969
1970   if(Distance(clp, U, V) > myCriteria)
1971     return Standard_False;
1972
1973   //
1974   ComputeRangeFromStartPoint(Standard_False, clp, U, V);
1975   //
1976
1977   for(i = 1; i < nbSeg; i++) {
1978     Standard_Real aPar = (cfp+((Standard_Real)i)*cdp);
1979
1980     if(Distance(aPar, U, V) > myCriteria) 
1981       return Standard_False;
1982
1983     Standard_Integer aNbRanges = myRangeManager.Length();
1984     ComputeRangeFromStartPoint(Standard_False, aPar, U, V);
1985     ComputeRangeFromStartPoint(Standard_True, aPar, U, V);
1986
1987     if(aNbRanges == myRangeManager.Length()) {
1988       SetEmptyResultRange(aPar, myRangeManager);
1989     }
1990   }
1991
1992   return Standard_True;
1993 }
1994
1995 //  Modified by skv - Wed Nov  2 15:21:11 2005 Optimization Begin
1996 // ---------------------------------------------------------------------------------
1997 // static function: GetSurfaceBox
1998 // purpose:  
1999 // ---------------------------------------------------------------------------------
2000 Bnd_Box GetSurfaceBox(const Handle(Geom_BSplineSurface)        &theSurf,
2001                       const Standard_Real                       theFirstU,
2002                       const Standard_Real                       theLastU,
2003                       const Standard_Real                       theFirstV,
2004                       const Standard_Real                       theLastV,
2005                       const Standard_Real                       theTolerance,
2006                       IntTools_SurfaceRangeLocalizeData  &theSurfaceData)
2007 {
2008   Bnd_Box              aTotalBox;
2009   
2010   BuildBox(theSurf, theFirstU, theLastU, theFirstV, theLastV,
2011            theSurfaceData, aTotalBox);
2012
2013   aTotalBox.Enlarge(theTolerance);
2014   return aTotalBox;
2015 }
2016
2017
2018 // ---------------------------------------------------------------------------------
2019 // static function: ComputeGridPoints
2020 // purpose:  
2021 // ---------------------------------------------------------------------------------
2022 void ComputeGridPoints
2023   (const Handle(Geom_BSplineSurface)       &theSurf,
2024    const Standard_Real                      theFirstU,
2025    const Standard_Real                      theLastU,
2026    const Standard_Real                      theFirstV,
2027    const Standard_Real                      theLastV,
2028    const Standard_Real                      theTolerance,
2029    IntTools_SurfaceRangeLocalizeData &theSurfaceData)
2030 {
2031   Standard_Integer     i;
2032   Standard_Integer     j;
2033   Standard_Integer     k;
2034   Standard_Integer     aNbSamples[2] = { theSurf->UDegree(),
2035                                          theSurf->VDegree() };
2036   Standard_Integer     aNbKnots[2]   = { theSurf->NbUKnots(),
2037                                          theSurf->NbVKnots() };
2038   TColStd_Array1OfReal aKnotsU(1, aNbKnots[0]);
2039   TColStd_Array1OfReal aKnotsV(1, aNbKnots[1]);
2040
2041   theSurf->UKnots(aKnotsU);
2042   theSurf->VKnots(aKnotsV);
2043
2044   Standard_Integer iLmI;
2045   Standard_Integer iMin[2]   = { -1, -1 };
2046   Standard_Integer iMax[2]   = { -1, -1 };
2047   Standard_Integer aNbGridPnts[2];
2048   Standard_Real    aFPar[2]  = { theFirstU, theFirstV};
2049   Standard_Real    aLPar[2]  = { theLastU,  theLastV};
2050   Standard_Real    aFpTol[2] = { aFPar[0] + theTolerance,
2051                                  aFPar[1] + theTolerance };
2052   Standard_Real    aFmTol[2] = { aFPar[0] - theTolerance,
2053                                  aFPar[1] - theTolerance };
2054   Standard_Real    aLpTol[2] = { aLPar[0] + theTolerance,
2055                                  aLPar[1] + theTolerance };
2056   Standard_Real    aLmTol[2] = { aLPar[0] - theTolerance,
2057                                  aLPar[1] - theTolerance };
2058   
2059
2060   // Compute number of U and V grid points.
2061   for (j = 0; j < 2; j++) {
2062     const TColStd_Array1OfReal &aKnots = (j == 0) ? aKnotsU : aKnotsV;
2063     
2064     for (i = 1; i <= aNbKnots[j] && (iMin[j] == -1 || iMax[j] == -1); i++) {
2065       if (iMin[j] == -1 && aFpTol[j] < aKnots.Value(i))
2066         iMin[j] = i - 1;
2067       
2068       iLmI = aNbKnots[j] - i + 1;
2069       
2070       if (iMax[j] == -1 && aLmTol[j] > aKnots.Value(iLmI))
2071         iMax[j] = iLmI + 1;
2072     }
2073     
2074     // If indices are not found, return.
2075     //if (iMin[j] == -1 || iMax[j] == -1)
2076       //return;
2077     if(iMin[j] == -1)
2078       iMin[j] = 1;
2079
2080     if (iMax[j] == -1)
2081       iMax[j] = aNbKnots[j];
2082
2083     if (iMin[j] == 0)
2084       iMin[j] = 1;
2085
2086     if (iMax[j] > aNbKnots[j])
2087       iMax[j] = aNbKnots[j];
2088
2089     if (iMax[j] < iMin[j])
2090       return;
2091
2092     if (iMax[j] == iMin[j]) {
2093       iMax[j]++;
2094       iMin[j]--;
2095       if (iMin[j] == 0)
2096         iMin[j] = 1;
2097       if (iMax[j] > aNbKnots[j])
2098         iMax[j] = aNbKnots[j];
2099
2100     }
2101
2102     aNbGridPnts[j] = (iMax[j] - iMin[j])*aNbSamples[j] + 1;
2103
2104   // Setting the number of grid points.
2105     if (j == 0)
2106       theSurfaceData.SetRangeUGrid(aNbGridPnts[j]);
2107     else // j == 1
2108       theSurfaceData.SetRangeVGrid(aNbGridPnts[j]);
2109     
2110     // Setting the first and last parameters.
2111     Standard_Integer iAbs    = 1;
2112     Standard_Real    aMinPar;
2113     Standard_Real    aMaxPar = (j == 0) ? theLastU : theLastV;
2114     
2115     for (i = iMin[j]; i < iMax[j]; i++) {
2116       // Get the first parameter.
2117       if (i == iMin[j]) {
2118         // The first knot.
2119         if (aFmTol[j] > aKnots.Value(iMin[j]))
2120           aMinPar = aFPar[j];
2121         else
2122           aMinPar = aKnots.Value(iMin[j]);
2123       } else {
2124         aMinPar = aKnots.Value(i);
2125       }
2126       
2127       // Get the last parameter.
2128       if (i == iMax[j] - 1) {
2129         // The last knot.
2130         if (aLpTol[j] < aKnots.Value(iMax[j]))
2131           aMaxPar = aLPar[j];
2132         else
2133           aMaxPar = aKnots.Value(iMax[j]);
2134       } else {
2135         aMaxPar = aKnots.Value(i + 1);
2136       }
2137       
2138       // Compute grid parameters.
2139       Standard_Real aDelta = (aMaxPar - aMinPar)/aNbSamples[j];
2140       
2141       for (k = 0; k < aNbSamples[j]; k++, aMinPar += aDelta) {
2142         if (j == 0)
2143           theSurfaceData.SetUParam(iAbs++, aMinPar);
2144         else
2145           theSurfaceData.SetVParam(iAbs++, aMinPar);
2146       }
2147     }
2148     
2149     // Add the last parameter
2150     if (j == 0)
2151       theSurfaceData.SetUParam(iAbs++, aMaxPar);
2152     else
2153       theSurfaceData.SetVParam(iAbs++, aMaxPar);
2154   }
2155   
2156   // Compute of grid points.
2157   gp_Pnt        aPnt;
2158   Standard_Real aParU;
2159   Standard_Real aParV;
2160   
2161   for (i = 1; i <= aNbGridPnts[0]; i++) {
2162     aParU = theSurfaceData.GetUParam(i);
2163     
2164     for (j = 1; j <= aNbGridPnts[1]; j++) {
2165       aParV = theSurfaceData.GetVParam(j);
2166       
2167       theSurf->D0(aParU, aParV, aPnt);
2168       theSurfaceData.SetGridPoint(i, j, aPnt);
2169     }
2170   }
2171
2172   // Compute deflection.
2173   Standard_Real aDef = 0.;
2174 //   Standard_Real aDefLin;
2175 //   Standard_Real aParMid;
2176 //   Standard_Real aParConst;
2177 //   Standard_Real aDistPP;
2178 //   gp_Pnt        aPntMid;
2179 //   gp_Vec        aVec;
2180 //   gp_XYZ        aCoord;
2181
2182 //   // Compute DU deflection.
2183 //   for (i = 1; i < aNbGridPnts[0]; i++) {
2184 //     aParMid = 0.5*(theSurfaceData.GetUParam(i + 1) +
2185 //         theSurfaceData.GetUParam(i));
2186
2187 //     for (j = 1; j <= aNbGridPnts[1]; j++) {
2188 //       const gp_Pnt &thePnt1 = theSurfaceData.GetGridPoint(i,     j);
2189 //       const gp_Pnt &thePnt2 = theSurfaceData.GetGridPoint(i + 1, j);
2190
2191 //       aVec.SetXYZ(thePnt2.XYZ().Subtracted(thePnt1.XYZ()));
2192 //       aDistPP = aVec.Magnitude();
2193
2194 //       if (aDistPP > theTolerance) {
2195 //      // Computation of a distance of a middle point from the line P1 - P2.
2196 //      aParConst = theSurfaceData.GetVParam(j);
2197 //      theSurf->D0(aParMid, aParConst, aPntMid);
2198 //      aCoord = aPntMid.XYZ();
2199 //      aCoord.Subtract(thePnt1.XYZ());
2200 //      aCoord.Cross (aVec.XYZ());
2201 //      aCoord.Divide(aDistPP);
2202 //      aDefLin = aCoord.Modulus();
2203
2204 //      if (aDefLin > aDef)
2205 //   aDef = aDefLin;
2206 //       }
2207 //     }
2208 //   }
2209
2210 //   // Compute DV deflection.
2211 //   for (j = 1; j < aNbGridPnts[1]; j++) {
2212 //     aParMid = 0.5*(theSurfaceData.GetVParam(j + 1) +
2213 //         theSurfaceData.GetVParam(j));
2214
2215 //     for (i = 1; i <= aNbGridPnts[0]; i++) {
2216 //       const gp_Pnt &thePnt1 = theSurfaceData.GetGridPoint(i, j);
2217 //       const gp_Pnt &thePnt2 = theSurfaceData.GetGridPoint(i, j + 1);
2218
2219 //       aVec.SetXYZ(thePnt2.XYZ().Subtracted(thePnt1.XYZ()));
2220 //       aDistPP = aVec.Magnitude();
2221
2222 //       if (aDistPP > theTolerance) {
2223 //      // Computation of a distance of a middle point from the line P1 - P2.
2224 //      aParConst = theSurfaceData.GetUParam(i);
2225 //      theSurf->D0(aParConst, aParMid, aPntMid);
2226 //      aCoord = aPntMid.XYZ();
2227 //      aCoord.Subtract(thePnt1.XYZ());
2228 //      aCoord.Cross (aVec.XYZ());
2229 //      aCoord.Divide(aDistPP);
2230 //      aDefLin = aCoord.Modulus();
2231
2232 //      if (aDefLin > aDef)
2233 //   aDef = aDefLin;
2234 //       }
2235 //     }
2236 //   }
2237
2238   if (theTolerance > aDef)
2239     aDef = theTolerance;
2240
2241   aDef *= 2.;
2242   theSurfaceData.SetGridDeflection(aDef);
2243 }
2244
2245 // ---------------------------------------------------------------------------------
2246 // static function: BuildBox
2247 // purpose:  Compute bounding box.
2248 // ---------------------------------------------------------------------------------
2249 void BuildBox(const Handle(Geom_BSplineSurface)       &theSurf,
2250       const Standard_Real                      theFirstU,
2251       const Standard_Real                      theLastU,
2252       const Standard_Real                      theFirstV,
2253       const Standard_Real                      theLastV,
2254             IntTools_SurfaceRangeLocalizeData &theSurfaceData,
2255               Bnd_Box                           &theBox)
2256 {
2257   Standard_Integer i;
2258   Standard_Integer j;
2259   Standard_Integer aNbUPnts;
2260   Standard_Integer aNbVPnts;
2261   Standard_Real    aParam;
2262   gp_Pnt           aPnt;
2263
2264   theSurfaceData.SetFrame(theFirstU, theLastU, theFirstV, theLastV);
2265   aNbUPnts = theSurfaceData.GetNBUPointsInFrame();
2266   aNbVPnts = theSurfaceData.GetNBVPointsInFrame();
2267
2268   // Add corner points.
2269   theSurf->D0(theFirstU, theFirstV, aPnt);
2270   theBox.Add(aPnt);
2271   theSurf->D0(theLastU,  theFirstV, aPnt);
2272   theBox.Add(aPnt);
2273   theSurf->D0(theFirstU, theLastV, aPnt);
2274   theBox.Add(aPnt);
2275   theSurf->D0(theLastU,  theLastV, aPnt);
2276   theBox.Add(aPnt);
2277
2278   for (i = 1; i <= aNbUPnts; i++) {
2279     // Add top and bottom points.
2280     aParam = theSurfaceData.GetUParamInFrame(i);
2281     theSurf->D0(aParam, theFirstV, aPnt);
2282     theBox.Add(aPnt);
2283     theSurf->D0(aParam, theLastV, aPnt);
2284     theBox.Add(aPnt);
2285
2286     // Add internal points.
2287     for (j = 1; j <= aNbVPnts; j++) {
2288       const gp_Pnt &aGridPnt = theSurfaceData.GetPointInFrame(i, j);
2289
2290       theBox.Add(aGridPnt);
2291     }
2292   }
2293
2294   // Add left and right points.
2295   for (j = 1; j <= aNbVPnts; j++) {
2296     aParam = theSurfaceData.GetVParamInFrame(j);
2297     theSurf->D0(theFirstU, aParam, aPnt);
2298     theBox.Add(aPnt);
2299     theSurf->D0(theLastU,  aParam, aPnt);
2300     theBox.Add(aPnt);
2301   }
2302
2303   theBox.Enlarge(theSurfaceData.GetGridDeflection());
2304 }
2305 //  Modified by skv - Wed Nov  2 15:21:11 2005 Optimization End
2306
2307
2308 // ---------------------------------------------------------------------------------
2309 // static function: MergeSolutions
2310 // purpose:  
2311 // ---------------------------------------------------------------------------------
2312 static void MergeSolutions(const IntTools_ListOfCurveRangeSample& theListCurveRange,
2313                            const IntTools_ListOfSurfaceRangeSample& theListSurfaceRange,
2314                            IntTools_ListOfCurveRangeSample& theListCurveRangeSort,
2315                            IntTools_ListOfSurfaceRangeSample& theListSurfaceRangeSort) {
2316   
2317   IntTools_ListIteratorOfListOfCurveRangeSample anItC2;
2318   IntTools_ListIteratorOfListOfSurfaceRangeSample anItS1(theListSurfaceRange), anItS2;
2319   IntTools_MapOfSurfaceSample aMapToAvoid;
2320
2321   for(; anItS1.More(); anItS1.Next()) {
2322     const IntTools_SurfaceRangeSample& aRangeS = anItS1.Value();
2323
2324     if(aMapToAvoid.Contains(aRangeS))
2325       continue;
2326     aMapToAvoid.Add(aRangeS);
2327
2328     anItC2.Initialize(theListCurveRange);
2329     anItS2.Initialize(theListSurfaceRange);
2330
2331     for(; anItS2.More() && anItC2.More(); anItS2.Next(), anItC2.Next()) {
2332       if(aRangeS.IsEqual(anItS2.Value())) {
2333         theListCurveRangeSort.Append(anItC2.Value());
2334         theListSurfaceRangeSort.Append(anItS2.Value());
2335       }
2336     }
2337   }
2338 }
2339
2340 // ---------------------------------------------------------------------------------
2341 // static function: CheckSampling
2342 // purpose:  
2343 // ---------------------------------------------------------------------------------
2344 static void CheckSampling(const IntTools_CurveRangeSample& theCurveRange,
2345                           const IntTools_SurfaceRangeSample& theSurfaceRange,
2346                           const IntTools_CurveRangeLocalizeData& theCurveData,
2347                           const IntTools_SurfaceRangeLocalizeData& theSurfaceData,
2348                           const Standard_Real DiffC,
2349                           const Standard_Real DiffU,
2350                           const Standard_Real DiffV,
2351                           Standard_Boolean& bAllowSamplingC,
2352                           Standard_Boolean& bAllowSamplingU,
2353                           Standard_Boolean& bAllowSamplingV) {
2354   
2355   const Standard_Real dLimit = 1000;
2356   bAllowSamplingC = Standard_True;
2357   bAllowSamplingU = Standard_True;
2358   bAllowSamplingV = Standard_True;
2359
2360   // check
2361   if((pow((Standard_Real)theCurveData.GetNbSample(), (Standard_Real )(theCurveRange.GetDepth() + 1)) > dLimit) ||
2362      ((DiffC / theCurveData.GetNbSample()) < theCurveData.GetMinRange())) {
2363     bAllowSamplingC = Standard_False;
2364   }
2365
2366   if((pow((Standard_Real )theSurfaceData.GetNbSampleU(), (Standard_Real )(theSurfaceRange.GetDepthU() + 1)) > dLimit) ||
2367      ((DiffU / theSurfaceData.GetNbSampleU()) < theSurfaceData.GetMinRangeU())) {
2368     bAllowSamplingU = Standard_False;
2369   }
2370   
2371
2372   if((pow((Standard_Real )theSurfaceData.GetNbSampleV(), (Standard_Real )(theSurfaceRange.GetDepthV() + 1)) > dLimit) ||
2373      ((DiffV / theSurfaceData.GetNbSampleV()) < theSurfaceData.GetMinRangeV())) {
2374     bAllowSamplingV = Standard_False;
2375   }
2376 }