Cleanup: move mesh mirror functions to own file

4 files changed, 375 insertions, 337 deletions

diff --git a/source/blender/editors/mesh/CMakeLists.txt b/source/blender/editors/mesh/CMakeLists.txt
index 8783367ef7e..725d31a64ba 100644
--- a/source/blender/editors/mesh/CMakeLists.txt
+++ b/source/blender/editors/mesh/CMakeLists.txt
@@ -58,6 +58,7 @@ set(SRC
 	editmesh_undo.c
 	editmesh_utils.c
 	mesh_data.c
+	mesh_mirror.c
 	mesh_ops.c
 	meshtools.c
 
diff --git a/source/blender/editors/mesh/editface.c b/source/blender/editors/mesh/editface.c
index 87c8c55b0a1..c453284a617 100644
--- a/source/blender/editors/mesh/editface.c
+++ b/source/blender/editors/mesh/editface.c
@@ -24,7 +24,6 @@
  *  \ingroup edmesh
  */
 
-
 #include "MEM_guardedalloc.h"
 
 #include "BLI_blenlib.h"
@@ -41,7 +40,6 @@
 #include "BKE_global.h"
 #include "BKE_mesh.h"
 #include "BKE_context.h"
-#include "BKE_editmesh.h"
 
 #include "BIF_gl.h"
 
@@ -605,258 +603,3 @@ void paintvert_select_ungrouped(Object *ob, bool extend, bool flush_flags)
 		paintvert_flush_flags(ob);
 	}
 }
-
-/* ********************* MESH VERTEX MIRR TOPO LOOKUP *************** */
-/* note, this is not the best place for the function to be but moved
- * here for the purpose of syncing with bmesh */
-
-typedef unsigned int MirrTopoHash_t;
-
-typedef struct MirrTopoVert_t {
-	MirrTopoHash_t hash;
-	int v_index;
-} MirrTopoVert_t;
-
-static int mirrtopo_hash_sort(const void *l1, const void *l2)
-{
-	if      ((MirrTopoHash_t)(intptr_t)l1 > (MirrTopoHash_t)(intptr_t)l2) return 1;
-	else if ((MirrTopoHash_t)(intptr_t)l1 < (MirrTopoHash_t)(intptr_t)l2) return -1;
-	return 0;
-}
-
-static int mirrtopo_vert_sort(const void *v1, const void *v2)
-{
-	if      (((MirrTopoVert_t *)v1)->hash > ((MirrTopoVert_t *)v2)->hash) return 1;
-	else if (((MirrTopoVert_t *)v1)->hash < ((MirrTopoVert_t *)v2)->hash) return -1;
-	return 0;
-}
-
-bool ED_mesh_mirrtopo_recalc_check(Mesh *me, DerivedMesh *dm, const int ob_mode, MirrTopoStore_t *mesh_topo_store)
-{
-	int totvert;
-	int totedge;
-
-	if (dm) {
-		totvert = dm->getNumVerts(dm);
-		totedge = dm->getNumEdges(dm);
-	}
-	else if (me->edit_btmesh) {
-		totvert = me->edit_btmesh->bm->totvert;
-		totedge = me->edit_btmesh->bm->totedge;
-	}
-	else {
-		totvert = me->totvert;
-		totedge = me->totedge;
-	}
-
-	if ((mesh_topo_store->index_lookup == NULL) ||
-	    (mesh_topo_store->prev_ob_mode != ob_mode) ||
-	    (totvert != mesh_topo_store->prev_vert_tot) ||
-	    (totedge != mesh_topo_store->prev_edge_tot))
-	{
-		return true;
-	}
-	else {
-		return false;
-	}
-
-}
-
-void ED_mesh_mirrtopo_init(Mesh *me, DerivedMesh *dm, const int ob_mode, MirrTopoStore_t *mesh_topo_store,
-                           const bool skip_em_vert_array_init)
-{
-	MEdge *medge = NULL, *med;
-	BMEditMesh *em = dm ?  NULL : me->edit_btmesh;
-
-	/* editmode*/
-	BMEdge *eed;
-	BMIter iter;
-
-	int a, last;
-	int totvert, totedge;
-	int tot_unique = -1, tot_unique_prev = -1;
-	int tot_unique_edges = 0, tot_unique_edges_prev;
-
-	MirrTopoHash_t *topo_hash = NULL;
-	MirrTopoHash_t *topo_hash_prev = NULL;
-	MirrTopoVert_t *topo_pairs;
-	MirrTopoHash_t  topo_pass = 1;
-
-	intptr_t *index_lookup; /* direct access to mesh_topo_store->index_lookup */
-
-	/* reallocate if needed */
-	ED_mesh_mirrtopo_free(mesh_topo_store);
-
-	mesh_topo_store->prev_ob_mode = ob_mode;
-
-	if (em) {
-		BM_mesh_elem_index_ensure(em->bm, BM_VERT);
-
-		totvert = em->bm->totvert;
-	}
-	else {
-		totvert = dm ? dm->getNumVerts(dm) : me->totvert;
-	}
-
-	topo_hash = MEM_callocN(totvert * sizeof(MirrTopoHash_t), "TopoMirr");
-
-	/* Initialize the vert-edge-user counts used to detect unique topology */
-	if (em) {
-		totedge = me->edit_btmesh->bm->totedge;
-
-		BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
-			const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
-			topo_hash[i1]++;
-			topo_hash[i2]++;
-		}
-	}
-	else {
-		totedge = dm ? dm->getNumEdges(dm) : me->totedge;
-		medge = dm ? dm->getEdgeArray(dm) : me->medge;
-
-		for (a = 0, med = medge; a < totedge; a++, med++) {
-			const unsigned int i1 = med->v1, i2 = med->v2;
-			topo_hash[i1]++;
-			topo_hash[i2]++;
-		}
-	}
-
-	topo_hash_prev = MEM_dupallocN(topo_hash);
-
-	tot_unique_prev = -1;
-	tot_unique_edges_prev = -1;
-	while (1) {
-		/* use the number of edges per vert to give verts unique topology IDs */
-
-		tot_unique_edges = 0;
-
-		/* This can make really big numbers, wrapping around here is fine */
-		if (em) {
-			BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
-				const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
-				topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
-				topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
-				tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
-			}
-		}
-		else {
-			for (a = 0, med = medge; a < totedge; a++, med++) {
-				const unsigned int i1 = med->v1, i2 = med->v2;
-				topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
-				topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
-				tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
-			}
-		}
-		memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
-
-		/* sort so we can count unique values */
-		qsort(topo_hash_prev, totvert, sizeof(MirrTopoHash_t), mirrtopo_hash_sort);
-
-		tot_unique = 1; /* account for skiping the first value */
-		for (a = 1; a < totvert; a++) {
-			if (topo_hash_prev[a - 1] != topo_hash_prev[a]) {
-				tot_unique++;
-			}
-		}
-
-		if ((tot_unique <= tot_unique_prev) && (tot_unique_edges <= tot_unique_edges_prev)) {
-			/* Finish searching for unique values when 1 loop dosnt give a
-			 * higher number of unique values compared to the previous loop */
-			break;
-		}
-		else {
-			tot_unique_prev = tot_unique;
-			tot_unique_edges_prev = tot_unique_edges;
-		}
-		/* Copy the hash calculated this iter, so we can use them next time */
-		memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
-
-		topo_pass++;
-	}
-
-	/* Hash/Index pairs are needed for sorting to find index pairs */
-	topo_pairs = MEM_callocN(sizeof(MirrTopoVert_t) * totvert, "MirrTopoPairs");
-
-	/* since we are looping through verts, initialize these values here too */
-	index_lookup = MEM_mallocN(totvert * sizeof(*index_lookup), "mesh_topo_lookup");
-
-	if (em) {
-		if (skip_em_vert_array_init == false) {
-			BM_mesh_elem_table_ensure(em->bm, BM_VERT);
-		}
-	}
-
-	for (a = 0; a < totvert; a++) {
-		topo_pairs[a].hash    = topo_hash[a];
-		topo_pairs[a].v_index = a;
-
-		/* initialize lookup */
-		index_lookup[a] = -1;
-	}
-
-	qsort(topo_pairs, totvert, sizeof(MirrTopoVert_t), mirrtopo_vert_sort);
-
-	last = 0;
-
-	/* Get the pairs out of the sorted hashes, note, totvert+1 means we can use the previous 2,
-	 * but you cant ever access the last 'a' index of MirrTopoPairs */
-	if (em) {
-		BMVert **vtable = em->bm->vtable;
-		for (a = 1; a <= totvert; a++) {
-			/* printf("I %d %ld %d\n", (a - last), MirrTopoPairs[a].hash, MirrTopoPairs[a].v_indexs); */
-			if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
-				const int match_count = a - last;
-				if (match_count == 2) {
-					const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
-					index_lookup[j] = (intptr_t)vtable[k];
-					index_lookup[k] = (intptr_t)vtable[j];
-				}
-				else if (match_count == 1) {
-					/* Center vertex. */
-					const int j = topo_pairs[a - 1].v_index;
-					index_lookup[j] = (intptr_t)vtable[j];
-				}
-				last = a;
-			}
-		}
-	}
-	else {
-		/* same as above, for mesh */
-		for (a = 1; a <= totvert; a++) {
-			if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
-				const int match_count = a - last;
-				if (match_count == 2) {
-					const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
-					index_lookup[j] = k;
-					index_lookup[k] = j;
-				}
-				else if (match_count == 1) {
-					/* Center vertex. */
-					const int j = topo_pairs[a - 1].v_index;
-					index_lookup[j] = j;
-				}
-				last = a;
-			}
-		}
-	}
-
-	MEM_freeN(topo_pairs);
-	topo_pairs = NULL;
-
-	MEM_freeN(topo_hash);
-	MEM_freeN(topo_hash_prev);
-
-	mesh_topo_store->index_lookup  = index_lookup;
-	mesh_topo_store->prev_vert_tot = totvert;
-	mesh_topo_store->prev_edge_tot = totedge;
-}
-
-void ED_mesh_mirrtopo_free(MirrTopoStore_t *mesh_topo_store)
-{
-	if (mesh_topo_store->index_lookup) {
-		MEM_freeN(mesh_topo_store->index_lookup);
-	}
-	mesh_topo_store->index_lookup  = NULL;
-	mesh_topo_store->prev_vert_tot = -1;
-	mesh_topo_store->prev_edge_tot = -1;
-}
diff --git a/source/blender/editors/mesh/mesh_mirror.c b/source/blender/editors/mesh/mesh_mirror.c
new file mode 100644
index 00000000000..96b9f054252
--- /dev/null
+++ b/source/blender/editors/mesh/mesh_mirror.c
@@ -0,0 +1,374 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Blender Foundation, Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/editors/mesh/mesh_mirror.c
+ *  \ingroup edmesh
+ *
+ * Mirror calculation for edit-mode and object mode.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_bitmap.h"
+
+#include "DNA_mesh_types.h"
+#include "DNA_object_types.h"
+
+#include "BKE_DerivedMesh.h"
+#include "BLI_kdtree.h"
+#include "BKE_editmesh.h"
+
+#include "ED_mesh.h"
+
+/* -------------------------------------------------------------------- */
+/** \name Mesh Spatial Mirror API
+ * \{ */
+
+#define KD_THRESH      0.00002f
+
+static struct { void *tree; } MirrKdStore = {NULL};
+
+/* mode is 's' start, or 'e' end, or 'u' use */
+/* if end, ob can be NULL */
+int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, DerivedMesh *dm, const float co[3], char mode)
+{
+	if (mode == 'u') {        /* use table */
+		if (MirrKdStore.tree == NULL)
+			ED_mesh_mirror_spatial_table(ob, em, dm, NULL, 's');
+
+		if (MirrKdStore.tree) {
+			KDTreeNearest nearest;
+			const int i = BLI_kdtree_find_nearest(MirrKdStore.tree, co, &nearest);
+
+			if (i != -1) {
+				if (nearest.dist < KD_THRESH) {
+					return i;
+				}
+			}
+		}
+		return -1;
+	}
+	else if (mode == 's') {   /* start table */
+		Mesh *me = ob->data;
+		const bool use_em = (!dm && em && me->edit_btmesh == em);
+		const int totvert = use_em ? em->bm->totvert : dm ? dm->getNumVerts(dm) : me->totvert;
+
+		if (MirrKdStore.tree) /* happens when entering this call without ending it */
+			ED_mesh_mirror_spatial_table(ob, em, dm, co, 'e');
+
+		MirrKdStore.tree = BLI_kdtree_new(totvert);
+
+		if (use_em) {
+			BMVert *eve;
+			BMIter iter;
+			int i;
+
+			/* this needs to be valid for index lookups later (callers need) */
+			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);
+			}
+		}
+		else {
+			MVert *mvert = dm ? dm->getVertArray(dm) : me->mvert;
+			int i;
+			
+			for (i = 0; i < totvert; i++, mvert++) {
+				BLI_kdtree_insert(MirrKdStore.tree, i, mvert->co);
+			}
+		}
+
+		BLI_kdtree_balance(MirrKdStore.tree);
+	}
+	else if (mode == 'e') { /* end table */
+		if (MirrKdStore.tree) {
+			BLI_kdtree_free(MirrKdStore.tree);
+			MirrKdStore.tree = NULL;
+		}
+	}
+	else {
+		BLI_assert(0);
+	}
+
+	return 0;
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Mesh Topology Mirror API
+ * \{ */
+
+typedef unsigned int MirrTopoHash_t;
+
+typedef struct MirrTopoVert_t {
+	MirrTopoHash_t hash;
+	int v_index;
+} MirrTopoVert_t;
+
+static int mirrtopo_hash_sort(const void *l1, const void *l2)
+{
+	if      ((MirrTopoHash_t)(intptr_t)l1 > (MirrTopoHash_t)(intptr_t)l2) return 1;
+	else if ((MirrTopoHash_t)(intptr_t)l1 < (MirrTopoHash_t)(intptr_t)l2) return -1;
+	return 0;
+}
+
+static int mirrtopo_vert_sort(const void *v1, const void *v2)
+{
+	if      (((MirrTopoVert_t *)v1)->hash > ((MirrTopoVert_t *)v2)->hash) return 1;
+	else if (((MirrTopoVert_t *)v1)->hash < ((MirrTopoVert_t *)v2)->hash) return -1;
+	return 0;
+}
+
+bool ED_mesh_mirrtopo_recalc_check(Mesh *me, DerivedMesh *dm, const int ob_mode, MirrTopoStore_t *mesh_topo_store)
+{
+	int totvert;
+	int totedge;
+
+	if (dm) {
+		totvert = dm->getNumVerts(dm);
+		totedge = dm->getNumEdges(dm);
+	}
+	else if (me->edit_btmesh) {
+		totvert = me->edit_btmesh->bm->totvert;
+		totedge = me->edit_btmesh->bm->totedge;
+	}
+	else {
+		totvert = me->totvert;
+		totedge = me->totedge;
+	}
+
+	if ((mesh_topo_store->index_lookup == NULL) ||
+	    (mesh_topo_store->prev_ob_mode != ob_mode) ||
+	    (totvert != mesh_topo_store->prev_vert_tot) ||
+	    (totedge != mesh_topo_store->prev_edge_tot))
+	{
+		return true;
+	}
+	else {
+		return false;
+	}
+
+}
+
+void ED_mesh_mirrtopo_init(Mesh *me, DerivedMesh *dm, const int ob_mode, MirrTopoStore_t *mesh_topo_store,
+                           const bool skip_em_vert_array_init)
+{
+	MEdge *medge = NULL, *med;
+	BMEditMesh *em = dm ?  NULL : me->edit_btmesh;
+
+	/* editmode*/
+	BMEdge *eed;
+	BMIter iter;
+
+	int a, last;
+	int totvert, totedge;
+	int tot_unique = -1, tot_unique_prev = -1;
+	int tot_unique_edges = 0, tot_unique_edges_prev;
+
+	MirrTopoHash_t *topo_hash = NULL;
+	MirrTopoHash_t *topo_hash_prev = NULL;
+	MirrTopoVert_t *topo_pairs;
+	MirrTopoHash_t  topo_pass = 1;
+
+	intptr_t *index_lookup; /* direct access to mesh_topo_store->index_lookup */
+
+	/* reallocate if needed */
+	ED_mesh_mirrtopo_free(mesh_topo_store);
+
+	mesh_topo_store->prev_ob_mode = ob_mode;
+
+	if (em) {
+		BM_mesh_elem_index_ensure(em->bm, BM_VERT);
+
+		totvert = em->bm->totvert;
+	}
+	else {
+		totvert = dm ? dm->getNumVerts(dm) : me->totvert;
+	}
+
+	topo_hash = MEM_callocN(totvert * sizeof(MirrTopoHash_t), "TopoMirr");
+
+	/* Initialize the vert-edge-user counts used to detect unique topology */
+	if (em) {
+		totedge = me->edit_btmesh->bm->totedge;
+
+		BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
+			const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
+			topo_hash[i1]++;
+			topo_hash[i2]++;
+		}
+	}
+	else {
+		totedge = dm ? dm->getNumEdges(dm) : me->totedge;
+		medge = dm ? dm->getEdgeArray(dm) : me->medge;
+
+		for (a = 0, med = medge; a < totedge; a++, med++) {
+			const unsigned int i1 = med->v1, i2 = med->v2;
+			topo_hash[i1]++;
+			topo_hash[i2]++;
+		}
+	}
+
+	topo_hash_prev = MEM_dupallocN(topo_hash);
+
+	tot_unique_prev = -1;
+	tot_unique_edges_prev = -1;
+	while (1) {
+		/* use the number of edges per vert to give verts unique topology IDs */
+
+		tot_unique_edges = 0;
+
+		/* This can make really big numbers, wrapping around here is fine */
+		if (em) {
+			BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
+				const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
+				topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
+				topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
+				tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
+			}
+		}
+		else {
+			for (a = 0, med = medge; a < totedge; a++, med++) {
+				const unsigned int i1 = med->v1, i2 = med->v2;
+				topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
+				topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
+				tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
+			}
+		}
+		memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
+
+		/* sort so we can count unique values */
+		qsort(topo_hash_prev, totvert, sizeof(MirrTopoHash_t), mirrtopo_hash_sort);
+
+		tot_unique = 1; /* account for skiping the first value */
+		for (a = 1; a < totvert; a++) {
+			if (topo_hash_prev[a - 1] != topo_hash_prev[a]) {
+				tot_unique++;
+			}
+		}
+
+		if ((tot_unique <= tot_unique_prev) && (tot_unique_edges <= tot_unique_edges_prev)) {
+			/* Finish searching for unique values when 1 loop dosnt give a
+			 * higher number of unique values compared to the previous loop */
+			break;
+		}
+		else {
+			tot_unique_prev = tot_unique;
+			tot_unique_edges_prev = tot_unique_edges;
+		}
+		/* Copy the hash calculated this iter, so we can use them next time */
+		memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
+
+		topo_pass++;
+	}
+
+	/* Hash/Index pairs are needed for sorting to find index pairs */
+	topo_pairs = MEM_callocN(sizeof(MirrTopoVert_t) * totvert, "MirrTopoPairs");
+
+	/* since we are looping through verts, initialize these values here too */
+	index_lookup = MEM_mallocN(totvert * sizeof(*index_lookup), "mesh_topo_lookup");
+
+	if (em) {
+		if (skip_em_vert_array_init == false) {
+			BM_mesh_elem_table_ensure(em->bm, BM_VERT);
+		}
+	}
+
+	for (a = 0; a < totvert; a++) {
+		topo_pairs[a].hash    = topo_hash[a];
+		topo_pairs[a].v_index = a;
+
+		/* initialize lookup */
+		index_lookup[a] = -1;
+	}
+
+	qsort(topo_pairs, totvert, sizeof(MirrTopoVert_t), mirrtopo_vert_sort);
+
+	last = 0;
+
+	/* Get the pairs out of the sorted hashes, note, totvert+1 means we can use the previous 2,
+	 * but you cant ever access the last 'a' index of MirrTopoPairs */
+	if (em) {
+		BMVert **vtable = em->bm->vtable;
+		for (a = 1; a <= totvert; a++) {
+			/* printf("I %d %ld %d\n", (a - last), MirrTopoPairs[a].hash, MirrTopoPairs[a].v_indexs); */
+			if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
+				const int match_count = a - last;
+				if (match_count == 2) {
+					const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
+					index_lookup[j] = (intptr_t)vtable[k];
+					index_lookup[k] = (intptr_t)vtable[j];
+				}
+				else if (match_count == 1) {
+					/* Center vertex. */
+					const int j = topo_pairs[a - 1].v_index;
+					index_lookup[j] = (intptr_t)vtable[j];
+				}
+				last = a;
+			}
+		}
+	}
+	else {
+		/* same as above, for mesh */
+		for (a = 1; a <= totvert; a++) {
+			if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
+				const int match_count = a - last;
+				if (match_count == 2) {
+					const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
+					index_lookup[j] = k;
+					index_lookup[k] = j;
+				}
+				else if (match_count == 1) {
+					/* Center vertex. */
+					const int j = topo_pairs[a - 1].v_index;
+					index_lookup[j] = j;
+				}
+				last = a;
+			}
+		}
+	}
+
+	MEM_freeN(topo_pairs);
+	topo_pairs = NULL;
+
+	MEM_freeN(topo_hash);
+	MEM_freeN(topo_hash_prev);
+
+	mesh_topo_store->index_lookup  = index_lookup;
+	mesh_topo_store->prev_vert_tot = totvert;
+	mesh_topo_store->prev_edge_tot = totedge;
+}
+
+void ED_mesh_mirrtopo_free(MirrTopoStore_t *mesh_topo_store)
+{
+	if (mesh_topo_store->index_lookup) {
+		MEM_freeN(mesh_topo_store->index_lookup);
+	}
+	mesh_topo_store->index_lookup  = NULL;
+	mesh_topo_store->prev_vert_tot = -1;
+	mesh_topo_store->prev_edge_tot = -1;
+}
+
+/** \} */
diff --git a/source/blender/editors/mesh/meshtools.c b/source/blender/editors/mesh/meshtools.c
index b66821c4e37..73413bcbaad 100644
--- a/source/blender/editors/mesh/meshtools.c
+++ b/source/blender/editors/mesh/meshtools.c
@@ -46,8 +46,6 @@
 #include "BLI_math.h"
 #include "BLI_blenlib.h"
 
-
-#include "BLI_kdtree.h"
 #include "BKE_context.h"
 #include "BKE_depsgraph.h"
 #include "BKE_deform.h"
@@ -671,84 +669,6 @@ int join_mesh_shapes_exec(bContext *C, wmOperator *op)
 	return OPERATOR_FINISHED;
 }
 
-/* -------------------------------------------------------------------- */
-/* Mesh Mirror (Spatial) */
-
-/** \name Mesh Spatial Mirror API
- * \{ */
-
-#define KD_THRESH      0.00002f
-
-static struct { void *tree; } MirrKdStore = {NULL};
-
-/* mode is 's' start, or 'e' end, or 'u' use */
-/* if end, ob can be NULL */
-int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, DerivedMesh *dm, const float co[3], char mode)
-{
-	if (mode == 'u') {        /* use table */
-		if (MirrKdStore.tree == NULL)
-			ED_mesh_mirror_spatial_table(ob, em, dm, NULL, 's');
-
-		if (MirrKdStore.tree) {
-			KDTreeNearest nearest;
-			const int i = BLI_kdtree_find_nearest(MirrKdStore.tree, co, &nearest);
-
-			if (i != -1) {
-				if (nearest.dist < KD_THRESH) {
-					return i;
-				}
-			}
-		}
-		return -1;
-	}
-	else if (mode == 's') {   /* start table */
-		Mesh *me = ob->data;
-		const bool use_em = (!dm && em && me->edit_btmesh == em);
-		const int totvert = use_em ? em->bm->totvert : dm ? dm->getNumVerts(dm) : me->totvert;
-
-		if (MirrKdStore.tree) /* happens when entering this call without ending it */
-			ED_mesh_mirror_spatial_table(ob, em, dm, co, 'e');
-
-		MirrKdStore.tree = BLI_kdtree_new(totvert);
-
-		if (use_em) {
-			BMVert *eve;
-			BMIter iter;
-			int i;
-
-			/* this needs to be valid for index lookups later (callers need) */
-			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);
-			}
-		}
-		else {
-			MVert *mvert = dm ? dm->getVertArray(dm) : me->mvert;
-			int i;
-			
-			for (i = 0; i < totvert; i++, mvert++) {
-				BLI_kdtree_insert(MirrKdStore.tree, i, mvert->co);
-			}
-		}
-
-		BLI_kdtree_balance(MirrKdStore.tree);
-	}
-	else if (mode == 'e') { /* end table */
-		if (MirrKdStore.tree) {
-			BLI_kdtree_free(MirrKdStore.tree);
-			MirrKdStore.tree = NULL;
-		}
-	}
-	else {
-		BLI_assert(0);
-	}
-
-	return 0;
-}
-
-/** \} */
-
 
 /* -------------------------------------------------------------------- */
 /* Mesh Mirror (Topology) */