Finding Y given X on a Cubic Bezier Curve?

Question

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?

Pontine

More a maths question... – Rally

Very well, I'll go ask the Maths people instead. I assumed it being used in computing would mean people here might know. Thank you. – Pontine

Even in 2018 this question pops up enough to still warrant a real answer, so I wrote up the code for getting the symbolic solution for this over on https://mcmap.net/q/907876/-cubic-bezier-curves-get-y-for-given-x-special-case-where-x-of-control-points-is-increasing, with a second answer that gives the imprecise (but often good enough) binary search solution. – Yoruba

Answer 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) x_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.

Unfrock

Can you help me solve the parametrized version? I have the parametrized x and y. I need y given x. So I don't know t but know x. – Rheumatoid

@activatedGeek - You can't necessarily solve your case. There may be no solution, one solution, many solutions or even infinitely many solutions (sad). Your best bet is to note that the bezier curve is guaranteed to fall inside the convex hull of its control points. Then consider whether each segments CVH could cross your x value, if it does keep it in a list, if it doesn't - forget it. Now on each segment apply a bezier mid-point split to get a new list of bezier segments. Repeat discarding and splitting until all segments are "small" enough. They are your solutions. – Unfrock

Ok I would go straight to the source. Could you tell me how this works? I understand how the curve is being drawn on the left. What I don't understand is that how would one convert the time of animation to map the t parameter of a Bezier curve to cover an animation in some T seconds. – Rheumatoid

In case future visitors find this answer, for monotonically increasing curves ("curves that look like normal functions instead of having true vertical/horizontal tangents, or curving 'back' over itself) there is a symbolic solution, explained over on https://mcmap.net/q/907876/-cubic-bezier-curves-get-y-for-given-x-special-case-where-x-of-control-points-is-increasing - This covers quite a lot of use cases, such as CSS animations, parametric EQs, etc. – Yoruba

@MichaelAnderson What is the f_i function in your answer? – Cubical

The f_i are the cubic bezier basis functions: f_0(z) = (1-z)^3, f_1(z)=3(1-z)^2z, f_2(z)=3(1-z)z^2, f_3(z)=z^3. – Unfrock

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

Seibert

Answer 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) 

Apposite

Answer 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

Quit

"Solve this using the cubic equation" is a good answer on maths.stackexchange, but a bad answer for a Stackoverflow C++ question. Without code to show the implementation for the cubic formula, this is an incomplete answer. – Yoruba

Should the last term in the cubic form be "(P0x) - Bx" instead of "(P0x) * P3x - Bx"? And the formula for d be "P0x - Bx" and not just "P0x"? – Deposition

Answer 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).

Laundromat

But remember that just because there is no general solution, doesn't mean there are no solutions for all cases. If the curve is invertible, then there definitely are solutions, and the answer to this problem is discussed in https://mcmap.net/q/907876/-cubic-bezier-curves-get-y-for-given-x-special-case-where-x-of-control-points-is-increasing – Yoruba