diff options
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_walkers.h | 1 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_walkers_impl.c | 123 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_walkers_private.h | 7 | ||||
| -rw-r--r-- | source/blender/editors/mesh/editmesh_select.c | 12 |
4 files changed, 142 insertions, 1 deletions
diff --git a/source/blender/bmesh/intern/bmesh_walkers.h b/source/blender/bmesh/intern/bmesh_walkers.h index 22ee8809a19..ce0f8ae8324 100644 --- a/source/blender/bmesh/intern/bmesh_walkers.h +++ b/source/blender/bmesh/intern/bmesh_walkers.h @@ -114,6 +114,7 @@ enum { BMW_FACELOOP, BMW_EDGERING, BMW_EDGEBOUNDARY, + BMW_EDGELOOP_NONMANIFOLD, /* BMW_RING, */ BMW_LOOPDATA_ISLAND, BMW_ISLANDBOUND, diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index 647a22baaeb..a8558ec4011 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -1596,6 +1596,118 @@ static void *bmw_UVEdgeWalker_step(BMWalker *walker) /** \} */ +/* -------------------------------------------------------------------- */ +/** \name Non-manifold Edge Walker + * \{ */ + +static void bmw_NonManifoldedgeWalker_begin(BMWalker *walker, void *data) +{ + BMwNonManifoldEdgeLoopWalker *lwalk; + BMEdge *e = data; + + if (BLI_gset_haskey(walker->visit_set, e)) { + return; + } + + lwalk = BMW_state_add(walker); + lwalk->start = e; + lwalk->cur = e; + lwalk->startv = e->v1; + lwalk->lastv = e->v1; + lwalk->face_count = BM_edge_face_count(e); + BLI_gset_insert(walker->visit_set, e); +} + +static void *bmw_NonManifoldedgeWalker_yield(BMWalker *walker) +{ + BMwNonManifoldEdgeLoopWalker *lwalk = BMW_current_state(walker); + + if (!lwalk) { + return NULL; + } + return lwalk->cur; +} + +/** + * Walk over manifold loops around `v` until loop-edge is found with `face_count` users. + * or return NULL if not found. + * */ +static BMLoop *bmw_NonManifoldLoop_find_next_around_vertex(BMLoop *l, BMVert *v, int face_count) +{ + BLI_assert(!BM_loop_is_manifold(l)); + do { + l = BM_loop_other_edge_loop(l, v); + if (BM_loop_is_manifold(l)) { + l = l->radial_next; + } + else if (BM_edge_face_count_is_equal(l->e, face_count)) { + return l; + } + else { + break; + } + } while (true); + return NULL; +} + +static void *bmw_NonManifoldedgeWalker_step(BMWalker *walker) +{ + BMwNonManifoldEdgeLoopWalker *lwalk, owalk; + BMW_state_remove_r(walker, &owalk); + lwalk = &owalk; + BMLoop *l_cur = NULL; + const int face_count = lwalk->face_count; + + BMVert *v = NULL; + + /* Use the second pass is unlikely, only needed to walk back in the opposite direction. */ + for (int pass = 0; pass < 2; pass++) { + + BMEdge *e = lwalk->cur; + v = BM_edge_other_vert(e, lwalk->lastv); + + /* If `lwalk.lastv` can't be walked along, start walking in the opposite direction + * on the initial edge, do this at most one time during this walk operation. */ + if (UNLIKELY(pass == 1)) { + e = lwalk->start; + v = lwalk->startv; + } + + BMLoop *l = e->l; + do { + BMLoop *l_next = bmw_NonManifoldLoop_find_next_around_vertex(l, v, face_count); + if ((l_next != NULL) && !BLI_gset_haskey(walker->visit_set, l_next->e)) { + if (l_cur == NULL) { + l_cur = l_next; + } + else if (l_cur->e != l_next->e) { + /* If there are more than one possible edge to step onto (unlikely but possible), + * treat as a junction and stop walking as there is no correct answer in this case. */ + l_cur = NULL; + break; + } + } + } while ((l = l->radial_next) != e->l); + + if (l_cur != NULL) { + break; + } + } + + if (l_cur != NULL) { + BLI_assert(!BLI_gset_haskey(walker->visit_set, l_cur->e)); + BLI_assert(BM_edge_face_count(l_cur->e) == face_count); + lwalk = BMW_state_add(walker); + lwalk->lastv = v; + lwalk->cur = l_cur->e; + lwalk->face_count = face_count; + BLI_gset_insert(walker->visit_set, l_cur->e); + } + return owalk.cur; +} + +/** \} */ + static BMWalker bmw_VertShellWalker_Type = { BM_VERT | BM_EDGE, bmw_VertShellWalker_begin, @@ -1708,6 +1820,16 @@ static BMWalker bmw_EdgeboundaryWalker_Type = { 0, }; +static BMWalker bmw_NonManifoldedgeWalker_type = { + BM_EDGE, + bmw_NonManifoldedgeWalker_begin, + bmw_NonManifoldedgeWalker_step, + bmw_NonManifoldedgeWalker_yield, + sizeof(BMwNonManifoldEdgeLoopWalker), + BMW_DEPTH_FIRST, + 0, +}; + static BMWalker bmw_UVEdgeWalker_Type = { BM_LOOP, bmw_UVEdgeWalker_begin, @@ -1737,6 +1859,7 @@ BMWalker *bm_walker_types[] = { &bmw_FaceLoopWalker_Type, /* #BMW_FACELOOP */ &bmw_EdgeringWalker_Type, /* #BMW_EDGERING */ &bmw_EdgeboundaryWalker_Type, /* #BMW_EDGEBOUNDARY */ + &bmw_NonManifoldedgeWalker_type, /* #BMW_EDGELOOP_NONMANIFOLD */ &bmw_UVEdgeWalker_Type, /* #BMW_LOOPDATA_ISLAND */ &bmw_IslandboundWalker_Type, /* #BMW_ISLANDBOUND */ &bmw_IslandWalker_Type, /* #BMW_ISLAND */ diff --git a/source/blender/bmesh/intern/bmesh_walkers_private.h b/source/blender/bmesh/intern/bmesh_walkers_private.h index 721f3c2c65b..2da4f290c76 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_private.h +++ b/source/blender/bmesh/intern/bmesh_walkers_private.h @@ -84,6 +84,13 @@ typedef struct BMwEdgeboundaryWalker { BMEdge *e; } BMwEdgeboundaryWalker; +typedef struct BMwNonManifoldEdgeLoopWalker { + BMwGenericWalker header; + BMEdge *start, *cur; + BMVert *startv, *lastv; + int face_count; /* face count around the edge. */ +} BMwNonManifoldEdgeLoopWalker; + typedef struct BMwUVEdgeWalker { BMwGenericWalker header; BMLoop *l; diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c index 903e50bf668..35608a4abde 100644 --- a/source/blender/editors/mesh/editmesh_select.c +++ b/source/blender/editors/mesh/editmesh_select.c @@ -1524,7 +1524,13 @@ static int edbm_loop_multiselect_exec(bContext *C, wmOperator *op) else { for (edindex = 0; edindex < totedgesel; edindex += 1) { eed = edarray[edindex]; - walker_select(em, BMW_EDGELOOP, eed, true); + bool non_manifold = BM_edge_face_count_is_over(eed, 2); + if (non_manifold) { + walker_select(em, BMW_EDGELOOP_NONMANIFOLD, eed, true); + } + else { + walker_select(em, BMW_EDGELOOP, eed, true); + } } EDBM_selectmode_flush(em); } @@ -1585,6 +1591,7 @@ static void mouse_mesh_loop_edge( BMEditMesh *em, BMEdge *eed, bool select, bool select_clear, bool select_cycle) { bool edge_boundary = false; + bool non_manifold = BM_edge_face_count_is_over(eed, 2); /* Cycle between BMW_EDGELOOP / BMW_EDGEBOUNDARY. */ if (select_cycle && BM_edge_is_boundary(eed)) { @@ -1610,6 +1617,9 @@ static void mouse_mesh_loop_edge( if (edge_boundary) { walker_select(em, BMW_EDGEBOUNDARY, eed, select); } + else if (non_manifold) { + walker_select(em, BMW_EDGELOOP_NONMANIFOLD, eed, select); + } else { walker_select(em, BMW_EDGELOOP, eed, select); } |