[Bf-blender-cvs] [60cfdf08092] master: Anim: Keylist drawing optimization by using arrays.
Jeroen Bakker
noreply at git.blender.org
Fri Sep 10 13:29:48 CEST 2021
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. @@
More information about the Bf-blender-cvs
mailing list