Requesting Help: Smooth Keyframe Interpolation Alg

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

Is this 3d??

If it's 2D then use Fixed-Step logic timing to update the anim frame and then display the image frame in the draw cycle.

Look at DMAZ code in this thread:

http://www.blitzmax.com/Community/posts.php?topic=80553

Its awesome! I won't pretend i fully understand the passing of the 2 functions but this is the best working sourcecode i have found so far.

Goodluck

I use parametric animations.
That is: normalize start and end situations (start = 0, end = 1) e.g. (millisecs() - startTime) / float(duration)

and then use the parameter to animate.
Then you can bias the parameter to ease-in or out the animation.
I hope this is what you mean.

example:

SuperStrict

Graphics 800, 600, 0

'In this example I will use elapsed time as a parameter.
'The tween will take fDuration milliseconds
Local fDuration# = 3000.0	'3000 millisecond
Local iStart% = MilliSecs()

Local fp#				'fp is the animation parameter
Local fStartX# = 50		'start at 50,550
Local fStartY# = 550
Local fTargetX# = 750	'move to 750,50
Local fTargetY# = 50


While Not KeyHit(KEY_ESCAPE) 	'press Esc to quit
	Cls
	'use elapsed time to calculate parameter
	'you can use whatever you like: number of frames, MouseX(), the hue of a color, the number of characters typed in a string, etc.
	fp = (MilliSecs() - iStart) / fDuration
	
	If fp >= 1 Then		'restart animation
		fp = 1
		iStart = MilliSecs() 
	End If
	
	'select one of the bias functions
'	fp = BiasIn(fp) 	'accelerate
'	fp = BiasOut(fp)	'decelerate	
'	fp = BiasBoth(fp)	'well.. accelerate and decelerate
	
	'use parameter to find the 'inbetween' positions
	Local fx# = fp * (fTargetX - fStartX) + fStartX
	Local fy# = fp * (fTargetY - fStartY) + fStartY
	
	'draw an oval at calculated x,y position
	DrawOval(fx-20, fy-20, 40, 40)
	Flip
Wend
	
End

'there are a lot of bias functions suitable. I've chosen these...
Function BiasIn#(fp#) 
	Return Sin((fp - 1) * 90) + 1
End Function

Function BiasOut#(fp#) 
	Return Sin(fp * 90)
End Function

Function BiasBoth#(fp#) 
	Return (- Cos(fp * 180) + 1) / 2.0
End Function

You could also try splines, like bezier curves, where the start and end points are the previous and next tween points, passing through the mid-point as the current tween position. Then you can find a step along the slpine curve. This would also give you smoother tweening with rounded corner movements rather than sudden changes in trajectory with sharper angles.

Thanks everyone!

The answer was to use Cardinal Splines which I got the code for here:

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

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

The logic is unreadable because I've collapsed it for speed, but you can get it from the website too - a tension value of .5 looks great on the keyframes :D

There is one trick to it that isn't mentioned: It assumes an equal distance between keyframes in time between prevVal, StartVal, EndVal and nextVal - the trick here (because I have uneven keyframes) is to use linear interpolation to grab the right values for those times rather than the actual early and late keyframe values.

Later on and when I'm sure it's working I'll post my keyframe code.

Best,
Will