Use BLI_heap_reinsert for decimate and beautify
authorCampbell Barton <ideasman42@gmail.com>
Sat, 28 Oct 2017 18:23:27 +0000 (05:23 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sat, 28 Oct 2017 18:28:00 +0000 (05:28 +1100)
Improves performance for high poly meshes,
~70% faster for decimate, only ~10% for beautify.

source/blender/blenlib/intern/polyfill2d_beautify.c
source/blender/bmesh/tools/bmesh_decimate_collapse.c

index f2a1c194eb1af592b4d96822b1647615ca43e405..56309a4b1157255ea70d19e4933a64ec7dd9010a 100644 (file)
@@ -219,23 +219,23 @@ static void polyedge_beauty_cost_update_single(
         Heap *eheap, HeapNode **eheap_table)
 {
        const uint i = e->base_index;
-
-       if (eheap_table[i]) {
-               BLI_heap_remove(eheap, eheap_table[i]);
-               eheap_table[i] = NULL;
-       }
-
-       {
-               /* recalculate edge */
-               const float cost = polyedge_rotate_beauty_calc(coords, edges, e);
-               /* We can get cases where both choices generate very small negative costs, which leads to infinite loop.
-                * Anyway, costs above that are not worth recomputing, maybe we could even optimize it to a smaller limit?
-                * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully?
-                * See T43578, T49478. */
-               if (cost < -1e-6f) {
-                       eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+       /* recalculate edge */
+       const float cost = polyedge_rotate_beauty_calc(coords, edges, e);
+       /* We can get cases where both choices generate very small negative costs, which leads to infinite loop.
+        * Anyway, costs above that are not worth recomputing, maybe we could even optimize it to a smaller limit?
+        * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully?
+        * See T43578, T49478. */
+       if (cost < -1e-6f) {
+               if (eheap_table[i]) {
+                       BLI_heap_reinsert(eheap, eheap_table[i], cost);
                }
                else {
+                       eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+               }
+       }
+       else {
+               if (eheap_table[i]) {
+                       BLI_heap_remove(eheap, eheap_table[i]);
                        eheap_table[i] = NULL;
                }
        }
index d734d9b6ae158dab1dd29bf4a17554dabab1007e..a081a1b70e4b478017107bed523e5b1eb3999f94 100644 (file)
@@ -256,10 +256,6 @@ static void bm_decim_build_edge_cost_single(
 {
        float cost;
 
-       if (eheap_table[BM_elem_index_get(e)]) {
-               BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
-       }
-
        if (UNLIKELY(vweights &&
                     ((vweights[BM_elem_index_get(e->v1)] == 0.0f) ||
                      (vweights[BM_elem_index_get(e->v2)] == 0.0f))))
@@ -341,10 +337,18 @@ static void bm_decim_build_edge_cost_single(
                }
        }
 
-       eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
+       if (eheap_table[BM_elem_index_get(e)]) {
+               BLI_heap_reinsert(eheap, eheap_table[BM_elem_index_get(e)], cost);
+       }
+       else {
+               eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
+       }
        return;
 
 clear:
+       if (eheap_table[BM_elem_index_get(e)]) {
+               BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
+       }
        eheap_table[BM_elem_index_get(e)] = NULL;
 }