[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [55675] trunk/blender/source/blender/bmesh /operators/bmo_beautify.c: Beautify - use a heap for the edge rotation queue rather then checking to rotate all edges until none can be rotated .
Campbell Barton
ideasman42 at gmail.com
Sat Mar 30 12:05:58 CET 2013
Revision: 55675
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=55675
Author: campbellbarton
Date: 2013-03-30 11:05:57 +0000 (Sat, 30 Mar 2013)
Log Message:
-----------
Beautify - use a heap for the edge rotation queue rather then checking to rotate all edges until none can be rotated.
this means the best edges to rotate are done first, also speeds up execution ~20% in my tests.
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-30 09:57:35 UTC (rev 55674)
+++ trunk/blender/source/blender/bmesh/operators/bmo_beautify.c 2013-03-30 11:05:57 UTC (rev 55675)
@@ -38,6 +38,7 @@
*/
#include "BLI_math.h"
+#include "BLI_heap.h"
#include "MEM_guardedalloc.h"
@@ -125,28 +126,10 @@
}
/* -------------------------------------------------------------------- */
-/* 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);
-}
-
-/* -------------------------------------------------------------------- */
/* Calculate the improvement of rotating the edge */
/**
- * \return a positive value means the edge can be rotated.
+ * \return a negative value means the edge can be rotated.
*/
static float bm_edge_calc_rotate_beauty(const BMEdge *e)
{
@@ -232,14 +215,73 @@
opp2 = area_tri_v2(v2_xy, v4_xy, v1_xy);
fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
- return fac1 - fac2;
+ /* negative number if we're OK */
+ return fac2 - fac1;
}
} while (false);
- return -1.0f;
+ return FLT_MAX;
}
/* -------------------------------------------------------------------- */
+/* Update the edge cost of rotation in the heap */
+
+/* recalc an edge in the heap (surrounding geometry has changed) */
+static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr)
+{
+ if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+ const int i = BM_elem_index_get(e);
+ GHash *e_state_hash = edge_state_arr[i];
+
+ if (eheap_table[i]) {
+ BLI_heap_remove(eheap, eheap_table[i]);
+ eheap_table[i] = NULL;
+ }
+
+ /* check if we can add it back */
+ 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));
+
+ /* check we're not moving back into a state we have been in before */
+ 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");
+ return;
+ }
+ }
+
+ {
+ /* recalculate edge */
+ const float cost = bm_edge_calc_rotate_beauty(e);
+ if (cost < 0.0f) {
+ eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+ }
+ else {
+ eheap_table[i] = NULL;
+ }
+ }
+ }
+}
+
+/* we have rotated an edge, tag other egdes and clear this one */
+static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr)
+{
+ BMLoop *l;
+ BLI_assert(e->l->f->len == 3 &&
+ e->l->radial_next->f->len == 3);
+
+ l = e->l;
+ bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr);
+ bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr);
+ l = l->radial_next;
+ bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr);
+ bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr);
+}
+
+/* -------------------------------------------------------------------- */
/* Beautify Fill */
#define ELE_NEW 1
@@ -251,80 +293,72 @@
*/
static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len)
{
+ Heap *eheap; /* edge heap */
+ HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */
+
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 {
- is_breaked = true;
+ eheap = BLI_heap_new_ex(edge_array_len);
+ eheap_table = MEM_mallocN(sizeof(HeapNode *) * bm->totedge, __func__);
- for (i = 0; i < edge_array_len; i++) {
- BMEdge *e = edge_array[i];
- GHash *e_state_hash;
+ /* build heap */
+ for (i = 0; i < edge_array_len; i++) {
+ BMEdge *e = edge_array[i];
+ const float cost = bm_edge_calc_rotate_beauty(e);
+ if (cost < 0.0f) {
+ eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+ }
+ else {
+ eheap_table[i] = NULL;
+ }
+ }
- 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));
+ while (BLI_heap_is_empty(eheap) == false) {
+ BMEdge *e = BLI_heap_popmin(eheap);
+ i = BM_elem_index_get(e);
+ eheap_table[i] = NULL;
- 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);
- }
+ e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
+ if (LIKELY(e)) {
+ GHash *e_state_hash = edge_state_arr[i];
- /* 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;
- }
+ /* add the new state into the hash so we don't move into this state again
+ * note: we could add the previous state too but this isn't essential)
+ * for avoiding eternal loops */
+ EdRotState *e_state = BLI_mempool_alloc(edge_state_pool);
+ erot_state_current(e, e_state);
+ if (UNLIKELY(e_state_hash == NULL)) {
+ edge_state_arr[i] = e_state_hash = erot_ghash_new(); /* store previous state */
}
+ BLI_assert(BLI_ghash_haskey(e_state_hash, (void *)e_state) == false);
+ BLI_ghash_insert(e_state_hash, e_state, NULL);
- if (bm_edge_calc_rotate_beauty(e) > 0.0f) {
- e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
- if (LIKELY(e)) {
- /* add the new state into the hash so we don't move into this state again
- * note: we could add the previous state too but this isn't essential)
- * for avoiding eternal loops */
- EdRotState *e_state = BLI_mempool_alloc(edge_state_pool);
- erot_state_current(e, e_state);
- if (UNLIKELY(e_state_hash == NULL)) {
- edge_state_arr[i] = e_state_hash = erot_ghash_new(); /* store previous state */
- }
- BLI_assert(BLI_ghash_haskey(e_state_hash, (void *)e_state) == false);
- BLI_ghash_insert(e_state_hash, e_state, NULL);
+ // printf(" %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2));
+ /* maintain the index array */
+ edge_array[i] = e;
+ BM_elem_index_set(e, i);
- // printf(" %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2));
+ /* recalculate faces connected on the heap */
+ bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr);
- /* maintain the index array */
- edge_array[i] = e;
- BM_elem_index_set(e, i);
+ /* 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);
+ }
+ }
- /* tag other edges so we know to check them again */
- bm_edge_tag_rotated(e);
+ BLI_heap_free(eheap, NULL);
+ MEM_freeN(eheap_table);
- /* 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;
- }
- }
- }
- } 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);
More information about the Bf-blender-cvs
mailing list