From cfd7b4d1cd48ecffbf61d45dfa4f24ccda3d6a71 Mon Sep 17 00:00:00 2001 From: Germano Cavalcante Date: Tue, 9 Mar 2021 16:02:40 -0300 Subject: 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 --- source/blender/blenlib/BLI_array_utils.h | 8 ++ source/blender/blenlib/intern/array_utils.c | 97 ++++++++++++++++++++++++- source/blender/draw/intern/draw_select_buffer.c | 92 +++++++++-------------- 3 files changed, 135 insertions(+), 62 deletions(-) (limited to 'source') 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; } /** \} */ -- cgit v1.2.3