[Bf-blender-cvs] [cfd7b4d1cd4] master: BLI: New 'BLI_array_iter_spiral_square'
Germano Cavalcante
noreply at git.blender.org
Tue Mar 9 20:05:39 CET 2021
Commit: cfd7b4d1cd48ecffbf61d45dfa4f24ccda3d6a71
Author: Germano Cavalcante
Date: Tue Mar 9 16:02:40 2021 -0300
Branches: master
https://developer.blender.org/rBcfd7b4d1cd48ecffbf61d45dfa4f24ccda3d6a71
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
===================================================================
M source/blender/blenlib/BLI_array_utils.h
M source/blender/blenlib/intern/array_utils.c
M source/blender/draw/intern/draw_select_buffer.c
===================================================================
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;
}
/** \} */
More information about the Bf-blender-cvs
mailing list