next »

[peous]

Hi guys !

I'm currently working on incoming game that involves 3d animations made using motion capture.

The problem that such capture have a lot of animation keys, and thus weight a lot in memory.
I'm starting a custom algorithm to remove useless values, but I'd like to know if anyone here have some experience in such maths.

See Curve fitting


I've found some algorithms (in Maya) using simple "slope" formulas (that's a start)
But I already worked in the past on much more complex algorithms, taking in account the bone distribution...

Any idea or good link to share ?
Thanks !

[ClockworkWolf]

No experience in keyframes - but the kind of data in the graph reminds me of accelerometer data - which I've dabbled with, and my first thought would be to apply a low pas filter to your incoming data. Given the data is not in real time, I'd probably look at filter types that will not lag. A gaussian filter may do the trick to remove the unwanted high frequency jitter.

Once the filter has smoothed the curve, I'd look at keeping keys only in areas of the curve based on the tangents of the curve.

Curve Fitting is an interesting concept! I will read up on it.

My 2p!

[BorisTheBrave]

ClockworkWolf's suggest is not bad - smooth it, then sample at a frequency that varies with the slope.

My suggestion is to decide on the number of key frames. Spread them evenly over the time range, approximately where the curve is. Consider the bezier curve through them the fitted line. Then treat adjusting the points as an optimization problem, where you are attempting to optimize the sum of squares of residuals (the differences of each sample to the curve). There's lots of optimization stuff to read, and it'll be slow, but it will probably allow you to get to smaller numbers of keyframes than ClockworkWolf's suggestion. It's pretty much what the image you've shown is doing.

For bonus points, include bezier control points as well. Tool can be easily adjusted for cycling animations.

You don't want to do polynomial curve fitting - that is not appropriate for animation data, which is typically stationary.

[peous]

Thanks for the replies.

I'm going to try "smooth" first to see if it doesn't damage too much animation. Because it tends to remove some extreme positions that could be important, like if a character is taking an object, a smooth could prevent the hand from reaching the object as it's an extreme position (as you can see in previous graph, red curve is always below extremes of the black one).
I'll post updates here when done.

[ClockworkWolf]

Last I worked on a project with mocap data, we had animators to fix up the keys so cases like you mentioned don't happen. They were bored beyond tears.

It was with 3dsmax/biped, and I remember there was a frame reduction filter in biped but I am not sure if the animators used it.

[Columbo]

If you're not already doing it, then on top of your attempts to remove unneeded samples from your data, you can save a lot of data by compressing.

Firstly, you can make sure you don't store positions and scale data for a bone when they're not necessary (they're usually unnecessary for most bones in a skeletal animation).

Next, you can look at compressing quaternions, you can go down to 32 bits if you don't mind a loss in quality and you should be able to compress to 64 bits easily without any perceivable loss in precision.

[peous]

I store no scale as I never used it.

About translation, I need it for now because I store each bones in his "parent space" and not in "skeleton bindpose space". So I multiply each computed bone by inverse bindpose matrix at each computed frame. I know this may be inefficient, but that's the way it is for now, and like this it's easier for me to bind animation to the skeleton later in the engine and not at import time. If it changes one day, not storing translation would be a plus !

About orientation, I've seen some compression of quaternions like not storing "w" and computing it using "w=sqrt(1-x*x+y*y+z*z)", but yes I could also lower precision... you mean use some "half float" software implementation ? of fixed point ?

[BleakProspects]

I would try first filtering your data with a lowpass filter and then decimating it. Basically, create a set of K buckets. Average the data in the bucket. Put a data point there.

If that is not sufficient, you could try fitting a curve. You could use polynomial regression, for instance, or piecewise linear regression, or fitting splines.

[Columbo]

I store no scale as I never used it.

About translation, I need it for now because I store each bones in his "parent space" and not in "skeleton bindpose space". So I multiply each computed bone by inverse bindpose matrix at each computed frame. I know this may be inefficient, but that's the way it is for now, and like this it's easier for me to bind animation to the skeleton later in the engine and not at import time. If it changes one day, not storing translation would be a plus !

About orientation, I've seen some compression of quaternions like not storing "w" and computing it using "w=sqrt(1-x*x+y*y+z*z)", but yes I could also lower precision... you mean use some "half float" software implementation ? of fixed point ?

For quaternions in 32 bits, there's a fairly good, albeit brief description of the same algorithm I use in the 2nd to last paragraph here (I think it was originally in a game programming gems book, can't find the reference though) : http://bitsquid.blogspot.co.uk/2009/11/bitsquid-low-level-animation-system.html

For compressing quaternions to 64 bits, I wouldn't bother doing anything clever. Just multiply each value by 32767 and store the result in a short. There's plenty of ways to do it more cleverly, but this is fast to implement and to compute, and is probably accurate enough for the vast majority of cases.

It might be wise to make compression a per-animation option though, just in case there are some that need to be extra accurate for some reason.