From 60acf217f8238cb56fdbd1191c7e9684161a0178 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 17 Jun 2013 16:55:05 +0000 Subject: 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). --- .../editors/transform/transform_conversions.c | 146 ++++++++++----------- 1 file changed, 69 insertions(+), 77 deletions(-) (limited to 'source/blender/editors/transform/transform_conversions.c') 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] */ -- cgit v1.2.3