diff options
Diffstat (limited to 'source/blender/bmesh/intern/bmesh_walkers_impl.c')
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_walkers_impl.c | 412 |
1 files changed, 372 insertions, 40 deletions
diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index 406dd412d6d..28c3debb93c 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -33,7 +33,6 @@ #include "BKE_customdata.h" #include "bmesh.h" -#include "intern/bmesh_private.h" #include "intern/bmesh_walkers_private.h" /* pop into stack memory (common operation) */ @@ -87,6 +86,30 @@ static bool bmw_mask_check_face(BMWalker *walker, BMFace *f) /** \} */ +/** \name BMesh Queries (modified to check walker flags) + * \{ */ + +/** + * Check for a wire edge, taking ignoring hidden. + */ +static bool bmw_edge_is_wire(const BMWalker *walker, const BMEdge *e) +{ + if (walker->flag & BMW_FLAG_TEST_HIDDEN) { + /* check if this is a wire edge, ignoring hidden faces */ + if (BM_edge_is_wire(e)) { + return true; + } + else { + return BM_edge_is_all_face_flag_test(e, BM_ELEM_HIDDEN, false); + } + } + else { + return BM_edge_is_wire(e); + } +} +/** \} */ + + /** \name Shell Walker * \{ * @@ -224,6 +247,291 @@ static void *bmw_VertShellWalker_step(BMWalker *walker) /** \} */ +/** \name LoopShell Walker + * \{ + * + * Starts at any element on the mesh and walks over the 'shell' it belongs + * to via visiting connected loops. + * + * \note this is mainly useful to loop over a shell delimited by edges. + */ +static void bmw_LoopShellWalker_visitLoop(BMWalker *walker, BMLoop *l) +{ + BMwLoopShellWalker *shellWalk = NULL; + + if (BLI_gset_haskey(walker->visit_set, l)) { + return; + } + + if (!bmw_mask_check_face(walker, l->f)) { + return; + } + + shellWalk = BMW_state_add(walker); + shellWalk->curloop = l; + BLI_gset_insert(walker->visit_set, l); +} + +static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data) +{ + BMIter iter; + BMHeader *h = data; + + if (UNLIKELY(h == NULL)) { + return; + } + + switch (h->htype) { + case BM_LOOP: + { + /* starting the walk at a vert, add all the edges + * to the worklist */ + BMLoop *l = (BMLoop *)h; + bmw_LoopShellWalker_visitLoop(walker, l); + break; + } + + case BM_VERT: + { + BMVert *v = (BMVert *)h; + BMLoop *l; + BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { + bmw_LoopShellWalker_visitLoop(walker, l); + } + break; + } + case BM_EDGE: + { + BMEdge *e = (BMEdge *)h; + BMLoop *l; + BM_ITER_ELEM (l, &iter, e, BM_LOOPS_OF_EDGE) { + bmw_LoopShellWalker_visitLoop(walker, l); + } + break; + } + case BM_FACE: + { + BMFace *f = (BMFace *)h; + BMLoop *l = BM_FACE_FIRST_LOOP(f); + /* walker will handle other loops within the face */ + bmw_LoopShellWalker_visitLoop(walker, l); + break; + } + default: + BLI_assert(0); + } +} + +static void *bmw_LoopShellWalker_yield(BMWalker *walker) +{ + BMwLoopShellWalker *shellWalk = BMW_current_state(walker); + return shellWalk->curloop; +} + +static void bmw_LoopShellWalker_step_impl(BMWalker *walker, BMLoop *l) +{ + BMEdge *e_edj_pair[2]; + int i; + + /* seems paranoid, but one caller also walks edges */ + BLI_assert(l->head.htype == BM_LOOP); + + bmw_LoopShellWalker_visitLoop(walker, l->next); + bmw_LoopShellWalker_visitLoop(walker, l->prev); + + e_edj_pair[0] = l->e; + e_edj_pair[1] = l->prev->e; + + for (i = 0; i < 2; i++) { + BMEdge *e = e_edj_pair[i]; + if (bmw_mask_check_edge(walker, e)) { + BMLoop *l_iter, *l_first; + + l_iter = l_first = e->l; + do { + BMLoop *l_radial = (l_iter->v == l->v) ? l_iter : l_iter->next; + BLI_assert(l_radial->v == l->v); + if (l != l_radial) { + bmw_LoopShellWalker_visitLoop(walker, l_radial); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } +} + +static void *bmw_LoopShellWalker_step(BMWalker *walker) +{ + BMwLoopShellWalker *swalk, owalk; + BMLoop *l; + + BMW_state_remove_r(walker, &owalk); + swalk = &owalk; + + l = swalk->curloop; + bmw_LoopShellWalker_step_impl(walker, l); + + return l; +} + +/** \} */ + +/** \name LoopShell & 'Wire' Walker + * \{ + * + * Piggyback ontop of #BMwLoopShellWalker, but also walk over wire edges + * This isn't elegant but users expect it when selecting linked, + * so we can support delimiters _and_ walking over wire edges. + * + * Details: + * - can yield edges (as well as loops) + * - only step over wire edges. + * - verts and edges are stored in `visit_set_alt`. + */ + +static void bmw_LoopShellWalker_visitEdgeWire(BMWalker *walker, BMEdge *e) +{ + BMwLoopShellWireWalker *shellWalk = NULL; + + BLI_assert(bmw_edge_is_wire(walker, e)); + + if (BLI_gset_haskey(walker->visit_set_alt, e)) { + return; + } + + if (!bmw_mask_check_edge(walker, e)) { + return; + } + + shellWalk = BMW_state_add(walker); + shellWalk->curelem = (BMElem *)e; + BLI_gset_insert(walker->visit_set_alt, e); +} + +static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from) +{ + BMEdge *e; + + BLI_assert(v->head.htype == BM_VERT); + + if (BLI_gset_haskey(walker->visit_set_alt, v)) { + return; + } + + if (!bmw_mask_check_vert(walker, v)) { + return; + } + + e = v->e; + do { + if (bmw_edge_is_wire(walker, e) && (e != e_from)) { + BMVert *v_other; + BMIter iter; + BMLoop *l; + + bmw_LoopShellWalker_visitEdgeWire(walker, e); + + /* check if we step onto a non-wire vertex */ + v_other = BM_edge_other_vert(e, v); + BM_ITER_ELEM (l, &iter, v_other, BM_LOOPS_OF_VERT) { + + bmw_LoopShellWalker_visitLoop(walker, l); + } + } + } while ((e = BM_DISK_EDGE_NEXT(e, v)) != v->e); + + BLI_gset_insert(walker->visit_set_alt, v); +} + +static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data) +{ + BMHeader *h = data; + + if (UNLIKELY(h == NULL)) { + return; + } + + bmw_LoopShellWalker_begin(walker, data); + + switch (h->htype) { + case BM_LOOP: + { + BMLoop *l = (BMLoop *)h; + bmw_LoopShellWireWalker_visitVert(walker, l->v, NULL); + break; + } + + case BM_VERT: + { + BMVert *v = (BMVert *)h; + if (v->e) { + bmw_LoopShellWireWalker_visitVert(walker, v, NULL); + } + break; + } + case BM_EDGE: + { + BMEdge *e = (BMEdge *)h; + if (bmw_mask_check_edge(walker, e)) { + bmw_LoopShellWireWalker_visitVert(walker, e->v1, NULL); + bmw_LoopShellWireWalker_visitVert(walker, e->v2, NULL); + } + else { + BMLoop *l_iter, *l_first; + + l_iter = l_first = e->l; + do { + bmw_LoopShellWalker_visitLoop(walker, l_iter); + bmw_LoopShellWalker_visitLoop(walker, l_iter->next); + } while ((l_iter = l_iter->radial_next) != l_first); + } + break; + } + case BM_FACE: + { + /* wire verts will be walked over */ + break; + } + default: + BLI_assert(0); + } +} + +static void *bmw_LoopShellWireWalker_yield(BMWalker *walker) +{ + BMwLoopShellWireWalker *shellWalk = BMW_current_state(walker); + return shellWalk->curelem; +} + +static void *bmw_LoopShellWireWalker_step(BMWalker *walker) +{ + BMwLoopShellWireWalker *swalk, owalk; + + BMW_state_remove_r(walker, &owalk); + swalk = &owalk; + + if (swalk->curelem->head.htype == BM_LOOP) { + BMLoop *l = (BMLoop *)swalk->curelem; + + bmw_LoopShellWalker_step_impl(walker, l); + + bmw_LoopShellWireWalker_visitVert(walker, l->v, NULL); + + return l; + } + else { + BMEdge *e = (BMEdge *)swalk->curelem; + + BLI_assert(e->head.htype == BM_EDGE); + + bmw_LoopShellWireWalker_visitVert(walker, e->v1, e); + bmw_LoopShellWireWalker_visitVert(walker, e->v2, e); + + return e; + } +} + +/** \} */ + /** \name FaceShell Walker * \{ @@ -544,9 +852,9 @@ static bool bm_edge_is_single(BMEdge *e) (BM_edge_is_boundary(e->l->next->e) || BM_edge_is_boundary(e->l->prev->e))); } -static void bmw_LoopWalker_begin(BMWalker *walker, void *data) +static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data) { - BMwLoopWalker *lwalk = NULL, owalk, *owalk_pt; + BMwEdgeLoopWalker *lwalk = NULL, owalk, *owalk_pt; BMEdge *e = data; BMVert *v; const int vert_edge_count[2] = { @@ -594,7 +902,7 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) /* rewind */ while ((owalk_pt = BMW_current_state(walker))) { - owalk = *((BMwLoopWalker *)owalk_pt); + owalk = *((BMwEdgeLoopWalker *)owalk_pt); BMW_walk(walker); } @@ -607,16 +915,16 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) BLI_gset_insert(walker->visit_set, owalk.cur); } -static void *bmw_LoopWalker_yield(BMWalker *walker) +static void *bmw_EdgeLoopWalker_yield(BMWalker *walker) { - BMwLoopWalker *lwalk = BMW_current_state(walker); + BMwEdgeLoopWalker *lwalk = BMW_current_state(walker); return lwalk->cur; } -static void *bmw_LoopWalker_step(BMWalker *walker) +static void *bmw_EdgeLoopWalker_step(BMWalker *walker) { - BMwLoopWalker *lwalk, owalk; + BMwEdgeLoopWalker *lwalk, owalk; BMEdge *e, *nexte = NULL; BMLoop *l; BMVert *v; @@ -738,7 +1046,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) (owalk.is_single == false && vert_edge_tot > 2) || /* initial edge was a boundary, so is this edge and vertex is only apart of this face - * this lets us walk over the the boundary of an ngon which is handy */ + * this lets us walk over the boundary of an ngon which is handy */ (owalk.is_single == true && vert_edge_tot == 2 && BM_edge_is_boundary(e))) { /* find next boundary edge in the fan */ @@ -936,7 +1244,7 @@ static void *bmw_FaceLoopWalker_step(BMWalker *walker) * * Starts at a tool-flagged edge and walks over the edge ring * Conditions for starting and stepping the edge ring have been - * tuned in an attempt to match the edge rings built by EditMesh + * tuned to match behavior users expect (dating back to v2.4x). */ static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data) { @@ -1180,17 +1488,16 @@ static void *bmw_UVEdgeWalker_yield(BMWalker *walker) static void *bmw_UVEdgeWalker_step(BMWalker *walker) { const int type = walker->bm->ldata.layers[walker->layer].type; + const int offset = walker->bm->ldata.layers[walker->layer].offset; + BMwUVEdgeWalker *lwalk, owalk; - BMLoop *l, *l2, *l3, *nl, *cl; - BMIter liter; - void *d1, *d2; - int i, j, rlen; + BMLoop *l; + int i; BMW_state_remove_r(walker, &owalk); lwalk = &owalk; l = lwalk->l; - nl = l->next; if (!bmw_mask_check_edge(walker, l->e)) { return l; @@ -1199,37 +1506,40 @@ static void *bmw_UVEdgeWalker_step(BMWalker *walker) /* go over loops around l->v and nl->v and see which ones share l and nl's * mloopuv's coordinates. in addition, push on l->next if necessary */ for (i = 0; i < 2; i++) { - cl = i ? nl : l; - BM_ITER_ELEM (l2, &liter, cl->v, BM_LOOPS_OF_VERT) { - d1 = CustomData_bmesh_get_layer_n(&walker->bm->ldata, - cl->head.data, walker->layer); - - rlen = BM_edge_face_count(l2->e); - for (j = 0; j < rlen; j++) { - if (BLI_gset_haskey(walker->visit_set, l2)) { + BMIter liter; + BMLoop *l_pivot, *l_radial; + + l_pivot = i ? l->next : l; + BM_ITER_ELEM (l_radial, &liter, l_pivot->v, BM_LOOPS_OF_VERT) { + BMLoop *l_radial_first = l_radial; + void *data_pivot = BM_ELEM_CD_GET_VOID_P(l_pivot, offset); + + do { + BMLoop *l_other; + void *data_other; + + if (BLI_gset_haskey(walker->visit_set, l_radial)) { continue; } - if (!bmw_mask_check_edge(walker, l2->e)) { - if (l2->v != cl->v) { + if (l_radial->v != l_pivot->v) { + if (!bmw_mask_check_edge(walker, l_radial->e)) { continue; } } - l3 = l2->v != cl->v ? l2->next : l2; - d2 = CustomData_bmesh_get_layer_n(&walker->bm->ldata, - l3->head.data, walker->layer); + l_other = (l_radial->v != l_pivot->v) ? l_radial->next : l_radial; + data_other = BM_ELEM_CD_GET_VOID_P(l_other, offset); - if (!CustomData_data_equals(type, d1, d2)) + if (!CustomData_data_equals(type, data_pivot, data_other)) continue; - + lwalk = BMW_state_add(walker); - BLI_gset_insert(walker->visit_set, l2); + BLI_gset_insert(walker->visit_set, l_radial); - lwalk->l = l2; + lwalk->l = l_radial; - l2 = l2->radial_next; - } + } while ((l_radial = l_radial->radial_next) != l_radial_first); } } @@ -1249,6 +1559,26 @@ static BMWalker bmw_VertShellWalker_Type = { BM_EDGE, /* valid restrict masks */ }; +static BMWalker bmw_LoopShellWalker_Type = { + BM_FACE | BM_LOOP | BM_EDGE | BM_VERT, + bmw_LoopShellWalker_begin, + bmw_LoopShellWalker_step, + bmw_LoopShellWalker_yield, + sizeof(BMwLoopShellWalker), + BMW_BREADTH_FIRST, + BM_EDGE, /* valid restrict masks */ +}; + +static BMWalker bmw_LoopShellWireWalker_Type = { + BM_FACE | BM_LOOP | BM_EDGE | BM_VERT, + bmw_LoopShellWireWalker_begin, + bmw_LoopShellWireWalker_step, + bmw_LoopShellWireWalker_yield, + sizeof(BMwLoopShellWireWalker), + BMW_BREADTH_FIRST, + BM_EDGE, /* valid restrict masks */ +}; + static BMWalker bmw_FaceShellWalker_Type = { BM_EDGE, bmw_FaceShellWalker_begin, @@ -1279,12 +1609,12 @@ static BMWalker bmw_IslandWalker_Type = { BM_EDGE | BM_FACE, /* valid restrict masks */ }; -static BMWalker bmw_LoopWalker_Type = { +static BMWalker bmw_EdgeLoopWalker_Type = { BM_EDGE, - bmw_LoopWalker_begin, - bmw_LoopWalker_step, - bmw_LoopWalker_yield, - sizeof(BMwLoopWalker), + bmw_EdgeLoopWalker_begin, + bmw_EdgeLoopWalker_step, + bmw_EdgeLoopWalker_yield, + sizeof(BMwEdgeLoopWalker), BMW_DEPTH_FIRST, 0, /* valid restrict masks */ /* could add flags here but so far none are used */ }; @@ -1341,8 +1671,10 @@ static BMWalker bmw_ConnectedVertexWalker_Type = { BMWalker *bm_walker_types[] = { &bmw_VertShellWalker_Type, /* BMW_VERT_SHELL */ + &bmw_LoopShellWalker_Type, /* BMW_LOOP_SHELL */ + &bmw_LoopShellWireWalker_Type, /* BMW_LOOP_SHELL_WIRE */ &bmw_FaceShellWalker_Type, /* BMW_FACE_SHELL */ - &bmw_LoopWalker_Type, /* BMW_LOOP */ + &bmw_EdgeLoopWalker_Type, /* BMW_EDGELOOP */ &bmw_FaceLoopWalker_Type, /* BMW_FACELOOP */ &bmw_EdgeringWalker_Type, /* BMW_EDGERING */ &bmw_EdgeboundaryWalker_Type, /* BMW_EDGEBOUNDARY */ |