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

11 files changed, 566 insertions, 41 deletions

diff --git a/source/blender/blenkernel/intern/curve_decimate.c b/source/blender/blenkernel/intern/curve_decimate.c
index cccdf830854..d569684d55c 100644
--- a/source/blender/blenkernel/intern/curve_decimate.c
+++ b/source/blender/blenkernel/intern/curve_decimate.c
@@ -269,11 +269,11 @@ uint BKE_curve_decimate_bezt_array(BezTriple *bezt_array,
     if (a == HD_VECT) { \
       a = HD_FREE; \
     } \
-    else if (a == HD_AUTO) { \
+    else if (a == HD_AUTO || a == HD_AUTO_ANIM) { \
       a = HD_ALIGN; \
     } \
     /* opposite handle */ \
-    if (b == HD_AUTO) { \
+    if (b == HD_AUTO || b == HD_AUTO_ANIM) { \
       b = HD_ALIGN; \
     } \
   } \
diff --git a/source/blender/editors/animation/keyframes_general.c b/source/blender/editors/animation/keyframes_general.c
index ffae402989c..ed5cb65c42e 100644
--- a/source/blender/editors/animation/keyframes_general.c
+++ b/source/blender/editors/animation/keyframes_general.c
@@ -328,34 +328,135 @@ void clean_fcurve(struct bAnimContext *ac, bAnimListElem *ale, float thresh, boo
 
 /* ---------------- */
 
+/* Check if the keyframe interpolation type is supported */
+static bool prepare_for_decimate(FCurve *fcu, int i)
+{
+  switch (fcu->bezt[i].ipo) {
+    case BEZT_IPO_BEZ:
+      /* We do not need to do anything here as the keyframe already has the required setting.
+       */
+      return true;
+    case BEZT_IPO_LIN:
+      /* Convert to a linear bezt curve to be able to use the decimation algorithm. */
+      fcu->bezt[i].ipo = BEZT_IPO_BEZ;
+      fcu->bezt[i].h1 = HD_FREE;
+      fcu->bezt[i].h2 = HD_FREE;
+
+      if (i != 0) {
+        float h1[3];
+        sub_v3_v3v3(h1, fcu->bezt[i - 1].vec[1], fcu->bezt[i].vec[1]);
+        mul_v3_fl(h1, 1.0f / 3.0f);
+        add_v3_v3(h1, fcu->bezt[i].vec[1]);
+        copy_v3_v3(fcu->bezt[i].vec[0], h1);
+      }
+
+      if (i + 1 != fcu->totvert) {
+        float h2[3];
+        sub_v3_v3v3(h2, fcu->bezt[i + 1].vec[1], fcu->bezt[i].vec[1]);
+        mul_v3_fl(h2, 1.0f / 3.0f);
+        add_v3_v3(h2, fcu->bezt[i].vec[1]);
+        copy_v3_v3(fcu->bezt[i].vec[2], h2);
+      }
+      return true;
+    default:
+      /* These are unsupported. */
+      return false;
+  }
+}
+
+/* Decimate the given curve segment. */
+static void decimate_fcurve_segment(FCurve *fcu,
+                                    int bezt_segment_start_idx,
+                                    int bezt_segment_len,
+                                    float remove_ratio,
+                                    float error_sq_max)
+{
+  int selected_len = bezt_segment_len;
+
+  /* Make sure that we can remove the start/end point of the segment if they
+   * are not the start/end point of the curve. BKE_curve_decimate_bezt_array
+   * has a check that prevents removal of the first and last index in the
+   * passed array. */
+  if (bezt_segment_len + bezt_segment_start_idx != fcu->totvert &&
+      prepare_for_decimate(fcu, bezt_segment_len + bezt_segment_start_idx)) {
+    bezt_segment_len++;
+  }
+  if (bezt_segment_start_idx != 0 && prepare_for_decimate(fcu, bezt_segment_start_idx - 1)) {
+    bezt_segment_start_idx--;
+    bezt_segment_len++;
+  }
+
+  const int target_fcurve_verts = ceil(bezt_segment_len - selected_len * remove_ratio);
+
+  BKE_curve_decimate_bezt_array(&fcu->bezt[bezt_segment_start_idx],
+                                bezt_segment_len,
+                                12, /* The actual resolution displayed in the viewport is dynamic
+                                       so we just pick a value that preserves the curve shape. */
+                                false,
+                                SELECT,
+                                BEZT_FLAG_TEMP_TAG,
+                                error_sq_max,
+                                target_fcurve_verts);
+}
+
 /**
  * F-Curve 'decimate' function that removes a certain ratio of curve
  * points that will affect the curves overall shape the least.
+ * If you want to remove based on a error margin, set remove_ratio to 1 and
+ * simply specify the desired error_sq_max. Otherwise, set the error margin to
+ * FLT_MAX.
  */
-void decimate_fcurve(bAnimListElem *ale, float remove_ratio)
+bool decimate_fcurve(bAnimListElem *ale, float remove_ratio, float error_sq_max)
 {
   FCurve *fcu = (FCurve *)ale->key_data;
 
   /* Check if the curve actually has any points  */
   if (fcu == NULL || fcu->bezt == NULL || fcu->totvert == 0) {
-    return;
+    return true;
   }
 
-  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);
+  /* Only decimate the individual selected curve segments. */
+  int bezt_segment_start_idx = 0;
+  int bezt_segment_len = 0;
+
+  bool selected;
+  bool can_decimate_all_selected = true;
+  bool in_segment = false;
+
+  for (int i = 0; i < fcu->totvert; i++) {
+    selected = fcu->bezt[i].f2 & SELECT;
+    /* Make sure that the temp flag is unset as we use it to determine what to remove. */
+    fcu->bezt[i].f2 &= ~BEZT_FLAG_TEMP_TAG;
+
+    if (selected && !prepare_for_decimate(fcu, i)) {
+      /* This keyframe is not supported, treat them as if they were unselected. */
+      selected = false;
+      can_decimate_all_selected = false;
+    }
+
+    if (selected) {
+      if (!in_segment) {
+        bezt_segment_start_idx = i;
+        in_segment = true;
+      }
+      bezt_segment_len++;
+    }
+    else if (in_segment) {
+      /* If the curve point is not selected then we have reached the end of the selected curve
+       * segment. */
+      decimate_fcurve_segment(
+          fcu, bezt_segment_start_idx, bezt_segment_len, remove_ratio, error_sq_max);
+      in_segment = false;
+      bezt_segment_len = 0;
+    }
+  }
+
+  /* Did the segment run to the end of the curve? */
+  if (in_segment) {
+    decimate_fcurve_segment(
+        fcu, bezt_segment_start_idx, bezt_segment_len, remove_ratio, error_sq_max);
   }
 
   uint old_totvert = fcu->totvert;
@@ -372,6 +473,8 @@ void decimate_fcurve(bAnimListElem *ale, float remove_ratio)
   if (old_bezts) {
     MEM_freeN(old_bezts);
   }
+
+  return can_decimate_all_selected;
 }
 
 /* ---------------- */
diff --git a/source/blender/editors/include/ED_keyframes_edit.h b/source/blender/editors/include/ED_keyframes_edit.h
index 8181cebfe3c..c347d75fa66 100644
--- a/source/blender/editors/include/ED_keyframes_edit.h
+++ b/source/blender/editors/include/ED_keyframes_edit.h
@@ -309,7 +309,7 @@ void clean_fcurve(struct bAnimContext *ac,
                   struct bAnimListElem *ale,
                   float thresh,
                   bool cleardefault);
-void decimate_fcurve(struct bAnimListElem *ale, float remove_ratio);
+bool decimate_fcurve(struct bAnimListElem *ale, float remove_ratio, float error_sq_max);
 void smooth_fcurve(struct FCurve *fcu);
 void sample_fcurve(struct FCurve *fcu);
 
diff --git a/source/blender/editors/include/UI_view2d.h b/source/blender/editors/include/UI_view2d.h
index 0dbf3c710d6..e34f40d057d 100644
--- a/source/blender/editors/include/UI_view2d.h
+++ b/source/blender/editors/include/UI_view2d.h
@@ -220,6 +220,7 @@ bool UI_view2d_view_to_region_rcti_clip(struct View2D *v2d,
 struct View2D *UI_view2d_fromcontext(const struct bContext *C);
 struct View2D *UI_view2d_fromcontext_rwin(const struct bContext *C);
 
+void UI_view2d_scroller_size_get(const struct View2D *v2d, float *r_x, float *r_y);
 void UI_view2d_scale_get(struct View2D *v2d, float *r_x, float *r_y);
 float UI_view2d_scale_get_x(const struct View2D *v2d);
 float UI_view2d_scale_get_y(const struct View2D *v2d);
diff --git a/source/blender/editors/interface/interface_region_hud.c b/source/blender/editors/interface/interface_region_hud.c
index 54bdbe0ec6e..fa471441cc9 100644
--- a/source/blender/editors/interface/interface_region_hud.c
+++ b/source/blender/editors/interface/interface_region_hud.c
@@ -265,6 +265,14 @@ static ARegion *hud_region_add(ScrArea *sa)
   ar->overlap = true;
   ar->flag |= RGN_FLAG_DYNAMIC_SIZE;
 
+  if (ar_win) {
+    float x, y;
+
+    UI_view2d_scroller_size_get(&ar_win->v2d, &x, &y);
+    ar->runtime.offset_x = x;
+    ar->runtime.offset_y = y;
+  }
+
   return ar;
 }
 
diff --git a/source/blender/editors/interface/view2d.c b/source/blender/editors/interface/view2d.c
index b1a060089ee..a3f84e7bdd0 100644
--- a/source/blender/editors/interface/view2d.c
+++ b/source/blender/editors/interface/view2d.c
@@ -174,12 +174,9 @@ static void view2d_masks(View2D *v2d, bool check_scrollers, const rcti *mask_scr
    * - if they overlap, they must not occupy the corners (which are reserved for other widgets)
    */
   if (scroll) {
-    const int scroll_width = (v2d->scroll & V2D_SCROLL_VERTICAL_HANDLES) ?
-                                 V2D_SCROLL_HANDLE_WIDTH :
-                                 V2D_SCROLL_WIDTH;
-    const int scroll_height = (v2d->scroll & V2D_SCROLL_HORIZONTAL_HANDLES) ?
-                                  V2D_SCROLL_HANDLE_HEIGHT :
-                                  V2D_SCROLL_HEIGHT;
+    float scroll_width, scroll_height;
+
+    UI_view2d_scroller_size_get(v2d, &scroll_width, &scroll_height);
 
     /* vertical scroller */
     if (scroll & V2D_SCROLL_LEFT) {
@@ -1939,6 +1936,31 @@ View2D *UI_view2d_fromcontext_rwin(const bContext *C)
   return &(region->v2d);
 }
 
+/* Get scrollbar sizes of the current 2D view. The size will be zero if the view has its scrollbars
+ * disabled. */
+void UI_view2d_scroller_size_get(const View2D *v2d, float *r_x, float *r_y)
+{
+  int scroll = view2d_scroll_mapped(v2d->scroll);
+
+  if (r_x) {
+    if (scroll & V2D_SCROLL_VERTICAL) {
+      *r_x = (scroll & V2D_SCROLL_VERTICAL_HANDLES) ? V2D_SCROLL_HANDLE_WIDTH : V2D_SCROLL_WIDTH;
+    }
+    else {
+      *r_x = 0;
+    }
+  }
+  if (r_y) {
+    if (scroll & V2D_SCROLL_HORIZONTAL) {
+      *r_y = (scroll & V2D_SCROLL_HORIZONTAL_HANDLES) ? V2D_SCROLL_HANDLE_HEIGHT :
+                                                        V2D_SCROLL_HEIGHT;
+    }
+    else {
+      *r_y = 0;
+    }
+  }
+}
+
 /**
  * Calculate the scale per-axis of the drawing-area
  *
diff --git a/source/blender/editors/screen/area.c b/source/blender/editors/screen/area.c
index ccee88eb0d6..36a2b4c2893 100644
--- a/source/blender/editors/screen/area.c
+++ b/source/blender/editors/screen/area.c
@@ -1280,11 +1280,12 @@ static void region_rect_recursive(
      */
     const int size_min[2] = {UI_UNIT_X, UI_UNIT_Y};
     rcti overlap_remainder_margin = *overlap_remainder;
+
     BLI_rcti_resize(&overlap_remainder_margin,
                     max_ii(0, BLI_rcti_size_x(overlap_remainder) - UI_UNIT_X / 2),
                     max_ii(0, BLI_rcti_size_y(overlap_remainder) - UI_UNIT_Y / 2));
-    ar->winrct.xmin = overlap_remainder_margin.xmin;
-    ar->winrct.ymin = overlap_remainder_margin.ymin;
+    ar->winrct.xmin = overlap_remainder_margin.xmin + ar->runtime.offset_x;
+    ar->winrct.ymin = overlap_remainder_margin.ymin + ar->runtime.offset_y;
     ar->winrct.xmax = ar->winrct.xmin + prefsizex - 1;
     ar->winrct.ymax = ar->winrct.ymin + prefsizey - 1;
 
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);
 }
diff --git a/source/blender/makesdna/DNA_screen_types.h b/source/blender/makesdna/DNA_screen_types.h
index ec42e9bd04f..d3c5a707b44 100644
--- a/source/blender/makesdna/DNA_screen_types.h
+++ b/source/blender/makesdna/DNA_screen_types.h
@@ -382,6 +382,9 @@ typedef struct ARegion_Runtime {
    *
    * Lazy initialize, zero'd when unset, relative to #ARegion.winrct x/y min. */
   rcti visible_rect;
+
+  /* The offset needed to not overlap with window scrollbars. Only used by HUD regions for now. */
+  int offset_x, offset_y;
 } ARegion_Runtime;
 
 typedef struct ARegion {
diff --git a/source/blender/makesrna/intern/rna_space.c b/source/blender/makesrna/intern/rna_space.c
index 89c6c05021e..7b0f3bf708c 100644
--- a/source/blender/makesrna/intern/rna_space.c
+++ b/source/blender/makesrna/intern/rna_space.c
@@ -4954,7 +4954,7 @@ static void rna_def_space_graph(BlenderRNA *brna)
   RNA_def_struct_sdna(srna, "SpaceGraph");
   RNA_def_struct_ui_text(srna, "Space Graph Editor", "Graph Editor space data");
 
-  rna_def_space_generic_show_region_toggles(srna, (1 << RGN_TYPE_UI));
+  rna_def_space_generic_show_region_toggles(srna, (1 << RGN_TYPE_UI) | (1 << RGN_TYPE_HUD));
 
   /* mode */
   prop = RNA_def_property(srna, "mode", PROP_ENUM, PROP_NONE);