Make curve decimation only take into account the selected curve points

Previously the decimation would take the whole curve into account when
decimating and not just the selected part.

This also contains various smaller bug fixes for the fcurve decimation.

Reviewed By: Sybren

Differential Revision: http://developer.blender.org/D6286

2 files changed, 401 insertions, 14 deletions

diff --git a/source/blender/editors/space_graph/graph_edit.c b/source/blender/editors/space_graph/graph_edit.c
index e7a25f6c659..2948566ff0e 100644
--- a/source/blender/editors/space_graph/graph_edit.c
+++ b/source/blender/editors/space_graph/graph_edit.c
@@ -60,6 +60,7 @@
 #include "ED_anim_api.h"
 #include "ED_keyframing.h"
 #include "ED_keyframes_edit.h"
+#include "ED_numinput.h"
 #include "ED_screen.h"
 #include "ED_transform.h"
 #include "ED_markers.h"
@@ -1305,7 +1306,7 @@ void GRAPH_OT_clean(wmOperatorType *ot)
 
 /* ******************** Decimate Keyframes Operator ************************* */
 
-static void decimate_graph_keys(bAnimContext *ac, float remove_ratio)
+static void decimate_graph_keys(bAnimContext *ac, float remove_ratio, float error_sq_max)
 {
   ListBase anim_data = {NULL, NULL};
   bAnimListElem *ale;
@@ -1318,7 +1319,10 @@ static void decimate_graph_keys(bAnimContext *ac, float remove_ratio)
 
   /* loop through filtered data and clean curves */
   for (ale = anim_data.first; ale; ale = ale->next) {
-    decimate_fcurve(ale, remove_ratio);
+    if (!decimate_fcurve(ale, remove_ratio, error_sq_max)) {
+      /* The selection contains unsupported keyframe types! */
+      WM_report(RPT_WARNING, "Decimate: Skipping non linear/bezier keyframes!");
+    }
 
     ale->update |= ANIM_UPDATE_DEFAULT;
   }
@@ -1329,18 +1333,329 @@ static void decimate_graph_keys(bAnimContext *ac, float remove_ratio)
 
 /* ------------------- */
 
+/* This data type is only used for modal operation. */
+typedef struct tDecimateGraphOp {
+  bAnimContext ac;
+  Scene *scene;
+  ScrArea *sa;
+  ARegion *ar;
+
+  /** A 0-1 value for determining how much we should decimate. */
+  PropertyRNA *percentage_prop;
+
+  /** The original bezt curve data (used for restoring fcurves).*/
+  ListBase bezt_arr_list;
+
+  NumInput num;
+} tDecimateGraphOp;
+
+typedef struct tBeztCopyData {
+  int tot_vert;
+  BezTriple *bezt;
+} tBeztCopyData;
+
+typedef enum tDecimModes {
+  DECIM_RATIO = 1,
+  DECIM_ERROR,
+} tDecimModes;
+
+/* Overwrite the current bezts arrays with the original data. */
+static void decimate_reset_bezts(tDecimateGraphOp *dgo)
+{
+  ListBase anim_data = {NULL, NULL};
+  LinkData *link_bezt;
+  bAnimListElem *ale;
+  int filter;
+
+  bAnimContext *ac = &dgo->ac;
+
+  /* filter data */
+  filter = (ANIMFILTER_DATA_VISIBLE | ANIMFILTER_CURVE_VISIBLE | ANIMFILTER_FOREDIT |
+            ANIMFILTER_SEL | ANIMFILTER_NODUPLIS);
+  ANIM_animdata_filter(ac, &anim_data, filter, ac->data, ac->datatype);
+
+  /* Loop through filtered data and reset bezts. */
+  for (ale = anim_data.first, link_bezt = dgo->bezt_arr_list.first; ale;
+       ale = ale->next, link_bezt = link_bezt->next) {
+    FCurve *fcu = (FCurve *)ale->key_data;
+    tBeztCopyData *data = link_bezt->data;
+
+    const int arr_size = sizeof(BezTriple) * data->tot_vert;
+
+    MEM_freeN(fcu->bezt);
+
+    fcu->bezt = MEM_mallocN(arr_size, __func__);
+    fcu->totvert = data->tot_vert;
+
+    memcpy(fcu->bezt, data->bezt, arr_size);
+  }
+
+  ANIM_animdata_freelist(&anim_data);
+}
+
+static void decimate_exit(bContext *C, wmOperator *op)
+{
+  tDecimateGraphOp *dgo = op->customdata;
+  wmWindow *win = CTX_wm_window(C);
+
+  /* If data exists, clear its data and exit. */
+  if (dgo == NULL) {
+    return;
+  }
+  LinkData *link;
+
+  for (link = dgo->bezt_arr_list.first; link != NULL; link = link->next) {
+    tBeztCopyData *copy = link->data;
+    MEM_freeN(copy->bezt);
+    MEM_freeN(link->data);
+  }
+
+  BLI_freelistN(&dgo->bezt_arr_list);
+  MEM_freeN(dgo);
+
+  WM_cursor_modal_restore(win);
+
+  /* cleanup */
+  op->customdata = NULL;
+}
+
+/* Draw a percentage indicator in header. */
+static void decimate_draw_status_header(wmOperator *op, tDecimateGraphOp *dgo)
+{
+  char status_str[UI_MAX_DRAW_STR];
+  char mode_str[32];
+
+  strcpy(mode_str, TIP_("Decimate Keyframes"));
+
+  if (hasNumInput(&dgo->num)) {
+    char str_offs[NUM_STR_REP_LEN];
+
+    outputNumInput(&dgo->num, str_offs, &dgo->scene->unit);
+
+    BLI_snprintf(status_str, sizeof(status_str), "%s: %s", mode_str, str_offs);
+  }
+  else {
+    float percentage = RNA_property_float_get(op->ptr, dgo->percentage_prop);
+    BLI_snprintf(
+        status_str, sizeof(status_str), "%s: %d %%", mode_str, (int)(percentage * 100.0f));
+  }
+
+  ED_area_status_text(dgo->sa, status_str);
+}
+
+/* Calculate percentage based on position of mouse (we only use x-axis for now.
+ * Since this is more convenient for users to do), and store new percentage value.
+ */
+static void decimate_mouse_update_percentage(tDecimateGraphOp *dgo,
+                                             wmOperator *op,
+                                             const wmEvent *event)
+{
+  float percentage = (event->x - dgo->ar->winrct.xmin) / ((float)dgo->ar->winx);
+  RNA_property_float_set(op->ptr, dgo->percentage_prop, percentage);
+}
+
+static int graphkeys_decimate_invoke(bContext *C, wmOperator *op, const wmEvent *event)
+{
+  tDecimateGraphOp *dgo;
+
+  WM_cursor_modal_set(CTX_wm_window(C), WM_CURSOR_EW_SCROLL);
+
+  /* Init slide-op data. */
+  dgo = op->customdata = MEM_callocN(sizeof(tDecimateGraphOp), "tDecimateGraphOp");
+
+  /* Get editor data. */
+  if (ANIM_animdata_get_context(C, &dgo->ac) == 0) {
+    decimate_exit(C, op);
+    return OPERATOR_CANCELLED;
+  }
+
+  dgo->percentage_prop = RNA_struct_find_property(op->ptr, "remove_ratio");
+
+  dgo->scene = CTX_data_scene(C);
+  dgo->sa = CTX_wm_area(C);
+  dgo->ar = CTX_wm_region(C);
+
+  /* initialise percentage so that it will have the correct value before the first mouse move. */
+  decimate_mouse_update_percentage(dgo, op, event);
+
+  decimate_draw_status_header(op, dgo);
+
+  /* Construct a list with the original bezt arrays so we can restore them during modal operation.
+   */
+  {
+    ListBase anim_data = {NULL, NULL};
+    bAnimContext *ac = &dgo->ac;
+    bAnimListElem *ale;
+
+    int filter;
+
+    /* filter data */
+    filter = (ANIMFILTER_DATA_VISIBLE | ANIMFILTER_CURVE_VISIBLE | ANIMFILTER_FOREDIT |
+              ANIMFILTER_SEL | ANIMFILTER_NODUPLIS);
+    ANIM_animdata_filter(ac, &anim_data, filter, ac->data, ac->datatype);
+
+    /* Loop through filtered data and copy the curves. */
+    for (ale = anim_data.first; ale; ale = ale->next) {
+      FCurve *fcu = (FCurve *)ale->key_data;
+      const int arr_size = sizeof(BezTriple) * fcu->totvert;
+
+      tBeztCopyData *copy = MEM_mallocN(sizeof(tBeztCopyData), "bezts_copy");
+      BezTriple *bezts_copy = MEM_mallocN(arr_size, "bezts_copy_array");
+
+      copy->tot_vert = fcu->totvert;
+      memcpy(bezts_copy, fcu->bezt, arr_size);
+
+      copy->bezt = bezts_copy;
+
+      LinkData *link = NULL;
+
+      link = MEM_callocN(sizeof(LinkData), "Bezt Link");
+      link->data = copy;
+
+      BLI_addtail(&dgo->bezt_arr_list, link);
+    }
+
+    ANIM_animdata_freelist(&anim_data);
+  }
+
+  WM_event_add_modal_handler(C, op);
+  return OPERATOR_RUNNING_MODAL;
+}
+
+static void graphkeys_decimate_modal_update(bContext *C, wmOperator *op)
+{
+  /* Perform decimate updates - in response to some user action
+   * (e.g. pressing a key or moving the mouse). */
+  tDecimateGraphOp *dgo = op->customdata;
+
+  decimate_draw_status_header(op, dgo);
+
+  /* Reset keyframe data (so we get back to the original state). */
+  decimate_reset_bezts(dgo);
+
+  /* apply... */
+  float remove_ratio = RNA_property_float_get(op->ptr, dgo->percentage_prop);
+  /* We don't want to limit the decimation to a certain error margin. */
+  const float error_sq_max = FLT_MAX;
+  decimate_graph_keys(&dgo->ac, remove_ratio, error_sq_max);
+  WM_event_add_notifier(C, NC_ANIMATION | ND_KEYFRAME | NA_EDITED, NULL);
+}
+
+static int graphkeys_decimate_modal(bContext *C, wmOperator *op, const wmEvent *event)
+{
+  /* This assumes that we are in "DECIM_RATIO" mode. This is because the error margin is very hard
+   * and finicky to control with this modal mouse grab method. Therefore, it is expected that the
+   * error margin mode is not adjusted by the modal operator but instead tweaked via the redo
+   * panel.*/
+  tDecimateGraphOp *dgo = op->customdata;
+
+  const bool has_numinput = hasNumInput(&dgo->num);
+
+  switch (event->type) {
+    case LEFTMOUSE: /* confirm */
+    case RETKEY:
+    case PADENTER: {
+      if (event->val == KM_PRESS) {
+        ED_area_status_text(dgo->sa, NULL);
+
+        decimate_exit(C, op);
+
+        return OPERATOR_FINISHED;
+      }
+      break;
+    }
+
+    case ESCKEY: /* cancel */
+    case RIGHTMOUSE: {
+      if (event->val == KM_PRESS) {
+        /* Return to normal cursor and header status. */
+        ED_area_status_text(dgo->sa, NULL);
+
+        decimate_reset_bezts(dgo);
+
+        WM_event_add_notifier(C, NC_ANIMATION | ND_KEYFRAME | NA_EDITED, NULL);
+
+        decimate_exit(C, op);
+
+        return OPERATOR_CANCELLED;
+      }
+      break;
+    }
+
+    /* Percentage Change... */
+    case MOUSEMOVE: /* calculate new position */
+    {
+      if (has_numinput == false) {
+        /* Update percentage based on position of mouse. */
+        decimate_mouse_update_percentage(dgo, op, event);
+
+        /* Update pose to reflect the new values. */
+        graphkeys_decimate_modal_update(C, op);
+      }
+      break;
+    }
+    default: {
+      if ((event->val == KM_PRESS) && handleNumInput(C, &dgo->num, event)) {
+        float value;
+        float percentage = RNA_property_float_get(op->ptr, dgo->percentage_prop);
+
+        /* Grab percentage from numeric input, and store this new value for redo
+         * NOTE: users see ints, while internally we use a 0-1 float.
+         */
+        value = percentage * 100.0f;
+        applyNumInput(&dgo->num, &value);
+
+        percentage = value / 100.0f;
+        RNA_property_float_set(op->ptr, dgo->percentage_prop, percentage);
+
+        /* Update decimate output to reflect the new values. */
+        graphkeys_decimate_modal_update(C, op);
+        break;
+      }
+      else {
+        /* unhandled event - maybe it was some view manip? */
+        /* allow to pass through */
+        return OPERATOR_RUNNING_MODAL | OPERATOR_PASS_THROUGH;
+      }
+    }
+  }
+
+  return OPERATOR_RUNNING_MODAL;
+}
+
 static int graphkeys_decimate_exec(bContext *C, wmOperator *op)
 {
   bAnimContext ac;
-  float remove_ratio;
 
   /* get editor data */
   if (ANIM_animdata_get_context(C, &ac) == 0) {
     return OPERATOR_CANCELLED;
   }
 
-  remove_ratio = RNA_float_get(op->ptr, "remove_ratio");
-  decimate_graph_keys(&ac, remove_ratio);
+  tDecimModes mode = RNA_enum_get(op->ptr, "mode");
+  /* We want to be able to work on all available keyframes. */
+  float remove_ratio = 1.0f;
+  /* We don't want to limit the decimation to a certain error margin. */
+  float error_sq_max = FLT_MAX;
+
+  switch (mode) {
+    case DECIM_RATIO:
+      remove_ratio = RNA_float_get(op->ptr, "remove_ratio");
+      break;
+    case DECIM_ERROR:
+      error_sq_max = RNA_float_get(op->ptr, "remove_error_margin");
+      /* The decimate algorithm expects the error to be squared. */
+      error_sq_max *= error_sq_max;
+
+      break;
+  }
+
+  if (remove_ratio == 0.0f || error_sq_max == 0.0f) {
+    /* Nothing to remove. */
+    return OPERATOR_FINISHED;
+  }
+
+  decimate_graph_keys(&ac, remove_ratio, error_sq_max);
 
   /* set notifier that keyframes have changed */
   WM_event_add_notifier(C, NC_ANIMATION | ND_KEYFRAME | NA_EDITED, NULL);
@@ -1348,6 +1663,55 @@ static int graphkeys_decimate_exec(bContext *C, wmOperator *op)
   return OPERATOR_FINISHED;
 }
 
+static bool graphkeys_decimate_poll_property(const bContext *UNUSED(C),
+                                             wmOperator *op,
+                                             const PropertyRNA *prop)
+{
+  const char *prop_id = RNA_property_identifier(prop);
+
+  if (STRPREFIX(prop_id, "remove")) {
+    int mode = RNA_enum_get(op->ptr, "mode");
+
+    if (STREQ(prop_id, "remove_ratio") && mode != DECIM_RATIO) {
+      return false;
+    }
+    else if (STREQ(prop_id, "remove_error_margin") && mode != DECIM_ERROR) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+static char *graphkeys_decimate_desc(bContext *UNUSED(C),
+                                     wmOperatorType *UNUSED(op),
+                                     PointerRNA *ptr)
+{
+
+  if (RNA_enum_get(ptr, "mode") == DECIM_ERROR) {
+    return BLI_strdup(
+        "Decimate F-Curves by specifying how much it can deviate from the original curve");
+  }
+
+  /* Use default description. */
+  return NULL;
+}
+
+static const EnumPropertyItem decimate_mode_items[] = {
+    {DECIM_RATIO,
+     "RATIO",
+     0,
+     "Ratio",
+     "Use a percentage to specify how many keyframes you want to remove"},
+    {DECIM_ERROR,
+     "ERROR",
+     0,
+     "Error Margin",
+     "Use an error margin to specify how much the curve is allowed to deviate from the original "
+     "path"},
+    {0, NULL, 0, NULL, NULL},
+};
+
 void GRAPH_OT_decimate(wmOperatorType *ot)
 {
   /* identifiers */
@@ -1357,6 +1721,10 @@ void GRAPH_OT_decimate(wmOperatorType *ot)
       "Decimate F-Curves by removing keyframes that influence the curve shape the least";
 
   /* api callbacks */
+  ot->poll_property = graphkeys_decimate_poll_property;
+  ot->get_description = graphkeys_decimate_desc;
+  ot->invoke = graphkeys_decimate_invoke;
+  ot->modal = graphkeys_decimate_modal;
   ot->exec = graphkeys_decimate_exec;
   ot->poll = graphop_editable_keyframes_poll;
 
@@ -1364,15 +1732,31 @@ void GRAPH_OT_decimate(wmOperatorType *ot)
   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
 
   /* properties */
-  ot->prop = RNA_def_float_percentage(ot->srna,
-                                      "remove_ratio",
-                                      1.0f / 3.0f,
-                                      0.0f,
-                                      1.0f,
-                                      "Remove",
-                                      "The percentage of keyframes to remove",
-                                      0.0f,
-                                      1.0f);
+  RNA_def_enum(ot->srna,
+               "mode",
+               decimate_mode_items,
+               DECIM_RATIO,
+               "Mode",
+               "Which mode to use for decimation");
+
+  RNA_def_float_percentage(ot->srna,
+                           "remove_ratio",
+                           1.0f / 3.0f,
+                           0.0f,
+                           1.0f,
+                           "Remove",
+                           "The percentage of keyframes to remove",
+                           0.0f,
+                           1.0f);
+  RNA_def_float(ot->srna,
+                "remove_error_margin",
+                0.0f,
+                0.0f,
+                FLT_MAX,
+                "Max Error Margin",
+                "How much the new decimated curve is allowed to deviate from the original",
+                0.0f,
+                10.0f);
 }
 
 /* ******************** Bake F-Curve Operator *********************** */
diff --git a/source/blender/editors/space_graph/space_graph.c b/source/blender/editors/space_graph/space_graph.c
index eb7ba480296..7bc907bb3db 100644
--- a/source/blender/editors/space_graph/space_graph.c
+++ b/source/blender/editors/space_graph/space_graph.c
@@ -905,5 +905,8 @@ void ED_spacetype_ipo(void)
 
   graph_buttons_register(art);
 
+  art = ED_area_type_hud(st->spaceid);
+  BLI_addhead(&st->regiontypes, art);
+
   BKE_spacetype_register(st);
 }