Keyframe Interpolation Through Drawn Targets

This project started as an assignment for the Graduate Graphics course CS6491, and I ended up working on it a bit beyond the scope of the assignment. Basically you would draw a stroke on the screen and the moving animated line would pass through what you drew, with continuity determined by which "mode" you choose to use.

The user draws the desired future position(s) of the moving edge, and using interpolation, the edge moves to that position over the course of 1 second. If there are no more target keyframes drawn, the edge continues its motion along the curve used to interpolate the edge position as defined by the most recent user input.

Multiple edges can be drawn, and inbetween frames will be displayed showing the edge's future position at some fraction of time between any two keyframes. A logarithmic spiral interpolation method is used to animate the edge between keyframes. We extended this to also interpolate between keyframes using a Bezier curve and by linearly interpolating the motion between two consecutive spiral interpolations using Neville's algorithm.

The primary interpolation scheme is based on a logarithmic sprial. I first find the angle of rotation between the beginning position of the line and the drawn keyframe, as well as the ratio of starting and ending lengths of the line. Then I use these quantities, along with one of the endpoints from each of the lines defining the animation, to find a point F, about which both the beginning and ending lines of the animation can be said to be rotating around, using the following code, which solves a linear system :

pt SP_CTR(float a, float z, pt A, pt C) {
	float c=cos(a), s=sin(a);
	float D = sq(c*z-1)+sq(s*z);
	float ex = c*z*A.x - C.x - s*z*A.y;
	float ey = c*z*A.y - C.y + s*z*A.x;
	float x=(ex*(c*z-1) + ey*s*z) / D;
	float y=(ey*(c*z-1) - ex*s*z) / D;
	return P(x,y);
}

where a is the angle, z is the scale difference, and A and C are two points on the arc of the circle which I am trying to find the center of. Lastly, the current time position of the edge is derived via the following equation :

	e(t) = F + (sc^t) *(R(e,t*alpha,F) – F)

where t denotes the interpolant, usually varying between 0 and 1, e is the edge, R(a,t,b) means rotate a around b by t radians, F is the derived fixed point center, and sc^t means the ratio of the beginning and ending edge lengths, raised to the t power.

I also use the logarithmic spiral to derive the knots that define the Bezier curve, and then used them to define how I wished the line to move. I calculate the locations of the endpoints of the line at t=1/3 and t=2/3 and use them along with the beginning and ending edge end points as control points to define a cubic bezier interpolation curve for the animating line. Note that the line will often not interpolate to the control points. The equation for this is simple – just linear interpolations of linear interpolations of the results of the spiral interpolation.

Finally, using Neville’s algorithm, I interpolate between two sequential frames of spiral motion to derive a final motion that has C1 continuity. By taking the results of two consecutive spiral interpolations over the same time period, I then linearly interpolate between those motions to describe the final line motion

Below are videos of the interpolation process with various configurations (with links if the videos don't play automatically) :

Spiral Interpolation

Spiral Interpolation Through Keyframes

Intermediate Keyframes via Bezier Interpolation