Prototype for new Reduce Keyframes operator and assisting module
Needs ReviewPublic
Actions

Authored by Richard Roberts (Riro) on Dec 11 2014, 4:41 AM.

Details

Reviewers

Summary

I've added a new operator to the graph_edit module, in source/blender/editors/space_graph. The purpose of this operator is to give Blender users the ability to reduce the number of keyframes in a dense animation, to a particular number. By density I mean that a high number of key-frames exist in the animation. If the user is intending to edit the animation, this density can become an issue. For example a user might want to reduce a dense 90 keyframes of a motion capture animation to a sparse 20 keyframe animation. I imagine that the operator will be useful in situations where motion capture or physics simulation has been used to create animation which now needs to be edited. It may also be helpful if a user has manually created dense animation data, and now wishes to simplify it. In my testing, the operator takes no more than one second to complete for up to 100 frames of dense animation data.

This patch contains a new c module graph_reduction, with an accompanying ED_reduction header file. The module and header declare a number of data structures and functions that enable this operator to run. As well as the brief statements about the structures and functions given via comments in the code, I will attempt to give a somewhat adequate summary:

There are two algorithms used by the operator, the first "learns" the animation data in order to pick out which of the existing keyframes are most important. In implementation, this algorithm uses a dynamic programming approach to recursively update a table of best placements of keyframes. Once the algorithm is finished, an array of integers representing frames is given back to the operator. The operator will then pass these frame numbers to the next algorithm, which simple deletes all the existing keyframes of each curve, and inserts new keyframes at those indices. Once this has been done, the handles of the keyframes' beziers are tweaked to match the original data as closely as possible (this second algorithm is a uses a brute-force approach, checking a set of different anchor points for the beziers, using the best it finds).

Thanks!

Diff Detail

Event Timeline

Richard Roberts (Riro) updated this revision to Diff 2991.Dec 11 2014, 4:41 AM

Richard Roberts (Riro) retitled this revision from to Prototype for new Reduce Keyframes operator and assisting module.

Richard Roberts (Riro) updated this object.

Richard Roberts (Riro) added a reviewer: Joshua Leung (aligorith).

Hey again!

Of course I managed to do this wrong on my first time. I had changed a couple of things in the latest commit, but I missed these in the diff. I haven't figured out how to edit the diff to add this last commit yet, but in the mean time I have attached the necessary changes to the attached file below:

fix.diff4 KBDownload

Thanks.

Hi Richard,

Firstly, interesting approach :)

As I've mentioned in the inline comments, here are a few general comments related to code style/cross platform compiling:

Check out BLI_math_vectors.h" and the other headers there in blenlib for existing math functions you can reuse
Mixed code and declarations (i.e. defining variables in places other than at the start of a block) breaks compiling on some compilers (e.g. gcc)
Defining arrays with a variable size is something that we've generally had to avoid doing, as this wasn't supported by all compilers. IIRC, this one used to be a MSVC thing, though I can't remember
IIRC, defining the iterator variables in the for loops may not work either for all compilers.
For dynamically allocating/freeing memory in Blender code, only use MEM_mallocN, MEM_callocN, and MEM_freeN() from MEM_guardedalloc. This helps us keep track of memory leaks, as it will report where there are things which haven't been freed when exiting Blender
It's better to pass the anim_data linked-lists by reference (i.e. as pointers) for consistency with the rest of the code.

Regarding the new module:

It's probably better that you have the module (graph_reduce.c) in the "animation" module, so that it can in future be called from a similar operator in the action editor
"ED_reduction.h" is a bit too generic. Maybe something like "ED_keyframe_reduction.h" may be better

Functionality:
Perhaps the biggest thing you should be aware of is that F-Curves can actually contain two different types of data: There are BezTriples (or "keyframes") and then there are FPoints (or "samples").

Most of the time, BezTriples are the ones you'll get. They are also the ones that users can edit, and which some importers/baking tools do create. So, the code you've got is fine for those.

However, we also have FPoints, which are basically frame+value pairs. These are meant to be created by any tool which bakes or imports animation data which has been sampled on a frame-by-frame basis, resulting in a dense dataset. It would be particularly useful if it was possible to use such reduction tools on F-Curves containing these points to convert these dense caches into a set of simpler, editable keyframes (i.e. BezTriples).

So, a great start so far.

source/blender/editors/space_graph/graph_edit.c
1034	Mixed code and declarations It'd be better to pass pointer to anim_data (i.e. &anim_data)
1076	Hmm... this operator should only ever end up running in the Graph Editor, so this check should be redundant. Was there some bug that this was added to handle?
source/blender/editors/space_graph/graph_reduction.c
91 ↗	(On Diff #2991)	sub_vn_vnvn(dst, src, size)
97 ↗	(On Diff #2991)	result = dot_vn_vn(a, b, size);
106 ↗	(On Diff #2991)	Hmm... it doesn't look like we have a copy_vn_vn(dst, src, size) for this. Maybe it'd be better if you defined that one, probably as a wrapper for: memcpy(dst, src, sizeof(float) * size)
112 ↗	(On Diff #2991)	mul_vn_fl(vec, size, val)
137 ↗	(On Diff #2991)	BLI_countlist(ListBase *) Example usage: ListBase anim_data = {NULL, NULL}; // ... len = BLI_countlist(&anim_data);
149 ↗	(On Diff #2991)	So is the idea here that you have a single curve that stores arrays of the values/keys at each frame within that range?
203 ↗	(On Diff #2991)	Watch out for div by zero
349 ↗	(On Diff #2991)	Is there any reason why it's 40 tweaks?
444 ↗	(On Diff #2991)	Not all the compilers we use/support like "mixed declarations and code". You'll need to have this line after all the declarations are done
447 ↗	(On Diff #2991)	IIRC, this is C99 stuff which is not portable for all the compilers we currently support (notably MSVC)
481 ↗	(On Diff #2991)	Mixed code and declarations
485 ↗	(On Diff #2991)	Hmm... I've a feeling this is another thing which may not compile/parse cleanly on all platforms.
499 ↗	(On Diff #2991)	Mixed code and declarations Dynamic array sizes

Joshua Leung (aligorith) requested changes to this revision.Dec 11 2014, 7:22 AM

Joshua Leung (aligorith) edited edge metadata.

This revision now requires changes to proceed.Dec 11 2014, 7:22 AM

Richard Roberts (Riro) edited edge metadata.Dec 16 2014, 8:08 AM

In this version I have responded to the previous suggestions. I have decided to upload this version as a diff over multiple commits for brevity, but if smaller commit-by-commit diffs are preferable please let me know!

First up here are some responses to questions:

Hmm... this operator should only ever end up running in the Graph Editor, so this check should be redundant. Was there some bug that this was added to handle?

It is redundant. Originally I had copied and pasted the operator from another module. I had overlooked this check, and it has now been removed.

So is the idea here that you have a single curve that stores arrays of the values/keys at each frame within that range?

Yes, that is correct. It is a single curve in a high dimension, where that dimension is equal to the total number of curves. This means the distance based cost function need only concern itself with one high dimensional curve, rather than many one-dimensional curves. I've changed the variables names in this patch to make this part of the algorithm seem more intuitive. The n-dimensional curve data structure has now be renamed to NPoseArray, an array of poses. A pose is simply an array of the values of curves at the each frame, i.e. all curve values at frame one for the first index, all curve values at frame two for the second index, all curve values frame n for the n-th index. Abstractly speaking, the data structure now gives the algorithm a way to compare distance between poses.

Is there any reason why it's 40 tweaks?

I didn't explain this well previously. I chose 40 tweaks because it was a large enough number to try a good range of bezier handle placements, while being a small enough number for the algorithm to run quickly. Using more tweaks will mean that the algorithm will tweak the handles to match to the original data more accurately, at the cost of being more expensive. It would be a better idea for me to change this to some kind of heuristic-based algorithm, but ultimately it's only a small part of a larger and more costly algorithm. In any case, I've now defined a global variable called NUMBER_OF_TWEAKS, where the amount of tweaks can be set - I'm not sure what the best thing is to do in this case?

*Patch Summary*:

Functional changes:

added functions to reduction module to deal with the processing of fcurves that use FPoints instead of BezTriples.

Operator changes:

the operator exec function now does more processing, and uses the reduction module more as an API, rather than wrapping an all-in-function from the module. Specifically, the operator decides whether the data is of the FPoints or BezTriples format, and then does the following:
1. build pose array
2. pick most significant frames
  
  for each curve
  1. cache fcurve data
  2. delete all fcurve data
  3. rebuild fcurve using BezTriples placed at the most significant frames
  4. tweak new fcurves handles

Reduction module changes:

separated all areas where there was mixed code
removed all variably sized arrays, and where necessary replaced these with dynamically allocated arrays
all dynamically allocated arrays now use blender MEM_mallocN, MEM_callocN, and MEM_freeN functions
most of the utility functions have been removed, and calls to such functions have been replaced with the correlating blender functions.

Other:

added a copy_vn_vn function to BLI_math_vector

Note I'm still relatively new to c, please don't hesitate to be picky (I won't mind), and again - thanks for all of your time and help!

In this diff I have simply moved the reduction module into the animation directory, and changed the name of it's matching header file:

from - blender/source/blender/editors/graph/graph_reduction.c
to - blender/source/blender/editors/animation/anim_reduction.c

from - ED_reduction.h
to - ED_keyframes_reduction.h

The appropriate changes have been made in the CMakeLists.txt files.

Joshua Leung (aligorith) added inline comments.Jan 5 2015, 12:32 AM

source/blender/editors/animation/anim_reduction.c
85	This method seems rather redundant.
107	There's no need for a loop here if you're just going to grab the value from the first FCurve encountered.
149	Why i+1 ?
201	Style: Else on a new line
344	Between this and ED_reduction_free_frame_cache(), it seems that it might be simpler and more transparent if you just passed "Frame cache" around instead of using the FrameCache typedef. That way, it's clearer what the nature of the types involved are. In that case, this function become something like: Frame ED_reduction_init_frame_cache(int n) { return MEM_mallocN(sizeof(Frame) * n, "FrameCache_new"); }
404	No space needed here
459	No space needed here
471	To avoid extra type implicit conversions, it's better if all of these numeric constants were declared as float literals. That is, 2.0f and 0.5f
489	This may be problematic on some compilers still. Currently, the general guideline for most of our codebase is that we stick to C90 features for all of our C code. At least last time this was reviewed, not all compilers had good/consistent support for C99 (despite that being over a decade old now!) AFAIK, although compound literals do work on MSVC and gcc (but only via an extension), it's probably better that we don't start using this here.
531	Style: Space before before the asterix but not after. So, FCurve *fcu,
550	Style: Prefer all non-primitive types to be declared before primitive types. So, BezTriple bezLeft; BezTriple bezRight; float start_f, end_f; int i;
556	Mixed code and declarations
560	It would be better if the order here is consistent: So, always do left first, then right. That way, it's easier to see what's going on. BTW, it seems a bit unexpected that p1 goes to the right (later) control whereas p2 goes to the left (earlier)
source/blender/editors/include/ED_keyframes_reduction.h
54	NPoseArray may be a nicer name?

In this version I have responded to the suggested changes. I agree with all of the suggestions, and have hopefully implemented the each one successfully. To answer the question as to why i + 1 is used in the ED_reduction_fill_pose_arr_beziertriples function:

The NPoseArray is a matrix, where the n-th column holds the value for each degree of freedom at frame n (the matrix can be imagined as a dense vector of poses). The 0-th row of this matrix structure always contains the frame number - this serves two purposes: firstly the frame number is available in the column data (this may be useful if I later introduce a NPose data type), and secondly it serves to create a numerical difference between two columns that have identical poses (this means the algorithm sees them as different poses). Doing this was a difficult decision for me, and to be honest it's only there at the moment to avoid poor output in an edge case where many frames are similar (for example an idle animation where a character only turns their head slightly over a long period of time).

The first loop adds the frame numbers to the matrix:

		for (j = 0; j < n_frames; j++)
			(*n_pose_array)[j][0] = j;

And then the next loop adds in the "real" data:

		for (i = 0, ale = anim_data->first; ale; i++, ale = ale->next) {
			fcu = ale->key_data;

			for (j = 0, bezt = fcu->bezt; j < fcu->totvert; j++, bezt++)
				(*n_pose_array)[j][i + 1] = bezt->vec[1][1];
		}

Other notes:

Sorry about the misuse of C99, I'm still adjusting to C90 - should be fixed now
The unexpected p1 anchor being linked to the right (later) control and p2 to the left (earlier) was actually a mistake, I've switched them - thanks for spotting that!

Thanks again for your time :)

I've been testing this patch out over the past 2 days. Firstly with a test case I put together quickly and then again with some mocap files I found online:

My test file -
cube_reduce-simple01.blend724 KBDownload
A collection of BVH files adapted for Blender - http://www.centralsource.com/blender/bvh/files.htm

There were 2 main issues that came up:

The default setting of 8 keyframes seems way too low. Often I needed 20-30 to start getting reasonable results. (EDIT: and indeed, it seems that that is what your initial description suggested)
Performance - In most "simple" files, it was a bit sluggish to tweak the value, but at least it responsive. Things were a bit more problematic for the "ballet" example from the BVH collection, which locked up my machine for 1-2 minutes, and then kept going again. That's due to the way the operators are set up to interact with the event system, every time the setting changes, the operator gets executed again.

Firstly, I'm curious how this compares to some other algorithms :) I tried briefly to run a similar tool in the mocap tools addon to compare these a bit (with some allowances for C vs Py), though that was unfortunately broken atm

Secondly, I think some tweaks will be needed to make sure that this can be run without it accidentally locking up people's work (which is more of a blender-integration problem). As part of this, I suspect that it may be beneficial to expose the NUM_OF_TWEAKS as a secondary parameter to the operator.

Now, as for the code:
I ran into a few errors when compiling the code (notably, the weird logic concerning WM_operator_props_ptr), and also managed to simplify some of the unnecessary wrappers around there. Those are all relatively minor things though that aren't really blocking issues for accepting the code.

Another point which will likely cause problems down the track is the way it currently only uses the first FCurve to determine what it's dealing with. To make it user-proof, it would be better that we actually check to make sure the FCurves being simplified were all roughly equivalent (i.e. similar frame ranges,

Overall though, I'm currently leaning towards accepting this patch now and then fixing up the issues before the release :)

Firstly, thanks a lot for the testing you've been doing! It's great to hear about another user's experience like. As a summary, I agree with the points you've raised - and will aim to make these changes over this month. Great news about the patch leaning towards acceptance, that would be really great! :D

How would you recommend continuing from here? I can make some of the changes you suggest, but will also need some help with a couple of things such as the issue where the algorithm "blocks" the program when running. Would I go the IRC channel about this?

Again thanks for all your help, very exciting! Below are some more specific replies to the points you raised:

The default setting of 8 keyframes seems way too low. Often I needed 20-30 to start getting reasonable results.

Yes, this actually quiet an issue. As a rule of thumb, I find that between 4 and 6 keyframes are required to accurately reduce a cyclic motion (recorded at 60 frames per second). So, if the motion capture is 360 frames long, I'd say between 24 and 36 frames. Perhaps one idea would be to set this variable to 10% of the frame count?

Performance - In most "simple" files, it was a bit sluggish to tweak the value, but at least it responsive. Things were a bit more problematic for the "ballet" example from the BVH collection, which locked up my machine for 1-2 minutes, and then kept going again. That's due to the way the operators are set up to interact with the event system, every time the setting changes, the operator gets executed again.

Yeah, this is also an issue. The algorithm really works best on motion segments up to around 200 or 300 frames - anything after that and the running time will become uncomfortable for users - it's an O(n^2) algorithm. I'm not sure what to here, if the user really wants to run the algorithm on a long sequence of motion data perhaps there is some way to warn them of this, and then run the process on a separate thread?

Firstly, I'm curious how this compares to some other algorithms :) I tried briefly to run a similar tool in the mocap tools addon to compare these a bit (with some allowances for C vs Py), though that was unfortunately broken atm

This is a good question. I'm writing a literature review currently, with the intention of comparing this technique to existing approaches. The main curve simplification algorithm is known as the Douglas-Peucker algorithm, and there are other heuristic based approaches. While it's possible that these algorithms may produce a result faster, the dynamic approach I used has a claim to optimal (produces "correct" result). I'm currently implementing other curve simplification algorithms, and plan to add a "choice" of reduction type in a second version of this patch. I'd hope to add these options in the format of a menu similar to the "Interpolation Type" (under the key menu in the graph editor window).

Secondly, I think some tweaks will be needed to make sure that this can be run without it accidentally locking up people's work (which is more of a blender-integration problem). As part of this, I suspect that it may be beneficial to expose the NUM_OF_TWEAKS as a secondary parameter to the operator.

Why didn't I think of this earlier?!

I ran into a few errors when compiling the code (notably, the weird logic concerning WM_operator_props_ptr), and also managed to simplify some of the unnecessary wrappers around there. Those are all relatively minor things though that aren't really blocking issues for accepting the code.

Yes, I need simplify the operator functions.

Another point which will likely cause problems down the track is the way it currently only uses the first FCurve to determine what it's dealing with. To make it user-proof, it would be better that we actually check to make sure the FCurves being simplified were all roughly equivalent (i.e. similar frame ranges,

This has been a concern to me for a while, but I haven't found a good way to analyze the data. Would I simply be able to iterate over the FCurves, and store there length to an array... if all elements in the array or approximately equal then the operator runs, or otherwise prints some error to Blender's status bar?