diff options
author | Jacques Lucke <mail@jlucke.com> | 2019-03-05 18:20:43 +0300 |
---|---|---|
committer | Jacques Lucke <mail@jlucke.com> | 2019-03-05 18:23:58 +0300 |
commit | 301bcf771dec827138412ca6e7a25e2269eb5e9e (patch) | |
tree | 3d978bc3be308e4f8bd73f79fc14e5effd80033d /source/blender/blenlib | |
parent | 8887988b1543a794ba5d0c72db95284936969c0c (diff) |
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.
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 9 |
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; |