# finding roots of a bezier curve

This topic is 3589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 on other sites
When i wrote my vector font system i simply subdivided the curve into n control points.

##### Share on other sites
Quote:
 Original post by staticVoid2I'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 staticVoid2with 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 staticVoid2or would it be more efficient to just sub-divide the curve into line segments?

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

##### 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.

1. 1
Rutin
23
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002150
×