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>
42 void LocalPrepareArgs(BRepAdaptor_Curve& theCurve,
43 const Standard_Real theFirstParameter,
44 const Standard_Real theLastParameter,
45 Standard_Real& theDeflection,
46 IntTools_CArray1OfReal& theArgs);
49 Standard_Boolean SetEmptyResultRange(const Standard_Real theParameter,
50 IntTools_MarkedRangeSet& theMarkedRange);
52 Standard_Integer CheckCoincidence(const Standard_Real aT11,
53 const Standard_Real aT12,
54 const Handle(Geom_Curve)& aC1,
55 const Standard_Real aT21,
56 const Standard_Real aT22,
57 const Handle(Geom_Curve)& aC2,
58 const Standard_Real aCriteria,
59 const Standard_Real aCurveResolution1,
60 GeomAPI_ProjectPointOnCurve& aProjector);
63 // ==================================================================================
64 // function: IntTools_BeanBeanIntersector
66 // ==================================================================================
67 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector() :
69 myFirstParameter1(0.),
71 myFirstParameter2(0.),
75 myCurveResolution1(0.),
77 myIsDone(Standard_False)
81 // ==================================================================================
82 // function: IntTools_BeanBeanIntersector
84 // ==================================================================================
85 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const TopoDS_Edge& theEdge1,
86 const TopoDS_Edge& theEdge2) :
88 myFirstParameter1(0.),
90 myFirstParameter2(0.),
94 myCurveResolution1(0.),
96 myIsDone(Standard_False)
98 Init(theEdge1, theEdge2);
101 // ==================================================================================
102 // function: IntTools_BeanBeanIntersector
104 // ==================================================================================
105 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const BRepAdaptor_Curve& theCurve1,
106 const BRepAdaptor_Curve& theCurve2,
107 const Standard_Real theBeanTolerance1,
108 const Standard_Real theBeanTolerance2) :
110 myFirstParameter1(0.),
111 myLastParameter1(0.),
112 myFirstParameter2(0.),
113 myLastParameter2(0.),
114 myBeanTolerance1(0.),
115 myBeanTolerance2(0.),
116 myCurveResolution1(0.),
118 myIsDone(Standard_False)
120 Init(theCurve1, theCurve2, theBeanTolerance1, theBeanTolerance2);
123 // ==================================================================================
124 // function: IntTools_BeanBeanIntersector
126 // ==================================================================================
127 IntTools_BeanBeanIntersector::IntTools_BeanBeanIntersector(const BRepAdaptor_Curve& theCurve1,
128 const BRepAdaptor_Curve& theCurve2,
129 const Standard_Real theFirstParOnCurve1,
130 const Standard_Real theLastParOnCurve1,
131 const Standard_Real theFirstParOnCurve2,
132 const Standard_Real theLastParOnCurve2,
133 const Standard_Real theBeanTolerance1,
134 const Standard_Real theBeanTolerance2) :
136 myFirstParameter1(0.),
137 myLastParameter1(0.),
138 myFirstParameter2(0.),
139 myLastParameter2(0.),
140 myBeanTolerance1(0.),
141 myBeanTolerance2(0.),
142 myCurveResolution1(0.),
144 myIsDone(Standard_False)
146 Init(theCurve1, theCurve2, theFirstParOnCurve1, theLastParOnCurve1,
147 theFirstParOnCurve2, theLastParOnCurve2,
148 theBeanTolerance1, theBeanTolerance2);
151 // ==================================================================================
154 // ==================================================================================
155 void IntTools_BeanBeanIntersector::Init(const TopoDS_Edge& theEdge1,
156 const TopoDS_Edge& theEdge2)
158 myCurve1.Initialize(theEdge1);
159 myCurve2.Initialize(theEdge2);
161 myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
162 myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
164 SetBeanParameters(Standard_True, myCurve1.FirstParameter(), myCurve1.LastParameter());
165 SetBeanParameters(Standard_False, myCurve2.FirstParameter(), myCurve2.LastParameter());
167 myBeanTolerance1 = BRep_Tool::Tolerance(theEdge1);
168 myBeanTolerance2 = BRep_Tool::Tolerance(theEdge2);
169 myCriteria = myBeanTolerance1 + myBeanTolerance2;
170 myCurveResolution1 = myCurve1.Resolution(myCriteria);
173 // ==================================================================================
176 // ==================================================================================
177 void IntTools_BeanBeanIntersector::Init(const BRepAdaptor_Curve& theCurve1,
178 const BRepAdaptor_Curve& theCurve2,
179 const Standard_Real theBeanTolerance1,
180 const Standard_Real theBeanTolerance2)
182 myCurve1 = theCurve1;
183 myCurve2 = theCurve2;
185 SetBeanParameters(Standard_True, myCurve1.FirstParameter(), myCurve1.LastParameter());
186 SetBeanParameters(Standard_False, myCurve2.FirstParameter(), myCurve2.LastParameter());
188 myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
189 myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
191 myBeanTolerance1 = theBeanTolerance1;
192 myBeanTolerance2 = theBeanTolerance2;
193 myCriteria = myBeanTolerance1 + myBeanTolerance2;
194 myCurveResolution1 = myCurve1.Resolution(myCriteria);
197 // ==================================================================================
200 // ==================================================================================
201 void IntTools_BeanBeanIntersector::Init(const BRepAdaptor_Curve& theCurve1,
202 const BRepAdaptor_Curve& theCurve2,
203 const Standard_Real theFirstParOnCurve1,
204 const Standard_Real theLastParOnCurve1,
205 const Standard_Real theFirstParOnCurve2,
206 const Standard_Real theLastParOnCurve2,
207 const Standard_Real theBeanTolerance1,
208 const Standard_Real theBeanTolerance2)
210 myCurve1 = theCurve1;
211 myCurve2 = theCurve2;
213 myTrsfCurve1 = Handle(Geom_Curve)::DownCast(myCurve1.Curve().Curve()->Transformed(myCurve1.Trsf()));
214 myTrsfCurve2 = Handle(Geom_Curve)::DownCast(myCurve2.Curve().Curve()->Transformed(myCurve2.Trsf()));
216 SetBeanParameters(Standard_True, theFirstParOnCurve1, theLastParOnCurve1);
217 SetBeanParameters(Standard_False, theFirstParOnCurve2, theLastParOnCurve2);
219 myBeanTolerance1 = theBeanTolerance1;
220 myBeanTolerance2 = theBeanTolerance2;
221 myCriteria = myBeanTolerance1 + myBeanTolerance2;
222 myCurveResolution1 = myCurve1.Resolution(myCriteria);
225 // ==================================================================================
226 // function: SetBeanParameters
228 // ==================================================================================
229 void IntTools_BeanBeanIntersector::SetBeanParameters(const Standard_Boolean IsFirstBean,
230 const Standard_Real theFirstParOnCurve,
231 const Standard_Real theLastParOnCurve)
234 myFirstParameter1 = theFirstParOnCurve;
235 myLastParameter1 = theLastParOnCurve;
238 myFirstParameter2 = theFirstParOnCurve;
239 myLastParameter2 = theLastParOnCurve;
242 // ==================================================================================
245 // ==================================================================================
246 const IntTools_SequenceOfRanges& IntTools_BeanBeanIntersector::Result() const
251 // ==================================================================================
254 // ==================================================================================
255 void IntTools_BeanBeanIntersector::Result(IntTools_SequenceOfRanges& theResults) const
257 theResults = myResults;
259 // ==================================================================================
262 // ==================================================================================
263 void IntTools_BeanBeanIntersector::Perform()
265 Standard_Boolean bFastComputed;
266 Standard_Integer k, i, iFlag, aNbRanges, aNbResults;
267 Standard_Real aMidParameter, aCoeff, aParamDist, aPPC;
268 Standard_Real aCriteria2, aD2;
270 IntTools_CArray1OfReal aParams;
271 IntTools_Range aRange2, aRange;
273 myIsDone = Standard_False;
276 LocalPrepareArgs(myCurve1, myFirstParameter1, myLastParameter1, myDeflection, aParams);
278 myRangeManager.SetRanges(aParams, 0);
280 aNbRanges=myRangeManager.Length();
285 bFastComputed=FastComputeIntersection();
287 aRange.SetFirst(myFirstParameter1);
288 aRange.SetLast (myLastParameter1);
289 myResults.Append(aRange);
290 myIsDone = Standard_True;
294 ComputeRoughIntersection();
296 //Standard_Real aMidParameter = (myFirstParameter2 + myLastParameter2) * 0.5;
298 aMidParameter = myFirstParameter2+(myLastParameter2-myFirstParameter2)*aCoeff;
300 for(k = 0; k < 2; ++k) {
302 aRange2.SetFirst(myFirstParameter2);
303 aRange2.SetLast(aMidParameter);
306 aRange2.SetFirst(aMidParameter);
307 aRange2.SetLast(myLastParameter2);
310 ComputeUsingExtrema(aRange2);
312 ComputeNearRangeBoundaries(aRange2);
317 // 0 - just initialized
318 // 1 - non-intersected
319 // 2 - roughly intersected
320 // 3 - intersection is not done
321 // 4 - coincided range
323 aPPC=Precision::PConfusion();
324 aCriteria2=myCriteria*myCriteria;
325 aNbRanges=myRangeManager.Length();
327 for(i=1; i<=aNbRanges; ++i) {
328 iFlag=myRangeManager.Flag(i);
331 aRange=myRangeManager.Range(i);
332 aNbResults=myResults.Length();
334 const IntTools_Range& aLastRange = myResults.Last();
336 aParamDist = Abs(aRange.First() - aLastRange.Last());
337 if(aParamDist > myCurveResolution1) {
338 myResults.Append(aRange);
341 aPi=myCurve1.Value(aRange.First());
342 aPh=myCurve1.Value(aLastRange.Last());
343 aD2=aPi.SquareDistance(aPh);
344 if(aParamDist<aPPC || aD2<aCriteria2) {
345 myResults.ChangeValue(aNbResults).SetLast(aRange.Last());
348 myResults.Append(aRange);
353 myResults.Append(aRange);
356 } // for(i = 1; i <= myRangeManager.Length(); i++) {
357 myIsDone = Standard_True;
359 // ==================================================================================
360 // function: FastComputeIntersection
362 // ==================================================================================
363 Standard_Boolean IntTools_BeanBeanIntersector::FastComputeIntersection()
365 Standard_Boolean aresult;
366 GeomAbs_CurveType aCT1, aCT2;
368 aresult = Standard_False;
370 aCT1=myCurve1.GetType();
371 aCT2=myCurve2.GetType();
378 if(aCT1==GeomAbs_Line) {
379 Standard_Real par1, par2;
381 if((Distance(myFirstParameter1, par1) < myCriteria) &&
382 (Distance(myLastParameter1, par2) < myCriteria)) {
384 if((par1 >= myFirstParameter2) && (par1 <= myLastParameter2) &&
385 (par2 >= myFirstParameter2) && (par2 <= myLastParameter2)) {
386 myRangeManager.InsertRange(myFirstParameter1, myLastParameter1, 4);
387 aresult = Standard_True;
394 if(aCT1==GeomAbs_Circle) {
395 Standard_Real anAngle, aPA, aDistLoc, aDist, aDiff, aR1, aR2;
396 gp_Circ aCirc1, aCirc2;
399 aCirc1=myCurve1.Circle();
400 aCirc2=myCurve2.Circle();
404 aPA=Precision::Angular();
405 aDir1 = aCirc1.Axis().Direction();
406 aDir2 = aCirc2.Axis().Direction();
408 anAngle = aDir1.Angle(aDir2);
413 const gp_Pnt& aPLoc1=aCirc1.Location();
414 const gp_Pnt& aPLoc2=aCirc2.Location();
415 aDistLoc = aPLoc1.Distance(aPLoc2);
419 if(Abs(aDist) > myCriteria) {
423 Standard_Real aSinPA, atmpvalue, aprojectedradius;
426 atmpvalue = aR1*aSinPA;
427 atmpvalue *= atmpvalue;
428 aprojectedradius = sqrt(aR1*aR1 - atmpvalue);
430 aDiff = aprojectedradius - aR2;
431 aDist = aDistLoc + sqrt((aDiff * aDiff) + atmpvalue);
432 if(Abs(aDist) > myCriteria) {
436 Standard_Boolean newparfound;
438 Standard_Real afirstpar, alastpar, par1, par2, apar;
440 afirstpar = myFirstParameter1;
441 alastpar = myLastParameter1;
443 for(i = 0; i < 2; i++) {
444 if((Distance(afirstpar, par1) < myCriteria) &&
445 (Distance(alastpar , par2) < myCriteria)) {
447 if(i || Distance((myFirstParameter1 + myLastParameter2) * 0.5, apar) < myCriteria) {
448 myRangeManager.InsertRange(afirstpar, alastpar, 4);
451 aresult = Standard_True;
461 newparfound = Standard_False;
463 if(Distance((myFirstParameter1 + myLastParameter2) * 0.5, apar) < myCriteria) {
464 afirstpar = myFirstParameter1 + myCriteria;
465 alastpar = myLastParameter1 - myCriteria;
466 newparfound = Standard_True;
468 if(alastpar <= afirstpar) {
469 newparfound = Standard_False;
476 }// for(i = 0; i < 2; i++) {
477 } // if(aCT1==GeomAbs_Circle)
478 //modified by NIZNHY-PKV Mon Oct 08 14:08:19 2012f
479 if (aCT1==GeomAbs_BSplineCurve || aCT1==GeomAbs_BezierCurve) {
480 Standard_Integer iFlag;
482 iFlag=CheckCoincidence(myFirstParameter1,
495 //modified by NIZNHY-PKV Mon Oct 08 14:08:23 2012t
498 // ==================================================================================
499 // function: Distance
501 // ==================================================================================
502 Standard_Real IntTools_BeanBeanIntersector::Distance(const Standard_Real theArg,
503 Standard_Real& theArgOnOtherBean)
505 Standard_Real aDistance;
506 Standard_Integer aNbPoints;
509 aDistance=RealLast();
511 aPoint=myCurve1.Value(theArg);
512 myProjector.Init(myTrsfCurve2, myFirstParameter2, myLastParameter2);
513 myProjector.Perform(aPoint);
515 aNbPoints=myProjector.NbPoints();
517 theArgOnOtherBean = myProjector.LowerDistanceParameter();
518 aDistance=myProjector.LowerDistance();
522 Standard_Real aDistance1, aDistance2;
524 aDistance1 = aPoint.Distance(myCurve2.Value(myFirstParameter2));
525 aDistance2 = aPoint.Distance(myCurve2.Value(myLastParameter2));
527 theArgOnOtherBean = myLastParameter2;
528 aDistance=aDistance2;
529 if(aDistance1 < aDistance2) {
530 theArgOnOtherBean = myFirstParameter2;
531 aDistance=aDistance1;
536 // ==================================================================================
537 // function: ComputeRoughIntersection
539 // ==================================================================================
540 void IntTools_BeanBeanIntersector::ComputeRoughIntersection()
542 Standard_Boolean isintersection;
543 Standard_Integer i, aNbArgs, aNbArgs1, aNbRanges, j, aNbLines, k, pIt, extIt, iFlag;
544 Standard_Real aDeflection, aGPR, aCurDeflection, aT1, aT2, aD;
545 Standard_Real aMaxDistance, aDistance, aPPC, aPrm1, aPrm2, aPPA;
546 GeomAbs_CurveType aCT1, aCT2;
547 gp_Pnt aPoint1, aPoint2, aMidPOnCurve, aMidPOnLine, aP1, aP2;
548 IntTools_CArray1OfReal anArgs;
549 LocalPrepareArgs(myCurve2, myFirstParameter2, myLastParameter2, aDeflection, anArgs);
551 aNbArgs=anArgs.Length();
556 aCT1=myCurve1.GetType();
557 aCT2=myCurve2.GetType();
558 aGPR=gp::Resolution();
559 aPPC=Precision::PConfusion();
560 aPPA=Precision::Angular();
563 Intf_Array1OfLin aLines(1, aNbArgs1);
564 TColStd_Array1OfInteger aLineFlags(1, aNbArgs1);
565 TColStd_Array1OfReal aDistances(1, aNbArgs1);
568 aPoint1 = myCurve2.Value(aT1);
569 for(i=1; i<aNbArgs; ++i) {
571 aPoint2 = myCurve2.Value(aT2);
572 gp_Vec aVec(aPoint1, aPoint2);
574 aDistances.SetValue(i, aD);
577 aLineFlags.SetValue(i, 0);
580 aLineFlags.SetValue(i, 1);
581 gp_Lin aLine(aPoint1, gp_Dir(aVec));
582 aLines.SetValue(i, aLine);
584 if((aCT2 == GeomAbs_BezierCurve) ||
585 (aCT2 == GeomAbs_BSplineCurve)) {
586 aMidPOnCurve = myCurve2.Value((aT1+aT2) * 0.5);
587 aMidPOnLine = ElCLib::Value((aDistances(i)*0.5), aLine);
588 aCurDeflection = aMidPOnCurve.Distance(aMidPOnLine);
589 if(aCurDeflection > aDeflection) {
590 aDeflection = aCurDeflection;
598 aNbLines=aLines.Upper();
599 aMaxDistance = myCriteria + myDeflection + aDeflection;
601 aT1=myRangeManager.Range(1).First();
602 aPoint1 = myCurve1.Value(aT1);
603 aNbRanges=myRangeManager.Length();
604 for(i = 1; i <= aNbRanges; ++i) {
605 const IntTools_Range& aRange = myRangeManager.Range(i);
607 aPoint2 = myCurve1.Value(aT2);
609 iFlag=myRangeManager.Flag(i);
610 if(iFlag==4) {// coincided
616 myRangeManager.SetFlag(i, 1); // not intersected
621 aBox1.Enlarge(myBeanTolerance1 + myDeflection);
623 gp_Vec aVec(aPoint1, aPoint2);
625 aDistance=aVec.Magnitude();
626 if(aDistance <= aGPR) {
627 myRangeManager.SetFlag(i, 0);
631 gp_Lin aLine(aPoint1, gp_Dir(aVec));
633 if((aCT1 == GeomAbs_BezierCurve) ||
634 (aCT1 == GeomAbs_BSplineCurve)) {
635 aMidPOnCurve = myCurve1.Value((aRange.First() + aRange.Last()) * 0.5);
636 aMidPOnLine = ElCLib::Value((aDistance*0.5), aLine);
637 aCurDeflection = aMidPOnCurve.Distance(aMidPOnLine);
638 if(myDeflection < aCurDeflection) {
639 aMaxDistance += aCurDeflection - myDeflection;
640 myDeflection = aCurDeflection;
644 for(j=1; j<=aNbLines; ++j) {
646 myRangeManager.SetFlag(i, 0);
650 const gp_Lin& aL2=aLines(j);
651 //Handle(Geom_Line) aC2=new Geom_Line(aL2); // DEB ft
653 aP1=ElCLib::Value(0., aL2);
654 aP2=ElCLib::Value(aD, aL2);
656 Extrema_ExtElC anExtrema(aLine, aL2, aPPA);
657 if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
658 isintersection = Standard_False;
660 if(anExtrema.IsParallel()) {
661 isintersection = (anExtrema.SquareDistance(1) < aMaxDistance * aMaxDistance);
664 for(k = 1; !isintersection && k <= anExtrema.NbExt(); ++k) {
665 if(anExtrema.SquareDistance(k) < aMaxDistance * aMaxDistance) {
666 Extrema_POnCurv P1, P2;
667 anExtrema.Points(k, P1, P2);
668 aPrm1=P1.Parameter();
669 aPrm2=P2.Parameter();
670 if((aPrm1 >= -aMaxDistance) && (aPrm1 <= aDistance+aMaxDistance) &&
671 (aPrm2 >= -aMaxDistance) && (aPrm2 <= aD+aMaxDistance)) {
672 isintersection = Standard_True;
675 Extrema_ExtPElC aPointProjector;
677 for(pIt = 0; !isintersection && (pIt < 4); ++pIt) {
681 //Extrema_ExtPElC(aPoint1, aLines(j), aPPC, 0., aDistances(j));
682 Extrema_ExtPElC(aPoint1, aL2, aPPC, -aMaxDistance, aD+aMaxDistance);
687 //Extrema_ExtPElC(aPoint2, aLines(j), aPPC, 0., aD);
688 Extrema_ExtPElC(aPoint2, aL2, aPPC, -aMaxDistance, aD+aMaxDistance);
693 //Extrema_ExtPElC(ElCLib::Value(0., aLines(j)), aLine, aPPC, 0., aDistance);
694 Extrema_ExtPElC(aP1, aLine, aPPC, -aMaxDistance, aDistance+aMaxDistance);
699 //Extrema_ExtPElC(ElCLib::Value(aDistances(j), aLines(j)), aLine, aPPC, 0., aDistance);
700 Extrema_ExtPElC(aP2, aLine, aPPC, -aMaxDistance, aDistance+aMaxDistance);
708 if(aPointProjector.IsDone()) {
709 Standard_Real aMaxDistance2 = aMaxDistance * aMaxDistance;
710 for(extIt = 1; extIt <= aPointProjector.NbExt(); extIt++) {
711 if(aPointProjector.SquareDistance(extIt) < aMaxDistance2) {
712 isintersection = Standard_True;
718 }//if(anExtrema.Value(k) < aMaxDistance) {
719 }//for(k = 1; !isintersection && k <= anExtrema.NbExt(); k++) {
723 myRangeManager.SetFlag(i, 2); // roughly intersected
726 }//if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
729 aBox2.Add(myCurve2.Value(anArgs(j-1)));
730 aBox2.Add(myCurve2.Value(anArgs(j)));
731 aBox2.Enlarge(myBeanTolerance2 + aDeflection);
733 if(!aBox1.IsOut(aBox2)) {
734 myRangeManager.SetFlag(i, 2); // roughly intersected
744 // ==================================================================================
745 // function: ComputeUsingExtrema
747 // ==================================================================================
748 void IntTools_BeanBeanIntersector::ComputeUsingExtrema(const IntTools_Range& theRange2)
751 //Extrema_ExtCC is reused throughout this method to store caches computed on
752 //theRange2. However it is actually used only in a few calls of
753 //ComputeUsingExtrema(), so using a default constructor would add unnecessary overhead
754 //of initialization its internal fields. Since it is not manipulated by Handle then
755 //we will use a pointer to it and initialize it only when needed.
756 Extrema_ExtCC *apExtrema = 0;
757 Handle(GeomAdaptor_HCurve) aHCurve1, aHCurve2; //will be initialized later, only if needed
758 //handles are used to guard pointers to GeomAdaptor_Curve inside Extrema
759 Standard_Real aCriteria2 = myCriteria * myCriteria;
760 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
762 if(myRangeManager.Flag(i) == 2 || myRangeManager.Flag(i) == 0) {
763 const IntTools_Range& aParamRange = myRangeManager.Range(i);
765 if(aParamRange.Last() - aParamRange.First() < Precision::PConfusion()) {
767 if(((i > 1) && (myRangeManager.Flag(i-1) == 4)) ||
768 ((i < myRangeManager.Length()) && (myRangeManager.Flag(i+1) == 4))) {
769 myRangeManager.SetFlag(i, 4);
773 if (aHCurve2.IsNull()) {
774 //initialize only once
775 apExtrema = new Extrema_ExtCC;
776 Standard_Real ftmp = theRange2.First() - Precision::PConfusion();
777 Standard_Real ltmp = theRange2.Last() + Precision::PConfusion();
778 ftmp = (ftmp < myFirstParameter2) ? myFirstParameter2 : ftmp;
779 ltmp = (ltmp > myLastParameter2) ? myLastParameter2 : ltmp;
780 aHCurve2 = new GeomAdaptor_HCurve (myTrsfCurve2, ftmp, ltmp);
781 apExtrema->SetCurve (2, aHCurve2->Curve(), theRange2.First(), theRange2.Last());
783 Extrema_ExtCC& anExtrema = *apExtrema;
785 Standard_Real ftmp = aParamRange.First() - Precision::PConfusion();
786 Standard_Real ltmp = aParamRange.Last() + Precision::PConfusion();
787 ftmp = (ftmp < myFirstParameter1) ? myFirstParameter1 : ftmp;
788 ltmp = (ltmp > myLastParameter1) ? myLastParameter1 : ltmp;
789 aHCurve1 = new GeomAdaptor_HCurve (myTrsfCurve1, ftmp, ltmp);
790 anExtrema.SetCurve (1, aHCurve1->Curve(), aParamRange.First(), aParamRange.Last());
794 if(anExtrema.IsDone() && (anExtrema.IsParallel() || (anExtrema.NbExt() > 0))) {
795 Standard_Integer anOldNbRanges = myRangeManager.Length();
797 if (anExtrema.IsParallel()) {
798 if(anExtrema.SquareDistance(1) < aCriteria2) {
799 Standard_Real theParameter1, theParameter2;
800 Standard_Real adistance1 = Distance(aParamRange.First(), theParameter1);
801 Standard_Real adistance2 = Distance(aParamRange.Last(), theParameter2);
802 Standard_Boolean validdistance1 = (adistance1 < myCriteria);
803 Standard_Boolean validdistance2 = (adistance2 < myCriteria);
805 if (validdistance1 && validdistance2) {
806 myRangeManager.InsertRange(aParamRange.First(), aParamRange.Last(), 4);
811 ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), i, theParameter1, theRange2);
815 ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), i, theParameter2, theRange2);
818 Standard_Real a = aParamRange.First();
819 Standard_Real b = aParamRange.Last();
820 Standard_Real da = adistance1;
821 Standard_Real db = adistance2;
822 Standard_Real asolution = a;
823 Standard_Boolean found = Standard_False;
825 while(((b - a) > myCurveResolution1) && !found) {
826 asolution = (a+b)*0.5;
827 Standard_Real adist = Distance(asolution, theParameter1);
829 if(adist < myCriteria) {
830 found = Standard_True;
845 ComputeRangeFromStartPoint(Standard_False, asolution, i, theParameter1, theRange2);
846 ComputeRangeFromStartPoint(Standard_True, asolution, i, theParameter1, theRange2);
849 myRangeManager.SetFlag(i, 2);
858 for(Standard_Integer j = 1 ; j <= anExtrema.NbExt(); j++) {
859 if(anExtrema.SquareDistance(j) < aCriteria2) {
860 Extrema_POnCurv p1, p2;
861 anExtrema.Points(j, p1, p2);
863 Standard_Integer aNbRanges = myRangeManager.Length();
865 Standard_Integer anIndex = myRangeManager.GetIndex(p1.Parameter(), Standard_False);
867 ComputeRangeFromStartPoint(Standard_False, p1.Parameter(), anIndex, p2.Parameter(), theRange2);
870 anIndex = myRangeManager.GetIndex(p1.Parameter(), Standard_True);
873 ComputeRangeFromStartPoint(Standard_True, p1.Parameter(), anIndex, p2.Parameter(), theRange2);
876 if(aNbRanges == myRangeManager.Length()) {
877 SetEmptyResultRange(p1.Parameter(), myRangeManager);
882 Standard_Integer adifference = myRangeManager.Length() - anOldNbRanges;
884 if(adifference > 0) {
889 myRangeManager.SetFlag(i, 3); // intersection not done.
893 if (apExtrema) delete apExtrema;
896 // ==================================================================================
897 // function: ComputeNearRangeBoundaries
899 // ==================================================================================
900 void IntTools_BeanBeanIntersector::ComputeNearRangeBoundaries(const IntTools_Range& theRange2)
902 Standard_Real theParameter = theRange2.First();
904 for(Standard_Integer i = 1; i <= myRangeManager.Length(); i++) {
905 if(myRangeManager.Flag(i) != 3)
908 if((i > 1) && ((myRangeManager.Flag(i-1) == 1) || (myRangeManager.Flag(i-1) == 4))) {
909 myRangeManager.SetFlag(i, 2);
913 const IntTools_Range& aParamRange = myRangeManager.Range(i);
915 if(Distance(aParamRange.First(), theParameter) < myCriteria) {
916 Standard_Integer aNbRanges = myRangeManager.Length();
919 ComputeRangeFromStartPoint(Standard_False, aParamRange.First(), i-1, theParameter, theRange2);
921 ComputeRangeFromStartPoint(Standard_True, aParamRange.First(), i + (myRangeManager.Length() - aNbRanges), theParameter, theRange2);
923 if(aNbRanges == myRangeManager.Length()) {
924 SetEmptyResultRange(aParamRange.First(), myRangeManager);
928 myRangeManager.SetFlag(i, 2);
932 if((myRangeManager.Flag(myRangeManager.Length()) == 3) ||
933 (myRangeManager.Flag(myRangeManager.Length()) == 2)) {
934 const IntTools_Range& aParamRange = myRangeManager.Range(myRangeManager.Length());
936 if(Distance(aParamRange.Last(), theParameter) < myCriteria) {
937 Standard_Integer aNbRanges = myRangeManager.Length();
938 myRangeManager.SetFlag(myRangeManager.Length(), 2);
940 ComputeRangeFromStartPoint(Standard_False, aParamRange.Last(), myRangeManager.Length(), theParameter, theRange2);
942 if(aNbRanges == myRangeManager.Length()) {
943 SetEmptyResultRange(aParamRange.Last(), myRangeManager);
947 myRangeManager.SetFlag(myRangeManager.Length(), 2);
952 // ==================================================================================
953 // function: ComputeRangeFromStartPoint
955 // ==================================================================================
956 void IntTools_BeanBeanIntersector::ComputeRangeFromStartPoint(const Standard_Boolean ToIncreaseParameter,
957 const Standard_Real theParameter,
958 const Standard_Integer theIndex,
959 const Standard_Real theParameter2,
960 const IntTools_Range& theRange2)
963 if(myRangeManager.Flag(theIndex) == 4 ||
964 myRangeManager.Flag(theIndex) == 1)
967 Standard_Integer aValidIndex = theIndex;
968 Standard_Real aMinDelta = myCurveResolution1 * 0.5;
969 Standard_Real aDeltaRestrictor = myLastParameter1 - myFirstParameter1;
971 if(Abs(aDeltaRestrictor) < Precision::PConfusion()) {
975 if(aMinDelta > aDeltaRestrictor) {
976 aMinDelta = aDeltaRestrictor;
978 Standard_Real tenOfMinDelta = aMinDelta * 10.;
979 Standard_Real aDelta = myCurveResolution1;
980 Standard_Real aCurPar = (ToIncreaseParameter) ? (theParameter + aDelta) : (theParameter - aDelta);
981 Standard_Real aPrevPar = theParameter;
982 IntTools_Range aCurrentRange = myRangeManager.Range(aValidIndex);
984 Standard_Boolean BoundaryCondition = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
986 if(BoundaryCondition) {
987 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
988 BoundaryCondition = Standard_False;
991 Standard_Integer loopcounter = 0; // neccesary to have no infinite loop
992 Standard_Real aParameter = theParameter2;
993 Standard_Boolean anotherSolutionFound = Standard_False;
995 Standard_Boolean isboundaryindex = Standard_False;
996 Standard_Boolean isvalidindex = Standard_True;
998 Standard_Real aCriteria2 = myCriteria * myCriteria;
1000 while((aDelta >= aMinDelta) && (loopcounter <= 10)) {
1001 Standard_Boolean pointfound = Standard_False;
1003 gp_Pnt aPoint = myCurve1.Value(aCurPar);
1004 GeomAdaptor_Curve aCurve2(myTrsfCurve2, theRange2.First(), theRange2.Last());
1006 Extrema_LocateExtPC anExtrema(aPoint, aCurve2, aParameter, theRange2.First(), theRange2.Last(), 1.e-10);
1008 if(anExtrema.IsDone()) {
1009 if(anExtrema.SquareDistance() < aCriteria2) {
1010 Extrema_POnCurv aPOnCurv = anExtrema.Point();
1011 aParameter = aPOnCurv.Parameter();
1012 pointfound = Standard_True;
1016 // pointfound = (Distance(aCurPar, aParameter) < myCriteria);
1017 Standard_Real afoundparam = aParameter;
1019 if(Distance(aCurPar, afoundparam) < myCriteria) {
1020 aParameter = afoundparam;
1021 pointfound = Standard_True;
1027 anotherSolutionFound = Standard_True;
1029 if(BoundaryCondition && (isboundaryindex || !isvalidindex))
1033 aDeltaRestrictor = aDelta;
1036 // if pointfound decide to increase aDelta using derivative of distance function
1039 aDelta = (pointfound) ? (aDelta * 2.) : (aDelta * 0.5);
1040 aDelta = (aDelta < aDeltaRestrictor) ? aDelta : aDeltaRestrictor;
1041 aCurPar = (ToIncreaseParameter) ? (aPrevPar + aDelta) : (aPrevPar - aDelta);
1043 BoundaryCondition = (ToIncreaseParameter) ? (aCurPar > aCurrentRange.Last()) : (aCurPar < aCurrentRange.First());
1045 isboundaryindex = Standard_False;
1046 isvalidindex = Standard_True;
1048 if(BoundaryCondition) {
1049 isboundaryindex = ((!ToIncreaseParameter && (aValidIndex == 1)) ||
1050 (ToIncreaseParameter && (aValidIndex == myRangeManager.Length())));
1052 if(!isboundaryindex) {
1054 Standard_Integer aFlag = (ToIncreaseParameter) ? myRangeManager.Flag(aValidIndex + 1) : myRangeManager.Flag(aValidIndex - 1);
1056 if(aFlag != 1 && aFlag != 4) {
1057 aValidIndex = (ToIncreaseParameter) ? (aValidIndex + 1) : (aValidIndex - 1);
1058 aCurrentRange = myRangeManager.Range(aValidIndex);
1060 if((ToIncreaseParameter && (aCurPar > aCurrentRange.Last())) ||
1061 (!ToIncreaseParameter && (aCurPar < aCurrentRange.First()))) {
1062 aCurPar = (aCurrentRange.First() + aCurrentRange.Last()) * 0.5;
1067 isvalidindex = Standard_False;
1068 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1073 aCurPar = (ToIncreaseParameter) ? aCurrentRange.Last() : aCurrentRange.First();
1076 if(aDelta < tenOfMinDelta) {
1082 } // end if(BoundaryCondition)
1085 if(anotherSolutionFound) {
1086 if(ToIncreaseParameter)
1087 myRangeManager.InsertRange(theParameter, aPrevPar, 4);
1089 myRangeManager.InsertRange(aPrevPar, theParameter, 4);
1093 // ---------------------------------------------------------------------------------
1094 // static function: LocalPrepareArgs
1096 // ---------------------------------------------------------------------------------
1097 static void LocalPrepareArgs(BRepAdaptor_Curve& theCurve,
1098 const Standard_Real theFirstParameter,
1099 const Standard_Real theLastParameter,
1100 Standard_Real& theDeflection,
1101 IntTools_CArray1OfReal& theArgs) {
1102 Standard_Integer aDiscretization = 30;
1103 Standard_Real aRelativeDeflection = 0.01;
1104 theDeflection = aRelativeDeflection;
1105 Standard_Boolean prepareargs = Standard_True;
1107 switch(theCurve.GetType()) {
1108 case GeomAbs_Line: {
1109 prepareargs = Standard_False;
1110 aDiscretization = 3;
1111 theArgs.Append(theFirstParameter);
1113 if((theLastParameter - theFirstParameter) > Precision::PConfusion()) {
1114 theArgs.Append((theFirstParameter + theLastParameter)*0.5);
1116 theArgs.Append(theLastParameter);
1117 theDeflection = Precision::Confusion();
1120 case GeomAbs_Circle: {
1121 aDiscretization = 23;
1122 theDeflection = aRelativeDeflection * theCurve.Circle().Radius();
1125 case GeomAbs_Ellipse: {
1126 aDiscretization = 40;
1127 theDeflection = 2 * aRelativeDeflection * theCurve.Ellipse().MajorRadius();
1130 case GeomAbs_Hyperbola:
1131 case GeomAbs_Parabola: {
1132 aDiscretization = 40;
1133 theDeflection = aRelativeDeflection;
1136 case GeomAbs_BezierCurve: {
1137 aDiscretization = 30;
1138 theDeflection = aRelativeDeflection;
1141 case GeomAbs_BSplineCurve: {
1142 aDiscretization = 30;
1143 theDeflection = aRelativeDeflection;
1147 aDiscretization = 30;
1148 theDeflection = aRelativeDeflection;
1153 IntTools::PrepareArgs(theCurve, theLastParameter, theFirstParameter, aDiscretization, aRelativeDeflection, theArgs);
1156 // ---------------------------------------------------------------------------------
1157 // static function: SetEmptyResultRange
1159 // ---------------------------------------------------------------------------------
1160 static Standard_Boolean SetEmptyResultRange(const Standard_Real theParameter,
1161 IntTools_MarkedRangeSet& theMarkedRange) {
1163 const TColStd_SequenceOfInteger& anIndices = theMarkedRange.GetIndices(theParameter);
1164 Standard_Boolean add = (anIndices.Length() > 0);
1166 for(Standard_Integer k = 1; k <= anIndices.Length(); k++) {
1167 if(theMarkedRange.Flag(anIndices(k)) == 4) {
1168 add = Standard_False;
1174 theMarkedRange.InsertRange(theParameter, theParameter, 4);
1179 //modified by NIZNHY-PKV Fri Oct 12 09:34:10 2012f
1181 Standard_Integer DistPC(const Standard_Real aT1,
1182 const Handle(Geom_Curve)& aC1,
1183 const Standard_Real aCriteria,
1184 GeomAPI_ProjectPointOnCurve& aProjector,
1186 Standard_Real& aT2);
1190 Standard_Integer DistPC(const Standard_Real aT1,
1191 const Handle(Geom_Curve)& aC1,
1192 const Standard_Real aCriteria,
1193 GeomAPI_ProjectPointOnCurve& aProjector,
1196 Standard_Real& aDmax,
1197 Standard_Real& aTmax);
1200 Standard_Integer FindMaxDistPC(const Standard_Real aT1A,
1201 const Standard_Real aT1B,
1202 const Handle(Geom_Curve)& aC1,
1203 const Standard_Real aCriteria,
1204 const Standard_Real aEps1,
1205 GeomAPI_ProjectPointOnCurve& aProjector,
1206 Standard_Real& aDmax,
1207 Standard_Real& aT1max);
1209 //=======================================================================
1210 //function : CheckCoincidence
1212 //=======================================================================
1213 Standard_Integer CheckCoincidence(const Standard_Real aT11,
1214 const Standard_Real aT12,
1215 const Handle(Geom_Curve)& aC1,
1216 const Standard_Real aT21,
1217 const Standard_Real aT22,
1218 const Handle(Geom_Curve)& aC2,
1219 const Standard_Real aCriteria,
1220 const Standard_Real aEps1,
1221 GeomAPI_ProjectPointOnCurve& aProjector)
1223 Standard_Integer iErr, aNb1, i, aNbX;
1224 Standard_Real dT1, aT1, aT2, aD, aDmax, aTmax;
1225 Standard_Real aT1A, aT1B, aD1max,aT1max;
1227 iErr=0; // the patches are coincided
1230 aProjector.Init(aC2, aT21, aT22);
1234 // 1. Express evaluation
1236 aNb1=10; // Number of intervals on the curve #1
1237 dT1=(aT12-aT11)/aNb1;
1238 for (i=1; i<aNb1; ++i) {
1241 iErr=DistPC(aT1, aC1, aCriteria, aProjector, aD, aT2, aDmax, aTmax);
1243 iErr=1;// a point from aC1 can not be projected on aC2
1247 if (aDmax>aCriteria) {
1248 iErr=2; // the distance is too big
1253 // 2. Deep evaluation
1257 for (i=1; i<aNbX; ++i) {
1261 iErr=FindMaxDistPC(aT1A, aT1B, aC1, aCriteria, aEps1, aProjector, aD1max, aT1max);
1271 //=======================================================================
1272 //function : FindMaxDistPC
1274 //=======================================================================
1275 Standard_Integer FindMaxDistPC(const Standard_Real aT1A,
1276 const Standard_Real aT1B,
1277 const Handle(Geom_Curve)& aC1,
1278 const Standard_Real aCriteria,
1279 const Standard_Real aEps1,
1280 GeomAPI_ProjectPointOnCurve& aProjector,
1281 Standard_Real& aDmax,
1282 Standard_Real& aT1max)
1284 Standard_Integer iErr, iCnt;
1285 Standard_Real aGS, aXP, aA, aB, aXL, aYP, aYL, aT2P, aT2L, aX0;
1291 aGS=0.6180339887498948482045868343656;// =0.5*(1.+sqrt(5.))-1.;
1298 iErr=DistPC(aXP, aC1, aCriteria, aProjector, aYP, aT2P, aDmax, aT1max);
1303 iErr=DistPC(aXL, aC1, aCriteria, aProjector, aYL, aT2L, aDmax, aT1max);
1314 iErr=DistPC(aXP, aC1, aCriteria, aProjector, aYP, aT2P, aDmax, aT1max);
1324 iErr=DistPC(aXL, aC1, aCriteria, aProjector, aYL, aT2L, aDmax, aT1max);
1330 if ((aB-aA)<aEps1) {
1338 //=======================================================================
1341 //=======================================================================
1342 Standard_Integer DistPC(const Standard_Real aT1,
1343 const Handle(Geom_Curve)& aC1,
1344 const Standard_Real aCriteria,
1345 GeomAPI_ProjectPointOnCurve& aProjector,
1348 Standard_Real& aDmax,
1349 Standard_Real& aTmax)
1351 Standard_Integer iErr;
1353 iErr=DistPC(aT1, aC1, aCriteria, aProjector, aD, aT2);
1365 //=======================================================================
1368 //=======================================================================
1369 Standard_Integer DistPC(const Standard_Real aT1,
1370 const Handle(Geom_Curve)& aC1,
1371 const Standard_Real aCriteria,
1372 GeomAPI_ProjectPointOnCurve& aProjector,
1376 Standard_Integer iErr, aNbP2;
1382 aProjector.Perform(aP1);
1383 aNbP2=aProjector.NbPoints();
1385 iErr=1;// the point from aC1 can not be projected on aC2
1389 aD=aProjector.LowerDistance();
1390 aT2=aProjector.LowerDistanceParameter();
1392 iErr=2;// the distance is too big
1397 //modified by NIZNHY-PKV Fri Oct 12 09:34:12 2012t