Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--source/blender/blenkernel/intern/pbvh_bmesh.c20
-rw-r--r--source/blender/blenlib/BLI_heap_simple.h23
-rw-r--r--source/blender/blenlib/intern/BLI_heap_simple.c58
-rw-r--r--source/blender/blenlib/intern/astar.c26
-rw-r--r--source/blender/bmesh/operators/bmo_connect_pair.c22
-rw-r--r--source/blender/bmesh/tools/bmesh_path.c54
-rw-r--r--source/blender/editors/curve/editcurve_select.c14
-rw-r--r--source/blender/editors/mesh/editmesh_tools.c14
-rw-r--r--source/blender/modifiers/intern/MOD_skin.c12
9 files changed, 123 insertions, 120 deletions
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 35c02a250dd..3369b05ea60 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 {
- 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);
}
diff --git a/source/blender/blenlib/BLI_heap_simple.h b/source/blender/blenlib/BLI_heap_simple.h
index 077c8cc1bb9..eed33558d84 100644
--- a/source/blender/blenlib/BLI_heap_simple.h
+++ b/source/blender/blenlib/BLI_heap_simple.h
@@ -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__ */
diff --git a/source/blender/blenlib/intern/BLI_heap_simple.c b/source/blender/blenlib/intern/BLI_heap_simple.c
index 66766489781..777b9c61b28 100644
--- a/source/blender/blenlib/intern/BLI_heap_simple.c
+++ b/source/blender/blenlib/intern/BLI_heap_simple.c
@@ -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;
diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c
index 959d1a46ac5..30ad6c7838c 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)
{
- 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;
}
diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c
index 4deffb8b652..caf40c71756 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 {
- 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) {
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c
index 76ab3b33018..07e3c2a2d78 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(
- 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;
}
diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c
index d8db1bb1dd4..3c4d8caba3a 100644
--- a/source/blender/editors/curve/editcurve_select.c
+++ b/source/blender/editors/curve/editcurve_select.c
@@ -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;
diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c
index 9fe4ea46913..b7ab1e159f7 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);
- 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;
diff --git a/source/blender/modifiers/intern/MOD_skin.c b/source/blender/modifiers/intern/MOD_skin.c
index 098f4051347..87d47769cdb 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;
- 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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-28 01:10:13 +0300