diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-05-15 10:27:48 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-05-15 10:27:48 +0400 |
commit | cd089ea321666817336e5bb7b3eba7d4ecc74479 (patch) | |
tree | 846b0667c52d95befdbdccf80d7a0b3b97b9c4e6 /source/blender/bmesh/intern/bmesh_edgeloop.c | |
parent | be409d446c5d34d41d35c1ca9f7ec82547a152e5 (diff) |
bmesh edgeloop utility function, calculates an edge loop from 2 verts (start and endpoint).
Diffstat (limited to 'source/blender/bmesh/intern/bmesh_edgeloop.c')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_edgeloop.c | 193 |
1 files changed, 193 insertions, 0 deletions
diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c index 60ed3a49378..1ab7652502c 100644 --- a/source/blender/bmesh/intern/bmesh_edgeloop.c +++ b/source/blender/bmesh/intern/bmesh_edgeloop.c @@ -31,6 +31,7 @@ #include "BLI_math_vector.h" #include "BLI_listbase.h" +#include "BLI_mempool.h" #include "bmesh.h" @@ -47,6 +48,10 @@ typedef struct BMEdgeLoopStore { #define BM_EDGELOOP_IS_CLOSED (1 << 0) + +/* -------------------------------------------------------------------- */ +/* BM_mesh_edgeloops_find & Util Functions */ + static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, BMEdge **r_e) { @@ -165,6 +170,194 @@ int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops, return count; } + +/* -------------------------------------------------------------------- */ +/* BM_mesh_edgeloops_find_path & Util Functions */ + +/** + * Find s single, open edge loop - given 2 vertices. + * Add to + */ +struct VertStep { + struct VertStep *next, *prev; + BMVert *v; +}; + +static void vs_add(BLI_mempool *vs_pool, ListBase *lb, + BMVert *v, BMEdge *e_prev, const int iter_tot) +{ + struct VertStep *vs_new = BLI_mempool_alloc(vs_pool); + vs_new->v = v; + + BM_elem_index_set(v, iter_tot); + + /* This edge stores a direct path back to the original vertex so we can + * backtrack without having to store an array of previous verts. */ + + /* WARNING - setting the edge is not common practice + * but currently harmless, take care. */ + BLI_assert(BM_vert_in_edge(e_prev, v)); + v->e = e_prev; + + BLI_addtail(lb, vs_new); +} + +static bool bm_loop_path_build_step(BLI_mempool *vs_pool, ListBase *lb, const int dir, BMVert *v_match[2]) +{ + ListBase lb_tmp = {NULL, NULL}; + struct VertStep *vs, *vs_next; + BLI_assert(ABS(dir) == 1); + + for (vs = lb->first; vs; vs = vs_next) { + BMIter iter; + BMEdge *e; + /* these values will be the same every iteration */ + const int vs_iter_tot = BM_elem_index_get(vs->v); + const int vs_iter_next = vs_iter_tot + dir; + + vs_next = vs->next; + + BM_ITER_ELEM (e, &iter, vs->v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) { + BMVert *v_next = BM_edge_other_vert(e, vs->v); + const int v_next_index = BM_elem_index_get(v_next); + /* not essential to clear flag but prevents more checking next time round */ + BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG); + if (v_next_index == 0) { + vs_add(vs_pool, &lb_tmp, v_next, e, vs_iter_next); + } + else if ((dir < 0) == (v_next_index < 0)) { + /* on the same side - do nothing */ + } + else { + /* we have met out match! (vertices from differnt sides meet) */ + if (dir == 1) { + v_match[0] = vs->v; + v_match[1] = v_next; + } + else { + v_match[0] = v_next; + v_match[1] = vs->v; + } + /* normally we would manage memory of remaining items in (lb, lb_tmp), + * but search is done, vs_pool will get destroyed immediately */ + return true; + } + } + } + + BLI_mempool_free(vs_pool, vs); + } + + /* lb is now full of free'd items, overwrite */ + *lb = lb_tmp; + + return (lb->first != NULL); +} + +bool BM_mesh_edgeloops_find_path(BMesh *bm, ListBase *r_eloops, + bool (*test_fn)(BMEdge *, void *user_data), void *user_data, + BMVert *v_src, BMVert *v_dst) +{ + BMIter iter; + BMEdge *e; + + BLI_assert(v_src != v_dst); + + { + BMVert *v; + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + BM_elem_index_set(v, 0); + } + } + bm->elem_index_dirty |= BM_VERT; + + /* first flush edges to tags, and tag verts */ + if (test_fn) { + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (test_fn(e, user_data)) { + BM_elem_flag_enable(e, BM_ELEM_INTERNAL_TAG); + BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG); + BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG); + } + else { + BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG); + } + } + } + else { + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + BM_elem_flag_enable(e, BM_ELEM_INTERNAL_TAG); + BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG); + BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG); + } + } + + /* prime the lists and begin search */ + { + BMVert *v_match[2] = {NULL, NULL}; + ListBase lb_src = {NULL, NULL}; + ListBase lb_dst = {NULL, NULL}; + BLI_mempool *vs_pool = BLI_mempool_create(sizeof(struct VertStep), 1, 512, 0); + + /* edge args are dummy */ + vs_add(vs_pool, &lb_src, v_src, v_src->e, 1); + vs_add(vs_pool, &lb_dst, v_dst, v_dst->e, -1); + + do { + if ((bm_loop_path_build_step(vs_pool, &lb_src, 1, v_match) == false) || v_match[0]) { + break; + } + if ((bm_loop_path_build_step(vs_pool, &lb_dst, -1, v_match) == false) || v_match[0]) { + break; + } + } while (true); + + BLI_mempool_destroy(vs_pool); + + if (v_match[0]) { + BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__); + BMVert *v; + + /* build loop from edge pointers */ + v = v_match[0]; + while (true) { + LinkData *node = MEM_callocN(sizeof(*node), __func__); + node->data = v; + BLI_addhead(&el_store->verts, node); + el_store->len++; + if (v == v_src) { + break; + } + v = BM_edge_other_vert(v->e, v); + } + + v = v_match[1]; + while (true) { + LinkData *node = MEM_callocN(sizeof(*node), __func__); + node->data = v; + BLI_addtail(&el_store->verts, node); + el_store->len++; + if (v == v_dst) { + break; + } + v = BM_edge_other_vert(v->e, v); + } + + + BLI_addtail(r_eloops, el_store); + + return true; + } + } + + return false; +} + + +/* -------------------------------------------------------------------- */ +/* BM_mesh_edgeloops_xxx utility function */ + void BM_mesh_edgeloops_free(ListBase *eloops) { BMEdgeLoopStore *el_store; |