BLI_kdtree.h File Reference

A kd-tree for nearest neighbour search. More...

Go to the source code of this file.

Classes
struct	KDTreeNearest
Typedefs
typedef struct KDTree	KDTree
typedef struct KDTreeNearest	KDTreeNearest
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)
void	BLI_kdtree_balance (KDTree *tree)
int	BLI_kdtree_find_nearest (KDTree *tree, float *co, float *nor, KDTreeNearest *nearest)
int	BLI_kdtree_find_n_nearest (KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest)
int	BLI_kdtree_range_search (KDTree *tree, float range, float *co, float *nor, KDTreeNearest **nearest)

---

Detailed Description

A kd-tree for nearest neighbour search.

Author:

Janne Karhu

Brecht van Lommel

Definition in file BLI_kdtree.h.

---

Typedef Documentation

typedef struct KDTree KDTree

Definition at line 40 of file BLI_kdtree.h.

typedef struct KDTreeNearest KDTreeNearest

---

Function Documentation

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().