diff options
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_path_region_uv.c')
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_path_region_uv.c | 502 |
1 files changed, 502 insertions, 0 deletions
diff --git a/source/blender/bmesh/tools/bmesh_path_region_uv.c b/source/blender/bmesh/tools/bmesh_path_region_uv.c new file mode 100644 index 00000000000..d036c20d0e4 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_path_region_uv.c @@ -0,0 +1,502 @@ +/* + * 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. + */ + +/** \file + * \ingroup bmesh + * + * Find the region defined by the path(s) between 2 UV elements. + * (path isn't ordered). + * + * \note This uses the same behavior as bmesh_path_region.c + * however walking UV's causes enough differences that it's + * impractical to share the code. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_alloca.h" +#include "BLI_linklist.h" +#include "BLI_math.h" +#include "BLI_utildefines_stack.h" + +#include "bmesh.h" +#include "bmesh_path_region_uv.h" /* own include */ + +/** + * Special handling of vertices with 2 edges + * (act as if the edge-chain is a single edge). + * + * \note Regarding manifold edge stepping: #BM_vert_is_edge_pair_manifold usage. + * Logic to skip a chain of vertices is not applied at boundaries because it gives + * strange behavior from a user perspective especially with boundary quads, see: T52701 + * + * Restrict walking over a vertex chain to cases where the edges share the same faces. + * This is more typical of what a user would consider a vertex chain. + */ +#define USE_EDGE_CHAIN + +#ifdef USE_EDGE_CHAIN +/** + * Takes a vertex with 2 edge users and assigns the vertices at each end-point, + * + * \return Success when \a l_end_pair values are set or false if the edges loop back on themselves. + */ +static bool bm_loop_pair_ends(BMLoop *l_pivot, BMLoop *l_end_pair[2]) +{ + int j; + for (j = 0; j < 2; j++) { + BMLoop *l_other = j ? l_pivot->next : l_pivot->prev; + while (BM_vert_is_edge_pair_manifold(l_other->v)) { + l_other = j ? l_other->next : l_other->prev; + if (l_other == l_pivot) { + return false; + } + } + l_end_pair[j] = l_other; + } + BLI_assert(j == 2); + return true; +} +#endif /* USE_EDGE_CHAIN */ + +/** \name Loop Vertex in Region Checks + * \{ */ + +static bool bm_loop_region_test(BMLoop *l, int *const depths[2], const int pass) +{ + const int index = BM_elem_index_get(l); + return (((depths[0][index] != -1) && (depths[1][index] != -1)) && + ((depths[0][index] + depths[1][index]) < pass)); +} + +#ifdef USE_EDGE_CHAIN +static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass) +{ + BMLoop *l_end_pair[2]; + if (bm_loop_region_test(l, depths, pass)) { + return true; + } + if (BM_vert_is_edge_pair_manifold(l->v) && bm_loop_pair_ends(l, l_end_pair) && + bm_loop_region_test(l_end_pair[0], depths, pass) && + bm_loop_region_test(l_end_pair[1], depths, pass)) { + return true; + } + + return false; +} +#else +static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass) +{ + return bm_loop_region_test(l, 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 uint cd_loop_uv_offset, + const char path_htype) +{ + int ele_loops_len[2]; + BMLoop **ele_loops[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_loops[side] = BLI_array_alloca(ele_loops[side], f->len); + + BMLoop *l_first, *l_iter; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + ele_loops[side][j++] = l_iter; + } while ((l_iter = l_iter->next) != l_first); + } + else if (ele->head.htype == BM_LOOP) { + if (path_htype == BM_EDGE) { + BMLoop *l = (BMLoop *)ele; + ele_loops[side] = BLI_array_alloca(ele_loops[side], 2); + ele_loops[side][j++] = l; + ele_loops[side][j++] = l->next; + } + else if (path_htype == BM_VERT) { + BMLoop *l = (BMLoop *)ele; + ele_loops[side] = BLI_array_alloca(ele_loops[side], 1); + + ele_loops[side][j++] = l; + } + else { + BLI_assert(0); + } + } + else { + BLI_assert(0); + } + ele_loops_len[side] = j; + } + + int *depths[2] = {NULL}; + int pass = 0; + + BMLoop **stack = MEM_mallocN(sizeof(*stack) * bm->totloop, __func__); + BMLoop **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totloop, __func__); + + STACK_DECLARE(stack); + STACK_INIT(stack, bm->totloop); + + STACK_DECLARE(stack_other); + STACK_INIT(stack_other, bm->totloop); + + BM_mesh_elem_index_ensure(bm, BM_LOOP); + + /* 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->totloop, __func__); + copy_vn_i(depths[side], bm->totloop, -1); + + /* needed for second side */ + STACK_CLEAR(stack); + STACK_CLEAR(stack_other); + + for (int i = 0; i < ele_loops_len[side]; i++) { + BMLoop *l = ele_loops[side][i]; + depths[side][BM_elem_index_get(l)] = 0; + if (!BM_elem_flag_test(l, BM_ELEM_TAG)) { + STACK_PUSH(stack, l); + } + } + +#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_loops_len[side]; i++) { + BMLoop *l = ele_loops[side][i]; + BMLoop *l_end_pair[2]; + if (BM_vert_is_edge_pair_manifold(l->v) && bm_loop_pair_ends(l, l_end_pair)) { + for (int j = 0; j < 2; j++) { + const int l_end_index = BM_elem_index_get(l_end_pair[j]); + if (depths[side][l_end_index] == -1) { + depths[side][l_end_index] = 0; + if (!BM_elem_flag_test(l_end_pair[j], BM_ELEM_TAG)) { + STACK_PUSH(stack, l_end_pair[j]); + } + } + } + } + } + } +#endif /* USE_EDGE_CHAIN */ + + /* Keep walking over connected geometry until we find all the vertices in + * `ele_loops[side_other]`, or exit the loop when there's no connection. */ + found_all = false; + for (pass = 1; (STACK_SIZE(stack) != 0); pass++) { + while (STACK_SIZE(stack) != 0) { + BMLoop *l_a = STACK_POP(stack); + const int l_a_index = BM_elem_index_get(l_a); + + BMIter iter; + BMLoop *l_iter; + + BM_ITER_ELEM (l_iter, &iter, l_a->v, BM_LOOPS_OF_VERT) { + if (BM_elem_flag_test(l_iter, BM_ELEM_TAG)) { + continue; + } + if (!BM_loop_uv_share_vert_check(l_a, l_iter, cd_loop_uv_offset)) { + continue; + } + + /* Flush the depth to connected loops (only needed for UV's). */ + if (depths[side][BM_elem_index_get(l_iter)] == -1) { + depths[side][BM_elem_index_get(l_iter)] = depths[side][l_a_index]; + } + + for (int j = 0; j < 2; j++) { + BMLoop *l_b = j ? l_iter->next : l_iter->prev; + int l_b_index = BM_elem_index_get(l_b); + if (depths[side][l_b_index] == -1) { + +#ifdef USE_EDGE_CHAIN + /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */ + { + while (BM_vert_is_edge_pair_manifold(l_b->v) && + ((depths[side][l_b_index] == -1) && + /* Don't walk back to the beginning */ + (l_b != (j ? l_iter->prev : l_iter->next)))) { + depths[side][l_b_index] = pass; + + l_b = j ? l_b->next : l_b->prev; + l_b_index = BM_elem_index_get(l_b); + } + } +#endif /* USE_EDGE_CHAIN */ + + /* Add the other vertex to the stack, to be traversed in the next pass. */ + if (depths[side][l_b_index] == -1) { +#ifdef USE_EDGE_CHAIN + BLI_assert(!BM_vert_is_edge_pair_manifold(l_b->v)); +#endif + BLI_assert(pass == depths[side][BM_elem_index_get(l_a)] + 1); + depths[side][l_b_index] = pass; + if (!BM_elem_flag_test(l_b, BM_ELEM_TAG)) { + STACK_PUSH(stack_other, l_b); + } + } + } + } + } + } + + /* Stop searching once there's 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_loops_len[side_other]; i++) { + if (depths[side][BM_elem_index_get(ele_loops[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; +#if 0 + do { + if (!bm_loop_region_test_chain(l_iter->v, depths, pass)) { + ok = false; + break; + } + } while ((l_iter = l_iter->next) != l_first); +#else + /* Allowing a single failure on a face gives fewer 'gaps'. + * While correct, in practice they're often part of what + * a user would consider the 'region'. */ + int ok_tests = f->len > 3 ? 1 : 0; /* how many times we may fail */ + do { + if (!bm_loop_region_test_chain(l_iter, depths, pass)) { + if (ok_tests == 0) { + ok = false; + break; + } + ok_tests--; + } + } while ((l_iter = l_iter->next) != l_first); +#endif + + if (ok) { + BLI_linklist_prepend(&path, f); + } + } + } + } + else if (path_htype == BM_EDGE) { + BMIter fiter; + BMFace *f; + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BMIter liter; + BMLoop *l; + /* Check the current and next loop vertices are in the region. */ + bool l_in_chain_next = bm_loop_region_test_chain(BM_FACE_FIRST_LOOP(f), depths, pass); + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + const bool l_in_chain = l_in_chain_next; + l_in_chain_next = bm_loop_region_test_chain(l->next, depths, pass); + if (l_in_chain && l_in_chain_next) { + BLI_linklist_prepend(&path, l); + } + } + } + } + else if (path_htype == BM_VERT) { + BMIter fiter; + BMFace *f; + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BMIter liter; + BMLoop *l; + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + if (bm_loop_region_test_chain(l, depths, pass)) { + BLI_linklist_prepend(&path, l); + } + } + } + } + + 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_uv_region_vert(BMesh *bm, + BMElem *ele_src, + BMElem *ele_dst, + const uint cd_loop_uv_offset, + bool (*filter_fn)(BMLoop *, 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 = 0; + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BMIter liter; + BMLoop *l; + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + BM_elem_flag_set(l, BM_ELEM_TAG, !filter_fn(l, user_data)); + BM_elem_index_set(l, i); /* set_inline */ + i += 1; + } + } + bm->elem_index_dirty &= ~BM_LOOP; + + path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_VERT); + + return path; +} + +LinkNode *BM_mesh_calc_path_uv_region_edge(BMesh *bm, + BMElem *ele_src, + BMElem *ele_dst, + const uint cd_loop_uv_offset, + bool (*filter_fn)(BMLoop *, 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 = 0; + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BMIter liter; + BMLoop *l; + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + BM_elem_flag_set(l, BM_ELEM_TAG, !filter_fn(l, user_data)); + BM_elem_index_set(l, i); /* set_inline */ + i += 1; + } + } + bm->elem_index_dirty &= ~BM_LOOP; + + path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_EDGE); + + return path; +} + +LinkNode *BM_mesh_calc_path_uv_region_face(BMesh *bm, + BMElem *ele_src, + BMElem *ele_dst, + const uint cd_loop_uv_offset, + 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, cd_loop_uv_offset, BM_FACE); + + return path; +} + +/** \} */ |