Add curve decimate in the graph editor

Added a animation curve decimate operator in the graph editor

Reviewed By: Sybren

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

5 files changed, 125 insertions, 0 deletions

diff --git a/source/blender/editors/animation/keyframes_general.c b/source/blender/editors/animation/keyframes_general.c
index be8de66a262..ffae402989c 100644
--- a/source/blender/editors/animation/keyframes_general.c
+++ b/source/blender/editors/animation/keyframes_general.c
@@ -31,12 +31,14 @@
 #include "BLI_blenlib.h"
 #include "BLI_utildefines.h"
 #include "BLI_string_utils.h"
+#include "BLI_math.h"
 
 #include "DNA_anim_types.h"
 #include "DNA_object_types.h"
 #include "DNA_scene_types.h"
 
 #include "BKE_action.h"
+#include "BKE_curve.h"
 #include "BKE_fcurve.h"
 #include "BKE_report.h"
 #include "BKE_main.h"
@@ -326,6 +328,54 @@ void clean_fcurve(struct bAnimContext *ac, bAnimListElem *ale, float thresh, boo
 
 /* ---------------- */
 
+/**
+ * F-Curve 'decimate' function that removes a certain ratio of curve
+ * points that will affect the curves overall shape the least.
+ */
+void decimate_fcurve(bAnimListElem *ale, float remove_ratio)
+{
+  FCurve *fcu = (FCurve *)ale->key_data;
+
+  /* Check if the curve actually has any points  */
+  if (fcu == NULL || fcu->bezt == NULL || fcu->totvert == 0) {
+    return;
+  }
+
+  const int target_fcurve_verts = max_ii(2, fcu->totvert - fcu->totvert * remove_ratio);
+
+  BezTriple *old_bezts = fcu->bezt;
+
+  if (target_fcurve_verts != fcu->totvert) {
+    /* We don't want to limit the decimation to a certain error margin */
+    const float error_sq_max = FLT_MAX;
+    BKE_curve_decimate_bezt_array(fcu->bezt,
+                                  fcu->totvert,
+                                  12, /* 12 is the resolution of graph editor curves */
+                                  false,
+                                  SELECT,
+                                  BEZT_FLAG_TEMP_TAG,
+                                  error_sq_max,
+                                  target_fcurve_verts);
+  }
+
+  uint old_totvert = fcu->totvert;
+  fcu->bezt = NULL;
+  fcu->totvert = 0;
+
+  for (int i = 0; i < old_totvert; i++) {
+    BezTriple *bezt = (old_bezts + i);
+    if ((bezt->f2 & BEZT_FLAG_TEMP_TAG) == 0) {
+      insert_bezt_fcurve(fcu, bezt, 0);
+    }
+  }
+  /* now free the memory used by the old BezTriples */
+  if (old_bezts) {
+    MEM_freeN(old_bezts);
+  }
+}
+
+/* ---------------- */
+
 /* temp struct used for smooth_fcurve */
 typedef struct tSmooth_Bezt {
   float *h1, *h2, *h3; /* bezt->vec[0,1,2][1] */
diff --git a/source/blender/editors/include/ED_keyframes_edit.h b/source/blender/editors/include/ED_keyframes_edit.h
index 99a13dc6a87..621a325eabd 100644
--- a/source/blender/editors/include/ED_keyframes_edit.h
+++ b/source/blender/editors/include/ED_keyframes_edit.h
@@ -303,6 +303,7 @@ void clean_fcurve(struct bAnimContext *ac,
                   struct bAnimListElem *ale,
                   float thresh,
                   bool cleardefault);
+void decimate_fcurve(struct bAnimListElem *ale, float remove_ratio);
 void smooth_fcurve(struct FCurve *fcu);
 void sample_fcurve(struct FCurve *fcu);
 
diff --git a/source/blender/editors/space_graph/graph_edit.c b/source/blender/editors/space_graph/graph_edit.c
index 7ca0b6afadc..1a488118403 100644
--- a/source/blender/editors/space_graph/graph_edit.c
+++ b/source/blender/editors/space_graph/graph_edit.c
@@ -1298,6 +1298,78 @@ void GRAPH_OT_clean(wmOperatorType *ot)
   RNA_def_boolean(ot->srna, "channels", false, "Channels", "");
 }
 
+/* ******************** Decimate Keyframes Operator ************************* */
+
+static void decimate_graph_keys(bAnimContext *ac, float remove_ratio)
+{
+  ListBase anim_data = {NULL, NULL};
+  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 clean curves */
+  for (ale = anim_data.first; ale; ale = ale->next) {
+    decimate_fcurve(ale, remove_ratio);
+
+    ale->update |= ANIM_UPDATE_DEFAULT;
+  }
+
+  ANIM_animdata_update(ac, &anim_data);
+  ANIM_animdata_freelist(&anim_data);
+}
+
+/* ------------------- */
+
+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);
+
+  /* set notifier that keyframes have changed */
+  WM_event_add_notifier(C, NC_ANIMATION | ND_KEYFRAME | NA_EDITED, NULL);
+
+  return OPERATOR_FINISHED;
+}
+
+void GRAPH_OT_decimate(wmOperatorType *ot)
+{
+  /* identifiers */
+  ot->name = "Decimate Keyframes";
+  ot->idname = "GRAPH_OT_decimate";
+  ot->description =
+      "Decimate F-Curves by removing keyframes that influence the curve shape the least";
+
+  /* api callbacks */
+  ot->exec = graphkeys_decimate_exec;
+  ot->poll = graphop_editable_keyframes_poll;
+
+  /* flags */
+  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);
+}
+
 /* ******************** Bake F-Curve Operator *********************** */
 /* This operator bakes the data of the selected F-Curves to F-Points */
 
diff --git a/source/blender/editors/space_graph/graph_intern.h b/source/blender/editors/space_graph/graph_intern.h
index 320240221b5..abd8d2db04a 100644
--- a/source/blender/editors/space_graph/graph_intern.h
+++ b/source/blender/editors/space_graph/graph_intern.h
@@ -99,6 +99,7 @@ void GRAPH_OT_paste(struct wmOperatorType *ot);
 void GRAPH_OT_duplicate(struct wmOperatorType *ot);
 void GRAPH_OT_delete(struct wmOperatorType *ot);
 void GRAPH_OT_clean(struct wmOperatorType *ot);
+void GRAPH_OT_decimate(struct wmOperatorType *ot);
 void GRAPH_OT_sample(struct wmOperatorType *ot);
 void GRAPH_OT_bake(struct wmOperatorType *ot);
 void GRAPH_OT_sound_bake(struct wmOperatorType *ot);
diff --git a/source/blender/editors/space_graph/graph_ops.c b/source/blender/editors/space_graph/graph_ops.c
index c9dc9803105..17cf5dca594 100644
--- a/source/blender/editors/space_graph/graph_ops.c
+++ b/source/blender/editors/space_graph/graph_ops.c
@@ -461,6 +461,7 @@ void graphedit_operatortypes(void)
   WM_operatortype_append(GRAPH_OT_sound_bake);
   WM_operatortype_append(GRAPH_OT_smooth);
   WM_operatortype_append(GRAPH_OT_clean);
+  WM_operatortype_append(GRAPH_OT_decimate);
   WM_operatortype_append(GRAPH_OT_euler_filter);
   WM_operatortype_append(GRAPH_OT_delete);
   WM_operatortype_append(GRAPH_OT_duplicate);