Fix T62210: endless loop in kd tree lookup

The problem was that `balance` expected that all node children
are set to `KD_NODE_UNSET` by default.
However, this might not be the case when `balance` is called
more than once.

The balance function might change the order of nodes even
when no new point has been inserted.

1 files changed, 7 insertions, 2 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c
index 4f12bd0a93f..20e30ce669c 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -112,10 +112,15 @@ static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uin
 	float co;
 	uint left, right, median, i, j;
 
-	if (totnode <= 0)
+	if (totnode <= 0) {
 		return KD_NODE_UNSET;
-	else if (totnode == 1)
+	}
+	else if (totnode == 1) {
+		node = nodes + ofs;
+		node->left = KD_NODE_UNSET;
+		node->right = KD_NODE_UNSET;
 		return 0 + ofs;
+	}
 
 	/* quicksort style sorting around median */
 	left = 0;