KFAST - Key Frame Animator with Skeletal Technique

KFAST is a collection of functions to implement a two-dimensional
object based animator designed to use the skeletal technique of
modeling objects and simple tweening to free the animator from the
labors of producing smooth transitions between key drawings.
A crude demo program has been included utilizing the routines.
   
*** The req.library is required for the demo program ***

Public Domain, Source in C included.
Author:  Craig M. Lever

DISCLAIMER
   I make no warrantee to the usefulness of this program nor can I
   be held responsible for any damage caused while using it.
   I release this program and source into the public domain.   

REACHING ME
   While I'm releasing the source as PD I'm still interested in hearing
   if anyone puts the source to good use.

   I can be reached at the following mailing address:
        Craig Lever
        RR #1.
        Airdrie, Alberta, Canada.
        T4B 2A3

   I can also be reached through some of the Fido Amiga echoes
   or by Fido Netmail at:
        Craig Lever @ 1:134/27.0 - The AMUC Express
   or by UseNet Netmail at:
        cmlever@wwshop.cuc.ab.ca - The Wizard's Workshop

THE PROGRAM
   The animator is a test bed I used to make sure the functions
   for the inbetweening work correctly.  For this reason a number of
   features have not been included.  If someone wishes to fill in the
   gaps feel free.  The underlying routines which calculate
   inbetweened objects are fairly complete (support for transparant
   colors was never added) but some eager programmer could overhaul
   them to reduce temporary memory consumption.  If someone does
   undertake the task, here's my wish list for the interface :-):
        color palette and screen resolution control
        nice editing functions and the ability to enter     
          independant objects
        precreated objects like circles, rectangles and fonts
          since freehand is frustrating

   To try the program out start it (either from the WB or CLI) and
   a list of commands will be displayed.  After skimming these 
   (they can be redisplayed by hitting "h") select the "OK" gadget.
   Now hit "r" which will bring up a requester to read in a file and
   select the file "Example.kfast".  Using the "n" and "p" key you
   can move through the frames and see just what the input file
   included.  Then hit "a" and it will generate images for the
   remaining frames (a slow process which may require 300K).
   Once that is done you should be able to scroll through the frames
   with the space bar.  No I'm NOT and artist I realize that but
   it shows how the routines respond given the amount of information
   (an image and/or a skeleton and outline) in the surrounding key
   frames.
     
THEORY OF KEY FRAME ANIMATION
   Inbetweening, or tweening, is the process by which the computer
   calculates the additional drawings between specified "key" frames
   by computing linear distances between corresponding points in each
   of the keys.  For a given velocity law between the key frames the
   intermediate locations can be calculated and the object can be
   reconstructed for those intermediate frames.

   For tweening, the simplest case is to assume the objects in the key
   frames are composed of strokes which are composed of line segments
   joined end-to-end.  Since it is unlikely that the object in the
   each key frames has the exact same number of strokes composed of
   the exact same number of line segments some preprocessing is
   required.  One method, is to simply subdivide strokes and/or line
   segments until each key has the same number.

   This is accomplished by the following algorithm:
        1. Preprocessing for a different number of strokes
             Let 01 and 02 represent the corresponding key objects
             Let N1 and N2 equal the # of strokes in O1 and O2
             respectively.
             if(N1>N2) then the following values are computed:
               RT = N1 div N2
               RS = N1 mod N2
             then RS strokes of O2 are broken up into RT+1 strokes and
             the remaining strokes are broken into RT strokes.

        2. Preprocessing for different number of point for
           corresponding strokes
             Let S1 and S2 represent the corresponding strokes
             Let NP1 and NP2 equal the # of points in S1 and S2
             respectively.
             if(NP1>NP2) then the following values are computed:
               RT = (NP1-1) div (NP2-1)
               RS = (NP1-1) mod (NP2-1)
             then RT points are added to the first RS line segments of
             S2 and RT-1 are added to the remaining line segments.

   To visualize this draw two frames. The first with two strokes: the
   first composed of 6 points (label them a b c d e & f) joined by
   line segments and the second stroke composed of three points(label
   these 1 2 & 3).  The second frame is a single stroke of 8 points
   (label these A B C D E F G H).
   Note if you want closed objects the first and last points must be
   the same and count as 2 points.

   For stroke preprocessing RT is determined to be 2 and RT is 0.
   Therefore zero strokes are broken into 3 strokes and the remaining
   strokes are broken into two strokes.  So stroke ABCDEFGH becomes
   two strokes ABCD and DEFGH.  (The break point is logically chosen
   at the halfway point D and both resulting segments contain point D)

   Looking at the second pair of strokes, 123 and DEFGH, the point
   preprocessing again gives RT=2 and RS=0.
   Therefore zero segments of object 1 are divided into 3 line
   segments and all remaining segments are divided in two.
   This gives the stroke 11'22'3 where 1' is choosen halfway between 1
   and 2 and similarly 2' is halfway between 2 and 3.

   Once this is done a velocity law must be chosen to determine where
   each point in the object is position for the inbetweens.  There are
   four general cases which can be applied in any combination as the
   velocity law for x and y relative motion:
     1) Velocity constant
     2) Velocity accelerating
     3) Velocity decelerating
     4) Velocity accelerating then decelerating

   These four cases allow the animation to be fine tuned so as not to
   appear too "jerky".  A rough example of these can be made by
   showing how the distance moved changes if an object was crossing
   the screen.  The numbers represent the frame number.

                 Start                                      End
      Constant:    1     2     3     4     5     6     7     8
      Accelerating:1 2  3    4     5      6       7          8
      Decelerating:1          2       3      4     5    6  7 8
      A & D:       1  2    3       4         5       6    7  8

   The tweening process as described has one serious limitation and
   that is that most motion is not linear over anything but very short
   durations meaning that a large number of key frames must be
   created.  This means that a complex objects has to be redrawn with
   subtle differences in a large number of key frames by the animator.

   One solution to this is to have a simple model, such as a stick
   figure, represent the object for all intermediate key frames.  Once
   they are correctly positioned for animation the detailed object can
   be drawn around the stick figure.  This is the basis for skeletal
   animation.

   Consider a skeleton as a backbone and an outline which highlights
   the extent of the area bound to each segment of the backbone.
   Using the outline the object can be transformed into relative
   coordinates.  Then as the backbone or outline is moved the object
   can be recreated to reflect that motion by simply inverse
   transforming the relative coordinates with the new outline.

   This technique does have the disadvantage of requiring more input
   than the linear interpolation tweening previously described but its
   implementation can be made such that the two can be used
   individually or in concert. This way the animator can choose the
   combination which yields the best results from the most minimum
   effort.
   
