# Keyframe Interpolation Methods

7 replies to this topic

### #1 Chessmasterriley

Chessmasterriley

Creative Concentrate

• GMC Member
• 1782 posts
• Version:GM:Studio

Posted 22 August 2012 - 06:25 PM

Alright, now that I've got a method of storing the keyframes, I want to know if anyone has a better method for linear interpolation and furthermore, a method for spline interpolation.

Here is the .gmk(GM7) that I was using for testing this:

Here is my code for interpolating the ds_grid I have set up for keyframes:
//interpolate(current_frame,ds_grid,column_number)
var frame1,frame2,val1,val2,i;
frame2=0
i=0
while frame2<argument0
{
i+=1
frame2=ds_grid_get(argument1,0,i)
val2=ds_grid_get(argument1,argument2,i)
}
frame1=ds_grid_get(argument1,0,i-1)
val1=ds_grid_get(argument1,argument2,i-1)
if i>0
{
return (val1+((argument0-frame1)/(frame2-frame1))*(val2-val1))
}
else
{
return ds_grid_get(argument1,argument2,0)
}

And, here is the draw code I'm using to display the information:
var xx,yy;
for (xx=0;xx<ds_grid_width(keyframes);xx+=1)
{
for (yy=0;yy<ds_grid_height(keyframes);yy+=1)
{
draw_text(128+xx*24,yy*24,string(ds_grid_get(keyframes,xx,yy)))
}
}

draw_text(0,0,string(fps))

var d1, d2, d3;
for (i=0;i<=animation_length;i+=1)
{
d1=interpolate(i,keyframes,1)
draw_text(320,i*20,string(i)+"  "+string(d1))
}

And this is the result:

On the left is the ds_grid data with the keyframes on the left column and the data on the remaining columns. On the right is the interpolated data. As you can see, the interpolation works, but, given the framerate displayed on the upper left, I don't think it's terribly efficient.

Here are my two questions I pose to you:

1) What's a more efficient interpolation method?
2) What's an efficient method for spline-based interpolation? (Wiki Link for Spline-Base Interpolation)

Best,
Riley

Old Post:
Spoiler

Edited by Chessmasterriley, 23 August 2012 - 12:05 AM.

• 1

### #2 jo-thijs

jo-thijs

GMC Member

• GMC Member
• 1464 posts
• Version:GM8.1

Posted 22 August 2012 - 06:52 PM

to sort a grid, based on the first column, you should have 2 scripts:
swap_rows (id,row1,row2)
var i,t;
for(i=0;i<ds_grid_width(argument0);i+=1){
t=ds_grid_get(argument0,i,argument1);
ds_grid_set(argument0,i,argument1,ds_grid_get(argument0,i,argument2));
ds_grid_set(argument0,i,argument2,t));
}

sort_grid (id)
var i;
for(i=ds_grid_height(argument0)-1;i>=0;i-=1)
swap_rows(argument0,i,ds_grid_value_y(argument0,0,0,0,i,ds_gid_get_max(argument0,0,0,0,i)));

Edited by jo-thijs, 22 August 2012 - 06:54 PM.

• 2

### #3 Chessmasterriley

Chessmasterriley

Creative Concentrate

• GMC Member
• 1782 posts
• Version:GM:Studio

Posted 22 August 2012 - 07:03 PM

Perhaps you might know something about interpolation as well?
Spoiler

Edited by Chessmasterriley, 22 August 2012 - 10:53 PM.

• 0

### #4 Chessmasterriley

Chessmasterriley

Creative Concentrate

• GMC Member
• 1782 posts
• Version:GM:Studio

Posted 22 August 2012 - 08:47 PM

Alright, I've edited my post to further my question:

1) What's a more efficient interpolation method?
2) What's an efficient method for spline-based interpolation?

Best,
Riley

EDIT: Hmm - perhaps paths are the answer - they already provide a built in spline interpolation calculation - I can even use them for linear interpolation! Eureka? Maybe? We'll see.

EDIT2: Nope - paths don't use the interpolation method I'm looking for. It looks as though they use bezier interpolation and I need Catmull-Rom Splines instead.

After reading this article I have suddenly realized the sheer complexity of this task. Please, oh please, let there be a mathematical genius out there that might have a way to implement the irregular keyframe timing; I'm stumped at this point. I'll continue with my linear implementation, but the animator will eventually need this to become a viable option.

Edited by Chessmasterriley, 23 August 2012 - 01:33 AM.

• 0

### #5 jo-thijs

jo-thijs

GMC Member

• GMC Member
• 1464 posts
• Version:GM8.1

Posted 23 August 2012 - 09:43 AM

what do you want to interpolate?
colors?
and how do you want it to be interpolated?
• 0

### #6 Gamer3D

Gamer3D

Human* me = this;

• GMC Member
• 1590 posts
• Version:GM8.1

Posted 23 August 2012 - 12:54 PM

After reading this article I have suddenly realized the sheer complexity of this task. Please, oh please, let there be a mathematical genius out there that might have a way to implement the irregular keyframe timing; I'm stumped at this point. I'll continue with my linear implementation, but the animator will eventually need this to become a viable option.

...

It's a cubic spline, which can be implemented using a Bezier spline, with the requirement being that each tangent (velocity at a given point) be parallel to the vector from the point behind to the point ahead, and with magnitude equal to the distance between those points divided by the time taken to get from the point behind to the point ahead.

Now let's make it easy for you to understand.

For 1 dimension (Each axis is interpolated independently for more dimensions), the spline for the dataset (tk,pk) is generated like this (x is the sampling time):

First, we wish to know the tangents (derivatives) for the points ahead of and behind x (find k such that tk < x < tk+1). We will call the tangent at a point k "mk".
$m_k = \frac{p_{k+1} - p_k}{t_{k+1} - t_k}$
Now we use those in a cubic spline. Remember, the derivative at the beginning must be mk and the derivative at the end must be mk+1 You can do those rather easily with a cubic bezier spline.

I'm currently out of time. I may come back and amend this, but we'll see how things go.
• 1

### #7 Chessmasterriley

Chessmasterriley

Creative Concentrate

• GMC Member
• 1782 posts
• Version:GM:Studio

Posted 23 August 2012 - 04:29 PM

@jo-thijs
I am interpolating x/y coordinates, angles, x/yscale, and image_blends. I have a working method for linear interpolation (or lerp...lol) for each of these data pieces, but I wanted a catmull-rom or cubic bezier interpolation method that wasn't horribly slow. Or, if you see a faster way I could calculate the linear interpolation(I've posted the code above), by all means hit me up with it!

@Gamer3D
Let's PRETEND like I know f**k all about what you just said.

Okay, serious face now. Yes, a cubic spline would work - I was thinking catmull-rom because of the smoother interpolation, but cubic splines will work perfectly fine as well. I do understand the math behind these calculations and would have no issues manually calculating points. What I'm struggling with is a GM solution that isn't slow as all get out. The way I have the data stored is in a 9 wide, keyframe # high ds_grid:

For the linear interpolation, I'm finding the nearest two keyframes and linearly calculating the value of the data at a given frame.

Thanks for the help, guys.

Best,
Riley
• 0

### #8 Gamer3D

Gamer3D

Human* me = this;

• GMC Member
• 1590 posts
• Version:GM8.1

Posted 23 August 2012 - 09:05 PM

Okay, serious face now. Yes, a cubic spline would work - I was thinking catmull-rom because of the smoother interpolation, but cubic splines will work perfectly fine as well. I do understand the math behind these calculations and would have no issues manually calculating points. What I'm struggling with is a GM solution that isn't slow as all get out. The way I have the data stored is in a 9 wide, keyframe # high ds_grid:

A Catmull-Rom spline is a cubic spline with additional rules for the tangent at the control points.

After calculating the tangents, I recommend a cubic Bezier curve to connect the control points because it's quite easy to put into layman's terms. The (explicit) cubic Bezier curve formula is: $f(t)=(1-t)^3A+3(1-t)^2tB+3(1-t)t^2C+t^3D$, where t must be between 0 and 1 (inclusive).
A and D are positions at t=0 and t=1, respectively. (B - A) / 3 is the derivative at 0, and (D - C) / 3 is the derivative at 1. You now have been told how to create a Catmull-Rom spline with unit (1) time intervals.

For non-unit intervals, all we need to do is linearly map t from the interval to [0, 1] and adjust B and C accordingly. To do that, divide t and multiply (B - A) and (D - C) by the length of the interval.

So yeah. Everything you wanted is right there. It doesn't require expensive calculation, and it gives you a smooth spline.
• 1

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users