Sign in to follow this  
skow

Speeding up bone animation.

Recommended Posts

Currently I got some skeletal animation running purely on the CPU and I’m not very happy with the results. I’m using quaternions for rotation and doing a spherical linear interpolation to get the quaterion between the 2 key frame quaternions. This sadly means up to 3 sins and 1 arc cos operation is being done per vertex per bone linked to that vertex. The result is a significant slow down (went from 35 fps to 20 with a single 2k poly model). The obvious thing to me would be to toss it in a vertex shader and draw the model via vertex arrays. The main problem arises is that each vertex can be affected by many different bone rotations . So I would need some looping in my shader that would grab the translation + rotation for each bone. So I would need a whole set of translation + rotation arrays for each bone available to each vertex in the shader. As far as I know there is no way to pass in a variable sized array in to the shader. I’m not sure if that would be too much data to pass, since it would be uniform data I shouldn’t be too bad. Has any one here stumbled across this issue and found a solution? Should i be looking for a different way to speed this up?

Share this post


Link to post
Share on other sites
You'll need to split the mesh into several subsets according to the bone influence.

I wrote only one shader which handles always 4 bones per subset. Of course, you can do different and use a matrix palette for example to get much more bones per draw call. The trick is that for the bones you don't need you can se zero influence and the same shader works with all different combinations. No need for looping etc. Of course, it isn't forbidden to use looping :)

Well first of all, you shouldn't use quaternions for vertex transformations. You can get a significant speed up by first turning your quaternions into matrices. This is the way to go with the shaders too. With matrices the transformations turn out to be pretty simple. Quaternions are ok for slerping between keyframes but after that matrices become more handy.

So, practically the shader needs 1 matrix per bone (which is the bone's worldspace matrix concanated with the inverse of the initial bone matrix) and of course view / projection matrices. This technique assumes that the mesh to be skinned is defined in the object space, which is the reason that you need the inverse bone matrices.

Cheers

Share this post


Link to post
Share on other sites
Quote:
Original post by skow
This sadly means up to 3 sins and 1 arc cos operation is being done per vertex per bone linked to that vertex.



That seems a little suspect. If you traverse the bone hiearchy once and do all your slerping and what not there, and then store your results, it seems like it will be more efficient (i.e. 3 sins and 1 arc cos per bone only). That's how I do it in my code. Also, note that if you move the transforming into a shader, if you do any kind of multipass shading, you will end up retransforming those vertices each time. So, if you have a depth fill pass, followed by a material pass, a lighting pass, and possibly a couple of renders for shadow maps, I start to wonder if the cost of redoing those transforms becomes prohibitive. I haven't done the research to back that up though, can anyone else comment on that.

Share this post


Link to post
Share on other sites
You can avoid the interpolation all together if you want to sacrafice memory for speed. Simply export the animation at 33 frames/second. Turning on and off interpolation, when a character is exported at that interval, will show no visible difference.

If memory is a problem but you still want to avoid interpolation you can then look into animation compression.

Share this post


Link to post
Share on other sites
Why are you doing a slerp for every vertex? That seems very wrong unless you are doing something very unusual. Normally with skeletal animation, you slerp the bones, and then use the bones to transform the vertexes. The slerp is done on the CPU and the vertex transforms are done in the the vertex shader.

Share this post


Link to post
Share on other sites
Here is a very rough (sorry I don't have time to do a nice write-up) description of how it is done:

You have a "bind pose".
You have n animated bones, B0..n-1, in a hierarchy. Bones are 4x4 (or 4x3) matrices. The initial values of the bones, P0..n-1, come from the bind pose.
You have m animated vertices, v0..m-1. The initial locations of the vertices, u0..m-1, are the locations of the vertices in the bind pose in model space. Each vertex contains a list (usually a fixed size) of r bone index/weight pairs.
In each frame,
Compute the animated values of the bones (B0..n-1).
For each vertex i = 0..m-1
vi = 0
for each index/weight pair (kj,wj)>), j = 0..r-1
vi += wjBkjPkj-1ui
As an optimization, you should compute Mi=0..n-1 = BiPi-1 once each frame instead of every for every vertex. Then the algorithm looks like this:
In each frame,
Compute the animated values of the bones (B0..n-1)
Compute the concatenated bone values, Mi=0..n-1 = BiPi-1
For each vertex i = 0..m-1
vi = 0
for each index/weight pair (kj,wj), j = 0..r-1
vi += wjMkjui


Normally, the animated bone values are computed on the CPU and passed to the GPU as constants. The remainder is done in the vertex shader.

A while back, I wrote a very thorough description on how to do this in one of these forums, but I can't find it. Take a look at this powerpoint slide show for a good explanation: Animation in Video Games

edit: fixed the link

[Edited by - JohnBolton on May 22, 2006 10:09:09 PM]

Share this post


Link to post
Share on other sites

Quote:
Original post by JohnBolton
Why are you doing a slerp for every vertex? That seems very wrong unless you are doing something very unusual. Normally with skeletal animation, you slerp the bones, and then use the bones to transform the vertexes. The slerp is done on the CPU and the vertex transforms are done in the the vertex shader.


*sigh* well that is the down side to programming with almost no sleep. Yes I only need to do it once per bone, for some reason I had been re calculating it with each vertex. That will certainly cut down on the work being done. It’s embracing but thanks for pointing out that flaw.


Quote:
Original post by INVERSED
That seems a little suspect. If you traverse the bone hiearchy once and do all your slerping and what not there, and then store your results, it seems like it will be more efficient (i.e. 3 sins and 1 arc cos per bone only). That's how I do it in my code. Also, note that if you move the transforming into a shader, if you do any kind of multipass shading, you will end up retransforming those vertices each time.


Hmm that is true. I will lose the current frame vertex cache (what i store myself in an array). But I will be able to cache the slerp for the bone if I do that on the CPU and pass that into the shader.

Quote:
Original post by JohnBolton
Here is a very rough (sorry I don't have time to do a nice write-up) description of how it is done:

Normally, the animated bone values are computed on the CPU and passed to the GPU as constants. The remainder is done in the vertex shader.


This seems painfully obvious now, thanks for taking the time to write that out. That PowerPoint link doesn’t seem to be working though.

You all have been most helpful!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this