Cleanup: use BLI_kdtree_3d prefix

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

10 files changed, 112 insertions, 112 deletions

diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c
index 25470f7344a..ba9a42a6c2b 100644
--- a/source/blender/editors/curve/editcurve_select.c
+++ b/source/blender/editors/curve/editcurve_select.c
@@ -1362,7 +1362,7 @@ static void nurb_bpoint_direction_worldspace_get(Object *ob, Nurb *nu, BPoint *b
 	normalize_v3(r_dir);
 }
 
-static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, KDTree *r_tree)
+static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, KDTree_3d *r_tree)
 {
 	float tree_entry[3] = {0.0f, 0.0f, 0.0f};
 
@@ -1393,7 +1393,7 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K
 						break;
 					}
 				}
-				BLI_kdtree_insert(r_tree, tree_index++, tree_entry);
+				BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry);
 			}
 		}
 	}
@@ -1423,7 +1423,7 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K
 						break;
 					}
 				}
-				BLI_kdtree_insert(r_tree, tree_index++, tree_entry);
+				BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry);
 			}
 		}
 	}
@@ -1431,7 +1431,7 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K
 
 static bool curve_nurb_select_similar_type(
         Object *ob, Nurb *nu, const int type,
-        const KDTree *tree, const float thresh, const int compare)
+        const KDTree_3d *tree, const float thresh, const int compare)
 {
 	const float thresh_cos = cosf(thresh * (float)M_PI_2);
 	bool changed = false;
@@ -1465,8 +1465,8 @@ static bool curve_nurb_select_similar_type(
 					{
 						float dir[3];
 						nurb_bezt_direction_worldspace_get(ob, nu, bezt, dir);
-						KDTreeNearest nearest;
-						if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) {
+						KDTreeNearest_3d nearest;
+						if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) {
 							float orient = angle_normalized_v3v3(dir, nearest.co);
 							float delta = thresh_cos - fabsf(cosf(orient));
 							if (ED_select_similar_compare_float(delta, thresh, compare)) {
@@ -1513,8 +1513,8 @@ static bool curve_nurb_select_similar_type(
 					{
 						float dir[3];
 						nurb_bpoint_direction_worldspace_get(ob, nu, bp, dir);
-						KDTreeNearest nearest;
-						if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) {
+						KDTreeNearest_3d nearest;
+						if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) {
 							float orient = angle_normalized_v3v3(dir, nearest.co);
 							float delta = fabsf(cosf(orient)) - thresh_cos;
 							if (ED_select_similar_compare_float(delta, thresh, compare)) {
@@ -1560,14 +1560,14 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
 		return OPERATOR_CANCELLED;
 	}
 
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 	short type_ref = 0;
 
 	switch (optype) {
 		case SIMCURHAND_RADIUS:
 		case SIMCURHAND_WEIGHT:
 		case SIMCURHAND_DIRECTION:
-			tree = BLI_kdtree_new(tot_nurbs_selected_all);
+			tree = BLI_kdtree_3d_new(tot_nurbs_selected_all);
 			break;
 	}
 
@@ -1598,7 +1598,7 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
 	}
 
 	if (tree != NULL) {
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 	}
 
 	/* Select control points with desired type. */
@@ -1635,7 +1635,7 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
 
 	MEM_freeN(objects);
 	if (tree != NULL) {
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 	}
 	return OPERATOR_FINISHED;
 
diff --git a/source/blender/editors/include/ED_select_utils.h b/source/blender/editors/include/ED_select_utils.h
index a7b9ac7e6c9..87045be9932 100644
--- a/source/blender/editors/include/ED_select_utils.h
+++ b/source/blender/editors/include/ED_select_utils.h
@@ -21,7 +21,7 @@
 #ifndef __ED_SELECT_UTILS_H__
 #define __ED_SELECT_UTILS_H__
 
-struct KDTree;
+struct KDTree_3d;
 
 enum {
 	SEL_TOGGLE		 = 0,
@@ -55,7 +55,7 @@ int ED_select_op_action(const eSelectOp sel_op, const bool is_select, const bool
 int ED_select_op_action_deselected(const eSelectOp sel_op, const bool is_select, const bool is_inside);
 
 int ED_select_similar_compare_float(const float delta, const float thresh, const int compare);
-bool ED_select_similar_compare_float_tree(const struct KDTree *tree, const float length, const float thresh, const int compare);
+bool ED_select_similar_compare_float_tree(const struct KDTree_3d *tree, const float length, const float thresh, const int compare);
 
 eSelectOp ED_select_op_modal(const eSelectOp sel_op, const bool is_first);
 
diff --git a/source/blender/editors/mesh/editmesh_select_similar.c b/source/blender/editors/mesh/editmesh_select_similar.c
index 299db63eca3..59c34578777 100644
--- a/source/blender/editors/mesh/editmesh_select_similar.c
+++ b/source/blender/editors/mesh/editmesh_select_similar.c
@@ -183,7 +183,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
 		return OPERATOR_CANCELLED;
 	}
 
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 	KDTree_4d *tree_plane = NULL;
 	GSet *gset = NULL;
 	GSet **gset_array = NULL;
@@ -193,7 +193,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
 		case SIMFACE_AREA:
 		case SIMFACE_PERIMETER:
 		case SIMFACE_NORMAL:
-			tree = BLI_kdtree_new(tot_faces_selected_all);
+			tree = BLI_kdtree_3d_new(tot_faces_selected_all);
 			break;
 		case SIMFACE_COPLANAR:
 			tree_plane = BLI_kdtree_4d_new(tot_faces_selected_all);
@@ -273,14 +273,14 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
 					{
 						float area = BM_face_calc_area_with_mat3(face, ob_m3);
 						float dummy[3] = {area, 0.0f, 0.0f};
-						BLI_kdtree_insert(tree, tree_index++, dummy);
+						BLI_kdtree_3d_insert(tree, tree_index++, dummy);
 						break;
 					}
 					case SIMFACE_PERIMETER:
 					{
 						float perimeter = BM_face_calc_perimeter_with_mat3(face, ob_m3);
 						float dummy[3] = {perimeter, 0.0f, 0.0f};
-						BLI_kdtree_insert(tree, tree_index++, dummy);
+						BLI_kdtree_3d_insert(tree, tree_index++, dummy);
 						break;
 					}
 					case SIMFACE_NORMAL:
@@ -290,7 +290,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
 						mul_transposed_mat3_m4_v3(ob->imat, normal);
 						normalize_v3(normal);
 
-						BLI_kdtree_insert(tree, tree_index++, normal);
+						BLI_kdtree_3d_insert(tree, tree_index++, normal);
 						break;
 					}
 					case SIMFACE_COPLANAR:
@@ -337,7 +337,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
 	BLI_assert((type != SIMFACE_FREESTYLE) || (face_data_value != SIMFACE_DATA_NONE));
 
 	if (tree != NULL) {
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 	}
 	if (tree_plane != NULL) {
 		BLI_kdtree_4d_balance(tree_plane);
@@ -446,8 +446,8 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
 
 						/* We are treating the normals as coordinates, the "nearest" one will
 						 * also be the one closest to the angle. */
-						KDTreeNearest nearest;
-						if (BLI_kdtree_find_nearest(tree, normal, &nearest) != -1) {
+						KDTreeNearest_3d nearest;
+						if (BLI_kdtree_3d_find_nearest(tree, normal, &nearest) != -1) {
 							if (angle_normalized_v3v3(normal, nearest.co) <= thresh_radians) {
 								select = true;
 							}
@@ -550,7 +550,7 @@ face_select_all:
 	}
 
 	MEM_freeN(objects);
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 	BLI_kdtree_4d_free(tree_plane);
 	if (gset != NULL) {
 		BLI_gset_free(gset, NULL);
@@ -671,7 +671,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 		return OPERATOR_CANCELLED;
 	}
 
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 	GSet *gset = NULL;
 	int edge_data_value = SIMEDGE_DATA_NONE;
 
@@ -681,7 +681,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 		case SIMEDGE_FACE_ANGLE:
 		case SIMEDGE_LENGTH:
 		case SIMEDGE_DIR:
-			tree = BLI_kdtree_new(tot_edges_selected_all);
+			tree = BLI_kdtree_3d_new(tot_edges_selected_all);
 			break;
 		case SIMEDGE_FACE:
 			gset = BLI_gset_ptr_new("Select similar edge: face");
@@ -721,7 +721,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 			{
 				if (!CustomData_has_layer(&bm->edata, custom_data_type)) {
 					float dummy[3] = {0.0f, 0.0f, 0.0f};
-					BLI_kdtree_insert(tree, tree_index++, dummy);
+					BLI_kdtree_3d_insert(tree, tree_index++, dummy);
 					continue;
 				}
 				break;
@@ -745,14 +745,14 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 					{
 						float dir[3];
 						edge_pos_direction_worldspace_get(ob, edge, dir);
-						BLI_kdtree_insert(tree, tree_index++, dir);
+						BLI_kdtree_3d_insert(tree, tree_index++, dir);
 						break;
 					}
 					case SIMEDGE_LENGTH:
 					{
 						float length = edge_length_squared_worldspace_get(ob, edge);
 						float dummy[3] = {length, 0.0f, 0.0f};
-						BLI_kdtree_insert(tree, tree_index++, dummy);
+						BLI_kdtree_3d_insert(tree, tree_index++, dummy);
 						break;
 					}
 					case SIMEDGE_FACE_ANGLE:
@@ -760,7 +760,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 						if (BM_edge_face_count_at_most(edge, 2) == 2) {
 							float angle = BM_edge_calc_face_angle_with_imat3(edge, ob_m3_inv);
 							float dummy[3] = {angle, 0.0f, 0.0f};
-							BLI_kdtree_insert(tree, tree_index++, dummy);
+							BLI_kdtree_3d_insert(tree, tree_index++, dummy);
 						}
 						break;
 					}
@@ -794,7 +794,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 					{
 						const float *value = CustomData_bmesh_get(&bm->edata, edge->head.data, custom_data_type);
 						float dummy[3] = {*value, 0.0f, 0.0f};
-						BLI_kdtree_insert(tree, tree_index++, dummy);
+						BLI_kdtree_3d_insert(tree, tree_index++, dummy);
 						break;
 					}
 				}
@@ -805,7 +805,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 	BLI_assert((type != SIMEDGE_FREESTYLE) || (edge_data_value != SIMEDGE_DATA_NONE));
 
 	if (tree != NULL) {
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 	}
 
 	for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
@@ -873,8 +873,8 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op)
 
 						/* We are treating the direction as coordinates, the "nearest" one will
 						 * also be the one closest to the intended direction. */
-						KDTreeNearest nearest;
-						if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) {
+						KDTreeNearest_3d nearest;
+						if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) {
 							if (angle_normalized_v3v3(dir, nearest.co) <= thresh_radians) {
 								select = true;
 							}
@@ -987,7 +987,7 @@ edge_select_all:
 	}
 
 	MEM_freeN(objects);
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 	if (gset != NULL) {
 		BLI_gset_free(gset, NULL);
 	}
@@ -1026,12 +1026,12 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op)
 		return OPERATOR_CANCELLED;
 	}
 
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 	GSet *gset = NULL;
 
 	switch (type) {
 		case SIMVERT_NORMAL:
-			tree = BLI_kdtree_new(tot_verts_selected_all);
+			tree = BLI_kdtree_3d_new(tot_verts_selected_all);
 			break;
 		case SIMVERT_EDGE:
 		case SIMVERT_FACE:
@@ -1081,7 +1081,7 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op)
 						mul_transposed_mat3_m4_v3(ob->imat, normal);
 						normalize_v3(normal);
 
-						BLI_kdtree_insert(tree, normal_tree_index++, normal);
+						BLI_kdtree_3d_insert(tree, normal_tree_index++, normal);
 						break;
 					}
 					case SIMVERT_VGROUP:
@@ -1123,7 +1123,7 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op)
 
 	/* Remove duplicated entries. */
 	if (tree != NULL) {
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 	}
 
 	/* Run .the BM operators. */
@@ -1204,8 +1204,8 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op)
 
 						/* We are treating the normals as coordinates, the "nearest" one will
 						 * also be the one closest to the angle. */
-						KDTreeNearest nearest;
-						if (BLI_kdtree_find_nearest(tree, normal, &nearest) != -1) {
+						KDTreeNearest_3d nearest;
+						if (BLI_kdtree_3d_find_nearest(tree, normal, &nearest) != -1) {
 							if (angle_normalized_v3v3(normal, nearest.co) <= thresh_radians) {
 								select = true;
 							}
@@ -1243,7 +1243,7 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op)
 	}
 
 	MEM_freeN(objects);
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 	if (gset != NULL) {
 		BLI_gset_free(gset, NULL);
 	}
diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c
index ed6ab38e5ab..68a2f382278 100644
--- a/source/blender/editors/mesh/editmesh_utils.c
+++ b/source/blender/editors/mesh/editmesh_utils.c
@@ -1006,7 +1006,7 @@ void EDBM_verts_mirror_cache_begin_ex(
 	const float maxdist_sq = SQUARE(maxdist);
 
 	/* one or the other is used depending if topo is enabled */
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 	MirrTopoStore_t mesh_topo_store = {NULL, -1, -1, -1};
 
 	BM_mesh_elem_table_ensure(bm, BM_VERT);
@@ -1032,11 +1032,11 @@ void EDBM_verts_mirror_cache_begin_ex(
 		ED_mesh_mirrtopo_init(me, NULL, &mesh_topo_store, true);
 	}
 	else {
-		tree = BLI_kdtree_new(bm->totvert);
+		tree = BLI_kdtree_3d_new(bm->totvert);
 		BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
-			BLI_kdtree_insert(tree, i, v->co);
+			BLI_kdtree_3d_insert(tree, i, v->co);
 		}
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 	}
 
 #define VERT_INTPTR(_v, _i) r_index ? &r_index[_i] : BM_ELEM_CD_GET_VOID_P(_v, cd_vmirr_offset);
@@ -1062,7 +1062,7 @@ void EDBM_verts_mirror_cache_begin_ex(
 				co[axis] *= -1.0f;
 
 				v_mirr = NULL;
-				i_mirr = BLI_kdtree_find_nearest(tree, co, NULL);
+				i_mirr = BLI_kdtree_3d_find_nearest(tree, co, NULL);
 				if (i_mirr != -1) {
 					BMVert *v_test = BM_vert_at_index(bm, i_mirr);
 					if (len_squared_v3v3(co, v_test->co) < maxdist_sq) {
@@ -1090,7 +1090,7 @@ void EDBM_verts_mirror_cache_begin_ex(
 		ED_mesh_mirrtopo_free(&mesh_topo_store);
 	}
 	else {
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 	}
 }
 
diff --git a/source/blender/editors/mesh/mesh_mirror.c b/source/blender/editors/mesh/mesh_mirror.c
index 3d49d874503..a1859bf70b0 100644
--- a/source/blender/editors/mesh/mesh_mirror.c
+++ b/source/blender/editors/mesh/mesh_mirror.c
@@ -51,8 +51,8 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons
 			ED_mesh_mirror_spatial_table(ob, em, me_eval, NULL, 's');
 
 		if (MirrKdStore.tree) {
-			KDTreeNearest nearest;
-			const int i = BLI_kdtree_find_nearest(MirrKdStore.tree, co, &nearest);
+			KDTreeNearest_3d nearest;
+			const int i = BLI_kdtree_3d_find_nearest(MirrKdStore.tree, co, &nearest);
 
 			if (i != -1) {
 				if (nearest.dist < KD_THRESH) {
@@ -70,7 +70,7 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons
 		if (MirrKdStore.tree) /* happens when entering this call without ending it */
 			ED_mesh_mirror_spatial_table(ob, em, me_eval, co, 'e');
 
-		MirrKdStore.tree = BLI_kdtree_new(totvert);
+		MirrKdStore.tree = BLI_kdtree_3d_new(totvert);
 
 		if (use_em) {
 			BMVert *eve;
@@ -81,7 +81,7 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons
 			BM_mesh_elem_table_ensure(em->bm, BM_VERT);
 
 			BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
-				BLI_kdtree_insert(MirrKdStore.tree, i, eve->co);
+				BLI_kdtree_3d_insert(MirrKdStore.tree, i, eve->co);
 			}
 		}
 		else {
@@ -89,15 +89,15 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons
 			int i;
 
 			for (i = 0; i < totvert; i++, mvert++) {
-				BLI_kdtree_insert(MirrKdStore.tree, i, mvert->co);
+				BLI_kdtree_3d_insert(MirrKdStore.tree, i, mvert->co);
 			}
 		}
 
-		BLI_kdtree_balance(MirrKdStore.tree);
+		BLI_kdtree_3d_balance(MirrKdStore.tree);
 	}
 	else if (mode == 'e') { /* end table */
 		if (MirrKdStore.tree) {
-			BLI_kdtree_free(MirrKdStore.tree);
+			BLI_kdtree_3d_free(MirrKdStore.tree);
 			MirrKdStore.tree = NULL;
 		}
 	}
diff --git a/source/blender/editors/metaball/mball_edit.c b/source/blender/editors/metaball/mball_edit.c
index 2af78261b87..d8e5b2cba89 100644
--- a/source/blender/editors/metaball/mball_edit.c
+++ b/source/blender/editors/metaball/mball_edit.c
@@ -194,7 +194,7 @@ static const EnumPropertyItem prop_similar_types[] = {
 	{0, NULL, 0, NULL, NULL},
 };
 
-static void mball_select_similar_type_get(Object *obedit, MetaBall *mb, int  type, KDTree *r_tree)
+static void mball_select_similar_type_get(Object *obedit, MetaBall *mb, int  type, KDTree_3d *r_tree)
 {
 	float tree_entry[3] = {0.0f, 0.0f, 0.0f};
 	MetaElem *ml;
@@ -231,12 +231,12 @@ static void mball_select_similar_type_get(Object *obedit, MetaBall *mb, int  typ
 					break;
 				}
 			}
-			BLI_kdtree_insert(r_tree, tree_index++, tree_entry);
+			BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry);
 		}
 	}
 }
 
-static bool mball_select_similar_type(Object *obedit, MetaBall *mb, int type, const KDTree *tree, const float thresh)
+static bool mball_select_similar_type(Object *obedit, MetaBall *mb, int type, const KDTree_3d *tree, const float thresh)
 {
 	MetaElem *ml;
 	bool changed = false;
@@ -277,8 +277,8 @@ static bool mball_select_similar_type(Object *obedit, MetaBall *mb, int type, co
 
 				float thresh_cos = cosf(thresh * (float)M_PI_2);
 
-				KDTreeNearest nearest;
-				if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) {
+				KDTreeNearest_3d nearest;
+				if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) {
 					float orient = angle_normalized_v3v3(dir, nearest.co);
 					/* Map to 0-1 to compare orientation. */
 					float delta = thresh_cos - fabsf(cosf(orient));
@@ -311,10 +311,10 @@ static int mball_select_similar_exec(bContext *C, wmOperator *op)
 	tot_mball_selected_all = BKE_mball_select_count_multi(objects, objects_len);
 
 	short type_ref = 0;
-	KDTree *tree = NULL;
+	KDTree_3d *tree = NULL;
 
 	if (type != SIMMBALL_TYPE) {
-		tree = BLI_kdtree_new(tot_mball_selected_all);
+		tree = BLI_kdtree_3d_new(tot_mball_selected_all);
 	}
 
 	/* Get type of selected MetaBall */
@@ -346,7 +346,7 @@ static int mball_select_similar_exec(bContext *C, wmOperator *op)
 	}
 
 	if (tree != NULL) {
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 	}
 	/* Select MetaBalls with desired type. */
 	for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
@@ -385,7 +385,7 @@ static int mball_select_similar_exec(bContext *C, wmOperator *op)
 
 	MEM_freeN(objects);
 	if (tree != NULL) {
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 	}
 	return OPERATOR_FINISHED;
 }
diff --git a/source/blender/editors/object/object_relations.c b/source/blender/editors/object/object_relations.c
index 6495575b76a..81925f42113 100644
--- a/source/blender/editors/object/object_relations.c
+++ b/source/blender/editors/object/object_relations.c
@@ -837,14 +837,14 @@ bool ED_object_parent_set(ReportList *reports, const bContext *C, Scene *scene,
 
 
 
-static void parent_set_vert_find(KDTree *tree, Object *child, int vert_par[3], bool is_tri)
+static void parent_set_vert_find(KDTree_3d *tree, Object *child, int vert_par[3], bool is_tri)
 {
 	const float *co_find = child->obmat[3];
 	if (is_tri) {
-		KDTreeNearest nearest[3];
+		KDTreeNearest_3d nearest[3];
 		int tot;
 
-		tot = BLI_kdtree_find_nearest_n(tree, co_find, nearest, 3);
+		tot = BLI_kdtree_3d_find_nearest_n(tree, co_find, nearest, 3);
 		BLI_assert(tot == 3);
 		UNUSED_VARS(tot);
 
@@ -855,7 +855,7 @@ static void parent_set_vert_find(KDTree *tree, Object *child, int vert_par[3], b
 		BLI_assert(min_iii(UNPACK3(vert_par)) >= 0);
 	}
 	else {
-		vert_par[0] = BLI_kdtree_find_nearest(tree, co_find, NULL);
+		vert_par[0] = BLI_kdtree_3d_find_nearest(tree, co_find, NULL);
 		BLI_assert(vert_par[0] >= 0);
 		vert_par[1] = 0;
 		vert_par[2] = 0;
@@ -876,7 +876,7 @@ static int parent_set_exec(bContext *C, wmOperator *op)
 	const bool is_vert_par = ELEM(partype, PAR_VERTEX, PAR_VERTEX_TRI);
 	const bool is_tri = partype == PAR_VERTEX_TRI;
 	int tree_tot;
-	struct KDTree *tree = NULL;
+	struct KDTree_3d *tree = NULL;
 	int vert_par[3] = {0, 0, 0};
 	const int *vert_par_p = is_vert_par ? vert_par : NULL;
 
@@ -908,7 +908,7 @@ static int parent_set_exec(bContext *C, wmOperator *op)
 	}
 
 	if (is_vert_par) {
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 	}
 
 	if (!ok)
diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c
index 78b677677bc..e4f17ca68f0 100644
--- a/source/blender/editors/physics/particle_edit.c
+++ b/source/blender/editors/physics/particle_edit.c
@@ -150,7 +150,7 @@ void PE_free_ptcache_edit(PTCacheEdit *edit)
 	}
 
 	if (edit->emitter_field) {
-		BLI_kdtree_free(edit->emitter_field);
+		BLI_kdtree_3d_free(edit->emitter_field);
 		edit->emitter_field = 0;
 	}
 
@@ -883,8 +883,8 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
 {
 	PTCacheEdit *edit;
 	ParticleSystemModifierData *psmd_eval;
-	KDTree *tree;
-	KDTreeNearest nearest;
+	KDTree_3d *tree;
+	KDTreeNearest_3d nearest;
 	HairKey *key;
 	PARTICLE_P;
 	float mat[4][4], co[3];
@@ -897,7 +897,7 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
 	if (!psmd_eval->mesh_final)
 		return;
 
-	tree = BLI_kdtree_new(totpart);
+	tree = BLI_kdtree_3d_new(totpart);
 
 	/* insert particles into kd tree */
 	LOOP_PARTICLES {
@@ -905,10 +905,10 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
 		psys_mat_hair_to_orco(ob, psmd_eval->mesh_final, psys->part->from, pa, mat);
 		copy_v3_v3(co, key->co);
 		mul_m4_v3(mat, co);
-		BLI_kdtree_insert(tree, p, co);
+		BLI_kdtree_3d_insert(tree, p, co);
 	}
 
-	BLI_kdtree_balance(tree);
+	BLI_kdtree_3d_balance(tree);
 
 	/* lookup particles and set in mirror cache */
 	if (!edit->mirror_cache)
@@ -921,7 +921,7 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
 		mul_m4_v3(mat, co);
 		co[0] = -co[0];
 
-		index = BLI_kdtree_find_nearest(tree, co, &nearest);
+		index = BLI_kdtree_3d_find_nearest(tree, co, &nearest);
 
 		/* this needs a custom threshold still, duplicated for editmode mirror */
 		if (index != -1 && index != p && (nearest.dist <= 0.0002f))
@@ -939,7 +939,7 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
 		}
 	}
 
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 }
 
 static void PE_mirror_particle(Object *ob, Mesh *mesh, ParticleSystem *psys, ParticleData *pa, ParticleData *mpa)
@@ -1107,7 +1107,7 @@ static void deflect_emitter_iter(
 			dist_1st *= dist * emitterdist;
 		}
 		else {
-			index = BLI_kdtree_find_nearest(edit->emitter_field, key->co, NULL);
+			index = BLI_kdtree_3d_find_nearest(edit->emitter_field, key->co, NULL);
 
 			vec = edit->emitter_cosnos + index * 6;
 			nor = vec + 3;
@@ -1329,14 +1329,14 @@ void recalc_emitter_field(Depsgraph *UNUSED(depsgraph), Object *UNUSED(ob), Part
 	if (edit->emitter_cosnos)
 		MEM_freeN(edit->emitter_cosnos);
 
-	BLI_kdtree_free(edit->emitter_field);
+	BLI_kdtree_3d_free(edit->emitter_field);
 
 	totface = mesh->totface;
 	/*totvert=dm->getNumVerts(dm);*/ /*UNUSED*/
 
 	edit->emitter_cosnos = MEM_callocN(totface * 6 * sizeof(float), "emitter cosnos");
 
-	edit->emitter_field = BLI_kdtree_new(totface);
+	edit->emitter_field = BLI_kdtree_3d_new(totface);
 
 	vec = edit->emitter_cosnos;
 	nor = vec + 3;
@@ -1370,10 +1370,10 @@ void recalc_emitter_field(Depsgraph *UNUSED(depsgraph), Object *UNUSED(ob), Part
 
 		normalize_v3(nor);
 
-		BLI_kdtree_insert(edit->emitter_field, i, vec);
+		BLI_kdtree_3d_insert(edit->emitter_field, i, vec);
 	}
 
-	BLI_kdtree_balance(edit->emitter_field);
+	BLI_kdtree_3d_balance(edit->emitter_field);
 }
 
 static void PE_update_selection(Depsgraph *depsgraph, Scene *scene, Object *ob, int useflag)
@@ -2803,8 +2803,8 @@ static int remove_doubles_exec(bContext *C, wmOperator *op)
 	PTCacheEdit *edit = PE_get_current(scene, ob);
 	ParticleSystem *psys = edit->psys;
 	ParticleSystemModifierData *psmd_eval;
-	KDTree *tree;
-	KDTreeNearest nearest[10];
+	KDTree_3d *tree;
+	KDTreeNearest_3d nearest[10];
 	POINT_P;
 	float mat[4][4], co[3], threshold = RNA_float_get(op->ptr, "threshold");
 	int n, totn, removed, totremoved;
@@ -2819,17 +2819,17 @@ static int remove_doubles_exec(bContext *C, wmOperator *op)
 	do {
 		removed = 0;
 
-		tree = BLI_kdtree_new(psys->totpart);
+		tree = BLI_kdtree_3d_new(psys->totpart);
 
 		/* insert particles into kd tree */
 		LOOP_SELECTED_POINTS {
 			psys_mat_hair_to_object(ob, psmd_eval->mesh_final, psys->part->from, psys->particles + p, mat);
 			copy_v3_v3(co, point->keys->co);
 			mul_m4_v3(mat, co);
-			BLI_kdtree_insert(tree, p, co);
+			BLI_kdtree_3d_insert(tree, p, co);
 		}
 
-		BLI_kdtree_balance(tree);
+		BLI_kdtree_3d_balance(tree);
 
 		/* tag particles to be removed */
 		LOOP_SELECTED_POINTS {
@@ -2837,7 +2837,7 @@ static int remove_doubles_exec(bContext *C, wmOperator *op)
 			copy_v3_v3(co, point->keys->co);
 			mul_m4_v3(mat, co);
 
-			totn = BLI_kdtree_find_nearest_n(tree, co, nearest, 10);
+			totn = BLI_kdtree_3d_find_nearest_n(tree, co, nearest, 10);
 
 			for (n = 0; n < totn; n++) {
 				/* this needs a custom threshold still */
@@ -2850,7 +2850,7 @@ static int remove_doubles_exec(bContext *C, wmOperator *op)
 			}
 		}
 
-		BLI_kdtree_free(tree);
+		BLI_kdtree_3d_free(tree);
 
 		/* remove tagged particles - don't do mirror here! */
 		remove_tagged_particles(ob, psys, 0);
@@ -3431,7 +3431,7 @@ static void brush_puff(PEData *data, int point_index, float mouse_distance)
 			 * ob->imat is set before calling */
 			mul_v3_m4v3(kco, data->ob->imat, co);
 
-			point_index = BLI_kdtree_find_nearest(edit->emitter_field, kco, NULL);
+			point_index = BLI_kdtree_3d_find_nearest(edit->emitter_field, kco, NULL);
 			if (point_index == -1) return;
 
 			copy_v3_v3(co_root, co);
@@ -3518,7 +3518,7 @@ static void brush_puff(PEData *data, int point_index, float mouse_distance)
 						 * ob->imat is set before calling */
 						mul_v3_m4v3(kco, data->ob->imat, oco);
 
-						point_index = BLI_kdtree_find_nearest(edit->emitter_field, kco, NULL);
+						point_index = BLI_kdtree_3d_find_nearest(edit->emitter_field, kco, NULL);
 						if (point_index != -1) {
 							copy_v3_v3(onor, &edit->emitter_cosnos[point_index * 6 + 3]);
 							mul_mat3_m4_v3(data->ob->obmat, onor); /* normal into worldspace */
@@ -3963,7 +3963,7 @@ static int brush_add(const bContext *C, PEData *data, short number)
 	if (n) {
 		int newtotpart = totpart + n;
 		float hairmat[4][4], cur_co[3];
-		KDTree *tree = 0;
+		KDTree_3d *tree = 0;
 		ParticleData *pa, *new_pars = MEM_callocN(newtotpart * sizeof(ParticleData), "ParticleData new");
 		PTCacheEditPoint *point, *new_points = MEM_callocN(newtotpart * sizeof(PTCacheEditPoint), "PTCacheEditPoint array new");
 		PTCacheEditKey *key;
@@ -3987,14 +3987,14 @@ static int brush_add(const bContext *C, PEData *data, short number)
 
 		/* create tree for interpolation */
 		if (pset->flag & PE_INTERPOLATE_ADDED && psys->totpart) {
-			tree = BLI_kdtree_new(psys->totpart);
+			tree = BLI_kdtree_3d_new(psys->totpart);
 
 			for (i = 0, pa = psys->particles; i < totpart; i++, pa++) {
 				psys_particle_on_dm(psmd_eval->mesh_final, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, cur_co, 0, 0, 0, 0);
-				BLI_kdtree_insert(tree, i, cur_co);
+				BLI_kdtree_3d_insert(tree, i, cur_co);
 			}
 
-			BLI_kdtree_balance(tree);
+			BLI_kdtree_3d_balance(tree);
 		}
 
 		edit->totpoint = psys->totpart = newtotpart;
@@ -4030,12 +4030,12 @@ static int brush_add(const bContext *C, PEData *data, short number)
 				ParticleData *ppa;
 				HairKey *thkey;
 				ParticleKey key3[3];
-				KDTreeNearest ptn[3];
+				KDTreeNearest_3d ptn[3];
 				int w, maxw;
 				float maxd, totw = 0.0, weight[3];
 
 				psys_particle_on_dm(psmd_eval->mesh_final, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co1, 0, 0, 0, 0);
-				maxw = BLI_kdtree_find_nearest_n(tree, co1, ptn, 3);
+				maxw = BLI_kdtree_3d_find_nearest_n(tree, co1, ptn, 3);
 
 				maxd = ptn[maxw - 1].dist;
 
@@ -4106,7 +4106,7 @@ static int brush_add(const bContext *C, PEData *data, short number)
 		}
 
 		if (tree)
-			BLI_kdtree_free(tree);
+			BLI_kdtree_3d_free(tree);
 	}
 
 	MEM_freeN(add_pars);
diff --git a/source/blender/editors/util/select_utils.c b/source/blender/editors/util/select_utils.c
index 80b103e0c4b..b2784aca7fa 100644
--- a/source/blender/editors/util/select_utils.c
+++ b/source/blender/editors/util/select_utils.c
@@ -97,7 +97,7 @@ int ED_select_similar_compare_float(const float delta, const float thresh, const
 	}
 }
 
-bool ED_select_similar_compare_float_tree(const KDTree *tree, const float length, const float thresh, const int compare)
+bool ED_select_similar_compare_float_tree(const KDTree_3d *tree, const float length, const float thresh, const int compare)
 {
 	/* Length of the edge we want to compare against. */
 	float nearest_edge_length;
@@ -123,9 +123,9 @@ bool ED_select_similar_compare_float_tree(const KDTree *tree, const float length
 			return false;
 	}
 
-	KDTreeNearest nearest;
+	KDTreeNearest_3d nearest;
 	float dummy[3] = {nearest_edge_length, 0.0f, 0.0f};
-	if (BLI_kdtree_find_nearest(tree, dummy, &nearest) != -1) {
+	if (BLI_kdtree_3d_find_nearest(tree, dummy, &nearest) != -1) {
 		float delta = length - nearest.co[0];
 		return ED_select_similar_compare_float(delta, thresh, compare);
 	}
diff --git a/source/blender/editors/uvedit/uvedit_ops.c b/source/blender/editors/uvedit/uvedit_ops.c
index f771feeff2c..108481b9dae 100644
--- a/source/blender/editors/uvedit/uvedit_ops.c
+++ b/source/blender/editors/uvedit/uvedit_ops.c
@@ -1853,7 +1853,7 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op)
 		uv_maxlen += em->bm->totloop;
 	}
 
-	KDTree *tree = BLI_kdtree_new(uv_maxlen);
+	KDTree_3d *tree = BLI_kdtree_3d_new(uv_maxlen);
 
 	int *duplicates = NULL;
 	BLI_array_declare(duplicates);
@@ -1886,7 +1886,7 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op)
 				if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
 					MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
 					copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f);
-					BLI_kdtree_insert(tree, mloopuv_count, uvw);
+					BLI_kdtree_3d_insert(tree, mloopuv_count, uvw);
 					BLI_array_append(duplicates, -1);
 					BLI_array_append(mloopuv_arr, luv);
 					mloopuv_count++;
@@ -1897,8 +1897,8 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op)
 		ob_mloopuv_max_idx[ob_index] = mloopuv_count - 1;
 	}
 
-	BLI_kdtree_balance(tree);
-	int found_duplicates = BLI_kdtree_calc_duplicates_fast(tree, threshold, false, duplicates);
+	BLI_kdtree_3d_balance(tree);
+	int found_duplicates = BLI_kdtree_3d_calc_duplicates_fast(tree, threshold, false, duplicates);
 
 	if (found_duplicates > 0) {
 		/* Calculate average uv for duplicates. */
@@ -1955,7 +1955,7 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op)
 		}
 	}
 
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 	BLI_array_free(mloopuv_arr);
 	BLI_array_free(duplicates);
 	MEM_freeN(changed);
@@ -1987,7 +1987,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op)
 		uv_maxlen += em->bm->totloop;
 	}
 
-	KDTree *tree = BLI_kdtree_new(uv_maxlen);
+	KDTree_3d *tree = BLI_kdtree_3d_new(uv_maxlen);
 
 	MLoopUV **mloopuv_arr = NULL;
 	BLI_array_declare(mloopuv_arr);
@@ -2018,7 +2018,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op)
 				if (!uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
 					MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
 					copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f);
-					BLI_kdtree_insert(tree, mloopuv_count, uvw);
+					BLI_kdtree_3d_insert(tree, mloopuv_count, uvw);
 					BLI_array_append(mloopuv_arr, luv);
 					mloopuv_count++;
 				}
@@ -2026,7 +2026,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op)
 		}
 	}
 
-	BLI_kdtree_balance(tree);
+	BLI_kdtree_3d_balance(tree);
 
 	/* For each selected uv, find duplicate non selected uv. */
 	for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
@@ -2053,8 +2053,8 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op)
 					MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
 					copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f);
 
-					KDTreeNearest nearest;
-					const int i = BLI_kdtree_find_nearest(tree, uvw, &nearest);
+					KDTreeNearest_3d nearest;
+					const int i = BLI_kdtree_3d_find_nearest(tree, uvw, &nearest);
 
 					if (i != -1 && nearest.dist < threshold) {
 						copy_v2_v2(luv->uv, mloopuv_arr[i]->uv);
@@ -2071,7 +2071,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op)
 		}
 	}
 
-	BLI_kdtree_free(tree);
+	BLI_kdtree_3d_free(tree);
 	BLI_array_free(mloopuv_arr);
 	MEM_freeN(objects);