BLI_kdtree.c File Reference

#include "MEM_guardedalloc.h"
#include "BLI_math.h"
#include "BLI_kdtree.h"

Go to the source code of this file.

Classes
struct	KDTreeNode
struct	KDTree
Defines
#define	SWAP(type, a, b)   { type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; }
Typedefs
typedef struct KDTreeNode	KDTreeNode
Functions
KDTree *	BLI_kdtree_new (int maxsize)
void	BLI_kdtree_free (KDTree *tree)
void	BLI_kdtree_insert (KDTree *tree, int index, float *co, float *nor)
static KDTreeNode *	kdtree_balance (KDTreeNode *nodes, int totnode, int axis)
void	BLI_kdtree_balance (KDTree *tree)
static float	squared_distance (float *v2, float *v1, float *n1, float *n2)
int	BLI_kdtree_find_nearest (KDTree *tree, float *co, float *nor, KDTreeNearest *nearest)
static void	add_nearest (KDTreeNearest *ptn, int *found, int n, int index, float dist, float *co)
int	BLI_kdtree_find_n_nearest (KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest)
static int	range_compare (const void *a, const void *b)
static void	add_in_range (KDTreeNearest **ptn, int found, int *totfoundstack, int index, float dist, float *co)
int	BLI_kdtree_range_search (KDTree *tree, float range, float *co, float *nor, KDTreeNearest **nearest)

---

Detailed Description

Definition in file BLI_kdtree.c.

---

Define Documentation

#define SWAP	(		type,
			a,
			b
	)		{ type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; }

Definition at line 41 of file BLI_kdtree.c.

Referenced by kdtree_balance().

---

Typedef Documentation

typedef struct KDTreeNode KDTreeNode

---

Function Documentation

static void add_in_range	(	KDTreeNearest **	ptn,
		int	found,
		int *	totfoundstack,
		int	index,
		float	dist,
		float *	co
	)		[static]

Definition at line 355 of file BLI_kdtree.c.

References KDTreeNearest::co, copy_v3_v3(), KDTreeNearest::dist, KDTreeNearest::index, MEM_callocN(), MEM_freeN(), and sqrt().

Referenced by BLI_kdtree_range_search().

static void add_nearest	(	KDTreeNearest *	ptn,
		int *	found,
		int	n,
		int	index,
		float	dist,
		float *	co
	)		[static]

Definition at line 240 of file BLI_kdtree.c.

References copy_v3_v3(), KDTreeNearest::dist, i, and KDTreeNearest::index.

Referenced by BLI_kdtree_find_n_nearest().

void BLI_kdtree_balance

(

KDTree *

tree

)

Definition at line 130 of file BLI_kdtree.c.

References kdtree_balance(), KDTree::nodes, KDTree::root, and KDTree::totnode.

Referenced by brush_add(), createFacepa(), distribute_threads_init_data(), dynamicPaint_paintParticles(), PE_update_mirror_cache(), psys_find_parents(), psys_update_particle_tree(), recalc_emitter_field(), and remove_doubles_exec().

int BLI_kdtree_find_n_nearest	(	KDTree *	tree,
		int	n,
		float *	co,
		float *	nor,
		KDTreeNearest *	nearest
	)

Definition at line 259 of file BLI_kdtree.c.

References add_nearest(), KDTreeNode::co, KDTreeNode::d, i, KDTreeNode::index, KDTreeNode::left, MEM_callocN(), MEM_freeN(), KDTreeNode::nor, NULL, KDTreeNode::right, MakeCursor::root, KDTree::root, sqrt(), squared_distance(), and stack.

Referenced by brush_add(), distribute_threads_exec(), remove_doubles_exec(), and rule_flock().

int BLI_kdtree_find_nearest	(	KDTree *	tree,
		float *	co,
		float *	nor,
		KDTreeNearest *	nearest
	)

Definition at line 153 of file BLI_kdtree.c.

References KDTreeNearest::co, KDTreeNode::co, copy_v3_v3(), KDTreeNode::d, KDTreeNearest::dist, KDTreeNode::index, KDTreeNearest::index, KDTreeNode::left, MEM_callocN(), MEM_freeN(), KDTreeNode::nor, KDTreeNode::right, KDTree::root, MakeCursor::root, sqrt(), squared_distance(), and stack.

Referenced by brush_puff(), createFacepa(), dynamicPaint_paintParticles(), pe_deflect_emitter(), PE_update_mirror_cache(), and psys_find_parents().

void BLI_kdtree_free

(

KDTree *

tree

)

Definition at line 68 of file BLI_kdtree.c.

References MEM_freeN(), and KDTree::nodes.

Referenced by brush_add(), createFacepa(), dynamicPaint_paintParticles(), PE_free_ptcache_edit(), PE_update_mirror_cache(), psys_find_parents(), psys_free(), psys_threads_free(), psys_update_particle_tree(), recalc_emitter_field(), and remove_doubles_exec().

void BLI_kdtree_insert	(	KDTree *	tree,
		int	index,
		float *	co,
		float *	nor
	)

Definition at line 76 of file BLI_kdtree.c.

References KDTreeNode::co, copy_v3_v3(), KDTreeNode::index, KDTree::nodes, KDTreeNode::nor, and KDTree::totnode.

Referenced by brush_add(), createFacepa(), distribute_threads_init_data(), dynamicPaint_paintParticles(), PE_update_mirror_cache(), psys_find_parents(), psys_update_particle_tree(), recalc_emitter_field(), and remove_doubles_exec().

KDTree* BLI_kdtree_new

(

int

maxsize

)

Definition at line 57 of file BLI_kdtree.c.

References MEM_callocN(), KDTree::nodes, and KDTree::totnode.

Referenced by brush_add(), createFacepa(), distribute_threads_init_data(), dynamicPaint_paintParticles(), PE_update_mirror_cache(), psys_find_parents(), psys_update_particle_tree(), recalc_emitter_field(), and remove_doubles_exec().

int BLI_kdtree_range_search	(	KDTree *	tree,
		float	range,
		float *	co,
		float *	nor,
		KDTreeNearest **	nearest
	)

Definition at line 374 of file BLI_kdtree.c.

References add_in_range(), KDTreeNode::co, KDTreeNode::d, KDTreeNode::index, KDTreeNode::left, MEM_callocN(), MEM_freeN(), KDTreeNode::nor, NULL, range_compare(), KDTreeNode::right, MakeCursor::root, KDTree::root, squared_distance(), and stack.

Referenced by dynamicPaint_paintParticles(), rule_avoid_collision(), rule_fight(), and rule_separate().

static KDTreeNode* kdtree_balance	(	KDTreeNode *	nodes,
		int	totnode,
		int	axis
	)		[static]

Definition at line 85 of file BLI_kdtree.c.

References co, KDTreeNode::co, KDTreeNode::d, i, KDTreeNode::left, left(), nodes, NULL, KDTreeNode::right, and SWAP.

Referenced by BLI_kdtree_balance().

static int range_compare	(	const void *	a,
		const void *	b
	)		[static]

Definition at line 343 of file BLI_kdtree.c.

References KDTreeNearest::dist.

Referenced by BLI_kdtree_range_search().

static float squared_distance	(	float *	v2,
		float *	v1,
		float *	n1,
		float *	n2
	)		[static]

Definition at line 135 of file BLI_kdtree.c.

References simple_enum_gen::d.

Referenced by BLI_kdtree_find_n_nearest(), BLI_kdtree_find_nearest(), and BLI_kdtree_range_search().