• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
MilchoPenchev

Model animation - too many calculations

12 posts in this topic

Well, I've been working on animating a model based on a skeleton. I have a half-assed algorithm that auto-attaches vertecies to bones. Each vertex is attached to anywhere from 1 to 3 bones. Each bone attachment also has an associated weight.

The problem is then with animating the model. I'm using a low-polygon model - something like 760 faces, with less than 2000 vertecies.

I then have to calculate the new position of each vertex based on it's bone attachment. For each bone, this consists of 3 multiplications, type double, to rotate to the correct position, 3 additions, again for doubles, to translate it to the correct position, and then a multiplication of that whole result by the weight assigned to that bone. At the end, I simply add up all the results for each bone, to get the new position.

The above method works, assuming the attachments are correct. The problem is that it seems to take TOO long to compute that for all vertecies. I split the calculation up in 4 parts, where each update event it does 1/4th of the vertecies, and then updates only after all of them are calculated. That allowed me a bit over 60fps, but considering I'm only drawing one low poly model, that framerate is unacceptable. (For comparison, without calculating the vertex positions, I get framerate of 900+). I'm not sure where to optimize the calculations. They're all done on the CPU, which is a pretty big bottleneck, but I can't figure out how, if at all possible, to use the the GPU for that.

Anyone have any experience programming model animation? Perhaps animating a model from a skeleton from an existing animation format? Any help at all would be greatly appreciated.

0

Share this post


Link to post
Share on other sites
Only update vertex positions associated with bones that have moved?

Bear in mind that a Bone is effectively a transformation matrix, and your Graphics API (OpenGL/DirectX) will be doing these anyway when you set the position of the Vertex (glVertex...(), etc). Offloading the calculations to a Vertex Shader would be a good boost.
0

Share this post


Link to post
Share on other sites
As AndyEsser mentions, the GPU will do those calcs a [i]lot[/i] faster in a shader. In addition, a [i]change[/i] in framerate is not a good measure of performance. The actual [i]time[/i] to do the calc is what you're concerned about.

Also, it sounds like your weighting algorithm is suspect. As AndyEsser mentions, bones are really reference frames, commonly implemented as matrices, not separate rotations and translations.

In any case, a common approach (which can be implemented on the CPU or GPU):
[code]
// Given a vertex vin, 3 weights, 3 bone indices for that vertex, and an array of bone matrices..
vector3 vout = vector3(0,0,0);
for( int i=0; i<3; i++) vout += weight[i]*vectorMatrixMult( vin, boneMat[ boneIndex[i] ] );
[/code]
0

Share this post


Link to post
Share on other sites
Well, that's unfortunate, because I have no experience with shaders.

I thought I was minimizing calculations by using my method instead of a matrix. What I have is a set of Axes that gets rotated, and that determines the bone's orientation. When loading the model I store the original relative position of each vertex to every attached bone's axes. Then to get the vertex's transformed location I essentially have a vector: ( origRelVer_x * x_axis + origRelVer_y * y_axis + origRelVer_z * z_axis), where xyz_axis are orthogonal vectors (i.e. the axes's axis) I thought this would be less calculations than a matrix multiplication, but then, it's all cpu. (Edit: now that I saw my code again, I realize that's actually a multiplication of a scalar times a vector = 3 mults, so 9 total multiplications + 2 additions, and that's before the other 3 additions for the correct position. So, yes, quite a bit more than I originally mentioned, and not actually an improvement over matrix multiplication)

You're right that FPS isn't the best measure, especially since I average it over a second. The function clearly is slow though, so I need to improve it. Though from what it sounds like I might have to rework the way my bone rotation is stored.

I'm starting to wonder whether it's worth reinventing the wheel for the experience. I know this problem has been solved before, though I haven't found too detailed descriptions about it.
0

Share this post


Link to post
Share on other sites
Depending on what API you're using, there are downloadable examples available. On my old machine ( ca. 2005 ), I have no problem (DirectX 9.0c) with CPU skinning/animation for a ~300 vertex model and 22 bones at ~90 FPS (I know, I know.. FPS isn't a good measure :) )

Also, if you have 700 faces and 2000 vertices, sounds like you're not using indexed vertices. If you use an indexed mesh, that might cut down the [s]calcs[/s] [s]quite[/s] time a bit, too.

Also, it obviously depends on the number of material changes that're made, also. Combining multiple textures into one will reduce the time to change texture samplers.

EDIT: With regard to experience, depending on how much animation work you'll be doing in the future, understanding what it takes to do skinned animation might serve you well. However, downloading some code and examining it for a good understanding may be better than working out all the details yourself.

EDIT2:
[quote]Well, that's unfortunate, because I have no experience with shaders.[/quote]

No time like the present. If you continue with game development, shaders are where you need to be anyway.
1

Share this post


Link to post
Share on other sites
Yes, well, this was just an attempt at animation because I don't want to use a pre-made engine, and I thought I'd try to build just a fairly simple animated character. It really wasn't the best use of my time. And the animation was going so well until this point.

Also for the vertex and face count and vertex count...hmm I just realized. See, I wrote my own .obj loader, and .obj format specifies a list of vertex positions, a separate list of normals, and a third list of texture coordinates. Then each face is a set of indecies to each list. Because I'm storing the texture and normal data in my vertex struct, I had to read in all the lists, and then when reading in a face, create its vertecies on the spot. I have a check to see if that perticular vertex (combination of position, normal and texture) already exists, and if it does, link to that instead of creating a new one. But, as I just realized, I turned that off, because it lengthens loading time by about a second. I'm going to turn that check on, which does indeed greatly decrease the number of vertecies (as most faces share). I don't think it will have a huge impact, but it's worth a try. Thanks for reminding me!

0

Share this post


Link to post
Share on other sites
The following test runs in approx. 300 micro-seconds (debug) / 150 micro-seconds (release) on my 2.66 GHz i7 laptop, compiled by gcc 4.2; if I made no mistake, it uses 20 bones, 2000 vertices, and 3 bones per vertex:

[code]
float matrices[20*4*3];
float vertices[2000*3];
float weights[6000];
float results[2000*3];

int matrixIndex = -1;
float * vertex = vertices;
float * result = results;
float * weight = weights;
for(uint vertexIndex = 0; vertexIndex<2000; ++vertexIndex) {
result[0] = result[1] = result[2] = 0.0f;
for(uint counter = 0; counter<3; ++counter) {
matrixIndex = (matrixIndex+1)%20;
float * matrix = matrices+matrixIndex*4*3;
result[0] += *weight * (*matrix++ * vertex[0] + *matrix++ * vertex[1] + *matrix++ * vertex[2] + *matrix++);
result[1] += *weight * (*matrix++ * vertex[0] + *matrix++ * vertex[1] + *matrix++ * vertex[2] + *matrix++);
result[2] += *weight * (*matrix++ * vertex[0] + *matrix++ * vertex[1] + *matrix++ * vertex[2] + *matrix++);
++weight;
}
vertex += 3;
result += 3;
}
[/code]
Using doubles instead means it to last approx. 330 micro-seconds (debug) / 190 micro-seconds (release).
1

Share this post


Link to post
Share on other sites
I feel kind of stupid now. I was running in debug mode. I ran my algorithm in release mode, and even without splitting the calculations in 4 parts, I got a good speed on it. Yes, I realized that from the last post, thanks Haegarr.

Here's what my vertex update code looks like:

[code]mesh_vertex *currVer;
for (unsigned int i = start; i < end; i++)
{ // for each vertex of the model

Vec3f newPos(0.0, 0.0, 0.0), tPos;
currVer = vertexList.at(i);
for (int k = 0; k < vertexAttachedBones.at(i)->getNumBones(); k++)
{ // for each of it's attached bones
tPos = getAbsolutePosition(
vertexOriginalPosition.at(i).at(k),
vertexAttachedBones.at(i)->getBoneAt(k)
);
newPos = newPos +
tPos *
vertexAttachedBones.at(i)->getNormalizedWeightAt(k);
}
// update position
currVer->x = newPos.x;
currVer->y = newPos.y;
currVer->z = newPos.z;
}
[/code]

Specifically, it runs in 1 or less than 1 millisecond (I used clock() to get the time). It could probably still use some improvement, but it's nowhere near as bad as I thought it was. Also, I know it's a bad measure, but I get ~650fps now. Much more acceptable.

Thanks for the help everyone.

edit: I have no clue why there's such a huge gap in performance between debug and release. Is it because I update everything with pointers? Not that it makes a big difference, since release is the mode to use for .. well, releasing.
0

Share this post


Link to post
Share on other sites
Here's a screenshot of the animation in progress:
[attachment=1269:screen-01.jpg]
I still have some issues to work out with the automatic vertex-bone association, but it runs smoothly now!

Again, thanks for the help people.
0

Share this post


Link to post
Share on other sites
Debug compiles (depending on what API you're using) usually link in debug (vs. release) libraries. Those debug libraries commonly do a lot of error-checking ( that's what "debug" does for a living ) - looking for unitialized variables, array indices out of bounds, etc., etc. Your experience isn't necessarily out of the ordinary. E.g., I get ratios of 200-400 ( 180mS vs. 0.7mS for one of my routines comes to mind ) between debug and release execution times.
1

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1296834694' post='4769572']
Debug compiles (depending on what API you're using) usually link in debug (vs. release) libraries. Those debug libraries commonly do a lot of error-checking ( that's what "debug" does for a living ) - looking for unitialized variables, array indices out of bounds, etc., etc. Your experience isn't necessarily out of the ordinary. E.g., I get ratios of 200-400 ( 180mS vs. 0.7mS for one of my routines comes to mind ) between debug and release execution times.
[/quote]

Yeah, I knew debug does a lot for checking for errors, hence why I usually run in debug mode when debugging (actually, I've noticed you can't rely on the debugger in release mode). I've just never had such a huge gap in performance, until now. That'll teach me to post on here with questions that could've been resolved by two mouse clicks. =)
0

Share this post


Link to post
Share on other sites
Actually, since I'm not testing with a higher polygon count, does anyone know what a low- to medium- acceptable polygon count is for a human model? I'm no modeler, but I can just use subdivision to create a higher-resolution model to test.
0

Share this post


Link to post
Share on other sites
I don't know about "acceptable," but something a bit more complete than what you have in your posted image: maybe on the order of 2000-4000 faces (triangles), about as many vertices.
1

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  
Followers 0