[Bf-blender-cvs] [d2a5ddb] master: Optimisations for building "Long Keyframes"

Joshua Leung noreply at git.blender.org
Tue Apr 15 17:25:02 CEST 2014


Commit: d2a5ddb4ec12245b4d1580490d88e808a2a04761
Author: Joshua Leung
Date:   Wed Apr 16 03:21:06 2014 +1200
https://developer.blender.org/rBd2a5ddb4ec12245b4d1580490d88e808a2a04761

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.

===================================================================

M	source/blender/editors/animation/keyframes_draw.c

===================================================================

diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c
index 1dea132..4dc3b17 100644
--- a/source/blender/editors/animation/keyframes_draw.c
+++ b/source/blender/editors/animation/keyframes_draw.c
@@ -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 

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list