Some notes on Skeleton LOD
for cheaper animation updating
10-07-02

--- INTRODUCTION --------------------------------------------

These are some old thoughts and things I've talked various
people about before.  As usual, I don't claim that these ideas
are original, I'm just going to write them down now, because
we started talking about them at work and I realized I'd
never seen them written before.

The idea of Skeleton LOD is to reduce the amount of work
required to animate characters in the distance.  The point
is that they're far away, so you can't tell if their
animations are slightly wrong.  You're doing VIPM on their
verts anyway, right, so what's the point of the big skeleton.

--- THE BASICS ----------------------------------------------

The most trivial way to do Skeleton LOD is like static LOD,
just swapping down to a simpler version at some point.  So,
at some distance, you swap skeletons to a smaller skeleton,
and swap skins to a skin that only uses the smaller skeleton,
and swap anims to animations that were made for the smaller
skeleton.  You could automate the creation of these anims
by IK tracking the smaller skeleton to the original anims,
but we won't get into that, because this whole technique is
too much pain to be worth doing.  In particular, we want to
be able to use the same animations and not bother with 
different animations for different skeleton LOD's.

--- SIMPLIFYING ONE SKELETON --------------------------------

So, we want to use the same animations on the lower LOD.  To do
that, we want the lower LOD skeleton to be a subset of the full
LOD skeleton, so that the animations for it are contained in
the animations for the full LOD skeleton.

I'm assuming that your animations are a series of transform
keys (transform = translation+rotation+scale) for each bone.  You
can choose to sample any of the bones in the animation that you
care about.

If your animations specify transforms in object space, then all
you have to do is pick the bones you want to be in your lower LOD
skeleton, and animate only those bones.  Tada, you have a lower LOD
skeleton and you can use the same animations.

If your animations specify transforms in relative space (eg. relative
to their parent), then your life is not so easy.  In this case, for
each bone you want in the lower LOD skeleton, its parent must also
be in the lower-LOD skeleton.  Obviously, you don't want to sample
animations for bones you're not even using, so the whole lower LOD
skeleton must be at the top of the skeleton tree structure.

Let's go back for a second and realise that skeletons are always
"trees" (or a DAG if you prefer the lingo), so there is a root and
a bunch of kids (you could have several roots if you're kooky, but
we won't address that here).  If you are using relative-transform
kids, then to evaluate an object-space transform of any particular
bone, you need to evaluate the animation of that bone and all its
parents.  If you pick any set of bones, then those bones and their
parents form a valid sub-skeleton of the original.

So, our lower-LOD skeleton just need to be a sub-skeleton of the
original, or a prefix of the skeleton tree.

The trick now is to arrange your skeleton so that this comes out
nicely.  You want the more important bones to be near the top of
the skeleton.  This might lead to a skeletal structure which is
a bit unnatural.  For example, if you want to have lots of spine
vertebrae in your full-LOD skeleton, they might be in the tree
between the "pelvis bone" and the "collar bone" ; in your low LOD
skeleton you don't want any spine vertebrae, so you want the
"pelvis bone" and "collar bone" to be adjacent in the skeleton.
To fix this, you can just re-arrange the tree structure of the
skeleton to your heart's content.  Note that this tree structure
may not be a good one for doing IK on, so you may want several
trees that work over the same set of bones.  That's just fine
(see Jeff Lander's articles, for example), the tree structure of
this skeleton is only important for sampling animations and setting
the parent-child relationship for relative-transform storage.

In practice, it's easiest just to have your artists make skeletons
that have a good skeleton as a prefix.

--- CONTINUOUS SKELETON LOD ---------------------------------

This prefix structure of LOD is just like VIPM, and guess what,
you can do continuous skeleton LOD just like VIPM.  It goes like
this :

Assign an importance to each bone.  This importance reflects how
much the animation would be damaged by removing it.  Your could
do this automatically in many ways, such as trying all possible
bone-removals, playing back the animations, and watching the
result with imaged-based sampling.  In practice, it's easiest to
assign them by hand.

Sort the bones such that higher importance bones come first, but
constrained such that a bone's parent always comes before it.
This produces a topological sort, such that any prefix of the
array is a "prefix" of the skeleton tree.  It also means that we
can make a good sub-skeleton just by selecting a prefix of the
tree.  Now we can remove bones one by one just be reducing how
many bones we animate.

One problem remains - the skin.  The original skin refers to all
the bones.  As we do LOD, we'd like to have a cheaper skin as
well, so at some point we have to do static LOD swapping of
the skin, even if we do VIPM.  We can do this swap invisibly,
swapping for a skin that uses the exact same bones as the previous
when we do the swap.  We might want 3 skins, say one with 60 bones,
one with 30, and one with 15.  So, what do we do with the extra
transforms needed when we have 59 bones?  We fill them in with
something "reasonable".  To do this, we store a non-animated
resting relative xform for each bone.  If your bones are made
with nice rest-pose orientations, this "resting" relative xform
could just be the identity.  We make the object-space transforms
for these non-animated bones just by copying from the parent.

--- PSEUDO CODE ---------------------------------------------

Here's the full loop for updating an animating skeleton :

importance_needed = smallest importance needed at
	current view distance, etc.
update animations on bones_array[0] (the root)
bone_ptr = bones_array + 1;
while( bone_ptr->importance >= importance_needed )
{
	update animations on bone_ptr
	rel_xform = bone_ptr->animation_xform;
	parent_xform = bone_ptr->parent_ptr->bone_xform;
	bone_ptr->bone_xform = rel_xform * parent_xform;
	bone_ptr++;
}
num_bones_updated = bone_ptr - bones_array;

NOTEZ : to force the loop to terminate, we add a dummy bone at 
the end with an importance of zero, and we make sur
importance_needed never goes to zero.  Note that because of
the topological sort, the parent is always updated already
when its child bone refers to it.

--- FINITO --------------------------------------------------