7 replies to this topic

[Chessmasterriley]

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:
Download from Host-A.net
Download Size: 24KB

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)

Thanks ahead of time, again.

Best,
Riley

Old Post:

Spoiler

Good morning/afternoon/evening ye of Brilliant Minds!

I have a question for you: what is the best way to store keyframe data while it's actively being edited?

At the moment, the best method I can think of would be to use a ds_grid(6,animation_length) like so:



Obviously, the '0's will be interpolated values and when saving the keyframe data, I'll save only the keyframed grid information. This method feels clunky to me and I wanted to see if anyone had any better ideas before I fully implemented this solution.

I was thinking there might be a way to store JUST the keyframes and then sort them as soon as the user adds another keyframe. Instead of a 1 or 0 in the keyframe slot,it would the the frame value - eg. 20, if on frame 20. But, there doesn't seem to be an easy way to sort a ds_grid of values and there's no way to copy the sort 'method' for several ds_lists.

A massive thank you, in advance, to all who help.

Best Regards,
Riley

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

[jo-thijs]

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.

[Chessmasterriley]

Perhaps you might know something about interpolation as well?

Spoiler

Ah! Thank you jo-thijs! I'm going to test this out immediately. I will edit with what turns up.

EDIT: Absolutely brilliant. It works flawlessly. So essentially, I'll increase the ds_grid size every time the user adds a new keyframe and then run the sort script right after adding the new data at the end. From there I can interpolate the values based on the current frame.

Thank you again, jo-thijs!

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

[Chessmasterriley]

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.

[jo-thijs]

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

[Gamer3D]

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 (t_k,p_k) 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 t_k < x < t_k+1). We will call the tangent at a point k "m_k".

Now we use those in a cubic spline. Remember, the derivative at the beginning must be m_k and the derivative at the end must be m_k+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.

[Chessmasterriley]

@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

[Gamer3D]

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: , 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.