1 files changed, 75 insertions, 24 deletions

diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c
index 5e1d9c3a98d..54fe2801d0c 100644
--- a/source/blender/bmesh/intern/bmesh_edgeloop.c
+++ b/source/blender/bmesh/intern/bmesh_edgeloop.c
@@ -32,6 +32,8 @@
 #include "BLI_math_vector.h"
 #include "BLI_listbase.h"
 #include "BLI_mempool.h"
+#include "BLI_utildefines_iter.h"
+#include "BLI_stack.h"
 
 #include "bmesh.h"
 
@@ -58,7 +60,7 @@ static int bm_vert_other_tag(
 {
 	BMIter iter;
 	BMEdge *e, *e_next = NULL;
-	unsigned int count = 0;
+	uint count = 0;
 
 	BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
 		if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
@@ -140,18 +142,27 @@ int BM_mesh_edgeloops_find(
 	}
 
 	/* first flush edges to tags, and tag verts */
+	BLI_Stack *edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
 	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		BLI_assert(!BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG));
 		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);
+			BLI_stack_push(edge_stack, (void *)&e);
 		}
 		else {
 			BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
 		}
 	}
 
-	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+	const uint edges_len = BLI_stack_count(edge_stack);
+	BMEdge **edges = MEM_mallocN(sizeof(*edges) * edges_len, __func__);
+	BLI_stack_pop_n_reverse(edge_stack, edges, BLI_stack_count(edge_stack));
+	BLI_stack_free(edge_stack);
+	
+	for (uint i = 0; i < edges_len; i += 1) {
+		e = edges[i];
 		if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
 			BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__);
 
@@ -161,7 +172,6 @@ int BM_mesh_edgeloops_find(
 			    el_store->len > 1)
 			{
 				BLI_addtail(r_eloops, el_store);
-				BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
 				count++;
 			}
 			else {
@@ -169,6 +179,15 @@ int BM_mesh_edgeloops_find(
 			}
 		}
 	}
+
+	for (uint i = 0; i < edges_len; i += 1) {
+		e = edges[i];
+		BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
+		BM_elem_flag_disable(e->v1, BM_ELEM_INTERNAL_TAG);
+		BM_elem_flag_disable(e->v2, BM_ELEM_INTERNAL_TAG);
+	}
+
+	MEM_freeN(edges);
 	return count;
 }
 
@@ -266,6 +285,7 @@ bool BM_mesh_edgeloops_find_path(
 {
 	BMIter iter;
 	BMEdge *e;
+	bool found = false;
 
 	BLI_assert(v_src != v_dst);
 
@@ -273,28 +293,43 @@ bool BM_mesh_edgeloops_find_path(
 		BMVert *v;
 		BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
 			BM_elem_index_set(v, 0);
+			BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
 		}
 	}
 	bm->elem_index_dirty |= BM_VERT;
 
 	/* first flush edges to tags, and tag verts */
+	int edges_len;
+	BMEdge **edges;
+
 	if (test_fn) {
+		BLI_Stack *edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
 		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);
+				BLI_stack_push(edge_stack, (void *)&e);
 			}
 			else {
 				BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
 			}
 		}
+		edges_len = BLI_stack_count(edge_stack);
+		edges = MEM_mallocN(sizeof(*edges) * edges_len, __func__);
+		BLI_stack_pop_n_reverse(edge_stack, edges, BLI_stack_count(edge_stack));
+		BLI_stack_free(edge_stack);
 	}
 	else {
-		BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		int i = 0;
+		edges_len = bm->totedge;
+		edges = MEM_mallocN(sizeof(*edges) * edges_len, __func__);
+
+		BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
 			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);
+			edges[i] = e;
 		}
 	}
 
@@ -353,11 +388,19 @@ bool BM_mesh_edgeloops_find_path(
 
 			BLI_addtail(r_eloops, el_store);
 
-			return true;
+			found = true;
 		}
 	}
 
-	return false;
+	for (uint i = 0; i < edges_len; i += 1) {
+		e = edges[i];
+		BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
+		BM_elem_flag_disable(e->v1, BM_ELEM_INTERNAL_TAG);
+		BM_elem_flag_disable(e->v2, BM_ELEM_INTERNAL_TAG);
+	}
+	MEM_freeN(edges);
+
+	return found;
 }
 
 
@@ -708,21 +751,16 @@ void BM_edgeloop_expand(
 	}
 
 	if (el_store->len < el_store_len) {
-		const int step = max_ii(1, el_store->len / (el_store->len % el_store_len));
-		LinkData *node_first = el_store->verts.first;
-		LinkData *node_curr = node_first;
+		LinkData *node_curr = el_store->verts.first;
 
-		do {
-			LinkData *node_curr_init = node_curr;
-			LinkData *node_curr_copy;
-			int i = 0;
-			BLI_LISTBASE_CIRCULAR_FORWARD_BEGIN (&el_store->verts, node_curr, node_curr_init) {
-				if (i++ < step) {
-					break;
-				}
+		int iter_prev = 0;
+		BLI_FOREACH_SPARSE_RANGE(el_store->len, (el_store_len - el_store->len), iter) {
+			while (iter_prev < iter) {
+				node_curr = node_curr->next;
+				iter_prev += 1;
 			}
-			BLI_LISTBASE_CIRCULAR_FORWARD_END (&el_store->verts, node_curr, node_curr_init);
 
+			LinkData *node_curr_copy;
 			node_curr_copy = MEM_dupallocN(node_curr);
 			if (split == false) {
 				BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
@@ -730,7 +768,8 @@ void BM_edgeloop_expand(
 			}
 			else {
 				if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) {
-					EDGE_SPLIT(node_curr_copy, node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first);
+					EDGE_SPLIT(node_curr_copy,
+					           node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first);
 					BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
 					node_curr = node_curr_copy->next;
 				}
@@ -742,9 +781,11 @@ void BM_edgeloop_expand(
 				split_swap = !split_swap;
 			}
 			el_store->len++;
-		} while (el_store->len < el_store_len);
+			iter_prev += 1;
+		}
 	}
 
+#undef BKE_FOREACH_SUBSET_OF_RANGE
 #undef EDGE_SPLIT
 
 	BLI_assert(el_store->len == el_store_len);
@@ -754,19 +795,29 @@ bool BM_edgeloop_overlap_check(struct BMEdgeLoopStore *el_store_a, struct BMEdge
 {
 	LinkData *node;
 
+	/* A little more efficient if 'a' as smaller. */
+	if (el_store_a->len > el_store_b->len) {
+		SWAP(BMEdgeLoopStore *, el_store_a, el_store_b);
+	}
+
 	/* init */
 	for (node = el_store_a->verts.first; node; node = node->next) {
-		BM_elem_flag_disable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
+		BM_elem_flag_enable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
 	}
 	for (node = el_store_b->verts.first; node; node = node->next) {
-		BM_elem_flag_enable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
+		BM_elem_flag_disable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
 	}
 
-	/* check 'a' */
+	/* Check 'a' (clear as we go). */
 	for (node = el_store_a->verts.first; node; node = node->next) {
-		if (BM_elem_flag_test((BMVert *)node->data, BM_ELEM_INTERNAL_TAG)) {
+		if (!BM_elem_flag_test((BMVert *)node->data, BM_ELEM_INTERNAL_TAG)) {
+			/* Finish clearing 'a', leave tag clean. */
+			while ((node = node->next)) {
+				BM_elem_flag_disable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
+			}
 			return true;
 		}
+		BM_elem_flag_disable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
 	}
 	return false;
 }