[Bf-blender-cvs] [9099305771e] master: Cleanup: rename BLI_kdtree vars & args for clarity
Campbell Barton
noreply at git.blender.org
Mon Mar 18 00:26:46 CET 2019
Commit: 9099305771ecf0b9af381894302d57a67e2de9ad
Author: Campbell Barton
Date: Mon Mar 18 10:21:45 2019 +1100
Branches: master
https://developer.blender.org/rB9099305771ecf0b9af381894302d57a67e2de9ad
Cleanup: rename BLI_kdtree vars & args for clarity
===================================================================
M source/blender/blenlib/BLI_kdtree.h
M source/blender/blenlib/intern/BLI_kdtree.c
===================================================================
diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h
index 3b21ad76b4d..fd404fa5aab 100644
--- a/source/blender/blenlib/BLI_kdtree.h
+++ b/source/blender/blenlib/BLI_kdtree.h
@@ -44,8 +44,8 @@ int BLI_kdtree_find_nearest(
const KDTree *tree, const float co[3],
KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2);
-#define BLI_kdtree_find_nearest_n(tree, co, r_nearest, n) \
- BLI_kdtree_find_nearest_n_with_len_squared_cb(tree, co, r_nearest, n, NULL, NULL)
+#define BLI_kdtree_find_nearest_n(tree, co, r_nearest, nearest_len_capacity) \
+ BLI_kdtree_find_nearest_n_with_len_squared_cb(tree, co, r_nearest, nearest_len_capacity, NULL, NULL)
#define BLI_kdtree_range_search(tree, co, r_nearest, range) \
BLI_kdtree_range_search_with_len_squared_cb(tree, co, r_nearest, range, NULL, NULL)
@@ -65,13 +65,13 @@ int BLI_kdtree_calc_duplicates_fast(
int BLI_kdtree_find_nearest_n_with_len_squared_cb(
const KDTree *tree, const float co[3],
KDTreeNearest *r_nearest,
- unsigned int n,
+ const uint nearest_len_capacity,
float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data),
const void *user_data) ATTR_NONNULL(1, 2, 3);
int BLI_kdtree_range_search_with_len_squared_cb(
const KDTree *tree, const float co[3],
KDTreeNearest **r_nearest,
- float range,
+ const float range,
float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data),
const void *user_data) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT;
diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c
index 92761a5ec7a..e9b8d173eb1 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -40,11 +40,11 @@ typedef struct KDTreeNode {
struct KDTree {
KDTreeNode *nodes;
- uint totnode;
+ uint nodes_len;
uint root;
#ifdef DEBUG
bool is_balanced; /* ensure we call balance first */
- uint maxsize; /* max size of the tree */
+ uint nodes_len_capacity; /* max size of the tree */
#endif
};
@@ -60,18 +60,18 @@ struct KDTree {
/**
* Creates or free a kdtree
*/
-KDTree *BLI_kdtree_new(uint maxsize)
+KDTree *BLI_kdtree_new(uint nodes_len_capacity)
{
KDTree *tree;
tree = MEM_mallocN(sizeof(KDTree), "KDTree");
- tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode");
- tree->totnode = 0;
+ tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * nodes_len_capacity, "KDTreeNode");
+ tree->nodes_len = 0;
tree->root = KD_NODE_ROOT_IS_INIT;
#ifdef DEBUG
tree->is_balanced = false;
- tree->maxsize = maxsize;
+ tree->nodes_len_capacity = nodes_len_capacity;
#endif
return tree;
@@ -90,10 +90,10 @@ void BLI_kdtree_free(KDTree *tree)
*/
void BLI_kdtree_insert(KDTree *tree, int index, const float co[3])
{
- KDTreeNode *node = &tree->nodes[tree->totnode++];
+ KDTreeNode *node = &tree->nodes[tree->nodes_len++];
#ifdef DEBUG
- BLI_assert(tree->totnode <= tree->maxsize);
+ BLI_assert(tree->nodes_len <= tree->nodes_len_capacity);
#endif
/* note, array isn't calloc'd,
@@ -109,23 +109,23 @@ void BLI_kdtree_insert(KDTree *tree, int index, const float co[3])
#endif
}
-static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uint ofs)
+static uint kdtree_balance(KDTreeNode *nodes, uint nodes_len, uint axis, const uint ofs)
{
KDTreeNode *node;
float co;
uint left, right, median, i, j;
- if (totnode <= 0) {
+ if (nodes_len <= 0) {
return KD_NODE_UNSET;
}
- else if (totnode == 1) {
+ else if (nodes_len == 1) {
return 0 + ofs;
}
/* quicksort style sorting around median */
left = 0;
- right = totnode - 1;
- median = totnode / 2;
+ right = nodes_len - 1;
+ median = nodes_len / 2;
while (right > left) {
co = nodes[right].co[axis];
@@ -157,7 +157,7 @@ static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uin
node->d = axis;
axis = (axis + 1) % 3;
node->left = kdtree_balance(nodes, median, axis, ofs);
- node->right = kdtree_balance(nodes + median + 1, (totnode - (median + 1)), axis, (median + 1) + ofs);
+ node->right = kdtree_balance(nodes + median + 1, (nodes_len - (median + 1)), axis, (median + 1) + ofs);
return median + ofs;
}
@@ -165,13 +165,13 @@ static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uin
void BLI_kdtree_balance(KDTree *tree)
{
if (tree->root != KD_NODE_ROOT_IS_INIT) {
- for (uint i = 0; i < tree->totnode; i++) {
+ for (uint i = 0; i < tree->nodes_len; i++) {
tree->nodes[i].left = KD_NODE_UNSET;
tree->nodes[i].right = KD_NODE_UNSET;
}
}
- tree->root = kdtree_balance(tree->nodes, tree->totnode, 0, 0);
+ tree->root = kdtree_balance(tree->nodes, tree->nodes_len, 0, 0);
#ifdef DEBUG
tree->is_balanced = true;
@@ -183,15 +183,15 @@ static float len_squared_v3v3_cb(const float co_kdtree[3], const float co_search
return len_squared_v3v3(co_kdtree, co_search);
}
-static uint *realloc_nodes(uint *stack, uint *totstack, const bool is_alloc)
+static uint *realloc_nodes(uint *stack, uint *stack_len_capacity, const bool is_alloc)
{
- uint *stack_new = MEM_mallocN((*totstack + KD_NEAR_ALLOC_INC) * sizeof(uint), "KDTree.treestack");
- memcpy(stack_new, stack, *totstack * sizeof(uint));
- // memset(stack_new + *totstack, 0, sizeof(uint) * KD_NEAR_ALLOC_INC);
+ uint *stack_new = MEM_mallocN((*stack_len_capacity + KD_NEAR_ALLOC_INC) * sizeof(uint), "KDTree.treestack");
+ memcpy(stack_new, stack, *stack_len_capacity * sizeof(uint));
+ // memset(stack_new + *stack_len_capacity, 0, sizeof(uint) * KD_NEAR_ALLOC_INC);
if (is_alloc) {
MEM_freeN(stack);
}
- *totstack += KD_NEAR_ALLOC_INC;
+ *stack_len_capacity += KD_NEAR_ALLOC_INC;
return stack_new;
}
@@ -204,9 +204,9 @@ int BLI_kdtree_find_nearest(
{
const KDTreeNode *nodes = tree->nodes;
const KDTreeNode *root, *min_node;
- uint *stack, defaultstack[KD_STACK_INIT];
+ uint *stack, stack_default[KD_STACK_INIT];
float min_dist, cur_dist;
- uint totstack, cur = 0;
+ uint stack_len_capacity, cur = 0;
#ifdef DEBUG
BLI_assert(tree->is_balanced == true);
@@ -216,8 +216,8 @@ int BLI_kdtree_find_nearest(
return -1;
}
- stack = defaultstack;
- totstack = KD_STACK_INIT;
+ stack = stack_default;
+ stack_len_capacity = KD_STACK_INIT;
root = &nodes[tree->root];
min_node = root;
@@ -279,8 +279,8 @@ int BLI_kdtree_find_nearest(
stack[cur++] = node->left;
}
}
- if (UNLIKELY(cur + 3 > totstack)) {
- stack = realloc_nodes(stack, &totstack, defaultstack != stack);
+ if (UNLIKELY(cur + 3 > stack_len_capacity)) {
+ stack = realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
}
}
@@ -290,7 +290,7 @@ int BLI_kdtree_find_nearest(
copy_v3_v3(r_nearest->co, min_node->co);
}
- if (stack != defaultstack) {
+ if (stack != stack_default) {
MEM_freeN(stack);
}
@@ -313,9 +313,9 @@ int BLI_kdtree_find_nearest_cb(
const KDTreeNode *nodes = tree->nodes;
const KDTreeNode *min_node = NULL;
- uint *stack, defaultstack[KD_STACK_INIT];
+ uint *stack, stack_default[KD_STACK_INIT];
float min_dist = FLT_MAX, cur_dist;
- uint totstack, cur = 0;
+ uint stack_len_capacity, cur = 0;
#ifdef DEBUG
BLI_assert(tree->is_balanced == true);
@@ -325,8 +325,8 @@ int BLI_kdtree_find_nearest_cb(
return -1;
}
- stack = defaultstack;
- totstack = KD_STACK_INIT;
+ stack = stack_default;
+ stack_len_capacity = ARRAY_SIZE(stack_default);
#define NODE_TEST_NEAREST(node) \
{ \
@@ -382,8 +382,8 @@ int BLI_kdtree_find_nearest_cb(
stack[cur++] = node->left;
}
}
- if (UNLIKELY(cur + 3 > totstack)) {
- stack = realloc_nodes(stack, &totstack, defaultstack != stack);
+ if (UNLIKELY(cur + 3 > stack_len_capacity)) {
+ stack = realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
}
}
@@ -391,7 +391,7 @@ int BLI_kdtree_find_nearest_cb(
finally:
- if (stack != defaultstack) {
+ if (stack != stack_default) {
MEM_freeN(stack);
}
@@ -409,55 +409,54 @@ finally:
}
}
-static void add_nearest(
- KDTreeNearest *ptn, uint *found, const uint n, const int index,
- const float dist, const float co[3])
+static void nearest_ordered_insert(
+ KDTreeNearest *nearest, uint *nearest_len, const uint nearest_len_capacity,
+ const int index, const float dist, const float co[3])
{
uint i;
- if (*found < n) {
- (*found)++;
+ if (*nearest_len < nearest_len_capacity) {
+ (*nearest_len)++;
}
- for (i = *found - 1; i > 0; i--) {
- if (dist >= ptn[i - 1].dist) {
+ for (i = *nearest_len - 1; i > 0; i--) {
+ if (dist >= nearest[i - 1].dist) {
break;
}
else {
- ptn[i] = ptn[i - 1];
+ nearest[i] = nearest[i - 1];
}
}
- ptn[i].index = index;
- ptn[i].dist = dist;
- copy_v3_v3(ptn[i].co, co);
+ nearest[i].index = index;
+ nearest[i].dist = dist;
+ copy_v3_v3(nearest[i].co, co);
}
/**
- * Find n nearest returns number of points found, with results in nearest.
- * Normal is optional, but if given will limit results to points in normal direction from co.
+ * Find \a nearest_len_capacity nearest returns number of points found, with results in nearest.
*
- * \param r_nearest: An array of nearest, sized at least \a n.
+ * \param r_nearest: An array of nearest, sized at least \a nearest_len_capacity.
*/
int BLI_kdtree_find_nearest_n_with_len_squared_cb(
const KDTree *tree, const float co[3],
KDTreeNearest r_nearest[],
- uint n,
+ const uint nearest_len_capacity,
float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data),
const void *user_data)
{
const KDTreeNode *nodes = tree->nodes;
const KDTreeNode *root;
- uint *stack, defaultstack[KD_STACK_INIT];
+ uint *stack, stack_default[KD_STACK_INIT];
float cur_dist;
- uint totstack, cur = 0;
- uint i, found = 0;
+ uint stack_len_capacity, cur = 0;
+ uint i, nearest_len = 0;
#ifdef DEBUG
BLI_assert(tree->is_balanced == true);
#endif
- if (UNLIKELY((tree->root == KD_NODE_UNSET) || n == 0)) {
+ if (UNLIKELY((tree->root == KD_N
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list