fix for editmesh transform connected,

the distance checks could get into a feedback loop so that the result depended on the order of verts/edges.

now you can randomize vert/edge/faces and get exactly the same results.

also made some internal improvements,
- used fixed sized arrays (no need to realloc).
- use vertex tag flags rather then a visit-hash.
- remove 'tots' array that did nothing (not sure why it was added).

1 files changed, 69 insertions, 77 deletions

diff --git a/source/blender/editors/transform/transform_conversions.c b/source/blender/editors/transform/transform_conversions.c
index c3848c06b06..08047289ffb 100644
--- a/source/blender/editors/transform/transform_conversions.c
+++ b/source/blender/editors/transform/transform_conversions.c
@@ -1775,90 +1775,82 @@ void flushTransParticles(TransInfo *t)
 
 /* ********************* mesh ****************** */
 
-/* I did this wrong, it should be a breadth-first search
- * but instead it's a depth-first search, fudged
- * to report shortest distances.  I have no idea how fast
- * or slow this is. */
-static void editmesh_set_connectivity_distance(BMEditMesh *em, float mtx[3][3], float *dists)
+static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float *dists)
 {
-	BMVert **queue = NULL;
-	float *dqueue = NULL;
-	int *tots = MEM_callocN(sizeof(int) * em->bm->totvert, "tots editmesh_set_connectivity_distance");
-	BLI_array_declare(queue);
-	BLI_array_declare(dqueue);
-	SmallHash svisit, *visit = &svisit;
-	BMVert *v;
-	BMIter viter;
-	int i, start;
-	
-	fill_vn_fl(dists, em->bm->totvert, FLT_MAX);
+	/* need to be very careful of feedback loops here, store previous dist's to avoid feedback */
+	float *dists_prev = MEM_mallocN(bm->totvert * sizeof(float), __func__);
 
-	BM_mesh_elem_index_ensure(em->bm, BM_VERT);
+	BMVert **queue = MEM_mallocN(bm->totvert * sizeof(BMVert *), __func__);
+	STACK_DECLARE(queue);
 
-	BLI_smallhash_init(visit);
+	BMVert **queue_next = MEM_mallocN(bm->totvert * sizeof(BMVert *), __func__);
+	STACK_DECLARE(queue_next);
 
-	BM_ITER_MESH (v, &viter, em->bm, BM_VERTS_OF_MESH) {
-		if (BM_elem_flag_test(v, BM_ELEM_SELECT) == 0 || BM_elem_flag_test(v, BM_ELEM_HIDDEN))
-			continue;
-			
-		
-		BLI_smallhash_insert(visit, (uintptr_t)v, NULL);
-		BLI_array_append(queue, v);
-		BLI_array_append(dqueue, 0.0f);
-		dists[BM_elem_index_get(v)] = 0.0f;
-	}
-	
-	start = 0;
-	while (start < BLI_array_count(queue)) {
-		BMIter eiter;
-		BMEdge *e;
-		BMVert *v3, *v2;
-		float d, vec[3];
-		
-		v2 = queue[start];
-		d = dqueue[start];
-		
-		BM_ITER_ELEM (e, &eiter, v2, BM_EDGES_OF_VERT) {
-			float d2;
-			v3 = BM_edge_other_vert(e, v2);
-			
-			if (BM_elem_flag_test(v3, BM_ELEM_SELECT) || BM_elem_flag_test(v3, BM_ELEM_HIDDEN))
-				continue;
-			
-			sub_v3_v3v3(vec, v2->co, v3->co);
-			mul_m3_v3(mtx, vec);
-			
-			d2 = d + len_v3(vec);
-			
-			if (dists[BM_elem_index_get(v3)] != FLT_MAX)
-				dists[BM_elem_index_get(v3)] = min_ff(d2, dists[BM_elem_index_get(v3)]);
-			else
-				dists[BM_elem_index_get(v3)] = d2;
-			
-			tots[BM_elem_index_get(v3)] = 1;
+	STACK_INIT(queue);
+	STACK_INIT(queue_next);
 
-			if (BLI_smallhash_haskey(visit, (uintptr_t)v3))
-				continue;
-			
-			BLI_smallhash_insert(visit, (uintptr_t)v3, NULL);
-			
-			BLI_array_append(queue, v3);
-			BLI_array_append(dqueue, d2);
+	{
+		BMIter viter;
+		BMVert *v;
+		int i;
+
+		BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
+			BM_elem_index_set(v, i); /* set_inline */
+
+			if (BM_elem_flag_test(v, BM_ELEM_SELECT) == 0 || BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
+				BM_elem_flag_disable(v, BM_ELEM_TAG);
+
+				dists[i] = FLT_MAX;
+			}
+			else {
+				BM_elem_flag_enable(v, BM_ELEM_TAG);
+				STACK_PUSH(queue, v);
+
+				dists[i] = 0.0f;
+			}
 		}
-		
-		start++;
 	}
 
-	BLI_smallhash_release(visit);
-	
-	for (i = 0; i < em->bm->totvert; i++) {
-		if (tots[i])
-			dists[i] /= (float)tots[i];
-	}
-	
-	BLI_array_free(queue);
-	BLI_array_free(dqueue);
-	MEM_freeN(tots);
+	do {
+		BMVert *v;
+		memcpy(dists_prev, dists, sizeof(float) * bm->totvert);
+
+		while ((v = STACK_POP(queue))) {
+			BMIter eiter;
+			BMEdge *e;
+			int i = BM_elem_index_get(v);
+
+			BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
+				float vec[3];
+				BMVert *v_other = BM_edge_other_vert(e, v);
+				const int i_other = BM_elem_index_get(v_other);
+
+				if (BM_elem_flag_test(v_other, BM_ELEM_SELECT) || BM_elem_flag_test(v_other, BM_ELEM_HIDDEN)) {
+					continue;
+				}
+
+				sub_v3_v3v3(vec, v->co, v_other->co);
+				mul_m3_v3(mtx, vec);
+
+				dists[i_other] = min_ff(dists_prev[i] + len_v3(vec), dists[i_other]);
+
+				if (!BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
+					BM_elem_flag_enable(v_other, BM_ELEM_TAG);
+					STACK_PUSH(queue_next, v_other);
+				}
+			}
+		}
+
+		STACK_SWAP(queue, queue_next);
+
+	} while (STACK_SIZE(queue));
+
+	STACK_FREE(queue);
+	STACK_FREE(queue_next);
+
+	MEM_freeN(queue);
+	MEM_freeN(queue_next);
+	MEM_freeN(dists_prev);
 }
 
 static BMElem *bm_vert_single_select_face(BMVert *eve)
@@ -2096,7 +2088,7 @@ static void createTransEditVerts(TransInfo *t)
 	pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
 
 	if (propmode & T_PROP_CONNECTED) {
-		editmesh_set_connectivity_distance(em, mtx, dists);
+		editmesh_set_connectivity_distance(em->bm, mtx, dists);
 	}
 
 	/* detect CrazySpace [tm] */