1 // Copyright (c) 1999-2012 OPEN CASCADE SAS
3 // The content of this file is subject to the Open CASCADE Technology Public
4 // License Version 6.5 (the "License"). You may not use the content of this file
5 // except in compliance with the License. Please obtain a copy of the License
6 // at http://www.opencascade.org and read it completely before using this file.
8 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
9 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
11 // The Original Code and all software distributed under the License is
12 // distributed on an "AS IS" basis, without warranty of any kind, and the
13 // Initial Developer hereby disclaims all such warranties, including without
14 // limitation, any warranties of merchantability, fitness for a particular
15 // purpose or non-infringement. Please see the License for the specific terms
16 // and conditions governing the rights and limitations under the License.
18 #include <IntTools_BeanBeanIntersector.ixx>
20 #include <IntTools_Root.hxx>
21 #include <Precision.hxx>
22 #include <Extrema_POnCurv.hxx>
23 #include <BRep_Tool.hxx>
24 #include <Geom_Curve.hxx>
25 #include <TColStd_Array1OfReal.hxx>
26 #include <TColStd_Array1OfInteger.hxx>
27 #include <IntTools_CArray1OfReal.hxx>
29 #include <Intf_Array1OfLin.hxx>
30 #include <Bnd_Box.hxx>
31 #include <Extrema_ExtCC.hxx>
32 #include <Extrema_ExtElC.hxx>
33 #include <Extrema_LocateExtPC.hxx>
34 #include <gp_Circ.hxx>
35 #include <gp_Elips.hxx>
36 #include <IntTools.hxx>
38 #include <Geom_Line.hxx>
39 #include <GeomAdaptor_HCurve.hxx>
41 static void LocalPrepareArgs(BRepAdaptor_Curve& theCurve,
42 const Standard_Real theFirstParameter,
43 const Standard_Real theLastParameter,
44 Standard_Real& theDeflection,
45 IntTools_CArray1OfReal& theArgs);
47 static Standard_Boolean SetEmptyResultRange(const Standard_Real theParameter,
48 IntTools_MarkedRangeSet& theMarkedRange);
50 // ==================================================================================
51 // function: IntTools_BeanBeanIntersector
53 // ==================================================================================
54 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector() :
56 myFirstParameter1(0.),
58 myFirstParameter2(0.),
62 myCurveResolution1(0.),
64 myIsDone(Standard_False)
68 // ==================================================================================
69 // function: IntTools_BeanBeanIntersector
71 // ==================================================================================
72 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const TopoDS_Edge& theEdge1,
73 const TopoDS_Edge& theEdge2) :
75 myFirstParameter1(0.),
77 myFirstParameter2(0.),
81 myCurveResolution1(0.),
83 myIsDone(Standard_False)
85 Init(theEdge1, theEdge2);
88 // ==================================================================================
89 // function: IntTools_BeanBeanIntersector
91 // ==================================================================================
92 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const BRepAdaptor_Curve& theCurve1,
93 const BRepAdaptor_Curve& theCurve2,
94 const Standard_Real theBeanTolerance1,
95 const Standard_Real theBeanTolerance2) :
97 myFirstParameter1(0.),
99 myFirstParameter2(0.),
100 myLastParameter2(0.),
101 myBeanTolerance1(0.),
102 myBeanTolerance2(0.),
103 myCurveResolution1(0.),
105 myIsDone(Standard_False)
107 Init(theCurve1, theCurve2, theBeanTolerance1, theBeanTolerance2);
110 // ==================================================================================
111 // function: IntTools_BeanBeanIntersector
113 // ==================================================================================
114 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const BRepAdaptor_Curve& theCurve1,
115 const BRepAdaptor_Curve& theCurve2,
116 const Standard_Real theFirstParOnCurve1,
117 const Standard_Real theLastParOnCurve1,
118 const Standard_Real theFirstParOnCurve2,
119 const Standard_Real theLastParOnCurve2,
120 const Standard_Real theBeanTolerance1,
121 const Standard_Real theBeanTolerance2) :
123 myFirstParameter1(0.),
124 myLastParameter1(0.),
125 myFirstParameter2(0.),
126 myLastParameter2(0.),
127 myBeanTolerance1(0.),
128 myBeanTolerance2(0.),
129 myCurveResolution1(0.),
131 myIsDone(Standard_False)
133 Init(theCurve1, theCurve2, theFirstParOnCurve1, theLastParOnCurve1,
134 theFirstParOnCurve2, theLastParOnCurve2,
135 theBeanTolerance1, theBeanTolerance2);
138 // ==================================================================================
141 // ==================================================================================
142 void IntTools_BeanBeanIntersector::Init(const TopoDS_Edge& theEdge1,
143 const TopoDS_Edge& theEdge2)
145 myCurve1.Initialize(theEdge1);
146 myCurve2.Initialize(theEdge2);
148 myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
149 myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
151 SetBeanParameters(Standard_True, myCurve1.FirstParameter(), myCurve1.LastParameter());
152 SetBeanParameters(Standard_False, myCurve2.FirstParameter(), myCurve2.LastParameter());
154 myBeanTolerance1 = BRep_Tool::Tolerance(theEdge1);
155 myBeanTolerance2 = BRep_Tool::Tolerance(theEdge2);
156 myCriteria = myBeanTolerance1 + myBeanTolerance2;
157 myCurveResolution1 = myCurve1.Resolution(myCriteria);
160 // ==================================================================================
163 // ==================================================================================
164 void IntTools_BeanBeanIntersector::Init(const BRepAdaptor_Curve& theCurve1,
165 const BRepAdaptor_Curve& theCurve2,
166 const Standard_Real theBeanTolerance1,
167 const Standard_Real theBeanTolerance2)
169 myCurve1 = theCurve1;
170 myCurve2 = theCurve2;
172 SetBeanParameters(Standard_True, myCurve1.FirstParameter(), myCurve1.LastParameter());
173 SetBeanParameters(Standard_False, myCurve2.FirstParameter(), myCurve2.LastParameter());
175 myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
176 myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
178 myBeanTolerance1 = theBeanTolerance1;
179 myBeanTolerance2 = theBeanTolerance2;
180 myCriteria = myBeanTolerance1 + myBeanTolerance2;
181 myCurveResolution1 = myCurve1.Resolution(myCriteria);
184 // ==================================================================================
187 // ==================================================================================
188 void IntTools_BeanBeanIntersector::Init(const BRepAdaptor_Curve& theCurve1,
189 const BRepAdaptor_Curve& theCurve2,
190 const Standard_Real theFirstParOnCurve1,
191 const Standard_Real theLastParOnCurve1,
192 const Standard_Real theFirstParOnCurve2,
193 const Standard_Real theLastParOnCurve2,
194 const Standard_Real theBeanTolerance1,
195 const Standard_Real theBeanTolerance2)
197 myCurve1 = theCurve1;
198 myCurve2 = theCurve2;
200 myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
201 myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
203 SetBeanParameters(Standard_True, theFirstParOnCurve1, theLastParOnCurve1);
204 SetBeanParameters(Standard_False, theFirstParOnCurve2, theLastParOnCurve2);
206 myBeanTolerance1 = theBeanTolerance1;
207 myBeanTolerance2 = theBeanTolerance2;
208 myCriteria = myBeanTolerance1 + myBeanTolerance2;
209 myCurveResolution1 = myCurve1.Resolution(myCriteria);
212 // ==================================================================================
213 // function: SetBeanParameters
215 // ==================================================================================
216 void IntTools_BeanBeanIntersector::SetBeanParameters(const Standard_Boolean IsFirstBean,
217 const Standard_Real theFirstParOnCurve,
218 const Standard_Real theLastParOnCurve)
221 myFirstParameter1 = theFirstParOnCurve;
222 myLastParameter1 = theLastParOnCurve;
225 myFirstParameter2 = theFirstParOnCurve;
226 myLastParameter2 = theLastParOnCurve;
229 // ==================================================================================
232 // ==================================================================================
233 const IntTools_SequenceOfRanges& IntTools_BeanBeanIntersector::Result() const
238 // ==================================================================================
241 // ==================================================================================
242 void IntTools_BeanBeanIntersector::Result(IntTools_SequenceOfRanges& theResults) const
244 theResults = myResults;
246 // ==================================================================================
249 // ==================================================================================
250 void IntTools_BeanBeanIntersector::Perform()
252 Standard_Boolean bFastComputed;
253 Standard_Integer k, i, iFlag, aNbRanges, aNbResults;
254 Standard_Real aMidParameter, aCoeff, aParamDist, aPPC;
255 Standard_Real aCriteria2, aD2;
257 IntTools_CArray1OfReal aParams;
258 IntTools_Range aRange2, aRange;
260 myIsDone = Standard_False;
263 LocalPrepareArgs(myCurve1, myFirstParameter1, myLastParameter1, myDeflection, aParams);
265 myRangeManager.SetRanges(aParams, 0);
267 aNbRanges=myRangeManager.Length();
272 bFastComputed=FastComputeIntersection();
274 aRange.SetFirst(myFirstParameter1);
275 aRange.SetLast (myLastParameter1);
276 myResults.Append(aRange);
277 myIsDone = Standard_True;
281 ComputeRoughIntersection();
283 //Standard_Real aMidParameter = (myFirstParameter2 + myLastParameter2) * 0.5;
285 aMidParameter = myFirstParameter2+(myLastParameter2-myFirstParameter2)*aCoeff;
287 for(k = 0; k < 2; ++k) {
289 aRange2.SetFirst(myFirstParameter2);
290 aRange2.SetLast(aMidParameter);
293 aRange2.SetFirst(aMidParameter);
294 aRange2.SetLast(myLastParameter2);
297 ComputeUsingExtrema(aRange2);
299 ComputeNearRangeBoundaries(aRange2);
304 // 0 - just initialized
305 // 1 - non-intersected
306 // 2 - roughly intersected
307 // 3 - intersection is not done
308 // 4 - coincided range
310 aPPC=Precision::PConfusion();
311 aCriteria2=myCriteria*myCriteria;
312 aNbRanges=myRangeManager.Length();
314 for(i=1; i<=aNbRanges; ++i) {
315 iFlag=myRangeManager.Flag(i);
318 aRange=myRangeManager.Range(i);
319 aNbResults=myResults.Length();
321 const IntTools_Range& aLastRange = myResults.Last();
323 aParamDist = Abs(aRange.First() - aLastRange.Last());
324 if(aParamDist > myCurveResolution1) {
325 myResults.Append(aRange);
328 aPi=myCurve1.Value(aRange.First());
329 aPh=myCurve1.Value(aLastRange.Last());
330 aD2=aPi.SquareDistance(aPh);
331 if(aParamDist<aPPC || aD2<aCriteria2) {
332 myResults.ChangeValue(aNbResults).SetLast(aRange.Last());
335 myResults.Append(aRange);
340 myResults.Append(aRange);
343 } // for(i = 1; i <= myRangeManager.Length(); i++) {
344 myIsDone = Standard_True;
346 // ==================================================================================
347 // function: FastComputeIntersection
349 // ==================================================================================
350 Standard_Boolean IntTools_BeanBeanIntersector::FastComputeIntersection()
352 Standard_Boolean aresult;
353 GeomAbs_CurveType aCT1, aCT2;
355 aresult = Standard_False;
357 aCT1=myCurve1.GetType();
358 aCT2=myCurve2.GetType();
365 if(aCT1==GeomAbs_Line) {
366 Standard_Real par1, par2;
368 if((Distance(myFirstParameter1, par1) < myCriteria) &&
369 (Distance(myLastParameter1, par2) < myCriteria)) {
371 if((par1 >= myFirstParameter2) && (par1 <= myLastParameter2) &&
372 (par2 >= myFirstParameter2) && (par2 <= myLastParameter2)) {
373 myRangeManager.InsertRange(myFirstParameter1, myLastParameter1, 4);
374 aresult = Standard_True;
381 if(aCT1==GeomAbs_Circle) {
382 Standard_Real anAngle, aPA, aDistLoc, aDist, aDiff, aR1, aR2;
383 gp_Circ aCirc1, aCirc2;
386 aCirc1=myCurve1.Circle();
387 aCirc2=myCurve2.Circle();
391 aPA=Precision::Angular();
392 aDir1 = aCirc1.Axis().Direction();
393 aDir2 = aCirc2.Axis().Direction();
395 anAngle = aDir1.Angle(aDir2);
400 const gp_Pnt& aPLoc1=aCirc1.Location();
401 const gp_Pnt& aPLoc2=aCirc2.Location();
402 aDistLoc = aPLoc1.Distance(aPLoc2);
406 if(Abs(aDist) > myCriteria) {
410 Standard_Real aSinPA, atmpvalue, aprojectedradius;
413 atmpvalue = aR1*aSinPA;
414 atmpvalue *= atmpvalue;
415 aprojectedradius = sqrt(aR1*aR1 - atmpvalue);
417 aDiff = aprojectedradius - aR2;
418 aDist = aDistLoc + sqrt((aDiff * aDiff) + atmpvalue);
419 if(Abs(aDist) > myCriteria) {
423 Standard_Boolean newparfound;
425 Standard_Real afirstpar, alastpar, par1, par2, apar;
427 afirstpar = myFirstParameter1;
428 alastpar = myLastParameter1;
430 for(i = 0; i < 2; i++) {
431 if((Distance(afirstpar, par1) < myCriteria) &&
432 (Distance(alastpar , par2) < myCriteria)) {
434 if(i || Distance((myFirstParameter1 + myLastParameter2) * 0.5, apar) < myCriteria) {
435 myRangeManager.InsertRange(afirstpar, alastpar, 4);
438 aresult = Standard_True;
448 newparfound = Standard_False;
450 if(Distance((myFirstParameter1 + myLastParameter2) * 0.5, apar) < myCriteria) {
451 afirstpar = myFirstParameter1 + myCriteria;
452 alastpar = myLastParameter1 - myCriteria;
453 newparfound = Standard_True;
455 if(alastpar <= afirstpar) {
456 newparfound = Standard_False;
463 }// for(i = 0; i < 2; i++) {
464 } // if(aCT1==GeomAbs_Circle)
467 // ==================================================================================
468 // function: Distance
470 // ==================================================================================
471 Standard_Real IntTools_BeanBeanIntersector::Distance(const Standard_Real theArg,
472 Standard_Real& theArgOnOtherBean)
474 Standard_Real aDistance;
475 Standard_Integer aNbPoints;
478 aDistance=RealLast();
480 aPoint=myCurve1.Value(theArg);
481 //modified by NIZNHY-PKV Thu Jul 01 12:20:52 2010f
482 myProjector.Init(myTrsfCurve2, myFirstParameter2, myLastParameter2);
483 myProjector.Perform(aPoint);
484 //myProjector.Init(aPoint, myTrsfCurve2, myFirstParameter2, myLastParameter2);
485 //modified by NIZNHY-PKV Thu Jul 01 12:21:05 2010t
487 aNbPoints=myProjector.NbPoints();
489 theArgOnOtherBean = myProjector.LowerDistanceParameter();
490 aDistance=myProjector.LowerDistance();
494 Standard_Real aDistance1, aDistance2;
496 aDistance1 = aPoint.Distance(myCurve2.Value(myFirstParameter2));
497 aDistance2 = aPoint.Distance(myCurve2.Value(myLastParameter2));
499 theArgOnOtherBean = myLastParameter2;
500 aDistance=aDistance2;
501 if(aDistance1 < aDistance2) {
502 theArgOnOtherBean = myFirstParameter2;
503 aDistance=aDistance1;
508 // ==================================================================================
509 // function: ComputeRoughIntersection
511 // ==================================================================================
512 void IntTools_BeanBeanIntersector::ComputeRoughIntersection()
514 Standard_Boolean isintersection;
515 Standard_Integer i, aNbArgs, aNbArgs1, aNbRanges, j, aNbLines, k, pIt, extIt, iFlag;
516 Standard_Real aDeflection, aGPR, aCurDeflection, aT1, aT2, aD;
517 Standard_Real aMaxDistance, aDistance, aPPC, aPrm1, aPrm2, aPPA;
518 GeomAbs_CurveType aCT1, aCT2;
519 gp_Pnt aPoint1, aPoint2, aMidPOnCurve, aMidPOnLine, aP1, aP2;
520 IntTools_CArray1OfReal anArgs;
521 LocalPrepareArgs(myCurve2, myFirstParameter2, myLastParameter2, aDeflection, anArgs);
523 aNbArgs=anArgs.Length();
528 aCT1=myCurve1.GetType();
529 aCT2=myCurve2.GetType();
530 aGPR=gp::Resolution();
531 aPPC=Precision::PConfusion();
532 aPPA=Precision::Angular();
535 Intf_Array1OfLin aLines(1, aNbArgs1);
536 TColStd_Array1OfInteger aLineFlags(1, aNbArgs1);
537 TColStd_Array1OfReal aDistances(1, aNbArgs1);
540 aPoint1 = myCurve2.Value(aT1);
541 for(i=1; i<aNbArgs; ++i) {
543 aPoint2 = myCurve2.Value(aT2);
544 gp_Vec aVec(aPoint1, aPoint2);
546 aDistances.SetValue(i, aD);
549 aLineFlags.SetValue(i, 0);
552 aLineFlags.SetValue(i, 1);
553 gp_Lin aLine(aPoint1, gp_Dir(aVec));
554 aLines.SetValue(i, aLine);
556 if((aCT2 == GeomAbs_BezierCurve) ||
557 (aCT2 == GeomAbs_BSplineCurve)) {
558 aMidPOnCurve = myCurve2.Value((aT1+aT2) * 0.5);
559 aMidPOnLine = ElCLib::Value((aDistances(i)*0.5), aLine);
560 aCurDeflection = aMidPOnCurve.Distance(aMidPOnLine);
561 if(aCurDeflection > aDeflection) {
562 aDeflection = aCurDeflection;
570 aNbLines=aLines.Upper();
571 aMaxDistance = myCriteria + myDeflection + aDeflection;
573 aT1=myRangeManager.Range(1).First();
574 aPoint1 = myCurve1.Value(aT1);
575 aNbRanges=myRangeManager.Length();
576 for(i = 1; i <= aNbRanges; ++i) {
577 const IntTools_Range& aRange = myRangeManager.Range(i);
579 aPoint2 = myCurve1.Value(aT2);
581 iFlag=myRangeManager.Flag(i);
582 if(iFlag==4) {// coincided
588 myRangeManager.SetFlag(i, 1); // not intersected
593 aBox1.Enlarge(myBeanTolerance1 + myDeflection);
595 gp_Vec aVec(aPoint1, aPoint2);
597 aDistance=aVec.Magnitude();
598 if(aDistance <= aGPR) {
599 myRangeManager.SetFlag(i, 0);
603 gp_Lin aLine(aPoint1, gp_Dir(aVec));
605 if((aCT1 == GeomAbs_BezierCurve) ||
606 (aCT1 == GeomAbs_BSplineCurve)) {
607 aMidPOnCurve = myCurve1.Value((aRange.First() + aRange.Last()) * 0.5);
608 aMidPOnLine = ElCLib::Value((aDistance*0.5), aLine);
609 aCurDeflection = aMidPOnCurve.Distance(aMidPOnLine);
610 if(myDeflection < aCurDeflection) {
611 aMaxDistance += aCurDeflection - myDeflection;
612 myDeflection = aCurDeflection;
616 for(j=1; j<=aNbLines; ++j) {
618 myRangeManager.SetFlag(i, 0);
622 const gp_Lin& aL2=aLines(j);
623 //Handle(Geom_Line) aC2=new Geom_Line(aL2); // DEB ft
625 aP1=ElCLib::Value(0., aL2);
626 aP2=ElCLib::Value(aD, aL2);
628 Extrema_ExtElC anExtrema(aLine, aL2, aPPA);
629 if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
630 isintersection = Standard_False;
632 if(anExtrema.IsParallel()) {
633 isintersection = (anExtrema.SquareDistance(1) < aMaxDistance * aMaxDistance);
636 for(k = 1; !isintersection && k <= anExtrema.NbExt(); ++k) {
637 if(anExtrema.SquareDistance(k) < aMaxDistance * aMaxDistance) {
638 Extrema_POnCurv P1, P2;
639 anExtrema.Points(k, P1, P2);
640 aPrm1=P1.Parameter();
641 aPrm2=P2.Parameter();
642 if((aPrm1 >= -aMaxDistance) && (aPrm1 <= aDistance+aMaxDistance) &&
643 (aPrm2 >= -aMaxDistance) && (aPrm2 <= aD+aMaxDistance)) {
644 isintersection = Standard_True;
647 Extrema_ExtPElC aPointProjector;
649 for(pIt = 0; !isintersection && (pIt < 4); ++pIt) {
653 //Extrema_ExtPElC(aPoint1, aLines(j), aPPC, 0., aDistances(j));
654 Extrema_ExtPElC(aPoint1, aL2, aPPC, -aMaxDistance, aD+aMaxDistance);
659 //Extrema_ExtPElC(aPoint2, aLines(j), aPPC, 0., aD);
660 Extrema_ExtPElC(aPoint2, aL2, aPPC, -aMaxDistance, aD+aMaxDistance);
665 //Extrema_ExtPElC(ElCLib::Value(0., aLines(j)), aLine, aPPC, 0., aDistance);
666 Extrema_ExtPElC(aP1, aLine, aPPC, -aMaxDistance, aDistance+aMaxDistance);
671 //Extrema_ExtPElC(ElCLib::Value(aDistances(j), aLines(j)), aLine, aPPC, 0., aDistance);
672 Extrema_ExtPElC(aP2, aLine, aPPC, -aMaxDistance, aDistance+aMaxDistance);
680 if(aPointProjector.IsDone()) {
681 Standard_Real aMaxDistance2 = aMaxDistance * aMaxDistance;
682 for(extIt = 1; extIt <= aPointProjector.NbExt(); extIt++) {
683 if(aPointProjector.SquareDistance(extIt) < aMaxDistance2) {
684 isintersection = Standard_True;
690 }//if(anExtrema.Value(k) < aMaxDistance) {
691 }//for(k = 1; !isintersection && k <= anExtrema.NbExt(); k++) {
695 myRangeManager.SetFlag(i, 2); // roughly intersected
698 }//if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
701 aBox2.Add(myCurve2.Value(anArgs(j-1)));
702 aBox2.Add(myCurve2.Value(anArgs(j)));
703 aBox2.Enlarge(myBeanTolerance2 + aDeflection);
705 if(!aBox1.IsOut(aBox2)) {
706 myRangeManager.SetFlag(i, 2); // roughly intersected
716 // ==================================================================================
717 // function: ComputeUsingExtrema
719 // ==================================================================================
720 void IntTools_BeanBeanIntersector::ComputeUsingExtrema(const IntTools_Range& theRange2)
723 //Extrema_ExtCC is reused throughout this method to store caches computed on
724 //theRange2. However it is actually used only in a few calls of
725 //ComputeUsingExtrema(), so using a default constructor would add unnecessary overhead
726 //of initialization its internal fields. Since it is not manipulated by Handle then
727 //we will use a pointer to it and initialize it only when needed.
728 Extrema_ExtCC *apExtrema = 0;
729 Handle(GeomAdaptor_HCurve) aHCurve1, aHCurve2; //will be initialized later, only if needed
730 //handles are used to guard pointers to GeomAdaptor_Curve inside Extrema
731 Standard_Real aCriteria2 = myCriteria * myCriteria;
732 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
734 if(myRangeManager.Flag(i) == 2 || myRangeManager.Flag(i) == 0) {
735 const IntTools_Range& aParamRange = myRangeManager.Range(i);
737 if(aParamRange.Last() - aParamRange.First() < Precision::PConfusion()) {
739 if(((i > 1) && (myRangeManager.Flag(i-1) == 4)) ||
740 ((i < myRangeManager.Length()) && (myRangeManager.Flag(i+1) == 4))) {
741 myRangeManager.SetFlag(i, 4);
745 if (aHCurve2.IsNull()) {
746 //initialize only once
747 apExtrema = new Extrema_ExtCC;
748 Standard_Real ftmp = theRange2.First() - Precision::PConfusion();
749 Standard_Real ltmp = theRange2.Last() + Precision::PConfusion();
750 ftmp = (ftmp < myFirstParameter2) ? myFirstParameter2 : ftmp;
751 ltmp = (ltmp > myLastParameter2) ? myLastParameter2 : ltmp;
752 aHCurve2 = new GeomAdaptor_HCurve (myTrsfCurve2, ftmp, ltmp);
753 apExtrema->SetCurve (2, aHCurve2->Curve(), theRange2.First(), theRange2.Last());
755 Extrema_ExtCC& anExtrema = *apExtrema;
757 Standard_Real ftmp = aParamRange.First() - Precision::PConfusion();
758 Standard_Real ltmp = aParamRange.Last() + Precision::PConfusion();
759 ftmp = (ftmp < myFirstParameter1) ? myFirstParameter1 : ftmp;
760 ltmp = (ltmp > myLastParameter1) ? myLastParameter1 : ltmp;
761 aHCurve1 = new GeomAdaptor_HCurve (myTrsfCurve1, ftmp, ltmp);
762 anExtrema.SetCurve (1, aHCurve1->Curve(), aParamRange.First(), aParamRange.Last());
766 if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
767 Standard_Integer anOldNbRanges = myRangeManager.Length();
769 if (anExtrema.IsParallel()) {
770 if(anExtrema.SquareDistance(1) < aCriteria2) {
771 Standard_Real theParameter1, theParameter2;
772 Standard_Real adistance1 = Distance(aParamRange.First(), theParameter1);
773 Standard_Real adistance2 = Distance(aParamRange.Last(), theParameter2);
774 Standard_Boolean validdistance1 = (adistance1 < myCriteria);
775 Standard_Boolean validdistance2 = (adistance2 < myCriteria);
777 if (validdistance1 && validdistance2) {
778 myRangeManager.InsertRange(aParamRange.First(), aParamRange.Last(), 4);
783 ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), i, theParameter1, theRange2);
787 ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), i, theParameter2, theRange2);
790 Standard_Real a = aParamRange.First();
791 Standard_Real b = aParamRange.Last();
792 Standard_Real da = adistance1;
793 Standard_Real db = adistance2;
794 Standard_Real asolution = a;
795 Standard_Boolean found = Standard_False;
797 while(((b - a) > myCurveResolution1) && !found) {
798 asolution = (a+b)*0.5;
799 Standard_Real adist = Distance(asolution, theParameter1);
801 if(adist < myCriteria) {
802 found = Standard_True;
817 ComputeRangeFromStartPoint(Standard_False, asolution, i, theParameter1, theRange2);
818 ComputeRangeFromStartPoint(Standard_True, asolution, i, theParameter1, theRange2);
821 myRangeManager.SetFlag(i, 2);
830 for(Standard_Integer j = 1 ; j <= anExtrema.NbExt(); j++) {
831 if(anExtrema.SquareDistance(j) < aCriteria2) {
832 Extrema_POnCurv p1, p2;
833 anExtrema.Points(j, p1, p2);
835 Standard_Integer aNbRanges = myRangeManager.Length();
837 Standard_Integer anIndex = myRangeManager.GetIndex(p1.Parameter(), Standard_False);
839 ComputeRangeFromStartPoint(Standard_False, p1.Parameter(), anIndex, p2.Parameter(), theRange2);
842 anIndex = myRangeManager.GetIndex(p1.Parameter(), Standard_True);
845 ComputeRangeFromStartPoint(Standard_True, p1.Parameter(), anIndex, p2.Parameter(), theRange2);
848 if(aNbRanges == myRangeManager.Length()) {
849 SetEmptyResultRange(p1.Parameter(), myRangeManager);
854 Standard_Integer adifference = myRangeManager.Length() - anOldNbRanges;
856 if(adifference > 0) {
861 myRangeManager.SetFlag(i, 3); // intersection not done.
865 if (apExtrema) delete apExtrema;
868 // ==================================================================================
869 // function: ComputeNearRangeBoundaries
871 // ==================================================================================
872 void IntTools_BeanBeanIntersector::ComputeNearRangeBoundaries(const IntTools_Range& theRange2)
874 Standard_Real theParameter = theRange2.First();
876 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
877 if(myRangeManager.Flag(i) != 3)
880 if((i > 1) && ((myRangeManager.Flag(i-1) == 1) || (myRangeManager.Flag(i-1) == 4))) {
881 myRangeManager.SetFlag(i, 2);
885 const IntTools_Range& aParamRange = myRangeManager.Range(i);
887 if(Distance(aParamRange.First(), theParameter) < myCriteria) {
888 Standard_Integer aNbRanges = myRangeManager.Length();
891 ComputeRangeFromStartPoint(Standard_False, aParamRange.First(), i-1, theParameter, theRange2);
893 ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), i + (myRangeManager.Length() - aNbRanges), theParameter, theRange2);
895 if(aNbRanges == myRangeManager.Length()) {
896 SetEmptyResultRange(aParamRange.First(), myRangeManager);
900 myRangeManager.SetFlag(i, 2);
904 if((myRangeManager.Flag(myRangeManager.Length()) == 3) ||
905 (myRangeManager.Flag(myRangeManager.Length()) == 2)) {
906 const IntTools_Range& aParamRange = myRangeManager.Range(myRangeManager.Length());
908 if(Distance(aParamRange.Last(), theParameter) < myCriteria) {
909 Standard_Integer aNbRanges = myRangeManager.Length();
910 myRangeManager.SetFlag(myRangeManager.Length(), 2);
912 ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), myRangeManager.Length(), theParameter, theRange2);
914 if(aNbRanges == myRangeManager.Length()) {
915 SetEmptyResultRange(aParamRange.Last(), myRangeManager);
919 myRangeManager.SetFlag(myRangeManager.Length(), 2);
924 // ==================================================================================
925 // function: ComputeRangeFromStartPoint
927 // ==================================================================================
928 void IntTools_BeanBeanIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
929 const Standard_Real theParameter,
930 const Standard_Integer theIndex,
931 const Standard_Real theParameter2,
932 const IntTools_Range& theRange2)
935 if(myRangeManager.Flag(theIndex) == 4 ||
936 myRangeManager.Flag(theIndex) == 1)
939 Standard_Integer aValidIndex = theIndex;
940 Standard_Real aMinDelta = myCurveResolution1 * 0.5;
941 Standard_Real aDeltaRestrictor = myLastParameter1 - myFirstParameter1;
943 if(Abs(aDeltaRestrictor) < Precision::PConfusion()) {
947 if(aMinDelta > aDeltaRestrictor) {
948 aMinDelta = aDeltaRestrictor;
950 Standard_Real tenOfMinDelta = aMinDelta * 10.;
951 Standard_Real aDelta = myCurveResolution1;
952 Standard_Real aCurPar = (ToIncreaseParameter) ? (theParameter + aDelta) : (theParameter - aDelta);
953 Standard_Real aPrevPar = theParameter;
954 IntTools_Range aCurrentRange = myRangeManager.Range(aValidIndex);
956 Standard_Boolean BoundaryCondition = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
958 if(BoundaryCondition) {
959 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
960 BoundaryCondition = Standard_False;
963 Standard_Integer loopcounter = 0; // neccesary to have no infinite loop
964 Standard_Real aParameter = theParameter2;
965 Standard_Boolean anotherSolutionFound = Standard_False;
967 Standard_Boolean isboundaryindex = Standard_False;
968 Standard_Boolean isvalidindex = Standard_True;
970 Standard_Real aCriteria2 = myCriteria * myCriteria;
972 while((aDelta >= aMinDelta) && (loopcounter <= 10)) {
973 Standard_Boolean pointfound = Standard_False;
975 gp_Pnt aPoint = myCurve1.Value(aCurPar);
976 GeomAdaptor_Curve aCurve2(myTrsfCurve2, theRange2.First(), theRange2.Last());
978 Extrema_LocateExtPC anExtrema(aPoint, aCurve2, aParameter, theRange2.First(), theRange2.Last(), 1.e-10);
980 if(anExtrema.IsDone()) {
981 if(anExtrema.SquareDistance() < aCriteria2) {
982 Extrema_POnCurv aPOnCurv = anExtrema.Point();
983 aParameter = aPOnCurv.Parameter();
984 pointfound = Standard_True;
988 // pointfound = (Distance(aCurPar, aParameter) < myCriteria);
989 Standard_Real afoundparam = aParameter;
991 if(Distance(aCurPar, afoundparam) < myCriteria) {
992 aParameter = afoundparam;
993 pointfound = Standard_True;
999 anotherSolutionFound = Standard_True;
1001 if(BoundaryCondition && (isboundaryindex || !isvalidindex))
1005 aDeltaRestrictor = aDelta;
1008 // if pointfound decide to increase aDelta using derivative of distance function
1011 aDelta = (pointfound) ? (aDelta * 2.) : (aDelta * 0.5);
1012 aDelta = (aDelta < aDeltaRestrictor) ? aDelta : aDeltaRestrictor;
1013 aCurPar = (ToIncreaseParameter) ? (aPrevPar + aDelta) : (aPrevPar - aDelta);
1015 BoundaryCondition = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1017 isboundaryindex = Standard_False;
1018 isvalidindex = Standard_True;
1020 if(BoundaryCondition) {
1021 isboundaryindex = ((!ToIncreaseParameter && (aValidIndex == 1)) ||
1022 (ToIncreaseParameter && (aValidIndex == myRangeManager.Length())));
1024 if(!isboundaryindex) {
1026 Standard_Integer aFlag = (ToIncreaseParameter) ? myRangeManager.Flag(aValidIndex + 1) : myRangeManager.Flag(aValidIndex - 1);
1028 if(aFlag != 1 && aFlag != 4) {
1029 aValidIndex = (ToIncreaseParameter) ? (aValidIndex + 1) : (aValidIndex - 1);
1030 aCurrentRange = myRangeManager.Range(aValidIndex);
1032 if((ToIncreaseParameter && (aCurPar > aCurrentRange.Last())) ||
1033 (!ToIncreaseParameter && (aCurPar < aCurrentRange.First()))) {
1034 aCurPar = (aCurrentRange.First() + aCurrentRange.Last()) * 0.5;
1039 isvalidindex = Standard_False;
1040 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1045 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1048 if(aDelta < tenOfMinDelta) {
1054 } // end if(BoundaryCondition)
1057 if(anotherSolutionFound) {
1058 if(ToIncreaseParameter)
1059 myRangeManager.InsertRange(theParameter, aPrevPar, 4);
1061 myRangeManager.InsertRange(aPrevPar, theParameter, 4);
1065 // ---------------------------------------------------------------------------------
1066 // static function: LocalPrepareArgs
1068 // ---------------------------------------------------------------------------------
1069 static void LocalPrepareArgs(BRepAdaptor_Curve& theCurve,
1070 const Standard_Real theFirstParameter,
1071 const Standard_Real theLastParameter,
1072 Standard_Real& theDeflection,
1073 IntTools_CArray1OfReal& theArgs) {
1074 Standard_Integer aDiscretization = 30;
1075 Standard_Real aRelativeDeflection = 0.01;
1076 theDeflection = aRelativeDeflection;
1077 Standard_Boolean prepareargs = Standard_True;
1079 switch(theCurve.GetType()) {
1080 case GeomAbs_Line: {
1081 prepareargs = Standard_False;
1082 aDiscretization = 3;
1083 theArgs.Append(theFirstParameter);
1085 if((theLastParameter - theFirstParameter) > Precision::PConfusion()) {
1086 theArgs.Append((theFirstParameter + theLastParameter)*0.5);
1088 theArgs.Append(theLastParameter);
1089 theDeflection = Precision::Confusion();
1092 case GeomAbs_Circle: {
1093 aDiscretization = 23;
1094 theDeflection = aRelativeDeflection * theCurve.Circle().Radius();
1097 case GeomAbs_Ellipse: {
1098 aDiscretization = 40;
1099 theDeflection = 2 * aRelativeDeflection * theCurve.Ellipse().MajorRadius();
1102 case GeomAbs_Hyperbola:
1103 case GeomAbs_Parabola: {
1104 aDiscretization = 40;
1105 theDeflection = aRelativeDeflection;
1108 case GeomAbs_BezierCurve: {
1109 aDiscretization = 30;
1110 theDeflection = aRelativeDeflection;
1113 case GeomAbs_BSplineCurve: {
1114 aDiscretization = 30;
1115 theDeflection = aRelativeDeflection;
1119 aDiscretization = 30;
1120 theDeflection = aRelativeDeflection;
1125 IntTools::PrepareArgs(theCurve, theLastParameter, theFirstParameter, aDiscretization, aRelativeDeflection, theArgs);
1129 // ---------------------------------------------------------------------------------
1130 // static function: SetEmptyResultRange
1132 // ---------------------------------------------------------------------------------
1133 static Standard_Boolean SetEmptyResultRange(const Standard_Real theParameter,
1134 IntTools_MarkedRangeSet& theMarkedRange) {
1136 const TColStd_SequenceOfInteger& anIndices = theMarkedRange.GetIndices(theParameter);
1137 Standard_Boolean add = (anIndices.Length() > 0);
1139 for(Standard_Integer k = 1; k <= anIndices.Length(); k++) {
1140 if(theMarkedRange.Flag(anIndices(k)) == 4) {
1141 add = Standard_False;
1147 theMarkedRange.InsertRange(theParameter, theParameter, 4);