From 60cfdf080929aca61c37439b601b1ef85d51391a Mon Sep 17 00:00:00 2001 From: Jeroen Bakker Date: Fri, 10 Sep 2021 13:27:26 +0200 Subject: Anim: Keylist drawing optimization by using arrays. Change data structure of keylists. Reducing the balancing overhead and therefore increases performance. | **Function** | **Master** | **Patch** | |`draw_summary_channel`| 0.202105s| 0.083874s | When adding items to the keylist it will store it in a linked list. This linked list is accompanied with the length (key_len) and a `last_accessed_column`. last_accessed_column is a cursor that improve the performance when adding new items as they are mostly ordered by frame numbers. last_accessed_column is reset when a new fcurve/mask/... is added to the keylist. Before searching or array access. the listbase needs to be converted to an array. `ED_keylist_prepare_for_direct_access`. After that the caller can use `ED_keylist_find_*` or `ED_keylist_array*` functions. The internal array can also be accessed via the `ED_keylist_listbase` function. The items inside the array link to the previous/next item in the list. Reviewed By: sybren Differential Revision: https://developer.blender.org/D12052 --- source/blender/editors/animation/anim_draw.c | 1 + .../blender/editors/animation/anim_motion_paths.c | 2 + source/blender/editors/animation/keyframes_draw.c | 29 +- .../blender/editors/animation/keyframes_keylist.cc | 482 +++++++++++++++------ source/blender/editors/armature/pose_slide.c | 2 + .../blender/editors/include/ED_keyframes_keylist.h | 14 +- source/blender/editors/screen/screen_ops.c | 1 + .../blender/editors/space_action/action_select.c | 1 + 8 files changed, 397 insertions(+), 135 deletions(-) diff --git a/source/blender/editors/animation/anim_draw.c b/source/blender/editors/animation/anim_draw.c index 6d272bfc180..993d10cf303 100644 --- a/source/blender/editors/animation/anim_draw.c +++ b/source/blender/editors/animation/anim_draw.c @@ -521,6 +521,7 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_ MaskLayer *masklay = BKE_mask_layer_active(mask); mask_to_keylist(&ads, masklay, keylist); } + ED_keylist_prepare_for_direct_access(keylist); /* TODO(jbakker): Keylists are ordered, no need to do any searching at all. */ /* find matching keyframe in the right direction */ diff --git a/source/blender/editors/animation/anim_motion_paths.c b/source/blender/editors/animation/anim_motion_paths.c index d976f5f72ad..d130941b9bc 100644 --- a/source/blender/editors/animation/anim_motion_paths.c +++ b/source/blender/editors/animation/anim_motion_paths.c @@ -329,6 +329,7 @@ static void motionpath_calculate_update_range(MPathTarget *mpt, for (FCurve *fcu = fcurve_list->first; fcu != NULL; fcu = fcu->next) { struct AnimKeylist *keylist = ED_keylist_create(); fcurve_to_keylist(adt, fcu, keylist, 0); + ED_keylist_prepare_for_direct_access(keylist); int fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, keylist, current_frame); int fcu_efra = motionpath_get_next_next_keyframe(mpt, keylist, current_frame); @@ -443,6 +444,7 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph, action_to_keylist(adt, adt->action, mpt->keylist, 0); } } + ED_keylist_prepare_for_direct_access(mpt->keylist); if (range == ANIMVIZ_CALC_RANGE_CHANGED) { int mpt_sfra, mpt_efra; diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c index 61918871b90..8a884c0bd5b 100644 --- a/source/blender/editors/animation/keyframes_draw.c +++ b/source/blender/editors/animation/keyframes_draw.c @@ -346,10 +346,12 @@ static void draw_keylist_block(const DrawKeylistUIData *ctx, const ActKeyColumn } static void draw_keylist_blocks(const DrawKeylistUIData *ctx, - const ListBase * /*ActKeyColumn*/ columns, + const ActKeyColumn *keys, + const int key_len, float ypos) { - LISTBASE_FOREACH (ActKeyColumn *, ab, columns) { + for (int i = 0; i < key_len; i++) { + const ActKeyColumn *ab = &keys[i]; draw_keylist_block(ctx, ab, ypos); } } @@ -362,13 +364,15 @@ static bool draw_keylist_is_visible_key(const View2D *v2d, const ActKeyColumn *a static void draw_keylist_keys(const DrawKeylistUIData *ctx, View2D *v2d, const KeyframeShaderBindings *sh_bindings, - const ListBase * /*ActKeyColumn*/ keys, + const ActKeyColumn *keys, + const int key_len, float ypos, eSAction_Flag saction_flag) { short handle_type = KEYFRAME_HANDLE_NONE, extreme_type = KEYFRAME_EXTREME_NONE; - LISTBASE_FOREACH (ActKeyColumn *, ak, keys) { + for (int i = 0; i < key_len; i++) { + const ActKeyColumn *ak = &keys[i]; if (draw_keylist_is_visible_key(v2d, ak)) { if (ctx->show_ipo) { handle_type = ak->handle_type; @@ -469,8 +473,9 @@ static void ED_keylist_draw_list_elem_draw_blocks(AnimKeylistDrawListElem *elem, DrawKeylistUIData ctx; draw_keylist_ui_data_init(&ctx, v2d, elem->yscale_fac, elem->channel_locked, elem->saction_flag); - const ListBase *keys = ED_keylist_listbase(elem->keylist); - draw_keylist_blocks(&ctx, keys, elem->ypos); + const int key_len = ED_keylist_array_len(elem->keylist); + const ActKeyColumn *keys = ED_keylist_array(elem->keylist); + draw_keylist_blocks(&ctx, keys, key_len, elem->ypos); } static void ED_keylist_draw_list_elem_draw_keys(AnimKeylistDrawListElem *elem, @@ -479,8 +484,15 @@ static void ED_keylist_draw_list_elem_draw_keys(AnimKeylistDrawListElem *elem, { DrawKeylistUIData ctx; draw_keylist_ui_data_init(&ctx, v2d, elem->yscale_fac, elem->channel_locked, elem->saction_flag); - const ListBase *keys = ED_keylist_listbase(elem->keylist); - draw_keylist_keys(&ctx, v2d, sh_bindings, keys, elem->ypos, elem->saction_flag); + + const int key_len = ED_keylist_array_len(elem->keylist); + const ActKeyColumn *keys = ED_keylist_array(elem->keylist); + draw_keylist_keys(&ctx, v2d, sh_bindings, keys, key_len, elem->ypos, elem->saction_flag); +} + +static void ED_keylist_draw_list_elem_prepare_for_drawing(AnimKeylistDrawListElem *elem) +{ + ED_keylist_prepare_for_direct_access(elem->keylist); } typedef struct AnimKeylistDrawList { @@ -496,6 +508,7 @@ static void ED_keylist_draw_list_build_keylists(AnimKeylistDrawList *draw_list) { LISTBASE_FOREACH (AnimKeylistDrawListElem *, elem, &draw_list->channels) { ED_keylist_draw_list_elem_build_keylist(elem); + ED_keylist_draw_list_elem_prepare_for_drawing(elem); } } diff --git a/source/blender/editors/animation/keyframes_keylist.cc b/source/blender/editors/animation/keyframes_keylist.cc index f6ade11a517..c1a18196a3a 100644 --- a/source/blender/editors/animation/keyframes_keylist.cc +++ b/source/blender/editors/animation/keyframes_keylist.cc @@ -23,15 +23,20 @@ /* System includes ----------------------------------------------------- */ +#include #include #include #include #include +#include +#include #include "MEM_guardedalloc.h" +#include "BLI_array.hh" #include "BLI_dlrbTree.h" #include "BLI_listbase.h" +#include "BLI_math.h" #include "BLI_range.h" #include "BLI_utildefines.h" @@ -50,117 +55,294 @@ extern "C" { /* *************************** Keyframe Processing *************************** */ -struct AnimKeylist { - DLRBT_Tree keys; -}; +/* ActKeyColumns (Keyframe Columns) ------------------------------------------ */ + +BLI_INLINE bool is_cfra_eq(const float a, const float b) +{ + return IS_EQT(a, b, BEZT_BINARYSEARCH_THRESH); +} -static void ED_keylist_init(AnimKeylist *keylist) +BLI_INLINE bool is_cfra_lt(const float a, const float b) { - BLI_dlrbTree_init(&keylist->keys); + return (b - a) > BEZT_BINARYSEARCH_THRESH; } +/* --------------- */ + +struct AnimKeylist { + /* Number of ActKeyColumn's in the keylist. */ + size_t column_len = 0; + + bool is_runtime_initialized = false; + + /* Before initializing the runtime, the key_columns list base is used to quickly add columns. + * Contains `ActKeyColumn`. Should not be used after runtime is initialized. */ + ListBase /* ActKeyColumn */ key_columns; + /* Last accessed column in the key_columns list base. Inserting columns are typically done in + * order. The last accessed column is used as starting point to search for a location to add or + * update the next column.*/ + std::optional last_accessed_column = std::nullopt; + + struct { + /* When initializing the runtime the columns from the list base `AnimKeyList.key_columns` are + * transferred to an array to support binary searching and index based access. */ + blender::Array key_columns; + /* Wrapper around runtime.key_columns so it can still be accessed as a ListBase. Elements are + * owned by runtime.key_columns. */ + ListBase /* ActKeyColumn */ list_wrapper; + } runtime; + + AnimKeylist() + { + BLI_listbase_clear(&this->key_columns); + BLI_listbase_clear(&this->runtime.list_wrapper); + } + + ~AnimKeylist() + { + BLI_freelistN(&this->key_columns); + BLI_listbase_clear(&this->runtime.list_wrapper); + } + +#ifdef WITH_CXX_GUARDEDALLOC + MEM_CXX_CLASS_ALLOC_FUNCS("editors:AnimKeylist") +#endif +}; + AnimKeylist *ED_keylist_create(void) { - AnimKeylist *keylist = static_cast(MEM_callocN(sizeof(AnimKeylist), __func__)); - ED_keylist_init(keylist); + AnimKeylist *keylist = new AnimKeylist(); return keylist; } void ED_keylist_free(AnimKeylist *keylist) { BLI_assert(keylist); - BLI_dlrbTree_free(&keylist->keys); - MEM_freeN(keylist); + delete keylist; } -const ActKeyColumn *ED_keylist_find_exact(const AnimKeylist *keylist, float cfra) +static void ED_keylist_convert_key_columns_to_array(AnimKeylist *keylist) { - return (const ActKeyColumn *)BLI_dlrbTree_search_exact( - &keylist->keys, compare_ak_cfraPtr, &cfra); + size_t index; + LISTBASE_FOREACH_INDEX (ActKeyColumn *, key, &keylist->key_columns, index) { + keylist->runtime.key_columns[index] = *key; + } } -const ActKeyColumn *ED_keylist_find_next(const AnimKeylist *keylist, float cfra) +static void ED_keylist_runtime_update_key_column_next_prev(AnimKeylist *keylist) { - return (const ActKeyColumn *)BLI_dlrbTree_search_next(&keylist->keys, compare_ak_cfraPtr, &cfra); + for (size_t index = 0; index < keylist->column_len; index++) { + const bool is_first = (index == 0); + keylist->runtime.key_columns[index].prev = is_first ? nullptr : + &keylist->runtime.key_columns[index - 1]; + const bool is_last = (index == keylist->column_len - 1); + keylist->runtime.key_columns[index].next = is_last ? nullptr : + &keylist->runtime.key_columns[index + 1]; + } } -const ActKeyColumn *ED_keylist_find_prev(const AnimKeylist *keylist, float cfra) +static void ED_keylist_runtime_init_listbase(AnimKeylist *keylist) { - return (const ActKeyColumn *)BLI_dlrbTree_search_prev(&keylist->keys, compare_ak_cfraPtr, &cfra); + if (ED_keylist_is_empty(keylist)) { + BLI_listbase_clear(&keylist->runtime.list_wrapper); + return; + } + + keylist->runtime.list_wrapper.first = &keylist->runtime.key_columns[0]; + keylist->runtime.list_wrapper.last = &keylist->runtime.key_columns[keylist->column_len - 1]; } -/* TODO(jbakker): Should we change this to use `ED_keylist_find_next(keys, min_fra)` and only check - * boundary of `max_fra`. */ -const ActKeyColumn *ED_keylist_find_any_between(const AnimKeylist *keylist, - const Range2f frame_range) +static void ED_keylist_runtime_init(AnimKeylist *keylist) { - for (const ActKeyColumn *ak = static_cast(keylist->keys.root); ak; - ak = static_cast((ak->cfra < frame_range.min) ? ak->right : - ak->left)) { - if (range2f_in_range(&frame_range, ak->cfra)) { - return ak; - } + BLI_assert(!keylist->is_runtime_initialized); + + keylist->runtime.key_columns = blender::Array(keylist->column_len); + + /* Convert linked list to array to support fast searching. */ + ED_keylist_convert_key_columns_to_array(keylist); + /* Ensure that the array can also be used as a listbase for external usages. */ + ED_keylist_runtime_update_key_column_next_prev(keylist); + ED_keylist_runtime_init_listbase(keylist); + + keylist->is_runtime_initialized = true; +} + +static void ED_keylist_reset_last_accessed(AnimKeylist *keylist) +{ + BLI_assert(!keylist->is_runtime_initialized); + keylist->last_accessed_column.reset(); +} + +void ED_keylist_prepare_for_direct_access(AnimKeylist *keylist) +{ + if (keylist->is_runtime_initialized) { + return; + } + ED_keylist_runtime_init(keylist); +} + +static const ActKeyColumn *ED_keylist_find_lower_bound(const AnimKeylist *keylist, + const float cfra) +{ + BLI_assert(!ED_keylist_is_empty(keylist)); + const ActKeyColumn *begin = std::begin(keylist->runtime.key_columns); + const ActKeyColumn *end = std::end(keylist->runtime.key_columns); + ActKeyColumn value; + value.cfra = cfra; + + const ActKeyColumn *found_column = std::lower_bound( + begin, end, value, [](const ActKeyColumn &column, const ActKeyColumn &other) { + return is_cfra_lt(column.cfra, other.cfra); + }); + return found_column; +} + +static const ActKeyColumn *ED_keylist_find_upper_bound(const AnimKeylist *keylist, + const float cfra) +{ + BLI_assert(!ED_keylist_is_empty(keylist)); + const ActKeyColumn *begin = std::begin(keylist->runtime.key_columns); + const ActKeyColumn *end = std::end(keylist->runtime.key_columns); + ActKeyColumn value; + value.cfra = cfra; + + const ActKeyColumn *found_column = std::upper_bound( + begin, end, value, [](const ActKeyColumn &column, const ActKeyColumn &other) { + return is_cfra_lt(column.cfra, other.cfra); + }); + return found_column; +} + +const ActKeyColumn *ED_keylist_find_exact(const AnimKeylist *keylist, const float cfra) +{ + BLI_assert_msg(keylist->is_runtime_initialized, + "ED_keylist_prepare_for_direct_access needs to be called before searching."); + + if (ED_keylist_is_empty(keylist)) { + return nullptr; + } + + const ActKeyColumn *found_column = ED_keylist_find_lower_bound(keylist, cfra); + + const ActKeyColumn *end = std::end(keylist->runtime.key_columns); + if (found_column == end) { + return nullptr; + } + if (is_cfra_eq(found_column->cfra, cfra)) { + return found_column; } return nullptr; } -bool ED_keylist_is_empty(const struct AnimKeylist *keylist) +const ActKeyColumn *ED_keylist_find_next(const AnimKeylist *keylist, const float cfra) { - return keylist->keys.root == nullptr; + BLI_assert_msg(keylist->is_runtime_initialized, + "ED_keylist_prepare_for_direct_access needs to be called before searching."); + + if (ED_keylist_is_empty(keylist)) { + return nullptr; + } + + const ActKeyColumn *found_column = ED_keylist_find_upper_bound(keylist, cfra); + + const ActKeyColumn *end = std::end(keylist->runtime.key_columns); + if (found_column == end) { + return nullptr; + } + return found_column; } -const struct ListBase *ED_keylist_listbase(const AnimKeylist *keylist) +const ActKeyColumn *ED_keylist_find_prev(const AnimKeylist *keylist, const float cfra) { - return (ListBase *)&keylist->keys; + BLI_assert_msg(keylist->is_runtime_initialized, + "ED_keylist_prepare_for_direct_access needs to be called before searching."); + + if (ED_keylist_is_empty(keylist)) { + return nullptr; + } + + const ActKeyColumn *end = std::end(keylist->runtime.key_columns); + const ActKeyColumn *found_column = ED_keylist_find_lower_bound(keylist, cfra); + + if (found_column == end) { + /* Nothing found, return the last item. */ + return end - 1; + } + + const ActKeyColumn *prev_column = found_column->prev; + return prev_column; } -bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range) +const ActKeyColumn *ED_keylist_find_any_between(const AnimKeylist *keylist, + const Range2f frame_range) { - BLI_assert(r_frame_range); + BLI_assert_msg(keylist->is_runtime_initialized, + "ED_keylist_prepare_for_direct_access needs to be called before searching."); if (ED_keylist_is_empty(keylist)) { - return false; + return nullptr; } - const ActKeyColumn *first_column = (const ActKeyColumn *)keylist->keys.first; - r_frame_range->min = first_column->cfra; + const ActKeyColumn *column = ED_keylist_find_lower_bound(keylist, frame_range.min); + const ActKeyColumn *end = std::end(keylist->runtime.key_columns); + if (column == end) { + return nullptr; + } + if (column->cfra >= frame_range.max) { + return nullptr; + } + return column; +} - const ActKeyColumn *last_column = (const ActKeyColumn *)keylist->keys.last; - r_frame_range->max = last_column->cfra; +const ActKeyColumn *ED_keylist_array(const struct AnimKeylist *keylist) +{ + BLI_assert_msg( + keylist->is_runtime_initialized, + "ED_keylist_prepare_for_direct_access needs to be called before accessing array."); + return keylist->runtime.key_columns.data(); +} - return true; +int64_t ED_keylist_array_len(const struct AnimKeylist *keylist) +{ + return keylist->column_len; } -/* ActKeyColumns (Keyframe Columns) ------------------------------------------ */ -BLI_INLINE bool is_cfra_eq(const float a, const float b) +bool ED_keylist_is_empty(const struct AnimKeylist *keylist) { - return IS_EQT(a, b, BEZT_BINARYSEARCH_THRESH); + return keylist->column_len == 0; } -BLI_INLINE bool is_cfra_lt(const float a, const float b) +const struct ListBase *ED_keylist_listbase(const AnimKeylist *keylist) { - return (b - a) > BEZT_BINARYSEARCH_THRESH; + if (keylist->is_runtime_initialized) { + return &keylist->runtime.list_wrapper; + } + return &keylist->key_columns; } -/* Comparator callback used for ActKeyColumns and cframe float-value pointer */ -/* NOTE: this is exported to other modules that use the ActKeyColumns for finding keyframes */ -short compare_ak_cfraPtr(void *node, void *data) +bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range) { - ActKeyColumn *ak = (ActKeyColumn *)node; - const float *cframe = static_cast(data); - const float val = *cframe; + BLI_assert(r_frame_range); - if (is_cfra_eq(val, ak->cfra)) { - return 0; + if (ED_keylist_is_empty(keylist)) { + return false; } - if (val < ak->cfra) { - return -1; + const ActKeyColumn *first_column; + const ActKeyColumn *last_column; + if (keylist->is_runtime_initialized) { + first_column = &keylist->runtime.key_columns[0]; + last_column = &keylist->runtime.key_columns[keylist->column_len - 1]; } - return 1; -} + else { + first_column = static_cast(keylist->key_columns.first); + last_column = static_cast(keylist->key_columns.last); + } + r_frame_range->min = first_column->cfra; + r_frame_range->max = last_column->cfra; -/* --------------- */ + return true; +} /* Set of references to three logically adjacent keys. */ struct BezTripleChain { @@ -243,16 +425,8 @@ static eKeyframeExtremeDrawOpts bezt_extreme_type(const BezTripleChain *chain) return KEYFRAME_EXTREME_NONE; } -/* Comparator callback used for ActKeyColumns and BezTripleChain */ -static short compare_ak_bezt(void *node, void *data) -{ - BezTripleChain *chain = static_cast(data); - - return compare_ak_cfraPtr(node, &chain->cur->vec[1][0]); -} - /* New node callback used for building ActKeyColumns from BezTripleChain */ -static DLRBT_Node *nalloc_ak_bezt(void *data) +static ActKeyColumn *nalloc_ak_bezt(void *data) { ActKeyColumn *ak = static_cast( MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn")); @@ -269,13 +443,12 @@ static DLRBT_Node *nalloc_ak_bezt(void *data) /* count keyframes in this column */ ak->totkey = 1; - return (DLRBT_Node *)ak; + return ak; } /* Node updater callback used for building ActKeyColumns from BezTripleChain */ -static void nupdate_ak_bezt(void *node, void *data) +static void nupdate_ak_bezt(ActKeyColumn *ak, void *data) { - ActKeyColumn *ak = static_cast(node); const BezTripleChain *chain = static_cast(data); const BezTriple *bezt = chain->cur; @@ -312,17 +485,8 @@ static void nupdate_ak_bezt(void *node, void *data) /* ......... */ -/* Comparator callback used for ActKeyColumns and GPencil frame */ -static short compare_ak_gpframe(void *node, void *data) -{ - const bGPDframe *gpf = (bGPDframe *)data; - - float frame = gpf->framenum; - return compare_ak_cfraPtr(node, &frame); -} - /* New node callback used for building ActKeyColumns from GPencil frames */ -static DLRBT_Node *nalloc_ak_gpframe(void *data) +static ActKeyColumn *nalloc_ak_gpframe(void *data) { ActKeyColumn *ak = static_cast( MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF")); @@ -340,14 +504,13 @@ static DLRBT_Node *nalloc_ak_gpframe(void *data) ak->block.sel = ak->sel; ak->block.flag |= ACTKEYBLOCK_FLAG_GPENCIL; - return (DLRBT_Node *)ak; + return ak; } /* Node updater callback used for building ActKeyColumns from GPencil frames */ -static void nupdate_ak_gpframe(void *node, void *data) +static void nupdate_ak_gpframe(ActKeyColumn *ak, void *data) { - ActKeyColumn *ak = (ActKeyColumn *)node; - const bGPDframe *gpf = (bGPDframe *)data; + bGPDframe *gpf = (bGPDframe *)data; /* set selection status and 'touched' status */ if (gpf->flag & GP_FRAME_SELECT) { @@ -366,17 +529,8 @@ static void nupdate_ak_gpframe(void *node, void *data) /* ......... */ -/* Comparator callback used for ActKeyColumns and GPencil frame */ -static short compare_ak_masklayshape(void *node, void *data) -{ - const MaskLayerShape *masklay_shape = (const MaskLayerShape *)data; - - float frame = masklay_shape->frame; - return compare_ak_cfraPtr(node, &frame); -} - /* New node callback used for building ActKeyColumns from GPencil frames */ -static DLRBT_Node *nalloc_ak_masklayshape(void *data) +static ActKeyColumn *nalloc_ak_masklayshape(void *data) { ActKeyColumn *ak = static_cast( MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF")); @@ -389,14 +543,13 @@ static DLRBT_Node *nalloc_ak_masklayshape(void *data) /* count keyframes in this column */ ak->totkey = 1; - return (DLRBT_Node *)ak; + return ak; } /* Node updater callback used for building ActKeyColumns from GPencil frames */ -static void nupdate_ak_masklayshape(void *node, void *data) +static void nupdate_ak_masklayshape(ActKeyColumn *ak, void *data) { - ActKeyColumn *ak = (ActKeyColumn *)node; - const MaskLayerShape *masklay_shape = (const MaskLayerShape *)data; + MaskLayerShape *masklay_shape = (MaskLayerShape *)data; /* set selection status and 'touched' status */ if (masklay_shape->flag & MASK_SHAPE_SELECT) { @@ -408,6 +561,95 @@ static void nupdate_ak_masklayshape(void *node, void *data) } /* --------------- */ +using KeylistCreateColumnFunction = std::function; +using KeylistUpdateColumnFunction = std::function; + +/* `ED_keylist_find_neighbour_front_to_back` is called before the runtime can be initialized so we + * cannot use bin searching. */ +static ActKeyColumn *ED_keylist_find_neighbour_front_to_back(ActKeyColumn *cursor, float cfra) +{ + while (cursor->next && cursor->next->cfra <= cfra) { + cursor = cursor->next; + } + return cursor; +} + +/* `ED_keylist_find_neighbour_back_to_front` is called before the runtime can be initialized so we + * cannot use bin searching. */ +static ActKeyColumn *ED_keylist_find_neighbour_back_to_front(ActKeyColumn *cursor, float cfra) +{ + while (cursor->prev && cursor->prev->cfra >= cfra) { + cursor = cursor->prev; + } + return cursor; +} + +/* + * `ED_keylist_find_exact_or_neighbour_column` is called before the runtime can be initialized so + * we cannot use bin searching. + * + * This function is called to add or update columns in the keylist. + * Typically columns are sorted by frame number so keeping track of the last_accessed_column + * reduces searching. + */ +static ActKeyColumn *ED_keylist_find_exact_or_neighbour_column(AnimKeylist *keylist, float cfra) +{ + BLI_assert(!keylist->is_runtime_initialized); + if (ED_keylist_is_empty(keylist)) { + return nullptr; + } + + ActKeyColumn *cursor = keylist->last_accessed_column.value_or( + static_cast(keylist->key_columns.first)); + if (!is_cfra_eq(cursor->cfra, cfra)) { + const bool walking_direction_front_to_back = cursor->cfra <= cfra; + if (walking_direction_front_to_back) { + cursor = ED_keylist_find_neighbour_front_to_back(cursor, cfra); + } + else { + cursor = ED_keylist_find_neighbour_back_to_front(cursor, cfra); + } + } + + keylist->last_accessed_column = cursor; + return cursor; +} + +static void ED_keylist_add_or_update_column(AnimKeylist *keylist, + float cfra, + KeylistCreateColumnFunction create_func, + KeylistUpdateColumnFunction update_func, + void *userdata) +{ + BLI_assert_msg( + !keylist->is_runtime_initialized, + "Modifying AnimKeylist isn't allowed after runtime is initialized " + "keylist->key_columns/columns_len will get out of sync with runtime.key_columns."); + if (ED_keylist_is_empty(keylist)) { + ActKeyColumn *key_column = create_func(userdata); + BLI_addhead(&keylist->key_columns, key_column); + keylist->column_len += 1; + keylist->last_accessed_column = key_column; + return; + } + + ActKeyColumn *nearest = ED_keylist_find_exact_or_neighbour_column(keylist, cfra); + if (is_cfra_eq(nearest->cfra, cfra)) { + update_func(nearest, userdata); + } + else if (is_cfra_lt(nearest->cfra, cfra)) { + ActKeyColumn *key_column = create_func(userdata); + BLI_insertlinkafter(&keylist->key_columns, nearest, key_column); + keylist->column_len += 1; + keylist->last_accessed_column = key_column; + } + else { + ActKeyColumn *key_column = create_func(userdata); + BLI_insertlinkbefore(&keylist->key_columns, nearest, key_column); + keylist->column_len += 1; + keylist->last_accessed_column = key_column; + } +} /* Add the given BezTriple to the given 'list' of Keyframes */ static void add_bezt_to_keycolumns_list(AnimKeylist *keylist, BezTripleChain *bezt) @@ -416,7 +658,8 @@ static void add_bezt_to_keycolumns_list(AnimKeylist *keylist, BezTripleChain *be return; } - BLI_dlrbTree_add(&keylist->keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt); + float cfra = bezt->cur->vec[1][0]; + ED_keylist_add_or_update_column(keylist, cfra, nalloc_ak_bezt, nupdate_ak_bezt, bezt); } /* Add the given GPencil Frame to the given 'list' of Keyframes */ @@ -426,7 +669,8 @@ static void add_gpframe_to_keycolumns_list(AnimKeylist *keylist, bGPDframe *gpf) return; } - BLI_dlrbTree_add(&keylist->keys, compare_ak_gpframe, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf); + float cfra = gpf->framenum; + ED_keylist_add_or_update_column(keylist, cfra, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf); } /* Add the given MaskLayerShape Frame to the given 'list' of Keyframes */ @@ -436,11 +680,9 @@ static void add_masklay_to_keycolumns_list(AnimKeylist *keylist, MaskLayerShape return; } - BLI_dlrbTree_add(&keylist->keys, - compare_ak_masklayshape, - nalloc_ak_masklayshape, - nupdate_ak_masklayshape, - masklay_shape); + float cfra = masklay_shape->frame; + ED_keylist_add_or_update_column( + keylist, cfra, nalloc_ak_masklayshape, nupdate_ak_masklayshape, masklay_shape); } /* ActKeyBlocks (Long Keyframes) ------------------------------------------ */ @@ -476,7 +718,7 @@ static void compute_keyblock_data(ActKeyBlockInfo *info, hold = IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) && IS_EQF(prev->vec[1][1], prev->vec[2][1]); } - /* This interpolation type induces movement even between identical keys. */ + /* This interpolation type induces movement even between identical columns. */ else { hold = !ELEM(prev->ipo, BEZT_IPO_ELASTIC); } @@ -514,7 +756,7 @@ static void add_keyblock_info(ActKeyColumn *col, const ActKeyBlockInfo *block) static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, const int bezt_len) { - ActKeyColumn *col = static_cast(keylist->keys.first); + ActKeyColumn *col = static_cast(keylist->key_columns.first); if (bezt && bezt_len >= 2) { ActKeyBlockInfo block; @@ -532,19 +774,15 @@ static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, co if (is_cfra_lt(bezt[1].vec[1][0], bezt[0].vec[1][0])) { /* Backtrack to find the right location. */ if (is_cfra_lt(bezt[1].vec[1][0], col->cfra)) { - ActKeyColumn *newcol = (ActKeyColumn *)BLI_dlrbTree_search_exact( - &keylist->keys, compare_ak_cfraPtr, &bezt[1].vec[1][0]); + ActKeyColumn *newcol = ED_keylist_find_exact_or_neighbour_column(keylist, col->cfra); - if (newcol != nullptr) { - col = newcol; + BLI_assert(newcol); + BLI_assert(newcol->cfra == col->cfra); - /* The previous keyblock is garbage too. */ - if (col->prev != nullptr) { - add_keyblock_info(col->prev, &dummy_keyblock); - } - } - else { - BLI_assert(false); + col = newcol; + /* The previous keyblock is garbage too. */ + if (col->prev != nullptr) { + add_keyblock_info(col->prev, &dummy_keyblock); } } @@ -577,20 +815,17 @@ static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, co */ static void update_keyblocks(AnimKeylist *keylist, BezTriple *bezt, const int bezt_len) { - /* Recompute the prev/next linked list. */ - BLI_dlrbTree_linkedlist_sync(&keylist->keys); - /* Find the curve count */ int max_curve = 0; - LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->keys) { + LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->key_columns) { max_curve = MAX2(max_curve, col->totcurve); } /* Propagate blocks to inserted keys */ ActKeyColumn *prev_ready = nullptr; - LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->keys) { + LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->key_columns) { /* Pre-existing column. */ if (col->totcurve > 0) { prev_ready = col; @@ -775,6 +1010,7 @@ void cachefile_to_keylist(bDopeSheet *ads, void fcurve_to_keylist(AnimData *adt, FCurve *fcu, AnimKeylist *keylist, const int saction_flag) { if (fcu && fcu->totvert && fcu->bezt) { + ED_keylist_reset_last_accessed(keylist); /* apply NLA-mapping (if applicable) */ if (adt) { ANIM_nla_mapping_apply_fcurve(adt, fcu, false, false); @@ -790,7 +1026,7 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, AnimKeylist *keylist, const i for (int v = 0; v < fcu->totvert; v++) { chain.cur = &fcu->bezt[v]; - /* Neighbor keys, accounting for being cyclic. */ + /* Neighbor columns, accounting for being cyclic. */ if (do_extremes) { chain.prev = (v > 0) ? &fcu->bezt[v - 1] : is_cyclic ? &fcu->bezt[fcu->totvert - 2] : @@ -856,6 +1092,7 @@ void gpencil_to_keylist(bDopeSheet *ads, bGPdata *gpd, AnimKeylist *keylist, con void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, AnimKeylist *keylist) { if (gpl && keylist) { + ED_keylist_reset_last_accessed(keylist); /* Although the frames should already be in an ordered list, * they are not suitable for displaying yet. */ LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) { @@ -869,6 +1106,7 @@ void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, AnimKeylist *keylis void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, AnimKeylist *keylist) { if (masklay && keylist) { + ED_keylist_reset_last_accessed(keylist); LISTBASE_FOREACH (MaskLayerShape *, masklay_shape, &masklay->splines_shapes) { add_masklay_to_keycolumns_list(keylist, masklay_shape); } diff --git a/source/blender/editors/armature/pose_slide.c b/source/blender/editors/armature/pose_slide.c index bc5cbd92deb..c02644cde39 100644 --- a/source/blender/editors/armature/pose_slide.c +++ b/source/blender/editors/armature/pose_slide.c @@ -976,6 +976,7 @@ static int pose_slide_invoke_common(bContext *C, wmOperator *op, const wmEvent * } /* Cancel if no keyframes found. */ + ED_keylist_prepare_for_direct_access(pso->keylist); if (ED_keylist_is_empty(pso->keylist)) { BKE_report(op->reports, RPT_ERROR, "No keyframes to slide between"); pose_slide_exit(C, op); @@ -1712,6 +1713,7 @@ static float pose_propagate_get_boneHoldEndFrame(tPChanFCurveLink *pfl, float st FCurve *fcu = (FCurve *)ld->data; fcurve_to_keylist(adt, fcu, keylist, 0); } + ED_keylist_prepare_for_direct_access(keylist); /* Find the long keyframe (i.e. hold), and hence obtain the endFrame value * - the best case would be one that starts on the frame itself diff --git a/source/blender/editors/include/ED_keyframes_keylist.h b/source/blender/editors/include/ED_keyframes_keylist.h index 3a9750c1206..4194444ca0f 100644 --- a/source/blender/editors/include/ED_keyframes_keylist.h +++ b/source/blender/editors/include/ED_keyframes_keylist.h @@ -139,14 +139,20 @@ typedef enum eKeyframeExtremeDrawOpts { struct AnimKeylist *ED_keylist_create(void); void ED_keylist_free(struct AnimKeylist *keylist); -const struct ActKeyColumn *ED_keylist_find_exact(const struct AnimKeylist *keylist, float cfra); -const struct ActKeyColumn *ED_keylist_find_next(const struct AnimKeylist *keylist, float cfra); -const struct ActKeyColumn *ED_keylist_find_prev(const struct AnimKeylist *keylist, float cfra); +void ED_keylist_prepare_for_direct_access(struct AnimKeylist *keylist); +const struct ActKeyColumn *ED_keylist_find_exact(const struct AnimKeylist *keylist, + const float cfra); +const struct ActKeyColumn *ED_keylist_find_next(const struct AnimKeylist *keylist, + const float cfra); +const struct ActKeyColumn *ED_keylist_find_prev(const struct AnimKeylist *keylist, + const float cfra); const struct ActKeyColumn *ED_keylist_find_any_between(const struct AnimKeylist *keylist, const Range2f frame_range); bool ED_keylist_is_empty(const struct AnimKeylist *keylist); const struct ListBase /* ActKeyColumn */ *ED_keylist_listbase(const struct AnimKeylist *keylist); bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range); +const ActKeyColumn *ED_keylist_array(const struct AnimKeylist *keylist); +int64_t ED_keylist_array_len(const struct AnimKeylist *keylist); /* Key-data Generation --------------- */ @@ -197,8 +203,6 @@ void mask_to_keylist(struct bDopeSheet *ads, struct AnimKeylist *keylist); /* ActKeyColumn API ---------------- */ -/* Comparator callback used for ActKeyColumns and cframe float-value pointer */ -short compare_ak_cfraPtr(void *node, void *data); /* Checks if ActKeyColumn has any block data */ bool actkeyblock_is_valid(const ActKeyColumn *ac); diff --git a/source/blender/editors/screen/screen_ops.c b/source/blender/editors/screen/screen_ops.c index 5d6f21f4854..3efe4ae85d5 100644 --- a/source/blender/editors/screen/screen_ops.c +++ b/source/blender/editors/screen/screen_ops.c @@ -3107,6 +3107,7 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op) mask_to_keylist(&ads, masklay, keylist); } } + ED_keylist_prepare_for_direct_access(keylist); /* find matching keyframe in the right direction */ const ActKeyColumn *ak; diff --git a/source/blender/editors/space_action/action_select.c b/source/blender/editors/space_action/action_select.c index 9dcfc626a50..a5e75e31e38 100644 --- a/source/blender/editors/space_action/action_select.c +++ b/source/blender/editors/space_action/action_select.c @@ -162,6 +162,7 @@ static void actkeys_find_key_in_list_element(bAnimContext *ac, struct AnimKeylist *keylist = ED_keylist_create(); actkeys_list_element_to_keylist(ac, keylist, ale); + ED_keylist_prepare_for_direct_access(keylist); AnimData *adt = ANIM_nla_mapping_get(ac, ale); -- cgit v1.2.3