Fix T52384: Bridge pair result depends on other loops

When 2x loops have different number of vertices,
the distribution for vertices fan-fill depended on the loop order
and was often lop-sided.

This caused noticeable inconstancies depending on the input
since edge-loops are flipped to match each others winding order.

1 files changed, 53 insertions, 30 deletions

diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c
index 5780dc57d78..16c1b2cc6d0 100644
--- a/source/blender/bmesh/intern/bmesh_edgeloop.c
+++ b/source/blender/bmesh/intern/bmesh_edgeloop.c
@@ -708,41 +708,64 @@ 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;
+		/**
+		 * Bresenham's line algorithm is used for even spaced edge-loop distribution.
+		 *
+		 * Step over x until y reaches a large enough error and a new pivot is added.
+		 * Note that x/y aren't meaningful in this context, but keep since logic matches line drawing.
+		 */
+		const int x_span = el_store->len;
+		const int y_span = el_store_len - el_store->len;
+
+		const int x_span_2x = x_span * 2;
+		const int y_span_2x = y_span * 2;
+
+		BLI_assert(x_span >= y_span);
+
+		/* error may go below zero */
+		int error = y_span_2x - x_span;
+
+		int x_iter = 0;  /* traverse elements in 'el_store->len'. */
+		int y_iter = 0;  /* each step on this variable represents a new pivot. */
+
+		while (x_iter != x_span) {
+			if (error >= 0) {
+				y_iter += 1;
+				error -= x_span_2x;
+
+				/* Split logic */
+				{
+					LinkData *node_curr_copy;
+					node_curr_copy = MEM_dupallocN(node_curr);
+					if (split == false) {
+						BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
+						node_curr = node_curr_copy->next;
+					}
+					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);
+							BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
+							node_curr = node_curr_copy->next;
+						}
+						else {
+							EDGE_SPLIT(node_curr_copy, node_curr->prev);
+							BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy);
+							node_curr = node_curr->next;
+						}
+						split_swap = !split_swap;
+					}
+					el_store->len++;
 				}
 			}
-			BLI_LISTBASE_CIRCULAR_FORWARD_END (&el_store->verts, node_curr, node_curr_init);
-
-			node_curr_copy = MEM_dupallocN(node_curr);
-			if (split == false) {
-				BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
-				node_curr = node_curr_copy->next;
-			}
 			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);
-					BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
-					node_curr = node_curr_copy->next;
-				}
-				else {
-					EDGE_SPLIT(node_curr_copy, node_curr->prev);
-					BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy);
-					node_curr = node_curr->next;
-				}
-				split_swap = !split_swap;
+				node_curr = node_curr->next;
 			}
-			el_store->len++;
-		} while (el_store->len < el_store_len);
+			x_iter += 1;
+			error += y_span_2x;
+		}
 	}
 
 #undef EDGE_SPLIT