From fee6ab18e7e9a38203bf8eb95d114ac837578aa7 Mon Sep 17 00:00:00 2001 From: Alexander Gavrilov Date: Mon, 5 Nov 2018 19:14:40 +0300 Subject: BLI_heap: implement a limited but faster version of heap. If the user only needs insertion and removal from top, there is no need to allocate and manage separate HeapNode objects: the data can be stored directly in the main tree array. This measured a 24% FPS increase on a ~50% heap-heavy workload. Reviewers: brecht Differential Revision: https://developer.blender.org/D3898 --- source/blender/blenkernel/intern/pbvh_bmesh.c | 20 +-- source/blender/blenlib/BLI_heap.h | 15 ++ source/blender/blenlib/intern/BLI_heap.c | 199 ++++++++++++++++++++++ source/blender/blenlib/intern/astar.c | 24 +-- source/blender/bmesh/operators/bmo_connect_pair.c | 22 +-- source/blender/bmesh/tools/bmesh_path.c | 54 +++--- source/blender/editors/curve/editcurve_select.c | 14 +- source/blender/editors/mesh/editmesh_tools.c | 14 +- source/blender/modifiers/intern/MOD_skin.c | 12 +- 9 files changed, 294 insertions(+), 80 deletions(-) (limited to 'source') diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index e32a5d0681e..0180bdc9e4d 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -721,7 +721,7 @@ static void pbvh_bmesh_node_drop_orig(PBVHNode *node) struct EdgeQueue; typedef struct EdgeQueue { - Heap *heap; + FastHeap *heap; const float *center; float center_proj[3]; /* for when we use projected coords. */ float radius_squared; @@ -840,7 +840,7 @@ static void edge_queue_insert( BMVert **pair = BLI_mempool_alloc(eq_ctx->pool); pair[0] = e->v1; pair[1] = e->v2; - BLI_heap_insert(eq_ctx->q->heap, priority, pair); + BLI_fastheap_insert(eq_ctx->q->heap, priority, pair); #ifdef USE_EDGEQUEUE_TAG BLI_assert(EDGE_QUEUE_TEST(e) == false); EDGE_QUEUE_ENABLE(e); @@ -1008,7 +1008,7 @@ static void long_edge_queue_create( PBVH *bvh, const float center[3], const float view_normal[3], float radius, const bool use_frontface, const bool use_projected) { - eq_ctx->q->heap = BLI_heap_new(); + eq_ctx->q->heap = BLI_fastheap_new(); eq_ctx->q->center = center; eq_ctx->q->radius_squared = radius * radius; eq_ctx->q->limit_len_squared = bvh->bm_max_edge_len * bvh->bm_max_edge_len; @@ -1070,7 +1070,7 @@ static void short_edge_queue_create( PBVH *bvh, const float center[3], const float view_normal[3], float radius, const bool use_frontface, const bool use_projected) { - eq_ctx->q->heap = BLI_heap_new(); + eq_ctx->q->heap = BLI_fastheap_new(); eq_ctx->q->center = center; eq_ctx->q->radius_squared = radius * radius; eq_ctx->q->limit_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len; @@ -1237,8 +1237,8 @@ static bool pbvh_bmesh_subdivide_long_edges( { bool any_subdivided = false; - while (!BLI_heap_is_empty(eq_ctx->q->heap)) { - BMVert **pair = BLI_heap_pop_min(eq_ctx->q->heap); + while (!BLI_fastheap_is_empty(eq_ctx->q->heap)) { + BMVert **pair = BLI_fastheap_pop_min(eq_ctx->q->heap); BMVert *v1 = pair[0], *v2 = pair[1]; BMEdge *e; @@ -1454,8 +1454,8 @@ static bool pbvh_bmesh_collapse_short_edges( /* deleted verts point to vertices they were merged into, or NULL when removed. */ GHash *deleted_verts = BLI_ghash_ptr_new("deleted_verts"); - while (!BLI_heap_is_empty(eq_ctx->q->heap)) { - BMVert **pair = BLI_heap_pop_min(eq_ctx->q->heap); + while (!BLI_fastheap_is_empty(eq_ctx->q->heap)) { + BMVert **pair = BLI_fastheap_pop_min(eq_ctx->q->heap); BMVert *v1 = pair[0], *v2 = pair[1]; BLI_mempool_free(eq_ctx->pool, pair); pair = NULL; @@ -1961,7 +1961,7 @@ bool BKE_pbvh_bmesh_update_topology( short_edge_queue_create(&eq_ctx, bvh, center, view_normal, radius, use_frontface, use_projected); modified |= pbvh_bmesh_collapse_short_edges( &eq_ctx, bvh, &deleted_faces); - BLI_heap_free(q.heap, NULL); + BLI_fastheap_free(q.heap, NULL); BLI_mempool_destroy(queue_pool); } @@ -1976,7 +1976,7 @@ bool BKE_pbvh_bmesh_update_topology( long_edge_queue_create(&eq_ctx, bvh, center, view_normal, radius, use_frontface, use_projected); modified |= pbvh_bmesh_subdivide_long_edges( &eq_ctx, bvh, &edge_loops); - BLI_heap_free(q.heap, NULL); + BLI_fastheap_free(q.heap, NULL); BLI_mempool_destroy(queue_pool); } diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index 35c8df3075c..08adb0d538c 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -54,4 +54,19 @@ void *BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT /* only for gtest */ bool BLI_heap_is_valid(const Heap *heap); +/* Simplified version of the heap that only supports insertion and removal from top. */ + +struct FastHeap; +typedef struct FastHeap FastHeap; + +FastHeap *BLI_fastheap_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT; +FastHeap *BLI_fastheap_new(void) ATTR_WARN_UNUSED_RESULT; +void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); +void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1); +void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr) ATTR_NONNULL(1); +bool BLI_fastheap_is_empty(const FastHeap *heap) ATTR_NONNULL(1); +unsigned int BLI_fastheap_len(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +float BLI_fastheap_top_value(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +void *BLI_fastheap_pop_min(FastHeap *heap) ATTR_NONNULL(1); + #endif /* __BLI_HEAP_H__ */ diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index c785c1ac012..cef3eb2dafb 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -73,6 +73,17 @@ struct Heap { } nodes; }; +typedef struct FastHeapNode { + float value; + void *ptr; +} FastHeapNode; + +struct FastHeap { + uint size; + uint bufsize; + FastHeapNode *tree; +}; + /** \name Internal Functions * \{ */ @@ -441,3 +452,191 @@ bool BLI_heap_is_valid(const Heap *heap) } /** \} */ + +/** \name FastHeap Internal Functions + * \{ */ + +static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *init) +{ +#if 1 + /* The compiler isn't smart enough to realize that all computations + * using index here can be modified to work with byte offset. */ + uint8_t *const tree_buf = (uint8_t*)heap->tree; + +#define OFFSET(i) (i * (uint)sizeof(FastHeapNode)) +#define NODE(offset) (*(FastHeapNode*)(tree_buf + (offset))) +#else + FastHeapNode *const tree = heap->tree; + +#define OFFSET(i) (i) +#define NODE(i) tree[i] +#endif + +#define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1)) + + const uint size = OFFSET(heap->size); + + /* Pull the active node values into locals. This allows spilling + * the data from registers instead of literally swapping nodes. */ + float active_val = init->value; + void *active_ptr = init->ptr; + + /* Prepare the first iteration and spill value. */ + uint i = OFFSET(start_i); + + NODE(i).value = active_val; + + for (;;) { + const uint l = HEAP_LEFT_OFFSET(i); + const uint r = l + OFFSET(1); /* right */ + + /* Find the child with the smallest value. */ + uint smallest = i; + + if (LIKELY(l < size) && NODE(l).value < active_val) { + smallest = l; + } + if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) { + smallest = r; + } + + if (UNLIKELY(smallest == i)) { + break; + } + + /* Move the smallest child into the current node. + * Skip padding: for some reason that makes it faster here. */ + NODE(i).value = NODE(smallest).value; + NODE(i).ptr = NODE(smallest).ptr; + + /* Proceed to next iteration and spill value. */ + i = smallest; + NODE(i).value = active_val; + } + + /* Spill the pointer into the final position of the node. */ + NODE(i).ptr = active_ptr; + +#undef NODE +#undef OFFSET +#undef HEAP_LEFT_OFFSET +} + +static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr) +{ + FastHeapNode *const tree = heap->tree; + + while (LIKELY(i > 0)) { + const uint p = HEAP_PARENT(i); + + if (active_val >= tree[p].value) { + break; + } + + tree[i] = tree[p]; + i = p; + } + + tree[i].value = active_val; + tree[i].ptr = active_ptr; +} + +/** \} */ + +/** \name Public FastHeap API + * \{ */ + +/** + * Creates a new fast heap, which only supports insertion and removal from top. + * + * \note Use when the size of the heap is known in advance. + */ +FastHeap *BLI_fastheap_new_ex(uint tot_reserve) +{ + FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __func__); + /* ensure we have at least one so we can keep doubling it */ + heap->size = 0; + heap->bufsize = MAX2(1u, tot_reserve); + heap->tree = MEM_mallocN(heap->bufsize * sizeof(FastHeapNode), "BLIFastHeapTree"); + return heap; +} + +FastHeap *BLI_fastheap_new(void) +{ + return BLI_fastheap_new_ex(1); +} + +void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp) +{ + if (ptrfreefp) { + for (uint i = 0; i < heap->size; i++) { + ptrfreefp(heap->tree[i].ptr); + } + } + + MEM_freeN(heap->tree); + MEM_freeN(heap); +} + +void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp) +{ + if (ptrfreefp) { + for (uint i = 0; i < heap->size; i++) { + ptrfreefp(heap->tree[i].ptr); + } + } + + heap->size = 0; +} + +/** + * Insert heap node with a value (often a 'cost') and pointer into the heap, + * duplicate values are allowed. + */ +void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr) +{ + if (UNLIKELY(heap->size >= heap->bufsize)) { + heap->bufsize *= 2; + heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree)); + } + + fastheap_up(heap, heap->size++, value, ptr); +} + +bool BLI_fastheap_is_empty(const FastHeap *heap) +{ + return (heap->size == 0); +} + +uint BLI_fastheap_len(const FastHeap *heap) +{ + return heap->size; +} + +/** + * Return the lowest value of the heap. + */ +float BLI_fastheap_top_value(const FastHeap *heap) +{ + BLI_assert(heap->size != 0); + + return heap->tree[0].value; +} + +/** + * Pop the top node off the heap and return it's pointer. + */ +void *BLI_fastheap_pop_min(FastHeap *heap) +{ + BLI_assert(heap->size != 0); + + void *ptr = heap->tree[0].ptr; + + if (--heap->size) { + fastheap_down(heap, 0, &heap->tree[heap->size]); + } + + return ptr; +} + +/** \} */ diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c index 86c1faad096..54c80def972 100644 --- a/source/blender/blenlib/intern/astar.c +++ b/source/blender/blenlib/intern/astar.c @@ -206,7 +206,7 @@ bool BLI_astar_graph_solve( BLI_AStarGraph *as_graph, const int node_index_src, const int node_index_dst, astar_f_cost f_cost_cb, BLI_AStarSolution *r_solution, const int max_steps) { - Heap *todo_nodes; + FastHeap *todo_nodes; BLI_bitmap *done_nodes = r_solution->done_nodes; int *prev_nodes = r_solution->prev_nodes; @@ -225,13 +225,13 @@ bool BLI_astar_graph_solve( return true; } - todo_nodes = BLI_heap_new(); - BLI_heap_insert(todo_nodes, - f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst), - POINTER_FROM_INT(node_index_src)); + todo_nodes = BLI_fastheap_new(); + BLI_fastheap_insert(todo_nodes, + f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst), + POINTER_FROM_INT(node_index_src)); - while (!BLI_heap_is_empty(todo_nodes)) { - const int node_curr_idx = POINTER_AS_INT(BLI_heap_pop_min(todo_nodes)); + while (!BLI_fastheap_is_empty(todo_nodes)) { + const int node_curr_idx = POINTER_AS_INT(BLI_fastheap_pop_min(todo_nodes)); BLI_AStarGNode *node_curr = &as_graph->nodes[node_curr_idx]; LinkData *ld; @@ -249,7 +249,7 @@ bool BLI_astar_graph_solve( /* Success! Path found... */ r_solution->steps = g_steps[node_curr_idx] + 1; - BLI_heap_free(todo_nodes, NULL); + BLI_fastheap_free(todo_nodes, NULL); return true; } @@ -269,14 +269,14 @@ bool BLI_astar_graph_solve( g_steps[node_next_idx] = g_steps[node_curr_idx] + 1; /* We might have this node already in heap, but since this 'instance' will be evaluated first, * no problem. */ - BLI_heap_insert(todo_nodes, - f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst), - POINTER_FROM_INT(node_next_idx)); + BLI_fastheap_insert(todo_nodes, + f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst), + POINTER_FROM_INT(node_next_idx)); } } } } - BLI_heap_free(todo_nodes, NULL); + BLI_fastheap_free(todo_nodes, NULL); return false; } diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c index b9e5cd927c3..3b3766b6f3a 100644 --- a/source/blender/bmesh/operators/bmo_connect_pair.c +++ b/source/blender/bmesh/operators/bmo_connect_pair.c @@ -94,7 +94,7 @@ // #define DEBUG_PRINT typedef struct PathContext { - Heap *states; + FastHeap *states; float matrix[3][3]; float axis_sep; @@ -331,7 +331,7 @@ static PathLinkState *state_link_add_test( /* after adding a link so we use the updated 'state->dist' */ if (is_new) { - BLI_heap_insert(pc->states, state->dist, state); + BLI_fastheap_insert(pc->states, state->dist, state); } return state; @@ -640,7 +640,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) /* setup context */ { - pc.states = BLI_heap_new(); + pc.states = BLI_fastheap_new(); pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP); } @@ -655,18 +655,18 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) PathLinkState *state; state = MEM_callocN(sizeof(*state), __func__); state_link_add(&pc, state, (BMElem *)pc.v_a, NULL); - BLI_heap_insert(pc.states, state->dist, state); + BLI_fastheap_insert(pc.states, state->dist, state); } - while (!BLI_heap_is_empty(pc.states)) { + while (!BLI_fastheap_is_empty(pc.states)) { #ifdef DEBUG_PRINT - printf("\n%s: stepping %u\n", __func__, BLI_heap_len(pc.states)); + printf("\n%s: stepping %u\n", __func__, BLI_fastheap_len(pc.states)); #endif - while (!BLI_heap_is_empty(pc.states)) { - PathLinkState *state = BLI_heap_pop_min(pc.states); + while (!BLI_fastheap_is_empty(pc.states)) { + PathLinkState *state = BLI_fastheap_pop_min(pc.states); /* either we insert this into 'pc.states' or its freed */ bool continue_search; @@ -679,7 +679,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) state_best = *state; /* we're done, exit all loops */ - BLI_heap_clear(pc.states, MEM_freeN); + BLI_fastheap_clear(pc.states, MEM_freeN); continue_search = false; } else if (state_step(&pc, state)) { @@ -696,7 +696,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) } if (continue_search) { - BLI_heap_insert(pc.states, state->dist, state); + BLI_fastheap_insert(pc.states, state->dist, state); } else { MEM_freeN(state); @@ -732,7 +732,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) BLI_mempool_destroy(pc.link_pool); - BLI_heap_free(pc.states, MEM_freeN); + BLI_fastheap_free(pc.states, MEM_freeN); #if 1 if (state_best.link_last) { diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c index cc5ac6dd8ce..57abd2c4726 100644 --- a/source/blender/bmesh/tools/bmesh_path.c +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -72,7 +72,7 @@ static float step_cost_3_v3( /* BM_mesh_calc_path_vert */ static void verttag_add_adjacent( - Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost, + FastHeap *heap, BMVert *v_a, BMVert **verts_prev, float *cost, const struct BMCalcPathParams *params) { const int v_a_index = BM_elem_index_get(v_a); @@ -93,7 +93,7 @@ static void verttag_add_adjacent( if (cost[v_b_index] > cost_new) { cost[v_b_index] = cost_new; verts_prev[v_b_index] = v_a; - BLI_heap_insert(heap, cost_new, v_b); + BLI_fastheap_insert(heap, cost_new, v_b); } } } @@ -119,7 +119,7 @@ static void verttag_add_adjacent( if (cost[v_b_index] > cost_new) { cost[v_b_index] = cost_new; verts_prev[v_b_index] = v_a; - BLI_heap_insert(heap, cost_new, v_b); + BLI_fastheap_insert(heap, cost_new, v_b); } } } while ((l_iter = l_iter->next) != l->prev); @@ -136,7 +136,7 @@ LinkNode *BM_mesh_calc_path_vert( /* BM_ELEM_TAG flag is used to store visited edges */ BMVert *v; BMIter viter; - Heap *heap; + FastHeap *heap; float *cost; BMVert **verts_prev; int i, totvert; @@ -169,12 +169,12 @@ LinkNode *BM_mesh_calc_path_vert( */ /* regular dijkstra shortest path, but over faces instead of vertices */ - heap = BLI_heap_new(); - BLI_heap_insert(heap, 0.0f, v_src); + heap = BLI_fastheap_new(); + BLI_fastheap_insert(heap, 0.0f, v_src); cost[BM_elem_index_get(v_src)] = 0.0f; - while (!BLI_heap_is_empty(heap)) { - v = BLI_heap_pop_min(heap); + while (!BLI_fastheap_is_empty(heap)) { + v = BLI_fastheap_pop_min(heap); if (v == v_dst) break; @@ -193,7 +193,7 @@ LinkNode *BM_mesh_calc_path_vert( MEM_freeN(verts_prev); MEM_freeN(cost); - BLI_heap_free(heap, NULL); + BLI_fastheap_free(heap, NULL); return path; } @@ -221,7 +221,7 @@ static float edgetag_cut_cost_face(BMEdge *e_a, BMEdge *e_b, BMFace *f) } static void edgetag_add_adjacent( - Heap *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost, + FastHeap *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost, const struct BMCalcPathParams *params) { const int e_a_index = BM_elem_index_get(e_a); @@ -255,7 +255,7 @@ static void edgetag_add_adjacent( if (cost[e_b_index] > cost_new) { cost[e_b_index] = cost_new; edges_prev[e_b_index] = e_a; - BLI_heap_insert(heap, cost_new, e_b); + BLI_fastheap_insert(heap, cost_new, e_b); } } } @@ -291,7 +291,7 @@ static void edgetag_add_adjacent( if (cost[e_b_index] > cost_new) { cost[e_b_index] = cost_new; edges_prev[e_b_index] = e_a; - BLI_heap_insert(heap, cost_new, e_b); + BLI_fastheap_insert(heap, cost_new, e_b); } } } while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end); @@ -308,7 +308,7 @@ LinkNode *BM_mesh_calc_path_edge( /* BM_ELEM_TAG flag is used to store visited edges */ BMEdge *e; BMIter eiter; - Heap *heap; + FastHeap *heap; float *cost; BMEdge **edges_prev; int i, totedge; @@ -341,12 +341,12 @@ LinkNode *BM_mesh_calc_path_edge( */ /* regular dijkstra shortest path, but over edges instead of vertices */ - heap = BLI_heap_new(); - BLI_heap_insert(heap, 0.0f, e_src); + heap = BLI_fastheap_new(); + BLI_fastheap_insert(heap, 0.0f, e_src); cost[BM_elem_index_get(e_src)] = 0.0f; - while (!BLI_heap_is_empty(heap)) { - e = BLI_heap_pop_min(heap); + while (!BLI_fastheap_is_empty(heap)) { + e = BLI_fastheap_pop_min(heap); if (e == e_dst) break; @@ -365,7 +365,7 @@ LinkNode *BM_mesh_calc_path_edge( MEM_freeN(edges_prev); MEM_freeN(cost); - BLI_heap_free(heap, NULL); + BLI_fastheap_free(heap, NULL); return path; } @@ -421,7 +421,7 @@ static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v, const vo } static void facetag_add_adjacent( - Heap *heap, BMFace *f_a, BMFace **faces_prev, float *cost, + FastHeap *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const void * const f_endpoints[2], const struct BMCalcPathParams *params) { const int f_a_index = BM_elem_index_get(f_a); @@ -447,7 +447,7 @@ static void facetag_add_adjacent( if (cost[f_b_index] > cost_new) { cost[f_b_index] = cost_new; faces_prev[f_b_index] = f_a; - BLI_heap_insert(heap, cost_new, f_b); + BLI_fastheap_insert(heap, cost_new, f_b); } } } while ((l_iter = l_iter->radial_next) != l_first); @@ -474,7 +474,7 @@ static void facetag_add_adjacent( if (cost[f_b_index] > cost_new) { cost[f_b_index] = cost_new; faces_prev[f_b_index] = f_a; - BLI_heap_insert(heap, cost_new, f_b); + BLI_fastheap_insert(heap, cost_new, f_b); } } } @@ -491,7 +491,7 @@ LinkNode *BM_mesh_calc_path_face( /* BM_ELEM_TAG flag is used to store visited edges */ BMFace *f; BMIter fiter; - Heap *heap; + FastHeap *heap; float *cost; BMFace **faces_prev; int i, totface; @@ -527,12 +527,12 @@ LinkNode *BM_mesh_calc_path_face( */ /* regular dijkstra shortest path, but over faces instead of vertices */ - heap = BLI_heap_new(); - BLI_heap_insert(heap, 0.0f, f_src); + heap = BLI_fastheap_new(); + BLI_fastheap_insert(heap, 0.0f, f_src); cost[BM_elem_index_get(f_src)] = 0.0f; - while (!BLI_heap_is_empty(heap)) { - f = BLI_heap_pop_min(heap); + while (!BLI_fastheap_is_empty(heap)) { + f = BLI_fastheap_pop_min(heap); if (f == f_dst) break; @@ -551,7 +551,7 @@ LinkNode *BM_mesh_calc_path_face( MEM_freeN(faces_prev); MEM_freeN(cost); - BLI_heap_free(heap, NULL); + BLI_fastheap_free(heap, NULL); return path; } diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c index 43ab3f2ccbc..573161d1024 100644 --- a/source/blender/editors/curve/editcurve_select.c +++ b/source/blender/editors/curve/editcurve_select.c @@ -1704,7 +1704,7 @@ static void curve_select_shortest_path_curve(Nurb *nu, int vert_src, int vert_ds static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst) { - Heap *heap; + FastHeap *heap; int i, vert_curr; @@ -1727,18 +1727,18 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst } /* init heap */ - heap = BLI_heap_new(); + heap = BLI_fastheap_new(); vert_curr = data[vert_src].vert; - BLI_heap_insert(heap, 0.0f, &data[vert_src].vert); + BLI_fastheap_insert(heap, 0.0f, &data[vert_src].vert); data[vert_src].cost = 0.0f; data[vert_src].vert_prev = vert_src; /* nop */ - while (!BLI_heap_is_empty(heap)) { + while (!BLI_fastheap_is_empty(heap)) { int axis, sign; int u, v; - vert_curr = *((int *)BLI_heap_pop_min(heap)); + vert_curr = *((int *)BLI_fastheap_pop_min(heap)); if (vert_curr == vert_dst) { break; } @@ -1760,7 +1760,7 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst if (data[vert_other].cost > dist) { data[vert_other].cost = dist; if (data[vert_other].vert_prev == -1) { - BLI_heap_insert(heap, data[vert_other].cost, &data[vert_other].vert); + BLI_fastheap_insert(heap, data[vert_other].cost, &data[vert_other].vert); } data[vert_other].vert_prev = vert_curr; } @@ -1771,7 +1771,7 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst } - BLI_heap_free(heap, NULL); + BLI_fastheap_free(heap, NULL); if (vert_curr == vert_dst) { i = 0; diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c index b16195023c9..71dbdfdbfb2 100644 --- a/source/blender/editors/mesh/editmesh_tools.c +++ b/source/blender/editors/mesh/editmesh_tools.c @@ -7818,7 +7818,7 @@ static int edbm_average_normals_exec(bContext *C, wmOperator *op) BM_normals_loops_edges_tag(bm, true); - Heap *loop_weight = BLI_heap_new(); + FastHeap *loop_weight = BLI_fastheap_new(); BM_ITER_MESH(f, &fiter, bm, BM_FACES_OF_MESH) { l_curr = l_first = BM_FACE_FIRST_LOOP(f); @@ -7858,7 +7858,7 @@ static int edbm_average_normals_exec(bContext *C, wmOperator *op) val = 1.0f / BM_loop_calc_face_angle(lfan_pivot); } - BLI_heap_insert(loop_weight, val, lfan_pivot); + BLI_fastheap_insert(loop_weight, val, lfan_pivot); if (!BM_elem_flag_test(e_next, BM_ELEM_TAG) || (e_next == e_org)) { break; @@ -7868,15 +7868,15 @@ static int edbm_average_normals_exec(bContext *C, wmOperator *op) BLI_SMALLSTACK_DECLARE(loops, BMLoop *); float wnor[3], avg_normal[3] = { 0.0f }, count = 0; - float val = BLI_heap_top_value(loop_weight); + float val = BLI_fastheap_top_value(loop_weight); - while (!BLI_heap_is_empty(loop_weight)) { - const float cur_val = BLI_heap_top_value(loop_weight); + while (!BLI_fastheap_is_empty(loop_weight)) { + const float cur_val = BLI_fastheap_top_value(loop_weight); if (!compare_ff(val, cur_val, threshold)) { count++; val = cur_val; } - l = BLI_heap_pop_min(loop_weight); + l = BLI_fastheap_pop_min(loop_weight); BLI_SMALLSTACK_PUSH(loops, l); const float n_weight = pow(weight, count); @@ -7907,7 +7907,7 @@ static int edbm_average_normals_exec(bContext *C, wmOperator *op) } while ((l_curr = l_curr->next) != l_first); } - BLI_heap_free(loop_weight, NULL); + BLI_fastheap_free(loop_weight, NULL); EDBM_update_generic(em, true, false); return OPERATOR_FINISHED; diff --git a/source/blender/modifiers/intern/MOD_skin.c b/source/blender/modifiers/intern/MOD_skin.c index d22bdb5fd0a..f93512bc81a 100644 --- a/source/blender/modifiers/intern/MOD_skin.c +++ b/source/blender/modifiers/intern/MOD_skin.c @@ -1431,10 +1431,10 @@ static void hull_merge_triangles(SkinOutput *so, const SkinModifierData *smd) { BMIter iter; BMEdge *e; - Heap *heap; + FastHeap *heap; float score; - heap = BLI_heap_new(); + heap = BLI_fastheap_new(); BM_mesh_elem_hflag_disable_all(so->bm, BM_FACE, BM_ELEM_TAG, false); @@ -1477,15 +1477,15 @@ static void hull_merge_triangles(SkinOutput *so, const SkinModifierData *smd) continue; } - BLI_heap_insert(heap, -score, e); + BLI_fastheap_insert(heap, -score, e); } } } - while (!BLI_heap_is_empty(heap)) { + while (!BLI_fastheap_is_empty(heap)) { BMFace *adj[2]; - e = BLI_heap_pop_min(heap); + e = BLI_fastheap_pop_min(heap); if (BM_edge_face_pair(e, &adj[0], &adj[1])) { /* If both triangles still free, and if they don't already @@ -1502,7 +1502,7 @@ static void hull_merge_triangles(SkinOutput *so, const SkinModifierData *smd) } } - BLI_heap_free(heap, NULL); + BLI_fastheap_free(heap, NULL); BM_mesh_delete_hflag_tagged(so->bm, BM_ELEM_TAG, BM_EDGE | BM_FACE); -- cgit v1.2.3