blender
/
blender
131
398
Fork 575
Code Issues 6.2k Pull Requests 748 Projects 19 Wiki Activity

Optimisations for building "Long Keyframes" 

For a long time, one of the bottlenecks when drawing summary channels in the dopesheet
(especially with many objects) was how the long keyframes feature (i.e showing holds
between keyframes) got built. Specifically, it was the step where we check on the previous
keyframe to see whether there's a hold between those two.

The old code performed some elaborate checks, which made sense back when we used to handle
certain summary channels (e.g. object-action/ipo, and groups IIRC) differently. However,
nowadays, everything just does it by going over the FCurves one by one, so the offending
code wasn't really providing much benefit. Unless I've forgotten some other reason why
that old method is necessary, this commit should provide a decent speedup here, making
things somewhat interactive now (if still a bit jerky).

Other Tweaks:
1) Introduced float-precision threshold when checking to see whether an existing long
   keyframe could be reused. This should hopefully reduce the number of fp-jitter issues
   when creating summaries for many channels, reducing the number of duplicates created.
2) Precompute colours used for shading the long keyframes, instead of recomputing for
   each block.
This commit is contained in:
Joshua Leung 2014-04-16 03:21:06 +12:00
parent 76dd3db304
commit d2a5ddb4ec
1 changed files with 41 additions and 149 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

190
source/blender/editors/animation/keyframes_draw.c
View File

@ -62,6 +62,7 @@
#include "DNA_gpencil_types.h"
#include "DNA_mask_types.h"
#include "BKE_fcurve.h"
#include "BKE_key.h"
#include "BKE_material.h"
#include "BKE_global.h" // XXX remove me!
@ -258,110 +259,6 @@ static void add_masklay_to_keycolumns_list(DLRBT_Tree *keys, MaskLayerShape *mas
BLI_dlrbTree_add(keys, compare_ak_masklayshape, nalloc_ak_masklayshape, nupdate_ak_masklayshape, masklay_shape);
}
/* ActBeztColumns (Helpers for Long Keyframes) ------------------------------ */
/* maximum size of default buffer for BezTriple columns */
#define MAX_ABK_BUFSIZE 4
/* BezTriple Container Node */
// NOTE: only used internally while building Long Keyframes for now, but may be useful externally?
typedef struct ActBeztColumn {
/* Tree Node interface ---------------- */
/* ListBase linkage */
struct ActBeztColumn *next, *prev;
/* sorting-tree linkage */
struct ActBeztColumn *left, *right; /* 'children' of this node, less than and greater than it (respectively) */
struct ActBeztColumn *parent; /* parent of this node in the tree */
char tree_col; /* DLRB_BLACK or DLRB_RED */
char pad;
/* BezTriple Store -------------------- */
short numBezts; /* number of BezTriples on this frame */
float cfra; /* frame that the BezTriples occur on */
BezTriple *bezts[MAX_ABK_BUFSIZE]; /* buffer of pointers to BezTriples on the same frame */
//BezTriple **bezts_extra; /* secondary buffer of pointers if need be */
} ActBeztColumn;
/* --------------- */
/* Comparator callback used for ActBeztColumns and BezTriple */
static short compare_abk_bezt(void *node, void *data)
{
ActBeztColumn *abk = (ActBeztColumn *)node;
BezTriple *bezt = (BezTriple *)data;
if (bezt->vec[1][0] < abk->cfra)
return -1;
else if (bezt->vec[1][0] > abk->cfra)
return 1;
else
return 0;
}
/* New node callback used for building ActBeztColumns from BezTriples */
static DLRBT_Node *nalloc_abk_bezt(void *data)
{
ActBeztColumn *abk = MEM_callocN(sizeof(ActBeztColumn), "ActKeyColumn");
BezTriple *bezt = (BezTriple *)data;
/* store the BeztTriple in the buffer, and keep track of its frame number */
abk->cfra = bezt->vec[1][0];
abk->bezts[abk->numBezts++] = bezt;
return (DLRBT_Node *)abk;
}
/* Node updater callback used for building ActBeztColumns from BezTriples */
static void nupdate_abk_bezt(void *node, void *data)
{
ActBeztColumn *abk = (ActBeztColumn *)node;
BezTriple *bezt = (BezTriple *)data;
/* just add the BezTriple to the buffer if there's space, or allocate a new one */
if (abk->numBezts >= MAX_ABK_BUFSIZE) {
// TODO: need to allocate new array to cater...
//bezts_extra = MEM_callocN(...);
if (G.debug & G_DEBUG)
printf("FIXME: nupdate_abk_bezt() missing case for too many overlapping BezTriples\n");
}
else {
/* just store an extra one */
abk->bezts[abk->numBezts++] = bezt;
}
}
/* --------------- */
/* Return the BezTriple in the given ActBeztColumn that matches the requested value */
static BezTriple *abk_get_bezt_with_value(ActBeztColumn *abk, float value)
{
BezTriple *bezt;
int i;
/* sanity checks */
if (abk == NULL)
return NULL;
/* look over each BezTriple in this container */
for (i = 0; i < abk->numBezts; i++) {
/* only do exact match for now... */
if (/*i >= MAX_ABK_BUFSIZE*/ 0) {
// TODO: this case needs special handling
}
else {
/* just use the default buffer */
bezt = abk->bezts[i];
if (bezt->vec[1][1] == value)
return bezt;
}
}
return NULL;
}
/* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
/* Comparator callback used for ActKeyBlock and cframe float-value pointer */
@ -370,10 +267,11 @@ short compare_ab_cfraPtr(void *node, void *data)
{
ActKeyBlock *ab = (ActKeyBlock *)node;
float *cframe = data;
float val = *cframe;
if (*cframe < ab->start)
if (val < ab->start)
return -1;
else if (*cframe > ab->start)
else if (val > ab->start)
return 1;
else
return 0;
@ -396,17 +294,25 @@ static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn)
return ab;
}
static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, DLRBT_Tree *beztTree, BezTriple *beztn)
static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, BezTriple *first_bezt, BezTriple *beztn)
{
ActKeyBlock *new_ab = NULL;
ActBeztColumn *abk;
BezTriple *prev;
BezTriple *prev = NULL;
/* get the BezTriple immediately before the given one which has the same value */
/* the keyframes immediately before the ones containing the specified keyframe */
abk = (ActBeztColumn *)BLI_dlrbTree_search_prev(beztTree, compare_abk_bezt, beztn);
/* if applicable, the BezTriple with the same value */
prev = (abk) ? abk_get_bezt_with_value(abk, beztn->vec[1][1]) : NULL;
if (beztn != first_bezt) {
/* XXX: Unless I'm overlooking some details from the past, this should be sufficient?
* The old code did some elaborate stuff trying to find keyframe columns for
* the given BezTriple, then step backwards to the column before that, and find
* an appropriate BezTriple with matching values there. Maybe that was warranted
* in the past, but now, that list is only ever filled with keyframes from the
* current FCurve.
*
* -- Aligorith (20140415)
*/
prev = beztn - 1;
}
/* check if block needed - same value(s)?
* -> firstly, handles must have same central value as each other
@ -414,6 +320,7 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, DLRBT_Tree *beztTree,
*/
if (prev == NULL) return;
if (IS_EQF(beztn->vec[1][1], prev->vec[1][1]) == 0) return;
if (IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) == 0) return;
if (IS_EQF(prev->vec[1][1], prev->vec[2][1]) == 0) return;
@ -428,6 +335,7 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, DLRBT_Tree *beztTree,
ActKeyBlock *ab, *abn = NULL;
/* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there
* Note: we perform a tree traversal here NOT a standard linked-list traversal...
* Note: we can't search from end to try to optimize this as it causes errors there's
* an A ___ B |---| B situation
*/
@ -436,17 +344,19 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, DLRBT_Tree *beztTree,
// A|------------------------------------------------|A
// A|----|A|---|A|-----------------------------------|A
for (ab = blocks->root; ab; ab = abn) {
/* check if this is a match, or whether we go left or right */
if (ab->start == prev->vec[1][0]) {
/* check if this is a match, or whether we go left or right
* NOTE: we now use a float threshold to prevent precision errors causing problems with summaries
*/
if (IS_EQT(ab->start, prev->vec[1][0], BEZT_BINARYSEARCH_THRESH)) {
/* set selection status and 'touched' status */
if (BEZSELECTED(beztn)) ab->sel = SELECT;
ab->modified += 1;
ab->modified++;
/* done... no need to insert */
return;
}
else {
ActKeyBlock **abnp = NULL;
ActKeyBlock **abnp = NULL; /* branch to go down - used to hook new blocks to parents */
/* check if go left or right, but if not available, add new node */
if (ab->start < prev->vec[1][0])
@ -674,18 +584,23 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa
/* draw keyblocks */
if (blocks) {
float sel_color[4], unsel_color[4];
/* cache colours first */
UI_GetThemeColor4fv(TH_STRIP_SELECT, sel_color);
UI_GetThemeColor4fv(TH_STRIP, unsel_color);
sel_color[3] *= alpha;
unsel_color[3] *= alpha;
/* NOTE: the tradeoff for changing colors between each draw is dwarfed by the cost of checking validity */
for (ab = blocks->first; ab; ab = ab->next) {
if (actkeyblock_is_valid(ab, keys)) {
float color[4];
/* draw block */
if (ab->sel)
UI_GetThemeColor4fv(TH_STRIP_SELECT, color);
glColor4fv(sel_color);
else
UI_GetThemeColor4fv(TH_STRIP, color);
color[3] *= alpha;
glColor4fv(color);
glColor4fv(unsel_color);
glRectf(ab->start, ypos - iconsize, ab->end, ypos + iconsize);
}
@ -875,7 +790,6 @@ void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
/* loop through each F-Curve, grabbing the keyframes */
for (ale = anim_data.first; ale; ale = ale->next) {
/* Why not use all #eAnim_KeyType here?
* All of the other key types are actually "summaries" themselves, and will just end up duplicating stuff
* that comes up through standard filtering of just F-Curves.
@ -896,7 +810,7 @@ void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
break;
}
}
BLI_freelistN(&anim_data);
}
}
@ -972,7 +886,6 @@ void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *bl
void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree *blocks)
{
DLRBT_Tree *beztTree = NULL;
BezTriple *bezt;
unsigned int v;
@ -981,25 +894,10 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree
if (adt)
ANIM_nla_mapping_apply_fcurve(adt, fcu, 0, 0);
/* if getting long keyframes too, grab the BezTriples in a BST for
* accelerated searching...
*/
if (blocks) {
/* init new tree */
beztTree = BLI_dlrbTree_new();
/* populate tree with the BezTriples */
for (v = 0, bezt = fcu->bezt; v < fcu->totvert; v++, bezt++)
BLI_dlrbTree_add(beztTree, compare_abk_bezt, nalloc_abk_bezt, nupdate_abk_bezt, bezt);
/* make sure that it is suitable for linked-list searching too */
BLI_dlrbTree_linkedlist_sync(beztTree);
}
/* loop through beztriples, making ActKeysColumns and ActKeyBlocks */
for (v = 0, bezt = fcu->bezt; v < fcu->totvert; v++, bezt++) {
add_bezt_to_keycolumns_list(keys, bezt);
if (blocks) add_bezt_to_keyblocks_list(blocks, beztTree, bezt);
if (blocks) add_bezt_to_keyblocks_list(blocks, fcu->bezt, bezt);
}
/* update the number of curves that elements have appeared in */
@ -1007,12 +905,6 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree
set_touched_actkeycolumn(keys->root);
if (blocks)
set_touched_actkeyblock(blocks->root);
/* free temp data for building long keyframes */
if (blocks && beztTree) {
BLI_dlrbTree_free(beztTree);
MEM_freeN(beztTree);
}
/* unapply NLA-mapping if applicable */
if (adt)