diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-09-11 09:45:19 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-09-11 09:45:19 +0300 |
commit | f56fea3d6b481b70e5ca518e41dab8c00bc26251 (patch) | |
tree | 937bc4287f3e0766202958ccbdcb84f8b9d2b9b5 /source/blender | |
parent | 7e5687977287a0a8551a3593ebe60733b1c14af7 (diff) |
Fix T52701: Mesh shortest path fails at boundaries
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 16 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path_region.c | 28 |
3 files changed, 36 insertions, 9 deletions
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 668fb998254..88f45c06c20 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -754,6 +754,22 @@ bool BM_vert_is_edge_pair(const BMVert *v) } /** + * Fast alternative to ``(BM_vert_edge_count(v) == 2)`` + * that checks both edges connect to the same faces. + */ +bool BM_vert_is_edge_pair_manifold(const BMVert *v) +{ + const BMEdge *e = v->e; + if (e) { + BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v); + if (((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e))) { + return BM_edge_is_manifold(e) && BM_edge_is_manifold(e_other); + } + } + return false; +} + +/** * Access a verts 2 connected edges. * * \return true when only 2 verts are found. diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 83977fa8be0..c9fce96c798 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -85,6 +85,7 @@ int BM_vert_face_count(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_edge_pair(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool BM_vert_is_edge_pair_manifold(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_edge_pair(BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b); bool BM_vert_face_check(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_vert_is_wire(const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); diff --git a/source/blender/bmesh/tools/bmesh_path_region.c b/source/blender/bmesh/tools/bmesh_path_region.c index aad1f9c5a49..27609ec3d48 100644 --- a/source/blender/bmesh/tools/bmesh_path_region.c +++ b/source/blender/bmesh/tools/bmesh_path_region.c @@ -36,15 +36,25 @@ #include "bmesh_path_region.h" /* own include */ -/* Special handling of vertices with 2 edges - * (act as if the edge-chain is a single edge). */ +/** + * 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 fills in the vertices at each end-point, - * or nothing if if the edges loop back to its self. + * Takes a vertex with 2 edge users and assigns the vertices at each end-point, + * + * \return Success when \a v_end_pair values are set or false if the edges loop back on themselves. */ static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2]) { @@ -53,7 +63,7 @@ static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2]) do { BMEdge *e_chain = e; BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot); - while (BM_vert_is_edge_pair(v_other)) { + while (BM_vert_is_edge_pair_manifold(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); @@ -88,7 +98,7 @@ static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const in if (bm_vert_region_test(v, depths, pass)) { return true; } - else if (BM_vert_is_edge_pair(v) && + else if (BM_vert_is_edge_pair_manifold(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)) @@ -206,7 +216,7 @@ static LinkNode *mesh_calc_path_region_elem( 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)) { + if (BM_vert_is_edge_pair_manifold(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) { @@ -239,7 +249,7 @@ static LinkNode *mesh_calc_path_region_elem( /* 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) && + while (BM_vert_is_edge_pair_manifold(v_b) && ((depths[side][v_b_index] == -1))) { depths[side][v_b_index] = pass; @@ -256,7 +266,7 @@ static LinkNode *mesh_calc_path_region_elem( /* 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)); + BLI_assert(!BM_vert_is_edge_pair_manifold(v_b)); #endif BLI_assert(pass == depths[side][BM_elem_index_get(v_a)] + 1); depths[side][v_b_index] = pass; |