diff options
| -rw-r--r-- | config/win32-mingw-config.py | 2 | ||||
| -rw-r--r-- | source/blender/blenkernel/BKE_animsys.h | 27 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_dlrbTree.h | 101 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/DLRB_tree.c | 359 | ||||
| -rw-r--r-- | source/blender/editors/animation/keyframes_draw.c | 450 | ||||
| -rw-r--r-- | source/blender/editors/armature/poselib.c | 5 | ||||
| -rw-r--r-- | source/blender/editors/include/ED_keyframes_draw.h | 40 | ||||
| -rw-r--r-- | source/blender/editors/space_action/action_ops.c | 71 | ||||
| -rw-r--r-- | source/blender/editors/space_action/action_select.c | 22 | ||||
| -rw-r--r-- | source/blender/editors/space_nla/nla_draw.c | 7 | ||||
| -rw-r--r-- | source/blender/editors/space_view3d/drawarmature.c | 20 |
11 files changed, 898 insertions, 206 deletions
diff --git a/config/win32-mingw-config.py b/config/win32-mingw-config.py index 1223a4c49e9..375b8c36ce8 100644 --- a/config/win32-mingw-config.py +++ b/config/win32-mingw-config.py @@ -148,7 +148,7 @@ LLIBS = ['-lshell32', '-lshfolder', '-lgdi32', '-lmsvcrt', '-lwinmm', '-lmingw32 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 diff --git a/source/blender/blenkernel/BKE_animsys.h b/source/blender/blenkernel/BKE_animsys.h index b45917e6ca1..2447d1823af 100644 --- a/source/blender/blenkernel/BKE_animsys.h +++ b/source/blender/blenkernel/BKE_animsys.h @@ -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 diff --git a/source/blender/blenlib/BLI_dlrbTree.h b/source/blender/blenlib/BLI_dlrbTree.h new file mode 100644 index 00000000000..eeb224ad1f4 --- /dev/null +++ b/source/blender/blenlib/BLI_dlrbTree.h @@ -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 diff --git a/source/blender/blenlib/intern/DLRB_tree.c b/source/blender/blenlib/intern/DLRB_tree.c new file mode 100644 index 00000000000..debe02164fb --- /dev/null +++ b/source/blender/blenlib/intern/DLRB_tree.c @@ -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 */ +static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root) +{ + DLRBT_Node **root_slot, *pivot; + + /* pivot is simply the root's right child, to become the root's parent */ + pivot= root->right; + if (pivot == NULL) + return; + + if (root->parent) { + if (root == root->parent->left) + root_slot= &root->parent->left; + else + root_slot= &root->parent->right; + } + else + root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root); + + /* - pivot's left child becomes root's right child + * - root now becomes pivot's left child + */ + root->right= pivot->left; + if (pivot->left) pivot->left->parent= root; + + pivot->left= root; + pivot->parent= root->parent; + root->parent= pivot; + + /* make the pivot the new root */ + if (root_slot) + *root_slot= pivot; +} + +static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root) +{ + DLRBT_Node **root_slot, *pivot; + + /* pivot is simply the root's left child, to become the root's parent */ + pivot= root->left; + if (pivot == NULL) + return; + + if (root->parent) { + if (root == root->parent->left) + root_slot= &root->parent->left; + else + root_slot= &root->parent->right; + } + else + root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root); + + /* - pivot's right child becomes root's left child + * - root now becomes pivot's right child + */ + root->left= pivot->right; + if (pivot->right) pivot->right->parent= root; + + pivot->right= root; + pivot->parent= root->parent; + root->parent= pivot; + + /* make the pivot the new root */ + if (root_slot) + *root_slot= pivot; +} + +/* *********************************************** */ +/* Post-Insertion Balancing */ + +/* forward defines for insertion checks */ +static void insert_check_1(DLRBT_Tree *tree, DLRBT_Node *node); +static void insert_check_2(DLRBT_Tree *tree, DLRBT_Node *node); +static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node); +static void insert_check_4(DLRBT_Tree *tree, DLRBT_Node *node); + +/* ----- */ + +/* W. 1) Root must be black (so that the 2nd-generation can have a black parent) */ +static void insert_check_1 (DLRBT_Tree *tree, DLRBT_Node *node) +{ + if (node) { + /* if this is the root, just ensure that it is black */ + if (node->parent == NULL) + node->tree_col= DLRBT_BLACK; + else + insert_check_2(tree, node); + } +} + +/* W. 2+3) Parent of node must be black, otherwise recolor and flush */ +static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node) +{ + /* if the parent is not black, we need to change that... */ + if (node && node->parent && node->parent->tree_col) { + DLRBT_Node *unc= get_uncle(node); + + /* if uncle and parent are both red, need to change them to black and make + * the parent black in order to satisfy the criteria of each node having the + * same number of black nodes to its leaves + */ + if (unc && unc->tree_col) { + DLRBT_Node *gp= get_grandparent(node); + + /* make the n-1 generation nodes black */ + node->parent->tree_col= unc->tree_col= DLRBT_BLACK; + + /* - make the grandparent red, so that we maintain alternating red/black property + * (it must exist, so no need to check for NULL here), + * - as the grandparent may now cause inconsistencies with the rest of the tree, + * we must flush up the tree and perform checks/rebalancing/repainting, using the + * grandparent as the node of interest + */ + gp->tree_col= DLRBT_RED; + insert_check_1(tree, gp); + } + else { + /* we've got an unbalanced branch going down the grandparent to the parent, + * so need to perform some rotations to re-balance the tree + */ + insert_check_3(tree, node); + } + } +} + +/* W. 4) Perform rotation on sub-tree containing the 'new' node */ +static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) +{ + DLRBT_Node *gp= get_grandparent(node); + + /* check that grandparent and node->parent exist (jut in case... really shouldn't happen on a good tree) */ + if (node && node->parent && gp) { + /* a left rotation will switch the roles of node and its parent, assuming that + * the parent is the left child of the grandparent... otherwise, rotation direction + * should be swapped + */ + if ((node == node->parent->right) && (node->parent == gp->left)) { + rotate_left(tree, node); + node= node->left; + } + else if ((node == node->parent->left) && (node->parent == gp->right)) { + rotate_right(tree, node); + node= node->right; + } + // TODO: what about other cases? + + /* fix old parent's color-tagging */ + insert_check_4(tree, node); + } +} + +/* W. 5) Perform rotation in the opposite direction on the parent of the given node */ +static void insert_check_4 (DLRBT_Tree *tree, DLRBT_Node *node) +{ + DLRBT_Node *gp= get_grandparent(node); + + if (node == NULL) + return; + + /* modify the coloring of the grandparent and parent so that they still satisfy the constraints */ + node->parent->tree_col= DLRBT_BLACK; + gp->tree_col= DLRBT_RED; + + /* if there are several nodes that all form a left chain, do a right rotation to correct this + * (or a rotation in the opposite direction if they all form a right chain) + */ + if ((node == node->parent->left) && (node->parent == gp->left)) + rotate_right(tree, gp); + else /* ((node == node->parent->right) && (node->parent == gp->right)) */ + rotate_left(tree, gp); +} + +/* ----- */ + +/* 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) +{ + /* sanity checks */ + if ((tree == NULL) || (node == NULL)) + return; + + /* firstly, the node we just added should be red by default */ + node->tree_col= DLRBT_RED; + + /* start from case 1, an trek through the tail-recursive insertion checks */ + insert_check_1(tree, node); +} + +/* *********************************************** */ +/* Remove */ + +// TODO: this hasn't been coded yet, since this functionality was not needed by the author + +/* *********************************************** */ diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c index 64e008b92ca..78ceb4a0149 100644 --- a/source/blender/editors/animation/keyframes_draw.c +++ b/source/blender/editors/animation/keyframes_draw.c @@ -17,12 +17,12 @@ * 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) 2001-2002 by NaN Holding BV. + * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung * All rights reserved. * * The Original Code is: all of this file. * - * Contributor(s): Joshua Leung + * Contributor(s): Joshua Leung (full recode) * * ***** END GPL LICENSE BLOCK ***** */ @@ -42,8 +42,7 @@ #include "BLI_blenlib.h" #include "BLI_arithb.h" - -/* Types --------------------------------------------------------------- */ +#include "BLI_dlrbTree.h" #include "DNA_listBase.h" #include "DNA_anim_types.h" @@ -75,8 +74,6 @@ #include "BKE_context.h" #include "BKE_utildefines.h" -/* Everything from source (BIF, BDR, BSE) ------------------------------ */ - #include "BIF_gl.h" #include "BIF_glutil.h" @@ -93,53 +90,99 @@ /* *************************** Keyframe Processing *************************** */ -/* The equivalent of add_to_cfra_elem except this version - * makes ActKeyColumns - one of the two datatypes required - * for DopeSheet drawing. - */ -static void add_bezt_to_keycolumnslist(ListBase *keys, BezTriple *bezt) +/* Create a ActKeyColumn from a BezTriple */ +static ActKeyColumn *bezt_to_new_actkeycolumn(BezTriple *bezt) { - ActKeyColumn *ak, *akn; + ActKeyColumn *ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn"); - if (ELEM(NULL, keys, bezt)) return; + /* store settings based on state of BezTriple */ + ak->cfra= bezt->vec[1][0]; + ak->sel= BEZSELECTED(bezt) ? SELECT : 0; - /* try to any existing key to replace, or where to insert after */ - for (ak= keys->last; ak; ak= ak->prev) { - /* do because of double keys */ - if (ak->cfra == bezt->vec[1][0]) { - /* set selection status and 'touched' status */ - if (BEZSELECTED(bezt)) ak->sel = SELECT; - ak->modified += 1; - - return; + // TODO: handle type = bezt->h1 or bezt->h2 + ak->handle_type= 0; + + /* set 'modified', since this is used to identify long keyframes */ + ak->modified = 1; + + return ak; +} + +/* Add the given BezTriple to the given 'list' of Keyframes */ +static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt) +{ + ActKeyColumn *new_ak=NULL; + + if ELEM(NULL, keys, bezt) return; + + /* if there are no keys already, just add as root */ + if (keys->root == NULL) { + /* just add this as the root, then call the tree-balancing functions to validate */ + new_ak= bezt_to_new_actkeycolumn(bezt); + keys->root= (DLRBT_Node *)new_ak; + } + else { + ActKeyColumn *ak, *akp=NULL, *akn=NULL; + + /* traverse tree to find an existing entry to update the status of, + * or a suitable point to add at + */ + for (ak= keys->root; ak; akp= ak, ak= akn) { + /* check if this is a match, or whether we go left or right */ + if (ak->cfra == bezt->vec[1][0]) { + /* set selection status and 'touched' status */ + if (BEZSELECTED(bezt)) ak->sel = SELECT; + ak->modified += 1; + + /* done... no need to insert */ + return; + } + else { + ActKeyColumn **aknp= NULL; + + /* check if go left or right, but if not available, add new node */ + if (ak->cfra < bezt->vec[1][0]) + aknp= &ak->right; + else + aknp= &ak->left; + + /* if this does not exist, add a new node, otherwise continue... */ + if (*aknp == NULL) { + /* add a new node representing this, and attach it to the relevant place */ + new_ak= bezt_to_new_actkeycolumn(bezt); + new_ak->parent= ak; + *aknp= new_ak; + break; + } + else + akn= *aknp; + } } - else if (ak->cfra < bezt->vec[1][0]) break; } - /* add new block */ - akn= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn"); - if (ak) BLI_insertlinkafter(keys, ak, akn); - else BLI_addtail(keys, akn); + /* now, balance the tree taking into account this newly added node */ + BLI_dlrbTree_insert(keys, (DLRBT_Node *)new_ak); +} + + +/* Create a ActKeyColumn for a pair of BezTriples */ +static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn) +{ + ActKeyBlock *ab= MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock"); - akn->cfra= bezt->vec[1][0]; - akn->modified += 1; + ab->start= prev->vec[1][0]; + ab->end= beztn->vec[1][0]; + ab->val= beztn->vec[1][1]; - // TODO: handle type = bezt->h1 or bezt->h2 - akn->handle_type= 0; + ab->sel= (BEZSELECTED(prev) || BEZSELECTED(beztn)) ? SELECT : 0; + ab->modified = 1; - if (BEZSELECTED(bezt)) - akn->sel = SELECT; - else - akn->sel = 0; + return ab; } -/* The equivalent of add_to_cfra_elem except this version - * makes ActKeyBlocks - one of the two datatypes required - * for DopeSheet drawing. - */ -static void add_bezt_to_keyblockslist(ListBase *blocks, FCurve *fcu, int index) +static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, FCurve *fcu, int index) { - ActKeyBlock *ab, *abn; + ActKeyBlock *new_ab= NULL; BezTriple *beztn=NULL, *prev=NULL; BezTriple *bezt; int v; @@ -148,6 +191,7 @@ static void add_bezt_to_keyblockslist(ListBase *blocks, FCurve *fcu, int index) beztn= (fcu->bezt + index); /* we need to go through all beztriples, as they may not be in order (i.e. during transform) */ + // TODO: this seems to be a bit of a bottleneck for (v=0, bezt=fcu->bezt; v < fcu->totvert; v++, bezt++) { /* skip if beztriple is current */ if (v != index) { @@ -174,68 +218,119 @@ static void add_bezt_to_keyblockslist(ListBase *blocks, FCurve *fcu, int index) if (IS_EQ(beztn->vec[1][1], beztn->vec[0][1])==0) return; if (IS_EQ(prev->vec[1][1], prev->vec[2][1])==0) return; - /* try to find a keyblock that starts on the previous beztriple - * Note: we can't search from end to try to optimise this as it causes errors there's - * an A ___ B |---| B situation - */ - // FIXME: here there is a bug where we are trying to get the summary for the following channels - // A|--------------|A ______________ B|--------------|B - // A|------------------------------------------------|A - // A|----|A|---|A|-----------------------------------|A - for (ab= blocks->first; ab; ab= ab->next) { - /* check if alter existing block or add new block */ - if (ab->start == prev->vec[1][0]) { - /* set selection status and 'touched' status */ - if (BEZSELECTED(beztn)) ab->sel = SELECT; - ab->modified += 1; - - return; + + /* if there are no blocks already, just add as root */ + if (blocks->root == NULL) { + /* just add this as the root, then call the tree-balancing functions to validate */ + new_ab= bezts_to_new_actkeyblock(prev, beztn); + blocks->root= (DLRBT_Node *)new_ab; + } + else { + ActKeyBlock *ab, *abp=NULL, *abn=NULL; + + /* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there + * Note: we can't search from end to try to optimise this as it causes errors there's + * an A ___ B |---| B situation + */ + // FIXME: here there is a bug where we are trying to get the summary for the following channels + // A|--------------|A ______________ B|--------------|B + // A|------------------------------------------------|A + // A|----|A|---|A|-----------------------------------|A + for (ab= blocks->root; ab; abp= ab, ab= abn) { + /* check if this is a match, or whether we go left or right */ + if (ab->start == prev->vec[1][0]) { + /* set selection status and 'touched' status */ + if (BEZSELECTED(beztn)) ab->sel = SELECT; + ab->modified += 1; + + /* done... no need to insert */ + return; + } + else { + ActKeyBlock **abnp= NULL; + + /* check if go left or right, but if not available, add new node */ + if (ab->start < prev->vec[1][0]) + abnp= &ab->right; + else + abnp= &ab->left; + + /* if this does not exist, add a new node, otherwise continue... */ + if (*abnp == NULL) { + /* add a new node representing this, and attach it to the relevant place */ + new_ab= bezts_to_new_actkeyblock(prev, beztn); + new_ab->parent= ab; + *abnp= new_ab; + break; + } + else + abn= *abnp; + } } - else if (ab->start < prev->vec[1][0]) break; } - /* add new block */ - abn= MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock"); - if (ab) BLI_insertlinkbefore(blocks, ab, abn); - else BLI_addtail(blocks, abn); + /* now, balance the tree taking into account this newly added node */ + BLI_dlrbTree_insert(blocks, (DLRBT_Node *)new_ab); +} + +/* --------- */ + +/* Handle the 'touched' status of ActKeyColumn tree nodes */ +static void set_touched_actkeycolumn (ActKeyColumn *ak) +{ + /* sanity check */ + if (ak == NULL) + return; + + /* deal with self first */ + if (ak->modified) { + ak->modified= 0; + ak->totcurve++; + } - abn->start= prev->vec[1][0]; - abn->end= beztn->vec[1][0]; - abn->val= beztn->vec[1][1]; + /* children */ + set_touched_actkeycolumn(ak->left); + set_touched_actkeycolumn(ak->right); +} + +/* Handle the 'touched' status of ActKeyBlock tree nodes */ +static void set_touched_actkeyblock (ActKeyBlock *ab) +{ + /* sanity check */ + if (ab == NULL) + return; + + /* deal with self first */ + if (ab->modified) { + ab->modified= 0; + ab->totcurve++; + } - if (BEZSELECTED(prev) || BEZSELECTED(beztn)) - abn->sel = SELECT; - else - abn->sel = 0; - abn->modified = 1; + /* children */ + set_touched_actkeyblock(ab->left); + set_touched_actkeyblock(ab->right); } /* *************************** Keyframe Drawing *************************** */ /* helper function - find actkeycolumn that occurs on cframe */ -static ActKeyColumn *cfra_find_actkeycolumn (ListBase *keys, float cframe) +static ActKeyColumn *cfra_find_actkeycolumn (ActKeyColumn *ak, float cframe) { - ActKeyColumn *ak, *ak2; - - if (keys==NULL) + /* sanity checks */ + if (ak == NULL) return NULL; - - /* search from both ends at the same time, and stop if we find match or if both ends meet */ - for (ak=keys->first, ak2=keys->last; ak && ak2; ak=ak->next, ak2=ak2->prev) { - /* return whichever end encounters the frame */ - if (ak->cfra == cframe) - return ak; - if (ak2->cfra == cframe) - return ak2; - - /* no matches on either end, so return NULL */ - if (ak == ak2) - return NULL; - } - return NULL; + /* check if this is a match, or whether it is in some subtree */ + if (cframe < ak->cfra) + return cfra_find_actkeycolumn(ak->left, cframe); + else if (cframe > ak->cfra) + return cfra_find_actkeycolumn(ak->right, cframe); + else + return ak; /* match */ } +/* -------- */ + /* coordinates for diamond shape */ static const float _unit_diamond_shape[4][2] = { {0.0f, 1.0f}, /* top vert */ @@ -306,7 +401,7 @@ void draw_keyframe_shape (float x, float y, float xscale, float hsize, short sel glTranslatef(-x, -y, 0.0f); } -static void draw_keylist(View2D *v2d, ListBase *keys, ListBase *blocks, float ypos) +static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, float ypos) { ActKeyColumn *ak; ActKeyBlock *ab; @@ -323,10 +418,10 @@ static void draw_keylist(View2D *v2d, ListBase *keys, ListBase *blocks, float yp short startCurves, endCurves, totCurves; /* find out how many curves occur at each keyframe */ - ak= cfra_find_actkeycolumn(keys, ab->start); + ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->start); startCurves = (ak)? ak->totcurve: 0; - ak= cfra_find_actkeycolumn(keys, ab->end); + ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->end); endCurves = (ak)? ak->totcurve: 0; /* only draw keyblock if it appears in at all of the keyframes at lowest end */ @@ -382,76 +477,112 @@ static void draw_keylist(View2D *v2d, ListBase *keys, ListBase *blocks, float yp void draw_scene_channel(View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos) { - ListBase keys = {0, 0}; - ListBase blocks = {0, 0}; - - scene_to_keylist(ads, sce, &keys, &blocks); - draw_keylist(v2d, &keys, &blocks, ypos); + DLRBT_Tree keys, blocks; + + BLI_dlrbTree_init(&keys); + BLI_dlrbTree_init(&blocks); + + scene_to_keylist(ads, sce, &keys, &blocks); - BLI_freelistN(&keys); - BLI_freelistN(&blocks); + BLI_dlrbTree_linkedlist_sync(&keys); + BLI_dlrbTree_linkedlist_sync(&blocks); + + draw_keylist(v2d, &keys, &blocks, ypos); + + BLI_dlrbTree_free(&keys); + BLI_dlrbTree_free(&blocks); } void draw_object_channel(View2D *v2d, bDopeSheet *ads, Object *ob, float ypos) { - ListBase keys = {0, 0}; - ListBase blocks = {0, 0}; - - ob_to_keylist(ads, ob, &keys, &blocks); - draw_keylist(v2d, &keys, &blocks, ypos); + DLRBT_Tree keys, blocks; - BLI_freelistN(&keys); - BLI_freelistN(&blocks); + BLI_dlrbTree_init(&keys); + BLI_dlrbTree_init(&blocks); + + ob_to_keylist(ads, ob, &keys, &blocks); + + BLI_dlrbTree_linkedlist_sync(&keys); + BLI_dlrbTree_linkedlist_sync(&blocks); + + draw_keylist(v2d, &keys, &blocks, ypos); + + BLI_dlrbTree_free(&keys); + BLI_dlrbTree_free(&blocks); } void draw_fcurve_channel(View2D *v2d, AnimData *adt, FCurve *fcu, float ypos) { - ListBase keys = {0, 0}; - ListBase blocks = {0, 0}; - - fcurve_to_keylist(adt, fcu, &keys, &blocks); - draw_keylist(v2d, &keys, &blocks, ypos); + DLRBT_Tree keys, blocks; + + BLI_dlrbTree_init(&keys); + BLI_dlrbTree_init(&blocks); + + fcurve_to_keylist(adt, fcu, &keys, &blocks); - BLI_freelistN(&keys); - BLI_freelistN(&blocks); + BLI_dlrbTree_linkedlist_sync(&keys); + BLI_dlrbTree_linkedlist_sync(&blocks); + + draw_keylist(v2d, &keys, &blocks, ypos); + + BLI_dlrbTree_free(&keys); + BLI_dlrbTree_free(&blocks); } void draw_agroup_channel(View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos) { - ListBase keys = {0, 0}; - ListBase blocks = {0, 0}; - - agroup_to_keylist(adt, agrp, &keys, &blocks); - draw_keylist(v2d, &keys, &blocks, ypos); + DLRBT_Tree keys, blocks; + + BLI_dlrbTree_init(&keys); + BLI_dlrbTree_init(&blocks); + + agroup_to_keylist(adt, agrp, &keys, &blocks); + + BLI_dlrbTree_linkedlist_sync(&keys); + BLI_dlrbTree_linkedlist_sync(&blocks); - BLI_freelistN(&keys); - BLI_freelistN(&blocks); + draw_keylist(v2d, &keys, &blocks, ypos); + + BLI_dlrbTree_free(&keys); + BLI_dlrbTree_free(&blocks); } void draw_action_channel(View2D *v2d, AnimData *adt, bAction *act, float ypos) { - ListBase keys = {0, 0}; - ListBase blocks = {0, 0}; - - action_to_keylist(adt, act, &keys, &blocks); - draw_keylist(v2d, &keys, &blocks, ypos); + DLRBT_Tree keys, blocks; + + BLI_dlrbTree_init(&keys); + BLI_dlrbTree_init(&blocks); + + action_to_keylist(adt, act, &keys, &blocks); - BLI_freelistN(&keys); - BLI_freelistN(&blocks); + BLI_dlrbTree_linkedlist_sync(&keys); + BLI_dlrbTree_linkedlist_sync(&blocks); + + draw_keylist(v2d, &keys, &blocks, ypos); + + BLI_dlrbTree_free(&keys); + BLI_dlrbTree_free(&blocks); } void draw_gpl_channel(View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos) { - ListBase keys = {0, 0}; + DLRBT_Tree keys; + + BLI_dlrbTree_init(&keys); - gpl_to_keylist(ads, gpl, &keys, NULL); - draw_keylist(v2d, &keys, NULL, ypos); - BLI_freelistN(&keys); + gpl_to_keylist(ads, gpl, &keys, NULL); + + BLI_dlrbTree_linkedlist_sync(&keys); + + draw_keylist(v2d, &keys, NULL, ypos); + + BLI_dlrbTree_free(&keys); } /* *************************** Keyframe List Conversions *************************** */ -void scene_to_keylist(bDopeSheet *ads, Scene *sce, ListBase *keys, ListBase *blocks) +void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree *blocks) { if (sce) { AnimData *adt; @@ -483,7 +614,7 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, ListBase *keys, ListBase *blo } } -void ob_to_keylist(bDopeSheet *ads, Object *ob, ListBase *keys, ListBase *blocks) +void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *blocks) { Key *key= ob_get_key(ob); @@ -508,12 +639,9 @@ void ob_to_keylist(bDopeSheet *ads, Object *ob, ListBase *keys, ListBase *blocks } } - -void fcurve_to_keylist(AnimData *adt, FCurve *fcu, ListBase *keys, ListBase *blocks) +void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree *blocks) { BezTriple *bezt; - ActKeyColumn *ak, *ak2; - ActKeyBlock *ab, *ab2; int v; if (fcu && fcu->totvert && fcu->bezt) { @@ -525,51 +653,23 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, ListBase *keys, ListBase *blo bezt= fcu->bezt; for (v=0; v < fcu->totvert; v++, bezt++) { - /* only if keyframe is in range (optimisation) */ - add_bezt_to_keycolumnslist(keys, bezt); - if (blocks) add_bezt_to_keyblockslist(blocks, fcu, v); + add_bezt_to_keycolumns_list(keys, bezt); + if (blocks) add_bezt_to_keyblocks_list(blocks, fcu, v); } /* update the number of curves that elements have appeared in */ - if (keys) { - for (ak=keys->first, ak2=keys->last; ak && ak2; ak=ak->next, ak2=ak2->prev) { - if (ak->modified) { - ak->modified = 0; - ak->totcurve += 1; - } - - if (ak == ak2) - break; - - if (ak2->modified) { - ak2->modified = 0; - ak2->totcurve += 1; - } - } - } - if (blocks) { - for (ab=blocks->first, ab2=blocks->last; ab && ab2; ab=ab->next, ab2=ab2->prev) { - if (ab->modified) { - ab->modified = 0; - ab->totcurve += 1; - } - - if (ab == ab2) - break; - - if (ab2->modified) { - ab2->modified = 0; - ab2->totcurve += 1; - } - } - } + // FIXME: this is broken with the new tree structure for now... + if (keys) + set_touched_actkeycolumn(keys->root); + if (blocks) + set_touched_actkeyblock(blocks->root); /* unapply NLA-mapping if applicable */ ANIM_nla_mapping_apply_fcurve(adt, fcu, 1, 1); } } -void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, ListBase *keys, ListBase *blocks) +void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, DLRBT_Tree *blocks) { FCurve *fcu; @@ -581,7 +681,7 @@ void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, ListBase *keys, ListBa } } -void action_to_keylist(AnimData *adt, bAction *act, ListBase *keys, ListBase *blocks) +void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, DLRBT_Tree *blocks) { FCurve *fcu; @@ -594,7 +694,7 @@ void action_to_keylist(AnimData *adt, bAction *act, ListBase *keys, ListBase *bl } -void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, ListBase *keys, ListBase *blocks) +void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, DLRBT_Tree *keys, DLRBT_Tree *blocks) { bGPDframe *gpf; ActKeyColumn *ak; @@ -603,7 +703,7 @@ void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, ListBase *keys, ListBase *b /* loop over frames, converting directly to 'keyframes' (should be in order too) */ for (gpf= gpl->frames.first; gpf; gpf= gpf->next) { ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn"); - BLI_addtail(keys, ak); + BLI_addtail((ListBase *)keys, ak); ak->cfra= (float)gpf->framenum; ak->modified = 1; diff --git a/source/blender/editors/armature/poselib.c b/source/blender/editors/armature/poselib.c index 93611a30bd8..d0a99e4ad13 100644 --- a/source/blender/editors/armature/poselib.c +++ b/source/blender/editors/armature/poselib.c @@ -37,6 +37,7 @@ #include "BLI_arithb.h" #include "BLI_blenlib.h" #include "BLI_dynstr.h" +#include "BLI_dlrbTree.h" #include "DNA_listBase.h" #include "DNA_anim_types.h" @@ -216,7 +217,7 @@ bAction *poselib_validate (Object *ob) // TODO: operatorfy me! void poselib_validate_act (bAction *act) { - ListBase keys = {NULL, NULL}; + DLRBT_Tree keys = {NULL, NULL}; ActKeyColumn *ak; TimeMarker *marker, *markern; @@ -227,7 +228,9 @@ void poselib_validate_act (bAction *act) } /* determine which frames have keys */ + BLI_dlrbTree_init(&keys); action_to_keylist(NULL, act, &keys, NULL); + BLI_dlrbTree_linkedlist_sync(&keys); /* for each key, make sure there is a correspnding pose */ for (ak= keys.first; ak; ak= ak->next) { diff --git a/source/blender/editors/include/ED_keyframes_draw.h b/source/blender/editors/include/ED_keyframes_draw.h index 63adcf39c12..e940aaed36e 100644 --- a/source/blender/editors/include/ED_keyframes_draw.h +++ b/source/blender/editors/include/ED_keyframes_draw.h @@ -17,12 +17,12 @@ * 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) 2001-2002 by NaN Holding BV. + * The Original Code is Copyright (C) (C) 2009 Blender Foundation, Joshua Leung * All rights reserved. * * The Original Code is: all of this file. * - * Contributor(s): none yet. + * Contributor(s): Joshua Leung (full recode) * * ***** END GPL LICENSE BLOCK ***** */ @@ -41,13 +41,23 @@ struct ListBase; struct bGPDlayer; struct Scene; struct View2D; +struct DLRBT_Tree; /* ****************************** Base Structs ****************************** */ /* Keyframe Column Struct */ typedef struct ActKeyColumn { + /* ListBase linkage */ struct ActKeyColumn *next, *prev; - short sel, handle_type; + + /* sorting-tree linkage */ + struct ActKeyColumn *left, *right; /* 'children' of this node, less than and greater than it (respectively) */ + struct ActKeyColumn *parent; /* parent of this node in the tree */ + char tree_col; /* DLRB_BLACK or DLRB_RED */ + + /* keyframe info */ + char sel; + short handle_type; float cfra; /* only while drawing - used to determine if long-keyframe needs to be drawn */ @@ -57,8 +67,17 @@ typedef struct ActKeyColumn { /* 'Long Keyframe' Struct */ typedef struct ActKeyBlock { + /* ListBase linkage */ struct ActKeyBlock *next, *prev; - short sel, handle_type; + + /* sorting-tree linkage */ + struct ActKeyBlock *left, *right; /* 'children' of this node, less than and greater than it (respectively) */ + struct ActKeyBlock *parent; /* parent of this node in the tree */ + char tree_col; /* DLRB_BLACK or DLRB_RED */ + + /* key-block info */ + char sel; + short handle_type; float val; float start, end; @@ -67,7 +86,6 @@ typedef struct ActKeyBlock { short totcurve; } ActKeyBlock; - /* *********************** Keyframe Drawing ****************************** */ /* options for keyframe shape drawing */ @@ -94,12 +112,12 @@ void draw_scene_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Scene void draw_gpl_channel(struct View2D *v2d, struct bDopeSheet *ads, struct bGPDlayer *gpl, float ypos); /* Keydata Generation */ -void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, ListBase *keys, ListBase *blocks); -void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, ListBase *keys, ListBase *blocks); -void action_to_keylist(struct AnimData *adt, struct bAction *act, ListBase *keys, ListBase *blocks); -void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, ListBase *keys, ListBase *blocks); -void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, ListBase *keys, ListBase *blocks); -void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, ListBase *keys, ListBase *blocks); +void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); #endif /* ED_KEYFRAMES_DRAW_H */ 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); diff --git a/source/blender/editors/space_nla/nla_draw.c b/source/blender/editors/space_nla/nla_draw.c index 8d56670a149..9e60651081f 100644 --- a/source/blender/editors/space_nla/nla_draw.c +++ b/source/blender/editors/space_nla/nla_draw.c @@ -56,6 +56,7 @@ #include "BLI_blenlib.h" #include "BLI_arithb.h" #include "BLI_rand.h" +#include "BLI_dlrbTree.h" #include "BKE_animsys.h" #include "BKE_fcurve.h" @@ -127,13 +128,15 @@ static void nla_action_get_color (AnimData *adt, bAction *act, float color[4]) /* draw the keyframes in the specified Action */ static void nla_action_draw_keyframes (AnimData *adt, bAction *act, View2D *v2d, float y, float ymin, float ymax) { - ListBase keys = {NULL, NULL}; + DLRBT_Tree keys; ActKeyColumn *ak; float xscale, f1, f2; float color[4]; /* get a list of the keyframes with NLA-scaling applied */ + BLI_dlrbTree_init(&keys); action_to_keylist(adt, act, &keys, NULL); + BLI_dlrbTree_linkedlist_sync(&keys); if ELEM(NULL, act, keys.first) return; @@ -165,7 +168,7 @@ static void nla_action_draw_keyframes (AnimData *adt, bAction *act, View2D *v2d, draw_keyframe_shape(ak->cfra, y, xscale, 3.0f, 0, KEYFRAME_SHAPE_FRAME); /* free icons */ - BLI_freelistN(&keys); + BLI_dlrbTree_free(&keys); } /* Strips (Proper) ---------------------- */ diff --git a/source/blender/editors/space_view3d/drawarmature.c b/source/blender/editors/space_view3d/drawarmature.c index ec3b716e616..b698b404825 100644 --- a/source/blender/editors/space_view3d/drawarmature.c +++ b/source/blender/editors/space_view3d/drawarmature.c @@ -52,6 +52,7 @@ #include "BLI_blenlib.h" #include "BLI_arithb.h" +#include "BLI_dlrbTree.h" #include "BKE_animsys.h" #include "BKE_action.h" @@ -2026,7 +2027,7 @@ static void draw_pose_paths(Scene *scene, View3D *v3d, RegionView3D *rv3d, Objec bArmature *arm= ob->data; bPoseChannel *pchan; ActKeyColumn *ak; - ListBase keys; + DLRBT_Tree keys; float *fp, *fp_start; int a, stepsize; int sfra, efra, len; @@ -2168,12 +2169,14 @@ static void draw_pose_paths(Scene *scene, View3D *v3d, RegionView3D *rv3d, Objec /* Keyframes - dots and numbers */ if (arm->pathflag & ARM_PATH_KFRAS) { /* build list of all keyframes in active action for pchan */ - keys.first = keys.last = NULL; + BLI_dlrbTree_init(&keys); if (adt) { bActionGroup *agrp= action_groups_find_named(adt->action, pchan->name); - if (agrp) + if (agrp) { agroup_to_keylist(adt, agrp, &keys, NULL); + BLI_dlrbTree_linkedlist_sync(&keys); + } } /* Draw slightly-larger yellow dots at each keyframe */ @@ -2205,7 +2208,7 @@ static void draw_pose_paths(Scene *scene, View3D *v3d, RegionView3D *rv3d, Objec } } - BLI_freelistN(&keys); + BLI_dlrbTree_free(&keys); } } } @@ -2319,7 +2322,7 @@ static void draw_ghost_poses_keys(Scene *scene, View3D *v3d, RegionView3D *rv3d, bAction *act= (adt) ? adt->action : NULL; bArmature *arm= ob->data; bPose *posen, *poseo; - ListBase keys= {NULL, NULL}; + DLRBT_Tree keys; ActKeyColumn *ak, *akn; float start, end, range, colfac, i; int cfrao, flago; @@ -2330,13 +2333,16 @@ static void draw_ghost_poses_keys(Scene *scene, View3D *v3d, RegionView3D *rv3d, return; /* get keyframes - then clip to only within range */ + BLI_dlrbTree_init(&keys); action_to_keylist(adt, act, &keys, NULL); + BLI_dlrbTree_linkedlist_sync(&keys); + range= 0; for (ak= keys.first; ak; ak= akn) { akn= ak->next; if ((ak->cfra < start) || (ak->cfra > end)) - BLI_freelinkN(&keys, ak); + BLI_freelinkN((ListBase *)&keys, ak); else range++; } @@ -2374,7 +2380,7 @@ static void draw_ghost_poses_keys(Scene *scene, View3D *v3d, RegionView3D *rv3d, if (v3d->zbuf) glEnable(GL_DEPTH_TEST); ghost_poses_tag_unselected(ob, 1); /* unhide unselected bones if need be */ - BLI_freelistN(&keys); + BLI_dlrbTree_free(&keys); free_pose(posen); /* restore */ |