[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [55579] trunk/blender/source/blender/bmesh /operators/bmo_beautify.c: fix [#34603] ALT-F fails, freezes, CPU=100%
Campbell Barton
ideasman42 at gmail.com
Tue Mar 26 01:29:58 CET 2013
Revision: 55579
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=55579
Author: campbellbarton
Date: 2013-03-26 00:29:57 +0000 (Tue, 26 Mar 2013)
Log Message:
-----------
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.
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/operators/bmo_beautify.c
Modified: trunk/blender/source/blender/bmesh/operators/bmo_beautify.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_beautify.c 2013-03-25 23:21:16 UTC (rev 55578)
+++ trunk/blender/source/blender/bmesh/operators/bmo_beautify.c 2013-03-26 00:29:57 UTC (rev 55579)
@@ -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 @@
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);
+
+ /* 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 @@
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++;
}
More information about the Bf-blender-cvs
mailing list