Sign in to follow this  
chibitotoro0_0

Efficient Deformations/Animations in Graphics Engines?

Recommended Posts

chibitotoro0_0    122
Hi, I've been working on my graphics engine for a bit now but I came across this problem which I didn't know the fastest way to solve and that is animations. I thought of a few ways to do this but none seemed flawless. I want to ask if other people have experience with how they are done in other engines or suggest alternatives which I haven't come up with off the top of my head. Let's take a human skeleton for example. 1) Separate the skeleton in code _______________________________ By this I mean handle all the bones in the body as separate meshes and transform them directly in the code. I see this is done in some DS games, where when you change a specific piece of armor, that piece of the mesh changes. This requires fine tuning in the code. But the way I see it, this will be efficiency for humanoid models, but not for others. The way I have thought of doing this is just to animate a set of bones and export them to Collada DAEs and essentially just attach different meshes to each joint. This however poses the big problem of very noticeable intersecting meshes. 2) Deform the mesh according to the skeleton _____________________________________________ I've programmed this before in C++ using Collada exports. Everything worked fine except it was slow calculating the inverse matrices for each joint and applying it to every vertex. Doing this in real time was time consuming. One could argue that I can calculate this only when a move has occurred, but this doesn't work too well with cases where a model is just standing still but is moving up and down doing some basic stationary actions such as just basic breathing. 3) Separating Every Frame of the animation into separate files _____________________________________________________________ The Big O of storage space of this method will be off the charts. To save on space, I'm assuming vertex texture coords don't change as the mesh moves. But each vertex position and their normals will change from frame to frame. However just saving 1/3 per frame still implies a huge amount of data that needs to be stored. I don't like this method and don't think that is how it's done. I know there must be a better way other than my best idea so far which is method 1. Can some people in the community give me some ideas or links? PS: The reason I ported using Collada is that OBJ files lack Joint information. Thanks. I think many others have the same questions that I do.

Share this post


Link to post
Share on other sites
jdindia    259
I'm not an expert on this, but since no one else is commenting, I'll tell you what I can. It's not an easy problem by any means, and the obvious proof of that is in the old Quake 2 method of literally saving mesh information for every frame of animation.

The generic solution is to have a skeleton for your 3d object. You have one mesh, but for each vertex in your mesh you give a weight for how much it's influenced by nearby bones. Typically there's a cap on how many bones can influence a vertex (usually 2-4, I think). The skeleton has some default position and the mesh is assumed to fit the skeleton in default position. When the skeleton moves, you then calculate where that vertex would wind up in each bone's frame of reference and then sum everything up, multiplying each by the respective weights, and divide by the sum of the weights to normalize the result. By adjusting the weights, you can improve things at joint intersections.

Since you don't want to generate all the skeletal data by yourself, you'll need to be able to import some skeletal animation data from somewhere. I remember learning a lot about how skeletal animation worked by actually reading the specification for the lightwave format.

My understanding is that modern 3d graphics cards are capable of doing all of this in vertex shaders. When I wrote such a program, it was on the cpu, which I think is easier to figure out the first time. I believe Doom 3 and many older games do it on the cpu. There are probably tricks to programming a vertex shader for skeletal animation, but I can't help you there. =(

Finally, this is one of those things that's probably been done many times. Since you're writing your own engine, I assume you're enjoying reinventing the wheel (and I do it a lot myself), but at the very least, look at Ogre's code or something like that to save yourself some headache.

I hope that helped.

Share this post


Link to post
Share on other sites
Ashaman73    13715
"2) Deform the mesh according to the skeleton":
I think this is the most widely used approach for animation in games. Calculate your skeleton on the CPU (today a character contains 30-100 bones!?!), then do the skinning in the vertex shader (GPU).

In a bone animation system you only need one inverse matrix, the bind pose matrix, which is precalculated and doesn't need any recalculation at run-time.

In this context a little tip:
If your transformations only consist of translations and rotations you could calculate the inverse of your matrix quite fast. In this case each transformation is the product of a rotation and translation:
A = T * R
inv(A) = inv(T * R) = inv(R) * inv(T) = transpose(R) * inv(T)
To invert T you just need to negate the position vector.


--
Ashaman

Share this post


Link to post
Share on other sites
Guardian_Light    122
It sounds like you are talking about two different but related animation techniques:

1) Skeletal (skinned) animation - often the vertex calculations are computed on the GPU. On the 3D modeling app side of things every app seems to do this stuff differently, and writing exporters for the bones and skeletal key frames can be a real bitch. In game engines the implementations are generally a little more consistent - mostly because there are some standard ways to do this on the GPU. Most engines allow around 1-100 bones per mesh, with up 1-8 bones influencing a single vertex. Anything more complex and you'll end doing all the work on the CPU (due to limitations of GPUs).

2) Vertex frames (which are either an entire copy of the mesh for each frame, or just the vertices's that change). You can do change sets between the base mesh, the previous frame mesh etc. etc. There are a lot of subtle differences between various implementations. Unless you have a lot of frames, you'll definitely be doing interpolation between frames.

#1 is definitely the right choice for humanoid type animated objects.
#2 is pretty much used only when necessary considering the massive amount of data stored per frame.

Most modern 3D engines support both types in someway, but there is a fair bit of variation. Check http://www.unrealtechnology.com/features.php?ref=animation for some bullet point ideas on what is normally supported.

I wish I could recommend a good book on real-time animation in general, but sadly, I am unaware of a good, comprehensive one. The game programming gems series has a bunch of useful articles on animation, but they are pretty much spread between all the separate volumes. Still, it is a good place to start for ideas.

Finally, the ogre3d graphics engine has a decent animation system and its open source. You can learn a lot by taking a peak at the code: http://www.ogre3d.org/

Share this post


Link to post
Share on other sites
chibitotoro0_0    122
Thanks for the replies! I'm kind of getting the hang of it now after looking at some other articles.

In terms of skeletal deformations. I only know how to do this on the CPU side, which was what I did previously in C++. All I can say is, it wasn't very efficient(the way I programmed it). I'm only familiar with OpenGL so I don't how to do the calculations via GPU.

So option 2 with the vertex frames is my newly decided approach. After looking at some articles, it seems logical to use this for small meshes. Also, this would work well if using non-skeletal-deformations like FFD, etc. But, yea you guys are right about one thing, the storage space increases exponentially with the mesh size. So I'll have to come up with a way to reduce the storage space or do it some other smarter way.

I do like reinventing the wheel =). I guess it gives me an edge after I learn enough of the basics I can develop new techniques. Also, after going to some interviews, they were surprised that I worked on my own engine and telling them what I could do and showing some material also helped me with these interviews (although I do not currently work at the two gaming companies I got into because Taiwanese gaming industry pays poorly). So to those who are in the same boat as me, don't give up because everyone told you to. I got alot of people telling me that I was stupid for reinventing the wheel.

Also, I didn't have to write a bone exporter because Collada provides an excellent one in their .dae exports.

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