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
This commit is contained in:
parent
80f7f1070f
commit
cfd7b4d1cd
|
@ -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
|
||||
|
|
|
@ -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;
|
||||
}
|
||||
|
|
|
@ -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);
|
||||
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);
|
||||
|
||||
/* 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;
|
||||
|
||||
/* 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;
|
||||
}
|
||||
|
||||
/** \} */
|
||||
|
|
Loading…
Reference in New Issue