2.5 - Optimisations for Keyframe Drawing in DopeSheet

Keyframes are now prepared for drawing by being added to a binary-tree structure instead of using insertion-sort on a Double-Linked List. This gives rather significant improvements on a few bad cases (*).

I've implemented a basic Red-Black Tree whose nodes/data-structures can also be used as a simple Double-Linked List (ListBase) for this purpose. The implementation of this tree currently does not have support for removing individual nodes, since such capabilities aren't needed yet. 

Stats (using keyframes from an imported .bvh animation file):
* When only the keyframes are drawn (i.e. long keyframes are not identified), the time needed to draw the DopeSheet region 10 times went down from 4000ms to about 300ms.
* When long keyframes are considered as well, the same test has gone from 6000ms to 3000ms. There is still a bottleneck there that I haven't been able to remove yet (an attempt at this made the runtimes go through the roof - 32000 ms for the test done here).

Assorted Notes:
* Added missing headers for some files
* Fixed profiling flags for mingw. There was an extra space which prevented the sound-code from compiling.

2 files changed, 86 insertions, 7 deletions

diff --git a/source/blender/editors/space_action/action_ops.c b/source/blender/editors/space_action/action_ops.c
index d1c9e1deac3..c4dbe92985a 100644
--- a/source/blender/editors/space_action/action_ops.c
+++ b/source/blender/editors/space_action/action_ops.c
@@ -32,6 +32,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "DNA_listBase.h"
+#include "DNA_anim_types.h"
 #include "DNA_action_types.h"
 #include "DNA_scene_types.h"
 #include "DNA_screen_types.h"
@@ -57,6 +58,70 @@
 #include "WM_types.h"
 
 
+/* ------------- */
+
+#include "BLI_dlrbTree.h"
+#include "ED_anim_api.h"
+#include "ED_keyframes_draw.h"
+#include "DNA_object_types.h"
+
+static int act_drawtree_test_exec (bContext *C, wmOperator *op)
+{
+	bAnimContext ac;
+	bDopeSheet *ads;
+	ListBase anim_data = {NULL, NULL};
+	bAnimListElem *ale;
+	int filter, items;
+	
+	ANIM_animdata_get_context(C, &ac);
+	ads= ac.data;
+	
+	/* build list of channels to draw */
+	filter= (ANIMFILTER_VISIBLE|ANIMFILTER_CHANNELS);
+	items= ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
+	
+	if (items) {
+		for (ale= anim_data.first; ale; ale= ale->next) {
+			AnimData *adt= BKE_animdata_from_id(ale->id);
+			
+			
+			if (ale->type == ANIMTYPE_GROUP) {
+				DLRBT_Tree keys;
+				ActKeyColumn *ak;
+				
+				BLI_dlrbTree_init(&keys);
+				
+					agroup_to_keylist(adt, ale->data, &keys, NULL);
+				
+				BLI_dlrbTree_linkedlist_sync(&keys);
+				
+					printf("printing sorted list of object keyframes --------------- \n");
+					for (ak= keys.first; ak; ak= ak->next) {
+						printf("\t%p (%f) | L:%p R:%p P:%p \n", ak, ak->cfra, ak->left, ak->right, ak->parent);
+					}	
+
+					printf("printing tree ---------------- \n");
+					for (ak= keys.root; ak; ak= ak->next) {
+						printf("\t%p (%f) | L:%p R:%p P:%p \n", ak, ak->cfra, ak->left, ak->right, ak->parent);
+					}
+				
+				BLI_dlrbTree_free(&keys);
+				
+				break;
+			}
+		}
+		
+		BLI_freelistN(&anim_data);
+	}
+}
+
+void ACT_OT_test (wmOperatorType *ot)
+{
+	ot->idname= "ACT_OT_test";
+	
+	ot->exec= act_drawtree_test_exec;
+}
+
 /* ************************** registration - operator types **********************************/
 
 void action_operatortypes(void)
@@ -85,6 +150,9 @@ void action_operatortypes(void)
 	
 	WM_operatortype_append(ACT_OT_previewrange_set);
 	WM_operatortype_append(ACT_OT_view_all);
+	
+	// test
+	WM_operatortype_append(ACT_OT_test);
 }
 
 /* ************************** registration - keymaps **********************************/
@@ -154,6 +222,9 @@ static void action_keymap_keyframes (wmWindowManager *wm, ListBase *keymap)
 	
 	/* transform system */
 	transform_keymap_for_space(wm, keymap, SPACE_ACTION);
+	
+		/* test */
+	WM_keymap_add_item(keymap, "ACT_OT_test", QKEY, KM_PRESS, 0, 0);
 }
 
 /* --------------- */
diff --git a/source/blender/editors/space_action/action_select.c b/source/blender/editors/space_action/action_select.c
index ef1b392815d..e358f559b14 100644
--- a/source/blender/editors/space_action/action_select.c
+++ b/source/blender/editors/space_action/action_select.c
@@ -37,6 +37,7 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_arithb.h"
+#include "BLI_dlrbTree.h"
 
 #include "DNA_anim_types.h"
 #include "DNA_action_types.h"
@@ -224,7 +225,6 @@ static void borderselect_action (bAnimContext *ac, rcti rect, short mode, short
 	BeztEditFunc ok_cb, select_cb;
 	View2D *v2d= &ac->ar->v2d;
 	rctf rectf;
-	//float ymin=0, ymax=(float)(-ACHANNEL_HEIGHT);
 	float ymin=0, ymax=(float)(-ACHANNEL_HEIGHT_HALF);
 	
 	/* convert mouse coordinates to frame ranges and channel coordinates corrected for view pan/zoom */
@@ -745,7 +745,7 @@ static void actkeys_mselect_column(bAnimContext *ac, short select_mode, float se
 static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode, short column)
 {
 	ListBase anim_data = {NULL, NULL};
-	ListBase anim_keys = {NULL, NULL};
+	DLRBT_Tree anim_keys;
 	bAnimListElem *ale;
 	int filter;
 	
@@ -784,10 +784,12 @@ static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode,
 	else {
 		/* found match - must return here... */
 		AnimData *adt= ANIM_nla_mapping_get(ac, ale);
-		ActKeyColumn *ak;
+		ActKeyColumn *ak, *akn=NULL;
 		
 		/* make list of keyframes */
 		// TODO: it would be great if we didn't have to apply this to all the keyframes to do this...
+		BLI_dlrbTree_init(&anim_keys);
+		
 		if (ale->key_data) {
 			switch (ale->datatype) {
 				case ALE_OB:
@@ -825,8 +827,11 @@ static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode,
 			gpl_to_keylist(ads, gpl, &anim_keys, NULL);
 		}
 		
-		/* loop through keyframes, finding one that was clicked on */
-		for (ak= anim_keys.first; ak; ak= ak->next) {
+		// the call below is not strictly necessary, since we have adjacency info anyway
+		//BLI_dlrbTree_linkedlist_sync(&anim_keys);
+		
+		/* loop through keyframes, finding one that was within the range clicked on */
+		for (ak= anim_keys.root; ak; ak= akn) {
 			if (IN_RANGE(ak->cfra, rectf.xmin, rectf.xmax)) {
 				/* set the frame to use, and apply inverse-correction for NLA-mapping 
 				 * so that the frame will get selected by the selection functiosn without
@@ -836,14 +841,17 @@ static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode,
 				found= 1;
 				break;
 			}
+			else if (ak->cfra < rectf.xmin)
+				akn= ak->right;
+			else
+				akn= ak->left;
 		}
 		
 		/* remove active channel from list of channels for separate treatment (since it's needed later on) */
 		BLI_remlink(&anim_data, ale);
 		
 		/* cleanup temporary lists */
-		BLI_freelistN(&anim_keys);
-		anim_keys.first = anim_keys.last = NULL;
+		BLI_dlrbTree_free(&anim_keys);
 		
 		/* free list of channels, since it's not used anymore */
 		BLI_freelistN(&anim_data);