Shortest Path Select: option to select all paths between 2 elements
This option selects all paths between source/destination which are no longer than the path found. Handy for selecting meshes with a grid-topology.
This commit is contained in:
parent
26132eaf1f
commit
a55477d32a
|
@ -36,11 +36,15 @@
|
|||
|
||||
#include "BLI_math.h"
|
||||
#include "BLI_linklist.h"
|
||||
#include "BLI_stackdefines.h"
|
||||
#include "BLI_heap.h"
|
||||
|
||||
#include "bmesh.h"
|
||||
#include "bmesh_path.h" /* own include */
|
||||
|
||||
/* optionally expand all paths (result is no longer ordered) */
|
||||
#define USE_PATH_FILL
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/* Generic Helpers */
|
||||
|
||||
|
@ -67,6 +71,72 @@ static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3
|
|||
/* -------------------------------------------------------------------- */
|
||||
/* BM_mesh_calc_path_vert */
|
||||
|
||||
#ifdef USE_PATH_FILL
|
||||
static void verttag_calc_fill_steps(
|
||||
BMesh *bm, BMVert *v_start, int *steps, int steps_max, BMVert **stack_array,
|
||||
const struct BMCalcPathParams *params)
|
||||
{
|
||||
copy_vn_i(steps, bm->totvert, steps_max);
|
||||
|
||||
BMVert **stack = stack_array;
|
||||
STACK_DECLARE(stack);
|
||||
STACK_INIT(stack, bm->totvert);
|
||||
|
||||
STACK_PUSH(stack, v_start);
|
||||
steps[BM_elem_index_get(v_start)] = 0;
|
||||
|
||||
while (STACK_SIZE(stack) != 0) {
|
||||
BMVert *v_a = STACK_POP(stack);
|
||||
const int v_a_index = BM_elem_index_get(v_a);
|
||||
int step_a = steps[v_a_index];
|
||||
|
||||
if (step_a < steps_max) {
|
||||
{
|
||||
BMIter eiter;
|
||||
BMEdge *e;
|
||||
/* loop over faces of face, but do so by first looping over loops */
|
||||
BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) {
|
||||
BMVert *v_b = BM_edge_other_vert(e, v_a);
|
||||
if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
|
||||
/* we know 'v_b' is not visited, check it out! */
|
||||
const int v_b_index = BM_elem_index_get(v_b);
|
||||
const int step_b = step_a + 1;
|
||||
if (steps[v_b_index] > step_b) {
|
||||
steps[v_b_index] = step_b;
|
||||
STACK_PUSH(stack, v_b);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
if (params->use_step_face) {
|
||||
BMIter liter;
|
||||
BMLoop *l;
|
||||
/* loop over faces of face, but do so by first looping over loops */
|
||||
BM_ITER_ELEM (l, &liter, v_a, BM_LOOPS_OF_VERT) {
|
||||
if (l->f->len > 3) {
|
||||
/* skip loops on adjacent edges */
|
||||
BMLoop *l_iter = l->next->next;
|
||||
do {
|
||||
BMVert *v_b = l_iter->v;
|
||||
if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
|
||||
/* we know 'v_b' is not visited, check it out! */
|
||||
const int v_b_index = BM_elem_index_get(v_b);
|
||||
const int step_b = step_a + 1;
|
||||
if (steps[v_b_index] > step_b) {
|
||||
steps[v_b_index] = step_b;
|
||||
STACK_PUSH(stack, v_b);
|
||||
}
|
||||
}
|
||||
} while ((l_iter = l_iter->next) != l->prev);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
#endif /* USE_PATH_FILL */
|
||||
|
||||
static void verttag_add_adjacent(
|
||||
Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost,
|
||||
const struct BMCalcPathParams *params)
|
||||
|
@ -188,9 +258,36 @@ LinkNode *BM_mesh_calc_path_vert(
|
|||
}
|
||||
|
||||
if (v == v_dst) {
|
||||
int path_len = 0;
|
||||
do {
|
||||
BLI_linklist_prepend(&path, v);
|
||||
path_len++;
|
||||
} while ((v = verts_prev[BM_elem_index_get(v)]));
|
||||
|
||||
#ifdef USE_PATH_FILL
|
||||
if (params->use_fill) {
|
||||
BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
|
||||
BM_elem_flag_set(v, BM_ELEM_TAG, !test_fn(v, user_data));
|
||||
}
|
||||
|
||||
int *steps_src = MEM_mallocN(sizeof(*steps_src) * totvert, __func__);
|
||||
int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totvert, __func__);
|
||||
|
||||
/* reuse memory */
|
||||
BMVert **stack_array = verts_prev;
|
||||
verttag_calc_fill_steps(bm, v_src, steps_src, path_len, stack_array, params);
|
||||
verttag_calc_fill_steps(bm, v_dst, steps_dst, path_len, stack_array, params);
|
||||
|
||||
BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
|
||||
if (steps_src[i] + steps_dst[i] < path_len) {
|
||||
BLI_linklist_prepend(&path, v);
|
||||
}
|
||||
}
|
||||
|
||||
MEM_freeN(steps_src);
|
||||
MEM_freeN(steps_dst);
|
||||
}
|
||||
#endif
|
||||
}
|
||||
|
||||
MEM_freeN(verts_prev);
|
||||
|
@ -200,11 +297,88 @@ LinkNode *BM_mesh_calc_path_vert(
|
|||
return path;
|
||||
}
|
||||
|
||||
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/* BM_mesh_calc_path_edge */
|
||||
|
||||
#ifdef USE_PATH_FILL
|
||||
static void edgetag_calc_fill_steps(
|
||||
BMesh *bm, BMEdge *e_start, int *steps, int steps_max, BMEdge **stack_array,
|
||||
const struct BMCalcPathParams *params)
|
||||
{
|
||||
copy_vn_i(steps, bm->totedge, steps_max);
|
||||
|
||||
BMEdge **stack = stack_array;
|
||||
STACK_DECLARE(stack);
|
||||
STACK_INIT(stack, bm->totedge);
|
||||
|
||||
STACK_PUSH(stack, e_start);
|
||||
steps[BM_elem_index_get(e_start)] = 0;
|
||||
|
||||
while (STACK_SIZE(stack) != 0) {
|
||||
BMEdge *e_a = STACK_POP(stack);
|
||||
const int e_a_index = BM_elem_index_get(e_a);
|
||||
int step_a = steps[e_a_index];
|
||||
|
||||
if (step_a < steps_max) {
|
||||
/* unlike vert/face, stepping faces disables scanning connected edges
|
||||
* and only steps over faces (selecting a ring of edges instead of a loop) */
|
||||
if (params->use_step_face == false) {
|
||||
BMIter viter;
|
||||
BMVert *v;
|
||||
|
||||
BMIter eiter;
|
||||
BMEdge *e_b;
|
||||
|
||||
BM_ITER_ELEM (v, &viter, e_a, BM_VERTS_OF_EDGE) {
|
||||
BM_ITER_ELEM (e_b, &eiter, v, BM_EDGES_OF_VERT) {
|
||||
if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
|
||||
/* we know 'e_b' is not visited, check it out! */
|
||||
const int e_b_index = BM_elem_index_get(e_b);
|
||||
const int step_b = step_a + 1;
|
||||
if (steps[e_b_index] > step_b) {
|
||||
steps[e_b_index] = step_b;
|
||||
STACK_PUSH(stack, e_b);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
else {
|
||||
BMLoop *l_first, *l_iter;
|
||||
|
||||
l_iter = l_first = e_a->l;
|
||||
do {
|
||||
BMLoop *l_cycle_iter, *l_cycle_end;
|
||||
|
||||
l_cycle_iter = l_iter->next;
|
||||
l_cycle_end = l_iter;
|
||||
|
||||
/* good, but we need to allow this otherwise paths may fail to connect at all */
|
||||
#if 0
|
||||
if (l_iter->f->len > 3) {
|
||||
l_cycle_iter = l_cycle_iter->next;
|
||||
l_cycle_end = l_cycle_end->prev;
|
||||
}
|
||||
#endif
|
||||
|
||||
do {
|
||||
BMEdge *e_b = l_cycle_iter->e;
|
||||
if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
|
||||
/* we know 'e_b' is not visited, check it out! */
|
||||
const int e_b_index = BM_elem_index_get(e_b);
|
||||
const int step_b = step_a + 1;
|
||||
if (steps[e_b_index] > step_b) {
|
||||
steps[e_b_index] = step_b;
|
||||
STACK_PUSH(stack, e_b);
|
||||
}
|
||||
}
|
||||
} while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end);
|
||||
} while ((l_iter = l_iter->radial_next) != l_first);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
#endif /* USE_PATH_FILL */
|
||||
|
||||
static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v)
|
||||
{
|
||||
|
@ -369,9 +543,36 @@ LinkNode *BM_mesh_calc_path_edge(
|
|||
}
|
||||
|
||||
if (e == e_dst) {
|
||||
int path_len = 0;
|
||||
do {
|
||||
BLI_linklist_prepend(&path, e);
|
||||
path_len++;
|
||||
} while ((e = edges_prev[BM_elem_index_get(e)]));
|
||||
|
||||
#ifdef USE_PATH_FILL
|
||||
if (params->use_fill) {
|
||||
BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
|
||||
BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data));
|
||||
}
|
||||
|
||||
int *steps_src = MEM_mallocN(sizeof(*steps_src) * totedge, __func__);
|
||||
int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totedge, __func__);
|
||||
|
||||
/* reuse memory */
|
||||
BMEdge **stack_array = edges_prev;
|
||||
edgetag_calc_fill_steps(bm, e_src, steps_src, path_len, stack_array, params);
|
||||
edgetag_calc_fill_steps(bm, e_dst, steps_dst, path_len, stack_array, params);
|
||||
|
||||
BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
|
||||
if (steps_src[i] + steps_dst[i] < path_len) {
|
||||
BLI_linklist_prepend(&path, e);
|
||||
}
|
||||
}
|
||||
|
||||
MEM_freeN(steps_src);
|
||||
MEM_freeN(steps_dst);
|
||||
}
|
||||
#endif
|
||||
}
|
||||
|
||||
MEM_freeN(edges_prev);
|
||||
|
@ -386,6 +587,80 @@ LinkNode *BM_mesh_calc_path_edge(
|
|||
/* -------------------------------------------------------------------- */
|
||||
/* BM_mesh_calc_path_face */
|
||||
|
||||
#ifdef USE_PATH_FILL
|
||||
static void facetag_calc_fill_steps(
|
||||
BMesh *bm, BMFace *f_start, int *steps, int steps_max, BMFace **stack_array,
|
||||
const struct BMCalcPathParams *params)
|
||||
{
|
||||
copy_vn_i(steps, bm->totface, steps_max);
|
||||
|
||||
BMFace **stack = stack_array;
|
||||
STACK_DECLARE(stack);
|
||||
STACK_INIT(stack, bm->totface);
|
||||
|
||||
STACK_PUSH(stack, f_start);
|
||||
steps[BM_elem_index_get(f_start)] = 0;
|
||||
|
||||
while (STACK_SIZE(stack) != 0) {
|
||||
BMFace *f_a = STACK_POP(stack);
|
||||
const int f_a_index = BM_elem_index_get(f_a);
|
||||
int step_a = steps[f_a_index];
|
||||
|
||||
if (step_a < steps_max) {
|
||||
|
||||
{
|
||||
BMIter liter;
|
||||
BMLoop *l_a;
|
||||
|
||||
BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
|
||||
BMLoop *l_first, *l_iter;
|
||||
|
||||
l_iter = l_first = l_a;
|
||||
do {
|
||||
BMFace *f_b = l_iter->f;
|
||||
if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
|
||||
/* we know 'f_b' is not visited, check it out! */
|
||||
const int f_b_index = BM_elem_index_get(f_b);
|
||||
const int step_b = step_a + 1;
|
||||
if (steps[f_b_index] > step_b) {
|
||||
steps[f_b_index] = step_b;
|
||||
STACK_PUSH(stack, f_b);
|
||||
}
|
||||
}
|
||||
} while ((l_iter = l_iter->radial_next) != l_first);
|
||||
}
|
||||
}
|
||||
|
||||
|
||||
if (params->use_step_face) {
|
||||
BMIter liter;
|
||||
BMLoop *l_a;
|
||||
|
||||
BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
|
||||
BMIter litersub;
|
||||
BMLoop *l_b;
|
||||
BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) {
|
||||
if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) {
|
||||
BMFace *f_b = l_b->f;
|
||||
if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
|
||||
/* we know 'f_b' is not visited, check it out! */
|
||||
const int f_b_index = BM_elem_index_get(f_b);
|
||||
const int step_b = step_a + 1;
|
||||
if (steps[f_b_index] > step_b) {
|
||||
steps[f_b_index] = step_b;
|
||||
STACK_PUSH(stack, f_b);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
}
|
||||
}
|
||||
}
|
||||
#endif /* USE_PATH_FILL */
|
||||
|
||||
static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e)
|
||||
{
|
||||
float f_a_cent[3];
|
||||
|
@ -555,9 +830,36 @@ LinkNode *BM_mesh_calc_path_face(
|
|||
}
|
||||
|
||||
if (f == f_dst) {
|
||||
int path_len = 0;
|
||||
do {
|
||||
BLI_linklist_prepend(&path, f);
|
||||
path_len++;
|
||||
} while ((f = faces_prev[BM_elem_index_get(f)]));
|
||||
|
||||
#ifdef USE_PATH_FILL
|
||||
if (params->use_fill) {
|
||||
BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
|
||||
BM_elem_flag_set(f, BM_ELEM_TAG, !test_fn(f, user_data));
|
||||
}
|
||||
|
||||
int *steps_src = MEM_mallocN(sizeof(*steps_src) * totface, __func__);
|
||||
int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totface, __func__);
|
||||
|
||||
/* reuse memory */
|
||||
BMFace **stack_array = faces_prev;
|
||||
facetag_calc_fill_steps(bm, f_src, steps_src, path_len, stack_array, params);
|
||||
facetag_calc_fill_steps(bm, f_dst, steps_dst, path_len, stack_array, params);
|
||||
|
||||
BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
|
||||
if (steps_src[i] + steps_dst[i] < path_len) {
|
||||
BLI_linklist_prepend(&path, f);
|
||||
}
|
||||
}
|
||||
|
||||
MEM_freeN(steps_src);
|
||||
MEM_freeN(steps_dst);
|
||||
}
|
||||
#endif
|
||||
}
|
||||
|
||||
MEM_freeN(faces_prev);
|
||||
|
|
|
@ -30,6 +30,8 @@
|
|||
struct BMCalcPathParams {
|
||||
unsigned int use_topology_distance : 1;
|
||||
unsigned int use_step_face : 1;
|
||||
/* return all paths (no longer ordered) */
|
||||
unsigned int use_fill : 1;
|
||||
};
|
||||
|
||||
struct LinkNode *BM_mesh_calc_path_vert(
|
||||
|
|
|
@ -65,6 +65,7 @@ struct PathSelectParams {
|
|||
bool track_active; /* ensure the active element is the last selected item (handy for picking) */
|
||||
bool use_topology_distance;
|
||||
bool use_face_step;
|
||||
bool use_fill;
|
||||
char edge_mode;
|
||||
struct CheckerIntervalParams interval_params;
|
||||
};
|
||||
|
@ -77,6 +78,9 @@ static void path_select_properties(wmOperatorType *ot)
|
|||
RNA_def_boolean(
|
||||
ot->srna, "use_topology_distance", false, "Topology Distance",
|
||||
"Find the minimum number of steps, ignoring spatial distance");
|
||||
RNA_def_boolean(
|
||||
ot->srna, "use_fill", false, "Fill Region",
|
||||
"Select all paths between the source/destination elements");
|
||||
WM_operator_properties_checker_interval(ot, true);
|
||||
}
|
||||
|
||||
|
@ -85,6 +89,7 @@ static void path_select_params_from_op(wmOperator *op, struct PathSelectParams *
|
|||
op_params->edge_mode = EDGE_MODE_SELECT;
|
||||
op_params->track_active = false;
|
||||
op_params->use_face_step = RNA_boolean_get(op->ptr, "use_face_step");
|
||||
op_params->use_fill = RNA_boolean_get(op->ptr, "use_fill");
|
||||
op_params->use_topology_distance = RNA_boolean_get(op->ptr, "use_topology_distance");
|
||||
WM_operator_properties_checker_interval_from_op(op, &op_params->interval_params);
|
||||
}
|
||||
|
@ -130,6 +135,7 @@ static void mouse_mesh_shortest_path_vert(
|
|||
&(const struct BMCalcPathParams) {
|
||||
.use_topology_distance = op_params->use_topology_distance,
|
||||
.use_step_face = op_params->use_face_step,
|
||||
.use_fill = op_params->use_fill,
|
||||
},
|
||||
verttag_filter_cb, &user_data)))
|
||||
{
|
||||
|
@ -305,6 +311,7 @@ static void mouse_mesh_shortest_path_edge(
|
|||
&(const struct BMCalcPathParams) {
|
||||
.use_topology_distance = op_params->use_topology_distance,
|
||||
.use_step_face = op_params->use_face_step,
|
||||
.use_fill = op_params->use_fill,
|
||||
},
|
||||
edgetag_filter_cb, &user_data)))
|
||||
{
|
||||
|
@ -434,6 +441,7 @@ static void mouse_mesh_shortest_path_face(
|
|||
&(const struct BMCalcPathParams) {
|
||||
.use_topology_distance = op_params->use_topology_distance,
|
||||
.use_step_face = op_params->use_face_step,
|
||||
.use_fill = op_params->use_fill,
|
||||
},
|
||||
facetag_filter_cb, &user_data)))
|
||||
{
|
||||
|
|
Loading…
Reference in New Issue