diff options
author | Jeroen Bakker <jbakker> | 2021-09-10 14:27:26 +0300 |
---|---|---|
committer | Jeroen Bakker <jeroen@blender.org> | 2021-09-10 14:28:47 +0300 |
commit | 60cfdf080929aca61c37439b601b1ef85d51391a (patch) | |
tree | 47f8cbf44718abb740d0455b21470488e80eeffe /source/blender/editors/animation/keyframes_keylist.cc | |
parent | a00507c482e28ad20813f082057d4a09061c03cc (diff) |
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
Diffstat (limited to 'source/blender/editors/animation/keyframes_keylist.cc')
-rw-r--r-- | source/blender/editors/animation/keyframes_keylist.cc | 482 |
1 files changed, 360 insertions, 122 deletions
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 <algorithm> #include <cfloat> #include <cmath> #include <cstdlib> #include <cstring> +#include <functional> +#include <optional> #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<ActKeyColumn *> 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<ActKeyColumn> 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<AnimKeylist *>(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<const ActKeyColumn *>(keylist->keys.root); ak; - ak = static_cast<const ActKeyColumn *>((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<ActKeyColumn>(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<const float *>(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<const ActKeyColumn *>(keylist->key_columns.first); + last_column = static_cast<const ActKeyColumn *>(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<BezTripleChain *>(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<ActKeyColumn *>( 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<ActKeyColumn *>(node); const BezTripleChain *chain = static_cast<const BezTripleChain *>(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<ActKeyColumn *>( 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<ActKeyColumn *>( 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<ActKeyColumn *(void *userdata)>; +using KeylistUpdateColumnFunction = std::function<void(ActKeyColumn *, void *)>; + +/* `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<ActKeyColumn *>(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<ActKeyColumn *>(keylist->keys.first); + ActKeyColumn *col = static_cast<ActKeyColumn *>(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); } |