Date: Fri, 18 Jan 2002 12:26:46 -0800 (Pacific Standard Time)
From: Casey Muratori <cmu@funkytroll.com>
Subject: Periodic decomposition for animated root nodes [EXTREMELY LONG]

OK, this is something I've been meaning to post about for a while, but
I've been scared to, because I seem woefully unable to explain it to
people.  This is primarily because I don't really understand it, and thus,
I can't explain the problem I'm having, which is a catch 22, because if I
could explain it, I'd probably understand the problem well enough to solve
it, but then I wouldn't need to explain it, etc.  The pain.

Anyway, here's the deal.  Suppose I have a walk cycle in Maya where my
dude walks one cycle forwards, and his root node actually translates
forwards.  Obviously, when you play this back looping, you can't just play
it back like you would some "in place" animation, because the guy will
walk forwards, spring back to the origin, walk forwards, spring back, etc.
However, at the same time, you can't just suck out all the movement and
just translate the guy forwards with a constant linear velocity either,
because the feet will slip.  So, games typically like record the amount of
linear movement per frame, and advance the guy that much, and know not to
apply the reverse translation at the loop point.  Or something like that.
Right?

Well, the thing I "realized" when I was doing this for Granny a few months
ago was that, hey, it's really convenient for the app to just translate
the guy around linearly, because it makes the code a lot simpler on their
end - no matter where you are in the animation, you know that the timestep
times the constant linear velocity is the movement, period.  If you have
to worry about a different amount of movement every frame, or handling the
loop point specially, or any other concern, you get into a bunch of
lookups or if statements or other stuff which is generally nowhere near as
clean as just f(t) = t*v, which is obviously what you would prefer.

So, to allow people to do this with Granny, I just said hey, why not
pretend the guy _does_ translate at a constant velocity, and make the
spline animation for his root bone be the _difference_ between movement at
that constant velocity and the _actual_ animation.  This way, the relative
animation system takes care of all the tweaky differences from frame to
frame of the original motion, but the app that's just thinking about some
point in space that's "where the guy is" just thinks in terms of f(t) =
t*v, and it always works.

Anyway, this works great.  It's just super convenient.  The app gets total
convenience, but the feet always stay pegged and the animations are easy
to create for the artists.  Everyone's happy.

Now, here's the starting point for the problem.  It would be nice to do
this for rotation, right?  Because hey, that way people can animate their
guys doing like a 45 degree turn or something, and then if they play that
back looping, the guy turns 45, and then another 45, and so on.  We'd like
to keep all the same benefits of the linear version - namely, not caring
when a loop point occurs, having the app-side deal only with f(t) = t*v
(although v is now angular velocity, not linear, obviously), and all that.

This is easy to do for something that was just rotating in place,
obviously, because you just do the same thing you do with the linear
version.  But, lets suppose someone is walking forwards and turning at the
same time.  Now there's really two things we know at export time: the
degree of the turn (theta) and the gross displacement from the first
frame to the last frame (some vector).  And we ask ourselves, how does
this all relate?

Well, here's the interesting thing.  It may not be immediately obvious,
but if you take a look on paper, you'll see that any movement that
involves a rotating frame is circular-periodic in the plane of the
rotation.  To make clear what I'm talking about, consider the
walk-while-turn.  At t=0, I'm at the origin, facing forwards.  At t=1
(let's assume 1 is the end of the animation), I'm somewhere away from the
origin, rotated theta degrees.  Now, take that animation, and place the
t=0 frame aligned rotationally and translationally with the t=1 frame, and
repeat the animation.  Keep stringing the animations end to end, and you
will see that you _always_ go in a circle.  Your total path from 0 to 1 is
not always on the circle, because there can be arbitrary variations in the
animation, but you cannot _not_ stay in a circle.  There is no way for you
to "spiral", ie., close in to a point or grow to infinity.  This may be
counterintuitive, but take the time to verify it for yourself if you don't
believe me.

To complete the example, suppose the person is also ascending a spiral
staircase during this motion.  Obviously, this means there is a net
upwards translation from t=0 to t=1.  Now, this motion continues to
accumulate to infinty - the longer I walk, the further up I go.  It is not
periodic.  This may seem contrary to what I just said, but it's not,
because this motion is _not_ in the plane of rotation, it is
_perpendicular_ to the plane of rotation.

Thus, I posit, for the enjoyment of kids everywhere, that the proper
decomposition for root node motion, such that it can always be phrased in
f(t) = t*v form, is a plane of rotation (a vector), and angular rate
(theta), a radius of curvature (r), and a perpendicular displacement
scalar (p).  This is all you need.  You can solve for it in a variety of
ways, and how you structure your exact construction determines certain
other properties of what you get and so forth.  But it is "the right
thing" for making the app code as simple as possible, because they
literally don't see any of the complexity in looping + foot pegging
anymore, period.

However, at the beginning of the mail I said I was having a problem, and
now it's time that we got to the actual problem.  I hope I've done a
better job explaining the millieu of the problem this time (I tried
previously to explain this to [CENSORED], and my explaination was so bad that
at the end of it I wasn't even sure _I_ understood what I was talking
about), because the problem itself is kind of out of my league in terms of
numerical analysis, and I'm hoping somebody out there might give me a
nudge in the right direction.

Now we have to ask ourselves, what do we do with our old motions that had
no gross rotational displacement?  Well, the easy answer is we don't do
anything with them - we just store the two types separately.  So we keep
both ways of doing things.

The problem with this simplistic approach (besides its obvious inelegance)
comes when you want to do motion blending between multiple animations that
are going to be decomposed in this format.  Obviously, you can just
produce the motions and then linearly blend between them, or something
similar.  This is basically the crap-ass way that looks crappy just like
every other way.  But, because we have a decomposition, there should be a
way to do something _better_, right?

Well, it's hard to define "better", when it comes to motion blending,
because we suck so bad at it everywhere else anyway (like what the hell
is blending joint orientations supposed to mean?).  But here's one
definition of "better": suppose I have a walk + 90 degree turn to the
left, and a walk + 90 degree turn to the right.  So, I've got two curves,
one to the right and one to the left.  If I blended these two things
together at 50%/50%, then hey, intuitively, I should get a straight line.
Blending the _results_ linearly at 50%/50% actually does give a straight
line, but wait, the distance is wrong - we should move the average
distance between the two arclengths, but instead we move the average of
only one axis of the arclength, which is obviously wrong.

But then, there's _no_ way we can really blend our decomposed
representation either, because if you think about it, the resulting
animation (a straight line with no rotation) isn't even _in_ the space of
our decomposition - 'cause I just said we were going to treat rotation
movements differently than linear ones!  So we're just fucked before we
even start.

And so herein lies the problem that's been bugging me.  I refuse to
believe there isn't some universal, beautiful set of parameters that works
for both the linear and the angular case, and that blends together in a
superior way to blending the results.  It just _has_ to be.  I'm totally
convinced.

The problem, of course, is that I can't find it.  I've tried thinking
about the problem a bunch of ways, and each time I come close I find
something that will trip me up.  It's very frustrating.

Advice appreciated.

Cheers,
- Casey



Date: Wed, 23 Jan 2002 23:25:45 -0800 (Pacific Standard Time)
From: Casey Muratori <cmu@funkytroll.com>
Subject: Periodic decomposition report

I have finished integrating my periodic decomposition code into Granny
proper, and although I still would like to try out [CENSORED]'s ideas about
differential formulations, I have verified that the current solution works
exactly as expected so I figure it's worth reporting.

Here is the final parameter set I decided on:

    struct periodic_loop
    {
        real32 Radius;
        real32 dAngle;
        real32 dZ;

        real32 BasisX[3];
        real32 BasisY[3];
        real32 Axis[3];
    };

Radius is the radius of the circle.

dAngle is the angle between the starting and ending orientation of the
animation, divided by the duration of the animation.  So this is
dAngle/dt.

dZ is the distance along the axis of rotation that the animation
translated (ie., the _non_-periodic movement, which must needs be
perpendicular to the plane of rotation, and thus is always along the axis
of rotation).  Like the dAngle parameter, this is divided by the duration,
do it is dZ/dt.

The three vectors are the full bases.  Axis is the rotation axis, and
BasisX and BasisY are what the cosine and sine terms are applied against,
respectively.

This is overspecified, but this was the most efficient set of parameters
in terms of run-time evaluation that I could come up with.  I've gotten
the run-time evaluation down to this:

    // This computes the position update vector
    VectorScale3(Result, Loop.dZ * Seconds, Loop.Axis);
    ScaleVectorAdd3(Result,
                    Loop.Radius*(Cos(Loop.dAngle * Seconds) - 1.0f),
                    Loop.BasisX);
    ScaleVectorAdd3(Result,
                    Loop.Radius*Sin(Loop.dAngle * Seconds),
                    Loop.BasisY);

    // This computes the orientation update vector, but you're free
    // to compute anything you want here in terms of rotation reps
    // since it's coming out in angle/axis form
    VectorScale3(Result, Loop.dAngle * Seconds, Loop.Axis);

It is for all intents and purposes free, because the only costly things
are the sine and cosine, and this is done once per character per frame, so
you are in good shape.

And now for the obligatory screenshots, in mathvis as usual.  The bright
white arrow goes from the starting point of the animation to the ending
point.  There are frames of reference drawn at each so that you can see
the orientation change between them.  Following the white line, there is a
set of diminishing teal lines.  These show the effect of rigidly
positioning the motion end-to-end on itself ad infinitum.  The idea behind
this whole thing is to find something that always passes through the
endpoints of these lines.  The yellow curve is the periodic decomposition,
which does just that.

Here is a simple planar walk loop:

    http://www.funkytroll.com/periodic/planar_loop.jpg

And, that same walk loop, but "climbing up the stairs":

    http://www.funkytroll.com/periodic/z_spiral.jpg

Finally, a random demonstration that even crazy loops will always
decompose into a circle and a line perpendicular to that circle:

    http://www.funkytroll.com/periodic/arbitrary_spiral.jpg

If you're looping, you're either a line or a spiral.  Such is your life!

As a test inside Granny, I made a character walk up 2 steps of a spiral
staircase.  I then played back the animation in Granny, and let the
character go.  It walked up all the stairs, and kept the feet planted the
whole way.  Yay+!

- Casey