bmesh: replace BLI_array reallocs with alloca, also don't check all faces for connecting verts.

2 files changed, 89 insertions, 65 deletions

diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h
index a51dcfe197c..2b86569024f 100644
--- a/source/blender/blenlib/BLI_utildefines.h
+++ b/source/blender/blenlib/BLI_utildefines.h
@@ -293,8 +293,9 @@ typedef bool _BLI_Bool;
 /* simple stack */
 #define STACK_DECLARE(stack)   unsigned int _##stack##_index
 #define STACK_INIT(stack)      ((void)stack, (void)((_##stack##_index) = 0))
-#define STACK_SIZE(stack)      ((void)stack, (void)(_##stack##_index))
+#define STACK_SIZE(stack)      ((void)stack, (_##stack##_index))
 #define STACK_PUSH(stack, val)  (void)((stack)[(_##stack##_index)++] = val)
+#define STACK_PUSH_RET(stack)  ((void)stack, ((stack)[(_##stack##_index)++]))
 #define STACK_POP(stack)       ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL)
 #define STACK_FREE(stack)      ((void)stack)
 
diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c
index 0c62330fc24..2aa97916e70 100644
--- a/source/blender/bmesh/operators/bmo_connect.c
+++ b/source/blender/bmesh/operators/bmo_connect.c
@@ -38,88 +38,111 @@
 
 #define VERT_INPUT	1
 #define EDGE_OUT	1
-#define FACE_NEW	2
+#define FACE_TAG	2
 
-void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
+static int bm_face_connect_verts(BMesh *bm, BMFace *f)
 {
-	BMIter iter, liter;
-	BMFace *f, *f_new;
-	BMLoop *(*loops_split)[2] = NULL;
-	BLI_array_declare(loops_split);
-	BMLoop *l, *l_new;
-	BMVert *(*verts_pair)[2] = NULL;
-	BLI_array_declare(verts_pair);
-	int i;
-	
-	BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_INPUT);
-
-	/* BMESH_TODO, loop over vert faces:
-	 * faster then looping over all faces, then searching each for flagged verts*/
-	BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
-		BMLoop *l_last;
-		BLI_array_empty(loops_split);
-		BLI_array_empty(verts_pair);
-		
-		if (BMO_elem_flag_test(bm, f, FACE_NEW)) {
-			continue;
-		}
+	BMLoop *(*loops_split)[2] = BLI_array_alloca(loops_split, f->len);
+	STACK_DECLARE(loops_split);
+	BMVert *(*verts_pair)[2] = BLI_array_alloca(verts_pair, f->len);
+	STACK_DECLARE(verts_pair);
 
-		l_last = NULL;
-		BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
-			if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) {
-				if (!l_last) {
-					l_last = l;
-					continue;
-				}
+	BMIter liter;
+	BMFace *f_new;
+	BMLoop *l, *l_new;
+	BMLoop *l_last;
+	unsigned int i;
 
-				if (l_last != l->prev && l_last != l->next) {
-					BLI_array_grow_one(loops_split);
-					loops_split[BLI_array_count(loops_split) - 1][0] = l_last;
-					loops_split[BLI_array_count(loops_split) - 1][1] = l;
+	STACK_INIT(loops_split);
+	STACK_INIT(verts_pair);
 
-				}
+	l_last = NULL;
+	BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
+		if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) {
+			if (!l_last) {
 				l_last = l;
+				continue;
 			}
+
+			if (l_last != l->prev && l_last != l->next) {
+				BMLoop **l_pair = STACK_PUSH_RET(loops_split);
+				l_pair[0] = l_last;
+				l_pair[1] = l;
+			}
+			l_last = l;
 		}
+	}
+
+	if (STACK_SIZE(loops_split) == 0) {
+		return 0;
+	}
 
-		if (BLI_array_count(loops_split) == 0) {
+	if (STACK_SIZE(loops_split) > 1) {
+		BMLoop **l_pair = STACK_PUSH_RET(loops_split);
+		l_pair[0] = loops_split[STACK_SIZE(loops_split) - 2][1];
+		l_pair[1] = loops_split[0][0];
+	}
+
+	BM_face_legal_splits(bm, f, loops_split, STACK_SIZE(loops_split));
+
+	for (i = 0; i < STACK_SIZE(loops_split); i++) {
+		BMVert **v_pair;
+		if (loops_split[i][0] == NULL) {
 			continue;
 		}
-		
-		if (BLI_array_count(loops_split) > 1) {
-			BLI_array_grow_one(loops_split);
-			loops_split[BLI_array_count(loops_split) - 1][0] = loops_split[BLI_array_count(loops_split) - 2][1];
-			loops_split[BLI_array_count(loops_split) - 1][1] = loops_split[0][0];
-		}
 
-		BM_face_legal_splits(bm, f, loops_split, BLI_array_count(loops_split));
-		
-		for (i = 0; i < BLI_array_count(loops_split); i++) {
-			if (loops_split[i][0] == NULL) {
-				continue;
-			}
+		v_pair = STACK_PUSH_RET(verts_pair);
+		v_pair[0] = loops_split[i][0]->v;
+		v_pair[1] = loops_split[i][1]->v;
+	}
+
+	for (i = 0; i < STACK_SIZE(verts_pair); i++) {
+		f_new = BM_face_split(bm, f, verts_pair[i][0], verts_pair[i][1], &l_new, NULL, false);
+		f = f_new;
 
-			BLI_array_grow_one(verts_pair);
-			verts_pair[BLI_array_count(verts_pair) - 1][0] = loops_split[i][0]->v;
-			verts_pair[BLI_array_count(verts_pair) - 1][1] = loops_split[i][1]->v;
+		if (!l_new || !f_new) {
+			return -1;
 		}
+		// BMO_elem_flag_enable(bm, f_new, FACE_NEW);
+		BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT);
+	}
+
+	return 1;
+}
+
 
-		for (i = 0; i < BLI_array_count(verts_pair); i++) {
-			f_new = BM_face_split(bm, f, verts_pair[i][0], verts_pair[i][1], &l_new, NULL, false);
-			f = f_new;
-			
-			if (!l_new || !f_new) {
-				BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
-				BLI_array_free(loops_split);
-				return;
+void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
+{
+	BMOIter siter;
+	BMIter iter;
+	BMVert *v;
+	BMFace *f;
+	BMFace **faces = MEM_mallocN(sizeof(BMFace *) * bm->totface, __func__);
+	STACK_DECLARE(faces);
+
+	STACK_INIT(faces);
+
+	/* add all faces connected to verts */
+	BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
+		BMO_elem_flag_enable(bm, v, VERT_INPUT);
+		BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
+			if (!BMO_elem_flag_test(bm, f, FACE_TAG)) {
+				BMO_elem_flag_enable(bm, f, FACE_TAG);
+				if (f->len > 3) {
+					STACK_PUSH(faces, f);
+				}
 			}
-			BMO_elem_flag_enable(bm, f_new, FACE_NEW);
-			BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT);
 		}
 	}
 
-	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
+	/* connect faces */
+	while ((f = STACK_POP(faces))) {
+		if (bm_face_connect_verts(bm, f) == -1) {
+			BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
+		}
+	}
 
-	BLI_array_free(loops_split);
-	BLI_array_free(verts_pair);
+	MEM_freeN(faces);
+
+	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
 }