Finding Y given X on a Cubic Bezier Curve?

问题:

I need a method that allows me to find the Y-coordinate on a Cubic Bezier Curve, given an x-coordinate.

I've come across lots of places telling me to treat it as a cubic function then attempt to find the roots, which I understand. HOWEVER the equation for a Cubic Bezier curve is (for x-coords):

X(t) = (1-t)^3 * X0 + 3*(1-t)^2 * t * X1 + 3*(1-t) * t^2 * X2 + t^3 * X3

What confuses me is the addition of the (1-t) values. For instance, if I fill in the X values with some random numbers:

400 = (1-t)^3 * 100 + 3*(1-t)^2 * t * 600 + 3*(1-t) * t^2 * 800 + t^3 * 800

then rearrange it:

800t^3 + 3*(1-t)*800t^2 + 3*(1-t)^2*600t + (1-t)^3*100 -400 = 0

I still don't know the value of the (1-t) coefficients. How I am I supposed to solve the equation when (1-t) is still unknown?

回答1:

There are three common ways of expressing a cubic bezier curve.

First x as a function of t

x(t) = sum( f_i(t) a_i )
     = (1-t)^3 * x0 + 3*(1-t)^2 * t * x1 + 3*(1-t) * t^2 * x2 + t^3 * x3

Secondly y as a function of x

y(x) = sum( f_i(x) a_i )
     = (1-x)^3 * y0 + 3*(1-x)^2 * x * y1 + 3*(1-x) * x^2 * y2 + x^3 * y3

These first two are mathematically the same, just using different names for the variables.

Judging by your description "find the Y-coordinate on a Cubic Bezier Curve, given an x-coordinate on it." I'm guessing that you've got a question using the second equation are are trying to rearrange the first equation to help you solve it, where as you should be using the second equation. If thats the case, then no rearranging or solving is required - just plug your x value in and you have the solution.

Its possible that you have an equation of the third kind case, which is the ugly and hard case. This is both the x and y parameters are cubic Beziers of a third variable t.

x(t) = sum( f_i(t) x_i )
y(t) = sum( f_i(t) y_i )

If this is your case. Let me know and I can detail what you need to do to solve it.

回答2:

I think this is a fair CS question, so I'm going to attempt to show how I solved this. Note that a given x may have more than 1 y value associated with it. In the case where I needed this, that was guaranteed not to be the case, so you'll have to figure out how to determine which one you want.

I iterated over t generating an array of x and y values. I did it at a fairly high resolution for my purposes. (I was looking to generate an 8-bit look-up table, so I used ~1000 points.) I just plugged t into the bezier equation for the next x and the next y coordinates to store in the array. Once I had the entire thing generated, I scanned through the array to find the 2 nearest x values. (Or if there was an exact match, used that.) I then did a linear interpolation on that very small line segment to get the y-value I needed.

回答3:

Developing the expression further should get you rid of the (1 - t) factors

If you run:

expand(800*t^3 + 3*(1-t)*800*t^2 + 3*(1-t)^2*600*t + (1-t)^3*100 -400 = 0);

In either wxMaxima or Maple (you have to add the parameter t in this one though), you get:

100*t^3 - 900*t^2 + 1500*t - 300 = 0

Solve the new cubic equation for t (you can use the cubic equation formula for that), after you got t, you can find x doing:

x = (x4 - x0) * t      (asuming x4 > x0) 

回答4:

Equation for Bezier curve (getting x value):

Bx = (-t^3 + 3*t^2 - 3*t + 1) * P0x + 
     (3*t^3 - 6*t^2 + 3*t) * P1x + 
     (-3*t^3 + 3*t^2) * P2x + 
     (t^3) * P3x

Rearrange in the form of a cubic of t

0  = (-P0x + 3*P1x - 3*P2x + P3x) * t^3+ 
     (3*P0x - 6*P1x + 3*P2x) * t^2 + 
     (-3*P0x + 3*P1x) * t + 
     (P0x) * P3x - Bx

Solve this using the cubic formula to find values for t. There may be multiple real values of t (if your curve crosses the same x point twice). In my case I was dealing with a situation where there was only ever a single y value for any value of x. So I was able to just take the only real root as the value of t.

a = -P0x + 3.0 * P1x - 3.0 * P2x + P3x;
b = 3.0 * P0x - 6.0 * P1x + 3.0 * P2x;
c = -3.0 * P0x + 3.0 * P1x;
d = P0x;
t = CubicFormula(a, b, c, d);

Next put the value of t back into the Bezier curve for y

By = (1-t)^3 * P0x + 
     3t(1-t)^2 * P1x + 
     3t^2(1-t) * P2x + 
     t^3 * P3x

回答5:

So I've been looking around for some sort of method to allow me to find the Y-coordinate on a Cubic Bezier Curve, given an x-coordinate on it.

Consider a cubic bezier curve between points (0, 0) and (0, 100), with control points at (0, 33) and (0, 66). There are an infinite number of Y's there for a given X. So there's no equation that's going to solve Y given X for an arbitrary cubic bezier.

For a robust solution, you'll likely want to start with De Casteljau's algorithm

Split the curve recursively until individual segments approximate a straight line. You can then detect whether and where these various line segments intercept your x or whether they are vertical line segments whose x corresponds to the x you're looking for (my example above).