blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 746 Projects 19 Wiki Activity

Fix T62210: endless loop in kd tree lookup 

Reset nodes after the first balance call.
This commit is contained in:
Campbell Barton 2019-03-06 14:46:58 +11:00
parent f79930989d
commit ecd086ac32
Notes: blender-bot 2023-02-14 04:46:12 +01:00 
Referenced by issue #62254, Hair object mode not rendering in right view of sterescopic mode
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 11 additions and 1 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

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

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