Merge branch 'master' into blender2.8
[blender.git] / source / blender / editors / transform / transform_conversions.c
index 96970fa8a0ffabc423c1e59d3b2a6d0848dfd520..d73d5e82d0f9c265dc8d7016e50d1fc0de85f3af 100644 (file)
@@ -3497,67 +3497,136 @@ static void posttrans_mask_clean(Mask *mask)
        }
 }
 
+/* Time + Average value */
+typedef struct tRetainedKeyframe {
+       struct tRetainedKeyframe *next, *prev;
+       float frame;      /* frame to cluster around */
+       float val;        /* average value */
+       
+       size_t tot_count; /* number of keyframes that have been averaged */
+       size_t del_count; /* number of keyframes of this sort that have been deleted so far */
+} tRetainedKeyframe;
+
 /* Called during special_aftertrans_update to make sure selected keyframes replace
  * any other keyframes which may reside on that frame (that is not selected).
  */
 static void posttrans_fcurve_clean(FCurve *fcu, const bool use_handle)
 {
-       float *selcache;    /* cache for frame numbers of selected frames (fcu->totvert*sizeof(float)) */
-       int len, index, i;  /* number of frames in cache, item index */
-
-       /* allocate memory for the cache */
-       // TODO: investigate using BezTriple columns instead?
-       if (fcu->totvert == 0 || fcu->bezt == NULL)
+       /* NOTE: We assume that all keys are sorted */
+       ListBase retained_keys = {NULL, NULL};
+       const bool can_average_points = ((fcu->flag & (FCURVE_INT_VALUES | FCURVE_DISCRETE_VALUES)) == 0);
+       
+       /* sanity checks */
+       if ((fcu->totvert == 0) || (fcu->bezt == NULL))
                return;
-       selcache = MEM_callocN(sizeof(float) * fcu->totvert, "FCurveSelFrameNums");
-       len = 0;
-       index = 0;
-
-       /* We do 2 loops, 1 for marking keyframes for deletion, one for deleting
-        * as there is no guarantee what order the keyframes are exactly, even though
-        * they have been sorted by time.
+       
+       /* 1) Identify selected keyframes, and average the values on those
+        * in case there are collisions due to multiple keys getting scaled
+        * to all end up on the same frame
         */
-
-       /*      Loop 1: find selected keyframes   */
-       for (i = 0; i < fcu->totvert; i++) {
+       for (int i = 0; i < fcu->totvert; i++) {
                BezTriple *bezt = &fcu->bezt[i];
                
                if (BEZT_ISSEL_ANY(bezt)) {
-                       selcache[index] = bezt->vec[1][0];
-                       index++;
-                       len++;
+                       bool found = false;
+                       
+                       /* If there's another selected frame here, merge it */
+                       for (tRetainedKeyframe *rk = retained_keys.last; rk; rk = rk->prev) {
+                               if (IS_EQT(rk->frame, bezt->vec[1][0], BEZT_BINARYSEARCH_THRESH)) {
+                                       rk->val += bezt->vec[1][1];
+                                       rk->tot_count++;
+                                       
+                                       found = true;
+                                       break;
+                               }
+                               else if (rk->frame < bezt->vec[1][0]) {
+                                       /* Terminate early if have passed the supposed insertion point? */
+                                       break;
+                               }
+                       }
+                       
+                       /* If nothing found yet, create a new one */
+                       if (found == false) {
+                               tRetainedKeyframe *rk = MEM_callocN(sizeof(tRetainedKeyframe), "tRetainedKeyframe");
+                               
+                               rk->frame = bezt->vec[1][0];
+                               rk->val   = bezt->vec[1][1];
+                               rk->tot_count = 1;
+                               
+                               BLI_addtail(&retained_keys, rk);
+                       }
                }
        }
-
-       /* Loop 2: delete unselected keyframes on the same frames 
-        * (if any keyframes were found, or the whole curve wasn't affected) 
+       
+       if (BLI_listbase_is_empty(&retained_keys)) {
+               /* This may happen if none of the points were selected... */
+               if (G.debug & G_DEBUG) {
+                       printf("%s: nothing to do for FCurve %p (rna_path = '%s')\n", __func__, fcu, fcu->rna_path);
+               }
+               return;
+       }
+       else {
+               /* Compute the average values for each retained keyframe */
+               for (tRetainedKeyframe *rk = retained_keys.first; rk; rk = rk->next) {
+                       rk->val = rk->val / (float)rk->tot_count;
+               }
+       }
+       
+       /* 2) Delete all keyframes duplicating the "retained keys" found above
+        *   - Most of these will be unselected keyframes
+        *   - Some will be selected keyframes though. For those, we only keep the last one
+        *     (or else everything is gone), and replace its value with the averaged value. 
         */
-       if ((len) && (len != fcu->totvert)) {
-               for (i = fcu->totvert - 1; i >= 0; i--) {
-                       BezTriple *bezt = &fcu->bezt[i];
-                       
-                       if (BEZT_ISSEL_ANY(bezt) == 0) {
-                               /* check beztriple should be removed according to cache */
-                               for (index = 0; index < len; index++) {
-                                       if (IS_EQF(bezt->vec[1][0], selcache[index])) {
+       for (int i = fcu->totvert - 1; i >= 0; i--) {
+               BezTriple *bezt = &fcu->bezt[i];
+               
+               /* Is this keyframe a candidate for deletion? */
+               /* TODO: Replace loop with an O(1) lookup instead */
+               for (tRetainedKeyframe *rk = retained_keys.last; rk; rk = rk->prev) {
+                       if (IS_EQT(bezt->vec[1][0], rk->frame, BEZT_BINARYSEARCH_THRESH)) {
+                               /* Selected keys are treated with greater care than unselected ones... */
+                               if (BEZT_ISSEL_ANY(bezt)) {
+                                       /* - If this is the last selected key left (based on rk->del_count) ==> UPDATE IT
+                                        *   (or else we wouldn't have any keyframe left here)
+                                        * - Otherwise, there are still other selected keyframes on this frame
+                                        *   to be merged down still ==> DELETE IT
+                                        */
+                                       if (rk->del_count == rk->tot_count - 1) {
+                                               /* Update keyframe... */
+                                               if (can_average_points) {
+                                                       /* TODO: update handles too? */
+                                                       bezt->vec[1][1] = rk->val;
+                                               }
+                                       }
+                                       else {
+                                               /* Delete Keyframe */
                                                delete_fcurve_key(fcu, i, 0);
-                                               break;
                                        }
-                                       else if (bezt->vec[1][0] < selcache[index])
-                                               break;
+                                       
+                                       /* Update count of how many we've deleted
+                                        * - It should only matter that we're doing this for all but the last one
+                                        */
+                                       rk->del_count++;
+                               }
+                               else {
+                                       /* Always delete - Unselected keys don't matter */
+                                       delete_fcurve_key(fcu, i, 0);
                                }
+                                                               
+                               /* Stop the RK search... we've found our match now */
+                               break;
                        }
                }
-               
-               testhandles_fcurve(fcu, use_handle);
        }
-
-       /* free cache */
-       MEM_freeN(selcache);
+       
+       /* 3) Recalculate handles */
+       testhandles_fcurve(fcu, use_handle);
+       
+       /* cleanup */
+       BLI_freelistN(&retained_keys);
 }
 
 
-
 /* Called by special_aftertrans_update to make sure selected keyframes replace
  * any other keyframes which may reside on that frame (that is not selected).
  * remake_action_ipos should have already been called