diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-04-01 15:27:31 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-04-01 15:36:06 +0300 |
commit | c6b27dd4fa02b2609a18ce3aa9c71b64e12b500d (patch) | |
tree | 3f6ba288e59f714c08331297b0d54dc0b8ad9e93 /source/blender/bmesh | |
parent | ae49f2ed99b650669541daf056e979c28dc7c73b (diff) |
BMesh: improve path-select fill region w/ ngons
Rewrote to work with ngons and and more complex topology, now uses separate function.
Fixes T48009.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/bmesh/bmesh_tools.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path.c | 340 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path.h | 4 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path_region.c | 462 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path_region.h | 43 |
6 files changed, 514 insertions, 338 deletions
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index 1afa98fd6f8..30fefe37f0e 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -148,6 +148,8 @@ set(SRC tools/bmesh_intersect.h tools/bmesh_path.c tools/bmesh_path.h + tools/bmesh_path_region.c + tools/bmesh_path_region.h tools/bmesh_region_match.c tools/bmesh_region_match.h tools/bmesh_triangulate.c diff --git a/source/blender/bmesh/bmesh_tools.h b/source/blender/bmesh/bmesh_tools.h index f7f767f91bf..23212dd085e 100644 --- a/source/blender/bmesh/bmesh_tools.h +++ b/source/blender/bmesh/bmesh_tools.h @@ -41,6 +41,7 @@ extern "C" { #include "tools/bmesh_edgenet.h" #include "tools/bmesh_edgesplit.h" #include "tools/bmesh_path.h" +#include "tools/bmesh_path_region.h" #include "tools/bmesh_region_match.h" #include "tools/bmesh_triangulate.h" diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c index 79a002f9f41..30b083cacda 100644 --- a/source/blender/bmesh/tools/bmesh_path.c +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -15,13 +15,6 @@ * along with this program; if not, write to the Free Software Foundation, * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * - * The Original Code is Copyright (C) 2004 Blender Foundation. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * * ***** END GPL LICENSE BLOCK ***** */ @@ -36,14 +29,11 @@ #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 */ @@ -71,72 +61,6 @@ 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) @@ -196,7 +120,7 @@ static void verttag_add_adjacent( LinkNode *BM_mesh_calc_path_vert( BMesh *bm, BMVert *v_src, BMVert *v_dst, const struct BMCalcPathParams *params, - bool (*test_fn)(BMVert *, void *user_data), void *user_data) + bool (*filter_fn)(BMVert *, void *user_data), void *user_data) { LinkNode *path = NULL; /* BM_ELEM_TAG flag is used to store visited edges */ @@ -211,13 +135,7 @@ LinkNode *BM_mesh_calc_path_vert( // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) { - if (test_fn(v, user_data)) { - BM_elem_flag_disable(v, BM_ELEM_TAG); - } - else { - BM_elem_flag_enable(v, BM_ELEM_TAG); - } - + BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data)); BM_elem_index_set(v, i); /* set_inline */ } bm->elem_index_dirty &= ~BM_VERT; @@ -258,36 +176,9 @@ 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); @@ -300,86 +191,6 @@ LinkNode *BM_mesh_calc_path_vert( /* -------------------------------------------------------------------- */ /* 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) { BMVert *v1 = BM_edge_other_vert(e_a, v); @@ -496,13 +307,7 @@ LinkNode *BM_mesh_calc_path_edge( BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) { - if (filter_fn(e, user_data)) { - BM_elem_flag_disable(e, BM_ELEM_TAG); - } - else { - BM_elem_flag_enable(e, BM_ELEM_TAG); - } - + BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data)); BM_elem_index_set(e, i); /* set_inline */ } bm->elem_index_dirty &= ~BM_EDGE; @@ -543,36 +348,9 @@ 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); @@ -583,84 +361,9 @@ 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]; @@ -768,7 +471,7 @@ static void facetag_add_adjacent( LinkNode *BM_mesh_calc_path_face( BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params, - bool (*test_fn)(BMFace *, void *user_data), void *user_data) + bool (*filter_fn)(BMFace *, void *user_data), void *user_data) { LinkNode *path = NULL; /* BM_ELEM_TAG flag is used to store visited edges */ @@ -783,13 +486,7 @@ LinkNode *BM_mesh_calc_path_face( // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) { - if (test_fn(f, user_data)) { - BM_elem_flag_disable(f, BM_ELEM_TAG); - } - else { - BM_elem_flag_enable(f, BM_ELEM_TAG); - } - + BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data)); BM_elem_index_set(f, i); /* set_inline */ } bm->elem_index_dirty &= ~BM_FACE; @@ -830,36 +527,9 @@ 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 9df1568f750..b6de5e0e4e0 100644 --- a/source/blender/bmesh/tools/bmesh_path.h +++ b/source/blender/bmesh/tools/bmesh_path.h @@ -30,8 +30,6 @@ 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( @@ -46,7 +44,7 @@ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5); struct LinkNode *BM_mesh_calc_path_face( BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params, - bool (*test_fn)(BMFace *, void *), void *user_data) + bool (*filter_fn)(BMFace *, void *), void *user_data) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5); #endif /* __BMESH_PATH_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_path_region.c b/source/blender/bmesh/tools/bmesh_path_region.c new file mode 100644 index 00000000000..e68dc867269 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_path_region.c @@ -0,0 +1,462 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/tools/bmesh_path_region.c + * \ingroup bmesh + * + * Find the region defined by the path(s) between 2 elements. + * (path isn't ordered). + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_math.h" +#include "BLI_linklist.h" +#include "BLI_stackdefines.h" +#include "BLI_alloca.h" + +#include "bmesh.h" +#include "bmesh_path_region.h" /* own include */ + + +/* Special handling of vertices with 2 edges + * (act as if the edge-chain is a single edge). */ +#define USE_EDGE_CHAIN + + +#ifdef USE_EDGE_CHAIN +/** + * Takes a vertex with 2 edge users and fills in the vertices at each end-point, + * or nothing if if the edges loop back to its self. + */ +static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2]) +{ + BMEdge *e = v_pivot->e; + int j = 0; + do { + BMEdge *e_chain = e; + BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot); + while (BM_vert_is_edge_pair(v_other)) { + BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other); + BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain); + v_other = BM_edge_other_vert(e_chain_next, v_other); + if (v_other == v_pivot) { + return false; + } + e_chain = e_chain_next; + } + v_end_pair[j++] = v_other; + } while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != v_pivot->e); + + BLI_assert(j == 2); + return true; +} +#endif /* USE_EDGE_CHAIN */ + + +/** \name Vertex in Region Checks + * \{ */ + +static bool bm_vert_region_test(BMVert *v, int * const depths[2], const int pass) +{ + const int index = BM_elem_index_get(v); + return (((depths[0][index] != -1) && (depths[1][index] != -1)) && \ + ((depths[0][index] + depths[1][index]) < pass)); +} + +#ifdef USE_EDGE_CHAIN +static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass) +{ + BMVert *v_end_pair[2]; + if (bm_vert_region_test(v, depths, pass)) { + return true; + } + else if (BM_vert_is_edge_pair(v) && + bm_vert_pair_ends(v, v_end_pair) && + bm_vert_region_test(v_end_pair[0], depths, pass) && + bm_vert_region_test(v_end_pair[1], depths, pass)) + { + return true; + } + + return false; +} +#else +static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass) +{ + return bm_vert_region_test(v, depths, pass); +} +#endif + +/** \} */ + + +/** + * Main logic for calculating region between 2 elements. + * + * This method works walking (breadth first) over all vertices, + * keeping track of topological distance from the source. + * + * This is done in both directions, after that each vertices 'depth' is added to check + * if its less than the number of passes needed to complete the search. + * When it is, we know the path is one of possible paths that have the minimum topological distance. + * + * \note Only verts without BM_ELEM_TAG will be walked over. + */ +static LinkNode *mesh_calc_path_region_elem( + BMesh *bm, + BMElem *ele_src, BMElem *ele_dst, + const char path_htype) +{ + int ele_verts_len[2]; + BMVert **ele_verts[2]; + + /* Get vertices from any `ele_src/ele_dst` elements. */ + for (int side = 0; side < 2; side++) { + BMElem *ele = side ? ele_dst : ele_src; + int j = 0; + + if (ele->head.htype == BM_FACE) { + BMFace *f = (BMFace *)ele; + ele_verts[side] = BLI_array_alloca(ele_verts[side], f->len); + + BMLoop *l_first, *l_iter; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + ele_verts[side][j++] = l_iter->v; + } while ((l_iter = l_iter->next) != l_first); + } + else if (ele->head.htype == BM_EDGE) { + BMEdge *e = (BMEdge *)ele; + ele_verts[side] = BLI_array_alloca(ele_verts[side], 2); + + ele_verts[side][j++] = e->v1; + ele_verts[side][j++] = e->v2; + } + else if (ele->head.htype == BM_VERT) { + BMVert *v = (BMVert *)ele; + ele_verts[side] = BLI_array_alloca(ele_verts[side], 1); + + ele_verts[side][j++] = v; + } + else { + BLI_assert(0); + } + ele_verts_len[side] = j; + } + + int *depths[2] = {NULL}; + int pass = 0; + + BMVert **stack = MEM_mallocN(sizeof(*stack) * bm->totvert, __func__); + BMVert **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totvert, __func__); + + STACK_DECLARE(stack); + STACK_INIT(stack, bm->totvert); + + STACK_DECLARE(stack_other); + STACK_INIT(stack_other, bm->totvert); + + BM_mesh_elem_index_ensure(bm, BM_VERT); + + /* After exhausting all possible elements, we should have found all elements on the 'side_other'. + * otherwise, exit early. */ + bool found_all = false; + + for (int side = 0; side < 2; side++) { + const int side_other = !side; + + /* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */ + depths[side] = MEM_mallocN(sizeof(*depths[side]) * bm->totvert, __func__); + copy_vn_i(depths[side], bm->totvert, -1); + + /* needed for second side */ + STACK_CLEAR(stack); + STACK_CLEAR(stack_other); + + for (int i = 0; i < ele_verts_len[side]; i++) { + BMVert *v = ele_verts[side][i]; + depths[side][BM_elem_index_get(v)] = 0; + if (v->e && !BM_elem_flag_test(v, BM_ELEM_TAG)) { + STACK_PUSH(stack, v); + } + } + +#ifdef USE_EDGE_CHAIN + /* Expand initial state to end-point vertices when they only have 2x edges, + * this prevents odd behavior when source or destination are in the middle of a long chain of edges. */ + if (ELEM(path_htype, BM_VERT, BM_EDGE)) { + for (int i = 0; i < ele_verts_len[side]; i++) { + BMVert *v = ele_verts[side][i]; + BMVert *v_end_pair[2]; + if (BM_vert_is_edge_pair(v) && bm_vert_pair_ends(v, v_end_pair)) { + for (int j = 0; j < 2; j++) { + const int v_end_index = BM_elem_index_get(v_end_pair[j]); + if (depths[side][v_end_index] == -1) { + depths[side][v_end_index] = 0; + if (!BM_elem_flag_test(v_end_pair[j], BM_ELEM_TAG)) { + STACK_PUSH(stack, v_end_pair[j]); + } + } + } + } + } + } +#endif /* USE_EDGE_CHAIN */ + + /* Keep walking over connected geometry until we find all the vertices in `ele_verts[side_other]`, + * or exit the loop when theres no connection. */ + found_all = false; + for (pass = 1; (STACK_SIZE(stack) != 0); pass++) { + while (STACK_SIZE(stack) != 0) { + BMVert *v_a = STACK_POP(stack); + const int v_a_index = BM_elem_index_get(v_a); + BMEdge *e = v_a->e; + + do { + BMVert *v_b = BM_edge_other_vert(e, v_a); + int v_b_index = BM_elem_index_get(v_b); + if (depths[side][v_b_index] == -1) { + +#ifdef USE_EDGE_CHAIN + /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */ + { + BMEdge *e_chain = e; + while (BM_vert_is_edge_pair(v_b) && + ((depths[side][v_b_index] == -1))) + { + depths[side][v_b_index] = pass; + + BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_b); + BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_b) == e_chain); + v_b = BM_edge_other_vert(e_chain_next, v_b); + v_b_index = BM_elem_index_get(v_b); + e_chain = e_chain_next; + } + } +#endif /* USE_EDGE_CHAIN */ + + /* Add the other vertex to the stack, to be traversed in the next pass. */ + if (depths[side][v_b_index] == -1) { +#ifdef USE_EDGE_CHAIN + BLI_assert(!BM_vert_is_edge_pair(v_b)); +#endif + BLI_assert(pass == depths[side][v_a_index] + 1); + depths[side][v_b_index] = pass; + if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) { + STACK_PUSH(stack_other, v_b); + } + } + } + } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != v_a->e); + } + + /* Stop searching once theres none left. + * Note that this looks in-efficient, however until the target elements reached, + * it will exit immediately. + * After that, it takes as many passes as the element has edges to finish off. */ + found_all = true; + for (int i = 0; i < ele_verts_len[side_other]; i++) { + if (depths[side][BM_elem_index_get(ele_verts[side_other][i])] == -1) { + found_all = false; + break; + } + } + if (found_all == true) { + pass++; + break; + } + + STACK_SWAP(stack, stack_other); + } + + /* if we have nothing left, and didn't find all elements on the other side, + * exit early and don't continue */ + if (found_all == false) { + break; + } + } + + MEM_freeN(stack); + MEM_freeN(stack_other); + + + /* Now we have depths recorded from both sides, + * select elements that use tagged verts. */ + LinkNode *path = NULL; + + if (found_all == false) { + /* fail! (do nothing) */ + } + else if (path_htype == BM_FACE) { + BMIter fiter; + BMFace *f; + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + if (!BM_elem_flag_test(f, BM_ELEM_TAG)) { + /* check all verts in face are tagged */ + BMLoop *l_first, *l_iter; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + bool ok = true; + do { + if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) { + ok = false; + break; + } + } while ((l_iter = l_iter->next) != l_first); + + if (ok) { + BLI_linklist_prepend(&path, f); + } + } + } + } + else if (path_htype == BM_EDGE) { + BMIter eiter; + BMEdge *e; + + BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) { + if (!BM_elem_flag_test(e, BM_ELEM_TAG)) { + /* check all verts in edge are tagged */ + bool ok = true; + for (int j = 0; j < 2; j++) { + if (!bm_vert_region_test_chain(*((&e->v1) + j), depths, pass)) { + ok = false; + break; + } + } + + if (ok) { + BLI_linklist_prepend(&path, e); + } + } + } + } + else if (path_htype == BM_VERT) { + BMIter viter; + BMVert *v; + + BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { + if (bm_vert_region_test_chain(v, depths, pass)) { + BLI_linklist_prepend(&path, v); + } + } + } + + + for (int side = 0; side < 2; side++) { + if (depths[side]) { + MEM_freeN(depths[side]); + } + } + + return path; +} + +#undef USE_EDGE_CHAIN + + +/** \name Main Functions (exposed externally). + * \{ */ + +LinkNode *BM_mesh_calc_path_region_vert( + BMesh *bm, BMElem *ele_src, BMElem *ele_dst, + bool (*filter_fn)(BMVert *, void *user_data), void *user_data) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited verts */ + BMVert *v; + BMIter viter; + int i; + + BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) { + BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data)); + BM_elem_index_set(v, i); /* set_inline */ + } + bm->elem_index_dirty &= ~BM_VERT; + + path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_VERT); + + return path; +} + +LinkNode *BM_mesh_calc_path_region_edge( + BMesh *bm, BMElem *ele_src, BMElem *ele_dst, + bool (*filter_fn)(BMEdge *, void *user_data), void *user_data) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited verts */ + BMEdge *e; + BMIter eiter; + int i; + + /* flush flag to verts */ + BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false); + + BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) { + bool test; + BM_elem_flag_set(e, BM_ELEM_TAG, test = !filter_fn(e, user_data)); + + /* flush tag to verts */ + if (test == false) { + for (int j = 0; j < 2; j++) { + BM_elem_flag_disable(*((&e->v1) + j), BM_ELEM_TAG); + } + } + } + + path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_EDGE); + + return path; +} + +LinkNode *BM_mesh_calc_path_region_face( + BMesh *bm, BMElem *ele_src, BMElem *ele_dst, + bool (*filter_fn)(BMFace *, void *user_data), void *user_data) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited verts */ + BMFace *f; + BMIter fiter; + int i; + + /* flush flag to verts */ + BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false); + + BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) { + bool test; + BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data)); + + /* flush tag to verts */ + if (test == false) { + BMLoop *l_first, *l_iter; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG); + } while ((l_iter = l_iter->next) != l_first); + } + } + + path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_FACE); + + return path; +} + +/** \} */ diff --git a/source/blender/bmesh/tools/bmesh_path_region.h b/source/blender/bmesh/tools/bmesh_path_region.h new file mode 100644 index 00000000000..06e56a59fb2 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_path_region.h @@ -0,0 +1,43 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BMESH_PATH_REGION_H__ +#define __BMESH_PATH_REGION_H__ + +/** \file blender/bmesh/tools/bmesh_path_region.h + * \ingroup bmesh + */ + +struct LinkNode *BM_mesh_calc_path_region_vert( + BMesh *bm, BMElem *ele_src, BMElem *ele_dst, + bool (*test_fn)(BMVert *, void *user_data), void *user_data) +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); + +struct LinkNode *BM_mesh_calc_path_region_edge( + BMesh *bm, BMElem *ele_src, BMElem *ele_dst, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data) +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); + +struct LinkNode *BM_mesh_calc_path_region_face( + BMesh *bm, BMElem *ele_src, BMElem *ele_dst, + bool (*test_fn)(BMFace *, void *user_data), void *user_data) +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); + +#endif /* __BMESH_PATH_REGION_H__ */ |