blender
/
blender
136
404
Fork 586
Code Issues 6.2k Pull Requests 762 Projects 19 Wiki Activity

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.
This commit is contained in:
Jacques Lucke 2019-03-05 16:20:43 +01:00
parent 8887988b15
commit 301bcf771d
Notes: blender-bot 2023-02-14 03:29:34 +01:00 
Referenced by commit f79930989d, Revert "Fix T62210: endless loop in kd tree lookup"
Referenced by issue #62247, Remove Double Vertices crashes Blender
Referenced by issue #62231, Add Sphere, adjust Rings, Crash
Referenced by issue #62210, Python Kd-tree hangs  blender on code below (2.8 win10)
1 changed files with 7 additions and 2 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

9
source/blender/blenlib/intern/BLI_kdtree.c
View File

@ -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;