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

[Campbell Barton]

Commit: ecd086ac32241c883689f3522cabc324a8e0064c
Author: Campbell Barton
Date:   Wed Mar 6 14:46:58 2019 +1100
Branches: master
https://developer.blender.org/rBecd086ac32241c883689f3522cabc324a8e0064c

Fix T62210: endless loop in kd tree lookup

Reset nodes after the first balance call.

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

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..ce06324ebca 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -54,6 +54,9 @@ struct KDTree {
 
 #define KD_NODE_UNSET ((uint)-1)
 
+/** When set we know all values are unbalanced, otherwise clear them when re-balancing: see T62210. */
+#define KD_NODE_ROOT_IS_INIT ((uint)-2)
+
 /**
  * Creates or free a kdtree
  */
@@ -64,7 +67,7 @@ KDTree *BLI_kdtree_new(uint maxsize)
 	tree = MEM_mallocN(sizeof(KDTree), "KDTree");
 	tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode");
 	tree->totnode = 0;
-	tree->root = KD_NODE_UNSET;
+	tree->root = KD_NODE_ROOT_IS_INIT;
 
 #ifdef DEBUG
 	tree->is_balanced = false;
@@ -156,6 +159,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++) {
+			tree->nodes[i].left = KD_NODE_UNSET;
+			tree->nodes[i].right = KD_NODE_UNSET;
+		}
+	}
+
 	tree->root = kdtree_balance(tree->nodes, tree->totnode, 0, 0);
 
 #ifdef DEBUG