bridge tool: support for bridging loops with different numbers of vertices.

3 files changed, 152 insertions, 27 deletions

diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c
index 1c302668409..2f68effc97a 100644
--- a/source/blender/bmesh/intern/bmesh_edgeloop.c
+++ b/source/blender/bmesh/intern/bmesh_edgeloop.c
@@ -157,7 +157,8 @@ int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops,
 				count++;
 			}
 			else {
-				BM_edgeloop_free(r_eloops, el_store);
+				BLI_remlink(r_eloops, el_store);
+				BM_edgeloop_free(el_store);
 			}
 		}
 	}
@@ -168,7 +169,8 @@ void BM_mesh_edgeloops_free(ListBase *eloops)
 {
 	BMEdgeLoopStore *el_store;
 	while ((el_store = eloops->first)) {
-		BM_edgeloop_free(eloops, el_store);
+		BLI_remlink(eloops, el_store);
+		BM_edgeloop_free(el_store);
 	}
 }
 
@@ -240,10 +242,17 @@ void BM_mesh_edgeloops_calc_order(BMesh *UNUSED(bm), ListBase *eloops)
 /* -------------------------------------------------------------------- */
 /* BM_edgeloop_*** functions */
 
-void BM_edgeloop_free(ListBase *eloops, BMEdgeLoopStore *el_store)
+BMEdgeLoopStore *BM_edgeloop_copy(BMEdgeLoopStore *el_store)
+{
+	BMEdgeLoopStore *el_store_copy = MEM_mallocN(sizeof(*el_store), __func__);
+	*el_store_copy = *el_store;
+	BLI_duplicatelist(&el_store_copy->verts, &el_store->verts);
+	return el_store_copy;
+}
+
+void BM_edgeloop_free(BMEdgeLoopStore *el_store)
 {
 	BLI_freelistN(&el_store->verts);
-	BLI_remlink(eloops, el_store);
 	MEM_freeN(el_store);
 }
 
@@ -347,3 +356,42 @@ void BM_edgeloop_flip(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
 	negate_v3(el_store->no);
 	BLI_reverselist(&el_store->verts);
 }
+
+void BM_edgeloop_expand(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store, int el_store_len)
+{
+	/* first double until we are more then half as big */
+	while ((el_store->len * 2) < el_store_len) {
+		LinkData *node_curr = el_store->verts.first;
+		while (node_curr) {
+			LinkData *node_curr_copy = MEM_dupallocN(node_curr);
+			BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
+			el_store->len++;
+			node_curr = node_curr_copy->next;
+		}
+	}
+
+	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;
+
+		do {
+			LinkData *node_curr_init = node_curr;
+			LinkData *node_curr_copy;
+			int i = 0;
+			LISTBASE_CIRCULAR_FORWARD_BEGIN (&el_store->verts, node_curr, node_curr_init) {
+				if (i++ < step) {
+					break;
+				}
+			}
+			LISTBASE_CIRCULAR_FORWARD_END (&el_store->verts, node_curr, node_curr_init);
+
+			node_curr_copy = MEM_dupallocN(node_curr);
+			BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
+			el_store->len++;
+			node_curr = node_curr_copy->next;
+		} while (el_store->len < el_store_len);
+	}
+
+	BLI_assert(el_store->len == el_store_len);
+}
diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.h b/source/blender/bmesh/intern/bmesh_edgeloop.h
index e6ea65fa85d..b569f0cf4ce 100644
--- a/source/blender/bmesh/intern/bmesh_edgeloop.h
+++ b/source/blender/bmesh/intern/bmesh_edgeloop.h
@@ -42,7 +42,8 @@ void                BM_mesh_edgeloops_calc_order(BMesh *UNUSED(bm), ListBase *el
 
 
 /* single edgeloop */
-void                BM_edgeloop_free(struct ListBase *eloops, struct BMEdgeLoopStore *el_store);
+struct BMEdgeLoopStore *BM_edgeloop_copy(struct BMEdgeLoopStore *el_store);
+void                BM_edgeloop_free(struct BMEdgeLoopStore *el_store);
 bool                BM_edgeloop_is_closed(struct BMEdgeLoopStore *el_store);
 int                 BM_edgeloop_length_get(struct BMEdgeLoopStore *el_store);
 struct ListBase    *BM_edgeloop_verts_get(struct BMEdgeLoopStore *el_store);
@@ -51,6 +52,7 @@ const float        *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store);
 void                BM_edgeloop_calc_center(BMesh *bm, struct BMEdgeLoopStore *el_store);
 void                BM_edgeloop_calc_normal(BMesh *bm, struct BMEdgeLoopStore *el_store);
 void                BM_edgeloop_flip(BMesh *bm, struct BMEdgeLoopStore *el_store);
+void                BM_edgeloop_expand(BMesh *bm, struct BMEdgeLoopStore *el_store, int el_store_len);
 
 #define BM_EDGELOOP_NEXT(el_store, elink) \
 	(elink)->next ? elink->next : (BM_edgeloop_is_closed(el_store) ? BM_edgeloop_verts_get(el_store)->first : NULL)
diff --git a/source/blender/bmesh/operators/bmo_bridge.c b/source/blender/bmesh/operators/bmo_bridge.c
index 5642cc5e8c1..9995cf43c25 100644
--- a/source/blender/bmesh/operators/bmo_bridge.c
+++ b/source/blender/bmesh/operators/bmo_bridge.c
@@ -118,6 +118,24 @@ static void bridge_loop_pair(BMesh *bm,
 {
 	LinkData *el_a_first, *el_b_first;
 	const bool is_closed = BM_edgeloop_is_closed(el_store_a) && BM_edgeloop_is_closed(el_store_b);
+	int el_store_a_len, el_store_b_len;
+	bool el_store_b_free = false;
+
+	el_store_a_len = BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store_a);
+	el_store_b_len = BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store_b);
+
+	if (el_store_a_len < el_store_b_len) {
+		SWAP(int, el_store_a_len, el_store_b_len);
+		SWAP(struct BMEdgeLoopStore *, el_store_a, el_store_b);
+	}
+
+	if (use_merge) {
+		BLI_assert((el_store_a_len == el_store_a_len));
+	}
+
+	if (el_store_a_len != el_store_b_len) {
+		BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false);
+	}
 
 	if (dot_v3v3(BM_edgeloop_normal_get(el_store_a), BM_edgeloop_normal_get(el_store_b)) < 0.0f) {
 		BM_edgeloop_flip(bm, el_store_b);
@@ -139,7 +157,7 @@ static void bridge_loop_pair(BMesh *bm,
 		/* vote on winding (so new face winding is based on existing connected faces) */
 		if (bm->totface) {
 			struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
-			int i = 0;
+			int i;
 			int winding_votes = 0;
 			int winding_dir = 1;
 			for (i = 0; i < 2; i++, winding_dir = -winding_dir) {
@@ -160,6 +178,12 @@ static void bridge_loop_pair(BMesh *bm,
 		}
 	}
 
+	if (el_store_a_len > el_store_b_len) {
+		el_store_b = BM_edgeloop_copy(el_store_b);
+		BM_edgeloop_expand(bm, el_store_b, el_store_a_len);
+		el_store_b_free = true;
+	}
+
 	if (is_closed) {
 		bm_bridge_best_rotation(el_store_a, el_store_b);
 	}
@@ -253,44 +277,95 @@ static void bridge_loop_pair(BMesh *bm,
 			v_b_next = el_b_next->data;
 
 			/* get loop data - before making the face */
-			bm_vert_loop_pair(bm, v_a, v_b, &l_1, &l_2);
-			bm_vert_loop_pair(bm, v_a_next, v_b_next, &l_1_next, &l_2_next);
-			/* copy if loop data if its is missing on one ring */
+			if (v_b != v_b_next) {
+				bm_vert_loop_pair(bm, v_a, v_b, &l_1, &l_2);
+				bm_vert_loop_pair(bm, v_a_next, v_b_next, &l_1_next, &l_2_next);
+			}
+			else {
+				/* lazy, could be more clever here */
+				l_1      = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v_a, 0);
+				l_1_next = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v_a_next, 0);
+				l_2      = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v_b, 0);
+				l_2_next = l_2;
+			}
+
 			if (l_1 && l_1_next == NULL) l_1_next = l_1;
 			if (l_1_next && l_1 == NULL) l_1 = l_1_next;
 			if (l_2 && l_2_next == NULL) l_2_next = l_2;
 			if (l_2_next && l_2 == NULL) l_2 = l_2_next;
 			f_example = l_1 ? l_1->f : (l_2 ? l_2->f : NULL);
 
-			f = BM_face_create_quad_tri(bm,
-			                            el_a->data,
-			                            el_b->data,
-			                            el_b_next->data,
-			                            el_a_next->data,
-			                            f_example, true);
-			BMO_elem_flag_enable(bm, f, FACE_OUT);
-			if (el_a_next == el_a_first) {
-				break;
+			if (v_b != v_b_next) {
+				/* copy if loop data if its is missing on one ring */
+				f = BM_face_create_quad_tri(bm, v_a, v_b, v_b_next, v_a_next, f_example, true);
+				BMO_elem_flag_enable(bm, f, FACE_OUT);
+				BM_elem_flag_enable(f, BM_ELEM_TAG);
+
+				l_iter = BM_FACE_FIRST_LOOP(f);
+
+				if (l_1)      BM_elem_attrs_copy(bm, bm, l_1,      l_iter); l_iter = l_iter->next;
+				if (l_2)      BM_elem_attrs_copy(bm, bm, l_2,      l_iter); l_iter = l_iter->next;
+				if (l_2_next) BM_elem_attrs_copy(bm, bm, l_2_next, l_iter); l_iter = l_iter->next;
+				if (l_1_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter);
 			}
+			else {
+				/* fan-fill a triangle */
+				f = BM_face_create_quad_tri(bm, v_a, v_b, v_a_next, NULL, f_example, true);
+				BMO_elem_flag_enable(bm, f, FACE_OUT);
+				BM_elem_flag_enable(f, BM_ELEM_TAG);
 
-			l_iter = BM_FACE_FIRST_LOOP(f);
+				l_iter = BM_FACE_FIRST_LOOP(f);
 
-			if (l_1)      BM_elem_attrs_copy(bm, bm, l_1,      l_iter); l_iter = l_iter->next;
-			if (l_2)      BM_elem_attrs_copy(bm, bm, l_2,      l_iter); l_iter = l_iter->next;
-			if (l_2_next) BM_elem_attrs_copy(bm, bm, l_2_next, l_iter); l_iter = l_iter->next;
-			if (l_1_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter);
+				if (l_1)      BM_elem_attrs_copy(bm, bm, l_1,      l_iter); l_iter = l_iter->next;
+				if (l_2)      BM_elem_attrs_copy(bm, bm, l_2,      l_iter); l_iter = l_iter->next;
+				if (l_2_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter);
+			}
+
+			if (el_a_next == el_a_first) {
+				break;
+			}
 
 			el_a = el_a_next;
 			el_b = el_b_next;
 		}
 	}
+
+	if (el_store_a_len != el_store_b_len) {
+		struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
+		int i;
+
+		BMOperator op_sub;
+		/* when we have to bridge betweeen different sized edge-loops,
+		 * be clever and post-process for best results */
+		BM_mesh_triangulate(bm, true, true, NULL, NULL);
+
+		/* tag verts on each side so we can restrict rotation of edges to verts on the same side */
+		for (i = 0; i < 2; i++) {
+			LinkData *el;
+			for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) {
+				BM_elem_flag_set((BMVert *)el->data, BM_ELEM_TAG, i);
+			}
+		}
+
+		BMO_op_initf(bm, &op_sub, 0,
+		             "beautify_fill faces=%hf edges=ae use_restrict_tag=%b",
+		             BM_ELEM_TAG, true);
+		BMO_op_exec(bm, &op_sub);
+		/* there may also be tagged faces that didnt rotate, mark input */
+		BMO_slot_buffer_flag_enable(bm, op_sub.slots_in, "faces", BM_FACE, FACE_OUT);
+		BMO_slot_buffer_flag_enable(bm, op_sub.slots_out, "geom.out", BM_FACE, FACE_OUT);
+		BMO_op_finish(bm, &op_sub);
+	}
+
+	if (el_store_b_free) {
+		BM_edgeloop_free(el_store_b);
+	}
 }
 
 void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op)
 {
 	ListBase eloops = {NULL};
 	LinkData *el_store;
-	int eloop_len;
 
 	/* merge-bridge support */
 	const bool  use_merge    = BMO_slot_bool_get(op->slots_in,  "use_merge");
@@ -310,11 +385,11 @@ void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op)
 		BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
 		                "Select at least two edge loops");
 		goto cleanup;
-
 	}
-	else {
+
+	if (use_merge) {
 		bool match = true;
-		eloop_len = BM_edgeloop_length_get(eloops.first);
+		const int eloop_len = BM_edgeloop_length_get(eloops.first);
 		for (el_store = eloops.first; el_store; el_store = el_store->next) {
 			if (eloop_len != BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store)) {
 				match = false;