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
This commit is contained in:
parent
a120b120ce
commit
fee6ab18e7
Notes:
blender-bot
2023-02-13 11:59:03 +01:00
Referenced by commit 55324b8a2e, Revert rBfee6ab18e7e9 in BLI_heap_test.cc
|
|
@ -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);
|
||||
}
|
||||
|
||||
|
|
|
|||
|
|
@ -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__ */
|
||||
|
|
|
|||
|
|
@ -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;
|
||||
}
|
||||
|
||||
/** \} */
|
||||
|
|
|
|||
|
|
@ -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;
|
||||
}
|
||||
|
|
|
|||
|
|
@ -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) {
|
||||
|
|
|
|||
|
|
@ -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;
|
||||
}
|
||||
|
|
|
|||
|
|
@ -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;
|
||||
|
|
|
|||
|
|
@ -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;
|
||||
|
|
|
|||
|
|
@ -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);
|
||||
|
||||
|
|
|
|||
|
|
@ -34,6 +34,16 @@ TEST(heap, Empty)
|
|||
BLI_heap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, FastEmpty)
|
||||
{
|
||||
FastHeap *heap;
|
||||
|
||||
heap = BLI_fastheap_new();
|
||||
EXPECT_TRUE(BLI_fastheap_is_empty(heap));
|
||||
EXPECT_EQ(BLI_fastheap_len(heap), 0);
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, One)
|
||||
{
|
||||
Heap *heap;
|
||||
|
|
@ -50,6 +60,22 @@ TEST(heap, One)
|
|||
BLI_heap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, FastOne)
|
||||
{
|
||||
FastHeap *heap;
|
||||
const char *in = "test";
|
||||
|
||||
heap = BLI_fastheap_new();
|
||||
|
||||
BLI_fastheap_insert(heap, 0.0f, (void *)in);
|
||||
EXPECT_FALSE(BLI_fastheap_is_empty(heap));
|
||||
EXPECT_EQ(BLI_fastheap_len(heap), 1);
|
||||
EXPECT_EQ(in, BLI_fastheap_pop_min(heap));
|
||||
EXPECT_TRUE(BLI_fastheap_is_empty(heap));
|
||||
EXPECT_EQ(BLI_fastheap_len(heap), 0);
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, Range)
|
||||
{
|
||||
const int items_total = SIZE;
|
||||
|
|
@ -65,6 +91,21 @@ TEST(heap, Range)
|
|||
BLI_heap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, FastRange)
|
||||
{
|
||||
const int items_total = SIZE;
|
||||
FastHeap *heap = BLI_fastheap_new();
|
||||
for (int in = 0; in < items_total; in++) {
|
||||
BLI_fastheap_insert(heap, (float)in, POINTER_FROM_INT(in));
|
||||
}
|
||||
for (int out_test = 0; out_test < items_total; out_test++) {
|
||||
EXPECT_EQ(out_test, POINTER_AS_INT(BLI_fastheap_pop_min(heap)));
|
||||
|
||||
}
|
||||
EXPECT_TRUE(BLI_fastheap_is_empty(heap));
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, RangeReverse)
|
||||
{
|
||||
const int items_total = SIZE;
|
||||
|
|
@ -79,6 +120,20 @@ TEST(heap, RangeReverse)
|
|||
BLI_heap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, FastRangeReverse)
|
||||
{
|
||||
const int items_total = SIZE;
|
||||
FastHeap *heap = BLI_fastheap_new();
|
||||
for (int in = 0; in < items_total; in++) {
|
||||
BLI_fastheap_insert(heap, (float)-in, POINTER_FROM_INT(-in));
|
||||
}
|
||||
for (int out_test = items_total - 1; out_test >= 0; out_test--) {
|
||||
EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_fastheap_pop_min(heap)));
|
||||
}
|
||||
EXPECT_TRUE(BLI_fastheap_is_empty(heap));
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, RangeRemove)
|
||||
{
|
||||
const int items_total = SIZE;
|
||||
|
|
@ -113,6 +168,20 @@ TEST(heap, Duplicates)
|
|||
BLI_heap_free(heap, NULL);
|
||||
}
|
||||
|
||||
TEST(heap, FastDuplicates)
|
||||
{
|
||||
const int items_total = SIZE;
|
||||
FastHeap *heap = BLI_fastheap_new();
|
||||
for (int in = 0; in < items_total; in++) {
|
||||
BLI_fastheap_insert(heap, 1.0f, 0);
|
||||
}
|
||||
for (int out_test = 0; out_test < items_total; out_test++) {
|
||||
EXPECT_EQ(0, POINTER_AS_INT(BLI_fastheap_pop_min(heap)));
|
||||
}
|
||||
EXPECT_TRUE(BLI_fastheap_is_empty(heap));
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
}
|
||||
|
||||
static void random_heap_helper(
|
||||
const int items_total,
|
||||
const int random_seed)
|
||||
|
|
@ -136,6 +205,28 @@ TEST(heap, Rand1) { random_heap_helper(1, 1234); }
|
|||
TEST(heap, Rand2) { random_heap_helper(2, 1234); }
|
||||
TEST(heap, Rand100) { random_heap_helper(100, 4321); }
|
||||
|
||||
static void random_fastheap_helper(
|
||||
const int items_total,
|
||||
const int random_seed)
|
||||
{
|
||||
FastHeap *heap = BLI_fastheap_new();
|
||||
float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__);
|
||||
range_fl(values, items_total);
|
||||
BLI_array_randomize(values, sizeof(float), items_total, random_seed);
|
||||
for (int i = 0; i < items_total; i++) {
|
||||
BLI_fastheap_insert(heap, values[i], POINTER_FROM_INT((int)values[i]));
|
||||
}
|
||||
for (int out_test = 0; out_test < items_total; out_test++) {
|
||||
EXPECT_EQ(out_test, POINTER_AS_INT(BLI_fastheap_pop_min(heap)));
|
||||
}
|
||||
EXPECT_TRUE(BLI_fastheap_is_empty(heap));
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
MEM_freeN(values);
|
||||
}
|
||||
|
||||
TEST(heap, FastRand1) { random_fastheap_helper(1, 1234); }
|
||||
TEST(heap, FastRand2) { random_fastheap_helper(2, 1234); }
|
||||
TEST(heap, FastRand100) { random_fastheap_helper(100, 4321); }
|
||||
|
||||
TEST(heap, ReInsertSimple)
|
||||
{
|
||||
|
|
|
|||
Loading…
Reference in New Issue