Cleanup: rename fast-heap -> heap-simple
In general prefer API names don't start with adjectives since it causes grouping of unrelated API's for completion.
This commit is contained in:
parent
d805a4a5ef
commit
900c562b71
|
@ -721,7 +721,7 @@ static void pbvh_bmesh_node_drop_orig(PBVHNode *node)
|
|||
struct EdgeQueue;
|
||||
|
||||
typedef struct EdgeQueue {
|
||||
FastHeap *heap;
|
||||
HeapSimple *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_fastheap_insert(eq_ctx->q->heap, priority, pair);
|
||||
BLI_heapsimple_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_fastheap_new();
|
||||
eq_ctx->q->heap = BLI_heapsimple_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_fastheap_new();
|
||||
eq_ctx->q->heap = BLI_heapsimple_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_fastheap_is_empty(eq_ctx->q->heap)) {
|
||||
BMVert **pair = BLI_fastheap_pop_min(eq_ctx->q->heap);
|
||||
while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) {
|
||||
BMVert **pair = BLI_heapsimple_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_fastheap_is_empty(eq_ctx->q->heap)) {
|
||||
BMVert **pair = BLI_fastheap_pop_min(eq_ctx->q->heap);
|
||||
while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) {
|
||||
BMVert **pair = BLI_heapsimple_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_fastheap_free(q.heap, NULL);
|
||||
BLI_heapsimple_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_fastheap_free(q.heap, NULL);
|
||||
BLI_heapsimple_free(q.heap, NULL);
|
||||
BLI_mempool_destroy(queue_pool);
|
||||
}
|
||||
|
||||
|
|
|
@ -26,20 +26,19 @@
|
|||
* \brief A min-heap / priority queue ADT
|
||||
*/
|
||||
|
||||
|
||||
struct FastHeap;
|
||||
typedef struct FastHeap FastHeap;
|
||||
struct HeapSimple;
|
||||
typedef struct HeapSimple HeapSimple;
|
||||
|
||||
typedef void (*HeapSimpleFreeFP)(void *ptr);
|
||||
|
||||
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, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1);
|
||||
void BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP 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);
|
||||
uint 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);
|
||||
HeapSimple *BLI_heapsimple_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT;
|
||||
HeapSimple *BLI_heapsimple_new(void) ATTR_WARN_UNUSED_RESULT;
|
||||
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1);
|
||||
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1);
|
||||
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1);
|
||||
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1);
|
||||
uint BLI_heapsimple_len(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
|
||||
float BLI_heapsimple_top_value(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
|
||||
void *BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1);
|
||||
|
||||
#endif /* __BLI_HEAP_SIMPLE_H__ */
|
||||
|
|
|
@ -24,6 +24,8 @@
|
|||
* A min-heap / priority queue ADT.
|
||||
*
|
||||
* Simplified version of the heap that only supports insertion and removal from top.
|
||||
*
|
||||
* See BLI_heap.c for a more full featured heap implementation.
|
||||
*/
|
||||
|
||||
#include <stdlib.h>
|
||||
|
@ -38,37 +40,37 @@
|
|||
#define HEAP_PARENT(i) (((i) - 1) >> 1)
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/** \name FastHeap Internal Structs
|
||||
/** \name HeapSimple Internal Structs
|
||||
* \{ */
|
||||
|
||||
typedef struct FastHeapNode {
|
||||
typedef struct HeapSimpleNode {
|
||||
float value;
|
||||
void *ptr;
|
||||
} FastHeapNode;
|
||||
} HeapSimpleNode;
|
||||
|
||||
struct FastHeap {
|
||||
struct HeapSimple {
|
||||
uint size;
|
||||
uint bufsize;
|
||||
FastHeapNode *tree;
|
||||
HeapSimpleNode *tree;
|
||||
};
|
||||
|
||||
/** \} */
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/** \name FastHeap Internal Functions
|
||||
/** \name HeapSimple Internal Functions
|
||||
* \{ */
|
||||
|
||||
static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *init)
|
||||
static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *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)))
|
||||
#define OFFSET(i) (i * (uint)sizeof(HeapSimpleNode))
|
||||
#define NODE(offset) (*(HeapSimpleNode*)(tree_buf + (offset)))
|
||||
#else
|
||||
FastHeapNode *const tree = heap->tree;
|
||||
HeapSimpleNode *const tree = heap->tree;
|
||||
|
||||
#define OFFSET(i) (i)
|
||||
#define NODE(i) tree[i]
|
||||
|
@ -124,9 +126,9 @@ static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *init
|
|||
#undef HEAP_LEFT_OFFSET
|
||||
}
|
||||
|
||||
static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr)
|
||||
static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
|
||||
{
|
||||
FastHeapNode *const tree = heap->tree;
|
||||
HeapSimpleNode *const tree = heap->tree;
|
||||
|
||||
while (LIKELY(i > 0)) {
|
||||
const uint p = HEAP_PARENT(i);
|
||||
|
@ -146,30 +148,30 @@ static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_p
|
|||
/** \} */
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/** \name Public FastHeap API
|
||||
/** \name Public HeapSimple API
|
||||
* \{ */
|
||||
|
||||
/**
|
||||
* Creates a new fast heap, which only supports insertion and removal from top.
|
||||
* Creates a new simple 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)
|
||||
HeapSimple *BLI_heapsimple_new_ex(uint tot_reserve)
|
||||
{
|
||||
FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __func__);
|
||||
HeapSimple *heap = MEM_mallocN(sizeof(HeapSimple), __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");
|
||||
heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapSimpleNode), "BLIHeapSimpleTree");
|
||||
return heap;
|
||||
}
|
||||
|
||||
FastHeap *BLI_fastheap_new(void)
|
||||
HeapSimple *BLI_heapsimple_new(void)
|
||||
{
|
||||
return BLI_fastheap_new_ex(1);
|
||||
return BLI_heapsimple_new_ex(1);
|
||||
}
|
||||
|
||||
void BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP ptrfreefp)
|
||||
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
|
||||
{
|
||||
if (ptrfreefp) {
|
||||
for (uint i = 0; i < heap->size; i++) {
|
||||
|
@ -181,7 +183,7 @@ void BLI_fastheap_free(FastHeap *heap, HeapSimpleFreeFP ptrfreefp)
|
|||
MEM_freeN(heap);
|
||||
}
|
||||
|
||||
void BLI_fastheap_clear(FastHeap *heap, HeapSimpleFreeFP ptrfreefp)
|
||||
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
|
||||
{
|
||||
if (ptrfreefp) {
|
||||
for (uint i = 0; i < heap->size; i++) {
|
||||
|
@ -196,22 +198,22 @@ void BLI_fastheap_clear(FastHeap *heap, HeapSimpleFreeFP ptrfreefp)
|
|||
* 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)
|
||||
void BLI_heapsimple_insert(HeapSimple *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);
|
||||
heapsimple_up(heap, heap->size++, value, ptr);
|
||||
}
|
||||
|
||||
bool BLI_fastheap_is_empty(const FastHeap *heap)
|
||||
bool BLI_heapsimple_is_empty(const HeapSimple *heap)
|
||||
{
|
||||
return (heap->size == 0);
|
||||
}
|
||||
|
||||
uint BLI_fastheap_len(const FastHeap *heap)
|
||||
uint BLI_heapsimple_len(const HeapSimple *heap)
|
||||
{
|
||||
return heap->size;
|
||||
}
|
||||
|
@ -219,7 +221,7 @@ uint BLI_fastheap_len(const FastHeap *heap)
|
|||
/**
|
||||
* Return the lowest value of the heap.
|
||||
*/
|
||||
float BLI_fastheap_top_value(const FastHeap *heap)
|
||||
float BLI_heapsimple_top_value(const HeapSimple *heap)
|
||||
{
|
||||
BLI_assert(heap->size != 0);
|
||||
|
||||
|
@ -229,14 +231,14 @@ float BLI_fastheap_top_value(const FastHeap *heap)
|
|||
/**
|
||||
* Pop the top node off the heap and return it's pointer.
|
||||
*/
|
||||
void *BLI_fastheap_pop_min(FastHeap *heap)
|
||||
void *BLI_heapsimple_pop_min(HeapSimple *heap)
|
||||
{
|
||||
BLI_assert(heap->size != 0);
|
||||
|
||||
void *ptr = heap->tree[0].ptr;
|
||||
|
||||
if (--heap->size) {
|
||||
fastheap_down(heap, 0, &heap->tree[heap->size]);
|
||||
heapsimple_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)
|
||||
{
|
||||
FastHeap *todo_nodes;
|
||||
HeapSimple *todo_nodes;
|
||||
|
||||
BLI_bitmap *done_nodes = r_solution->done_nodes;
|
||||
int *prev_nodes = r_solution->prev_nodes;
|
||||
|
@ -225,13 +225,14 @@ bool BLI_astar_graph_solve(
|
|||
return true;
|
||||
}
|
||||
|
||||
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));
|
||||
todo_nodes = BLI_heapsimple_new();
|
||||
BLI_heapsimple_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_fastheap_is_empty(todo_nodes)) {
|
||||
const int node_curr_idx = POINTER_AS_INT(BLI_fastheap_pop_min(todo_nodes));
|
||||
while (!BLI_heapsimple_is_empty(todo_nodes)) {
|
||||
const int node_curr_idx = POINTER_AS_INT(BLI_heapsimple_pop_min(todo_nodes));
|
||||
BLI_AStarGNode *node_curr = &as_graph->nodes[node_curr_idx];
|
||||
LinkData *ld;
|
||||
|
||||
|
@ -249,7 +250,7 @@ bool BLI_astar_graph_solve(
|
|||
/* Success! Path found... */
|
||||
r_solution->steps = g_steps[node_curr_idx] + 1;
|
||||
|
||||
BLI_fastheap_free(todo_nodes, NULL);
|
||||
BLI_heapsimple_free(todo_nodes, NULL);
|
||||
return true;
|
||||
}
|
||||
|
||||
|
@ -269,14 +270,15 @@ 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_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_heapsimple_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_free(todo_nodes, NULL);
|
||||
BLI_heapsimple_free(todo_nodes, NULL);
|
||||
return false;
|
||||
}
|
||||
|
|
|
@ -94,7 +94,7 @@
|
|||
// #define DEBUG_PRINT
|
||||
|
||||
typedef struct PathContext {
|
||||
FastHeap *states;
|
||||
HeapSimple *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_fastheap_insert(pc->states, state->dist, state);
|
||||
BLI_heapsimple_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_fastheap_new();
|
||||
pc.states = BLI_heapsimple_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_fastheap_insert(pc.states, state->dist, state);
|
||||
BLI_heapsimple_insert(pc.states, state->dist, state);
|
||||
}
|
||||
|
||||
|
||||
while (!BLI_fastheap_is_empty(pc.states)) {
|
||||
while (!BLI_heapsimple_is_empty(pc.states)) {
|
||||
|
||||
#ifdef DEBUG_PRINT
|
||||
printf("\n%s: stepping %u\n", __func__, BLI_fastheap_len(pc.states));
|
||||
printf("\n%s: stepping %u\n", __func__, BLI_heapsimple_len(pc.states));
|
||||
#endif
|
||||
|
||||
while (!BLI_fastheap_is_empty(pc.states)) {
|
||||
PathLinkState *state = BLI_fastheap_pop_min(pc.states);
|
||||
while (!BLI_heapsimple_is_empty(pc.states)) {
|
||||
PathLinkState *state = BLI_heapsimple_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_fastheap_clear(pc.states, MEM_freeN);
|
||||
BLI_heapsimple_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_fastheap_insert(pc.states, state->dist, state);
|
||||
BLI_heapsimple_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_fastheap_free(pc.states, MEM_freeN);
|
||||
BLI_heapsimple_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(
|
||||
FastHeap *heap, BMVert *v_a, BMVert **verts_prev, float *cost,
|
||||
HeapSimple *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_fastheap_insert(heap, cost_new, v_b);
|
||||
BLI_heapsimple_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_fastheap_insert(heap, cost_new, v_b);
|
||||
BLI_heapsimple_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;
|
||||
FastHeap *heap;
|
||||
HeapSimple *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_fastheap_new();
|
||||
BLI_fastheap_insert(heap, 0.0f, v_src);
|
||||
heap = BLI_heapsimple_new();
|
||||
BLI_heapsimple_insert(heap, 0.0f, v_src);
|
||||
cost[BM_elem_index_get(v_src)] = 0.0f;
|
||||
|
||||
while (!BLI_fastheap_is_empty(heap)) {
|
||||
v = BLI_fastheap_pop_min(heap);
|
||||
while (!BLI_heapsimple_is_empty(heap)) {
|
||||
v = BLI_heapsimple_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_fastheap_free(heap, NULL);
|
||||
BLI_heapsimple_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(
|
||||
FastHeap *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost,
|
||||
HeapSimple *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_fastheap_insert(heap, cost_new, e_b);
|
||||
BLI_heapsimple_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_fastheap_insert(heap, cost_new, e_b);
|
||||
BLI_heapsimple_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;
|
||||
FastHeap *heap;
|
||||
HeapSimple *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_fastheap_new();
|
||||
BLI_fastheap_insert(heap, 0.0f, e_src);
|
||||
heap = BLI_heapsimple_new();
|
||||
BLI_heapsimple_insert(heap, 0.0f, e_src);
|
||||
cost[BM_elem_index_get(e_src)] = 0.0f;
|
||||
|
||||
while (!BLI_fastheap_is_empty(heap)) {
|
||||
e = BLI_fastheap_pop_min(heap);
|
||||
while (!BLI_heapsimple_is_empty(heap)) {
|
||||
e = BLI_heapsimple_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_fastheap_free(heap, NULL);
|
||||
BLI_heapsimple_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(
|
||||
FastHeap *heap, BMFace *f_a, BMFace **faces_prev, float *cost,
|
||||
HeapSimple *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_fastheap_insert(heap, cost_new, f_b);
|
||||
BLI_heapsimple_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_fastheap_insert(heap, cost_new, f_b);
|
||||
BLI_heapsimple_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;
|
||||
FastHeap *heap;
|
||||
HeapSimple *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_fastheap_new();
|
||||
BLI_fastheap_insert(heap, 0.0f, f_src);
|
||||
heap = BLI_heapsimple_new();
|
||||
BLI_heapsimple_insert(heap, 0.0f, f_src);
|
||||
cost[BM_elem_index_get(f_src)] = 0.0f;
|
||||
|
||||
while (!BLI_fastheap_is_empty(heap)) {
|
||||
f = BLI_fastheap_pop_min(heap);
|
||||
while (!BLI_heapsimple_is_empty(heap)) {
|
||||
f = BLI_heapsimple_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_fastheap_free(heap, NULL);
|
||||
BLI_heapsimple_free(heap, NULL);
|
||||
|
||||
return path;
|
||||
}
|
||||
|
|
|
@ -1705,7 +1705,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)
|
||||
{
|
||||
FastHeap *heap;
|
||||
HeapSimple *heap;
|
||||
|
||||
int i, vert_curr;
|
||||
|
||||
|
@ -1728,18 +1728,18 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst
|
|||
}
|
||||
|
||||
/* init heap */
|
||||
heap = BLI_fastheap_new();
|
||||
heap = BLI_heapsimple_new();
|
||||
|
||||
vert_curr = data[vert_src].vert;
|
||||
BLI_fastheap_insert(heap, 0.0f, &data[vert_src].vert);
|
||||
BLI_heapsimple_insert(heap, 0.0f, &data[vert_src].vert);
|
||||
data[vert_src].cost = 0.0f;
|
||||
data[vert_src].vert_prev = vert_src; /* nop */
|
||||
|
||||
while (!BLI_fastheap_is_empty(heap)) {
|
||||
while (!BLI_heapsimple_is_empty(heap)) {
|
||||
int axis, sign;
|
||||
int u, v;
|
||||
|
||||
vert_curr = *((int *)BLI_fastheap_pop_min(heap));
|
||||
vert_curr = *((int *)BLI_heapsimple_pop_min(heap));
|
||||
if (vert_curr == vert_dst) {
|
||||
break;
|
||||
}
|
||||
|
@ -1761,7 +1761,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_fastheap_insert(heap, data[vert_other].cost, &data[vert_other].vert);
|
||||
BLI_heapsimple_insert(heap, data[vert_other].cost, &data[vert_other].vert);
|
||||
}
|
||||
data[vert_other].vert_prev = vert_curr;
|
||||
}
|
||||
|
@ -1772,7 +1772,7 @@ static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst
|
|||
|
||||
}
|
||||
|
||||
BLI_fastheap_free(heap, NULL);
|
||||
BLI_heapsimple_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);
|
||||
|
||||
FastHeap *loop_weight = BLI_fastheap_new();
|
||||
HeapSimple *loop_weight = BLI_heapsimple_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_fastheap_insert(loop_weight, val, lfan_pivot);
|
||||
BLI_heapsimple_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_fastheap_top_value(loop_weight);
|
||||
float val = BLI_heapsimple_top_value(loop_weight);
|
||||
|
||||
while (!BLI_fastheap_is_empty(loop_weight)) {
|
||||
const float cur_val = BLI_fastheap_top_value(loop_weight);
|
||||
while (!BLI_heapsimple_is_empty(loop_weight)) {
|
||||
const float cur_val = BLI_heapsimple_top_value(loop_weight);
|
||||
if (!compare_ff(val, cur_val, threshold)) {
|
||||
count++;
|
||||
val = cur_val;
|
||||
}
|
||||
l = BLI_fastheap_pop_min(loop_weight);
|
||||
l = BLI_heapsimple_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_fastheap_free(loop_weight, NULL);
|
||||
BLI_heapsimple_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;
|
||||
FastHeap *heap;
|
||||
HeapSimple *heap;
|
||||
float score;
|
||||
|
||||
heap = BLI_fastheap_new();
|
||||
heap = BLI_heapsimple_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_fastheap_insert(heap, -score, e);
|
||||
BLI_heapsimple_insert(heap, -score, e);
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
while (!BLI_fastheap_is_empty(heap)) {
|
||||
while (!BLI_heapsimple_is_empty(heap)) {
|
||||
BMFace *adj[2];
|
||||
|
||||
e = BLI_fastheap_pop_min(heap);
|
||||
e = BLI_heapsimple_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_fastheap_free(heap, NULL);
|
||||
BLI_heapsimple_free(heap, NULL);
|
||||
|
||||
BM_mesh_delete_hflag_tagged(so->bm, BM_ELEM_TAG, BM_EDGE | BM_FACE);
|
||||
|
||||
|
|
Loading…
Reference in New Issue