Sign in to follow this  
JonW

Solving a cubic Bezier at a particular coordinate

Recommended Posts

JonW    173
Hello, I'm interested in finding the point(s) where a 2D cubic Bezier curve crosses a particular horizontal or vertical line. For example, say I'm looking for the y coordinates of the curve at a particular value for x. It is pretty obvious what you would do: 1.) solve for t in the Bezier equation x = a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3, where a,b,c,d are the control points' x coordinates. 2.) go through the discovered real values of t and, for each 0 <= t <= 1, find y = e(1-t)^3 + 3ft(1-t)^2 + 3gt^2(1-t) + ht^3. The problem I'm having is solving for t. It basically comes down to an equation of the form at^3 + bt^2 + ct + d = 0. I've tried using the cubic formula to solve this but I find it so hard to come up with a general solution for t. Is there a simple formula in terms of t? Or perhaps a better way of doing this? Thanks, Jon

Share this post


Link to post
Share on other sites
jyk    2094
I don't think it will get much simpler than just solving the cubic (although I suppose an alternative would be a numerical or iterative solution).

Share this post


Link to post
Share on other sites
JonW    173
That's what I'm having trouble with. I spent a few hours trying to work it out on paper, but it became too complex for me to be confident in the result. My TI-89 doesn't know how/want to solve it.

Are there any good (preferably cheap/free) software programs that could solve these sorts of problems?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by JonWoyame
Are there any good (preferably cheap/free) software programs that could solve these sorts of problems?
Dave Eberly has some polynomial solvers on his site geometrictools.com, including cubic. You're probably already familiar with the general formula, but details can be found here.

Closed-form solutions to polynomials aren't always particularly stable, so it might be worth considering other options as well. If you feel like it, you might describe what exactly it is you're doing, i.e. what the line-curve intersection is for. With that info, people might be able to give you better suggestions about things to try.

Share this post


Link to post
Share on other sites
John Schultz    811
Simplest geometric solution: Convert the Bezier curve into sufficiently short line segments and test segments for intersection (adaptive de Casteljau will probably be the most efficient).

See also Bezier clipping (from link below).

Bezier Clipping info.
de Casteljua info.

de Casteljau methods are very easy to implement and relatively fast (also easy to make stable and deal with numeric issues). Since other cubic forms can be converted to the Bezier basis, the de Casteljau method can also be used for other cubic forms after transformation (for example, NURBS-based packages convert to Bezier form for complex operations (not necessarily using de Casteljau), then convert back to NURBS form).

Share this post


Link to post
Share on other sites
JonW    173
What I'm trying to do is fill a region bounded by bezier curves with a shading value from 0-255. These values go into an image buffer of a particular maximum width and height.

The way I plan to do this is to iterate through all of the rows in the buffer, calculate the value of each curve's intersection(s) with that row's y value (actually, the center of that row, which is y + 0.5), and check each pixel in that row against the calculated intersections. If the pixel has an odd number of intersections to its right, it is inside the region defined by the curves. If even, the pixel is outside the region.

I went with this solution because I could use the values to do some antialiasing. I could adjust the shade between 0-255 according to Manhatten distance. There are some other details that I didn't include, but that's the basic algorithm.

Maybe someone knows a better way to fill a region with antialiasing at the border?

[Edited by - JonWoyame on April 24, 2006 11:45:00 AM]

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