Help: Function Curves for Animation Interpolation

Let's see if I understand. You've written some Bézier interpolation code, but want to adapt it to give constant velocity (as in d(arc-length)/d(parameter))?

The process is known as arc-length parametrisation (though you'd probably have better luck Googling in American English).

I suspect you'd get a stronger set of responses in the Maths and Physics forum. Maybe a moderator will be kind enough to move the topic.

I'm just going to lift some text from the Maya API guide.....

Quote:

The animation parameter curves in Maya are defined by a restricted set of cubic two-dimensional Bezier curves. It is defined by four points. P1 = (x1, y1) is the (key,value) pair for the first key. P2 = (x2, y2) is a point which defines the outgoing tangent direction at P1. P4 = (x4, y4) defines the second key and P3 = (x3, y3) is a point which defines the incoming tangent direction at P4. There are some basic restrictions for the x coordinates of these points: x1 <= x2 <= x3 <= x4. The 2-dimensional Bezier curve is defined as F(u) = [ u^3 u^2 u 1 ] * B * | P1 | , 0 <= u <= 1 | P2 | | P3 | | P4 | = [ B0(u) B1(u) B2(u) B3(u) ] * | x1 y1 | | x2 y2 | | x3 y3 | | x4 y4 | where B is the Bezier Basis matrix | -1 3 -3 1 | | 3 -6 3 0 | | -3 3 0 0 | | 1 0 0 0 | F(u) yields a vector of two cubic polynomials [ Fx(u) Fy(u) ] which define an (x, y) position on the parameter curve for some u in the range [0,1]. For an animation parameter curve, we are given the x position and want to know its corresponding y position. To do this we use x = Fx(u) and solve for u. Fx(u) is cubic and the restrictions on valid values for x2 and x3 guarantee there will be only one real root value for u. Once we know u, we can plug it into Fy(u) to get the y value. One important note is how the outgoing and incoming tangents directions for a key are saved internally and in the Maya Ascii file format. Instead of being specified as points, the tangent directions are specified as vectors. The outgoing tangent direction at P1 is specified and saved as the vector 3*(P2 - P1) and the incoming tangent direction is specified and saved as the vector 3*(P4 - P3). An animation curve is basically a restricted form of a bezier curve for which the keys serve as the control points and have tangent information embedded within them. There are two different methods for converting tangent information into the control points of the bezier hull and we have taken to calling the two methods weighted and non-weighted tangents. The animation curve is evaluated in a piecewise manner, which means that each segment between two keys is evaluated on its own, without regards to any other segment. The only time keys outside of a segment are considered is when tangent values are calculated for the spline, clamped and plateau tangent types. When evaluating an animation curve, a two stage process is used: 1. the evaluation time is examined to determine if it falls within the range of the animation curve, and if it does not evaluation is based upon the infinity settings for the animation curve 2. if the evaluation time falls within the range of the animation curve, the bezier parameters of the curve are computed and used as described below Animation curves may have either weighted or non-weighted tangents. With non-weighted tangents, tangents are implemented as vectors and P2 and P3 are internally adjusted to account for the time difference between P1 and P4. When evaluating a time within a segment, the following algortithms are used: For weighted tangents: where x is the start of the segment given the bezier x parameters a', b', c', d', find the parameter t which satisfies the formula: (time - x) = (t^3 * a') + (t^2 + b') + (t * c') + d' with t (and the bezier y parameters a, b, c, d) compute the value as: v = (t^3 * a) + (t^2 + b) + (t * c) + d For non-weighted tangents: where x is the start of the segment compute the parameter t as time - x with t (and the bezier y parameters a, b, c, d) compute the value as: v = (t^3 * a) + (t^2 + b) + (t * c) + d

to solve the cubic equation, see the following :

link1
link2
link3

so basically, re-arrange the bezier equation into the form

x^3 + ax^2 + bx + c = 0

and compute a,b and c. Use the method to solve the cubic equation listed in the links i posted above. You'll get a t value returned which you can then plug back into the same bezier equation you use for rendering to get your output y value...

Quote:

Original post by RobTheBloke I'm just going to lift some text from the Maya API guide...

Isn't that just plain and simple Bézier spline evaluation? The OP says he already has code for this.

Quote:

Original post by TheAdmiral Quote: Original post by RobTheBloke I'm just going to lift some text from the Maya API guide... Isn't that just plain and simple Bézier spline evaluation? The OP says he already has code for this.

No. The bezier equation for our X and Y values are:

Qx(t) = B0(t)X0 + B1(t)X1 + B2(t)X2 + B3(t)X3
Qy(t) = B0(t)Y0 + B1(t)Y1 + B2(t)Y2 + B3(t)Y3

where x is the time, and y is the output value we want, and t is our interpolant. The OP has this - but this is not the solution the OP wants.

Typically for an anim curve, we know the value of time (Qx(t)) but we can't use that as some scaled t value, since Qx(t) does not linearly map to t.

So, we take

Qx(t) = B0(t)X0 + B1(t)X1 + B2(t)X2 + B3(t)X3

but we know the value of Qx(t), so....

time = B0(t)X0 + B1(t)X1 + B2(t)X2 + B3(t)X3

Now solve for t as a cubic equation of the form (which will involve some re-arranging) :

t^3 + at^2 + bt + c = time

hint:take the follwoing matrix calculation for a bezier curve [t^3  t^2  t  1] *  | -1  3 -3  1 |    | X0 |                        |  3 -6  3  0 |    | X1 |                      | -3  3  0  0 | *  | X2 |                        |  1  0  0  0 |    | X3 |concatonate the basis and geometry matrices (since X0, X1, X2 and X3 are known), which will give you : [t^3  t^2  t  1]  | A |                   | B |                   | C |                   | D |therefore our co-efficients are...a = B/A;b = C/A;c = D/A;

when we have the value for t, put it into

Qy(t) = B0(t)Y0 + B1(t)Y1 + B2(t)Y2 + B3(t)Y3

to get the value at the requested time.

This relies on the restriction....

key0.time < key1.time < key2.time < key3.time

which ensures we always have a single solution for any given time value (cubic equations have 1 real, and 2 imaginary solutions).

All of this is only neseccary if you use a 2D animation curve. If you use a 1D bezier curve for the animation data (and keep time linear), then this is not needed since time directly maps to t. Unfortunately Maya, Xsi, Motionbuilder etc all use 2D curves since it's easier to write the tools to author the tangents, so to correctly interpret those curves you need to do it the way listed above.