BLI: New 'BLI_array_iter_spiral_square'

No functional changes.

This function replaces some of the logic in
`DRW_select_buffer_find_nearest_to_point` that traverses a buffer in a
spiral way to search for a closer pixel (not the closest).

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

3 files changed, 135 insertions, 62 deletions

diff --git a/source/blender/blenlib/BLI_array_utils.h b/source/blender/blenlib/BLI_array_utils.h
index bd37d22023b..8f4630dd732 100644
--- a/source/blender/blenlib/BLI_array_utils.h
+++ b/source/blender/blenlib/BLI_array_utils.h
@@ -89,6 +89,14 @@ bool _bli_array_iter_span(const void *arr,
 bool _bli_array_is_zeroed(const void *arr, unsigned int arr_len, size_t arr_stride);
 #define BLI_array_is_zeroed(arr, arr_len) _bli_array_is_zeroed(arr, arr_len, sizeof(*(arr)))
 
+bool _bli_array_iter_spiral_square(const void *arr_v,
+                                   const int arr_shape[2],
+                                   const size_t elem_size,
+                                   const int center[2],
+                                   const bool (*test_fn)(const void *arr_item, void *user_data),
+                                   void *user_data);
+#define BLI_array_iter_spiral_square(arr, arr_shape, center, test_fn, user_data) \
+  _bli_array_iter_spiral_square(arr, arr_shape, sizeof(*(arr)), center, test_fn, user_data)
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenlib/intern/array_utils.c b/source/blender/blenlib/intern/array_utils.c
index 2da2bbbc2a5..5d35cf09c30 100644
--- a/source/blender/blenlib/intern/array_utils.c
+++ b/source/blender/blenlib/intern/array_utils.c
@@ -27,13 +27,13 @@
 
 #include "MEM_guardedalloc.h"
 
-#include "BLI_array_utils.h"
-
 #include "BLI_alloca.h"
+#include "BLI_math_base.h"
+#include "BLI_strict_flags.h"
 #include "BLI_sys_types.h"
 #include "BLI_utildefines.h"
 
-#include "BLI_strict_flags.h"
+#include "BLI_array_utils.h"
 
 /**
  *In-place array reverse.
@@ -318,3 +318,94 @@ bool _bli_array_is_zeroed(const void *arr_v, unsigned int arr_len, size_t arr_st
   }
   return true;
 }
+
+/**
+ * Smart function to sample a rect spiraling outside.
+ * Nice for selection ID.
+ *
+ * \param arr_shape: dimensions [w, h].
+ * \param center: coordinates [x, y] indicating where to start transversing.
+ */
+bool _bli_array_iter_spiral_square(const void *arr_v,
+                                   const int arr_shape[2],
+                                   size_t elem_size,
+                                   const int center[2],
+                                   const bool (*test_fn)(const void *arr_item, void *user_data),
+                                   void *user_data)
+{
+  BLI_assert(center[0] >= 0 && center[1] >= 0 && center[0] < arr_shape[0] &&
+             center[1] < arr_shape[1]);
+
+  const char *arr = arr_v;
+  const int stride[2] = {arr_shape[1] * (int)elem_size, (int)elem_size};
+
+  /* Test center first. */
+  int ofs[2] = {center[0] * stride[0], center[1] * stride[1]};
+  if (test_fn(arr + ofs[0] + ofs[1], user_data)) {
+    return true;
+  }
+
+  /* #steps_in and #steps_out are the "diameters" of the inscribed and ciscunscript squares in the
+   * rectangle. Each step smaller than #steps_in does not need to check bounds. */
+  int steps_in, steps_out;
+  {
+    int x_minus = center[0];
+    int x_plus = arr_shape[0] - center[0] - 1;
+    int y_minus = center[1];
+    int y_plus = arr_shape[1] - center[1] - 1;
+
+    steps_in = 2 * min_iiii(x_minus, x_plus, y_minus, y_plus);
+    steps_out = 2 * max_iiii(x_minus, x_plus, y_minus, y_plus);
+  }
+
+  /* For check_bounds. */
+  int limits[2] = {(arr_shape[0] - 1) * stride[0], stride[0] - stride[1]};
+
+  int steps = 0;
+  while (steps < steps_out) {
+    steps += 2;
+
+    /* Move one step to the diagonal of the negative quadrant. */
+    ofs[0] -= stride[0];
+    ofs[1] -= stride[1];
+
+    bool check_bounds = steps > steps_in;
+
+    /* sign: 0 neg; 1 pos; */
+    for (int sign = 2; sign--;) {
+      /* axis: 0 x; 1 y; */
+      for (int axis = 2; axis--;) {
+        int ofs_step = stride[axis];
+        if (!sign) {
+          ofs_step *= -1;
+        }
+
+        int ofs_iter = ofs[axis] + ofs_step;
+        int ofs_dest = ofs[axis] + steps * ofs_step;
+        int ofs_other = ofs[!axis];
+
+        ofs[axis] = ofs_dest;
+        if (check_bounds) {
+          if (ofs_other < 0 || ofs_other > limits[!axis]) {
+            /* Out of bounds. */
+            continue;
+          }
+
+          CLAMP(ofs_iter, 0, limits[axis]);
+          CLAMP(ofs_dest, 0, limits[axis]);
+        }
+
+        while (true) {
+          if (test_fn(arr + ofs_other + ofs_iter, user_data)) {
+            return true;
+          }
+          if (ofs_iter == ofs_dest) {
+            break;
+          }
+          ofs_iter += ofs_step;
+        }
+      }
+    }
+  }
+  return false;
+}
diff --git a/source/blender/draw/intern/draw_select_buffer.c b/source/blender/draw/intern/draw_select_buffer.c
index b5151293c1b..d7438b7e0f0 100644
--- a/source/blender/draw/intern/draw_select_buffer.c
+++ b/source/blender/draw/intern/draw_select_buffer.c
@@ -24,6 +24,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_array_utils.h"
 #include "BLI_bitmap.h"
 #include "BLI_bitmap_draw_2d.h"
 #include "BLI_rect.h"
@@ -336,6 +337,26 @@ uint DRW_select_buffer_sample_point(struct Depsgraph *depsgraph,
   return ret;
 }
 
+struct SelectReadData {
+  const void *val_ptr;
+  uint id_min;
+  uint id_max;
+  uint r_index;
+};
+
+static bool select_buffer_test_fn(const void *__restrict value, void *__restrict userdata)
+{
+  struct SelectReadData *data = userdata;
+  uint hit_id = *(uint *)value;
+  if (hit_id && hit_id >= data->id_min && hit_id < data->id_max) {
+    /* Start at 1 to confirm. */
+    data->val_ptr = value;
+    data->r_index = (hit_id - data->id_min) + 1;
+    return true;
+  }
+  return false;
+}
+
 /**
  * Find the selection id closest to \a center.
  * \param dist: Use to initialize the distance,
@@ -349,13 +370,8 @@ uint DRW_select_buffer_find_nearest_to_point(struct Depsgraph *depsgraph,
                                              const uint id_max,
                                              uint *dist)
 {
-  /* Smart function to sample a rect spiraling outside, nice for selection ID. */
-
   /* Create region around center (typically the mouse cursor).
-   * This must be square and have an odd width,
-   * the spiraling algorithm does not work with arbitrary rectangles. */
-
-  uint index = 0;
+   * This must be square and have an odd width. */
 
   rcti rect;
   BLI_rcti_init_pt_radius(&rect, center, *dist);
@@ -364,7 +380,6 @@ uint DRW_select_buffer_find_nearest_to_point(struct Depsgraph *depsgraph,
 
   int width = BLI_rcti_size_x(&rect);
   int height = width;
-  BLI_assert(width == height);
 
   /* Read from selection framebuffer. */
 
@@ -372,64 +387,23 @@ uint DRW_select_buffer_find_nearest_to_point(struct Depsgraph *depsgraph,
   const uint *buf = DRW_select_buffer_read(depsgraph, region, v3d, &rect, &buf_len);
 
   if (buf == NULL) {
-    return index;
+    return 0;
   }
 
-  BLI_assert(width * height == buf_len);
-
-  /* Spiral, starting from center of buffer. */
-  int spiral_offset = height * (int)(width / 2) + (height / 2);
-  int spiral_direction = 0;
-
-  for (int nr = 1; nr <= height; nr++) {
-    for (int a = 0; a < 2; a++) {
-      for (int b = 0; b < nr; b++) {
-        /* Find hit within the specified range. */
-        uint hit_id = buf[spiral_offset];
-
-        if (hit_id && hit_id >= id_min && hit_id < id_max) {
-          /* Get x/y from spiral offset. */
-          int hit_x = spiral_offset % width;
-          int hit_y = spiral_offset / width;
-
-          int center_x = width / 2;
-          int center_y = height / 2;
+  const int shape[2] = {height, width};
+  const int center_yx[2] = {(height - 1) / 2, (width - 1) / 2};
+  struct SelectReadData data = {NULL, id_min, id_max, 0};
+  BLI_array_iter_spiral_square(buf, shape, center_yx, select_buffer_test_fn, &data);
 
-          /* Manhattan distance in keeping with other screen-based selection. */
-          *dist = (uint)(abs(hit_x - center_x) + abs(hit_y - center_y));
-
-          /* Indices start at 1 here. */
-          index = (hit_id - id_min) + 1;
-          goto exit;
-        }
-
-        /* Next spiral step. */
-        if (spiral_direction == 0) {
-          spiral_offset += 1; /* right */
-        }
-        else if (spiral_direction == 1) {
-          spiral_offset -= width; /* down */
-        }
-        else if (spiral_direction == 2) {
-          spiral_offset -= 1; /* left */
-        }
-        else {
-          spiral_offset += width; /* up */
-        }
-
-        /* Stop if we are outside the buffer. */
-        if (spiral_offset < 0 || spiral_offset >= buf_len) {
-          goto exit;
-        }
-      }
-
-      spiral_direction = (spiral_direction + 1) % 4;
-    }
+  if (data.val_ptr) {
+    size_t offset = ((size_t)data.val_ptr - (size_t)buf) / sizeof(*buf);
+    int hit_x = offset % width;
+    int hit_y = offset / width;
+    *dist = (uint)(abs(hit_y - center_yx[0]) + abs(hit_x - center_yx[1]));
   }
 
-exit:
   MEM_freeN((void *)buf);
-  return index;
+  return data.r_index;
 }
 
 /** \} */