[Algorithms] Re: Keyframe reduction

[Casey M. <gd...@fu...>]

> On this first pass we're stuck with linear keyframing, because we just
> don't have the cycles in game to go to splines. I know this would help a
> lot, but it isn't an option.

In Granny I do successive least-squares approximations do the data.  I
take the array of samples for a given channel (ie., position) which is 2x
oversampled or better from the art tool.  I then start by doing a
least-square solve for a spline of arbitrary degree with knots at either
end.  I compute the error over the spline from the original samples, and
add knots in the areas of highest error.  Repeat and salt to taste.

Since it's fairly easy to write a single solver that solves for any degree
of spline, I use the same solver for linear keyframes as I do for
quadratic keyframes, cubic keyframes, or even "0th order keframes", which
is to say if you don't want to interpolate _at all_, the solver can still
place the "stop-motion" key frames in the best locations.  But hopefully
no one is still doing that kind of animation.

If I were doing this over again (which I probably will at some point), I
would probably use some kind of weird waveletty scheme now.  I decided not
to do that originally, because I had about a month to do the entire
spline/solver/reduction thing the first time, and it had to be highly
optimized.  So I didn't want to have to learn wavelets and spline solvers
at the same time.  Next time I'll spend some time on wavelets and probably
use some sort of hierachical reduction scheme instead, primarily so you
can change how densely your keyframes are placed at run-time, and so you
can get hard edges easier (motions which are intended to have sharp
discontinuities aren't handled well at all by my current scheme).

- Casey