[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [56811] trunk/blender/source/blender/bmesh /intern: bmesh edgeloop utility function, calculates an edge loop from 2 verts (start and endpoint).

Campbell Barton ideasman42 at gmail.com
Wed May 15 08:27:48 CEST 2013


Revision: 56811
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=56811
Author:   campbellbarton
Date:     2013-05-15 06:27:48 +0000 (Wed, 15 May 2013)
Log Message:
-----------
bmesh edgeloop utility function, calculates an edge loop from 2 verts (start and endpoint).

Modified Paths:
--------------
    trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c
    trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c	2013-05-15 05:56:49 UTC (rev 56810)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c	2013-05-15 06:27:48 UTC (rev 56811)
@@ -31,6 +31,7 @@
 
 #include "BLI_math_vector.h"
 #include "BLI_listbase.h"
+#include "BLI_mempool.h"
 
 #include "bmesh.h"
 
@@ -47,6 +48,10 @@
 
 #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 @@
 	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;

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h	2013-05-15 05:56:49 UTC (rev 56810)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h	2013-05-15 06:27:48 UTC (rev 56811)
@@ -34,6 +34,9 @@
 /* multiple edgeloops (ListBase) */
 int                 BM_mesh_edgeloops_find(BMesh *bm, struct ListBase *r_lb,
                                            bool (*test_fn)(BMEdge *, void *user_data), void *user_data);
+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);
 
 void                BM_mesh_edgeloops_free(struct ListBase *eloops);
 void                BM_mesh_edgeloops_calc_center(BMesh *bm, struct ListBase *eloops);




More information about the Bf-blender-cvs mailing list