A 2D keyframe animation system


Windows
--------------
The program consists of 2 windows:
(1) KeyFrameWindow class to define keyframe and rendering animation
(2) SpeedCurveWindow class to define speed curve they both extends Ortho2DWindow base class

Catmull-Rom splines is used to interpolate both curves. In both cases extra virtual keyframes are added at the very beginning and the very end.

The interface allow user to manipulate both speed and interpolate curves as follows :

(i) Insert keyframe at the beginning
(ii) Insert keyframe at the End
(iii) Insert keyframe in the middle of nearest 2 interpolate points for fine control.
(iv) Editing of existing keyframe
(v) Removal of keyframe
(vi) Clear the whole curve OR reset to default

For (iii), we find the closest point P to line distance for each line form by 2 keyframes A, B. In the case closest point Q (from P) in the line AB is not within segment of  A, B it is reject. Link list is used to store keyframes, this allow efficient add/remove keyframes operation.

Adaptive subdivision
-------------------------
Instead of using subdivision by checking the length between 2 points in curve and subdivide again if length too long. I use a faster approach by consider length of each curve segment, let say we have keyframe K0, K1, K2, K3, K4.
The number of segment for curve [K1, K2] is
(length(K0, K1) + 4*length(K1, K2) + length(K2, K3))/6.
similarly for [K2, K3] it is
(length(K1, K2) + 4*length(K2, K3) + length(K3, K4))/6.

where

length(Ki, K(i+1)) is the distance between point Ki, K(i+1) in SCREEN coordinates. The reason to take into account the length in previous segment and next segment is to handle case that K1 very close to K2 but K0 and K3 are far away - thus a loop is formed. Therefore we need more subdivision to faithfully represent the curve and can't just take screen coordinate between K1 and K2 as criteria.

Check for speed curve monotonic increasing
--------------------------------------------------
For speed cuve, special procedure is empolyed to gurantee monotonic increasing speed function. By default 4 keyframes are added. The first and last are virtual keyframe that allow user to modify (subject to monotonic increasing constraint). The second and second to last are fixed to make sure correct begin and end conditions.

For each keyframe when user insert/modify, we check if the neighbouring 4 segments are monotonic increasing. This is done by

(i) First check edit/new keyframe x, y coordinate are monotonic increasing with respect to neighbouring keyframes.
(ii) The above condition is not a sufficient condition since curve may have local max/min in the segment.

So I find the cubic equations of BSpline curve form by 4 keyframes. Then the derivative of it so it becomes quadratic equation. After solving u in both x and y dimension, there are at most 4 real roots. If both all of them are NOT within [0, 1] or no real root exists this mean the speed curve is  monotonic increasing. Otherwise the operation is not allow.

In case of remove, it is also possible that after a keyframe remove the 3 segments around it break monotonic increasing requirement. In this case remove is deny until user modify keyframes to a better position.

Computing time to distance in speed curve
---------------------------------------------
The speed curve is a cubic functions for each segments. So a cubic equation solver from a public open source code is employed for this task. (cubic.c and quadra.c). After the distance is solved it is used to search for 2 sample points found in adaptive subdivision above with distance fall in between. The correct u is interpolate from this 2 sample points.

For the search, we cache the value of last search as starting point. Since the function is invoke with increasing time value so the expected time to search is constant.

Rendering
-----------
We render interpolate keyframe as teapot and virtual keyframe as square. For efficient during animation we use display list for both curve and teapot so there is no need to recompute curve coordinate every frame during animation.

For line drawing, we turn on OpenGL line antialiasing using Blend mode and line smooth. This enchance quality of output.

Features
-----------
We draw a vertical time line in speed curve window which move with keyframe during animation. This help visualize the corresponding between them. In addition user can DRAG the timeline under time axis using left mouse button to see the position of interolate keyframe (draw in blue).

The inteface also displays the time [0, 1], distance [0, 1] and number of segment use in speed curve window.

For keyframe window it displays the total length and number of segments of curve. The total length is computed by summing individual line segments.


Speed of animation
----------------------
The program allow user to control speed of animation through a spin button. The method is just subdivide the timeline more/less so the object can travel slower/faster.

Load/Save
-----------
After user define both keyframe and speed curve, he/she can save the definition (together with speed of animation). So next time when program restart the user can reload the definition and run the animation easily.

Download program

Have fun !