1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 // This file is part of Open CASCADE Technology software library.
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.
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
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>
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>
68 static Standard_Boolean SetEmptyResultRange(const Standard_Real theParameter,
69 IntTools_MarkedRangeSet& theMarkedRange);
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);
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);
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,
99 static void MergeSolutions(const IntTools_ListOfCurveRangeSample& theListCurveRange,
100 const IntTools_ListOfSurfaceRangeSample& theListSurfaceRange,
101 IntTools_ListOfCurveRangeSample& theListCurveRangeSort,
102 IntTools_ListOfSurfaceRangeSample& theListSurfaceRangeSort);
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);
115 // ==================================================================================
116 // function: IntTools_BeanFaceIntersector
118 // ==================================================================================
119 IntTools_BeanFaceIntersector::IntTools_BeanFaceIntersector() :
120 myFirstParameter(0.),
128 myIsDone(Standard_False)
130 myCriteria = Precision::Confusion();
131 myCurveResolution = Precision::PConfusion();
135 // ==================================================================================
136 // function: IntTools_BeanFaceIntersector
138 // ==================================================================================
139 IntTools_BeanFaceIntersector::IntTools_BeanFaceIntersector(const TopoDS_Edge& theEdge,
140 const TopoDS_Face& theFace) :
141 myFirstParameter(0.),
149 myIsDone(Standard_False)
151 Init(theEdge, theFace);
154 // ==================================================================================
155 // function: IntTools_BeanFaceIntersector
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.),
168 myIsDone(Standard_False)
170 Init(theCurve, theSurface, theBeanTolerance, theFaceTolerance);
173 // ==================================================================================
174 // function: IntTools_BeanFaceIntersector
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)
199 myCriteria = myBeanTolerance + myFaceTolerance;
200 myCurveResolution = myCurve.Resolution(myCriteria);
202 mySurface = theSurface;
203 myTrsfSurface = Handle(Geom_Surface)::DownCast(mySurface.Surface().Surface()->Transformed(mySurface.Trsf()));
206 // ==================================================================================
209 // ==================================================================================
210 void IntTools_BeanFaceIntersector::Init(const TopoDS_Edge& theEdge,
211 const TopoDS_Face& theFace)
213 if (myContext.IsNull()) {
214 myContext = new IntTools_Context;
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);
223 myCriteria = myBeanTolerance + myFaceTolerance + Precision::Confusion();
224 myCurveResolution = myCurve.Resolution(myCriteria);
226 SetSurfaceParameters(mySurface.FirstUParameter(), mySurface.LastUParameter(),
227 mySurface.FirstVParameter(), mySurface.LastVParameter());
231 // ==================================================================================
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)
241 mySurface = theSurface;
242 myTrsfSurface = Handle(Geom_Surface)::DownCast(mySurface.Surface().Surface()->Transformed(mySurface.Trsf()));
243 myBeanTolerance = theBeanTolerance;
244 myFaceTolerance = theFaceTolerance;
246 myCriteria = myBeanTolerance + myFaceTolerance;
247 myCurveResolution = myCurve.Resolution(myCriteria);
249 SetSurfaceParameters(mySurface.FirstUParameter(), mySurface.LastUParameter(),
250 mySurface.FirstVParameter(), mySurface.LastVParameter());
254 // ==================================================================================
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)
269 Init(theCurve, theSurface, theBeanTolerance, theFaceTolerance);
270 SetBeanParameters(theFirstParOnCurve, theLastParOnCurve);
271 SetSurfaceParameters(theUMinParameter, theUMaxParameter, theVMinParameter, theVMaxParameter);
274 // ==================================================================================
275 // function: SetContext
277 // ==================================================================================
278 void IntTools_BeanFaceIntersector::SetContext(const Handle(IntTools_Context)& theContext)
280 myContext = theContext;
282 // ==================================================================================
285 // ==================================================================================
286 const Handle(IntTools_Context)& IntTools_BeanFaceIntersector::Context()const
291 // ==================================================================================
292 // function: SetBeanParameters
294 // ==================================================================================
295 void IntTools_BeanFaceIntersector::SetBeanParameters(const Standard_Real theFirstParOnCurve,
296 const Standard_Real theLastParOnCurve)
298 myFirstParameter = theFirstParOnCurve;
299 myLastParameter = theLastParOnCurve;
302 // ==================================================================================
303 // function: SetSurfaceParameters
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)
311 myUMinParameter = theUMinParameter;
312 myUMaxParameter = theUMaxParameter;
313 myVMinParameter = theVMinParameter;
314 myVMaxParameter = theVMaxParameter;
317 // ==================================================================================
320 // ==================================================================================
321 void IntTools_BeanFaceIntersector::Perform()
323 myIsDone = Standard_False;
326 if (myContext.IsNull())
328 myContext=new IntTools_Context;
331 // Fast computation of Line/Plane case
332 if (myCurve.GetType() == GeomAbs_Line &&
333 mySurface.GetType() == GeomAbs_Plane)
339 // Fast check on coincidence for analytic cases
340 if (FastComputeAnalytic())
342 // no further computation is necessary
343 myIsDone = Standard_True;
347 // Initialization of the range manager
348 myRangeManager.SetBoundaries(myFirstParameter, myLastParameter, 0);
351 Standard_Boolean isCoincide = TestComputeCoinside();
354 myResults.Append(IntTools_Range(myFirstParameter, myLastParameter));
355 myIsDone = Standard_True;
359 // Perform intersection
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)));
372 Standard_Boolean isLocalized = bLocalize && ComputeLocalized();
374 // Perform real intersection
377 ComputeAroundExactIntersection();
379 ComputeUsingExtremum();
381 ComputeNearRangeBoundaries();
384 myIsDone = Standard_True;
386 // Treatment of the results
387 for (Standard_Integer i = 1; i <= myRangeManager.Length(); i++)
389 if (myRangeManager.Flag(i) != 2)
392 IntTools_Range aRange = myRangeManager.Range(i);
393 Standard_Integer iLastRange = myResults.Length();
396 IntTools_Range& aLastRange = myResults.ChangeValue(iLastRange);
397 if (Abs(aRange.First() - aLastRange.Last()) > Precision::PConfusion())
399 myResults.Append(aRange);
403 aLastRange.SetLast(aRange.Last());
407 myResults.Append(aRange);
411 // ==================================================================================
414 // ==================================================================================
415 const IntTools_SequenceOfRanges& IntTools_BeanFaceIntersector::Result() const
420 // ==================================================================================
423 // ==================================================================================
424 void IntTools_BeanFaceIntersector::Result(IntTools_SequenceOfRanges& theResults) const
426 theResults = myResults;
429 // ==================================================================================
430 // function: Distance
432 // ==================================================================================
433 Standard_Real IntTools_BeanFaceIntersector::Distance(const Standard_Real theArg)
435 gp_Pnt aPoint = myCurve.Value(theArg);
437 GeomAPI_ProjectPointOnSurf& aProjector = myContext->ProjPS(mySurface.Face());
438 aProjector.Perform(aPoint);
440 if(aProjector.IsDone() && aProjector.NbPoints() > 0) {
441 return aProjector.LowerDistance();
444 Standard_Real aDistance = RealLast();
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);
455 Standard_Boolean useMinMaxPoints = Standard_True;
456 Standard_Boolean computeisoline = Standard_True;
458 if(aPointMin.IsEqual(aPointMax, myCriteria) &&
459 aPointMin.IsEqual(aPointMid, myCriteria) &&
460 aPointMax.IsEqual(aPointMid, myCriteria)) {
461 computeisoline = Standard_False;
465 Handle(Geom_Curve) aCurve = (i < 2) ? myTrsfSurface->UIso(anIsoParameter) : myTrsfSurface->VIso(anIsoParameter);
466 GeomAPI_ProjectPointOnCurve aProjectorOnCurve(aPoint, aCurve, aMinParameter, aMaxParameter);
468 if(aProjectorOnCurve.NbPoints() > 0) {
469 useMinMaxPoints = Standard_False;
471 if(aDistance > aProjectorOnCurve.LowerDistance())
472 aDistance = aProjectorOnCurve.LowerDistance();
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;
487 // ==================================================================================
488 // function: Distance
490 // ==================================================================================
491 Standard_Real IntTools_BeanFaceIntersector::Distance(const Standard_Real theArg,
492 Standard_Real& theUParameter,
493 Standard_Real& theVParameter)
495 gp_Pnt aPoint = myCurve.Value(theArg);
497 theUParameter = myUMinParameter;
498 theVParameter = myVMinParameter;
500 Standard_Real aDistance = RealLast();
501 Standard_Boolean projectionfound = Standard_False;
503 GeomAPI_ProjectPointOnSurf& aProjector = myContext->ProjPS(mySurface.Face());
504 aProjector.Perform(aPoint);
506 if(aProjector.IsDone() && aProjector.NbPoints() > 0) {
507 aProjector.LowerDistanceParameters(theUParameter, theVParameter);
508 aDistance = aProjector.LowerDistance();
509 projectionfound = Standard_True;
512 if(!projectionfound) {
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);
523 Standard_Boolean useMinMaxPoints = Standard_True;
524 Standard_Boolean computeisoline = Standard_True;
526 if(aPointMin.IsEqual(aPointMax, myCriteria) &&
527 aPointMin.IsEqual(aPointMid, myCriteria) &&
528 aPointMax.IsEqual(aPointMid, myCriteria)) {
529 computeisoline = Standard_False;
533 Handle(Geom_Curve) aCurve = (i < 2) ? myTrsfSurface->UIso(anIsoParameter) : myTrsfSurface->VIso(anIsoParameter);
534 GeomAPI_ProjectPointOnCurve aProjectorOnCurve(aPoint, aCurve, aMinParameter, aMaxParameter);
536 if(aProjectorOnCurve.NbPoints() > 0) {
537 useMinMaxPoints = Standard_False;
539 if(aDistance > aProjectorOnCurve.LowerDistance()) {
540 theUParameter = (i<=1) ? anIsoParameter : aProjectorOnCurve.LowerDistanceParameter();
541 theVParameter = (i>=2) ? anIsoParameter : aProjectorOnCurve.LowerDistanceParameter();
542 aDistance = aProjectorOnCurve.LowerDistance();
547 if(useMinMaxPoints) {
548 Standard_Real aPPDistance = aPoint.Distance(aPointMin);
550 if(aPPDistance < aDistance) {
551 theUParameter = (i<=1) ? anIsoParameter : aMinParameter;
552 theVParameter = (i>=2) ? anIsoParameter : aMinParameter;
553 aDistance = aPPDistance;
555 aPPDistance = aPoint.Distance(aPointMax);
557 if(aPPDistance < aDistance) {
558 theUParameter = (i<=1) ? anIsoParameter : aMaxParameter;
559 theVParameter = (i>=2) ? anIsoParameter : aMaxParameter;
560 aDistance = aPPDistance;
565 theUParameter = (myUMinParameter > theUParameter) ? myUMinParameter : theUParameter;
566 theUParameter = (myUMaxParameter < theUParameter) ? myUMaxParameter : theUParameter;
567 theVParameter = (myVMinParameter > theVParameter) ? myVMinParameter : theVParameter;
568 theVParameter = (myVMaxParameter < theVParameter) ? myVMaxParameter : theVParameter;
573 // ==================================================================================
574 // function: ComputeAroundExactIntersection
576 // ==================================================================================
577 void IntTools_BeanFaceIntersector::ComputeAroundExactIntersection()
579 IntCurveSurface_HInter anExactIntersector;
581 Handle(BRepAdaptor_HCurve) aCurve = new BRepAdaptor_HCurve(myCurve);
582 Handle(BRepAdaptor_HSurface) aSurface = new BRepAdaptor_HSurface(mySurface);
584 anExactIntersector.Perform(aCurve, aSurface);
586 if (anExactIntersector.IsDone()) {
587 Standard_Integer i = 0;
589 if (anExactIntersector.NbPoints() > 1)
591 // To avoid unification of the intersection points in a single intersection
592 // range, perform exact range search considering the lowest possible tolerance
593 // for edge and face.
594 myCriteria = 3 * Precision::Confusion();
595 myCurveResolution = myCurve.Resolution (myCriteria);
598 for(i = 1; i <= anExactIntersector.NbPoints(); i++) {
599 const IntCurveSurface_IntersectionPoint& aPoint = anExactIntersector.Point(i);
601 if((aPoint.W() >= myFirstParameter) && (aPoint.W() <= myLastParameter)) {
602 Standard_Boolean UIsNotValid = ((myUMinParameter > aPoint.U()) || (aPoint.U() > myUMaxParameter));
603 Standard_Boolean VIsNotValid = ((myVMinParameter > aPoint.V()) || (aPoint.V() > myVMaxParameter));
604 Standard_Boolean solutionIsValid = !UIsNotValid && !VIsNotValid;
605 Standard_Real U = aPoint.U();
606 Standard_Real V = aPoint.V();
608 if(UIsNotValid || VIsNotValid) {
609 Standard_Boolean bUCorrected = Standard_True;
612 bUCorrected = Standard_False;
613 solutionIsValid = Standard_False;
615 if(mySurface.IsUPeriodic()) {
616 Standard_Real aNewU, aUPeriod, aEps, du;
618 aUPeriod = mySurface.UPeriod();
619 aEps = Epsilon(aUPeriod);
621 GeomInt::AdjustPeriodic(U, myUMinParameter, myUMaxParameter,
622 aUPeriod, aNewU, du, aEps);
623 solutionIsValid = Standard_True;
624 bUCorrected = Standard_True;
628 // if(solutionIsValid && VIsNotValid) {
629 if(bUCorrected && VIsNotValid) {
630 solutionIsValid = Standard_False;
632 if(mySurface.IsVPeriodic()) {
633 Standard_Real aNewV, aVPeriod, aEps, dv;
635 aVPeriod = mySurface.VPeriod();
636 aEps = Epsilon(aVPeriod);
638 GeomInt::AdjustPeriodic(V, myVMinParameter, myVMaxParameter,
639 aVPeriod, aNewV, dv, aEps);
640 solutionIsValid = Standard_True;
649 Standard_Integer aNbRanges = myRangeManager.Length();
651 ComputeRangeFromStartPoint(Standard_False, aPoint.W(), U, V);
652 ComputeRangeFromStartPoint(Standard_True, aPoint.W(), U, V);
654 if(aNbRanges == myRangeManager.Length()) {
655 SetEmptyResultRange(aPoint.W(), myRangeManager);
656 } // end if(aNbRanges == myRangeManager.Length())
660 for(i = 1; i <= anExactIntersector.NbSegments(); i++) {
661 const IntCurveSurface_IntersectionSegment& aSegment = anExactIntersector.Segment(i);
662 IntCurveSurface_IntersectionPoint aPoint1, aPoint2;
663 aSegment.Values(aPoint1, aPoint2);
665 Standard_Real aFirstParameter = (aPoint1.W() < myFirstParameter) ? myFirstParameter : aPoint1.W();
666 Standard_Real aLastParameter = (myLastParameter < aPoint2.W()) ? myLastParameter : aPoint2.W();
668 myRangeManager.InsertRange(aFirstParameter, aLastParameter, 2);
670 ComputeRangeFromStartPoint(Standard_False, aPoint1.W(), aPoint1.U(), aPoint1.V());
671 ComputeRangeFromStartPoint(Standard_True, aPoint2.W(), aPoint2.U(), aPoint2.V());
676 // ==================================================================================
677 // function: FastComputeExactIntersection
679 // ==================================================================================
680 Standard_Boolean IntTools_BeanFaceIntersector::FastComputeAnalytic()
682 GeomAbs_CurveType aCT = myCurve.GetType();
683 if (aCT == GeomAbs_BezierCurve ||
684 aCT == GeomAbs_BSplineCurve ||
685 aCT == GeomAbs_OffsetCurve ||
686 aCT == GeomAbs_OtherCurve)
688 // not supported type
689 return Standard_False;
692 Standard_Boolean isCoincide = Standard_False;
693 Standard_Boolean hasIntersection = Standard_True;
695 GeomAbs_SurfaceType aST = mySurface.GetType();
697 // Plane - Circle/Ellipse/Hyperbola/Parabola
698 if (aST == GeomAbs_Plane)
700 gp_Pln surfPlane = mySurface.Plane();
707 aDir = myCurve.Circle().Axis().Direction();
708 aPLoc = myCurve.Circle().Location();
711 case GeomAbs_Ellipse:
713 aDir = myCurve.Ellipse().Axis().Direction();
714 aPLoc = myCurve.Ellipse().Location();
717 case GeomAbs_Hyperbola:
719 aDir = myCurve.Hyperbola().Axis().Direction();
720 aPLoc = myCurve.Hyperbola().Location();
723 case GeomAbs_Parabola:
725 aDir = myCurve.Parabola().Axis().Direction();
726 aPLoc = myCurve.Parabola().Location();
730 return Standard_False;
733 Standard_Real anAngle = aDir.Angle(surfPlane.Axis().Direction());
734 if (anAngle > Precision::Angular())
735 return Standard_False;
737 hasIntersection = Standard_False;
739 Standard_Real aDist = surfPlane.Distance(aPLoc);
740 isCoincide = aDist < myCriteria;
743 // Cylinder - Line/Circle
744 else if (aST == GeomAbs_Cylinder)
746 gp_Cylinder aCylinder = mySurface.Cylinder();
747 const gp_Ax1& aCylAxis = aCylinder.Axis();
748 const gp_Dir& aCylDir = aCylAxis.Direction();
749 Standard_Real aCylRadius = aCylinder.Radius();
751 if (aCT == GeomAbs_Line)
753 gp_Lin aLin = myCurve.Line();
754 if (!aLin.Direction().IsParallel(aCylDir, Precision::Angular()))
755 return Standard_False;
757 hasIntersection = Standard_False;
759 Standard_Real aDist = Abs(aLin.Distance(aCylAxis.Location()) - aCylRadius);
760 isCoincide = (aDist < myCriteria);
763 else if (aCT == GeomAbs_Circle)
765 gp_Circ aCircle = myCurve.Circle();
767 Standard_Real anAngle = aCylDir.Angle(aCircle.Axis().Direction());
768 if (anAngle > Precision::Angular())
769 return Standard_False;
771 Standard_Real aDistLoc = gp_Lin(aCylAxis).Distance(aCircle.Location());
772 Standard_Real aDist = aDistLoc + Abs(aCircle.Radius() - aCylRadius);
773 isCoincide = (aDist < myCriteria);
776 hasIntersection = (aDistLoc - (aCircle.Radius() + aCylRadius)) < myCriteria &&
777 (Abs(aCircle.Radius() - aCylRadius) - aDistLoc) < myCriteria;
782 else if (aST == GeomAbs_Sphere)
784 gp_Sphere aSph = mySurface.Sphere();
785 gp_Pnt aSphLoc = aSph.Location();
786 if (aCT == GeomAbs_Line)
788 gp_Lin aLin = myCurve.Line();
789 Standard_Real aDist = aLin.Distance(aSphLoc) - aSph.Radius();
790 hasIntersection = aDist < myCriteria;
794 // Check intermediate point
797 myResults.Append(IntTools_Range(myFirstParameter, myLastParameter));
800 return isCoincide || !hasIntersection;
803 // ==================================================================================
804 // function: ComputeLinePlane
806 // ==================================================================================
807 void IntTools_BeanFaceIntersector::ComputeLinePlane()
809 Standard_Real Tolang = 1.e-9;
810 gp_Pln P = mySurface.Plane();
811 gp_Lin L = myCurve.Line();
813 myIsDone = Standard_True;
815 Standard_Real A,B,C,D;
816 Standard_Real Al,Bl,Cl;
817 Standard_Real Dis,Direc;
819 P.Coefficients(A,B,C,D);
820 gp_Pnt Orig(L.Location());
821 L.Direction().Coord(Al,Bl,Cl);
823 Direc=A*Al+B*Bl+C*Cl;
824 Dis = A*Orig.X() + B*Orig.Y() + C*Orig.Z() + D;
826 Standard_Boolean parallel = Standard_False, inplane = Standard_False;
827 if (Abs(Direc) < Tolang) {
828 parallel= Standard_True;
829 if (Abs(Dis) < myCriteria) {
830 inplane=Standard_True;
833 inplane=Standard_False;
837 gp_Pnt p1 = ElCLib::Value(myFirstParameter, L);
838 gp_Pnt p2 = ElCLib::Value(myLastParameter, L);
839 Standard_Real d1 = A*p1.X() + B*p1.Y() + C*p1.Z() + D;
841 Standard_Real d2 = A*p2.X() + B*p2.Y() + C*p2.Z() + D;
843 if(d1 <= myCriteria && d2 <= myCriteria) {
844 inplane=Standard_True;
849 IntTools_Range aRange(myFirstParameter, myLastParameter);
850 myResults.Append(aRange);
858 Standard_Real t = - Dis/Direc;
859 if(t < myFirstParameter || t > myLastParameter) {
863 gp_Pnt pint(Orig.X()+t*Al, Orig.Y()+t*Bl, Orig.Z()+t*Cl);
866 ElSLib::Parameters(P, pint, u, v);
867 if(myUMinParameter > u || u > myUMaxParameter || myVMinParameter > v || v > myVMaxParameter) {
871 // compute correct range on the edge
872 Standard_Real anAngle, aDt;
875 aDL = L.Position().Direction();
876 aDP = P.Position().Direction();
877 anAngle = Abs(M_PI_2 - aDL.Angle(aDP));
879 aDt = IntTools_Tools::ComputeIntRange
880 (myBeanTolerance, myFaceTolerance, anAngle);
882 Standard_Real t1 = Max(myFirstParameter, t - aDt);
883 Standard_Real t2 = Min(myLastParameter, t + aDt);
884 IntTools_Range aRange(t1, t2);
885 myResults.Append(aRange);
891 // ==================================================================================
892 // function: ComputeUsingExtremum
894 // ==================================================================================
895 void IntTools_BeanFaceIntersector::ComputeUsingExtremum()
897 Standard_Real Tol, af, al;
898 Tol = Precision::PConfusion();
899 Handle(Geom_Curve) aCurve = BRep_Tool::Curve (myCurve.Edge(), af, al);
900 GeomAdaptor_Surface aGASurface (myTrsfSurface,
906 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
908 if(myRangeManager.Flag(i) > 0)
911 IntTools_Range aParamRange = myRangeManager.Range(i);
912 Standard_Real anarg1 = aParamRange.First();
913 Standard_Real anarg2 = aParamRange.Last();
915 if(anarg2 - anarg1 < Precision::PConfusion()) {
917 if (((i > 1) && (myRangeManager.Flag(i - 1) == 2)) ||
918 ((i < myRangeManager.Length()) && (myRangeManager.Flag(i + 1) == 2))) {
919 myRangeManager.SetFlag(i, 1);
924 GeomAdaptor_Curve aGACurve(aCurve, anarg1, anarg2);
925 Extrema_ExtCS theExtCS;
926 theExtCS.Initialize(aGASurface, myUMinParameter, myUMaxParameter,
927 myVMinParameter, myVMaxParameter, Tol, Tol);
928 Standard_Real first = aCurve->FirstParameter(), last = aCurve->LastParameter();
929 if (aCurve->IsPeriodic() ||
930 (anarg1 >= first - Precision::PConfusion() && anarg2 <= last + Precision::PConfusion()))
932 //Extrema_ExtCS theExtCS(aGACurve, aGASurface, Tol, Tol);
933 theExtCS.Perform(aGACurve, anarg1, anarg2);
936 myExtrema = theExtCS;
938 if(myExtrema.IsDone() && (myExtrema.NbExt() || myExtrema.IsParallel())) {
939 Standard_Integer anOldNbRanges = myRangeManager.Length();
941 if (myExtrema.IsParallel()) {
943 if(myExtrema.SquareDistance(1) < myCriteria * myCriteria) {
944 Standard_Real U1, V1, U2, V2;
945 Standard_Real adistance1 = Distance(anarg1, U1, V1);
946 Standard_Real adistance2 = Distance(anarg2, U2, V2);
947 Standard_Boolean validdistance1 = (adistance1 < myCriteria);
948 Standard_Boolean validdistance2 = (adistance2 < myCriteria);
950 if (validdistance1 && validdistance2) {
951 myRangeManager.InsertRange(anarg1, anarg2, 2);
956 ComputeRangeFromStartPoint(Standard_True, anarg1, U1, V1);
960 ComputeRangeFromStartPoint(Standard_False, anarg2, U2, V2);
963 Standard_Real a = anarg1;
964 Standard_Real b = anarg2;
965 Standard_Real da = adistance1;
966 Standard_Real db = adistance2;
967 Standard_Real asolution = a;
968 Standard_Boolean found = Standard_False;
970 while(((b - a) > myCurveResolution) && !found) {
971 asolution = (a+b)*0.5;
972 Standard_Real adist = Distance(asolution, U1, V1);
974 if(adist < myCriteria) {
975 found = Standard_True;
990 ComputeRangeFromStartPoint(Standard_False, asolution, U1, V1);
991 ComputeRangeFromStartPoint(Standard_True, asolution, U1, V1);
994 myRangeManager.SetFlag(i, 1);
1001 myRangeManager.SetFlag(i, 1);
1005 Standard_Boolean solutionfound = Standard_False;
1007 for(Standard_Integer j = 1 ; j <= myExtrema.NbExt(); j++) {
1009 if(myExtrema.SquareDistance(j) < myCriteria * myCriteria) {
1012 myExtrema.Points(j, p1, p2);
1016 Standard_Integer aNbRanges = myRangeManager.Length();
1017 ComputeRangeFromStartPoint(Standard_False, p1.Parameter(), U, V);
1018 ComputeRangeFromStartPoint(Standard_True, p1.Parameter(), U, V);
1019 solutionfound = Standard_True;
1021 if(aNbRanges == myRangeManager.Length()) {
1022 SetEmptyResultRange(p1.Parameter(), myRangeManager);
1027 if(!solutionfound) {
1028 myRangeManager.SetFlag(i, 1);
1031 Standard_Integer adifference = myRangeManager.Length() - anOldNbRanges;
1033 if(adifference > 0) {
1036 } // end if(myExtrema.IsDone() && (myExtrema.NbExt() || myExtrema.IsParallel()))
1040 // ==================================================================================
1041 // function: ComputeNearRangeBoundaries
1043 // ==================================================================================
1044 void IntTools_BeanFaceIntersector::ComputeNearRangeBoundaries()
1046 Standard_Real U = myUMinParameter;
1047 Standard_Real V = myVMinParameter;
1049 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1051 if(myRangeManager.Flag(i) > 0)
1054 if((i > 1) && (myRangeManager.Flag(i-1) > 0))
1057 IntTools_Range aParamRange = myRangeManager.Range(i);
1059 if(Distance(aParamRange.First(), U, V) < myCriteria) {
1060 Standard_Integer aNbRanges = myRangeManager.Length();
1063 ComputeRangeFromStartPoint(Standard_False, aParamRange.First(), U, V, i-1);
1065 ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), U, V, i + (myRangeManager.Length() - aNbRanges));
1067 if(aNbRanges == myRangeManager.Length()) {
1068 SetEmptyResultRange(aParamRange.First(), myRangeManager);
1073 if(myRangeManager.Flag(myRangeManager.Length()) == 0) {
1074 IntTools_Range aParamRange = myRangeManager.Range(myRangeManager.Length());
1076 if(Distance(aParamRange.Last(), U, V) < myCriteria) {
1077 Standard_Integer aNbRanges = myRangeManager.Length();
1079 ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), U, V, myRangeManager.Length());
1081 if(aNbRanges == myRangeManager.Length()) {
1082 SetEmptyResultRange(aParamRange.Last(), myRangeManager);
1088 // ==================================================================================
1089 // function: ComputeRangeFromStartPoint
1090 // purpose: Compute range using start point according to parameter theParameter,
1091 // increasing parameter on curve if ToIncreaseParameter == Standard_True or
1092 // decreasing parameter on curve if ToIncreaseParameter == Standard_False
1093 // ==================================================================================
1094 void IntTools_BeanFaceIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
1095 const Standard_Real theParameter,
1096 const Standard_Real theUParameter,
1097 const Standard_Real theVParameter)
1099 Standard_Integer aFoundIndex = myRangeManager.GetIndex(theParameter, ToIncreaseParameter);
1101 if(aFoundIndex == 0) {
1105 ComputeRangeFromStartPoint(ToIncreaseParameter, theParameter, theUParameter, theVParameter, aFoundIndex);
1108 // ==================================================================================
1109 // function: ComputeRangeFromStartPoint
1110 // purpose: Compute range using start point according to parameter theParameter,
1111 // increasing parameter on curve if ToIncreaseParameter == Standard_True or
1112 // decreasing parameter on curve if ToIncreaseParameter == Standard_False.
1113 // theIndex indicate that theParameter belong the range number theIndex.
1114 // ==================================================================================
1115 void IntTools_BeanFaceIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
1116 const Standard_Real theParameter,
1117 const Standard_Real theUParameter,
1118 const Standard_Real theVParameter,
1119 const Standard_Integer theIndex)
1121 if(myRangeManager.Flag(theIndex) > 0)
1124 Standard_Integer aValidIndex = theIndex;
1126 Standard_Real aMinDelta = myCurveResolution * 0.5;
1127 Standard_Real aDeltaRestrictor = myLastParameter - myFirstParameter;
1129 if(aMinDelta > aDeltaRestrictor)
1130 aMinDelta = aDeltaRestrictor * 0.5;
1132 Standard_Real tenOfMinDelta = aMinDelta * 10.;
1133 Standard_Real aDelta = myCurveResolution;
1135 Standard_Real aCurPar = (ToIncreaseParameter) ? (theParameter + aDelta) : (theParameter - aDelta);
1136 Standard_Real aPrevPar = theParameter;
1137 IntTools_Range aCurrentRange = myRangeManager.Range(aValidIndex);
1139 Standard_Boolean BoundaryCondition = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1141 if(BoundaryCondition) {
1142 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1143 BoundaryCondition = Standard_False;
1146 Standard_Integer loopcounter = 0; // neccesary as infinite loop restricter
1147 Standard_Real U = theUParameter;
1148 Standard_Real V = theVParameter;
1149 Standard_Boolean anotherSolutionFound = Standard_False;
1151 Standard_Boolean isboundaryindex = Standard_False;
1152 Standard_Boolean isvalidindex = Standard_True;
1154 while((aDelta >= aMinDelta) && (loopcounter <= 10)) {
1155 Standard_Boolean pointfound = Standard_False;
1158 gp_Pnt aPoint = myCurve.Value(aCurPar);
1159 Extrema_GenLocateExtPS anExtrema(mySurface, 1.e-10, 1.e-10);
1160 anExtrema.Perform(aPoint, U, V);
1162 if(anExtrema.IsDone()) {
1163 if(anExtrema.SquareDistance() < myCriteria * myCriteria) {
1164 Extrema_POnSurf aPOnSurf = anExtrema.Point();
1165 aPOnSurf.Parameter(U, V);
1166 pointfound = Standard_True;
1170 pointfound = (Distance(aCurPar) < myCriteria);
1175 anotherSolutionFound = Standard_True;
1177 if(BoundaryCondition && (isboundaryindex || !isvalidindex))
1181 aDeltaRestrictor = aDelta;
1184 // if point found decide to increase aDelta using derivative of distance function
1187 aDelta = (pointfound) ? (aDelta * 2.) : (aDelta * 0.5);
1188 aDelta = (aDelta < aDeltaRestrictor) ? aDelta : aDeltaRestrictor;
1190 aCurPar = (ToIncreaseParameter) ? (aPrevPar + aDelta) : (aPrevPar - aDelta);
1193 // prevent infinite loop when (aPrevPar +/- aDelta) == aPrevPar == 0.
1196 if( aCurPar == aPrevPar )
1199 BoundaryCondition = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1201 isboundaryindex = Standard_False;
1202 isvalidindex = Standard_True;
1204 if(BoundaryCondition) {
1205 isboundaryindex = ((!ToIncreaseParameter && (aValidIndex == 1)) ||
1206 (ToIncreaseParameter && (aValidIndex == myRangeManager.Length())));
1208 if(!isboundaryindex) {
1211 Standard_Integer aFlag = (ToIncreaseParameter) ? myRangeManager.Flag(aValidIndex + 1) : myRangeManager.Flag(aValidIndex - 1);
1214 aValidIndex = (ToIncreaseParameter) ? (aValidIndex + 1) : (aValidIndex - 1);
1215 aCurrentRange = myRangeManager.Range(aValidIndex);
1217 if((ToIncreaseParameter && (aCurPar > aCurrentRange.Last())) ||
1218 (!ToIncreaseParameter && (aCurPar < aCurrentRange.First()))) {
1219 aCurPar = (aCurrentRange.First() + aCurrentRange.Last()) * 0.5;
1224 isvalidindex = Standard_False;
1225 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1230 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1233 if(aDelta < tenOfMinDelta) {
1239 } // if(BoundaryCondition)
1242 if(anotherSolutionFound) {
1243 if(ToIncreaseParameter)
1244 myRangeManager.InsertRange(theParameter, aPrevPar, 2);
1246 myRangeManager.InsertRange(aPrevPar, theParameter, 2);
1250 // ---------------------------------------------------------------------------------
1251 // static function: SetEmptyResultRange
1253 // ---------------------------------------------------------------------------------
1254 static Standard_Boolean SetEmptyResultRange(const Standard_Real theParameter,
1255 IntTools_MarkedRangeSet& theMarkedRange) {
1257 const TColStd_SequenceOfInteger& anIndices = theMarkedRange.GetIndices(theParameter);
1258 Standard_Boolean add = (anIndices.Length() > 0);
1260 for(Standard_Integer k = 1; k <= anIndices.Length(); k++) {
1261 if(theMarkedRange.Flag(anIndices(k)) == 2) {
1262 add = Standard_False;
1268 theMarkedRange.InsertRange(theParameter, theParameter, 2);
1274 // ---------------------------------------------------------------------------------
1275 // static function: TestCoinside
1277 // ---------------------------------------------------------------------------------
1278 // static Standard_Boolean TestClose(const Extrema_ExtPS & theExt,
1279 // const Standard_Real theDist)
1281 // Standard_Boolean close = Standard_False;
1282 // if(!theExt.IsDone() || theExt.NbExt() == 0)
1285 // Standard_Integer ie;
1286 // for(ie = 1; ie <= theExt.NbExt(); ie++) {
1287 // Standard_Real dist = theExt.Value(ie);
1288 // if(dist <= theDist) {
1289 // close = Standard_True;
1297 // Standard_Boolean TestCoinside(const BRepAdaptor_Curve& theCurve,
1298 // const BRepAdaptor_Surface& theSurface)
1300 // Standard_Real cfp = theCurve.FirstParameter(), clp = theCurve.LastParameter();
1301 // Standard_Real cdp = fabs(clp - cfp) / 23.;
1303 // Standard_Integer i = 0;
1304 // Standard_Real tolE = theCurve.Tolerance(), tolF = theSurface.Tolerance();
1305 // Standard_Real tolT = tolE + tolF, tolU = 1.e-9, tolV = 1.e-9;
1308 // theCurve.D0(cfp,aP);
1309 // Extrema_ExtPS eps(aP,theSurface,tolU,tolV);
1311 // if(!TestClose(eps,tolT))
1312 // return Standard_False;
1314 // theCurve.D0(clp,aP);
1317 // if(!TestClose(eps,tolT))
1318 // return Standard_False;
1320 // Standard_Boolean close = Standard_True;
1322 // for(i = 1; i <= 22; i++) {
1323 // theCurve.D0((cfp+((Standard_Real)i)*cdp),aP);
1325 // if(!TestClose(eps,tolT)) {
1326 // close = Standard_False;
1333 // ======================================================================================================================
1334 // function: LocalizeSolutions
1336 // ======================================================================================================================
1337 Standard_Boolean IntTools_BeanFaceIntersector::LocalizeSolutions(const IntTools_CurveRangeSample& theCurveRange,
1338 const Bnd_Box& theBoxCurve,
1339 const IntTools_SurfaceRangeSample& theSurfaceRange,
1340 const Bnd_Box& theBoxSurface,
1341 IntTools_CurveRangeLocalizeData& theCurveData,
1342 IntTools_SurfaceRangeLocalizeData& theSurfaceData,
1343 IntTools_ListOfCurveRangeSample& theListCurveRange,
1344 IntTools_ListOfSurfaceRangeSample& theListSurfaceRange)
1346 Standard_Integer tIt = 0, uIt = 0, vIt = 0;
1349 IntTools_CurveRangeSample aRootRangeC(0);
1350 aRootRangeC.SetDepth(0);
1351 IntTools_SurfaceRangeSample aRootRangeS(0, 0, 0, 0);
1353 Bnd_Box aMainBoxC = theBoxCurve;
1354 Bnd_Box aMainBoxS = theBoxSurface;
1355 Standard_Boolean bMainBoxFoundS = Standard_False;
1356 Standard_Boolean bMainBoxFoundC = Standard_False;
1358 IntTools_ListOfCurveRangeSample aListCurveRangeFound;
1359 IntTools_ListOfSurfaceRangeSample aListSurfaceRangeFound;
1362 IntTools_Range aRangeC = theCurveRange.GetRange(myFirstParameter, myLastParameter, theCurveData.GetNbSample());
1363 Standard_Real localdiffC = (aRangeC.Last() - aRangeC.First()) / theCurveData.GetNbSample();
1365 Standard_Real aCurPar = aRangeC.First();
1366 Standard_Real aPrevPar = aRangeC.First();
1367 Standard_Integer aCurIndexInit = theCurveRange.GetRangeIndexDeeper(theCurveData.GetNbSample());
1370 TColStd_ListOfInteger aListCToAvoid;
1371 Standard_Boolean bGlobalCheckDone = Standard_False;
1376 Standard_Integer aCurIndexU = theSurfaceRange.GetRangeIndexUDeeper(theSurfaceData.GetNbSampleU());
1378 Standard_Integer aCurIndexVInit = theSurfaceRange.GetRangeIndexVDeeper(theSurfaceData.GetNbSampleV());
1379 IntTools_Range aRangeV = theSurfaceRange.GetRangeV(myVMinParameter, myVMaxParameter, theSurfaceData.GetNbSampleV());
1382 IntTools_Range aRangeU = theSurfaceRange.GetRangeU(myUMinParameter, myUMaxParameter, theSurfaceData.GetNbSampleU());
1383 Standard_Real aCurParU = aRangeU.First();
1384 Standard_Real aLocalDiffU = (aRangeU.Last() - aRangeU.First()) / theSurfaceData.GetNbSampleU();
1386 Standard_Real aPrevParU = aCurParU;
1387 Standard_Real aLocalDiffV = (aRangeV.Last() - aRangeV.First()) / theSurfaceData.GetNbSampleV();
1390 // ranges check.begin
1391 Standard_Boolean bAllowSamplingC = Standard_True;
1392 Standard_Boolean bAllowSamplingU = Standard_True;
1393 Standard_Boolean bAllowSamplingV = Standard_True;
1396 CheckSampling(theCurveRange, theSurfaceRange, theCurveData, theSurfaceData,
1397 localdiffC, aLocalDiffU, aLocalDiffV,
1398 bAllowSamplingC, bAllowSamplingU, bAllowSamplingV);
1401 if(!bAllowSamplingC && !bAllowSamplingU && !bAllowSamplingV) {
1402 theListCurveRange.Append(theCurveRange);
1403 theListSurfaceRange.Append(theSurfaceRange);
1404 return Standard_True;
1408 // init template. begin
1409 IntTools_CurveRangeSample aNewRangeCTemplate;
1411 if(!bAllowSamplingC) {
1412 aNewRangeCTemplate = theCurveRange;
1413 aCurIndexInit = theCurveRange.GetRangeIndex();
1414 localdiffC = (aRangeC.Last() - aRangeC.First());
1417 aNewRangeCTemplate.SetDepth(theCurveRange.GetDepth() + 1);
1418 aNewRangeCTemplate.SetRangeIndex(aCurIndexInit);
1421 IntTools_SurfaceRangeSample aNewRangeSTemplate = theSurfaceRange;
1423 if(bAllowSamplingU) {
1424 aNewRangeSTemplate.SetDepthU(theSurfaceRange.GetDepthU() + 1);
1427 aCurIndexU = aNewRangeSTemplate.GetIndexU();
1428 aLocalDiffU = aRangeU.Last() - aRangeU.First();
1431 if(bAllowSamplingV) {
1432 aNewRangeSTemplate.SetDepthV(theSurfaceRange.GetDepthV() + 1);
1435 aCurIndexVInit = theSurfaceRange.GetIndexV();
1436 aLocalDiffV = aRangeV.Last() - aRangeV.First();
1438 // init template. end
1441 Standard_Boolean bHasOut = Standard_False;
1442 const Standard_Integer nbU = (bAllowSamplingU) ? theSurfaceData.GetNbSampleU() : 1;
1443 const Standard_Integer nbV = (bAllowSamplingV) ? theSurfaceData.GetNbSampleV() : 1;
1444 const Standard_Integer nbC = (bAllowSamplingC) ? theCurveData.GetNbSample() : 1;
1446 for(uIt = 1; uIt <= nbU; uIt++, aCurIndexU++, aPrevParU = aCurParU) {
1447 aCurParU += aLocalDiffU;
1450 Standard_Real aCurParV = aRangeV.First();
1451 Standard_Real aPrevParV = aCurParV;
1452 Standard_Integer aCurIndexV = aCurIndexVInit;
1454 Standard_Boolean bHasOutV = Standard_False;
1457 for(vIt = 1; vIt <= nbV; vIt++, aCurIndexV++, aPrevParV = aCurParV) {
1459 aCurParV += aLocalDiffV;
1464 IntTools_SurfaceRangeSample aNewRangeS = aNewRangeSTemplate;
1466 if(bAllowSamplingU) {
1467 aNewRangeS.SetIndexU(aCurIndexU);
1470 if(bAllowSamplingV) {
1471 aNewRangeS.SetIndexV(aCurIndexV);
1474 if(theSurfaceData.IsRangeOut(aNewRangeS)) {
1475 bHasOutV = Standard_True;
1483 if(!theSurfaceData.FindBox(aNewRangeS, aBoxS)) {
1485 if(mySurface.GetType() == GeomAbs_BSplineSurface) {
1486 // if(Standard_False ) {
1487 Handle(Geom_BSplineSurface) aSurfBspl = Handle(Geom_BSplineSurface)::DownCast(myTrsfSurface);
1488 aBoxS = GetSurfaceBox(aSurfBspl, aPrevParU, aCurParU, aPrevParV, aCurParV, myCriteria, theSurfaceData);
1491 BndLib_AddSurface::Add(mySurface, aPrevParU, aCurParU, aPrevParV, aCurParV, myCriteria, aBoxS);
1493 // Bnd_Box aMainBoxC;
1495 if(!bMainBoxFoundC && theCurveData.FindBox(aRootRangeC, aMainBoxC)) {
1496 bMainBoxFoundC = Standard_True;
1499 if(aBoxS.IsOut(aMainBoxC)) {
1500 theSurfaceData.AddOutRange(aNewRangeS);
1501 bHasOutV = Standard_True;
1505 theSurfaceData.AddBox(aNewRangeS, aBoxS);
1508 if(aBoxS.IsOut(theBoxCurve)) {
1509 bHasOutV = Standard_True;
1513 IntTools_ListOfBox aListOfBox;
1514 TColStd_ListOfInteger aListOfIndex;
1516 Standard_Boolean bHasOutC = Standard_False;
1517 Standard_Integer aCurIndex = aCurIndexInit;
1519 // ////////////////////////////
1520 aCurPar = aRangeC.First();
1521 aPrevPar = aRangeC.First();
1522 IntTools_CurveRangeSample aCurRangeC = aNewRangeCTemplate;
1524 for (tIt = 1; tIt <= nbC; tIt++, aCurIndex++, aPrevPar = aCurPar) {
1526 aCurPar += localdiffC;
1528 // ignore already computed. begin
1529 Standard_Boolean bFound = Standard_False;
1530 TColStd_ListIteratorOfListOfInteger anItToAvoid(aListCToAvoid);
1532 for(; anItToAvoid.More(); anItToAvoid.Next()) {
1533 if(tIt == anItToAvoid.Value()) {
1534 bFound = Standard_True;
1540 if(bAllowSamplingC) {
1541 aCurRangeC.SetRangeIndex(aCurIndex);
1543 bFound = theCurveData.IsRangeOut(aCurRangeC);
1547 bHasOutC = Standard_True;
1550 // ignore already computed. end
1555 if(!theCurveData.FindBox(aCurRangeC, aBoxC)) {
1556 BndLib_Add3dCurve::Add(myCurve, aPrevPar, aCurPar, myCriteria, aBoxC);
1558 // Bnd_Box aMainBoxS;
1560 if(!bMainBoxFoundS && theSurfaceData.FindBox(aRootRangeS, aMainBoxS)) {
1561 bMainBoxFoundS = Standard_True;
1563 if(aBoxC.IsOut(aMainBoxS)) {
1564 theCurveData.AddOutRange(aCurRangeC);
1565 bHasOutC = Standard_True;
1569 theCurveData.AddBox(aCurRangeC, aBoxC);
1572 if(!bGlobalCheckDone && aBoxC.IsOut(theBoxSurface)) {
1573 aListCToAvoid.Append(tIt);
1574 bHasOutC = Standard_True;
1578 if(aBoxC.IsOut(aBoxS)) {
1579 bHasOutV = Standard_True;
1580 bHasOutC = Standard_True;
1585 aListOfIndex.Append(tIt);
1586 aListOfBox.Append(aBoxC);
1587 } // end for(tIt...)
1589 bGlobalCheckDone = Standard_True;
1592 bHasOutV = Standard_True;
1598 IntTools_CurveRangeSample aNewRangeC = aNewRangeCTemplate;
1600 aCurIndex = aCurIndexInit;
1601 TColStd_ListIteratorOfListOfInteger anItI(aListOfIndex);
1602 IntTools_ListIteratorOfListOfBox anItBox(aListOfBox);
1603 Standard_Boolean bUseOldC = Standard_False;
1604 Standard_Boolean bUseOldS = Standard_False;
1605 Standard_Boolean bCheckSize = !bHasOutC;
1607 for(; anItI.More() && anItBox.More(); anItI.Next(), anItBox.Next()) {
1608 aCurIndex = aCurIndexInit + anItI.Value() - 1;
1610 bUseOldS = Standard_False;
1612 if(bAllowSamplingC) {
1613 aNewRangeC.SetRangeIndex(aCurIndex);
1619 if((theCurveRange.GetDepth() == 0) ||
1620 (theSurfaceRange.GetDepthU() == 0) ||
1621 (theSurfaceRange.GetDepthV() == 0)) {
1622 bHasOutC = Standard_True;
1623 bHasOutV = Standard_True;
1625 else if((theCurveRange.GetDepth() < 4) &&
1626 (theSurfaceRange.GetDepthU() < 4) &&
1627 (theSurfaceRange.GetDepthV() < 4)) {
1628 Bnd_Box aBoxC = anItBox.Value();
1630 if(!aBoxC.IsWhole() && !aBoxS.IsWhole()) {
1631 Standard_Real aDiagC = aBoxC.SquareExtent();
1632 Standard_Real aDiagS = aBoxS.SquareExtent();
1634 if(aDiagC < aDiagS) {
1635 if((aDiagC * 10.) < aDiagS) {
1636 bUseOldC = Standard_True;
1637 bHasOutC = Standard_True;
1638 bHasOutV = Standard_True;
1643 if((aDiagS * 10.) < aDiagC) {
1644 bUseOldS = Standard_True;
1645 bHasOutC = Standard_True;
1646 bHasOutV = Standard_True;
1655 aListCurveRangeFound.Append(aNewRangeC);
1656 aListSurfaceRangeFound.Append(aNewRangeS);
1660 // if(bUseOldS || bAllowSamplingU || bAllowSamplingV) {
1661 // theSurfaceData.AddBox(aNewRangeS, aBoxS);
1664 if(bUseOldS && aNewRangeC.IsEqual(theCurveRange)) {
1665 return Standard_False;
1668 if(!LocalizeSolutions(aNewRangeC, anItBox.Value(),
1669 ((bUseOldS) ? theSurfaceRange : aNewRangeS),
1670 ((bUseOldS) ? theBoxSurface : aBoxS),
1671 theCurveData, theSurfaceData,
1672 theListCurveRange, theListSurfaceRange))
1673 return Standard_False;
1677 aListOfIndex.Clear();
1681 // theSurfaceData.AddBox(aNewRangeS, aBoxS);
1683 if(bUseOldC && bAllowSamplingC && (bAllowSamplingU || bAllowSamplingV)) {
1684 if(!LocalizeSolutions(theCurveRange, theBoxCurve,
1686 theCurveData, theSurfaceData,
1687 theListCurveRange, theListSurfaceRange))
1688 return Standard_False;
1691 } // end for (vIt...)
1694 bHasOut = Standard_True;
1699 theListCurveRange.Append(theCurveRange);
1700 theListSurfaceRange.Append(theSurfaceRange);
1703 IntTools_ListIteratorOfListOfCurveRangeSample anIt1(aListCurveRangeFound);
1704 IntTools_ListIteratorOfListOfSurfaceRangeSample anIt2(aListSurfaceRangeFound);
1706 for(; anIt1.More() && anIt2.More(); anIt1.Next(), anIt2.Next()) {
1707 theListCurveRange.Append(anIt1.Value());
1708 theListSurfaceRange.Append(anIt2.Value());
1711 return Standard_True;
1715 // ======================================================================================================================
1716 // function: ComputeLocalized
1718 // ======================================================================================================================
1719 Standard_Boolean IntTools_BeanFaceIntersector::ComputeLocalized() {
1720 Standard_Real Tol = Precision::PConfusion();
1722 IntTools_SurfaceRangeSample aSurfaceRange(0, 0, 0, 0);
1723 Standard_Real dMinU = 10. * Precision::PConfusion();
1724 Standard_Real dMinV = dMinU;
1725 IntTools_SurfaceRangeLocalizeData aSurfaceDataInit(3, 3, dMinU, dMinV);
1726 IntTools_SurfaceRangeLocalizeData& aSurfaceData = myContext->SurfaceData(mySurface.Face());
1727 aSurfaceData.RemoveRangeOutAll();
1728 aSurfaceData.ClearGrid();
1731 Standard_Boolean bFBoxFound = aSurfaceData.FindBox(aSurfaceRange, FBox);
1733 if(mySurface.GetType() == GeomAbs_BSplineSurface) {
1734 Handle(Geom_BSplineSurface) aSurfBspl = Handle(Geom_BSplineSurface)::DownCast(myTrsfSurface);
1736 ComputeGridPoints(aSurfBspl, myUMinParameter, myUMaxParameter,
1737 myVMinParameter, myVMaxParameter, myFaceTolerance,
1741 FBox = GetSurfaceBox(aSurfBspl, myUMinParameter, myUMaxParameter,
1742 myVMinParameter, myVMaxParameter, myCriteria,
1744 aSurfaceData.AddBox(aSurfaceRange, FBox);
1747 } else if(!bFBoxFound) {
1749 BndLib_AddSurface::Add(mySurface, myUMinParameter, myUMaxParameter, myVMinParameter, myVMaxParameter, myFaceTolerance, FBox);
1750 aSurfaceData.AddBox(aSurfaceRange, FBox);
1755 BndLib_Add3dCurve::Add(myCurve.Trim(myFirstParameter, myLastParameter, Precision::PConfusion())->Curve(), myBeanTolerance, EBox);
1757 if(EBox.IsOut(FBox)) {
1758 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
1759 myRangeManager.SetFlag(i, 1);
1761 aSurfaceData.ClearGrid();
1763 return Standard_True;
1766 IntTools_ListOfCurveRangeSample aListCurveRange;
1767 IntTools_ListOfSurfaceRangeSample aListSurfaceRange;
1769 IntTools_CurveRangeSample aCurveRange(0);
1770 aCurveRange.SetDepth(0);
1771 Standard_Integer nbSampleC = 3;
1772 Standard_Integer nbSampleU = aSurfaceData.GetNbSampleU();
1773 Standard_Integer nbSampleV = aSurfaceData.GetNbSampleV();
1774 Standard_Real dMinC = 10. * myCurveResolution;
1775 IntTools_ListOfCurveRangeSample aListOut;
1778 Standard_Boolean bAllowSamplingC = Standard_True;
1779 Standard_Boolean bAllowSamplingU = Standard_True;
1780 Standard_Boolean bAllowSamplingV = Standard_True;
1781 IntTools_CurveRangeLocalizeData aCurveDataTmp(nbSampleC, dMinC);
1782 IntTools_SurfaceRangeLocalizeData aSurfaceDataTmp(nbSampleU, nbSampleV, dMinU, dMinV);
1784 CheckSampling(aCurveRange, aSurfaceRange, aCurveDataTmp, aSurfaceDataTmp,
1785 myLastParameter - myFirstParameter,
1786 myUMaxParameter - myUMinParameter,
1787 myVMaxParameter - myVMinParameter,
1788 bAllowSamplingC, bAllowSamplingU, bAllowSamplingV);
1792 IntTools_CurveRangeLocalizeData aCurveData(nbSampleC, dMinC);
1794 aCurveData.AddBox(aCurveRange, EBox);
1796 if(!LocalizeSolutions(aCurveRange, EBox, aSurfaceRange, FBox,
1797 aCurveData, aSurfaceData,
1798 aListCurveRange, aListSurfaceRange)) {
1799 aSurfaceData.ClearGrid();
1801 return Standard_False;
1804 IntTools_ListOfCurveRangeSample aListCurveRangeSort;
1805 IntTools_ListOfSurfaceRangeSample aListSurfaceRangeSort;
1807 MergeSolutions(aListCurveRange, aListSurfaceRange, aListCurveRangeSort, aListSurfaceRangeSort);
1809 IntTools_ListIteratorOfListOfCurveRangeSample anItC(aListCurveRangeSort);
1810 IntTools_ListIteratorOfListOfSurfaceRangeSample anItS(aListSurfaceRangeSort);
1811 IntTools_SurfaceRangeSample aRangeSPrev;
1813 Extrema_GenExtCS anExtremaGen;
1815 for(; anItC.More() && anItS.More(); anItC.Next(), anItS.Next()) {
1817 IntTools_Range aRangeC(myFirstParameter, myLastParameter);
1820 aRangeC = anItC.Value().GetRange(myFirstParameter, myLastParameter, nbSampleC);
1822 IntTools_Range aRangeU(myUMinParameter, myUMaxParameter);
1825 aRangeU = anItS.Value().GetRangeU(myUMinParameter, myUMaxParameter, nbSampleU);
1827 IntTools_Range aRangeV(myVMinParameter, myVMaxParameter);
1830 aRangeV = anItS.Value().GetRangeV(myVMinParameter, myVMaxParameter, nbSampleV);
1832 Standard_Real anarg1 = aRangeC.First(), anarg2 = aRangeC.Last();
1834 Standard_Boolean bFound = Standard_False;
1836 Standard_Integer nMinIndex = myRangeManager.Length();
1837 Standard_Integer nMaxIndex = -1;
1838 const TColStd_SequenceOfInteger& anInds1 = myRangeManager.GetIndices(anarg1);
1839 Standard_Integer indIt = 1;
1841 for(indIt = 1 ; indIt <= anInds1.Length(); indIt++) {
1842 Standard_Integer nIndex = anInds1.Value(indIt);
1843 nMinIndex = (nMinIndex > nIndex) ? nIndex : nMinIndex;
1844 nMaxIndex = (nMaxIndex < nIndex) ? nIndex : nMaxIndex;
1847 for(indIt = nMinIndex ; indIt <= nMaxIndex; indIt++) {
1848 if(myRangeManager.Flag(indIt) == 2) {
1849 bFound = Standard_True;
1856 nMinIndex = (nMaxIndex >= 0) ? nMaxIndex : nMinIndex;
1857 const TColStd_SequenceOfInteger& anInds2 = myRangeManager.GetIndices(anarg2);
1859 for(indIt = 1 ; indIt <= anInds2.Length(); indIt++) {
1860 Standard_Integer nIndex = anInds2.Value(indIt);
1861 nMinIndex = (nMinIndex > nIndex) ? nIndex : nMinIndex;
1862 nMaxIndex = (nMaxIndex < nIndex) ? nIndex : nMaxIndex;
1865 for(indIt = nMinIndex ; indIt <= nMaxIndex; indIt++) {
1866 if(myRangeManager.Flag(indIt) == 2) {
1867 bFound = Standard_True;
1875 Standard_Real parUF = aRangeU.First(), parUL = aRangeU.Last();
1876 Standard_Real parVF = aRangeV.First(), parVL = aRangeV.Last();
1878 if(aRangeSPrev.IsEqual(anItS.Value())) {
1879 anExtremaGen.Perform(myCurve, 10, anarg1, anarg2, Tol);
1882 anExtremaGen.Initialize(mySurface, 10, 10, parUF, parUL, parVF, parVL, Tol);
1883 anExtremaGen.Perform(myCurve, 10, anarg1, anarg2, Tol);
1886 if(anExtremaGen.IsDone() && (anExtremaGen.NbExt() > 0)) {
1888 for(Standard_Integer j = 1 ; j <= anExtremaGen.NbExt(); j++) {
1890 if(anExtremaGen.SquareDistance(j) < myCriteria * myCriteria) {
1894 p1 = anExtremaGen.PointOnCurve(j);
1895 p2 = anExtremaGen.PointOnSurface(j);
1896 Standard_Real U, V, T;
1900 if (myCurve.IsPeriodic())
1901 T = ElCLib::InPeriod(T, anarg1, anarg1 + myCurve.Period());
1902 if (mySurface.IsUPeriodic())
1903 U = ElCLib::InPeriod(U, parUF, parUF + mySurface.UPeriod());
1904 if (mySurface.IsVPeriodic())
1905 V = ElCLib::InPeriod(V, parVF, parVF + mySurface.VPeriod());
1907 //To avoid occasional going out of boundaries because of numerical
1909 if(U < myUMinParameter) U = myUMinParameter;
1910 if(U > myUMaxParameter) U = myUMaxParameter;
1911 if(V < myVMinParameter) V = myVMinParameter;
1912 if(V > myVMaxParameter) V = myVMaxParameter;
1914 Standard_Integer aNbRanges = myRangeManager.Length();
1915 ComputeRangeFromStartPoint(Standard_False, T, U, V);
1916 ComputeRangeFromStartPoint(Standard_True, T, U, V);
1918 if(aNbRanges == myRangeManager.Length()) {
1919 SetEmptyResultRange(T, myRangeManager);
1925 myRangeManager.InsertRange(anarg1, anarg2, 0);
1928 aRangeSPrev = anItS.Value();
1932 aCurveData.ListRangeOut(aListOut);
1936 if(bAllowSamplingC) {
1937 IntTools_ListIteratorOfListOfCurveRangeSample anItC(aListOut);
1939 for(; anItC.More(); anItC.Next()) {
1940 IntTools_Range aRangeC =anItC.Value().GetRange(myFirstParameter, myLastParameter, nbSampleC);
1941 myRangeManager.InsertRange(aRangeC.First(), aRangeC.Last(), 1);
1944 ComputeNearRangeBoundaries();
1946 aSurfaceData.ClearGrid();
1948 return Standard_True;
1951 // ======================================================================================================================
1952 // function: TestComputeCoinside
1954 // ======================================================================================================================
1955 Standard_Boolean IntTools_BeanFaceIntersector::TestComputeCoinside()
1957 Standard_Real cfp = myFirstParameter, clp = myLastParameter;
1958 const Standard_Integer nbSeg = 23;
1959 Standard_Real cdp = (clp - cfp) / (Standard_Real )nbSeg;
1961 Standard_Integer i = 0;
1965 if(Distance(cfp, U, V) > myCriteria)
1966 return Standard_False;
1969 ComputeRangeFromStartPoint(Standard_True, cfp, U, V);
1972 Standard_Integer aFoundIndex = myRangeManager.GetIndex(clp, Standard_False );
1974 if(aFoundIndex != 0) {
1975 if(myRangeManager.Flag(aFoundIndex) == 2)
1976 return Standard_True;
1979 if(Distance(clp, U, V) > myCriteria)
1980 return Standard_False;
1983 ComputeRangeFromStartPoint(Standard_False, clp, U, V);
1986 for(i = 1; i < nbSeg; i++) {
1987 Standard_Real aPar = (cfp+((Standard_Real)i)*cdp);
1989 if(Distance(aPar, U, V) > myCriteria)
1990 return Standard_False;
1992 Standard_Integer aNbRanges = myRangeManager.Length();
1993 ComputeRangeFromStartPoint(Standard_False, aPar, U, V);
1994 ComputeRangeFromStartPoint(Standard_True, aPar, U, V);
1996 if(aNbRanges == myRangeManager.Length()) {
1997 SetEmptyResultRange(aPar, myRangeManager);
2001 return Standard_True;
2004 // Modified by skv - Wed Nov 2 15:21:11 2005 Optimization Begin
2005 // ---------------------------------------------------------------------------------
2006 // static function: GetSurfaceBox
2008 // ---------------------------------------------------------------------------------
2009 Bnd_Box GetSurfaceBox(const Handle(Geom_BSplineSurface) &theSurf,
2010 const Standard_Real theFirstU,
2011 const Standard_Real theLastU,
2012 const Standard_Real theFirstV,
2013 const Standard_Real theLastV,
2014 const Standard_Real theTolerance,
2015 IntTools_SurfaceRangeLocalizeData &theSurfaceData)
2019 BuildBox(theSurf, theFirstU, theLastU, theFirstV, theLastV,
2020 theSurfaceData, aTotalBox);
2022 aTotalBox.Enlarge(theTolerance);
2027 // ---------------------------------------------------------------------------------
2028 // static function: ComputeGridPoints
2030 // ---------------------------------------------------------------------------------
2031 void ComputeGridPoints
2032 (const Handle(Geom_BSplineSurface) &theSurf,
2033 const Standard_Real theFirstU,
2034 const Standard_Real theLastU,
2035 const Standard_Real theFirstV,
2036 const Standard_Real theLastV,
2037 const Standard_Real theTolerance,
2038 IntTools_SurfaceRangeLocalizeData &theSurfaceData)
2043 Standard_Integer aNbSamples[2] = { theSurf->UDegree(),
2044 theSurf->VDegree() };
2045 Standard_Integer aNbKnots[2] = { theSurf->NbUKnots(),
2046 theSurf->NbVKnots() };
2047 TColStd_Array1OfReal aKnotsU(1, aNbKnots[0]);
2048 TColStd_Array1OfReal aKnotsV(1, aNbKnots[1]);
2050 theSurf->UKnots(aKnotsU);
2051 theSurf->VKnots(aKnotsV);
2053 Standard_Integer iLmI;
2054 Standard_Integer iMin[2] = { -1, -1 };
2055 Standard_Integer iMax[2] = { -1, -1 };
2056 Standard_Integer aNbGridPnts[2];
2057 Standard_Real aFPar[2] = { theFirstU, theFirstV};
2058 Standard_Real aLPar[2] = { theLastU, theLastV};
2059 Standard_Real aFpTol[2] = { aFPar[0] + theTolerance,
2060 aFPar[1] + theTolerance };
2061 Standard_Real aFmTol[2] = { aFPar[0] - theTolerance,
2062 aFPar[1] - theTolerance };
2063 Standard_Real aLpTol[2] = { aLPar[0] + theTolerance,
2064 aLPar[1] + theTolerance };
2065 Standard_Real aLmTol[2] = { aLPar[0] - theTolerance,
2066 aLPar[1] - theTolerance };
2069 // Compute number of U and V grid points.
2070 for (j = 0; j < 2; j++) {
2071 const TColStd_Array1OfReal &aKnots = (j == 0) ? aKnotsU : aKnotsV;
2073 for (i = 1; i <= aNbKnots[j] && (iMin[j] == -1 || iMax[j] == -1); i++) {
2074 if (iMin[j] == -1 && aFpTol[j] < aKnots.Value(i))
2077 iLmI = aNbKnots[j] - i + 1;
2079 if (iMax[j] == -1 && aLmTol[j] > aKnots.Value(iLmI))
2083 // If indices are not found, return.
2084 //if (iMin[j] == -1 || iMax[j] == -1)
2090 iMax[j] = aNbKnots[j];
2095 if (iMax[j] > aNbKnots[j])
2096 iMax[j] = aNbKnots[j];
2098 if (iMax[j] < iMin[j])
2101 if (iMax[j] == iMin[j]) {
2106 if (iMax[j] > aNbKnots[j])
2107 iMax[j] = aNbKnots[j];
2111 aNbGridPnts[j] = (iMax[j] - iMin[j])*aNbSamples[j] + 1;
2113 // Setting the number of grid points.
2115 theSurfaceData.SetRangeUGrid(aNbGridPnts[j]);
2117 theSurfaceData.SetRangeVGrid(aNbGridPnts[j]);
2119 // Setting the first and last parameters.
2120 Standard_Integer iAbs = 1;
2121 Standard_Real aMinPar;
2122 Standard_Real aMaxPar = (j == 0) ? theLastU : theLastV;
2124 for (i = iMin[j]; i < iMax[j]; i++) {
2125 // Get the first parameter.
2128 if (aFmTol[j] > aKnots.Value(iMin[j]))
2131 aMinPar = aKnots.Value(iMin[j]);
2133 aMinPar = aKnots.Value(i);
2136 // Get the last parameter.
2137 if (i == iMax[j] - 1) {
2139 if (aLpTol[j] < aKnots.Value(iMax[j]))
2142 aMaxPar = aKnots.Value(iMax[j]);
2144 aMaxPar = aKnots.Value(i + 1);
2147 // Compute grid parameters.
2148 Standard_Real aDelta = (aMaxPar - aMinPar)/aNbSamples[j];
2150 for (k = 0; k < aNbSamples[j]; k++, aMinPar += aDelta) {
2152 theSurfaceData.SetUParam(iAbs++, aMinPar);
2154 theSurfaceData.SetVParam(iAbs++, aMinPar);
2158 // Add the last parameter
2160 theSurfaceData.SetUParam(iAbs++, aMaxPar);
2162 theSurfaceData.SetVParam(iAbs++, aMaxPar);
2165 // Compute of grid points.
2167 Standard_Real aParU;
2168 Standard_Real aParV;
2170 for (i = 1; i <= aNbGridPnts[0]; i++) {
2171 aParU = theSurfaceData.GetUParam(i);
2173 for (j = 1; j <= aNbGridPnts[1]; j++) {
2174 aParV = theSurfaceData.GetVParam(j);
2176 theSurf->D0(aParU, aParV, aPnt);
2177 theSurfaceData.SetGridPoint(i, j, aPnt);
2181 // Compute deflection.
2182 Standard_Real aDef = 0.;
2183 // Standard_Real aDefLin;
2184 // Standard_Real aParMid;
2185 // Standard_Real aParConst;
2186 // Standard_Real aDistPP;
2191 // // Compute DU deflection.
2192 // for (i = 1; i < aNbGridPnts[0]; i++) {
2193 // aParMid = 0.5*(theSurfaceData.GetUParam(i + 1) +
2194 // theSurfaceData.GetUParam(i));
2196 // for (j = 1; j <= aNbGridPnts[1]; j++) {
2197 // const gp_Pnt &thePnt1 = theSurfaceData.GetGridPoint(i, j);
2198 // const gp_Pnt &thePnt2 = theSurfaceData.GetGridPoint(i + 1, j);
2200 // aVec.SetXYZ(thePnt2.XYZ().Subtracted(thePnt1.XYZ()));
2201 // aDistPP = aVec.Magnitude();
2203 // if (aDistPP > theTolerance) {
2204 // // Computation of a distance of a middle point from the line P1 - P2.
2205 // aParConst = theSurfaceData.GetVParam(j);
2206 // theSurf->D0(aParMid, aParConst, aPntMid);
2207 // aCoord = aPntMid.XYZ();
2208 // aCoord.Subtract(thePnt1.XYZ());
2209 // aCoord.Cross (aVec.XYZ());
2210 // aCoord.Divide(aDistPP);
2211 // aDefLin = aCoord.Modulus();
2213 // if (aDefLin > aDef)
2219 // // Compute DV deflection.
2220 // for (j = 1; j < aNbGridPnts[1]; j++) {
2221 // aParMid = 0.5*(theSurfaceData.GetVParam(j + 1) +
2222 // theSurfaceData.GetVParam(j));
2224 // for (i = 1; i <= aNbGridPnts[0]; i++) {
2225 // const gp_Pnt &thePnt1 = theSurfaceData.GetGridPoint(i, j);
2226 // const gp_Pnt &thePnt2 = theSurfaceData.GetGridPoint(i, j + 1);
2228 // aVec.SetXYZ(thePnt2.XYZ().Subtracted(thePnt1.XYZ()));
2229 // aDistPP = aVec.Magnitude();
2231 // if (aDistPP > theTolerance) {
2232 // // Computation of a distance of a middle point from the line P1 - P2.
2233 // aParConst = theSurfaceData.GetUParam(i);
2234 // theSurf->D0(aParConst, aParMid, aPntMid);
2235 // aCoord = aPntMid.XYZ();
2236 // aCoord.Subtract(thePnt1.XYZ());
2237 // aCoord.Cross (aVec.XYZ());
2238 // aCoord.Divide(aDistPP);
2239 // aDefLin = aCoord.Modulus();
2241 // if (aDefLin > aDef)
2247 if (theTolerance > aDef)
2248 aDef = theTolerance;
2251 theSurfaceData.SetGridDeflection(aDef);
2254 // ---------------------------------------------------------------------------------
2255 // static function: BuildBox
2256 // purpose: Compute bounding box.
2257 // ---------------------------------------------------------------------------------
2258 void BuildBox(const Handle(Geom_BSplineSurface) &theSurf,
2259 const Standard_Real theFirstU,
2260 const Standard_Real theLastU,
2261 const Standard_Real theFirstV,
2262 const Standard_Real theLastV,
2263 IntTools_SurfaceRangeLocalizeData &theSurfaceData,
2268 Standard_Integer aNbUPnts;
2269 Standard_Integer aNbVPnts;
2270 Standard_Real aParam;
2273 theSurfaceData.SetFrame(theFirstU, theLastU, theFirstV, theLastV);
2274 aNbUPnts = theSurfaceData.GetNBUPointsInFrame();
2275 aNbVPnts = theSurfaceData.GetNBVPointsInFrame();
2277 // Add corner points.
2278 theSurf->D0(theFirstU, theFirstV, aPnt);
2280 theSurf->D0(theLastU, theFirstV, aPnt);
2282 theSurf->D0(theFirstU, theLastV, aPnt);
2284 theSurf->D0(theLastU, theLastV, aPnt);
2287 for (i = 1; i <= aNbUPnts; i++) {
2288 // Add top and bottom points.
2289 aParam = theSurfaceData.GetUParamInFrame(i);
2290 theSurf->D0(aParam, theFirstV, aPnt);
2292 theSurf->D0(aParam, theLastV, aPnt);
2295 // Add internal points.
2296 for (j = 1; j <= aNbVPnts; j++) {
2297 const gp_Pnt &aGridPnt = theSurfaceData.GetPointInFrame(i, j);
2299 theBox.Add(aGridPnt);
2303 // Add left and right points.
2304 for (j = 1; j <= aNbVPnts; j++) {
2305 aParam = theSurfaceData.GetVParamInFrame(j);
2306 theSurf->D0(theFirstU, aParam, aPnt);
2308 theSurf->D0(theLastU, aParam, aPnt);
2312 theBox.Enlarge(theSurfaceData.GetGridDeflection());
2314 // Modified by skv - Wed Nov 2 15:21:11 2005 Optimization End
2317 // ---------------------------------------------------------------------------------
2318 // static function: MergeSolutions
2320 // ---------------------------------------------------------------------------------
2321 static void MergeSolutions(const IntTools_ListOfCurveRangeSample& theListCurveRange,
2322 const IntTools_ListOfSurfaceRangeSample& theListSurfaceRange,
2323 IntTools_ListOfCurveRangeSample& theListCurveRangeSort,
2324 IntTools_ListOfSurfaceRangeSample& theListSurfaceRangeSort) {
2326 IntTools_ListIteratorOfListOfCurveRangeSample anItC2;
2327 IntTools_ListIteratorOfListOfSurfaceRangeSample anItS1(theListSurfaceRange), anItS2;
2328 IntTools_MapOfSurfaceSample aMapToAvoid;
2330 for(; anItS1.More(); anItS1.Next()) {
2331 const IntTools_SurfaceRangeSample& aRangeS = anItS1.Value();
2333 if(aMapToAvoid.Contains(aRangeS))
2335 aMapToAvoid.Add(aRangeS);
2337 anItC2.Initialize(theListCurveRange);
2338 anItS2.Initialize(theListSurfaceRange);
2340 for(; anItS2.More() && anItC2.More(); anItS2.Next(), anItC2.Next()) {
2341 if(aRangeS.IsEqual(anItS2.Value())) {
2342 theListCurveRangeSort.Append(anItC2.Value());
2343 theListSurfaceRangeSort.Append(anItS2.Value());
2349 // ---------------------------------------------------------------------------------
2350 // static function: CheckSampling
2352 // ---------------------------------------------------------------------------------
2353 static void CheckSampling(const IntTools_CurveRangeSample& theCurveRange,
2354 const IntTools_SurfaceRangeSample& theSurfaceRange,
2355 const IntTools_CurveRangeLocalizeData& theCurveData,
2356 const IntTools_SurfaceRangeLocalizeData& theSurfaceData,
2357 const Standard_Real DiffC,
2358 const Standard_Real DiffU,
2359 const Standard_Real DiffV,
2360 Standard_Boolean& bAllowSamplingC,
2361 Standard_Boolean& bAllowSamplingU,
2362 Standard_Boolean& bAllowSamplingV) {
2364 const Standard_Real dLimit = 1000;
2365 bAllowSamplingC = Standard_True;
2366 bAllowSamplingU = Standard_True;
2367 bAllowSamplingV = Standard_True;
2370 if((pow((Standard_Real)theCurveData.GetNbSample(), (Standard_Real )(theCurveRange.GetDepth() + 1)) > dLimit) ||
2371 ((DiffC / theCurveData.GetNbSample()) < theCurveData.GetMinRange())) {
2372 bAllowSamplingC = Standard_False;
2375 if((pow((Standard_Real )theSurfaceData.GetNbSampleU(), (Standard_Real )(theSurfaceRange.GetDepthU() + 1)) > dLimit) ||
2376 ((DiffU / theSurfaceData.GetNbSampleU()) < theSurfaceData.GetMinRangeU())) {
2377 bAllowSamplingU = Standard_False;
2381 if((pow((Standard_Real )theSurfaceData.GetNbSampleV(), (Standard_Real )(theSurfaceRange.GetDepthV() + 1)) > dLimit) ||
2382 ((DiffV / theSurfaceData.GetNbSampleV()) < theSurfaceData.GetMinRangeV())) {
2383 bAllowSamplingV = Standard_False;