Keyframe system

Quote:

Original post by noooooon I would need some advices for the Bezier interpolations. Since Bezier equation are defined by a time value (t) in the range [0, 1], finding the Y value for a specified X value is not direct.

You need to re-paramaterise the bezier function by arc-length
I know two good methods for this (and there are infos all over the place)
* You can use calculus, I suppose you differentiate with respect to t and integrate with respect to x.
* You can appoximate the curve and its length using linear segments

Quote:

- Is there a special kind of bezier equations that would be more suited for this purpose ?

I don't know, however you could always just limit the freedom of the tangent handles so that the user cannot create convex curves in the first place.

Quote:

- To find the Y value of a specified X, do you suggest to use the Newton-Raphson method every frame ?

Its probably not necessary, paramaterise by arc-length then you can pick any distance along the curve and get the Y coordinate; then if you guarentee the curve has a many-to-one mapping of X to Y components then you can get Y from X.

Thanks for your feedbacks.
I'll search about arc-length re-paramaterisation.

From what I read so far, it seems that arc length parametrization is mainly used to move at a constant speed along bezier spline. Like so :


It means that I can get the real length of the bezier spline at any given time t. As you said "paramaterise by arc-length then you can pick any distance along the curve"

But even with parametrization, I still don't understand how the Y of a given X can be found :


The red dots divide the parametrized spline with a constant interval.
The blue dots are the coordinates I need to find.

Hmm indeed.
I feel I must appologise as I now think you're right; and I've led you on a wild goose chase.
Evidently arc-length paramaterisation isn't what you're after and had I thought more before posting initially I would have realised [ignore].

So how about some more useful advice then...

Well firstly, you say you're creating a keyframe system. Typically animators want to be able to control keyframes using time-signatures. The problem is that bezier curves are parameterised with t which isn't 'time'. What we normally do is re-parameterise by arc-length and then use the good old speed = distance / time equation to allow not only constant-speed movement over the curve but also so the artist can control movement based on time (which is typically more useful).
This is why I led you down that route because I had that in my head.. although you may still want to consider that as an option.

However, it's not what you originally asked, what you're asking for is a cartesian equation from the parametric one.
So you have:
x = f(t)
y = g(t)

but you need:
y = f(x)

Probably the best approach to this is:
t = f(x)
y = g(t)

thus: y = g( f(x) )

The problem being that getting t = f(x) seems deceptively difficult, especially with high-order bezier curves.
I'm not sure my mathematics skills are quite good enough to derive that function for you im afraid, so in light of that I think I'd be inclined to go with you suggestion of using Newton-Raphson Iteration to approximate the function.

I thought the best way to get the Y value of the desired X was maybe to sample the curve enough and make some linear interpolations bewteen the sampled values. Keyframe's positions are constant and many values will need to be calculated (one for each frame).

So sampling the curve and caching the sampled points every time a user move a key seems to be a good solution.

I still wonder how to calculate the sampling precision.

Bezier curves are a little tricky, because even though you see a 2D curve there are typically three variables at play - X and Y, which are dependent parameters, and then t, which is the independent parameter.

It seems to me that you only want to keyframe a single parameter Y, but also want to visualize it as a 2D curve. In that case, all you need to use is the standard functional form Y = f(t), where t is both the independent variable AND the value you use for X when drawing the curve. f(t) can be whatever function you want. The equations boil down to:

X = t
Y = f(t)

Thanks for your answer.

How would you suggest to transform the X to t so t is still inside [0, 1] when calculating the bezier value ? t = (X - p0.x) / (p3.x - p0.x) ?

Anyway I'll try that as soon as possible.
Thanks

Quote:

Original post by noooooont = (X - p0.x) / (p3.x - p0.x) ?

yes. This is basically how Maya/XSI et al do it. Anim curves are basically just 1D hermite or TCB curves....

Thanks, It seems to work but I'm getting a little difference between :

- The black curve, a standard bezier, defined as x = f(t) and y = g(t)
- The red curve defined as X = t and Y = g(t)



I guess it can come from the way I transform X to t :
t = (X - p0.x) / (p3.x - p0.x)

This seems to be a really linear transformation, and maybe it shoudn't ?

Here is my code :

How are you going to use your keyframing system? If you could be more specific then you might get a better answer.

First of all, your statement "In a keyframe system there is allways only one possible Y for a particular X. But with bezier equations more than one solution could be found."

Is not entirely correct, it is true for a 2 dimensional bezier curve, but a bezier curve in general could which could be 1 to n dimensions.

Without knowing more about your application, I would suggest you do as Zipster suggests and use a one dimensional bezier curve. And it seems like it is the solution you want when looking your the images.

And yes there will be a difference between the 2d and the 1d version. It comes from the fact that it is two different curves.

The t = (X - p0.x) / (p3.x - p0.x) parametrisation will however have an effect if you look at the derivates of the curve, but not the look of your curve.

dmatter:s solution of feeding one bezier calculation into another will sort of make it a bezier (at least a polynomial) curve of the 6th degree instead of the 3rd (assuming you use a cubic bezier curve).

If you do want to find the Y solutions (can be multiple) for a specific X then I suggest using subdividing the bezier curve and for each consecutive step sorting out segments not in solution by filtering on the bezier curve segments convex hull against the X value. Newton-Raphson can then be used to when sufficient close to the solutions.

Quote:

Original post by mzeo77 How are you going to use your keyframing system? If you could be more specific then you might get a better answer.

As the 3dsmax / Maya / XSI keyframe system.

Quote:

Original post by mzeo77 First of all, your statement "In a keyframe system there is allways only one possible Y for a particular X. But with bezier equations more than one solution could be found." Is not entirely correct, it is true for a 2 dimensional bezier curve, but a bezier curve in general could which could be 1 to n dimensions.

It may sound stupid but I didn't find any 1d bezier curve equation, that's why I keep messing with 2D bezier equation. I'd be glad to see a 1D bezier equation, and ever glader if it fits my input / output :

input :
- PointF p0 : the first 2D point
- PointF p1 : the first 2D point tangent
- PointF p2 : the second 2D point tangent
- PointF p3 : the second 2D point
- Float X : a X coordinate (should be bewteen p0.X and p3.X)

output :
- Float Y : the Y coordinate of the point on the bezier curve that has the X coordinate.


(on this picture all the tangents are horizontal, but they are normal 2D points that could move almost freely with the restriction that the curve musn't have 2 Y for a X value)

The reason there is a difference between the red and black curves is because one uses X = f(t), while the other one uses X = t. One is cubic (I assume) and one is linear. I probably should have mentioned before that they won't look the same, since the standard Bezier curve "look" comes from parametering both X and Y using Bezier functions of a third variable 't'. In this case only Y is using a Bezier function of 't', while X is linear function of 't'. It sounds strange but the math works out :)

I'm not sure if that's how Max and other programs do it. They might be really using Bezier curves for both X and Y, and inversing mapping X to 't' and plugging in to find Y, i.e. Y = f(g^-1(X)). There are certainly more than a few ways you can do keyframing.