🔒 Locked

Requesting help: Algorithm for smooth interpolation of keyframed animation values

Started by whogben Jan 5, 2009 at 5:06 AM 2 replies 3.4k views

Original Post

Jan 5, 2009 at 5:06 AM

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

HappyCoder

Jan 5, 2009 at 5:17 PM

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 functionfloat 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.timefloat t = (timeInput - pointA->time) / (pointB->time - pointA->time); // approximate linearly firstfloat 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.

lubby

Jan 5, 2009 at 11:26 PM

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.

whogben

Jan 6, 2009 at 12:12 AM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.