[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [21672] branches/blender2.5/blender: 2. 5 - Optimisations for Keyframe Drawing in DopeSheet
Joshua Leung
aligorith at gmail.com
Sat Jul 18 09:11:37 CEST 2009
Revision: 21672
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21672
Author: aligorith
Date: 2009-07-18 09:11:37 +0200 (Sat, 18 Jul 2009)
Log Message:
-----------
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.
Modified Paths:
--------------
branches/blender2.5/blender/config/win32-mingw-config.py
branches/blender2.5/blender/source/blender/blenkernel/BKE_animsys.h
branches/blender2.5/blender/source/blender/editors/animation/keyframes_draw.c
branches/blender2.5/blender/source/blender/editors/armature/poselib.c
branches/blender2.5/blender/source/blender/editors/include/ED_keyframes_draw.h
branches/blender2.5/blender/source/blender/editors/space_action/action_ops.c
branches/blender2.5/blender/source/blender/editors/space_action/action_select.c
branches/blender2.5/blender/source/blender/editors/space_nla/nla_draw.c
branches/blender2.5/blender/source/blender/editors/space_view3d/drawarmature.c
Added Paths:
-----------
branches/blender2.5/blender/source/blender/blenlib/BLI_dlrbTree.h
branches/blender2.5/blender/source/blender/blenlib/intern/DLRB_tree.c
Modified: branches/blender2.5/blender/config/win32-mingw-config.py
===================================================================
--- branches/blender2.5/blender/config/win32-mingw-config.py 2009-07-18 07:01:16 UTC (rev 21671)
+++ branches/blender2.5/blender/config/win32-mingw-config.py 2009-07-18 07:11:37 UTC (rev 21672)
@@ -148,7 +148,7 @@
BF_DEBUG = False
BF_DEBUG_CCFLAGS= ['-g']
-BF_PROFILE_CCFLAGS = ['-pg', '-g ']
+BF_PROFILE_CCFLAGS = ['-pg', '-g']
BF_PROFILE_LINKFLAGS = ['-pg']
BF_PROFILE_FLAGS = BF_PROFILE_CCFLAGS
BF_PROFILE = False
Modified: branches/blender2.5/blender/source/blender/blenkernel/BKE_animsys.h
===================================================================
--- branches/blender2.5/blender/source/blender/blenkernel/BKE_animsys.h 2009-07-18 07:01:16 UTC (rev 21671)
+++ branches/blender2.5/blender/source/blender/blenkernel/BKE_animsys.h 2009-07-18 07:11:37 UTC (rev 21672)
@@ -1,5 +1,28 @@
-/* Testing code for new animation system in 2.5
- * Copyright 2009, Joshua Leung
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
+ * All rights reserved.
+ *
+ * Contributor(s): Joshua Leung (original author)
+ *
+ * ***** END GPL LICENSE BLOCK *****
*/
#ifndef BKE_ANIM_SYS_H
Added: branches/blender2.5/blender/source/blender/blenlib/BLI_dlrbTree.h
===================================================================
--- branches/blender2.5/blender/source/blender/blenlib/BLI_dlrbTree.h (rev 0)
+++ branches/blender2.5/blender/source/blender/blenlib/BLI_dlrbTree.h 2009-07-18 07:11:37 UTC (rev 21672)
@@ -0,0 +1,101 @@
+/**
+ * $Id: BLI_dlrbTree.h 21514 2009-07-11 05:41:21Z aligorith $
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
+ * All rights reserved.
+ *
+ * Contributor(s): Joshua Leung (original author)
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef BLI_DLRB_TREE_H
+#define BLI_DLRB_TREE_H
+
+/* Double-Linked Red-Black Tree Implementation:
+ *
+ * This is simply a Red-Black Tree implementation whose nodes can later
+ * be arranged + retrieved as elements in a Double-Linked list (i.e. ListBase).
+ * The Red-Black Tree implementation is based on the methods defined by Wikipedia.
+ */
+
+/* ********************************************** */
+/* Data Types and Type Defines */
+
+/* Base Structs --------------------------------- */
+
+/* Basic Layout for a Node */
+typedef struct DLRBT_Node {
+ /* ListBase capabilities */
+ struct DLRBT_Node *next, *prev;
+
+ /* Tree Associativity settings */
+ struct DLRBT_Node *left, *right;
+ struct DLRBT_Node *parent;
+
+ char tree_col;
+ /* ... for nice alignment, next item should usually be a char too... */
+} DLRBT_Node;
+
+/* Red/Black defines for tree_col */
+enum eDLRBT_Colors {
+ DLRBT_BLACK= 0,
+ DLRBT_RED,
+};
+
+/* -------- */
+
+/* The Tree Data */
+typedef struct DLRBT_Tree {
+ /* ListBase capabilities */
+ void *first, *last; /* these should be based on DLRBT_Node-s */
+
+ /* Root Node */
+ void *root; /* this should be based on DLRBT_Node-s */
+} DLRBT_Tree;
+
+/* ********************************************** */
+/* Public API */
+
+/* Create a new tree, and initialise as necessary */
+DLRBT_Tree *BLI_dlrbTree_new(void);
+
+/* Initialises some given trees */
+void BLI_dlrbTree_init(DLRBT_Tree *tree);
+
+/* Free some tree */
+void BLI_dlrbTree_free(DLRBT_Tree *tree);
+
+/* Make sure the tree's Double-Linked list representation is valid */
+void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
+
+
+
+/* Balance the tree after the given element has been added to it
+ * (using custom code, in the Binary Tree way).
+ */
+void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
+
+/* Remove the given element from the tree and balance again */
+// FIXME: this is not implemented yet...
+void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
+
+/* ********************************************** */
+
+#endif // BLI_DLRB_TREE_H
Property changes on: branches/blender2.5/blender/source/blender/blenlib/BLI_dlrbTree.h
___________________________________________________________________
Name: svn:eol-style
+ native
Added: branches/blender2.5/blender/source/blender/blenlib/intern/DLRB_tree.c
===================================================================
--- branches/blender2.5/blender/source/blender/blenlib/intern/DLRB_tree.c (rev 0)
+++ branches/blender2.5/blender/source/blender/blenlib/intern/DLRB_tree.c 2009-07-18 07:11:37 UTC (rev 21672)
@@ -0,0 +1,359 @@
+/**
+ * $Id: BLI_dlrbTree.c 21514 2009-07-11 05:41:21Z aligorith $
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
+ * All rights reserved.
+ *
+ * Contributor(s): Joshua Leung (original author)
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_dlrbTree.h"
+
+#include "DNA_listBase.h"
+
+/* *********************************************** */
+/* Tree API */
+
+/* Create a new tree, and initialise as necessary */
+DLRBT_Tree *BLI_dlrbTree_new (void)
+{
+ /* just allocate for now */
+ return MEM_callocN(sizeof(DLRBT_Tree), "DLRBT_Tree");
+}
+
+/* Just zero out the pointers used */
+void BLI_dlrbTree_init (DLRBT_Tree *tree)
+{
+ if (tree == NULL)
+ return;
+
+ tree->first= tree->last= tree->root= NULL;
+}
+
+/* Helper for traversing tree and freeing sub-nodes */
+static void recursive_tree_free_nodes (DLRBT_Node *node)
+{
+ /* sanity check */
+ if (node == NULL)
+ return;
+
+ /* free child nodes + subtrees */
+ recursive_tree_free_nodes(node->left);
+ recursive_tree_free_nodes(node->right);
+
+ /* free self */
+ MEM_freeN(node);
+}
+
+/* Free the given tree's data but not the tree itself */
+void BLI_dlrbTree_free (DLRBT_Tree *tree)
+{
+ if (tree == NULL)
+ return;
+
+ /* if the list-base stuff is set, just use that (and assume its set),
+ * otherwise, we'll need to traverse the tree...
+ */
+ if (tree->first) {
+ /* free list */
+ BLI_freelistN((ListBase *)tree);
+ }
+ else {
+ /* traverse tree, freeing sub-nodes */
+ recursive_tree_free_nodes(tree->root);
+ }
+
+ /* clear pointers */
+ tree->first= tree->last= tree->root= NULL;
+}
+
+/* ------- */
+
+/* Helper function - used for traversing down the tree from the root to add nodes in order */
+static void linkedlist_sync_add_node (DLRBT_Tree *tree, DLRBT_Node *node)
+{
+ /* sanity checks */
+ if ((tree == NULL) || (node == NULL))
+ return;
+
+ /* add left-node (and its subtree) */
+ linkedlist_sync_add_node(tree, node->left);
+
+ /* now add self
+ * - must remove detach from other links first
+ * (for now, only clear own pointers)
+ */
+ node->prev= node->next= NULL;
+ BLI_addtail((ListBase *)tree, (Link *)node);
+
+ /* finally, add right node (and its subtree) */
+ linkedlist_sync_add_node(tree, node->right);
+}
+
+/* Make sure the tree's Double-Linked list representation is valid */
+void BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree)
+{
+ /* sanity checks */
+ if (tree == NULL)
+ return;
+
+ /* clear list-base pointers so that the new list can be added properly */
+ tree->first= tree->last= NULL;
+
+ /* start adding items from the root */
+ linkedlist_sync_add_node(tree, tree->root);
+}
+
+/* *********************************************** */
+/* Tree Relationships Utilities */
+
+/* get the 'grandparent' - the parent of the parent - of the given node */
+static DLRBT_Node *get_grandparent (DLRBT_Node *node)
+{
+ if (node && node->parent)
+ return node->parent->parent;
+ else
+ return NULL;
+}
+
+/* get the 'uncle' - the sibling of the parent - of the given node */
+static DLRBT_Node *get_uncle (DLRBT_Node *node)
+{
+ DLRBT_Node *gpn= get_grandparent(node);
+
+ /* return the child of the grandparent which isn't the node's parent */
+ if (gpn) {
+ if (gpn->left == node->parent)
+ return gpn->right;
+ else
+ return gpn->left;
+ }
+
+ /* not found */
+ return NULL;
+}
+
+/* *********************************************** */
+/* Tree Rotation Utilities */
+
+/* Left Rotation is only done for Right-Right Case, and Left-Right Case */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list