Commit: 60cfdf080929aca61c37439b601b1ef85d51391a Author: Jeroen Bakker Date: Fri Sep 10 13:27:26 2021 +0200 Branches: master https://developer.blender.org/rB60cfdf080929aca61c37439b601b1ef85d51391a
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 =================================================================== M source/blender/editors/animation/anim_draw.c M source/blender/editors/animation/anim_motion_paths.c M source/blender/editors/animation/keyframes_draw.c M source/blender/editors/animation/keyframes_keylist.cc M source/blender/editors/armature/pose_slide.c M source/blender/editors/include/ED_keyframes_keylist.h M source/blender/editors/screen/screen_ops.c M source/blender/editors/space_action/action_select.c =================================================================== 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 <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 @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list [email protected] List details, subscription details or unsubscribe: https://lists.blender.org/mailman/listinfo/bf-blender-cvs
