Bezier Intersections

BlitzPlus Forums/BlitzPlus Programming/Bezier Intersections

iroker

(Posted 2006) [#1]

Blitz+ codes for Bezier Intersections

iroker

(Posted 2006) [#2]

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.

Andy_A

(Posted 2006) [#3]

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

Andy_A

(Posted 2006) [#4]

Maybe you can make this into a function.

Line-Bezier Intersect Demo:
http://blitzbasic.com/codearcs/codearcs.php?code=1856

Andy

iroker

(Posted 2006) [#5]

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

Andy_A

(Posted 2006) [#6]

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

iroker

(Posted 2006) [#7]

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