[quote=“Markus_Persson link=topic=12261.msg97671#msg97671 date=1138397887][quote author=Spasi,post:9,topic:26010”]
Oh how I struggled with that one. The documentation is… wrong, so that one is the result of a lot of guessing and manual .xsi file inspection… it seems to work with my test models, but feel free to do some more testing. =)
It makes absolutely no sense that it would use the input vectors from the next keyframe as the output from the current (instead of the output vectors from the current), so I think it’s wrong. 
[/quote]
OK, I spent the whole weekend and a couple of hours today trying to finally find a solution for this. I think I succeeded! 
So, basics first. I found this definition in an FTK file (xsi_fcurve.h):
[quote]Interpolation (how the value is evaluated between FCurveKeys) can be constant, linear, or cubic. Cubic means that a Bezier curve is calculated as the interpolation between the keys. XSI uses cubic Bezier curves defined as follows:
Definition from de Casteljau’s algorithm:
Four points A, B, C and D in the plane or in three-dimensional space define a cubic Bezier curve. The curve starts at A going toward B and arrives at D coming from the direction of C. In general, it will not pass through B or C; these points are only there to provide directional information. The distance between A and B determines “how long” the curve moves into direction B before turning towards D.
[/quote]
A is the “left” keyframe and B is its right tangent. D is the “right” keyframe and C is its left tangent. I believe that explains it well.
One thing I noticed was that de Casteljau’s algorithm is not the most efficient way to do cubic interpolation. Simply evaluating an optimized version of the curve’s parametric form is 4 instructions less. Compare the following:
de Casteljau’s algorithm
public static float interpolateCubic(float a, float b, float c, float d, float t) {
// 18 instructions
float ab = a + (b - a) * t;
float bc = b + (c - b) * t;
float cd = c + (d - c) * t;
float abbc = ab + (bc - ab) * t;
float bccd = bc + (cd - bc) * t;
return abbc + (bccd - abbc) * t;
}
Parametric form
public static float interpolateCubic(float a, float b, float c, float d, float t) {
// B(t) = a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3
// Let tInv = (1-t)
// B(t) = a * tInv^3 + 3 * t * tInv * (b * tInv + c * t) + d * t^3
// B(t) = tInv * (a * tInv^2 + 3 * t * (b * tInv + c * t)) + d * t^3
// 14 instructions
float tInv = 1.0f - t;
return tInv * (a * tInv * tInv + 3.0f * t * (b * tInv + c * t)) + d * t * t * t;
}
Anyway, the cubic method in your Interpolator class is wrong, simply because you’re not taking into account the x-axis values (time in keyframes). Imagine a key with “flat” left/right tangents (aligned to x-axis, height equal to the key). Grab one of the tangents and drag it left or right, without changing the height. Obviously, the curve profile is changing even without touching the y-axis values. We have to incorporate this effect to the interpolation algorithm. Some pics (click for hi-res, curve sampling is sparse on purpose to show the differences):
Original curve in XSI
http://www.zdimensions.gr/spasi/public/060130/curveXSI_thumb.jpg
Interpolating Y-Axis values only
http://www.zdimensions.gr/spasi/public/060130/curveYOnly_thumb.jpg
So, why don’t we just interpolate the x-axis values too? Yeah, that’s also what I thought would easily give some kind of solution. But, no:
Interpolating X-Axis values
http://www.zdimensions.gr/spasi/public/060130/curveXPulled_thumb.jpg
Well, we did get a nice curve. But there’s obviously something wrong with the above image. The (not so) vertical lines show where/when exactly we asked an interpolated value and what we ended up getting. As you can see, the sampled points tend to be pulled towards areas of the curve that change significantly. This is great if you only need to draw the curve (with a given amount of samples, you get the best quality), but not so if you just want to get an interpolated value at some time offset. You want the value at exactly that offset.
My solution was the simplest I could think of, but I believe it’s far from optimal performance-wise. Suppose I want to get the interpolated value at time t. Let Bx and By be equivalent to calling the above interpolateCubic with the x-axis and y-axis values respectively. To get the correct value, I have to interpolate the y-axis values at a time t’, where t’ is the value that satisfies the equation Bx(t’) = t. So, the correct result would be By(t’).
To solve the Bx(t’) = t for t’, we need to bring the curve’s parametric form to a better one:
B(t) = a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3 ==> (1)
B(t) = (-a + 3b - 3c + d)t^3 + 3(a - 2b + c)t^2 + 3(-a + b)t + a ==> (2)
// Let A = (-a + 3b - 3c + d)
// Let B = (a - 2b + c)
// Let C = (-a + b)
B(t) = At^3 + Bt^2 + Ct + a (3)
(1) is the original equation, (2) is what occurs after some math and (3) is a standard, solvable cubic equation. So, once you’ve solved the equation, with something like this:
public static float interpolateCubicInverse(final float a, final float b, final float c, final float d, final float t) {
float A = (-a + 3.0f * b - 3.0f * c + d);
float B = (3.0f * (a - 2.0f * b + c));
float C = (3.0f * (b - a));
float D = a - t;
int rootCount = solveCubic(A, B, C, D, roots, 0); // TODO: How to handle multiple roots?
return roots[0];
}
You can finally get the proper result:
float t = ...;
t = interpolateCubicInverse(x1, influenceX1, influenceX2, x2, t);
float value = interpolateCubic(y1, influenceY1, influenceY2, y2, t);
Correct Interpolation
http://www.zdimensions.gr/spasi/public/060130/curveCorrect_thumb.jpg
Some notes:
- Solving the cubic equation is the most costly part of this algorithm. 20+ instructions, one sqrt and two cube roots for the common case.
- I’m not sure how to handle multiple roots returned by solveCubic. From my tests, it occured very few times and just picking the first one (they’re ordered by value) produced no problems.
- An obvious optimization is to take advantage of equation (2). By storing A, B, C per key interval, instead of key & tangent values, interpolateCubic falls to 9 instructions, whereas solveCubic is the only cost in interpolateCubicInverse.
- I’m sure there are faster ways. One is obvious from the “Interpolating X-Axis values” image: Sample the curve at several points, optimize based on an error threshold, then store the resulting keyframes as a linear curve. There’s a performance-memory trade-off here of course.
Pheew! Sorry for the long post!
