Differential D4457 Diff 14017 source/blender/blenlib/intern/BLI_kdtree.c

Changeset View

Standalone View

source/blender/blenlib/intern/BLI_kdtree.c

Show First 20 Lines • Show All 48 Lines • ▼ Show 20 Lines
};		};

#define KD_STACK_INIT 100 /* initial size for array (on the stack) */		#define KD_STACK_INIT 100 /* initial size for array (on the stack) */
#define KD_NEAR_ALLOC_INC 100 /* alloc increment for collecting nearest */		#define KD_NEAR_ALLOC_INC 100 /* alloc increment for collecting nearest */
#define KD_FOUND_ALLOC_INC 50 /* alloc increment for collecting nearest */		#define KD_FOUND_ALLOC_INC 50 /* alloc increment for collecting nearest */

#define KD_NODE_UNSET ((uint)-1)		#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		* Creates or free a kdtree
*/		*/
KDTree *BLI_kdtree_new(uint maxsize)		KDTree *BLI_kdtree_new(uint maxsize)
{		{
KDTree *tree;		KDTree *tree;

tree = MEM_mallocN(sizeof(KDTree), "KDTree");		tree = MEM_mallocN(sizeof(KDTree), "KDTree");
tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode");		tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode");
tree->totnode = 0;		tree->totnode = 0;
tree->root = KD_NODE_UNSET;		tree->root = KD_NODE_ROOT_IS_INIT;

#ifdef DEBUG		#ifdef DEBUG
tree->is_balanced = false;		tree->is_balanced = false;
tree->maxsize = maxsize;		tree->maxsize = maxsize;
#endif		#endif

return tree;		return tree;
}		}
Show All 31 Lines
}		}

static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uint ofs)		static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uint ofs)
{		{
KDTreeNode *node;		KDTreeNode *node;
float co;		float co;
uint left, right, median, i, j;		uint left, right, median, i, j;

if (totnode <= 0) {		if (totnode <= 0)
return KD_NODE_UNSET;		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;		return 0 + ofs;
}

/* quicksort style sorting around median */		/* quicksort style sorting around median */
left = 0;		left = 0;
right = totnode - 1;		right = totnode - 1;
median = totnode / 2;		median = totnode / 2;

while (right > left) {		while (right > left) {
co = nodes[right].co[axis];		co = nodes[right].co[axis];
Show All 24 Lines	static uint kdtree_balance(KDTreeNode *nodes, uint totnode, uint axis, const uint ofs)
node->left = kdtree_balance(nodes, median, axis, ofs);		node->left = kdtree_balance(nodes, median, axis, ofs);
node->right = kdtree_balance(nodes + median + 1, (totnode - (median + 1)), axis, (median + 1) + ofs);		node->right = kdtree_balance(nodes + median + 1, (totnode - (median + 1)), axis, (median + 1) + ofs);

return median + ofs;		return median + ofs;
}		}

void BLI_kdtree_balance(KDTree *tree)		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);		tree->root = kdtree_balance(tree->nodes, tree->totnode, 0, 0);

#ifdef DEBUG		#ifdef DEBUG
tree->is_balanced = true;		tree->is_balanced = true;
#endif		#endif
}		}

static float squared_distance(const float v2[3], const float v1[3], const float n2[3])		static float squared_distance(const float v2[3], const float v1[3], const float n2[3])
▲ Show 20 Lines • Show All 633 Lines • Show Last 20 Lines