fix [#34603] ALT-F fails, freezes, CPU=100%

The way beauty fill was working was too fragile and prone to eternal loops,
Solution used is to is to store previous states and ensure edges don't get rotated back into those.

Also added an optimization to avoid testing the same edge rotation many times - using edge tags to only re-test edge rotations around areas that have been modified.

1 files changed, 149 insertions, 6 deletions

diff --git a/source/blender/bmesh/operators/bmo_beautify.c b/source/blender/bmesh/operators/bmo_beautify.c
index 88b82c390fd..849eb1197d7 100644
--- a/source/blender/bmesh/operators/bmo_beautify.c
+++ b/source/blender/bmesh/operators/bmo_beautify.c
@@ -37,30 +37,147 @@
 #  include "PIL_time.h"
 #endif
 
+/* -------------------------------------------------------------------- */
+/* GHash for edge rotation */
+
+typedef struct EdRotState {
+	int v1, v2; /*	edge vert, small -> large */
+	int f1, f2; /*	face vert, small -> large */
+} EdRotState;
+
+static unsigned int erot_ghashutil_hash(const void *ptr)
+{
+	const EdRotState *e_state = (const EdRotState *)ptr;
+	unsigned int
+	hash  = BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->v1));
+	hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->v2));
+	hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f1));
+	hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f2));
+	return hash;
+}
+static int erot_ghashutil_cmp(const void *a, const void *b)
+{
+	const EdRotState *e_state_a = (const EdRotState *)a;
+	const EdRotState *e_state_b = (const EdRotState *)b;
+	if      (e_state_a->v1 < e_state_b->v1) return -1;
+	else if (e_state_a->v1 > e_state_b->v1) return  1;
+	else if (e_state_a->v2 < e_state_b->v2) return -1;
+	else if (e_state_a->v2 > e_state_b->v2) return  1;
+	else if (e_state_a->f1 < e_state_b->f1) return -1;
+	else if (e_state_a->f1 > e_state_b->f1) return  1;
+	else if (e_state_a->f2 < e_state_b->f2) return -1;
+	else if (e_state_a->f2 > e_state_b->f2) return  1;
+	else                                    return  0;
+}
+
+static GHash *erot_ghash_new(void)
+{
+	return BLI_ghash_new(erot_ghashutil_hash, erot_ghashutil_cmp, __func__);
+}
+
+/* ensure v0 is smaller */
+#define EDGE_ORD(v0, v1) \
+	if (v0 > v1) {       \
+		v0 ^= v1;        \
+		v1 ^= v0;        \
+		v0 ^= v1;        \
+	} (void)0
+
+static void erot_state_ex(const BMEdge *e, int v_index[2], int f_index[2])
+{
+	BLI_assert(BM_edge_is_manifold((BMEdge *)e));
+	/* verts of the edge */
+	v_index[0] = BM_elem_index_get(e->v1);
+	v_index[1] = BM_elem_index_get(e->v2);
+	EDGE_ORD(v_index[0], v_index[1]);
+
+	/* verts of each of the 2 faces attached to this edge
+	 * (that are not apart of this edge) */
+	f_index[0] = BM_elem_index_get(e->l->prev->v);
+	f_index[1] = BM_elem_index_get(e->l->radial_next->prev->v);
+	EDGE_ORD(f_index[0], f_index[1]);
+}
+
+static void erot_state_current(const BMEdge *e, EdRotState *e_state)
+{
+	erot_state_ex(e, &e_state->v1, &e_state->f1);
+}
+
+static void erot_state_alternate(const BMEdge *e, EdRotState *e_state)
+{
+	erot_state_ex(e, &e_state->f1, &e_state->v1);
+}
+
+/* -------------------------------------------------------------------- */
+/* Util for setting edge tag once rotated */
+
+/* we have rotated an edge, tag other egdes and clear this one */
+static void bm_edge_tag_rotated(BMEdge *e)
+{
+	BMLoop *l;
+	BLI_assert(e->l->f->len == 3 &&
+	           e->l->radial_next->f->len == 3);
+
+	l = e->l;
+	BM_elem_flag_enable(l->next->e, BM_ELEM_TAG);
+	BM_elem_flag_enable(l->prev->e, BM_ELEM_TAG);
+	l = l->radial_next;
+	BM_elem_flag_enable(l->next->e, BM_ELEM_TAG);
+	BM_elem_flag_enable(l->prev->e, BM_ELEM_TAG);
+}
+
+/* -------------------------------------------------------------------- */
+/* Beautify Fill */
+
 #define ELE_NEW		1
 #define FACE_MARK	2
 
+/**
+ * \note All edges in \a edge_array must be tagged and
+ * have their index values set according to their position in the array.
+ */
 static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len)
 {
+	GHash      **edge_state_arr  = MEM_callocN(edge_array_len * sizeof(GHash *), __func__);
+	BLI_mempool *edge_state_pool = BLI_mempool_create(sizeof(EdRotState), 512, 512, BLI_MEMPOOL_SYSMALLOC);
 	bool is_breaked;
+	int i;
 
 #ifdef DEBUG_TIME
 	TIMEIT_START(beautify_fill);
 #endif
 
 	do {
-		int i;
-
 		is_breaked = true;
 
 		for (i = 0; i < edge_array_len; i++) {
 			BMVert *v1, *v2, *v3, *v4;
 			BMEdge *e = edge_array[i];
+			GHash *e_state_hash;
 
 			BLI_assert(BM_edge_is_manifold(e) == true);
 			BLI_assert(BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
 			           BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK));
 
+			if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
+				continue;
+			}
+			else {
+				/* don't check this edge again, unless adjaced edges are rotated */
+				BM_elem_flag_disable(e, BM_ELEM_TAG);
+			}
+
+			/* check we're not moving back into a state we have been in before */
+			e_state_hash = edge_state_arr[i];
+			if (e_state_hash != NULL) {
+				EdRotState e_state_alt;
+				erot_state_alternate(e, &e_state_alt);
+				if (BLI_ghash_haskey(e_state_hash, (void *)&e_state_alt)) {
+					// printf("  skipping, we already have this state\n");
+					continue;
+				}
+			}
+
 			v1 = e->l->prev->v;               /* first face vert not attached to 'e' */
 			v2 = e->l->v;                     /* e->v1 or e->v2*/
 			v3 = e->l->radial_next->prev->v;  /* second face vert not attached to 'e' */
@@ -100,24 +217,49 @@ static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge
 				fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
 
 				if (fac1 > fac2) {
-					const int e_index = BM_elem_index_get(e);
+
+					EdRotState *e_state = BLI_mempool_alloc(edge_state_pool);
+					erot_state_current(e, e_state);
+
 					e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
 					if (LIKELY(e)) {
 						/* maintain the index array */
-						edge_array[e_index] = e;
-						BM_elem_index_set(e, e_index);
+						edge_array[i] = e;
+						BM_elem_index_set(e, i);
 
-						BMO_elem_flag_enable(bm, e, ELE_NEW);
 
+						/* add this state into the hash */
+						if (UNLIKELY(e_state_hash == NULL)) {
+							edge_state_arr[i] = e_state_hash = erot_ghash_new();  /* store previous state */
+						}
+						BLI_ghash_insert(e_state_hash, e_state, NULL);
+
+						/* tag other edges so we know to check them again */
+						bm_edge_tag_rotated(e);
+
+						/* update flags */
+						BMO_elem_flag_enable(bm, e, ELE_NEW);
 						BMO_elem_flag_enable(bm, e->l->f, FACE_MARK | ELE_NEW);
 						BMO_elem_flag_enable(bm, e->l->radial_next->f, FACE_MARK | ELE_NEW);
 						is_breaked = false;
 					}
+					else {
+						BLI_mempool_free(edge_state_pool, e_state);
+					}
 				}
 			}
 		}
 	} while (is_breaked == false);
 
+	for (i = 0; i < edge_array_len; i++) {
+		if (edge_state_arr[i]) {
+			BLI_ghash_free(edge_state_arr[i], NULL, NULL);
+		}
+	}
+
+	MEM_freeN(edge_state_arr);
+	BLI_mempool_destroy(edge_state_pool);
+
 #ifdef DEBUG_TIME
 	TIMEIT_END(beautify_fill);
 #endif
@@ -151,6 +293,7 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
 			BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK))
 		{
 			BM_elem_index_set(e, edge_array_len);  /* set_dirty */
+			BM_elem_flag_enable(e, BM_ELEM_TAG);
 			edge_array[edge_array_len] = e;
 			edge_array_len++;
 		}