   Bezier Curve for Animation
  I'm using blender to export animation sequences, and internally it uses cubic bezier curves to represent animations. It exposes the X/Y coordinates of all the control points through the API and I was exporting these points to reconstruct the curves in my program. (Curves and handles like so:)However I'm a little stumped as to exactly how I would go about this. All of the bezier curve equations I've seen are parametric, such that given a time T from 0 to 1 it will return an X and Y value for that section of the curve. Although for these curves X is the animation time variable, not T. If this is the parametric equation for solving a cubic bezier curve:X(t) = (1-t)^3*X0 + 3(1-t)^2*t*X1 + 3*(1-t)*t^2*X2 + t^3*X3  t = [0,1]Y(t) = (1-t)^3*Y0 + 3(1-t)^2*t*Y1 + 3*(1-t)*t^2*Y2 + t^3*Y3  t = [0,1]Then does this mean to find Y(X) (which is the curve shown) I need to first solve this equation for t(X) (yuck), and then plug t back in to find Y? I first thought I could just let t = (x - x0) / (x3 - x0) and plug this in for Y(t), but now this seems naive and I'm pretty sure won't accurately reconstruct the curve.If this is the case, what would be a good idea to handle this ingame? Just precompute ~100 X,Y pairs and just do linear interpolation between them? That seems like it might be the fastest method.I guess to sum it all up I'm a little confused why these bezier curves are used for this, if animation curves are not parametric. The idea that I should have to find cubic roots of an equation just to find the Y value for a given X seems very onerous, and I just feel like I'm missing a simpler way.   
Quote:Original post by karwostsHowever I'm a little stumped as to exactly how I would go about this. All of the bezier curve equations I've seen are parametric, such that given a time T from 0 to 1 it will return an X and Y value for that section of the curve. This is only true if you have a 2D bezier curve. In your blender example all displayed curves are 1D. So the x-axis is time and the y-axis is LocX(t),LocY(t) ...As you can see, you have selected 6 values (rotation X,Y,Z and position X,Y,Z) which results in 6 separated 1D curves (two curves seem to overlap). ;Quote:Original post by Ashaman73Quote:Original post by karwostsHowever I'm a little stumped as to exactly how I would go about this. All of the bezier curve equations I've seen are parametric, such that given a time T from 0 to 1 it will return an X and Y value for that section of the curve. This is only true if you have a 2D bezier curve. In your blender example all displayed curves are 1D. So the x-axis is time and the y-axis is LocX(t),LocY(t) ...As you can see, you have selected 6 values (rotation X,Y,Z and position X,Y,Z) which results in 6 separated 1D curves (two curves seem to overlap).A common misconception (as is the use of path-length-paremeterization to evaluate 2D anim curves). I can't speak for blender, however all the others packages I have used (Maya/Max/Xsi/Motionbuilder/Endorphin) make use of 2D beziers for anim curves. From the Maya documentation: 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: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.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) + dFor 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) + dTo explain in simpler terms..... The 2D curves are 2 independent 1D anim curves. The X curve modifies the time, and the Y curve modifies the value. We need to plug a t value into the Y curve to get the final value, however we do not know the correct value of t (yet).To find that value we must use the X curve....  (but not in a normal fashion!)We know the control point values (they are the X curve values), and the final result (which is the time value we want to evaluate the curve at), but we do not know the value of t. Therefore, our aim is to solve for t. Once we know t, we can plug that t value into the Y curve, and out pops our desired result..... To find t, we have 2 choices:1. The Brute force solution. Using a binary search you can (relatively quickly) find the t value that gives the time value we want. This method is easy to implement and is fine for an offline process.2. Use the cubic formula to solve the X curve for t. This has a few problems with it. Firstly, there are always 3 solutions to a cubic equation - two of which are imaginary. We can of course disregard 2 of those if, and only if, we apply some constraints. In our case, we ensure that the X control point values will only ever increase. i.e. 0,2,1,3 would be invalid, but 0,1,2,3 is fine. This ensures we never get more than 1 real solution. I'll leave it as an exercise for the reader to figure out which of those values to disregard (I'm bounds by NDA's unfortunately). It's a little bit tricky, but very do-able with a little bit of cleverness ;)p.s.;  Hmmm.. I think Rob is right, my fault, sorry :-)   ;Quote:Original post by karwostsThen does this mean to find Y(X) (which is the curve shown) I need to first solve this equation for t(X) (yuck), and then plug t back in to find Y? Yes. Quote:Original post by karwostsI first thought I could just let t = (x - x0) / (x3 - x0) and plug this in for Y(t), but now this seems naive and I'm pretty sure won't accurately reconstruct the curve.You are correct. It won't produce the correct results (although it can look near enough that some people think this is the proper way to do it....)Quote:Original post by karwostsIf this is the case, what would be a good idea to handle this ingame? Just precompute ~100 X,Y pairs and just do linear interpolation between them? That seems like it might be the fastest method.Games like simple fast linear interpolation (although cardinal and Catmull-Rom splines can be useful for translational channels), so normally you just sample the data rather than using the curves directly (I'd also recommend using a very simple compression algorithm. Preferably one that is not some form of RLE, but compresses each key independently). This is especially important when it comes to blending animations, when the cost of solving the cubic beziers for 100 bones, for 12 anims cycles that are being blended together at the time becomes a bit too costly!Quote:I guess to sum it all up I'm a little confused why these bezier curves are used for this, if animation curves are not parametric. The idea that I should have to find cubic roots of an equation just to find the Y value for a given X seems very onerous, and I just feel like I'm missing a simpler way.It's purely for key tangent control. Using a 1D curve for X would give you the ability to accelerate and decelerate the value. However if you try and write a curve editor for this, you very quickly realise you don't get as much control as you'd like over the central portions of the curve. By adding a second curve for time, you can get an additional level of control that effectively allows you to accelerate/decelerate time in addition to the value. Of course if you told an animator they were doing this, they'd just stare back at you blankly and think you're a bit mental ;)  But ultimately that's just because 2D bezier curve editors are so intuitive, people simply don't realise what the full effects of manipulating a tangent are....   ;  Great, thanks :)   