diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-06-17 20:55:05 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-06-17 20:55:05 +0400 |
commit | 60acf217f8238cb56fdbd1191c7e9684161a0178 (patch) | |
tree | 7bf56c08735b81def340679aad2d653463ae8762 /source/blender | |
parent | d761b91b65487715a23f2b8ddf0efc4dec5b0278 (diff) |
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).
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_utildefines.h | 16 | ||||
-rw-r--r-- | source/blender/editors/transform/transform_conversions.c | 146 |
2 files changed, 83 insertions, 79 deletions
diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 224d02163cb..4d80080ed86 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -263,9 +263,21 @@ #define STACK_PUSH(stack, val) (void)((stack)[(_##stack##_index)++] = val) #define STACK_PUSH_RET(stack) ((void)stack, ((stack)[(_##stack##_index)++])) #define STACK_PUSH_RET_PTR(stack) ((void)stack, &((stack)[(_##stack##_index)++])) -#define STACK_POP(stack) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL) -#define STACK_POP_ELSE(stack, r) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : r) +#define STACK_POP(stack) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL) +#define STACK_POP_PTR(stack) ((_##stack##_index) ? &((stack)[--(_##stack##_index)]) : NULL) +#define STACK_POP_ELSE(stack, r) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : r) #define STACK_FREE(stack) ((void)stack) +#ifdef __GNUC__ +#define STACK_SWAP(stack_a, stack_b) { \ + SWAP(typeof(stack_a), stack_a, stack_b); \ + SWAP(unsigned int, _##stack_a##_index, _##stack_b##_index); \ + } (void)0 +#else +#define STACK_SWAP(stack_a, stack_b) { \ + SWAP(void *, stack_a, stack_b); \ + SWAP(unsigned int, _##stack_a##_index, _##stack_b##_index); \ + } (void)0 +#endif /* array helpers */ #define ARRAY_LAST_ITEM(arr_start, arr_dtype, elem_size, tot) \ 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] */ |