Jump to content
  • Advertisement
Sign in to follow this  
whogben

Requesting help: Algorithm for smooth interpolation of keyframed animation values

This topic is 3455 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Animations in my game are stored as a series of keyframes and I use linear interpolation to tween between them when running them on a character - but linear interpolation either makes the animator use extra of keyframes (harder for them (me in this case)) or looks jerky. I'd like to smoothly tween between the values, but I can't figure out an algorithm for this. My terms: time[] is the array of keyframe times value[] is the array of keyframe values t# is the time I want a value for lowIdx is the index of the closest keyframe lower than t highIdx is the index of the closest keyframe higher than t rLowHigh# is the ratio of the distance of t from time[lowIdx] relative to the distance between time[highIdx] - time[lowIdx] vLowHigh# is the value from linear interpolation between value[lowIdx] and value[highIdx] My linear interpolation algorithm: rLowHigh# = (t - time[lowIdx]) / (time[highIdx] - time[lowIdx]) vLowHigh# = value[lowIdx] + (value[highIdx] - value[lowIdx]) * rLowHigh I've been trying to think of ways to smooth this, taking into account the keyframes before and after low and high, time[lowIdx - 1] and time[highIdx + 1] but I haven't come up with anything that works. What algorithms do you use that are smoother looking than linear interpolation? I'd really love to fix this :D

Share this post


Link to post
Share on other sites
Advertisement
You could probably work something out using Bezier Curves. Blender does it in its ipo curve editor. Bezier curves offer some nice flexibility.

For each line segment you are going to need to add two handles. These handles determine how each point blends into the other.

You will be dealing with a 2D cubic bezier curve. You calculate the final value as follows.

Do the inverse cubic on the x equation of the bezier curve. This should result in a number between 0 and 1

take the number between 0 and 1 and put that into the y bezier curve. The result of this is your final value.

Some potentially useful code.

float cubicBezier(float t, float a, float b, float c, float d)
{
float tflip = 1.0f - t;
return tflip * tflip * tflip * a + 3.0f * tflip * t * (tflip * b + t * c) + t * t * t * d;
}

float cubicBezierSlope(float t, float a, float b, float c, float d)
{
return t*t*3.0f*((d-a) + 3.0f*(b-c)) + t*6.0f*(a-2.0f*b+c) + 3.0f*(b-a);
}

// aproximates the inverse bezier of a cubic function
float inverseCubicBezier(float value, float guess, float a, float b, float c, float d)
{
unsigned int i;
float result = guess;

i = 8; // the number of times the value is aproximated, larger numbers make it more accurate but slower
while (i)
{
float x = cubicBezier(result, a, b, c, d) - value;
float slope = cubicBezierSlope(result, a, b, c, d);

if (x == 0.0f || slope == 0.0f)
return result;

result -= x / slope;

--i;
}

if (result > 1.0f)
return 1.0f;
else if (result < 0.0f)
return 0.0f;
else
return result;
}



The inverseCubicBezier is a functional implementation but I would imagine there would be faster ways of doing it. You can take my implementation as is or try to find a faster way. My suggestion to you, if you choose to use bezier curves, use the current inverseCubicBezier function. If it is too slow (probably wont happen unless you need to use it several thousand times per second) then find someway to optimize it.

An example of how to use the code

typedef struct {
float time;
float value;
} AnimationPoint;

AnimationPoint *pointA = /*your code*/;
AnimationPoint *handleA = /*your code*/;
AnimationPoint *handleB = /*your code*/;
AnimationPoint *pointB = /*your code*/;

float timeInput = /*your code*/;// needs to be between pointA.time and pointB.time


float t = (timeInput - pointA->time) / (pointB->time - pointA->time); // approximate linearly first

float t = inverseCubicBezier(timeInput, t, pointA->time, handleA->time, handleB->time, pointB->time);

float finalValue = cubicBezier(t, pointA->value, handleA->value, handleB->value, pointB->value);




Calculating the handles is the next step. You need to make sure that the time value for each handle is between the time values of pointA and pointB. You could probably base the handle value on points adjacent to the point with the handles. Play with blenders ipo curves, a vector are program, or any other program with bezier curves to get a feel for how it should work.

Share this post


Link to post
Share on other sites
Quote:
Original post by whogben
Animations in my game are stored as a series of keyframes and I use linear interpolation to tween between them when running them on a character - but linear interpolation either makes the animator use extra of keyframes (harder for them (me in this case)) or looks jerky.

I'd like to smoothly tween between the values, but I can't figure out an algorithm for this.

...

What algorithms do you use that are smoother looking than linear interpolation? I'd really love to fix this :D


Hi, you may want to try a quaternion SLERP, spherical linear interpolation. Its a 'little' more grunt work but should improve your interpolation over standard linear interpolation.

Share this post


Link to post
Share on other sites
Thankyou HappyCode & Lubby - I've saved your bezier code and will experiment with it soon! I'll also look into quaternion SLERP :)

http://erikloyer.com/index.php/blog/comments/cardinal_splines_in_actionscript/

I found this code written in action script that is a very simple way to do what I want - it implements cardinal splines - I've added these to my keyframes for each dimension (rotation, length, x, y) and with a tension of .5 it looks great.

The logic is unreadable because I've collapsed it to decrease memory usage etc, but it should be easy to translate into any language. The language here is blitzmax. # after a word means it is (or returns) a float.


Function getCardinalSplinePoint#(prevVal#, startVal#, endVal#, nextVal#, ratio#, tension#)
Return (((2 * ratio^3) - (3 * ratio^2) + 1) * startVal) + ((-(2 * ratio^3) + (3 * ratio^2)) * endVal) + ((ratio^3 - (2 * ratio^2) + ratio) * ((endVal - prevVal)*tension)) + ((ratio^3 - ratio^2) * ((nextVal - startVal)*tension));
End Function

prevVal = value[lowIdx-1]
startVal = value[lowIdx]
endVal = value[highIdx]
nextVal = value[highIdx+1]
ratio = how far we are between startVal and endVal (in time, not in value)
tension = how curvy to make it, 1 is v. curvy, 0 is straight lines.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!