Cleanup: use BLI_kdtree_3d prefix

Use prefix now there isn't only the 3d version.

10 files changed, 77 insertions, 77 deletions

diff --git a/source/blender/blenkernel/BKE_object.h b/source/blender/blenkernel/BKE_object.h
index 9e6366f9992..4a1470797ba 100644
--- a/source/blender/blenkernel/BKE_object.h
+++ b/source/blender/blenkernel/BKE_object.h
@@ -339,7 +339,7 @@ struct LinkNode *BKE_object_relational_superset(
 struct LinkNode *BKE_object_groups(struct Main *bmain, struct Scene *scene, struct Object *ob);
 void             BKE_object_groups_clear(struct Main *bmain, struct Scene *scene, struct Object *object);
 
-struct KDTree *BKE_object_as_kdtree(struct Object *ob, int *r_tot);
+struct KDTree_3d *BKE_object_as_kdtree(struct Object *ob, int *r_tot);
 
 bool BKE_object_modifier_use_time(struct Object *ob, struct ModifierData *md);
 
diff --git a/source/blender/blenkernel/BKE_particle.h b/source/blender/blenkernel/BKE_particle.h
index 56f64829eb1..b2b7f9f9cb5 100644
--- a/source/blender/blenkernel/BKE_particle.h
+++ b/source/blender/blenkernel/BKE_particle.h
@@ -45,7 +45,7 @@ struct CustomData_MeshMasks;
 struct Depsgraph;
 struct Depsgraph;
 struct EdgeHash;
-struct KDTree;
+struct KDTree_3d;
 struct LatticeDeformData;
 struct LinkNode;
 struct MCol;
@@ -136,7 +136,7 @@ typedef struct ParticleThreadContext {
 	struct Material *ma;
 
 	/* distribution */
-	struct KDTree *tree;
+	struct KDTree_3d *tree;
 
 	struct ParticleSeam *seams;
 	int totseam;
diff --git a/source/blender/blenkernel/BKE_pointcache.h b/source/blender/blenkernel/BKE_pointcache.h
index 6f0145a493d..9cfc43b2e5b 100644
--- a/source/blender/blenkernel/BKE_pointcache.h
+++ b/source/blender/blenkernel/BKE_pointcache.h
@@ -226,7 +226,7 @@ typedef struct PTCacheUndo {
 
 	/* particles stuff */
 	struct ParticleData *particles;
-	struct KDTree *emitter_field;
+	struct KDTree_3d *emitter_field;
 	float *emitter_cosnos;
 	int psys_flag;
 
@@ -257,7 +257,7 @@ typedef struct PTCacheEdit {
 	struct ParticleSystem *psys_eval;
 	struct ParticleSystemModifierData *psmd;
 	struct ParticleSystemModifierData *psmd_eval;
-	struct KDTree *emitter_field;
+	struct KDTree_3d *emitter_field;
 	float *emitter_cosnos; /* localspace face centers and normals (average of its verts), from the derived mesh */
 	int *mirror_cache;
 
diff --git a/source/blender/blenkernel/intern/boids.c b/source/blender/blenkernel/intern/boids.c
index 8b71aa0fb69..c092b2c7e79 100644
--- a/source/blender/blenkernel/intern/boids.c
+++ b/source/blender/blenkernel/intern/boids.c
@@ -206,7 +206,7 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues *
 {
 	const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT);
 	BoidRuleAvoidCollision *acbr = (BoidRuleAvoidCollision*) rule;
-	KDTreeNearest *ptn = NULL;
+	KDTreeNearest_3d *ptn = NULL;
 	ParticleTarget *pt;
 	BoidParticle *bpa = pa->boid;
 	ColliderCache *coll;
@@ -274,7 +274,7 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues *
 
 	//check boids in own system
 	if (acbr->options & BRULE_ACOLL_WITH_BOIDS) {
-		neighbors = BLI_kdtree_range_search_with_len_squared_cb(
+		neighbors = BLI_kdtree_3d_range_search_with_len_squared_cb(
 		        bbd->sim->psys->tree, pa->prev_state.co, &ptn, acbr->look_ahead * len_v3(pa->prev_state.vel),
 		        len_squared_v3v3_with_normal_bias, pa->prev_state.ave);
 		if (neighbors > 1) for (n=1; n<neighbors; n++) {
@@ -323,7 +323,7 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues *
 
 		if (epsys) {
 			BLI_assert(epsys->tree != NULL);
-			neighbors = BLI_kdtree_range_search_with_len_squared_cb(
+			neighbors = BLI_kdtree_3d_range_search_with_len_squared_cb(
 			        epsys->tree, pa->prev_state.co, &ptn, acbr->look_ahead * len_v3(pa->prev_state.vel),
 			        len_squared_v3v3_with_normal_bias, pa->prev_state.ave);
 
@@ -377,11 +377,11 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues *
 }
 static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues *val, ParticleData *pa)
 {
-	KDTreeNearest *ptn = NULL;
+	KDTreeNearest_3d *ptn = NULL;
 	ParticleTarget *pt;
 	float len = 2.0f * val->personal_space * pa->size + 1.0f;
 	float vec[3] = {0.0f, 0.0f, 0.0f};
-	int neighbors = BLI_kdtree_range_search(
+	int neighbors = BLI_kdtree_3d_range_search(
 	            bbd->sim->psys->tree, pa->prev_state.co,
 	            &ptn, 2.0f * val->personal_space * pa->size);
 	int ret = 0;
@@ -401,7 +401,7 @@ static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues
 		ParticleSystem *epsys = psys_get_target_system(bbd->sim->ob, pt);
 
 		if (epsys) {
-			neighbors = BLI_kdtree_range_search(
+			neighbors = BLI_kdtree_3d_range_search(
 			        epsys->tree, pa->prev_state.co,
 			        &ptn, 2.0f * val->personal_space * pa->size);
 
@@ -421,9 +421,9 @@ static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues
 }
 static int rule_flock(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues *UNUSED(val), ParticleData *pa)
 {
-	KDTreeNearest ptn[11];
+	KDTreeNearest_3d ptn[11];
 	float vec[3] = {0.0f, 0.0f, 0.0f}, loc[3] = {0.0f, 0.0f, 0.0f};
-	int neighbors = BLI_kdtree_find_nearest_n_with_len_squared_cb(
+	int neighbors = BLI_kdtree_3d_find_nearest_n_with_len_squared_cb(
 	        bbd->sim->psys->tree, pa->state.co, ptn, ARRAY_SIZE(ptn),
 	        len_squared_v3v3_with_normal_bias, pa->prev_state.ave);
 	int n;
@@ -639,7 +639,7 @@ static int rule_average_speed(BoidRule *rule, BoidBrainData *bbd, BoidValues *va
 static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, ParticleData *pa)
 {
 	BoidRuleFight *fbr = (BoidRuleFight*)rule;
-	KDTreeNearest *ptn = NULL;
+	KDTreeNearest_3d *ptn = NULL;
 	ParticleTarget *pt;
 	ParticleData *epars;
 	ParticleData *enemy_pa = NULL;
@@ -652,7 +652,7 @@ static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, Parti
 	int n, ret = 0;
 
 	/* calculate own group strength */
-	int neighbors = BLI_kdtree_range_search(
+	int neighbors = BLI_kdtree_3d_range_search(
 	            bbd->sim->psys->tree, pa->prev_state.co,
 	            &ptn, fbr->distance);
 	for (n=0; n<neighbors; n++) {
@@ -670,7 +670,7 @@ static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, Parti
 		if (epsys) {
 			epars = epsys->particles;
 
-			neighbors = BLI_kdtree_range_search(
+			neighbors = BLI_kdtree_3d_range_search(
 			        epsys->tree, pa->prev_state.co,
 			        &ptn, fbr->distance);
 
diff --git a/source/blender/blenkernel/intern/dynamicpaint.c b/source/blender/blenkernel/intern/dynamicpaint.c
index eeaf0710a5f..0419a5ac348 100644
--- a/source/blender/blenkernel/intern/dynamicpaint.c
+++ b/source/blender/blenkernel/intern/dynamicpaint.c
@@ -4237,7 +4237,7 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex(
 	const float timescale = data->timescale;
 	const int c_index = data->c_index;
 
-	KDTree *tree = data->treeData;
+	KDTree_3d *tree = data->treeData;
 
 	const float solidradius = data->solidradius;
 	const float smooth = brush->particle_smooth * surface->radius_scale;
@@ -4255,11 +4255,11 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex(
 	 * It's enough to just find the nearest one.
 	 */
 	{
-		KDTreeNearest nearest;
+		KDTreeNearest_3d nearest;
 		float smooth_range, part_solidradius;
 
 		/* Find nearest particle and get distance to it */
-		BLI_kdtree_find_nearest(tree, bData->realCoord[bData->s_pos[index]].v, &nearest);
+		BLI_kdtree_3d_find_nearest(tree, bData->realCoord[bData->s_pos[index]].v, &nearest);
 		/* if outside maximum range, no other particle can influence either */
 		if (nearest.dist > range)
 			return;
@@ -4291,7 +4291,7 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex(
 		 * If we use per particle radius, we have to sample all particles
 		 * within max radius range
 		 */
-		KDTreeNearest *nearest;
+		KDTreeNearest_3d *nearest;
 
 		float smooth_range = smooth * (1.0f - strength), dist;
 		/* calculate max range that can have particles with higher influence than the nearest one */
@@ -4299,7 +4299,7 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex(
 		/* Make gcc happy! */
 		dist = max_range;
 
-		const int particles = BLI_kdtree_range_search(
+		const int particles = BLI_kdtree_3d_range_search(
 		                          tree, bData->realCoord[bData->s_pos[index]].v, &nearest, max_range);
 
 		/* Find particle that produces highest influence */
@@ -4397,7 +4397,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface,
 	PaintBakeData *bData = sData->bData;
 	VolumeGrid *grid = bData->grid;
 
-	KDTree *tree;
+	KDTree_3d *tree;
 	int particlesAdded = 0;
 	int invalidParticles = 0;
 	int p = 0;
@@ -4416,7 +4416,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface,
 	/*
 	 * Build a kd-tree to optimize distance search
 	 */
-	tree = BLI_kdtree_new(psys->totpart);
+	tree = BLI_kdtree_3d_new(psys->totpart);
 
 	/* loop through particles and insert valid ones to the tree */
 	p = 0;
@@ -4440,7 +4440,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface,
 		if (!boundIntersectPoint(&grid->grid_bounds, pa->state.co, range))
 			continue;
 
-		BLI_kdtree_insert(tree, p, pa->state.co);
+		BLI_kdtree_3d_insert(tree, p, pa->state.co);
 
 		/* calc particle system bounds */
 		boundInsert(&part_bb, pa->state.co);
@@ -4452,7 +4452,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface,
 
 	/* If no suitable particles were found, exit */
 	if (particlesAdded < 1) {
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 		return 1;
 	}
 
@@ -4465,7 +4465,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface,
 		int total_cells = grid->dim[0] * grid->dim[1] * grid->dim[2];
 
 		/* balance tree */
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 
 		/* loop through space partitioning grid */
 		for (c_index = 0; c_index < total_cells; c_index++) {
@@ -4493,7 +4493,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface,
 		}
 	}
 	BLI_threaded_malloc_end();
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 
 	return 1;
 }
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index 66b888c84f2..4f8be846b37 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -3968,7 +3968,7 @@ void BKE_object_groups_clear(Main *bmain, Scene *scene, Object *ob)
 }
 
 /**
- * Return a KDTree from the deformed object (in worldspace)
+ * Return a KDTree_3d from the deformed object (in worldspace)
  *
  * \note Only mesh objects currently support deforming, others are TODO.
  *
@@ -3976,9 +3976,9 @@ void BKE_object_groups_clear(Main *bmain, Scene *scene, Object *ob)
  * \param r_tot:
  * \return The kdtree or NULL if it can't be created.
  */
-KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
+KDTree_3d *BKE_object_as_kdtree(Object *ob, int *r_tot)
 {
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 	unsigned int tot = 0;
 
 	switch (ob->type) {
@@ -3996,14 +3996,14 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
 
 				/* tree over-allocs in case where some verts have ORIGINDEX_NONE */
 				tot = 0;
-				tree = BLI_kdtree_new(totvert);
+				tree = BLI_kdtree_3d_new(totvert);
 
 				/* we don't how how many verts from the DM we can use */
 				for (i = 0; i < totvert; i++) {
 					if (index[i] != ORIGINDEX_NONE) {
 						float co[3];
 						mul_v3_m4v3(co, ob->obmat, mvert[i].co);
-						BLI_kdtree_insert(tree, index[i], co);
+						BLI_kdtree_3d_insert(tree, index[i], co);
 						tot++;
 					}
 				}
@@ -4012,16 +4012,16 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
 				MVert *mvert = me->mvert;
 
 				tot = me->totvert;
-				tree = BLI_kdtree_new(tot);
+				tree = BLI_kdtree_3d_new(tot);
 
 				for (i = 0; i < tot; i++) {
 					float co[3];
 					mul_v3_m4v3(co, ob->obmat, mvert[i].co);
-					BLI_kdtree_insert(tree, i, co);
+					BLI_kdtree_3d_insert(tree, i, co);
 				}
 			}
 
-			BLI_kdtree_balance(tree);
+			BLI_kdtree_3d_balance(tree);
 			break;
 		}
 		case OB_CURVE:
@@ -4034,7 +4034,7 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
 			Nurb *nu;
 
 			tot = BKE_nurbList_verts_count_without_handles(&cu->nurb);
-			tree = BLI_kdtree_new(tot);
+			tree = BLI_kdtree_3d_new(tot);
 			i = 0;
 
 			nu = cu->nurb.first;
@@ -4047,7 +4047,7 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
 					while (a--) {
 						float co[3];
 						mul_v3_m4v3(co, ob->obmat, bezt->vec[1]);
-						BLI_kdtree_insert(tree, i++, co);
+						BLI_kdtree_3d_insert(tree, i++, co);
 						bezt++;
 					}
 				}
@@ -4059,14 +4059,14 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
 					while (a--) {
 						float co[3];
 						mul_v3_m4v3(co, ob->obmat, bp->vec);
-						BLI_kdtree_insert(tree, i++, co);
+						BLI_kdtree_3d_insert(tree, i++, co);
 						bp++;
 					}
 				}
 				nu = nu->next;
 			}
 
-			BLI_kdtree_balance(tree);
+			BLI_kdtree_3d_balance(tree);
 			break;
 		}
 		case OB_LATTICE:
@@ -4077,16 +4077,16 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
 			unsigned int i;
 
 			tot = lt->pntsu * lt->pntsv * lt->pntsw;
-			tree = BLI_kdtree_new(tot);
+			tree = BLI_kdtree_3d_new(tot);
 			i = 0;
 
 			for (bp = lt->def; i < tot; bp++) {
 				float co[3];
 				mul_v3_m4v3(co, ob->obmat, bp->vec);
-				BLI_kdtree_insert(tree, i++, co);
+				BLI_kdtree_3d_insert(tree, i++, co);
 			}
 
-			BLI_kdtree_balance(tree);
+			BLI_kdtree_3d_balance(tree);
 			break;
 		}
 	}
diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index bdf0b239917..4abc57ca1c9 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -650,7 +650,7 @@ void psys_free(Object *ob, ParticleSystem *psys)
 		BLI_freelistN(&psys->targets);
 
 		BLI_bvhtree_free(psys->bvhtree);
-		BLI_kdtree_free(psys->tree);
+		BLI_kdtree_3d_free(psys->tree);
 
 		if (psys->fluid_springs)
 			MEM_freeN(psys->fluid_springs);
@@ -1920,7 +1920,7 @@ void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params
 {
 	ParticleSystem *psys = sim->psys;
 	ParticleSettings *part = sim->psys->part;
-	KDTree *tree;
+	KDTree_3d *tree;
 	ChildParticle *cpa;
 	ParticleTexture ptex;
 	int p, totparent, totchild = sim->psys->totchild;
@@ -1936,7 +1936,7 @@ void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params
 		totparent = sim->psys->totpart;
 	}
 
-	tree = BLI_kdtree_new(totparent);
+	tree = BLI_kdtree_3d_new(totparent);
 
 	for (p = 0, cpa = sim->psys->child; p < totparent; p++, cpa++) {
 		psys_particle_on_emitter(sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco);
@@ -1945,18 +1945,18 @@ void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params
 		get_cpa_texture(sim->psmd->mesh_final, psys, part, psys->particles + cpa->pa[0], p, cpa->num, cpa->fuv, orco, &ptex, PAMAP_DENS | PAMAP_CHILD, psys->cfra);
 
 		if (ptex.exist >= psys_frand(psys, p + 24)) {
-			BLI_kdtree_insert(tree, p, orco);
+			BLI_kdtree_3d_insert(tree, p, orco);
 		}
 	}
 
-	BLI_kdtree_balance(tree);
+	BLI_kdtree_3d_balance(tree);
 
 	for (; p < totchild; p++, cpa++) {
 		psys_particle_on_emitter(sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco);
-		cpa->parent = BLI_kdtree_find_nearest(tree, orco, NULL);
+		cpa->parent = BLI_kdtree_3d_find_nearest(tree, orco, NULL);
 	}
 
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 }
 
 static bool psys_thread_context_init_path(
diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c
index 4485afb09de..bbf8fece5ff 100644
--- a/source/blender/blenkernel/intern/particle_distribute.c
+++ b/source/blender/blenkernel/intern/particle_distribute.c
@@ -464,12 +464,12 @@ static void distribute_from_verts_exec(ParticleTask *thread, ParticleData *pa, i
 
 #if ONLY_WORKING_WITH_PA_VERTS
 	if (ctx->tree) {
-		KDTreeNearest ptn[3];
+		KDTreeNearest_3d ptn[3];
 		int w, maxw;
 
 		psys_particle_on_dm(ctx->mesh,from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co1,0,0,0,orco1,0);
 		BKE_mesh_orco_verts_transform(ob->data, &orco1, 1, 1);
-		maxw = BLI_kdtree_find_nearest_n(ctx->tree,orco1,ptn,3);
+		maxw = BLI_kdtree_3d_find_nearest_n(ctx->tree,orco1,ptn,3);
 
 		for (w=0; w<maxw; w++) {
 			pa->verts[w]=ptn->num;
@@ -654,7 +654,7 @@ static void distribute_children_exec(ParticleTask *thread, ChildParticle *cpa, i
 	cpa->num = ctx->index[p];
 
 	if (ctx->tree) {
-		KDTreeNearest ptn[10];
+		KDTreeNearest_3d ptn[10];
 		int w,maxw;//, do_seams;
 		float maxd /*, mind,dd */, totw= 0.0f;
 		int parent[10];
@@ -662,7 +662,7 @@ static void distribute_children_exec(ParticleTask *thread, ChildParticle *cpa, i
 
 		psys_particle_on_dm(mesh,cfrom,cpa->num,DMCACHE_ISCHILD,cpa->fuv,cpa->foffset,co1,nor1,NULL,NULL,orco1);
 		BKE_mesh_orco_verts_transform(ob->data, &orco1, 1, 1);
-		maxw = BLI_kdtree_find_nearest_n(ctx->tree,orco1,ptn,3);
+		maxw = BLI_kdtree_3d_find_nearest_n(ctx->tree,orco1,ptn,3);
 
 		maxd=ptn[maxw-1].dist;
 		/* mind=ptn[0].dist; */ /* UNUSED */
@@ -809,7 +809,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti
 	ParticleData *pa=0, *tpars= 0;
 	ParticleSettings *part;
 	ParticleSeam *seams= 0;
-	KDTree *tree=0;
+	KDTree_3d *tree=0;
 	Mesh *mesh = NULL;
 	float *jit= NULL;
 	int i, p=0;
@@ -883,15 +883,15 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti
 
 		children=1;
 
-		tree=BLI_kdtree_new(totpart);
+		tree=BLI_kdtree_3d_new(totpart);
 
 		for (p=0,pa=psys->particles; p<totpart; p++,pa++) {
 			psys_particle_on_dm(mesh,part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co,nor,0,0,orco);
 			BKE_mesh_orco_verts_transform(ob->data, &orco, 1, 1);
-			BLI_kdtree_insert(tree, p, orco);
+			BLI_kdtree_3d_insert(tree, p, orco);
 		}
 
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 
 		totpart = psys_get_tot_child(scene, psys, use_render_params);
 		cfrom = from = PART_FROM_FACE;
@@ -917,7 +917,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti
 			float (*orcodata)[3] = CustomData_get_layer(&mesh->vdata, CD_ORCO);
 			int totvert = mesh->totvert;
 
-			tree=BLI_kdtree_new(totvert);
+			tree=BLI_kdtree_3d_new(totvert);
 
 			for (p=0; p<totvert; p++) {
 				if (orcodata) {
@@ -926,10 +926,10 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti
 				}
 				else
 					copy_v3_v3(co,mv[p].co);
-				BLI_kdtree_insert(tree, p, co);
+				BLI_kdtree_3d_insert(tree, p, co);
 			}
 
-			BLI_kdtree_balance(tree);
+			BLI_kdtree_3d_balance(tree);
 		}
 	}
 
@@ -944,7 +944,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti
 
 		if (mesh != final_mesh) BKE_id_free(NULL, mesh);
 
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 		BLI_rng_free(rng);
 
 		return 0;
diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c
index 2975eaaf5fc..28a2e6e94cb 100644
--- a/source/blender/blenkernel/intern/particle_system.c
+++ b/source/blender/blenkernel/intern/particle_system.c
@@ -512,7 +512,7 @@ void psys_thread_context_free(ParticleThreadContext *ctx)
 	if (ctx->index) MEM_freeN(ctx->index);
 	if (ctx->seams) MEM_freeN(ctx->seams);
 	//if (ctx->vertpart) MEM_freeN(ctx->vertpart);
-	BLI_kdtree_free(ctx->tree);
+	BLI_kdtree_3d_free(ctx->tree);
 
 	if (ctx->clumpcurve != NULL) {
 		curvemapping_free(ctx->clumpcurve);
@@ -1280,18 +1280,18 @@ void psys_update_particle_tree(ParticleSystem *psys, float cfra)
 				totpart++;
 			}
 
-			BLI_kdtree_free(psys->tree);
-			psys->tree = BLI_kdtree_new(psys->totpart);
+			BLI_kdtree_3d_free(psys->tree);
+			psys->tree = BLI_kdtree_3d_new(psys->totpart);
 
 			LOOP_SHOWN_PARTICLES {
 				if (pa->alive == PARS_ALIVE) {
 					if (pa->state.time == cfra)
-						BLI_kdtree_insert(psys->tree, p, pa->prev_state.co);
+						BLI_kdtree_3d_insert(psys->tree, p, pa->prev_state.co);
 					else
-						BLI_kdtree_insert(psys->tree, p, pa->state.co);
+						BLI_kdtree_3d_insert(psys->tree, p, pa->state.co);
 				}
 			}
-			BLI_kdtree_balance(psys->tree);
+			BLI_kdtree_3d_balance(psys->tree);
 
 			psys->tree_frame = cfra;
 		}
diff --git a/source/blender/blenkernel/intern/smoke.c b/source/blender/blenkernel/intern/smoke.c
index 4b9dd9ac6e3..82acc272c6b 100644
--- a/source/blender/blenkernel/intern/smoke.c
+++ b/source/blender/blenkernel/intern/smoke.c
@@ -1200,7 +1200,7 @@ static void em_combineMaps(EmissionMap *output, EmissionMap *em2, int hires_mult
 
 typedef struct EmitFromParticlesData {
 	SmokeFlowSettings *sfs;
-	KDTree *tree;
+	KDTree_3d *tree;
 	int hires_multiplier;
 
 	EmissionMap *em;
@@ -1237,9 +1237,9 @@ static void emit_from_particles_task_cb(
 				const float ray_start[3] = {((float)lx) + 0.5f, ((float)ly) + 0.5f, ((float)lz) + 0.5f};
 
 				/* find particle distance from the kdtree */
-				KDTreeNearest nearest;
+				KDTreeNearest_3d nearest;
 				const float range = data->solid + data->smooth;
-				BLI_kdtree_find_nearest(data->tree, ray_start, &nearest);
+				BLI_kdtree_3d_find_nearest(data->tree, ray_start, &nearest);
 
 				if (nearest.dist < range) {
 					em->influence[index] = (nearest.dist < data->solid) ?
@@ -1263,9 +1263,9 @@ static void emit_from_particles_task_cb(
 				const float ray_start[3] = {lx + 0.5f * data->hr, ly + 0.5f * data->hr, lz + 0.5f * data->hr};
 
 				/* find particle distance from the kdtree */
-				KDTreeNearest nearest;
+				KDTreeNearest_3d nearest;
 				const float range = data->solid + data->hr_smooth;
-				BLI_kdtree_find_nearest(data->tree, ray_start, &nearest);
+				BLI_kdtree_3d_find_nearest(data->tree, ray_start, &nearest);
 
 				if (nearest.dist < range) {
 					em->influence_high[index] = (nearest.dist < data->solid) ?
@@ -1295,7 +1295,7 @@ static void emit_from_particles(
 		const float solid = sfs->particle_size * 0.5f;
 		const float smooth = 0.5f; /* add 0.5 cells of linear falloff to reduce aliasing */
 		int hires_multiplier = 1;
-		KDTree *tree = NULL;
+		KDTree_3d *tree = NULL;
 
 		sim.depsgraph = depsgraph;
 		sim.scene = scene;
@@ -1325,7 +1325,7 @@ static void emit_from_particles(
 
 		/* setup particle radius emission if enabled */
 		if (sfs->flags & MOD_SMOKE_FLOW_USE_PART_SIZE) {
-			tree = BLI_kdtree_new(psys->totpart + psys->totchild);
+			tree = BLI_kdtree_3d_new(psys->totpart + psys->totchild);
 
 			/* check need for high resolution map */
 			if ((sds->flags & MOD_SMOKE_HIGHRES) && (sds->highres_sampling == SM_HRES_FULLSAMPLE)) {
@@ -1365,7 +1365,7 @@ static void emit_from_particles(
 			mul_mat3_m4_v3(sds->imat, &particle_vel[valid_particles * 3]);
 
 			if (sfs->flags & MOD_SMOKE_FLOW_USE_PART_SIZE) {
-				BLI_kdtree_insert(tree, valid_particles, pos);
+				BLI_kdtree_3d_insert(tree, valid_particles, pos);
 			}
 
 			/* calculate emission map bounds */
@@ -1423,7 +1423,7 @@ static void emit_from_particles(
 				res[i] = em->res[i] * hires_multiplier;
 			}
 
-			BLI_kdtree_balance(tree);
+			BLI_kdtree_3d_balance(tree);
 
 			EmitFromParticlesData data = {
 				.sfs = sfs, .tree = tree, .hires_multiplier = hires_multiplier, .hr = hr,
@@ -1441,7 +1441,7 @@ static void emit_from_particles(
 		}
 
 		if (sfs->flags & MOD_SMOKE_FLOW_USE_PART_SIZE) {
-			BLI_kdtree_free(tree);
+			BLI_kdtree_3d_free(tree);
 		}
 
 		/* free data */