[Bf-blender-cvs] [c7a84c23f11] blender2.8: Dope Sheet: rewrite computation of keyframe hold blocks.
Alexander Gavrilov
noreply at git.blender.org
Tue Oct 16 18:27:30 CEST 2018
Commit: c7a84c23f11cfccfeacf7ccfdbe7eca967c9b4ed
Author: Alexander Gavrilov
Date: Sat Oct 13 20:22:44 2018 +0300
Branches: blender2.8
https://developer.blender.org/rBc7a84c23f11cfccfeacf7ccfdbe7eca967c9b4ed
Dope Sheet: rewrite computation of keyframe hold blocks.
Computation of hold blocks was done by storing ranges (with start and
an end, and likely overlapping) in a tree keyed only by the block start.
This cannot work well, and there even were comments that it is not
reliable in complex cases.
A much better way to deal with it is to split all ranges so they don't
overlap. The most thorough way of doing this is to split at all and every
known keyframe, and in this case the data can actually be stored in the
key column data structures, avoiding the need for a second tree.
In practice, splitting requires a pass to copy this data to newly added
keys, and the necessity to loop over all keyframes in the range being
added. Both are linear and don't add excess algorithmic complexity.
The new implementation also calls BLI_dlrbTree_linkedlist_sync for
its own needs, so the users of the *_to_keylist functions don't have
to do it themselves anymore.
Differential Revision: https://developer.blender.org/D3790
===================================================================
M source/blender/blenkernel/intern/anim.c
M source/blender/editors/animation/anim_draw.c
M source/blender/editors/animation/keyframes_draw.c
M source/blender/editors/armature/pose_lib.c
M source/blender/editors/armature/pose_slide.c
M source/blender/editors/include/ED_keyframes_draw.h
M source/blender/editors/screen/screen_ops.c
M source/blender/editors/space_action/action_select.c
M source/blender/editors/space_nla/nla_draw.c
===================================================================
diff --git a/source/blender/blenkernel/intern/anim.c b/source/blender/blenkernel/intern/anim.c
index 1d38f8a8c71..d70f3459324 100644
--- a/source/blender/blenkernel/intern/anim.c
+++ b/source/blender/blenkernel/intern/anim.c
@@ -65,8 +65,8 @@
// XXX bad level call...
extern short compare_ak_cfraPtr(void *node, void *data);
-extern void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
-extern void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+extern void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys);
+extern void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys);
/* --------------------- */
/* forward declarations */
@@ -485,13 +485,11 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph,
bActionGroup *agrp = BKE_action_group_find_name(adt->action, mpt->pchan->name);
if (agrp) {
- agroup_to_keylist(adt, agrp, &mpt->keys, NULL);
- BLI_dlrbTree_linkedlist_sync(&mpt->keys);
+ agroup_to_keylist(adt, agrp, &mpt->keys);
}
}
else {
- action_to_keylist(adt, adt->action, &mpt->keys, NULL);
- BLI_dlrbTree_linkedlist_sync(&mpt->keys);
+ action_to_keylist(adt, adt->action, &mpt->keys);
}
}
}
diff --git a/source/blender/editors/animation/anim_draw.c b/source/blender/editors/animation/anim_draw.c
index 0ab6cdb3526..48dd310e2b4 100644
--- a/source/blender/editors/animation/anim_draw.c
+++ b/source/blender/editors/animation/anim_draw.c
@@ -551,11 +551,11 @@ static bool find_prev_next_keyframes(struct bContext *C, int *nextfra, int *prev
}
/* populate tree with keyframe nodes */
- scene_to_keylist(&ads, scene, &keys, NULL);
+ scene_to_keylist(&ads, scene, &keys);
gpencil_to_keylist(&ads, scene->gpd, &keys, false);
if (ob) {
- ob_to_keylist(&ads, ob, &keys, NULL);
+ ob_to_keylist(&ads, ob, &keys);
gpencil_to_keylist(&ads, ob->data, &keys, false);
}
@@ -564,9 +564,6 @@ static bool find_prev_next_keyframes(struct bContext *C, int *nextfra, int *prev
mask_to_keylist(&ads, masklay, &keys);
}
- /* build linked-list for searching */
- BLI_dlrbTree_linkedlist_sync(&keys);
-
/* find matching keyframe in the right direction */
do {
aknext = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfranext);
diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c
index e6245fffe47..451915aff6d 100644
--- a/source/blender/editors/animation/keyframes_draw.c
+++ b/source/blender/editors/animation/keyframes_draw.c
@@ -113,8 +113,8 @@ static DLRBT_Node *nalloc_ak_bezt(void *data)
ak->sel = BEZT_ISSEL_ANY(bezt) ? SELECT : 0;
ak->key_type = BEZKEYTYPE(bezt);
- /* set 'modified', since this is used to identify long keyframes */
- ak->modified = 1;
+ /* count keyframes in this column */
+ ak->totkey = 1;
return (DLRBT_Node *)ak;
}
@@ -127,7 +127,9 @@ static void nupdate_ak_bezt(void *node, void *data)
/* set selection status and 'touched' status */
if (BEZT_ISSEL_ANY(bezt)) ak->sel = SELECT;
- ak->modified += 1;
+
+ /* count keyframes in this column */
+ ak->totkey++;
/* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME)
@@ -161,8 +163,8 @@ static DLRBT_Node *nalloc_ak_gpframe(void *data)
ak->sel = (gpf->flag & GP_FRAME_SELECT) ? SELECT : 0;
ak->key_type = gpf->key_type;
- /* set 'modified', since this is used to identify long keyframes */
- ak->modified = 1;
+ /* count keyframes in this column */
+ ak->totkey = 1;
return (DLRBT_Node *)ak;
}
@@ -175,7 +177,9 @@ static void nupdate_ak_gpframe(void *node, void *data)
/* set selection status and 'touched' status */
if (gpf->flag & GP_FRAME_SELECT) ak->sel = SELECT;
- ak->modified += 1;
+
+ /* count keyframes in this column */
+ ak->totkey++;
/* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
if (gpf->key_type == BEZT_KEYTYPE_KEYFRAME)
@@ -208,8 +212,8 @@ static DLRBT_Node *nalloc_ak_masklayshape(void *data)
ak->cfra = masklay_shape->frame;
ak->sel = (masklay_shape->flag & MASK_SHAPE_SELECT) ? SELECT : 0;
- /* set 'modified', since this is used to identify long keyframes */
- ak->modified = 1;
+ /* count keyframes in this column */
+ ak->totkey = 1;
return (DLRBT_Node *)ak;
}
@@ -222,7 +226,9 @@ static void nupdate_ak_masklayshape(void *node, void *data)
/* set selection status and 'touched' status */
if (masklay_shape->flag & MASK_SHAPE_SELECT) ak->sel = SELECT;
- ak->modified += 1;
+
+ /* count keyframes in this column */
+ ak->totkey++;
}
@@ -257,64 +263,11 @@ static void add_masklay_to_keycolumns_list(DLRBT_Tree *keys, MaskLayerShape *mas
/* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
-/* Comparator callback used for ActKeyBlock and cframe float-value pointer */
-/* NOTE: this is exported to other modules that use the ActKeyBlocks for finding long-keyframes */
-short compare_ab_cfraPtr(void *node, void *data)
-{
- ActKeyBlock *ab = (ActKeyBlock *)node;
- const float *cframe = data;
- float val = *cframe;
-
- if (val < ab->start)
- return -1;
- else if (val > ab->start)
- return 1;
- else
- return 0;
-}
-
-/* --------------- */
+static const ActKeyBlockInfo dummy_keyblock = { 0 };
-/* Create a ActKeyColumn for a pair of BezTriples */
-static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn)
+static void compute_keyblock_data(ActKeyBlockInfo *info, BezTriple *prev, BezTriple *beztn)
{
- ActKeyBlock *ab = MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock");
-
- ab->start = prev->vec[1][0];
- ab->end = beztn->vec[1][0];
- ab->val = beztn->vec[1][1];
-
- ab->sel = (BEZT_ISSEL_ANY(prev) || BEZT_ISSEL_ANY(beztn)) ? SELECT : 0;
- ab->modified = 1;
-
- if (BEZKEYTYPE(beztn) == BEZT_KEYTYPE_MOVEHOLD)
- ab->flag |= ACTKEYBLOCK_FLAG_MOVING_HOLD;
-
- return ab;
-}
-
-static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, BezTriple *first_bezt, BezTriple *beztn)
-{
- ActKeyBlock *new_ab = NULL;
- BezTriple *prev = NULL;
-
- /* get the BezTriple immediately before the given one which has the same value */
- if (beztn != first_bezt) {
- /* XXX: Unless I'm overlooking some details from the past, this should be sufficient?
- * The old code did some elaborate stuff trying to find keyframe columns for
- * the given BezTriple, then step backwards to the column before that, and find
- * an appropriate BezTriple with matching values there. Maybe that was warranted
- * in the past, but now, that list is only ever filled with keyframes from the
- * current FCurve.
- *
- * -- Aligorith (20140415)
- */
- prev = beztn - 1;
- }
-
-
- /* check if block needed */
- if (prev == NULL) return;
+ memset(info, 0, sizeof (ActKeyBlockInfo));
if (BEZKEYTYPE(beztn) == BEZT_KEYTYPE_MOVEHOLD) {
/* Animator tagged a "moving hold"
@@ -322,153 +275,136 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, BezTriple *first_bezt
* we're just dealing with the first of a pair, and we don't
* want to be creating any phantom holds...
*/
- if (BEZKEYTYPE(prev) != BEZT_KEYTYPE_MOVEHOLD)
- return;
+ if (BEZKEYTYPE(prev) == BEZT_KEYTYPE_MOVEHOLD) {
+ info->flag |= ACTKEYBLOCK_FLAG_MOVING_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD;
+ }
}
- else {
- /* Check for same values...
- * - Handles must have same central value as each other
- * - Handles which control that section of the curve must be constant
- */
- if (IS_EQF(beztn->vec[1][1], prev->vec[1][1]) == 0) return;
+
+ /* Check for same values...
+ * - Handles must have same central value as each other
+ * - Handles which control that section of the curve must be constant
+ */
+ if (IS_EQF(beztn->vec[1][1], prev->vec[1][1])) {
+ bool hold;
/* Only check handles in case of actual bezier interpolation. */
if (prev->ipo == BEZT_IPO_BEZ) {
- if (IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) == 0) return;
- if (IS_EQF(prev->vec[1][1], prev->vec[2][1]) == 0) return;
+ 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. */
- else if (ELEM(prev->ipo, BEZT_IPO_ELASTIC)) {
- return;
+ else {
+ hold = !ELEM(prev->ipo, BEZT_IPO_ELASTIC);
+ }
+
+ if (hold) {
+ info->flag |= ACTKEYBLOCK_FLAG_STATIC_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD;
}
}
- /* if there are no blocks already, just add as root */
- if (blocks->root == NULL) {
- /* just add this as the root, then call the tree-balancing functions to validate */
- new_ab = bezts_to_new_actkeyblock(prev, beztn);
- blocks->root = (DLRBT_Node *)new_ab;
+ info->sel = BEZT_ISSEL_ANY(prev) || BEZT_ISSEL_ANY(beztn);
+}
+
+static void add_keyblock_info(ActKeyColumn *col, const ActKeyBlockInfo *block)
+{
+ /* New curve and block. */
+ if (col->totcurve <= 1 && col->totblock == 0) {
+ memcpy(&col->block, block, sizeof(ActKeyBlockInfo));
}
+ /* Existing curve. */
else {
- ActKeyBlock *ab, *abn = NULL;
+ col->block.conflict |= (col->block.flag ^ block->flag);
+ col->block.flag |= block->flag;
+ col->block.sel |= block->sel;
+ }
- /* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there
- * Note: we perform a tree traversal here NOT a standard linked-list traversal...
- * Note: we can't search from end to try to optimize this as it causes errors there's
- * an A ___ B |---| B situation
- */
- // FIXME: here there is a bug where we are trying to get the summary for the following channels
- // A|--------------|A ______________ B|--------------|B
- // A|------------------------------------------------|A
- // A|----|A|---|A|-----------------------------------|A
- for (ab = blocks->root; ab; ab = abn) {
- /* check if this is a match, or whether we go left or right
- * NOTE: we now use a float threshold to prevent precision errors causin
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list