diff options
| author | Campbell Barton <ideasman42@gmail.com> | 2019-03-06 06:46:58 +0300 |
|---|---|---|
| committer | Campbell Barton <ideasman42@gmail.com> | 2019-03-06 06:53:06 +0300 |
| commit | ecd086ac32241c883689f3522cabc324a8e0064c (patch) | |
| tree | 48724a26a873b12cbbb19afbba1505f74102010d /source/blender/blenlib/intern | |
| parent | f79930989d4f0bd04a1d524571cd25ac214020fb (diff) | |
Fix T62210: endless loop in kd tree lookup
Reset nodes after the first balance call.
Diffstat (limited to 'source/blender/blenlib/intern')
| -rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 12 |
1 files changed, 11 insertions, 1 deletions
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 |