GPencil: New Simplify modifier mode Sample and operator

This mode simplify the stroke doing a resampling of the points and generate new geometry at the distance defined.

Sample function developed by @NicksBest

New Resample Stroke operator

This operator recreates the stroke geometry with a predefined length between points.

The operator uses the same code used in Simplify modifier.

Reviewers: @mendio

10 files changed, 412 insertions, 17 deletions

diff --git a/release/scripts/startup/bl_ui/properties_data_modifier.py b/release/scripts/startup/bl_ui/properties_data_modifier.py
index 66e96199b08..5595408f1da 100644
--- a/release/scripts/startup/bl_ui/properties_data_modifier.py
+++ b/release/scripts/startup/bl_ui/properties_data_modifier.py
@@ -1785,13 +1785,13 @@ class DATA_PT_gpencil_modifiers(ModifierButtonsPanel, Panel):
 
         col = split.column()
         col.label(text="Settings:")
-        row = col.row(align=True)
-        row.enabled = md.mode == 'FIXED'
-        row.prop(md, "step")
 
-        row = col.row(align=True)
-        row.enabled = not md.mode == 'FIXED'
-        row.prop(md, "factor")
+        if md.mode == 'FIXED':
+            col.prop(md, "step")
+        elif md.mode == 'ADAPTIVE':
+            col.prop(md, "factor")
+        elif md.mode == 'SAMPLE':
+            col.prop(md, "length")
 
         col = layout.column()
         col.separator()
diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py
index 2eeb13310fa..c7fc79aa8e8 100644
--- a/release/scripts/startup/bl_ui/space_view3d.py
+++ b/release/scripts/startup/bl_ui/space_view3d.py
@@ -4447,6 +4447,7 @@ class VIEW3D_MT_gpencil_simplify(Menu):
         layout = self.layout
         layout.operator("gpencil.stroke_simplify_fixed", text="Fixed")
         layout.operator("gpencil.stroke_simplify", text="Adaptive")
+        layout.operator("gpencil.stroke_sample", text="Sample")
 
 
 class VIEW3D_MT_paint_gpencil(Menu):
@@ -6322,8 +6323,7 @@ class VIEW3D_MT_gpencil_edit_context_menu(Menu):
         if is_3d_view:
             layout.menu("GPENCIL_MT_cleanup")
 
-        layout.operator("gpencil.stroke_simplify_fixed", text="Simplify")
-        layout.operator("gpencil.stroke_simplify", text="Simplify Adaptive")
+        layout.menu("VIEW3D_MT_gpencil_simplify")
         layout.operator("gpencil.stroke_merge", text="Merge")
         layout.menu("VIEW3D_MT_edit_gpencil_delete")
 
diff --git a/source/blender/blenkernel/BKE_gpencil.h b/source/blender/blenkernel/BKE_gpencil.h
index 3dfd6eb466c..997f1fc82e1 100644
--- a/source/blender/blenkernel/BKE_gpencil.h
+++ b/source/blender/blenkernel/BKE_gpencil.h
@@ -216,6 +216,7 @@ void BKE_gpencil_stroke_2d_flat_ref(const struct bGPDspoint *ref_points,
 
 void BKE_gpencil_transform(struct bGPdata *gpd, float mat[4][4]);
 
+bool BKE_gpencil_sample_stroke(struct bGPDstroke *gps, const float dist, const bool select);
 bool BKE_gpencil_smooth_stroke(struct bGPDstroke *gps, int i, float inf);
 bool BKE_gpencil_smooth_stroke_strength(struct bGPDstroke *gps, int point_index, float influence);
 bool BKE_gpencil_smooth_stroke_thickness(struct bGPDstroke *gps, int point_index, float influence);
diff --git a/source/blender/blenkernel/intern/gpencil.c b/source/blender/blenkernel/intern/gpencil.c
index efdb35d4409..b9e7b155941 100644
--- a/source/blender/blenkernel/intern/gpencil.c
+++ b/source/blender/blenkernel/intern/gpencil.c
@@ -1404,6 +1404,324 @@ void BKE_gpencil_dvert_ensure(bGPDstroke *gps)
 
 /* ************************************************** */
 
+static void stroke_defvert_create_nr_list(MDeformVert *dv_list,
+                                          int count,
+                                          ListBase *result,
+                                          int *totweight)
+{
+  LinkData *ld;
+  MDeformVert *dv;
+  MDeformWeight *dw;
+  int i, j;
+  int tw = 0;
+  for (i = 0; i < count; i++) {
+    dv = &dv_list[i];
+
+    /* find def_nr in list, if not exist, then create one */
+    for (j = 0; j < dv->totweight; j++) {
+      int found = 0;
+      dw = &dv->dw[j];
+      for (ld = result->first; ld; ld = ld->next) {
+        if (ld->data == (void *)dw->def_nr) {
+          found = 1;
+          break;
+        }
+      }
+      if (!found) {
+        ld = MEM_callocN(sizeof(LinkData), "def_nr_item");
+        ld->data = (void *)dw->def_nr;
+        BLI_addtail(result, ld);
+        tw++;
+      }
+    }
+  }
+
+  *totweight = tw;
+}
+
+MDeformVert *stroke_defvert_new_count(int count, int totweight, ListBase *def_nr_list)
+{
+  int i, j;
+  LinkData *ld;
+  MDeformVert *dst = MEM_mallocN(count * sizeof(MDeformVert), "new_deformVert");
+
+  dst->totweight = totweight;
+
+  for (i = 0; i < count; i++) {
+    dst[i].dw = MEM_mallocN(sizeof(MDeformWeight) * totweight, "new_deformWeight");
+    j = 0;
+    /* re-assign deform groups */
+    for (ld = def_nr_list->first; ld; ld = ld->next) {
+      dst[i].dw[j].def_nr = (int)ld->data;
+      j++;
+    }
+  }
+
+  return dst;
+}
+
+static float stroke_defvert_get_nr_weight(MDeformVert *dv, int def_nr)
+{
+  int i;
+  for (i = 0; i < dv->totweight; i++) {
+    if (dv->dw[i].def_nr == def_nr) {
+      return dv->dw[i].weight;
+    }
+  }
+  return 0.0f;
+}
+
+static void stroke_interpolate_deform_weights(
+    bGPDstroke *gps, int index_from, int index_to, float ratio, MDeformVert *vert)
+{
+  MDeformVert *vl = &gps->dvert[index_from];
+  MDeformVert *vr = &gps->dvert[index_to];
+  int i;
+
+  for (i = 0; i < vert->totweight; i++) {
+    float wl = stroke_defvert_get_nr_weight(vl, vert->dw[i].def_nr);
+    float wr = stroke_defvert_get_nr_weight(vr, vert->dw[i].def_nr);
+    vert->dw[i].weight = interpf(wr, wl, ratio);
+  }
+}
+
+static int stroke_march_next_point(const bGPDstroke *gps,
+                                   const int index_next_pt,
+                                   const float *current,
+                                   const float dist,
+                                   float *result,
+                                   float *pressure,
+                                   float *strength,
+                                   float *ratio_result,
+                                   int *index_from,
+                                   int *index_to)
+{
+  float remaining_till_next = 0.0f;
+  float remaining_march = dist;
+  float step_start[3];
+  float point[3];
+  int next_point_index = index_next_pt;
+  bGPDspoint *pt = NULL;
+
+  if (!(next_point_index < gps->totpoints)) {
+    return -1;
+  }
+
+  copy_v3_v3(step_start, current);
+  pt = &gps->points[next_point_index];
+  copy_v3_v3(point, &pt->x);
+  remaining_till_next = len_v3v3(point, step_start);
+
+  while (remaining_till_next < remaining_march) {
+    remaining_march -= remaining_till_next;
+    pt = &gps->points[next_point_index];
+    copy_v3_v3(point, &pt->x);
+    copy_v3_v3(step_start, point);
+    next_point_index++;
+    if (!(next_point_index < gps->totpoints)) {
+      next_point_index = gps->totpoints - 1;
+      break;
+    }
+    pt = &gps->points[next_point_index];
+    copy_v3_v3(point, &pt->x);
+    remaining_till_next = len_v3v3(point, step_start);
+  }
+  if (remaining_till_next < remaining_march) {
+    pt = &gps->points[next_point_index];
+    copy_v3_v3(result, &pt->x);
+    *pressure = gps->points[next_point_index].pressure;
+    *strength = gps->points[next_point_index].strength;
+
+    *index_from = next_point_index - 1;
+    *index_to = next_point_index;
+    *ratio_result = 1.0f;
+
+    return 0;
+  }
+  else {
+    float ratio = remaining_march / remaining_till_next;
+    interp_v3_v3v3(result, step_start, point, ratio);
+    *pressure = interpf(
+        gps->points[next_point_index].pressure, gps->points[next_point_index - 1].pressure, ratio);
+    *strength = interpf(
+        gps->points[next_point_index].strength, gps->points[next_point_index - 1].strength, ratio);
+
+    *index_from = next_point_index - 1;
+    *index_to = next_point_index;
+    *ratio_result = ratio;
+
+    return next_point_index;
+  }
+}
+
+static int stroke_march_next_point_no_interp(const bGPDstroke *gps,
+                                             const int index_next_pt,
+                                             const float *current,
+                                             const float dist,
+                                             float *result)
+{
+  float remaining_till_next = 0.0f;
+  float remaining_march = dist;
+  float step_start[3];
+  float point[3];
+  int next_point_index = index_next_pt;
+  bGPDspoint *pt = NULL;
+
+  if (!(next_point_index < gps->totpoints)) {
+    return -1;
+  }
+
+  copy_v3_v3(step_start, current);
+  pt = &gps->points[next_point_index];
+  copy_v3_v3(point, &pt->x);
+  remaining_till_next = len_v3v3(point, step_start);
+
+  while (remaining_till_next < remaining_march) {
+    remaining_march -= remaining_till_next;
+    pt = &gps->points[next_point_index];
+    copy_v3_v3(point, &pt->x);
+    copy_v3_v3(step_start, point);
+    next_point_index++;
+    if (!(next_point_index < gps->totpoints)) {
+      next_point_index = gps->totpoints - 1;
+      break;
+    }
+    pt = &gps->points[next_point_index];
+    copy_v3_v3(point, &pt->x);
+    remaining_till_next = len_v3v3(point, step_start);
+  }
+  if (remaining_till_next < remaining_march) {
+    pt = &gps->points[next_point_index];
+    copy_v3_v3(result, &pt->x);
+    return 0;
+  }
+  else {
+    float ratio = remaining_march / remaining_till_next;
+    interp_v3_v3v3(result, step_start, point, ratio);
+    return next_point_index;
+  }
+}
+
+static int stroke_march_count(const bGPDstroke *gps, const float dist)
+{
+  int point_count = 0;
+  float point[3];
+  int next_point_index = 1;
+  bGPDspoint *pt = NULL;
+
+  pt = &gps->points[0];
+  copy_v3_v3(point, &pt->x);
+  point_count++;
+
+  while ((next_point_index = stroke_march_next_point_no_interp(
+              gps, next_point_index, point, dist, point)) > -1) {
+    point_count++;
+    if (next_point_index == 0) {
+      break; /* last point finished */
+    }
+  }
+  return point_count;
+}
+
+/**
+ * Resample a stroke
+ * \param gps: Stroke to sample
+ * \param dist: Distance of one segment
+ */
+bool BKE_gpencil_sample_stroke(bGPDstroke *gps, const float dist, const bool select)
+{
+  bGPDspoint *pt = gps->points;
+  bGPDspoint *pt1 = NULL;
+  bGPDspoint *pt2 = NULL;
+  int i;
+  LinkData *ld;
+  ListBase def_nr_list = {0};
+
+  if (gps->totpoints < 2 || dist < FLT_EPSILON) {
+    return false;
+  }
+  /* TODO: Implement feature point preservation. */
+  int count = stroke_march_count(gps, dist);
+
+  bGPDspoint *new_pt = MEM_callocN(sizeof(bGPDspoint) * count, "gp_stroke_points_sampled");
+  MDeformVert *new_dv = NULL;
+
+  int result_totweight;
+
+  if (gps->dvert != NULL) {
+    stroke_defvert_create_nr_list(gps->dvert, count, &def_nr_list, &result_totweight);
+    new_dv = stroke_defvert_new_count(count, result_totweight, &def_nr_list);
+  }
+
+  int next_point_index = 1;
+  i = 0;
+  float pressure, strength, ratio_result;
+  int index_from, index_to;
+  float last_coord[3];
+
+  /*  1st point is always at the start */
+  pt1 = &gps->points[0];
+  copy_v3_v3(last_coord, &pt1->x);
+  pt2 = &new_pt[i];
+  copy_v3_v3(&pt2->x, last_coord);
+  new_pt[i].pressure = pt[0].pressure;
+  new_pt[i].strength = pt[0].strength;
+  if (select) {
+    new_pt[i].flag |= GP_SPOINT_SELECT;
+  }
+  i++;
+
+  if (new_dv) {
+    stroke_interpolate_deform_weights(gps, 0, 0, 0, &new_dv[0]);
+  }
+
+  /*  the rest */
+  while ((next_point_index = stroke_march_next_point(gps,
+                                                     next_point_index,
+                                                     last_coord,
+                                                     dist,
+                                                     last_coord,
+                                                     &pressure,
+                                                     &strength,
+                                                     &ratio_result,
+                                                     &index_from,
+                                                     &index_to)) > -1) {
+    pt2 = &new_pt[i];
+    copy_v3_v3(&pt2->x, last_coord);
+    new_pt[i].pressure = pressure;
+    new_pt[i].strength = strength;
+    if (select) {
+      new_pt[i].flag |= GP_SPOINT_SELECT;
+    }
+
+    if (new_dv) {
+      stroke_interpolate_deform_weights(gps, index_from, index_to, ratio_result, &new_dv[i]);
+    }
+
+    i++;
+    if (next_point_index == 0) {
+      break; /* last point finished */
+    }
+  }
+
+  gps->points = new_pt;
+  gps->totpoints = i;
+  MEM_freeN(pt); /* original */
+
+  if (new_dv) {
+    BKE_gpencil_free_stroke_weights(gps);
+    while (ld = BLI_pophead(&def_nr_list)) {
+      MEM_freeN(ld);
+    }
+    gps->dvert = new_dv;
+  }
+
+  gps->flag |= GP_STROKE_RECALC_GEOMETRY;
+  gps->tot_triangles = 0;
+
+  return true;
+}
+
 /**
  * Apply smooth to stroke point
  * \param gps: Stroke to smooth
diff --git a/source/blender/editors/gpencil/gpencil_edit.c b/source/blender/editors/gpencil/gpencil_edit.c
index f7c90d44d95..01b62dce3c2 100644
--- a/source/blender/editors/gpencil/gpencil_edit.c
+++ b/source/blender/editors/gpencil/gpencil_edit.c
@@ -3847,6 +3847,54 @@ void GPENCIL_OT_stroke_simplify_fixed(wmOperatorType *ot)
   RNA_def_property_flag(prop, PROP_SKIP_SAVE);
 }
 
+/* ** Resample stroke *** */
+static int gp_stroke_sample_exec(bContext *C, wmOperator *op)
+{
+  bGPdata *gpd = ED_gpencil_data_get_active(C);
+  const float length = RNA_float_get(op->ptr, "length");
+
+  /* sanity checks */
+  if (ELEM(NULL, gpd)) {
+    return OPERATOR_CANCELLED;
+  }
+
+  /* Go through each editable + selected stroke */
+  GP_EDITABLE_STROKES_BEGIN (gpstroke_iter, C, gpl, gps) {
+    if (gps->flag & GP_STROKE_SELECT) {
+      BKE_gpencil_sample_stroke(gps, length, true);
+    }
+  }
+  GP_EDITABLE_STROKES_END(gpstroke_iter);
+
+  /* notifiers */
+  DEG_id_tag_update(&gpd->id, ID_RECALC_TRANSFORM | ID_RECALC_GEOMETRY);
+  WM_event_add_notifier(C, NC_GPENCIL | ND_DATA | NA_EDITED, NULL);
+
+  return OPERATOR_FINISHED;
+}
+
+void GPENCIL_OT_stroke_sample(wmOperatorType *ot)
+{
+  PropertyRNA *prop;
+
+  /* identifiers */
+  ot->name = "Sample Stroke";
+  ot->idname = "GPENCIL_OT_stroke_sample";
+  ot->description = "Sample stroke points to predefined segment length";
+
+  /* api callbacks */
+  ot->exec = gp_stroke_sample_exec;
+  ot->poll = gp_active_layer_poll;
+
+  /* flags */
+  ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+  /* properties */
+  prop = RNA_def_float(ot->srna, "length", 0.1f, 0.0f, 100.0f, "Length", "", 0.0f, 100.0f);
+  /* avoid re-using last var */
+  RNA_def_property_flag(prop, PROP_SKIP_SAVE);
+}
+
 /* ******************* Stroke trim ************************** */
 static int gp_stroke_trim_exec(bContext *C, wmOperator *UNUSED(op))
 {
diff --git a/source/blender/editors/gpencil/gpencil_intern.h b/source/blender/editors/gpencil/gpencil_intern.h
index 3776dd09eb5..2a608d44a0b 100644
--- a/source/blender/editors/gpencil/gpencil_intern.h
+++ b/source/blender/editors/gpencil/gpencil_intern.h
@@ -486,6 +486,7 @@ void GPENCIL_OT_stroke_simplify_fixed(struct wmOperatorType *ot);
 void GPENCIL_OT_stroke_separate(struct wmOperatorType *ot);
 void GPENCIL_OT_stroke_split(struct wmOperatorType *ot);
 void GPENCIL_OT_stroke_smooth(struct wmOperatorType *ot);
+void GPENCIL_OT_stroke_sample(struct wmOperatorType *ot);
 void GPENCIL_OT_stroke_merge(struct wmOperatorType *ot);
 void GPENCIL_OT_stroke_cutter(struct wmOperatorType *ot);
 void GPENCIL_OT_stroke_trim(struct wmOperatorType *ot);
diff --git a/source/blender/editors/gpencil/gpencil_ops.c b/source/blender/editors/gpencil/gpencil_ops.c
index 54e99802c54..acdf5c2be4f 100644
--- a/source/blender/editors/gpencil/gpencil_ops.c
+++ b/source/blender/editors/gpencil/gpencil_ops.c
@@ -314,6 +314,7 @@ void ED_operatortypes_gpencil(void)
   WM_operatortype_append(GPENCIL_OT_stroke_separate);
   WM_operatortype_append(GPENCIL_OT_stroke_split);
   WM_operatortype_append(GPENCIL_OT_stroke_smooth);
+  WM_operatortype_append(GPENCIL_OT_stroke_sample);
   WM_operatortype_append(GPENCIL_OT_stroke_merge);
   WM_operatortype_append(GPENCIL_OT_stroke_cutter);
   WM_operatortype_append(GPENCIL_OT_stroke_trim);
diff --git a/source/blender/gpencil_modifiers/intern/MOD_gpencilsimplify.c b/source/blender/gpencil_modifiers/intern/MOD_gpencilsimplify.c
index 746a689c08e..06f6f012818 100644
--- a/source/blender/gpencil_modifiers/intern/MOD_gpencilsimplify.c
+++ b/source/blender/gpencil_modifiers/intern/MOD_gpencilsimplify.c
@@ -66,7 +66,7 @@ static void deformStroke(GpencilModifierData *md,
                                       mmd->layername,
                                       mmd->pass_index,
                                       mmd->layer_pass,
-                                      4,
+                                      mmd->mode == GP_SIMPLIFY_SAMPLE ? 3 : 4,
                                       gpl,
                                       gps,
                                       mmd->flag & GP_SIMPLIFY_INVERT_LAYER,
@@ -75,14 +75,25 @@ static void deformStroke(GpencilModifierData *md,
     return;
   }
 
-  if (mmd->mode == GP_SIMPLIFY_FIXED) {
-    for (int i = 0; i < mmd->step; i++) {
-      BKE_gpencil_simplify_fixed(gps);
+  /* Select simplification mode. */
+  switch (mmd->mode) {
+    case GP_SIMPLIFY_FIXED: {
+      for (int i = 0; i < mmd->step; i++) {
+        BKE_gpencil_simplify_fixed(gps);
+      }
+      break;
     }
-  }
-  else {
-    /* simplify stroke using Ramer-Douglas-Peucker algorithm */
-    BKE_gpencil_simplify_stroke(gps, mmd->factor);
+    case GP_SIMPLIFY_ADAPTIVE: {
+      /* simplify stroke using Ramer-Douglas-Peucker algorithm */
+      BKE_gpencil_simplify_stroke(gps, mmd->factor);
+      break;
+    }
+    case GP_SIMPLIFY_SAMPLE: {
+      BKE_gpencil_sample_stroke(gps, mmd->length, false);
+      break;
+    }
+    default:
+      break;
   }
 }
 
diff --git a/source/blender/makesdna/DNA_gpencil_modifier_types.h b/source/blender/makesdna/DNA_gpencil_modifier_types.h
index 47347753f42..3acd7d6de12 100644
--- a/source/blender/makesdna/DNA_gpencil_modifier_types.h
+++ b/source/blender/makesdna/DNA_gpencil_modifier_types.h
@@ -502,7 +502,8 @@ typedef struct SimplifyGpencilModifierData {
   short step;
   /** Custom index for passes. */
   int layer_pass;
-  char _pad[4];
+  /* Sample length */
+  float length;
 } SimplifyGpencilModifierData;
 
 typedef enum eSimplifyGpencil_Flag {
@@ -516,6 +517,8 @@ typedef enum eSimplifyGpencil_Mode {
   GP_SIMPLIFY_FIXED = 0,
   /* Use RDP algorithm */
   GP_SIMPLIFY_ADAPTIVE = 1,
+  /* Sample the stroke using a fixed length */
+  GP_SIMPLIFY_SAMPLE = 2,
 } eSimplifyGpencil_Mode;
 
 typedef struct OffsetGpencilModifierData {
diff --git a/source/blender/makesrna/intern/rna_gpencil_modifier.c b/source/blender/makesrna/intern/rna_gpencil_modifier.c
index 754c443e7e6..ed23e603bec 100644
--- a/source/blender/makesrna/intern/rna_gpencil_modifier.c
+++ b/source/blender/makesrna/intern/rna_gpencil_modifier.c
@@ -617,6 +617,11 @@ static void rna_def_modifier_gpencilsimplify(BlenderRNA *brna)
        ICON_IPO_EASE_IN_OUT,
        "Adaptive",
        "Use a RDP algorithm to simplify"},
+      {GP_SIMPLIFY_SAMPLE,
+       "SAMPLE",
+       ICON_IPO_EASE_IN_OUT,
+       "Sample",
+       "Sample a curve using a fixed length"},
       {0, NULL, 0, NULL, NULL},
   };
 
@@ -675,6 +680,13 @@ static void rna_def_modifier_gpencilsimplify(BlenderRNA *brna)
   RNA_def_property_range(prop, 1, 50);
   RNA_def_property_ui_text(prop, "Iterations", "Number of times to apply simplify");
   RNA_def_property_update(prop, 0, "rna_GpencilModifier_update");
+
+  /* Sample */
+  prop = RNA_def_property(srna, "length", PROP_FLOAT, PROP_NONE);
+  RNA_def_property_float_sdna(prop, NULL, "length");
+  RNA_def_property_range(prop, 0, 10);
+  RNA_def_property_ui_text(prop, "Length", "Length of each segment");
+  RNA_def_property_update(prop, 0, "rna_GpencilModifier_update");
 }
 
 static void rna_def_modifier_gpencilthick(BlenderRNA *brna)