[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [57527] trunk/blender/source/blender: fix for editmesh transform connected,
Campbell Barton
ideasman42 at gmail.com
Mon Jun 17 18:55:05 CEST 2013
Revision: 57527
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=57527
Author: campbellbarton
Date: 2013-06-17 16:55:05 +0000 (Mon, 17 Jun 2013)
Log Message:
-----------
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).
Modified Paths:
--------------
trunk/blender/source/blender/blenlib/BLI_utildefines.h
trunk/blender/source/blender/editors/transform/transform_conversions.c
Modified: trunk/blender/source/blender/blenlib/BLI_utildefines.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_utildefines.h 2013-06-17 16:49:11 UTC (rev 57526)
+++ trunk/blender/source/blender/blenlib/BLI_utildefines.h 2013-06-17 16:55:05 UTC (rev 57527)
@@ -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) \
Modified: trunk/blender/source/blender/editors/transform/transform_conversions.c
===================================================================
--- trunk/blender/source/blender/editors/transform/transform_conversions.c 2013-06-17 16:49:11 UTC (rev 57526)
+++ trunk/blender/source/blender/editors/transform/transform_conversions.c 2013-06-17 16:55:05 UTC (rev 57527)
@@ -1775,90 +1775,82 @@
/* ********************* 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 @@
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] */
More information about the Bf-blender-cvs
mailing list