[Bf-blender-cvs] [301bcf771de] master: Fix T62210: endless loop in kd tree lookup

[Jacques Lucke]

Commit: 301bcf771dec827138412ca6e7a25e2269eb5e9e
Author: Jacques Lucke
Date:   Tue Mar 5 16:20:43 2019 +0100
Branches: master
https://developer.blender.org/rB301bcf771dec827138412ca6e7a25e2269eb5e9e

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.

===================================================================

M	source/blender/blenlib/intern/BLI_kdtree.c

===================================================================

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;