Problems with skeletal animation interpolation

Have you tried using a slerp function that you know works? From some library perhaps? Would just help narrow down the problem.

Can't believe I didn't think of that in the first place...unfortunately, using a math library gave me the same problems, so it looks like the problem is elsewhere. I'll keep plugging away at it I guess =/

My own SLERP function looks largely the same as yours, except the 'to' and 'from' quaternions are flipped around.


Quaternion c (b);
becomes
Quaternion c (a);

here ...
Quaternion r (Lerp (a, c, t));
you would instead lerp between
Quaternion r (Lerp (c, b, t));

and the actual slerp
return (a * std::sin ((1.0f - t) * halftheta) + c * std::sin (t * halftheta)) / std::sin (halftheta);
would become
return (c * std::sin ((1.0f - t) * halftheta) + b * std::sin (t * halftheta)) / std::sin (halftheta);

Though that doesn't explain why the library that you tried didn't fix things. The rest of your code does look to be correct ... as you said it works fine up until you start interpolating between frames.


Good luck!

Unfortunately that didn't make any difference, but thanks for trying.
I don't suppose anyone else has any more ideas? Or at least any ideas how I can go about debugging this problem? To recap my problem, I can build the skeleton for an animation perfectly fine if I don't interpolate between frames. Everything looks correct, everything is in the right place. But interpolating between animation frames gives me weird results. See the first post for an example video and relevant code.

The model format I'm using is the Ghoul2 model format, made by Ravensoft for a small number of their Quake 3 based games back in the 2001 - 2003 period, so there's no reference code I can look at. I've only managed to get as far as I have because the model structs were included in one of their game's SDKs.

Some things to check:

1.) Is there any position animation as well, or are the position values static. Just to narrow down the problem.

2.) It looks a bit like your lerp/t value that you use in the Slerp might be wrong, like it interpolates a doesn't stay between 0 and 1. Did you verify this? Although I see now that your function clamps this already.

3.) You tried replacing your slerp function with other code and got the same results right?

4.) DId you verify your Quaternion math, if it behaves correctly, like the dot product of it etc.


I don't really trust your Slerp function.
Can you try to replace it with this NLerp:


// t is your lerp value

Quaternion Quaternion::NLerp(const Quaternion& to, float t)
{
const float dot = x*to.x + y*to.y + z*to.z + w*to.w;
if (dot < 0.0f)
t = -t;

// calculate the interpolated values
const float omt = 1.0 - t;
const float newX = omt*x + t*to.x;
const float newY = omt*y + t*to.y;
const float newZ = omt*z + t*to.z;
const float newW = omt*w + t*to.w;

// calculate the inverse length
const float invLen = Math::InvSqrt( newX*newX + newY*newY + newZ*newZ + newW*newW ); // 1.0f / sqrt(..)

// return the normalized linear interpolation
return Quaternion( newX*invLen, newY*invLen, newZ*invLen, newW*invLen );
}


Cheers,
- John

1.) Is there any position animation as well, or are the position values static. Just to narrow down the problem.[/quote]

There is position animation as well.

2.) It looks a bit like your lerp/t value that you use in the Slerp might be wrong, like it interpolates a doesn't stay between 0 and 1. Did you verify this? Although I see now that your function clamps this already.[/quote]

Not sure what you mean here, but the t value is clamped between 0 and 1 in the slerp function. Anything below 0 returns the 'a' quaternion, anything above 1 returns the 'b' quaternion.

3.) You tried replacing your slerp function with other code and got the same results right?[/quote]

Yep, I've tried replacing the Slerp function, point rotation (using a quaternion) and quaternion multiplication with the equivalent functions from an existing math library (CML), and it still gives me the same problem.

4.) DId you verify your Quaternion math, if it behaves correctly, like the dot product of it etc.[/quote]

I've checked more times than I count Every time I come back to trying to fix this, I find myself checking the maths over and over, and there's nothing I can find wrong with it. And like I said above, existing math libraries give me the same problem.

I don't really trust your Slerp function.


Can you try to replace it with this NLerp:[/quote]
I don't really trust it either! But it gives me the right results apparently. I tried using your NLerp function, and that also gives me the same problem

Something I've noticed is that the animation glitches seem to get worse, deeper in the bone hierarchy. This may or may not be of any significance, but I thought I'd mention it just in case it is.

[delete]

Did you try increasing the epsilon a bit? The float epsilon is probably much too small...

How do you calculate your t or lerp value?
Are you sure that is correct as well.

And do you interpolate between the right keys? Did you verify that?

Also are your input quaternions normalized? I mean the key values stored.

If you don't animate the position, does it then still behave this weird?

Trying to narrow it down, we'll find it somehow

How do you calculate your t or lerp value?
Are you sure that is correct as well.[/quote]
I'm fairly sure my lerp value's calculated correctly. I divide the amount of time since the last frame change, by the time a single frame should last (the frame time). In the update function, the amount of time since the last frame change wraps around to 0 if it becomes greater than the frame time.

And do you interpolate between the right keys? Did you verify that?[/quote]
When the frame number changes, I've tried outputting the current frame number and the previous frame number to make sure they're correct and they are.

Also are your input quaternions normalized? I mean the key values stored.[/quote]
I've tried with normalizing and without, and both give me the same results.

If you don't animate the position, does it then still behave this weird?[/quote]
If I don't animate the position, then it looks even weirder! The animations looks completely wrong, e.g. head stretching forward, body stretching backwards, arms going everywhere.

Do you maybe have a simpler model to test with?

Like a cylinder with 2 bones in it or so. That might make it easier to debug and verify what is going on.

It looks like you are storing the data in the right way at least, relative to the parent. So interpolating should go fine.
I somehow suspect some small bug somewhere else in a piece of code we can't see in the post.

Worst case I can offer to look at your project and try to debug it on my computer when I have some time.

I don't have a simpler model, but I know someone who can make one for me. Something I've been wondering, about the vertex skinning: in the GLM format, there's a chunk of information about the skeleton itself, and also an array of base pose transformations for each bone, as well as the inverse transformation. Now, I never need to use this matrices, but surely they're there for some reason, otherwise why keep them in the file? Here's the struct itself:

struct mdxaSkel_t{
char name[MAX_QPATH]; // name of bone
unsigned int flags;
int parent; // index of bone that is parent to this one, -1 = NULL/root
mdxaBone_t BasePoseMat; // base pose
mdxaBone_t BasePoseMatInv; // inverse, to save run-time calc
int numChildren; // number of children bones
int children[1]; // [mdxaSkel_t->numChildren] (variable sized)
};


That struct (sorry about the formatting) describes a bone in the skeleton when it's in base pose (and only the base pose!). Also, here's my code for vertex skinning. The 'skeleton variable' is what's returned by my BuildSkeleton function in my first post.

void Ghoul2ModelInstance::Draw ( const Skeleton& basePose, const BonePalette &skeleton, const G2SkinPtr& skin, GLProgramPtr &program, unsigned int lod )
{
assert (lod >= 0 && lod < numLods);
Lod& lodData = lods[lod];
renderer->SetVertexLayout (lodData.vertexLayout);

// TODO: Replace buffer bind call
glBindBuffer (GL_ARRAY_BUFFER, lodData.vbo->GetId());
glBindBuffer (GL_ELEMENT_ARRAY_BUFFER, lodData.ibo->GetId());

std::vector<math::Matrix> bones (skeleton.size());
BonesToMatrices (skeleton, bones);
program->SetUniform ("u_BoneMatrices", &bones[0], skeleton.size());

// This just calls glDrawElements for the different submeshes of the model.
DrawSurface (program, *rootSurface, skin, lodData);
}

And then finally here's the vertex shader for rendering:

#version 120

uniform mat4 u_BoneMatrices[80];
uniform mat4 u_ModelViewProjectionMatrix;
uniform mat4 u_ModelMatrix;

attribute vec3 in_Position;
attribute vec3 in_Normal;
attribute vec2 in_TexCoord0;
attribute vec4 in_BoneIndices;
attribute vec4 in_WeightInfluences;

varying vec3 ex_Normal;
varying vec2 ex_DiffuseTexCoord;
varying vec4 ex_Position;
//varying vec3 ex_LightColor;

void main()
{
vec4 position = vec4 (0.0);
vec3 normal = vec3 (0.0);
vec4 p = vec4 (in_Position, 1.0);
vec4 n = vec4 (in_Normal, 0.0);

float influence = in_WeightInfluences[0];
mat4 boneMatrix = u_BoneMatrices[int (in_BoneIndices[0])];
position += boneMatrix * p * influence;
normal += (boneMatrix * n).xyz * influence;

influence = in_WeightInfluences[1];
boneMatrix = u_BoneMatrices[int (in_BoneIndices[1])];
position += boneMatrix * p * influence;
normal += (boneMatrix * n).xyz * influence;

influence = in_WeightInfluences[2];
boneMatrix = u_BoneMatrices[int (in_BoneIndices[2])];
position += boneMatrix * p * influence;
normal += (boneMatrix * n).xyz * influence;

influence = in_WeightInfluences[3];
boneMatrix = u_BoneMatrices[int (in_BoneIndices[3])];
position += boneMatrix * p * influence;
normal += (boneMatrix * n).xyz * influence;

gl_Position = u_ModelViewProjectionMatrix * position;

normal = normalize ((u_ModelMatrix * vec4 (normal, 0.0)).xyz);
position = u_ModelMatrix * position;

ex_Position = position;
ex_Normal = normal;
ex_DiffuseTexCoord = in_TexCoord0;
}


Hopefully that'll shed some light on what I might be doing wrong. Thank you Buckshag on all the help you've given so far btw!

Now, I never need to use this matrices, but surely they're there for some reason, otherwise why keep them in the file?[/quote]

You do need to use them actually This might be the problem, that you are performing the skinning incorrectly.
You shouldn't send over the world space matrices to your shader, but the world space matrices multiplied by their inverse bind pose transform matrix.
This makes the vertices move relative to their bind pose.

It is a bit silly that they are stored inside the file, especially the inverse, as that really is nothing to calculate just once at load time, but ok

You might also turn your shader code into a loop for all weights/influences instead of unrolling it.

You can still do quite a lot to improve your performance, but you can always do that after it works of course.

Happy New Year everyone So I've decided to come back to this (again) since I hate being so close to finishing and not being able to actually finish it! I'm absolutely convinced that the problem lies in the way I'm interpolating the keyframes, as the animations look completely right if I turn off the interpolation.

Since my last post in this topic, I've replaced all my own maths functions with ones from the CML math library, and I still get the same results. I've also confirmed that the keyframe position/rotations are stored as offsets from the bind pose, i.e. the keyframe describes how to transform the bones from the base pose, so the inverse base pose matrix isn't needed at all in my case. I have a friend who wrote a Blender importer for the animation format I'm trying to figure out, and it looks fine in Blender using this assumption.

Here's the code for interpolating the frames:
[source lang=cpp]
BonePalette Ghoul2AnimationSet::BuildSkeleton ( int currentFrame, int nextFrame, float lerp ) const
{
const BonePalette& current = frames[currentFrame];
const BonePalette& next = frames[nextFrame];

unsigned int numBones = joints.size();

BonePalette p (numBones), q (numBones);

for ( unsigned int i = 0; i < numBones; i++ )
{
p.position = cml::lerp (current.position, next.position, lerp);
p.orientation = cml::slerp (current.orientation, next.orientation, lerp);
p.orientation.normalize();
}

BuildFrame (q, p);

return q;
}[/source]

My main thoughts are that there's a different way of interpolating the keyframes perhaps? I don't know really, but hopefully this time around I'll be able to figure out what's wrong!

I'm not sure if that actually would work correctly, if you interpolate in the space you mentioned.
That might be the fundemental problem. I think you need to interpolate in local space, relative to the parent for it to work correctly.
I'm not 100% sure, but somehow my guts tell me this might be a problem.

Is there an easy way for you to test that? So not storing animation data relative to the bind pose, but relative to the parent.
Or is it relative to the local bind pose transforms?

Do you have any specific reasons for storing it relative to the bind pose instead of relative to the parent anyway?

I've also confirmed that the keyframe position/rotations are stored as offsets from the bind pose, i.e. the keyframe describes how to transform the bones from the base pose, so the inverse base pose matrix isn't needed at all in my case.

I'm assuming that when you slerp the quats you have *first* evaluated them as local space quats? (rather than trying to lerp the offsets from the bind pose?) The latter would result in an insane location for the -360 to +360 degree flip (the one which you correct for with the dot product + negation, so that rotation occurs along the shortest path between the two orientations). That would certainly produce results of the sort you are seeing?

Is there an easy way for you to test that? So not storing animation data relative to the bind pose, but relative to the parent.
Or is it relative to the local bind pose transforms?

Do you have any specific reasons for storing it relative to the bind pose instead of relative to the parent anyway?[/quote]
The animation and model format I'm using are ones used in the Jedi Knight series games, so it wasn't my choice to store them as they are

I might have to go back on what I said about the bones being stored as offsets from the bind pose though. I'm not exactly sure what space they're stored in. Here's what I do to animate the mesh, maybe it'll help determine how they're stored:

1. At load time, read the bone position/rotation from the animation file as a vec3 and a quaternion, and store them as-is in memory.

2a. Each frame: for each bone in the current and next keyframes, interpolate the vec3 and quaternion (as in my previous post). Then call BuildFrame, which accumulates the transforms of each of the bones with its parents.
[source lang=cpp]
void Ghoul2AnimationSet::BuildFrame ( BonePalette &newBones, const BonePalette &bones ) const
{
newBones[rootBone] = bones[rootBone];
for ( std::vector::const_iterator it = iterationOrder.begin() + 1; // skip the root bone
it != iterationOrder.end(); ++it )
{
const Bone& parent = newBones[joints[*it].parentIndex];
Bone& newChild = newBones[*it];
const Bone& currentChild = bones[*it];

newChild.orientation = parent.orientation * currentChild.orientation;
newChild.orientation.normalize();
newChild.position = parent.position + transform_vector_by_quaternion (parent.orientation, currentChild.position);
}
}[/source]
iterationOrder is a vector of ints which lets me loop through the bones in an order such that all parent bones are dealt with first and lets me avoid recursion.

2b. Convert the accumulated transforms into matrices, and then send them to the GPU. Skinning is then done in the vertex shader (GLSL):
[source lang=cpp]
vec4 position = vec4 (0.0);
vec3 normal = vec3 (0.0);
vec4 p = vec4 (in_Position, 1.0);
vec4 n = vec4 (in_Normal, 0.0);

float influence;
mat4 boneMatrix;
for ( int i = 0; i < 4; i++ )
{
influence = in_WeightInfluences;
boneMatrix = u_BoneMatrices[int (in_BoneIndices)];
position += boneMatrix * p * influence;
normal += (boneMatrix * n).xyz * influence;
}

gl_Position = u_ModelViewProjectionMatrix * position;[/source]

The thing I find odd about this (even though it works as long as I don't interpolate) is the inverse bind pose matrix is never needed. And yet everywhere I read, people say you need this.

The thing I find odd about this (even though it works as long as I don't interpolate) is the inverse bind pose matrix is never needed. And yet everywhere I read, people say you need this.

For that to be true....... The inverse bind pose will be the identity (in this particular case!). This can only happen if:

1. The mesh data is parented directly to the character root, and is not offset in any way.
2. The joints must have been specified as translation only in the bind pose (i.e. all rotations were all zero when the skin was applied).

Since you normally only animate the rotation values, this can make it look like you don't need the bind pose. To an extent that may be true, but it depends on whether your data importer is baking that information out, or whether you happen to have a character authored that way. If it's the latter situation, then you will still have to take account of the bind pose (unless your modeller always rigs characters the exact same way, then it's up to you if you want to ignore it or not). The downside of the latter, is that a model lacking initial joint orients will be a complete bitch for animators to animate.....

As for the code above, you conversion from local to world looks ok. The skinning in the original video works fine, so looking for a problem there is a red herring imho. Assuming your PosQuat to matrix code works correctly, then I'd start looking very closely at how you are choosing the time increments between frames. It *almost* looks like the time values are running in reverse between each frame (which is only noticeable on bones that have big motion deltas between frames. The legs don't move as much, so it's not as noticeable).

May I suggest creating a 3 joint rig with a skinned cylinder rather than using this character (with only the middle joint animated). That will be far easier for you to debug and figure out what's wrong....

I'm doing something wrong here and basically ignoring everything beyound the 5th comment, so some one probably already fixed this for you:

but make sure that your bone keyframe data is in the frame (mathematically) of the parent bone. Don't store it as a local to world, store it only as local, then do your interpolation, then transform to get your local to world. This is my suspicion as to the cause of your problems.