GPencil: Add more types of stroke extensions when filling

The motivation for this change: while working on an animation recently, I found that there are some gaps that won't close easily via stroke extension or leak size checking. In D14698, I attempted to address this by changing the algorithm of the raster-space flood fill. This patch attempts to address the same issue in vector space by adding two new cases where stroke extensions are added, as suggested by @frogstomp:

  # **Points of high curvature:** when the curvature at a point is high enough that it's hard to visually distinguish between it and an endpoint, add a stroke extension out along the normal (pointing in the opposite direction of the stroke's acceleration.) This addresses cases where technically the endpoint points up, but there's a sharp corner right below it that should extend to connect.

  # **Stroke endpoints within a radius**: when two endpoints are close together, regardless of the angle they make, connect them if they are within a radius. This addresses cases like where the two endpoints have effectively parallel tangents, so extensions won't close the gap.

Reviewed By: antoniov, mendio, frogstomp

Differential Revision: https://developer.blender.org/D14809

release/scripts/startup/bl_ui/space_view3d_toolbar.py

@@ -1605,6 +1605,10 @@ class VIEW3D_PT_tools_grease_pencil_brush_advanced(View3DPanel, Panel):
                 row = col.row(align=True)
                 row.prop(gp_settings, "fill_layer_mode", text="Layers")
 
+                col.separator()
+                row = col.row(align=True)
+                row.prop(gp_settings, "fill_extend_mode")
+
                 col.separator()
                 row = col.row(align=True)
                 row.prop(gp_settings, "extend_stroke_factor")

source/blender/editors/gpencil/gpencil_fill.c

@@ -140,6 +140,8 @@ typedef struct tGPDfill {
   int fill_simplylvl;
   /** boundary limits drawing mode */
   int fill_draw_mode;
+  /** types of extensions **/
+  int fill_extend_mode;
   /* scaling factor */
   float fill_factor;
 
@@ -197,7 +199,10 @@ static void gpencil_delete_temp_stroke_extension(tGPDfill *tgpf, const bool all_
     for (bGPDframe *gpf = init_gpf; gpf; gpf = gpf->next) {
       LISTBASE_FOREACH_MUTABLE (bGPDstroke *, gps, &gpf->strokes) {
         /* free stroke */
-        if ((gps->flag & GP_STROKE_NOFILL) && (gps->flag & GP_STROKE_TAG)) {
+        if (
+            (gps->flag & GP_STROKE_NOFILL) &&
+            (gps->flag & GP_STROKE_TAG || gps->flag & GP_STROKE_HELP))
+        {
           BLI_remlink(&gpf->strokes, gps);
           BKE_gpencil_free_stroke(gps);
         }
@@ -209,6 +214,70 @@ static void gpencil_delete_temp_stroke_extension(tGPDfill *tgpf, const bool all_
   }
 }
 
+static bool extended_bbox_overlap(float min1[3],
+                                  float max1[3],
+                                  float min2[3],
+                                  float max2[3],
+                                  float extend)
+{
+  for (int axis = 0; axis < 3; axis++) {
+    float intersection_min = max_ff(min1[axis], min2[axis]) - extend;
+    float intersection_max = min_ff(max1[axis], max2[axis]) + extend;
+    if (intersection_min > intersection_max) {
+      return false;
+    }
+  }
+  return true;
+}
+
+static void add_stroke_extension(bGPDframe *gpf,
+                                 bGPDstroke *gps,
+                                 float p1[3],
+                                 float p2[3])
+{
+  bGPDstroke *gps_new = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
+  gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_TAG;
+  BLI_addtail(&gpf->strokes, gps_new);
+
+  bGPDspoint *pt = &gps_new->points[0];
+  copy_v3_v3(&pt->x, p1);
+  pt->strength = 1.0f;
+  pt->pressure = 1.0f;
+
+  pt = &gps_new->points[1];
+  copy_v3_v3(&pt->x, p2);
+  pt->strength = 1.0f;
+  pt->pressure = 1.0f;
+}
+
+static void add_endpoint_radius_help(bGPDframe *gpf,
+                                     bGPDstroke *gps,
+                                     const float endpoint[3],
+                                     const float radius,
+                                     const bool focused)
+{
+  float circumference = 2.0f * M_PI * radius;
+  float vertex_spacing = 0.005f;
+  int num_vertices = min_ii(max_ii((int)ceilf(circumference / vertex_spacing), 3), 40);
+
+  bGPDstroke *gps_new = BKE_gpencil_stroke_new(gps->mat_nr, num_vertices, gps->thickness);
+  gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_CYCLIC | GP_STROKE_HELP;
+  if (focused) {
+    gps_new->flag |= GP_STROKE_TAG;
+  }
+  BLI_addtail(&gpf->strokes, gps_new);
+
+  for (int i = 0; i < num_vertices; i++) {
+    float angle = ((float)i / (float)num_vertices) * 2.0f * M_PI;
+    bGPDspoint *pt = &gps_new->points[i];
+    pt->x = endpoint[0] + radius * cosf(angle);
+    pt->y = endpoint[1];
+    pt->z = endpoint[2] + radius * sinf(angle);
+    pt->strength = 1.0f;
+    pt->pressure = 1.0f;
+  }
+}
+
 static void extrapolate_points_by_length(bGPDspoint *a,
                                          bGPDspoint *b,
                                          float length,
@@ -235,6 +304,9 @@ static void gpencil_create_extensions(tGPDfill *tgpf)
   const int gpl_active_index = BLI_findindex(&gpd->layers, gpl_active);
   BLI_assert(gpl_active_index >= 0);
 
+  float connection_dist = tgpf->fill_extend_fac * 0.1f;
+  GSet *connected_endpoints = BLI_gset_ptr_new(__func__);
+
   LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
     if (gpl->flag & GP_LAYER_HIDE) {
       continue;
@@ -266,41 +338,161 @@ static void gpencil_create_extensions(tGPDfill *tgpf)
         continue;
       }
 
-      /* Extend start. */
-      bGPDspoint *pt0 = &gps->points[1];
-      bGPDspoint *pt1 = &gps->points[0];
-      bGPDstroke *gps_new = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
-      gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_TAG;
-      BLI_addtail(&gpf->strokes, gps_new);
+      /* Find points of high curvature. */
+      float tan1[3];
+      float tan2[3];
+      float d1;
+      float d2;
+      float total_length = 0.f;
+      for (int i = 1; i < gps->totpoints; i++) {
+        if (i > 1) {
+          copy_v3_v3(tan1, tan2);
+          d1 = d2;
+        }
+        bGPDspoint *pt1 = &gps->points[i - 1];
+        bGPDspoint *pt2 = &gps->points[i];
+        sub_v3_v3v3(tan2, &pt2->x, &pt1->x);
+        d2 = normalize_v3(tan2);
+        total_length += d2;
+        if (i > 1) {
+          if (tgpf->fill_extend_mode == GP_FILL_EMODE_CIRCLES) {
+            continue;
+          }
+          float curvature[3];
+          sub_v3_v3v3(curvature, tan2, tan1);
+          float k = normalize_v3(curvature);
+          k /= min_ff(d1, d2);
+          float radius = 1.f / k;
+          /*
+           * The smaller the radius of curvature, the sharper the corner.
+           * The thicker the line, the larger the radius of curvature it
+           * takes to be visually indistinguishable from an endpoint.
+           */
+          float min_radius = gps->thickness * 0.0001f;
 
-      bGPDspoint *pt = &gps_new->points[0];
-      copy_v3_v3(&pt->x, &pt1->x);
-      pt->strength = 1.0f;
-      pt->pressure = 1.0f;
+          if (radius < min_radius) {
+            /* Extend along direction of curvature. */
+            bGPDstroke *gps_new = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
+            gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_TAG;
+            BLI_addtail(&gpf->strokes, gps_new);
 
-      pt = &gps_new->points[1];
-      pt->strength = 1.0f;
-      pt->pressure = 1.0f;
-      extrapolate_points_by_length(pt0, pt1, tgpf->fill_extend_fac * 0.1f, &pt->x);
+            bGPDspoint *pt = &gps_new->points[0];
+            copy_v3_v3(&pt->x, &pt1->x);
+            pt->strength = 1.0f;
+            pt->pressure = 1.0f;
 
-      /* Extend end. */
-      pt0 = &gps->points[gps->totpoints - 2];
-      pt1 = &gps->points[gps->totpoints - 1];
-      gps_new = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
-      gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_TAG;
-      BLI_addtail(&gpf->strokes, gps_new);
+            pt = &gps_new->points[1];
+            pt->strength = 1.0f;
+            pt->pressure = 1.0f;
+            mul_v3_fl(curvature, -connection_dist);
+            add_v3_v3v3(&pt->x, &pt1->x, curvature);
+          }
+        }
+      }
 
-      pt = &gps_new->points[0];
-      copy_v3_v3(&pt->x, &pt1->x);
-      pt->strength = 1.0f;
-      pt->pressure = 1.0f;
+      if (tgpf->fill_extend_mode != GP_FILL_EMODE_CIRCLES) {
+        /* Extend start. */
+        bGPDspoint *pt0 = &gps->points[1];
+        bGPDspoint *pt1 = &gps->points[0];
+        bGPDstroke *gps_new = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
+        gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_TAG;
+        BLI_addtail(&gpf->strokes, gps_new);
 
-      pt = &gps_new->points[1];
-      pt->strength = 1.0f;
-      pt->pressure = 1.0f;
-      extrapolate_points_by_length(pt0, pt1, tgpf->fill_extend_fac * 0.1f, &pt->x);
+        bGPDspoint *pt = &gps_new->points[0];
+        copy_v3_v3(&pt->x, &pt1->x);
+        pt->strength = 1.0f;
+        pt->pressure = 1.0f;
+
+        pt = &gps_new->points[1];
+        pt->strength = 1.0f;
+        pt->pressure = 1.0f;
+        extrapolate_points_by_length(pt0, pt1, connection_dist, &pt->x);
+
+        /* Extend end. */
+        pt0 = &gps->points[gps->totpoints - 2];
+        pt1 = &gps->points[gps->totpoints - 1];
+        gps_new = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
+        gps_new->flag |= GP_STROKE_NOFILL | GP_STROKE_TAG;
+        BLI_addtail(&gpf->strokes, gps_new);
+
+        pt = &gps_new->points[0];
+        copy_v3_v3(&pt->x, &pt1->x);
+        pt->strength = 1.0f;
+        pt->pressure = 1.0f;
+
+        pt = &gps_new->points[1];
+        pt->strength = 1.0f;
+        pt->pressure = 1.0f;
+        extrapolate_points_by_length(pt0, pt1, connection_dist, &pt->x);
+      }
+
+      /* Connect endpoints within a radius */
+      if (tgpf->fill_extend_mode == GP_FILL_EMODE_LINES) {
+        continue;
+      }
+      float *stroke1_start = &gps->points[0].x;
+      float *stroke1_end = &gps->points[gps->totpoints - 1].x;
+      /* Connect the start of the stroke to its own end if the whole stroke
+       * isn't already so short that it's within that distance
+       */
+      if (len_v3v3(stroke1_start, stroke1_end) < connection_dist &&
+          total_length > connection_dist)
+      {
+        add_stroke_extension(gpf, gps, stroke1_start, stroke1_end);
+        BLI_gset_add(connected_endpoints, stroke1_start);
+        BLI_gset_add(connected_endpoints, stroke1_end);
+      }
+      for (bGPDstroke *gps2 = (bGPDstroke *)(((Link *)gps)->next);
+          gps2 != NULL;
+          gps2 = (bGPDstroke *)(((Link *)gps2)->next))
+      {
+        /* Don't check distance to temporary extensions. */
+        if ((gps2->flag & GP_STROKE_NOFILL) && (gps2->flag & GP_STROKE_TAG)) {
+          continue;
+        }
+
+        /* Don't check endpoint distances unless the bounding boxes of the strokes
+        are close enough together that they can plausibly be connected. */
+        if (!extended_bbox_overlap(gps->boundbox_min,
+                                   gps->boundbox_max,
+                                   gps2->boundbox_min,
+                                   gps2->boundbox_max,
+                                   connection_dist)) {
+          continue;
+        }
+
+        float *stroke2_start = &gps2->points[0].x;
+        float *stroke2_end = &gps2->points[gps2->totpoints - 1].x;
+        if (len_v3v3(stroke1_start, stroke2_start) < connection_dist) {
+          add_stroke_extension(gpf, gps, stroke1_start, stroke2_start);
+          BLI_gset_add(connected_endpoints, stroke1_start);
+          BLI_gset_add(connected_endpoints, stroke2_start);
+        }
+        if (len_v3v3(stroke1_start, stroke2_end) < connection_dist) {
+          add_stroke_extension(gpf, gps, stroke1_start, stroke2_end);
+          BLI_gset_add(connected_endpoints, stroke1_start);
+          BLI_gset_add(connected_endpoints, stroke2_end);
+        }
+        if (len_v3v3(stroke1_end, stroke2_start) < connection_dist) {
+          add_stroke_extension(gpf, gps, stroke1_end, stroke2_start);
+          BLI_gset_add(connected_endpoints, stroke1_end);
+          BLI_gset_add(connected_endpoints, stroke2_start);
+        }
+        if (len_v3v3(stroke1_end, stroke2_end) < connection_dist) {
+          add_stroke_extension(gpf, gps, stroke1_end, stroke2_end);
+          BLI_gset_add(connected_endpoints, stroke1_end);
+          BLI_gset_add(connected_endpoints, stroke2_end);
+        }
+      }
+
+      bool start_connected = BLI_gset_haskey(connected_endpoints, stroke1_start);
+      bool end_connected = BLI_gset_haskey(connected_endpoints, stroke1_end);
+      add_endpoint_radius_help(gpf, gps, stroke1_start, connection_dist, start_connected);
+      add_endpoint_radius_help(gpf, gps, stroke1_end, connection_dist, end_connected);
     }
   }
+
+  BLI_gset_free(connected_endpoints, NULL);
 }
 
 static void gpencil_update_extend(tGPDfill *tgpf)
@@ -322,15 +514,16 @@ static bool gpencil_stroke_is_drawable(tGPDfill *tgpf, bGPDstroke *gps)
   const bool show_help = (tgpf->flag & GP_BRUSH_FILL_SHOW_HELPLINES) != 0;
   const bool show_extend = (tgpf->flag & GP_BRUSH_FILL_SHOW_EXTENDLINES) != 0;
   const bool is_extend = (gps->flag & GP_STROKE_NOFILL) && (gps->flag & GP_STROKE_TAG);
+  const bool is_extend_help = (gps->flag & GP_STROKE_NOFILL) && (gps->flag & GP_STROKE_HELP);
 
   if ((!show_help) && (show_extend)) {
-    if (!is_extend) {
+    if (!is_extend && !is_extend_help) {
       return false;
     }
   }
 
   if ((show_help) && (!show_extend)) {
-    if (is_extend) {
+    if (is_extend || is_extend_help) {
       return false;
     }
   }
@@ -357,13 +550,24 @@ static void gpencil_draw_basic_stroke(tGPDfill *tgpf,
   float fpt[3];
   float col[4];
   const float extend_col[4] = {0.0f, 1.0f, 1.0f, 1.0f};
-  const bool is_extend = (gps->flag & GP_STROKE_NOFILL) && (gps->flag & GP_STROKE_TAG);
+  const float help_col[4] = {1.0f, 0.0f, 0.5f, 1.0f};
+  const bool is_extend =
+    (gps->flag & GP_STROKE_NOFILL) && (gps->flag & GP_STROKE_TAG) && !(gps->flag & GP_STROKE_HELP);
+  const bool is_help = gps->flag & GP_STROKE_HELP;
 
   if (!gpencil_stroke_is_drawable(tgpf, gps)) {
     return;
   }
 
-  if ((is_extend) && (!tgpf->is_render)) {
+  if (is_help && tgpf->is_render) {
+    /* Help strokes are for display only and shouldn't render */
+    return;
+  } else if (is_help) {
+    /* Color help strokes that won't affect fill or render separately from
+     * extended strokes, as they will affect them */
+    copy_v4_v4(col, help_col);
+    col[3] = (gps->flag & GP_STROKE_TAG) ? 0.5f : 0.1f;
+  } else if ((is_extend) && (!tgpf->is_render)) {
     copy_v4_v4(col, extend_col);
   }
   else {
@@ -379,7 +583,7 @@ static void gpencil_draw_basic_stroke(tGPDfill *tgpf,
   immBindBuiltinProgram(GPU_SHADER_3D_FLAT_COLOR);
 
   /* draw stroke curve */
-  GPU_line_width((!is_extend) ? thickness : thickness * 2.0f);
+  GPU_line_width((!is_extend && !is_help) ? thickness : thickness * 2.0f);
   immBeginAtMost(GPU_PRIM_LINE_STRIP, totpoints + cyclic_add);
   const bGPDspoint *pt = points;
 
@@ -390,7 +594,7 @@ static void gpencil_draw_basic_stroke(tGPDfill *tgpf,
       CLAMP(alpha, 0.0f, 1.0f);
       col[3] = alpha <= thershold ? 0.0f : 1.0f;
     }
-    else {
+    else if (!is_help) {
       col[3] = 1.0f;
     }
     /* set point */
@@ -582,7 +786,9 @@ static void gpencil_draw_datablock(tGPDfill *tgpf, const float ink[4])
 
       /* Normal strokes. */
       if (ELEM(tgpf->fill_draw_mode, GP_FILL_DMODE_STROKE, GP_FILL_DMODE_BOTH)) {
-        if (gpencil_stroke_is_drawable(tgpf, gps) && ((gps->flag & GP_STROKE_TAG) == 0)) {
+        if (gpencil_stroke_is_drawable(tgpf, gps) &&
+            ((gps->flag & GP_STROKE_TAG) == 0) &&
+            ((gps->flag & GP_STROKE_HELP) == 0)) {
           ED_gpencil_draw_fill(&tgpw);
         }
       }
@@ -1777,6 +1983,7 @@ static tGPDfill *gpencil_session_init_fill(bContext *C, wmOperator *op)
   tgpf->fill_threshold = brush->gpencil_settings->fill_threshold;
   tgpf->fill_simplylvl = brush->gpencil_settings->fill_simplylvl;
   tgpf->fill_draw_mode = brush->gpencil_settings->fill_draw_mode;
+  tgpf->fill_extend_mode = brush->gpencil_settings->fill_extend_mode;
   tgpf->fill_extend_fac = brush->gpencil_settings->fill_extend_fac;
   tgpf->fill_factor = max_ff(GPENCIL_MIN_FILL_FAC,
                              min_ff(brush->gpencil_settings->fill_factor, GPENCIL_MAX_FILL_FAC));

source/blender/makesdna/DNA_brush_enums.h

@@ -118,13 +118,20 @@ typedef enum eGPDbrush_Flag2 {
   GP_BRUSH_USE_UV_RAND_PRESS = (1 << 11),
 } eGPDbrush_Flag2;
 
-/* BrushGpencilSettings->gp_fill_draw_mode */
+/* BrushGpencilSettings->fill_draw_mode */
 typedef enum eGP_FillDrawModes {
   GP_FILL_DMODE_BOTH = 0,
   GP_FILL_DMODE_STROKE = 1,
   GP_FILL_DMODE_CONTROL = 2,
 } eGP_FillDrawModes;
 
+/* BrushGpencilSettings->fill_extend_mode */
+typedef enum eGP_FillExtendModes {
+  GP_FILL_EMODE_LINES_AND_CIRCLES = 0,
+  GP_FILL_EMODE_LINES = 1,
+  GP_FILL_EMODE_CIRCLES = 2,
+} eGP_FillExtendModes;
+
 /* BrushGpencilSettings->fill_layer_mode */
 typedef enum eGP_FillLayerModes {
   GP_FILL_GPLMODE_VISIBLE = 0,

source/blender/makesdna/DNA_brush_types.h

@@ -62,7 +62,7 @@ typedef struct BrushGpencilSettings {
   short fill_leak;
   /* Type of caps: eGPDstroke_Caps. */
   int8_t caps_type;
-  char _pad;
+  char _pad[5];
 
   int flag2;
 
@@ -70,6 +70,8 @@ typedef struct BrushGpencilSettings {
   int fill_simplylvl;
   /** Type of control lines drawing mode. */
   int fill_draw_mode;
+  /** Type of gap filling to use */
+  int fill_extend_mode;
   /** Icon identifier. */
   int icon_id;
 

source/blender/makesdna/DNA_gpencil_types.h

@@ -347,6 +347,8 @@ typedef enum eGPDstroke_Flag {
   /* Flag to indicated that the editcurve has been changed and the stroke needs to be updated with
    * the curve data */
   GP_STROKE_NEEDS_CURVE_UPDATE = (1 << 9),
+  /* Flag to indicate that a stroke is used only for help, and will not affect rendering or fill */
+  GP_STROKE_HELP = (1 << 10),
   /* only for use with stroke-buffer (while drawing arrows) */
   GP_STROKE_USE_ARROW_START = (1 << 12),
   /* only for use with stroke-buffer (while drawing arrows) */

source/blender/makesrna/intern/rna_brush.c

@@ -286,6 +286,25 @@ static EnumPropertyItem rna_enum_gpencil_fill_draw_modes_items[] = {
     {GP_FILL_DMODE_CONTROL, "CONTROL", 0, "Edit Lines", "Use edit lines as fill boundary limits"},
     {0, NULL, 0, NULL, NULL}};
 
+static EnumPropertyItem rna_enum_gpencil_fill_extend_modes_items[] = {
+    {GP_FILL_EMODE_LINES,
+      "LINES",
+      0,
+      "Line",
+      "Extend strokes in straight lines"},
+    {
+      GP_FILL_EMODE_CIRCLES,
+      "CIRCLES",
+      0,
+      "Circle",
+      "Connect endpoints that are close together"},
+		{GP_FILL_EMODE_LINES_AND_CIRCLES,
+     "LINES_AND_CIRCLES",
+     0,
+     "Line & Circle",
+     "Extend strokes and connect close endpoints"},
+    {0, NULL, 0, NULL, NULL}};
+
 static EnumPropertyItem rna_enum_gpencil_fill_layers_modes_items[] = {
     {GP_FILL_GPLMODE_VISIBLE, "VISIBLE", 0, "Visible", "Visible layers"},
     {GP_FILL_GPLMODE_ACTIVE, "ACTIVE", 0, "Active", "Only active layer"},
@@ -1645,7 +1664,16 @@ static void rna_def_gpencil_options(BlenderRNA *brna)
   RNA_def_property_range(prop, 0.0f, 10.0f);
   RNA_def_property_float_default(prop, 0.0f);
   RNA_def_property_ui_text(
-      prop, "Stroke Extension", "Strokes end extension for closing gaps, use zero to disable");
+      prop, "Closure Size", "Strokes end extension for closing gaps, use zero to disable");
+  RNA_def_parameter_clear_flags(prop, PROP_ANIMATABLE, 0);
+
+  prop = RNA_def_property(srna, "fill_extend_mode", PROP_ENUM, PROP_NONE);
+  RNA_def_property_enum_sdna(prop, NULL, "fill_extend_mode");
+  RNA_def_property_enum_items(prop, rna_enum_gpencil_fill_extend_modes_items);
+  RNA_def_property_ui_text(
+      prop,
+      "Gap Closure",
+      "Types of stroke extensions used for closing gaps");
   RNA_def_parameter_clear_flags(prop, PROP_ANIMATABLE, 0);
 
   /* Number of pixels to dilate fill area. Negative values contract the filled area. */