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).