bmesh edgeloop utility function, calculates an edge loop from 2 verts (start and endpoint).

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;