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

1 files changed, 33 insertions, 54 deletions

diff --git a/source/blender/editors/armature/pose_slide.c b/source/blender/editors/armature/pose_slide.c
index 0a07af4ab43..3cd0897a326 100644
--- a/source/blender/editors/armature/pose_slide.c
+++ b/source/blender/editors/armature/pose_slide.c
@@ -722,13 +722,10 @@ static int pose_slide_invoke_common(bContext *C, wmOperator *op, tPoseSlideOp *p
 		/* do this for each F-Curve */
 		for (ld = pfl->fcurves.first; ld; ld = ld->next) {
 			FCurve *fcu = (FCurve *)ld->data;
-			fcurve_to_keylist(adt, fcu, &pso->keys, NULL);
+			fcurve_to_keylist(adt, fcu, &pso->keys);
 		}
 	}
 
-	/* consolidate these keyframes, and figure out the nearest ones */
-	BLI_dlrbTree_linkedlist_sync(&pso->keys);
-
 	/* cancel if no keyframes found... */
 	if (pso->keys.root) {
 		ActKeyColumn *ak;
@@ -1265,8 +1262,7 @@ typedef union tPosePropagate_ModeData {
  */
 static float pose_propagate_get_boneHoldEndFrame(Object *ob, tPChanFCurveLink *pfl, float startFrame)
 {
-	DLRBT_Tree keys, blocks;
-	ActKeyBlock *ab;
+	DLRBT_Tree keys;
 
 	AnimData *adt = ob->adt;
 	LinkData *ld;
@@ -1274,84 +1270,67 @@ static float pose_propagate_get_boneHoldEndFrame(Object *ob, tPChanFCurveLink *p
 
 	/* set up optimized data-structures for searching for relevant keyframes + holds */
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
 
 	for (ld = pfl->fcurves.first; ld; ld = ld->next) {
 		FCurve *fcu = (FCurve *)ld->data;
-		fcurve_to_keylist(adt, fcu, &keys, &blocks);
+		fcurve_to_keylist(adt, fcu, &keys);
 	}
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
-
 	/* 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
 	 */
-	ab = (ActKeyBlock *)BLI_dlrbTree_search_exact(&blocks, compare_ab_cfraPtr, &startFrame);
-
-	if (actkeyblock_is_valid(ab, &keys) == 0) {
-		/* There are only two cases for no-exact match:
-		 *  1) the current frame is just before another key but not on a key itself
-		 *  2) the current frame is on a key, but that key doesn't link to the next
-		 *
-		 * If we've got the first case, then we can search for another block,
-		 * otherwise forget it, as we'd be overwriting some valid data.
-		 */
-		if (BLI_dlrbTree_search_exact(&keys, compare_ak_cfraPtr, &startFrame) == NULL) {
-			/* we've got case 1, so try the one after */
-			ab = (ActKeyBlock *)BLI_dlrbTree_search_next(&blocks, compare_ab_cfraPtr, &startFrame);
-
-			if (actkeyblock_is_valid(ab, &keys) == 0) {
-				/* try the block before this frame then as last resort */
-				ab = (ActKeyBlock *)BLI_dlrbTree_search_prev(&blocks, compare_ab_cfraPtr, &startFrame);
-
-				/* whatever happens, stop searching now... */
-				if (actkeyblock_is_valid(ab, &keys) == 0) {
-					/* restrict range to just the frame itself
-					 * i.e. everything is in motion, so no holds to safely overwrite
-					 */
-					ab = NULL;
-				}
-			}
-		}
-		else {
-			/* we've got case 2 - set ab to NULL just in case, since we shouldn't do anything in this case */
-			ab = NULL;
+	ActKeyColumn *ab = (ActKeyColumn *)BLI_dlrbTree_search_exact(&keys, compare_ak_cfraPtr, &startFrame);
+
+	/* There are only two cases for no-exact match:
+	 *  1) the current frame is just before another key but not on a key itself
+	 *  2) the current frame is on a key, but that key doesn't link to the next
+	 *
+	 * If we've got the first case, then we can search for another block,
+	 * otherwise forget it, as we'd be overwriting some valid data.
+	 */
+	if (ab == NULL) {
+		/* we've got case 1, so try the one after */
+		ab = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &startFrame);
+
+		if ((actkeyblock_get_valid_hold(ab) & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
+			/* try the block before this frame then as last resort */
+			ab = (ActKeyColumn *)BLI_dlrbTree_search_prev(&keys, compare_ak_cfraPtr, &startFrame);
 		}
 	}
 
+	/* whatever happens, stop searching now... */
+	if ((actkeyblock_get_valid_hold(ab) & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
+		/* restrict range to just the frame itself
+		 * i.e. everything is in motion, so no holds to safely overwrite
+		 */
+		ab = NULL;
+	}
+
 	/* check if we can go any further than we've already gone */
 	if (ab) {
 		/* go to next if it is also valid and meets "extension" criteria */
 		while (ab->next) {
-			ActKeyBlock *abn = (ActKeyBlock *)ab->next;
+			ActKeyColumn *abn = ab->next;
 
 			/* must be valid */
-			if (actkeyblock_is_valid(abn, &keys) == 0)
-				break;
-			/* should start on the same frame that the last ended on */
-			if (ab->end != abn->start)
+			if ((actkeyblock_get_valid_hold(abn) & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
 				break;
+			}
 			/* should have the same number of curves */
-			if (ab->totcurve != abn->totcurve)
-				break;
-			/* should have the same value
-			 * XXX: this may be a bit fuzzy on larger data sets, so be careful
-			 */
-			if (ab->val != abn->val)
+			if (ab->totblock != abn->totblock) {
 				break;
+			}
 
 			/* we can extend the bounds to the end of this "next" block now */
 			ab = abn;
 		}
 
 		/* end frame can now take the value of the end of the block */
-		endFrame = ab->end;
+		endFrame = ab->next->cfra;
 	}
 
 	/* free temp memory */
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 
 	/* return the end frame we've found */
 	return endFrame;