diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-03-30 20:21:02 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-03-30 20:25:19 +0300 |
commit | a55477d32a2b3f20fd1f54ec45018208ade57b8e (patch) | |
tree | f6ca9ff32c6d88219e4b270ede187ea6df526951 /source/blender/bmesh | |
parent | 26132eaf1f8058d66f39a5009fa3803935e091c4 (diff) |
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.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path.c | 306 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path.h | 2 |
2 files changed, 306 insertions, 2 deletions
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c index a10a1b688dd..79a002f9f41 100644 --- a/source/blender/bmesh/tools/bmesh_path.c +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -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); diff --git a/source/blender/bmesh/tools/bmesh_path.h b/source/blender/bmesh/tools/bmesh_path.h index fdcea8e9803..9df1568f750 100644 --- a/source/blender/bmesh/tools/bmesh_path.h +++ b/source/blender/bmesh/tools/bmesh_path.h @@ -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( |