KDTree: deprecate 'normal' argument

Normals for each kdtree node were allocated but never used,
and search args only use in particles/boids code.

1 files changed, 21 insertions, 25 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c
index c8ee0c11fc7..1a4d8bc7f78 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -35,7 +35,7 @@
 
 typedef struct KDTreeNode {
 	struct KDTreeNode *left, *right;
-	float co[3], nor[3];
+	float co[3];
 	int index;
 	unsigned int d;  /* range is only (0-2) */
 } KDTreeNode;
@@ -85,7 +85,7 @@ void BLI_kdtree_free(KDTree *tree)
 /**
  * Construction: first insert points, then call balance. Normal is optional.
  */
-void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3])
+void BLI_kdtree_insert(KDTree *tree, int index, const float co[3])
 {
 	KDTreeNode *node = &tree->nodes[tree->totnode++];
 
@@ -98,11 +98,6 @@ void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float n
 
 	node->left = node->right = NULL;
 	copy_v3_v3(node->co, co);
-	if (nor)
-		copy_v3_v3(node->nor, nor);
-	else
-		zero_v3(node->nor);
-
 	node->index = index;
 	node->d = 0;
 
@@ -167,7 +162,7 @@ void BLI_kdtree_balance(KDTree *tree)
 #endif
 }
 
-static float squared_distance(const float v2[3], const float v1[3], const float UNUSED(n1[3]), const float n2[3])
+static float squared_distance(const float v2[3], const float v1[3], const float n2[3])
 {
 	float d[3], dist;
 
@@ -177,8 +172,6 @@ static float squared_distance(const float v2[3], const float v1[3], const float
 
 	dist = dot_v3v3(d, d);
 
-	//if (n1 && n2 && (dot_v3v3(n1, n2) < 0.0f))
-
 	/* can someone explain why this is done?*/
 	if (n2 && (dot_v3v3(d, n2) < 0.0f)) {
 		dist *= 10.0f;
@@ -201,8 +194,9 @@ static KDTreeNode **realloc_nodes(KDTreeNode **stack, unsigned int *totstack, co
 /**
  * Find nearest returns index, and -1 if no node is found.
  */
-int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
-                            KDTreeNearest *r_nearest)
+int BLI_kdtree_find_nearest(
+        KDTree *tree, const float co[3],
+        KDTreeNearest *r_nearest)
 {
 	KDTreeNode *root, *node, *min_node;
 	KDTreeNode **stack, *defaultstack[KD_STACK_INIT];
@@ -221,7 +215,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
 
 	root = tree->root;
 	min_node = root;
-	min_dist = squared_distance(root->co, co, root->nor, nor);
+	min_dist = len_squared_v3v3(root->co, co);
 
 	if (co[root->d] < root->co[root->d]) {
 		if (root->right)
@@ -245,7 +239,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
 			cur_dist = -cur_dist * cur_dist;
 
 			if (-cur_dist < min_dist) {
-				cur_dist = squared_distance(node->co, co, node->nor, nor);
+				cur_dist = len_squared_v3v3(node->co, co);
 				if (cur_dist < min_dist) {
 					min_dist = cur_dist;
 					min_node = node;
@@ -260,7 +254,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
 			cur_dist = cur_dist * cur_dist;
 
 			if (cur_dist < min_dist) {
-				cur_dist = squared_distance(node->co, co, node->nor, nor);
+				cur_dist = len_squared_v3v3(node->co, co);
 				if (cur_dist < min_dist) {
 					min_dist = cur_dist;
 					min_node = node;
@@ -313,9 +307,10 @@ static void add_nearest(KDTreeNearest *ptn, unsigned int *found, unsigned int n,
  *
  * \param r_nearest  An array of nearest, sized at least \a n.
  */
-int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3],
-                              KDTreeNearest r_nearest[],
-                              unsigned int n)
+int BLI_kdtree_find_nearest_n__normal(
+        KDTree *tree, const float co[3], const float nor[3],
+        KDTreeNearest r_nearest[],
+        unsigned int n)
 {
 	KDTreeNode *root, *node = NULL;
 	KDTreeNode **stack, *defaultstack[KD_STACK_INIT];
@@ -335,7 +330,7 @@ int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3
 
 	root = tree->root;
 
-	cur_dist = squared_distance(root->co, co, root->nor, nor);
+	cur_dist = squared_distance(root->co, co, nor);
 	add_nearest(r_nearest, &found, n, root->index, cur_dist, root->co);
 	
 	if (co[root->d] < root->co[root->d]) {
@@ -360,7 +355,7 @@ int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3
 			cur_dist = -cur_dist * cur_dist;
 
 			if (found < n || -cur_dist < r_nearest[found - 1].dist) {
-				cur_dist = squared_distance(node->co, co, node->nor, nor);
+				cur_dist = squared_distance(node->co, co, nor);
 
 				if (found < n || cur_dist < r_nearest[found - 1].dist)
 					add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co);
@@ -375,7 +370,7 @@ int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3
 			cur_dist = cur_dist * cur_dist;
 
 			if (found < n || cur_dist < r_nearest[found - 1].dist) {
-				cur_dist = squared_distance(node->co, co, node->nor, nor);
+				cur_dist = squared_distance(node->co, co, nor);
 				if (found < n || cur_dist < r_nearest[found - 1].dist)
 					add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co);
 
@@ -436,8 +431,9 @@ static void add_in_range(KDTreeNearest **ptn, unsigned int found, unsigned int *
  * Normal is optional, but if given will limit results to points in normal direction from co.
  * Remember to free nearest after use!
  */
-int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3],
-                            KDTreeNearest **r_nearest, float range)
+int BLI_kdtree_range_search__normal(
+        KDTree *tree, const float co[3], const float nor[3],
+        KDTreeNearest **r_nearest, float range)
 {
 	KDTreeNode *root, *node = NULL;
 	KDTreeNode **stack, *defaultstack[KD_STACK_INIT];
@@ -466,7 +462,7 @@ int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3],
 			stack[cur++] = root->right;
 	}
 	else {
-		dist2 = squared_distance(root->co, co, root->nor, nor);
+		dist2 = squared_distance(root->co, co, nor);
 		if (dist2 <= range2)
 			add_in_range(&foundstack, found++, &totfoundstack, root->index, dist2, root->co);
 
@@ -488,7 +484,7 @@ int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3],
 				stack[cur++] = node->right;
 		}
 		else {
-			dist2 = squared_distance(node->co, co, node->nor, nor);
+			dist2 = squared_distance(node->co, co, nor);
 			if (dist2 <= range2)
 				add_in_range(&foundstack, found++, &totfoundstack, node->index, dist2, node->co);