Sign in to follow this  
staticVoid2

finding roots of a bezier curve

Recommended Posts

I'm currently adding support for true type fonts in my engine and need a way to find the intersection of a 2d ray(will be axis aligned, if that helps?) with a bezier curve with n amount of control points, can this be done? or would it be more efficient to just sub-divide the curve into line segments?

Share this post


Link to post
Share on other sites
If you get the parametric equations of the x & y coordinates of a bezier curve, they look something like this:

x = at^3 + bt^2 + ct + d
y = et^3 + ft^2 + gt + h

where t=fraction along bezier curve.

So what you want to do comes down to the problem of solving a cubic equation for t as you know a,b,c and d and the value of x. I think theres a formula for solving cubics. You can find it on Wikipedia. Alternatively you could use a numerical formula like newtons method or some other one. Newtons method doesnt always work though or may produce the wrong answer. So it may be better to try another method.

They have info about bezier curve on wikipedia:

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Theres info about solving cubic equations here:

http://en.wikipedia.org/wiki/Cubic_equation




Share this post


Link to post
Share on other sites
Quote:
Original post by staticVoid2
I'm currently adding support for true type fonts in my engine and need a way to find the intersection of a 2d ray(will be axis aligned, if that helps?).


Not much unfortunately.

Quote:
Original post by staticVoid2
with a bezier curve with n amount of control points, can this be done?


yes and no. If, and only if, you can guarentee that 1 value (i.e. X or Y) will always increment, then it is poissible to solve for t. This is what 2D animation curve editors have to do (see the cubic equation for more info). This only works for an animation curve because time is guarenteed to go forwards. If does not work if that constraint on time is removed (i.e. you'll get a number of real and imaginary solutions, and picking which one is right is more or less impossible).

Quote:
Original post by staticVoid2
or would it be more efficient to just sub-divide the curve into line segments?


In this case..... err, yes ;)

Share this post


Link to post
Share on other sites
The equation for a spline in x & y is a cubic equation, so in general you will have up to 3 solutions.

To get the line intersections for a given x value, you have to go round your shape getting all the intersections for each spline segment (ignoring to complex ones of course and ones that aren't in the range of 0 to 1 for t). Then you sort all the intersections with regard to y. Then the first intersection will correspond with your line segment entering the shape, the second with it leaving the shape. This pattern will continue so that all odd intersections will be entering the shape and even ones leaving it. With this information you will be able to get the line segements corresponding to your x value.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this