# Solving a cubic Bezier at a particular coordinate

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

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
Quote:
 Original post by JonWoyameAre 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 on other sites
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).

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 on other sites
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]

• 10
• 18
• 14
• 19
• 15