GPencil: Fill Tool - Check if extensions collide with real strokes

This commit is an improvement in the previous fill tool
changes in order to improve how the extended strokes
are managed.

* Now, the algorithm checks if the extend cross a standard stroke, not only extend strokes.

* Option to enable or disable the stroke cross checking
because this can be slow in very complex scenes.

* Added `D` key to toggle stroke cross option.

* Option to use only collide strokes to be used as fill limit.

If the option to use only collide strokes is enabled, the
open extensions are in different color.

* Status text now shows mode and the actual extend factor.

This commits also contains a refactor of the loops
to use arrays as much as possible.

Reviewed By: mendio, pepeland

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

1 files changed, 144 insertions, 11 deletions

diff --git a/source/blender/editors/gpencil/gpencil_fill.c b/source/blender/editors/gpencil/gpencil_fill.c
index 79ce68f5aa1..ba187080bab 100644
--- a/source/blender/editors/gpencil/gpencil_fill.c
+++ b/source/blender/editors/gpencil/gpencil_fill.c
@@ -87,6 +87,8 @@ typedef struct tStroke {
   bGPDframe *gpf;
   /** Referenced stroke. */
   bGPDstroke *gps;
+  /** Array of 2D points */
+  float (*points2d)[2];
   /** Extreme Stroke A. */
   bGPDstroke *gps_ext_a;
   /** Extreme Stroke B. */
@@ -199,6 +201,7 @@ typedef struct tGPDfill {
 
 bool skip_layer_check(short fill_layer_mode, int gpl_active_index, int gpl_index);
 static void gpencil_draw_boundary_lines(const struct bContext *UNUSED(C), struct tGPDfill *tgpf);
+static void gpencil_fill_status_indicators(struct tGPDfill *tgpf);
 
 /* Free temp stroke array. */
 static void stroke_array_free(tGPDfill *tgpf)
@@ -206,6 +209,7 @@ static void stroke_array_free(tGPDfill *tgpf)
   if (tgpf->stroke_array) {
     for (int i = 0; i < tgpf->stroke_array_num; i++) {
       tStroke *stroke = tgpf->stroke_array[i];
+      MEM_SAFE_FREE(stroke->points2d);
       MEM_freeN(stroke);
     }
     MEM_SAFE_FREE(tgpf->stroke_array);
@@ -392,6 +396,9 @@ static void gpencil_load_array_strokes(tGPDfill *tgpf)
       continue;
     }
 
+    float diff_mat[4][4];
+    BKE_gpencil_layer_transform_matrix_get(tgpf->depsgraph, tgpf->ob, gpl, diff_mat);
+
     LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
       /* Check if stroke can be drawn. */
       if ((gps->points == NULL) || (gps->totpoints < 2)) {
@@ -407,13 +414,26 @@ static void gpencil_load_array_strokes(tGPDfill *tgpf)
         continue;
       }
 
-      tStroke *stroke = MEM_callocN(sizeof(tStroke), "temp stroke data");
+      tStroke *stroke = MEM_callocN(sizeof(tStroke), __func__);
       stroke->gpl = gpl;
       stroke->gpf = gpf;
       stroke->gps = gps;
 
       /* Create the extension strokes only for Lines. */
       if (tgpf->fill_extend_mode == GP_FILL_EMODE_EXTEND) {
+        /* Convert all points to 2D to speed up collision checks and avoid convert in each
+         * iteration. */
+        stroke->points2d = (float(*)[2])MEM_mallocN(sizeof(*stroke->points2d) * gps->totpoints,
+                                                    "GP Stroke temp 2d points");
+
+        for (int i = 0; i < gps->totpoints; i++) {
+          bGPDspoint *pt = &gps->points[i];
+          bGPDspoint pt2;
+          gpencil_point_to_parent_space(pt, diff_mat, &pt2);
+          gpencil_point_to_xy_fl(
+              &tgpf->gsc, gps, &pt2, &stroke->points2d[i][0], &stroke->points2d[i][1]);
+        }
+
         /* Extend start. */
         bGPDspoint *pt1 = &gps->points[0];
         stroke->gps_ext_a = BKE_gpencil_stroke_new(gps->mat_nr, 2, gps->thickness);
@@ -459,6 +479,21 @@ static void gpencil_load_array_strokes(tGPDfill *tgpf)
   tgpf->stroke_array_num = idx;
 }
 
+/* Check if a 2D point is inside a 2D Bounding Box. */
+static bool is_point_in_bbox(tGPDfill *tgpf,
+                             bGPDstroke *gps,
+                             float diff_mat[4][4],
+                             float point2d[2])
+{
+  float boundbox_min[2];
+  float boundbox_max[2];
+
+  ED_gpencil_projected_2d_bound_box(&tgpf->gsc, gps, diff_mat, boundbox_min, boundbox_max);
+
+  rctf rect_stroke = {boundbox_min[0], boundbox_max[0], boundbox_min[1], boundbox_max[1]};
+  return BLI_rctf_isect_pt_v(&rect_stroke, point2d);
+}
+
 static void set_stroke_collide(bGPDstroke *gps_a, bGPDstroke *gps_b, const float connection_dist)
 {
   gps_a->flag |= GP_STROKE_COLLIDE;
@@ -469,12 +504,69 @@ static void set_stroke_collide(bGPDstroke *gps_a, bGPDstroke *gps_b, const float
    * temp strokes without adding new variables to the bGPStroke struct. */
   gps_a->fill_opacity_fac = connection_dist;
   gps_b->fill_opacity_fac = connection_dist;
+  BKE_gpencil_stroke_boundingbox_calc(gps_a);
+  BKE_gpencil_stroke_boundingbox_calc(gps_b);
+}
+
+static void gpencil_stroke_collision(
+    tGPDfill *tgpf, bGPDlayer *gpl, bGPDstroke *gps_a, float a1xy[2], float a2xy[2])
+{
+  const float connection_dist = tgpf->fill_extend_fac * 0.1f;
+  float diff_mat[4][4], inv_mat[4][4];
+
+  /* Transform matrix for original stroke.*/
+  BKE_gpencil_layer_transform_matrix_get(tgpf->depsgraph, tgpf->ob, gpl, diff_mat);
+  invert_m4_m4(inv_mat, diff_mat);
+
+  for (int idx = 0; idx < tgpf->stroke_array_num; idx++) {
+    tStroke *stroke = tgpf->stroke_array[idx];
+    bGPDstroke *gps_b = stroke->gps;
+
+    if (!extended_bbox_overlap(gps_a->boundbox_min,
+                               gps_a->boundbox_max,
+                               gps_b->boundbox_min,
+                               gps_b->boundbox_max,
+                               1.1f)) {
+      continue;
+    }
+
+    /* Loop all segments of the stroke. */
+    for (int i = 0; i < gps_b->totpoints - 1; i++) {
+      /* Skip segments over same pixel. */
+      if (((int)a1xy[0] == (int)stroke->points2d[i + 1][0]) &&
+          ((int)a1xy[1] == (int)stroke->points2d[i + 1][1])) {
+        continue;
+      }
+
+      /* Check if extensions cross. */
+      if (isect_seg_seg_v2_simple(a1xy, a2xy, stroke->points2d[i], stroke->points2d[i + 1])) {
+        bGPDspoint *extreme_a = &gps_a->points[1];
+        float intersection2D[2];
+        isect_line_line_v2_point(
+            a1xy, a2xy, stroke->points2d[i], stroke->points2d[i + 1], intersection2D);
+        /* Verify the collision is inside the bounding box of the strokes. */
+        if (!is_point_in_bbox(tgpf, gps_a, diff_mat, intersection2D) &&
+            !is_point_in_bbox(tgpf, gps_b, diff_mat, intersection2D)) {
+          continue;
+        }
+
+        gpencil_point_xy_to_3d(&tgpf->gsc, tgpf->scene, intersection2D, &extreme_a->x);
+        mul_m4_v3(inv_mat, &extreme_a->x);
+        BKE_gpencil_stroke_boundingbox_calc(gps_a);
+
+        gps_a->flag |= GP_STROKE_COLLIDE;
+        gps_a->fill_opacity_fac = connection_dist;
+        return;
+      }
+    }
+  }
 }
 
 /* Cut the extended lines if collide. */
 static void gpencil_cut_extensions(tGPDfill *tgpf)
 {
   const float connection_dist = tgpf->fill_extend_fac * 0.1f;
+  const bool use_stroke_collide = (tgpf->flag & GP_BRUSH_FILL_STROKE_COLLIDE) != 0;
 
   bGPDlayer *gpl_prev = NULL;
   bGPDframe *gpf_prev = NULL;
@@ -547,7 +639,7 @@ static void gpencil_cut_extensions(tGPDfill *tgpf)
                                    gps_a->boundbox_max,
                                    gps_b->boundbox_min,
                                    gps_b->boundbox_max,
-                                   connection_dist)) {
+                                   1.1f)) {
           continue;
         }
 
@@ -574,9 +666,10 @@ static void gpencil_cut_extensions(tGPDfill *tgpf)
         }
         /* Check if extensions cross. */
         if (isect_seg_seg_v2_simple(a1xy, a2xy, b1xy, b2xy)) {
-          float intersection[2];
-          isect_line_line_v2_point(a1xy, a2xy, b1xy, b2xy, intersection);
-          gpencil_point_xy_to_3d(&tgpf->gsc, tgpf->scene, intersection, intersection3D);
+          float intersection2D[2];
+          isect_line_line_v2_point(a1xy, a2xy, b1xy, b2xy, intersection2D);
+
+          gpencil_point_xy_to_3d(&tgpf->gsc, tgpf->scene, intersection2D, intersection3D);
           mul_m4_v3(inv_mat, intersection3D);
           copy_v3_v3(&extreme_a->x, intersection3D);
           copy_v3_v3(&extreme_b->x, intersection3D);
@@ -597,6 +690,11 @@ static void gpencil_cut_extensions(tGPDfill *tgpf)
           break;
         }
       }
+
+      /* Check if collide with normal strokes. */
+      if (use_stroke_collide && (gps_a->flag & GP_STROKE_COLLIDE) == 0) {
+        gpencil_stroke_collision(tgpf, stroke->gpl, gps_a, a1xy, a2xy);
+      }
     }
   }
   MEM_SAFE_FREE(gps_array);
@@ -770,6 +868,7 @@ static void gpencil_update_extend(tGPDfill *tgpf)
     gpencil_delete_temp_stroke_extension(tgpf, false);
     gpencil_create_extensions_radius(tgpf);
   }
+  gpencil_fill_status_indicators(tgpf);
   WM_event_add_notifier(tgpf->C, NC_GPENCIL | NA_EDITED, NULL);
 }
 
@@ -783,6 +882,13 @@ static bool gpencil_stroke_is_drawable(tGPDfill *tgpf, bGPDstroke *gps)
   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);
+  const bool is_line_mode = (tgpf->fill_extend_mode == GP_FILL_EMODE_EXTEND);
+  const bool only_collide = (tgpf->flag & GP_BRUSH_FILL_COLLIDE_ONLY) != 0;
+  const bool is_collide = (gps->flag & GP_STROKE_COLLIDE) != 0;
+
+  if (is_line_mode && only_collide && tgpf->is_render && !is_collide) {
+    return;
+  }
 
   if ((!show_help) && (show_extend)) {
     if (!is_extend && !is_extend_help) {
@@ -822,6 +928,9 @@ static void gpencil_draw_basic_stroke(tGPDfill *tgpf,
   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;
+  const bool is_line_mode = (tgpf->fill_extend_mode == GP_FILL_EMODE_EXTEND);
+  const bool only_collide = (tgpf->flag & GP_BRUSH_FILL_COLLIDE_ONLY) != 0;
+  const bool stroke_collide = (gps->flag & GP_STROKE_COLLIDE) != 0;
 
   if (!gpencil_stroke_is_drawable(tgpf, gps)) {
     return;
@@ -841,7 +950,12 @@ static void gpencil_draw_basic_stroke(tGPDfill *tgpf,
     col[3] = (gps->flag & GP_STROKE_TAG) ? 0.0f : 0.5f;
   }
   else if ((is_extend) && (!tgpf->is_render)) {
-    copy_v4_v4(col, extend_col);
+    if (stroke_collide || !only_collide || !is_line_mode) {
+      copy_v4_v4(col, extend_col);
+    }
+    else {
+      copy_v4_v4(col, help_col);
+    }
   }
   else {
     copy_v4_v4(col, ink);
@@ -2153,11 +2267,21 @@ static void gpencil_stroke_from_buffer(tGPDfill *tgpf)
 /* ----------------------- */
 /* Drawing                 */
 /* Helper: Draw status message while the user is running the operator */
-static void gpencil_fill_status_indicators(bContext *C)
+static void gpencil_fill_status_indicators(tGPDfill *tgpf)
 {
-  const char *status_str = TIP_(
-      "Fill: ESC/RMB cancel, LMB Fill, Shift Draw on Back, S: Switch Mode");
-  ED_workspace_status_text(C, status_str);
+  const bool is_extend = (tgpf->fill_extend_mode == GP_FILL_EMODE_EXTEND);
+  const bool use_stroke_collide = (tgpf->flag & GP_BRUSH_FILL_STROKE_COLLIDE) != 0;
+
+  char status_str[UI_MAX_DRAW_STR];
+  BLI_snprintf(status_str,
+               sizeof(status_str),
+               TIP_("Fill: ESC/RMB cancel, LMB Fill, Shift Draw on Back, S: Switch Mode, D: "
+                    "Stroke Collision | %s %s (%.3f)"),
+               (is_extend) ? TIP_("Extend") : TIP_("Radius"),
+               (is_extend && use_stroke_collide) ? TIP_("Stroke: ON") : TIP_("Stroke: OFF"),
+               tgpf->fill_extend_fac);
+
+  ED_workspace_status_text(tgpf->C, status_str);
 }
 
 /* draw boundary lines to see fill limits */
@@ -2424,7 +2548,7 @@ static int gpencil_fill_invoke(bContext *C, wmOperator *op, const wmEvent *UNUSE
 
   WM_cursor_modal_set(CTX_wm_window(C), WM_CURSOR_PAINT_BRUSH);
 
-  gpencil_fill_status_indicators(C);
+  gpencil_fill_status_indicators(tgpf);
 
   DEG_id_tag_update(&tgpf->gpd->id, ID_RECALC_TRANSFORM | ID_RECALC_GEOMETRY);
   WM_event_add_notifier(C, NC_GPENCIL | NA_EDITED, NULL);
@@ -2815,6 +2939,15 @@ static int gpencil_fill_modal(bContext *C, wmOperator *op, const wmEvent *event)
         gpencil_update_extend(tgpf);
       }
       break;
+    case EVT_DKEY:
+      if ((do_extend) && (event->val == KM_PRESS)) {
+        tgpf->flag ^= GP_BRUSH_FILL_STROKE_COLLIDE;
+        /* Clean temp strokes. */
+        stroke_array_free(tgpf);
+        gpencil_delete_temp_stroke_extension(tgpf, true);
+        gpencil_update_extend(tgpf);
+      }
+      break;
     case EVT_PAGEUPKEY:
     case WHEELUPMOUSE:
       if (tgpf->oldkey == 1) {