# Bezier Intersections

BlitzPlus Forums/BlitzPlus Programming/Bezier Intersections
| ||

Blitz+ codes for Bezier Intersections |

| ||

I am asking for some help. Who can code a Function like IntersectBezier3Line(P1,P2,P3,P4,L1,L2) P1..4 Control Ponts of a Bezier3 curve L1,L2 Line segment coordinates. |

| ||

I haven't written this type of code, but my approach would be to write a function that converges on the approximation of where the bezier curve and the line segment intersect. Here are links to code to get you started Bezier Code: http://blitzbasic.com/codearcs/codearcs.php?code=170 Line-Line Intersect: http://blitzbasic.com/codearcs/codearcs.php?code=1202 For example: Using only 10 points to plot your bezier curve, test each line segment between the ten points until you determine if the bezier and line segment intersect using line-line intersect code. If the lines intersect you know approximately where they intersect. This may be good enough at this rough scale, again depending on how accurate you need to be. Otherwise, increase the number of segments in your bezier to 100 points, 1000 points (and so on...) and continue looking for line-line intersects until you zero in on the most accurate coordinates. Good Luck, Andy |

| ||

Maybe you can make this into a function. Line-Bezier Intersect Demo: http://blitzbasic.com/codearcs/codearcs.php?code=1856 Andy |

| ||

sorry but the code=1856 its not a real solution of my problem, its too slow for my purposes and its not exact enough. but i think that's easier than i thought. the equation of a Bezier3 is: Bzx#=x1*(1-t)^3 + 3*vx1*(1-t)^2*t + 3*vx2*(1-t)*t^2 + x2*t^3 (X-Coordinate) Bzy#=y1*(1-t)^3 + 3*vy1*(1-t)^2*t + 3*vy2*(1-t)*t^2 + y2*t^3 (Y-Coordinate) where t is a value between 0 and 1 the equation of a line is: A*x+B*y-C=0 substituting x and y values with Bzx and Bzy you have after solving for t something like this Q*t^3 + R*t^2 + S*t + T = 0 you have now to find the polynomial roots of the above . a 3 degree polynomial has 0 to 3 roots that means 0 no intersection 1 to 3 intersections at t=root(1) or t=root(2) etc. and........ only values between 0 to 1 are real intersections any ideas how to solve polynomials with Blitz+? here my code now i need a solver Function intersectBezier3Line(x1#,y1#,vx1#,vy1#,x2#,y2#,vx2#,vy2#,L1x#,L1y#,L2x#,L2y#) Local A#,B#,C#,E#,F#,G#,La#,Lb#,Lc#,Solution# A=3*vx1+x2-(3*vx2)-x1 B=3*x1-(6*vx1)+(3*vx2) C=3*vx1-(3*x1) E=3*vy1+y2-(3*vy2)-y1 F=3*y1-(6*vy1)+(3*vy2) G=3*vy1-(3*y1) La=L2y-L1y Lb=L1x-L2x Lc=L1y*(L2x-L1x) + L1x*(L1y-L2y) ax(4)=La*x1 + Lb*y1 + Lc ax(3)=La*C + Lb*G ax(2)=La*B + Lb*F ax(1)=La*A + Lb*E FindRootsPoly3(ax(4),ax(3),ax(2),ax(1)) End Function |

| ||

Well, when in doubt "Google it". Search for: bezier line intersect Results: http://tom.cs.byu.edu/~557/text/ch7.pdf http://www.gamedev.net/community/forums/topic.asp?topic_id=385751 http://72.14.209.104/search?q=cache:ckes2VdwvSgJ:maths.usm.my:8080/webMathematica/BezierPage/theory.htm+%22bezier+curve%22+line+intersect&hl=en&gl=us&ct=clnk&cd=10 http://www.cs.arizona.edu/classes/cs534/patches.pdf Looks like the "Bezier Clipping" method may be best choice. Following the polynomial solving approach may be slower than the methods above. Good Luck, Andy |

| ||

i have the solution here is it:Function FindRootsPoly3(A3#,A2#,A1#,A0#) Local fc2#,gc2#,hc2#,Rc2#,Sc2#,Tc2#,Uc2#,ic2#,jc2#,kc2#,Lc2#,Mc2#,Nc2#,Pc2# fc2 =( (3*A1/A3) - ((A2^2)/(A3^2) ))/ 3 gc2=(( (2*A2^3)/(A3^3)) - (9*A2*A1/(A3^2)) + (27*A0/A3)) / 27 hc2 = ((gc2^2)/4) + ((fc2^3)/27) If hc2>0 Then Rc2 = -(gc2/2) + (Sqr(hc2)) If Rc2<0 Then Sc2 = -(Abs(Rc2)^0.333333) Else Sc2 = ((Rc2))^0.333333 EndIf Tc2 = -(gc2/2) -( Sqr(hc2)) If Tc2<0 Then Uc2 = -(Abs(Tc2)^0.333333) Else Uc2 = (Tc2)^0.333333 EndIf Rx(0) = (Sc2 + Uc2) - (A2/(3*A3)) Else If hc2=0 And gc2=0 And fc2=0 Then Rx(0) =-((A0/A3)^0.3333333 ) Else If hc2<0 Or hc2=0 Then ic2= Sqr(((gc2^2)/4) - hc2) jc2 = (ic2)^0.333333 kc2 = ACos (- (gc2 / (2*ic2))) Lc2 = -jc2 Mc2 = Cos (kc2/3) Nc2 = Sqr( 3) * Sin (kc2/3) Pc2 = -(A2/(3*A3)) Rx(0) = 2*jc2 * Cos(kc2/3) -(A2/(3*A3)) Rx(1) = Lc2 * (Mc2 + Nc2) + Pc2 Rx(2) = Lc2 * (Mc2 - Nc2) + Pc2 EndIf EndIf EndIf End Function this calculates only the real roots they are Rx(0), Rx(1), Rx(2) i am using this code in my AiEditor for Racer my Site here a pic of this |