diff options
author | Joshua Leung <aligorith@gmail.com> | 2009-11-15 14:20:44 +0300 |
---|---|---|
committer | Joshua Leung <aligorith@gmail.com> | 2009-11-15 14:20:44 +0300 |
commit | 6468f21ddf25298f5b9d1c52955e185b368f496c (patch) | |
tree | a0401bd947c2f4b54a3cd797c33cd1dbcdd9f56e /source/blender | |
parent | 698086dfb1b3d5796115afed238b6d9225576ad8 (diff) |
Red-Black Tree Code Cleanups:
Added some more methods for the Red-Black Tree implementation in Blender (used for runtime viewing and searching of keyframes) which abstract away some of the lower-level handling of the BST (i.e. adding nodes without balancing and searching for nodes).
Also, improved the implementation of the jump next/prev keyframe operator so that it pops up an error message when the last keyframe in whatever direction is encountered.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_dlrbTree.h | 67 | ||||
-rw-r--r-- | source/blender/blenlib/intern/DLRB_tree.c | 237 | ||||
-rw-r--r-- | source/blender/editors/animation/keyframes_draw.c | 162 | ||||
-rw-r--r-- | source/blender/editors/armature/poseSlide.c | 6 | ||||
-rw-r--r-- | source/blender/editors/include/ED_keyframes_draw.h | 26 | ||||
-rw-r--r-- | source/blender/editors/screen/screen_ops.c | 24 |
6 files changed, 390 insertions, 132 deletions
diff --git a/source/blender/blenlib/BLI_dlrbTree.h b/source/blender/blenlib/BLI_dlrbTree.h index a17cbbd1993..bced738b4e7 100644 --- a/source/blender/blenlib/BLI_dlrbTree.h +++ b/source/blender/blenlib/BLI_dlrbTree.h @@ -54,10 +54,10 @@ typedef struct DLRBT_Node { } DLRBT_Node; /* Red/Black defines for tree_col */ -enum eDLRBT_Colors { +typedef enum eDLRBT_Colors { DLRBT_BLACK= 0, DLRBT_RED, -}; +} eDLRBT_Colors; /* -------- */ @@ -70,9 +70,30 @@ typedef struct DLRBT_Tree { void *root; /* this should be based on DLRBT_Node-s */ } DLRBT_Tree; +/* Callback Types --------------------------------- */ + +/* return -1, 0, 1 for whether the given data is less than, equal to, or greater than the given node + * - node: <DLRBT_Node> the node to compare to + * - data: pointer to the relevant data or values stored in the bitpattern dependant on the function + */ +typedef short (*DLRBT_Comparator_FP)(void *node, void *data); + +/* return a new node instance wrapping the given data + * - data: pointer to the relevant data to create a subclass of node from + */ +typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data); + +/* update an existing node instance accordingly to be in sync with the given data * + * - node: <DLRBT_Node> the node to update + * - data: pointer to the relevant data or values stored in the bitpattern dependant on the function + */ +typedef void (*DLRBT_NUpdate_FP)(void *node, void *data); + /* ********************************************** */ /* Public API */ +/* ADT Management ------------------------------- */ + /* Create a new tree, and initialise as necessary */ DLRBT_Tree *BLI_dlrbTree_new(void); @@ -86,16 +107,52 @@ void BLI_dlrbTree_free(DLRBT_Tree *tree); void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree); +/* Searching ------------------------------------ */ -/* Balance the tree after the given element has been added to it - * (using custom code, in the Binary Tree way). +/* Find the node which matches or is the closest to the requested node */ +DLRBT_Node *BLI_dlrbTree_search(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + +/* Find the node which exactly matches the required data */ +DLRBT_Node *BLI_dlrbTree_search_exact(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + +/* Find the node which occurs immediately before the best matching node */ +DLRBT_Node *BLI_dlrbTree_search_prev(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + +/* Find the node which occurs immediately after the best matching node */ +DLRBT_Node *BLI_dlrbTree_search_next(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + + +/* Check whether there is a node matching the requested node */ +short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + + +/* Node Operations (Managed) --------------------- */ +/* These methods automate the process of adding/removing nodes from the BST, + * using the supplied data and callbacks */ -void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node); + +/* Add the given data to the tree, and return the node added */ +// NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned +DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, + DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data); + /* 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); +/* Node Operations (Manual) --------------------- */ +/* These methods require custom code for creating BST nodes and adding them to the + * tree in special ways, such that the node can then be balanced. + * + * It is recommended that these methods are only used where the other method is too cumbersome... + */ + +/* Balance the tree after the given node has been added to it + * (using custom code, in the Binary Tree way). + */ +void BLI_dlrbTree_insert(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 index af9774c6afd..8eb743e282c 100644 --- a/source/blender/blenlib/intern/DLRB_tree.c +++ b/source/blender/blenlib/intern/DLRB_tree.c @@ -130,6 +130,155 @@ void BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree) } /* *********************************************** */ +/* Tree Search Utilities */ + +/* Find the node which matches or is the closest to the requested node */ +DLRBT_Node *BLI_dlrbTree_search (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +{ + DLRBT_Node *node = (tree) ? tree->root : NULL; + short found= 0; + + /* check that there is a comparator to use */ + // TODO: if no comparator is supplied, try using the one supplied with the tree... + if (cmp_cb == NULL) + return NULL; + + /* iteratively perform this search */ + while (node && found==0) + { + /* check if traverse further or not + * NOTE: it is assumed that the values will be unit values only + */ + switch (cmp_cb(node, search_data)) { + case -1: /* data less than node */ + if (node->left) + node= node->left; + else + found= 1; + break; + + case 1: /* data greater than node */ + if (node->right) + node= node->right; + else + found= 1; + break; + + default: /* data equals node */ + found= 1; + break; + } + } + + /* return the nearest matching node */ + return node; +} + +/* Find the node which exactly matches the required data */ +DLRBT_Node *BLI_dlrbTree_search_exact (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +{ + DLRBT_Node *node = (tree) ? tree->root : NULL; + short found= 0; + + /* check that there is a comparator to use */ + // TODO: if no comparator is supplied, try using the one supplied with the tree... + if (cmp_cb == NULL) + return NULL; + + /* iteratively perform this search */ + while (node && found==0) + { + /* check if traverse further or not + * NOTE: it is assumed that the values will be unit values only + */ + switch (cmp_cb(node, search_data)) { + case -1: /* data less than node */ + if (node->left) + node= node->left; + else + found= -1; + break; + + case 1: /* data greater than node */ + if (node->right) + node= node->right; + else + found= -1; + break; + + default: /* data equals node */ + found= 1; + break; + } + } + + /* return the nearest matching node */ + return (found == 1) ? (node) : (NULL); +} + +/* Find the node which occurs immediately before the best matching node */ +DLRBT_Node *BLI_dlrbTree_search_prev (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +{ + DLRBT_Node *node; + + /* check that there is a comparator to use */ + // TODO: if no comparator is supplied, try using the one supplied with the tree... + if (cmp_cb == NULL) + return NULL; + + /* get the node which best matches this description */ + node= BLI_dlrbTree_search(tree, cmp_cb, search_data); + + if (node) { + /* if the item we're searching for is greater than the node found, we've found the match */ + if (cmp_cb(node, search_data) > 0) + return node; + + /* return the previous node otherwise */ + // NOTE: what happens if there is no previous node? + return node->prev; + } + + /* nothing matching was found */ + return NULL; +} + +/* Find the node which occurs immediately after the best matching node */ +DLRBT_Node *BLI_dlrbTree_search_next (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +{ + DLRBT_Node *node; + + /* check that there is a comparator to use */ + // TODO: if no comparator is supplied, try using the one supplied with the tree... + if (cmp_cb == NULL) + return NULL; + + /* get the node which best matches this description */ + node= BLI_dlrbTree_search(tree, cmp_cb, search_data); + + if (node) { + /* if the item we're searching for is less than the node found, we've found the match */ + if (cmp_cb(node, search_data) < 0) + return node; + + /* return the previous node otherwise */ + // NOTE: what happens if there is no previous node? + return node->next; + } + + /* nothing matching was found */ + return NULL; +} + + +/* Check whether there is a node matching the requested node */ +short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +{ + /* check if an exact search throws up anything... */ + return (BLI_dlrbTree_search_exact(tree, cmp_cb, search_data) != NULL); +} + +/* *********************************************** */ /* Tree Relationships Utilities */ /* get the 'grandparent' - the parent of the parent - of the given node */ @@ -161,6 +310,7 @@ static DLRBT_Node *get_uncle (DLRBT_Node *node) /* *********************************************** */ /* Tree Rotation Utilities */ +/* make right child of 'root' the new root */ static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root) { DLRBT_Node **root_slot, *pivot; @@ -194,6 +344,7 @@ static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root) *root_slot= pivot; } +/* make the left child of the 'root' the new root */ static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root) { DLRBT_Node **root_slot, *pivot; @@ -332,7 +483,7 @@ static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) /* 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) +void BLI_dlrbTree_insert (DLRBT_Tree *tree, DLRBT_Node *node) { /* sanity checks */ if ((tree == NULL) || (node == NULL)) @@ -345,6 +496,90 @@ void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node) insert_check_1(tree, node); } +/* ----- */ + +/* Add the given data to the tree, and return the node added */ +// NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned +DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, + DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data) +{ + DLRBT_Node *parNode, *node=NULL; + short new_node = 0; + + /* sanity checks */ + if (tree == NULL) + return NULL; + + // TODO: if no comparator is supplied, try using the one supplied with the tree... + if (cmp_cb == NULL) + return NULL; + // TODO: if no allocator is supplied, try using the one supplied with the tree... + if (new_cb == NULL) + return NULL; + // TODO: if no updater is supplied, try using the one supplied with the tree... + + /* try to find the nearest node to this one */ + parNode= BLI_dlrbTree_search(tree, cmp_cb, data); + + /* add new node to the BST in the 'standard way' as appropriate + * NOTE: we do not support duplicates in our tree... + */ + if (parNode) { + /* check how this new node compares with the existing ones + * NOTE: it is assumed that the values will be unit values only + */ + switch (cmp_cb(parNode, data)) { + case -1: /* add new node as left child */ + { + node= new_cb(data); + new_node= 1; + + parNode->left= node; + node->parent= parNode; + } + break; + + case 1: /* add new node as right child */ + { + node= new_cb(data); + new_node= 1; + + parNode->right= node; + node->parent= parNode; + } + break; + + default: /* update the duplicate node as appropriate */ + { + if (update_cb) + update_cb(parNode, data); + } + break; + } + } + else { + /* no nodes in the tree yet... add a new node as the root */ + node= new_cb(data); + new_node= 1; + + tree->root= node; + } + + /* if a new node was added, it should be tagged as red, and then balanced as appropriate */ + if (new_node) { + /* tag this new node as being 'red' */ + node->tree_col= DLRBT_RED; + + /* perform BST balancing steps: + * start from case 1, an trek through the tail-recursive insertion checks + */ + insert_check_1(tree, node); + } + + /* return the node added */ + return node; +} + /* *********************************************** */ /* Remove */ diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c index fb02a88ea2b..b3d2b12a5a0 100644 --- a/source/blender/editors/animation/keyframes_draw.c +++ b/source/blender/editors/animation/keyframes_draw.c @@ -92,10 +92,41 @@ /* *************************** Keyframe Processing *************************** */ -/* Create a ActKeyColumn from a BezTriple */ -static ActKeyColumn *bezt_to_new_actkeycolumn(BezTriple *bezt) +/* Comparator callback used for ActKeyColumns and cframe float-value pointer */ +short compare_ak_cfraPtr (void *node, void *data) +{ + ActKeyColumn *ak= (ActKeyColumn *)node; + float *cframe= data; + + if (*cframe < ak->cfra) + return -1; + else if (*cframe > ak->cfra) + return 1; + else + return 0; +} + +/* .... */ + +/* Comparator callback used for ActKeyColumns and BezTriple */ +static short compare_ak_bezt (void *node, void *data) +{ + ActKeyColumn *ak= (ActKeyColumn *)node; + BezTriple *bezt= (BezTriple *)data; + + if (bezt->vec[1][0] < ak->cfra) + return -1; + else if (bezt->vec[1][0] > ak->cfra) + return 1; + else + return 0; +} + +/* New node callback used for building ActKeyColumns from BezTriples */ +static DLRBT_Node *nalloc_ak_bezt (void *data) { ActKeyColumn *ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn"); + BezTriple *bezt= (BezTriple *)data; /* store settings based on state of BezTriple */ ak->cfra= bezt->vec[1][0]; @@ -105,67 +136,33 @@ static ActKeyColumn *bezt_to_new_actkeycolumn(BezTriple *bezt) /* set 'modified', since this is used to identify long keyframes */ ak->modified = 1; - return ak; + return (DLRBT_Node *)ak; } -/* Add the given BezTriple to the given 'list' of Keyframes */ -static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt) +/* Node updater callback used for building ActKeyColumns from BezTriples */ +static void nupdate_ak_bezt (void *node, void *data) { - ActKeyColumn *new_ak=NULL; + ActKeyColumn *ak= (ActKeyColumn *)node; + BezTriple *bezt= (BezTriple *)data; - if ELEM(NULL, keys, bezt) return; + /* set selection status and 'touched' status */ + if (BEZSELECTED(bezt)) ak->sel = SELECT; + ak->modified += 1; - /* 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; - - /* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */ - if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME) - ak->key_type= BEZT_KEYTYPE_KEYFRAME; - - /* 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; - } - } - } - - /* now, balance the tree taking into account this newly added node */ - BLI_dlrbTree_insert(keys, (DLRBT_Node *)new_ak); + /* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */ + if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME) + ak->key_type= BEZT_KEYTYPE_KEYFRAME; +} + +/* --------------- */ + +/* Add the given BezTriple to the given 'list' of Keyframes */ +static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt) +{ + if ELEM(NULL, keys, bezt) + return; + else + BLI_dlrbTree_add(keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt); } @@ -317,47 +314,6 @@ static void set_touched_actkeyblock (ActKeyBlock *ab) /* *************************** Keyframe Drawing *************************** */ -/* helper function - find actkeycolumn that occurs on cframe */ -ActKeyColumn *cfra_find_actkeycolumn (ActKeyColumn *ak, float cframe) -{ - /* sanity checks */ - if (ak == 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 */ -} - -/* helper function - find actkeycolumn that occurs on cframe, or the nearest one if not found */ -// FIXME: this is buggy... next() is ignored completely... -ActKeyColumn *cfra_find_nearest_next_ak (ActKeyColumn *ak, float cframe, short next) -{ - ActKeyColumn *akn= NULL; - - /* sanity checks */ - if (ak == NULL) - return NULL; - - /* check if this is a match, or whether it is in some subtree */ - if (cframe < ak->cfra) - akn= cfra_find_nearest_next_ak(ak->left, cframe, next); - else if (cframe > ak->cfra) - akn= cfra_find_nearest_next_ak(ak->right, cframe, next); - - /* if no match found (or found match), just use the current one */ - if (akn == NULL) - return ak; - else - return akn; -} - -/* -------- */ - /* coordinates for diamond shape */ static const float _unit_diamond_shape[4][2] = { {0.0f, 1.0f}, /* top vert */ @@ -471,10 +427,10 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa short startCurves, endCurves, totCurves; /* find out how many curves occur at each keyframe */ - ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->start); + ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->start); startCurves = (ak)? ak->totcurve: 0; - ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->end); + ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->end); endCurves = (ak)? ak->totcurve: 0; /* only draw keyblock if it appears in at all of the keyframes at lowest end */ @@ -676,7 +632,6 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree if ((sce->adt) && !(filterflag & ADS_FILTER_NOSCE)) { adt= sce->adt; - // TODO: when we adapt NLA system, this needs to be the NLA-scaled version if (adt->action) action_to_keylist(adt, adt->action, keys, blocks); } @@ -685,7 +640,6 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree if ((sce->world) && (sce->world->adt) && !(filterflag & ADS_FILTER_NOWOR)) { adt= sce->world->adt; - // TODO: when we adapt NLA system, this needs to be the NLA-scaled version if (adt->action) action_to_keylist(adt, adt->action, keys, blocks); } @@ -694,7 +648,6 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree if ((sce->nodetree) && (sce->nodetree->adt) && !(filterflag & ADS_FILTER_NONTREE)) { adt= sce->nodetree->adt; - // TODO: when we adapt NLA system, this needs to be the NLA-scaled version if (adt->action) action_to_keylist(adt, adt->action, keys, blocks); } @@ -810,7 +763,6 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree } /* update the number of curves that elements have appeared in */ - // FIXME: this is broken with the new tree structure for now... if (keys) set_touched_actkeycolumn(keys->root); if (blocks) diff --git a/source/blender/editors/armature/poseSlide.c b/source/blender/editors/armature/poseSlide.c index e5d334e4d06..eb15d00c8ce 100644 --- a/source/blender/editors/armature/poseSlide.c +++ b/source/blender/editors/armature/poseSlide.c @@ -614,12 +614,12 @@ static int pose_slide_invoke_common (bContext *C, wmOperator *op, tPoseSlideOp * ActKeyColumn *ak; /* firstly, check if the current frame is a keyframe... */ - ak= cfra_find_actkeycolumn(pso->keys.root, pso->cframe); + ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(&pso->keys, compare_ak_cfraPtr, &pso->cframe); if (ak == NULL) { /* current frame is not a keyframe, so search */ - ActKeyColumn *pk= cfra_find_nearest_next_ak(pso->keys.root, pso->cframe, 0); - ActKeyColumn *nk= cfra_find_nearest_next_ak(pso->keys.root, pso->cframe, 1); + ActKeyColumn *pk= (ActKeyColumn *)BLI_dlrbTree_search_prev(&pso->keys, compare_ak_cfraPtr, &pso->cframe); + ActKeyColumn *nk= (ActKeyColumn *)BLI_dlrbTree_search_next(&pso->keys, compare_ak_cfraPtr, &pso->cframe); /* check if we found good keyframes */ if ((pk == nk) && (pk != NULL)) { diff --git a/source/blender/editors/include/ED_keyframes_draw.h b/source/blender/editors/include/ED_keyframes_draw.h index 699502eb9eb..8002918b870 100644 --- a/source/blender/editors/include/ED_keyframes_draw.h +++ b/source/blender/editors/include/ED_keyframes_draw.h @@ -104,27 +104,43 @@ void draw_keyframe_shape(float x, float y, float xscale, float hsize, short sel, /* ******************************* Methods ****************************** */ -/* Channel Drawing */ +/* Channel Drawing ------------------ */ +/* F-Curve */ void draw_fcurve_channel(struct View2D *v2d, struct AnimData *adt, struct FCurve *fcu, float ypos); +/* Action Group Summary */ void draw_agroup_channel(struct View2D *v2d, struct AnimData *adt, struct bActionGroup *agrp, float ypos); +/* Action Summary */ void draw_action_channel(struct View2D *v2d, struct AnimData *adt, struct bAction *act, float ypos); +/* Object Summary */ void draw_object_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Object *ob, float ypos); +/* Scene Summary */ void draw_scene_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Scene *sce, float ypos); +/* DopeSheet Summary */ void draw_summary_channel(struct View2D *v2d, struct bAnimContext *ac, float ypos); +/* Grease Pencil Layer */ +// XXX not restored void draw_gpl_channel(struct View2D *v2d, struct bDopeSheet *ads, struct bGPDlayer *gpl, float ypos); -/* Keydata Generation */ +/* Keydata Generation --------------- */ +/* F-Curve */ void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +/* Action Group */ void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +/* Action */ void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +/* Object */ void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +/* Scene */ void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +/* DopeSheet Summary */ void summary_to_keylist(struct bAnimContext *ac, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); +/* Grease Pencil Layer */ +// XXX not restored void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks); -/* Keyframe Finding */ -ActKeyColumn *cfra_find_actkeycolumn(ActKeyColumn *ak, float cframe); -ActKeyColumn *cfra_find_nearest_next_ak(ActKeyColumn *ak, float cframe, short next); +/* ActKeyColumn API ---------------- */ +/* Comparator callback used for ActKeyColumns and cframe float-value pointer */ +short compare_ak_cfraPtr(void *node, void *data); #endif /* ED_KEYFRAMES_DRAW_H */ diff --git a/source/blender/editors/screen/screen_ops.c b/source/blender/editors/screen/screen_ops.c index f90c1513116..6f0faf9d808 100644 --- a/source/blender/editors/screen/screen_ops.c +++ b/source/blender/editors/screen/screen_ops.c @@ -1468,6 +1468,7 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op) Object *ob= CTX_data_active_object(C); DLRBT_Tree keys; ActKeyColumn *ak; + float cfra= (scene)? (float)(CFRA) : 0.0f; short next= RNA_boolean_get(op->ptr, "next"); /* sanity checks */ @@ -1486,21 +1487,18 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op) /* build linked-list for searching */ BLI_dlrbTree_linkedlist_sync(&keys); - /* find nearest keyframe in the right direction */ - ak= cfra_find_nearest_next_ak(keys.root, (float)scene->r.cfra, next); + /* find matching keyframe in the right direction */ + if (next) + ak= (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfra); + else + ak= (ActKeyColumn *)BLI_dlrbTree_search_prev(&keys, compare_ak_cfraPtr, &cfra); /* set the new frame (if keyframe found) */ - if (ak) { - if (next && ak->next) - scene->r.cfra= (int)ak->next->cfra; - else if (!next && ak->prev) - scene->r.cfra= (int)ak->prev->cfra; - else { - printf("ERROR: no suitable keyframe found. Using %f as new frame \n", ak->cfra); - scene->r.cfra= (int)ak->cfra; // XXX - } - } - + if (ak) + CFRA= (int)ak->cfra; + else + BKE_report(op->reports, RPT_ERROR, "No more keyframes to jump to in this direction"); + /* free temp stuff */ BLI_dlrbTree_free(&keys); |