BMESH_TODO: xsort of vertices working again.

This commits adds a new function which can remap vertices/edges/faces of a BMesh in a new given order:
void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx)

3 files changed, 220 insertions, 37 deletions

diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c
index 826d4db4556..c70e694f9ea 100644
--- a/source/blender/bmesh/intern/bmesh_mesh.c
+++ b/source/blender/bmesh/intern/bmesh_mesh.c
@@ -584,6 +584,176 @@ void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *fu
 
 }
 
+/**
+ * Remaps the vertices, edges and/or faces of the bmesh as indicated by vert/edge/face_idx arrays
+ * (xxx_idx[org_index] = new_index).
+ *
+ * A NULL array means no changes.
+ *
+ * Note: - Does not mess with indices, just sets elem_index_dirty flag.
+ *       - For verts/edges/faces only (as loops must remain "ordered" and "aligned"
+ *         on a per-face basis...).
+ *
+ * WARNING: Be careful if you keep pointers to affected BM elements, or arrays, when using this func!
+ */
+void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx)
+{
+	/* Mapping old to new pointers. */
+	GHash *vptr_map = NULL, *eptr_map = NULL, *fptr_map = NULL;
+	BMIter iter, iterl;
+	BMVert *ve;
+	BMEdge *ed;
+	BMFace *fa;
+	BMLoop *lo;
+
+	if (!(vert_idx || edge_idx || face_idx))
+		return;
+
+	/* Remap vertices */
+	if (vert_idx) {
+		BMVert **verts_pool, *verts_copy, **vep;
+		int i, totvert = bm->totvert;
+		int *new_idx = NULL;
+
+		/* Init the old-to-new vert pointers mapping */
+		vptr_map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BM_mesh_remap vert pointers mapping");
+
+		/* Make a copy of all vertices. */
+		verts_pool = MEM_callocN(sizeof(BMVert*) * totvert, "BM_mesh_remap verts pool");
+		BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void**)verts_pool, totvert);
+		verts_copy = MEM_mallocN(sizeof(BMVert) * totvert, "BM_mesh_remap verts copy");
+		for (i = totvert, ve = verts_copy + totvert - 1, vep = verts_pool + totvert - 1; i--; ve--, vep--) {
+			*ve = **vep;
+/*			printf("*vep: %p, verts_pool[%d]: %p\n", *vep, i, verts_pool[i]);*/
+		}
+
+		/* Copy back verts to their new place, and update old2new pointers mapping. */
+		new_idx = vert_idx + totvert - 1;
+		ve = verts_copy + totvert - 1;
+		vep = verts_pool + totvert - 1; /* old, org pointer */
+		for (i = totvert; i--; new_idx--, ve--, vep--) {
+			BMVert *new_vep = verts_pool[*new_idx];
+			*new_vep = *ve;
+/*			printf("mapping vert from %d to %d (%p/%p to %p)\n", i, *new_idx, *vep, verts_pool[i], new_vep);*/
+			BLI_ghash_insert(vptr_map, (void*)*vep, (void*)new_vep);
+		}
+		bm->elem_index_dirty |= BM_VERT;
+
+		MEM_freeN(verts_pool);
+		MEM_freeN(verts_copy);
+	}
+
+	/* XXX Code not tested yet (though I don't why it would fail)! */
+	if (edge_idx) {
+		BMEdge **edges_pool, *edges_copy, **edp;
+		int i, totedge = bm->totedge;
+		int *new_idx = NULL;
+
+		/* Init the old-to-new vert pointers mapping */
+		eptr_map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BM_mesh_remap edge pointers mapping");
+
+		/* Make a copy of all vertices. */
+		edges_pool = MEM_callocN(sizeof(BMEdge*) * totedge, "BM_mesh_remap edges pool");
+		BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void**)edges_pool, totedge);
+		edges_copy = MEM_mallocN(sizeof(BMEdge) * totedge, "BM_mesh_remap edges copy");
+		for (i = totedge, ed = edges_copy + totedge - 1, edp = edges_pool + totedge - 1; i--; ed--, edp--) {
+			*ed = **edp;
+		}
+
+		/* Copy back verts to their new place, and update old2new pointers mapping. */
+		new_idx = edge_idx + totedge - 1;
+		ed = edges_copy + totedge - 1;
+		edp = edges_pool + totedge - 1; /* old, org pointer */
+		for (i = totedge; i--; new_idx--, ed--, edp--) {
+			BMEdge *new_edp = edges_pool[*new_idx];
+			*new_edp = *ed;
+			BLI_ghash_insert(eptr_map, (void*)*edp, (void*)new_edp);
+		}
+
+		bm->elem_index_dirty |= BM_EDGE;
+
+		MEM_freeN(edges_pool);
+		MEM_freeN(edges_copy);
+	}
+
+	/* XXX Code not tested yet (though I don't why it would fail)! */
+	if (face_idx) {
+		BMFace **faces_pool, *faces_copy, **fap;
+		int i, totface = bm->totface;
+		int *new_idx = NULL;
+
+		/* Init the old-to-new vert pointers mapping */
+		fptr_map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BM_mesh_remap face pointers mapping");
+
+		/* Make a copy of all vertices. */
+		faces_pool = MEM_callocN(sizeof(BMFace*) * totface, "BM_mesh_remap faces pool");
+		BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void**)faces_pool, totface);
+		faces_copy = MEM_mallocN(sizeof(BMFace) * totface, "BM_mesh_remap faces copy");
+		for (i = totface, fa = faces_copy + totface - 1, fap = faces_pool + totface - 1; i--; fa--, fap--) {
+			*fa = **fap;
+		}
+
+		/* Copy back verts to their new place, and update old2new pointers mapping. */
+		new_idx = face_idx + totface - 1;
+		fa = faces_copy + totface - 1;
+		fap = faces_pool + totface - 1; /* old, org pointer */
+		for (i = totface; i--; new_idx--, fa--, fap--) {
+			BMFace *new_fap = faces_pool[*new_idx];
+			*new_fap = *fa;
+			BLI_ghash_insert(fptr_map, (void*)*fap, (void*)new_fap);
+		}
+
+		bm->elem_index_dirty |= BM_FACE;
+
+		MEM_freeN(faces_pool);
+		MEM_freeN(faces_copy);
+	}
+
+	/* And now, fix all vertices/edges/faces/loops pointers! */
+	/* Verts' pointers, only edge pointers... */
+	if (eptr_map) {
+		BM_ITER(ve, &iter, bm, BM_VERTS_OF_MESH, NULL) {
+/*			printf("Vert e: %p -> %p\n", ve->e, BLI_ghash_lookup(eptr_map, (const void*)ve->e));*/
+			ve->e = BLI_ghash_lookup(eptr_map, (const void*)ve->e);
+		}
+	}
+
+	/* Edges' pointers, only vert pointers (as we don’t mess with loops!)... */
+	if (vptr_map) {
+		BM_ITER(ed, &iter, bm, BM_EDGES_OF_MESH, NULL) {
+/*			printf("Edge v1: %p -> %p\n", ed->v1, BLI_ghash_lookup(vptr_map, (const void*)ed->v1));*/
+/*			printf("Edge v2: %p -> %p\n", ed->v2, BLI_ghash_lookup(vptr_map, (const void*)ed->v2));*/
+			ed->v1 = BLI_ghash_lookup(vptr_map, (const void*)ed->v1);
+			ed->v2 = BLI_ghash_lookup(vptr_map, (const void*)ed->v2);
+		}
+	}
+
+	/* Faces' pointers (loops, in fact), always needed... */
+	BM_ITER(fa, &iter, bm, BM_FACES_OF_MESH, NULL) {
+		BM_ITER(lo, &iterl, bm, BM_LOOPS_OF_FACE, fa) {
+			if (vptr_map) {
+/*				printf("Loop v: %p -> %p\n", lo->v, BLI_ghash_lookup(vptr_map, (const void*)lo->v));*/
+				lo->v = BLI_ghash_lookup(vptr_map, (const void*)lo->v);
+			}
+			if (eptr_map) {
+/*				printf("Loop e: %p -> %p\n", lo->e, BLI_ghash_lookup(eptr_map, (const void*)lo->e));*/
+				lo->e = BLI_ghash_lookup(eptr_map, (const void*)lo->e);
+			}
+			if (fptr_map) {
+/*				printf("Loop f: %p -> %p\n", lo->f, BLI_ghash_lookup(fptr_map, (const void*)lo->f));*/
+				lo->f = BLI_ghash_lookup(fptr_map, (const void*)lo->f);
+			}
+		}
+	}
+
+	if (vptr_map)
+		BLI_ghash_free(vptr_map, NULL, NULL);
+	if (eptr_map)
+		BLI_ghash_free(eptr_map, NULL, NULL);
+	if (fptr_map)
+		BLI_ghash_free(fptr_map, NULL, NULL);
+}
+
 BMVert *BM_vert_at_index(BMesh *bm, const int index)
 {
 	return BLI_mempool_findelem(bm->vpool, index);
diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h
index f48cc09af3b..970db6339c3 100644
--- a/source/blender/bmesh/intern/bmesh_mesh.h
+++ b/source/blender/bmesh/intern/bmesh_mesh.h
@@ -43,6 +43,7 @@ void bmesh_edit_end(BMesh *bm, int flag);
 void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag);
 void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func,
                                  const char *msg_a, const char *msg_b);
+void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx);
 
 BMVert *BM_vert_at_index(BMesh *bm, const int index);
 BMEdge *BM_edge_at_index(BMesh *bm, const int index);
diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c
index e5eb7ad11fd..fe9571b1978 100644
--- a/source/blender/editors/mesh/editmesh_tools.c
+++ b/source/blender/editors/mesh/editmesh_tools.c
@@ -3599,15 +3599,14 @@ void MESH_OT_select_mirror(wmOperatorType *ot)
 	RNA_def_boolean(ot->srna, "extend", 0, "Extend", "Extend the existing selection");
 }
 
-#if 0 /* UNUSED */
 /* qsort routines.  not sure how to make these
  * work, since we aren't using linked lists for
  * geometry anymore.  might need a sortof "swap"
  * function for bmesh elements. */
 
 typedef struct xvertsort {
-	float x;
-	BMVert *v1;
+	int x; /* X screen-coordinate */
+	int org_idx; /* Original index of this vertex _in the mempool_ */
 } xvertsort;
 
 
@@ -3615,11 +3614,13 @@ static int vergxco(const void *v1, const void *v2)
 {
 	const xvertsort *x1 = v1, *x2 = v2;
 
-	if (x1->x > x2->x) return 1;
-	else if (x1->x < x2->x) return -1;
-	return 0;
+	/* We move unchanged vertices (org_idx < 0) at the begining of the sorted list. */
+	if (x1->org_idx >= 0 && x2->org_idx >= 0)
+		return (x1->x > x2->x) - (x1->x < x2->x);
+	return (x2->org_idx < 0) - (x1->org_idx < 0);
 }
 
+#if 0 /* Unused */
 struct facesort {
 	uintptr_t x;
 	struct EditFace *efa;
@@ -3635,66 +3636,77 @@ static int vergface(const void *v1, const void *v2)
 }
 #endif
 
-// XXX is this needed?
-/* called from buttons */
-#if 0 /* UNUSED */
-static void xsortvert_flag__doSetX(void *userData, EditVert *UNUSED(eve), int x, int UNUSED(y), int index)
+static void xsortvert_flag__doSetX(void *userData, BMVert *UNUSED(eve), int x, int UNUSED(y), int index)
 {
 	xvertsort *sortblock = userData;
 
 	sortblock[index].x = x;
 }
-#endif
 
 /* all verts with (flag & 'flag') are sorted */
-static void xsortvert_flag(bContext *UNUSED(C), int UNUSED(flag))
+static void xsortvert_flag(bContext *C, int flag)
 {
-	/* BMESH_TODO */
-#if 0 //hrm, geometry isn't in linked lists anymore. . .
 	ViewContext vc;
 	BMEditMesh *em;
-	BMVert *eve;
+	BMVert *ve;
 	BMIter iter;
 	xvertsort *sortblock;
-	ListBase tbase;
-	int i, amount;
+	int *unchangedblock, *vmap;
+	int totvert, sorted = 0, unchanged = 0, i;
 
 	em_setup_viewcontext(C, &vc);
 	em = vc.em;
 
-	amount = em->bm->totvert;
-	sortblock = MEM_callocN(sizeof(xvertsort) * amount, "xsort");
-	BM_ITER (eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
-		if (BM_elem_flag_test(eve, BM_ELEM_SELECT))
-			sortblock[i].v1 = eve;
+	totvert = em->bm->totvert;
+
+	sortblock = MEM_callocN(sizeof(xvertsort) * totvert, "xsort sorted");
+	/* Stores unchanged verts, will be reused as final old2new vert mapping... */
+	unchangedblock = MEM_callocN(sizeof(int) * totvert, "xsort unchanged");
+	BM_ITER_INDEX(ve, &iter, em->bm, BM_VERTS_OF_MESH, NULL, i) {
+		if (BM_elem_flag_test(ve, flag)) {
+			sortblock[i].org_idx = i;
+			sorted++;
+		}
+		else {
+			unchangedblock[unchanged++] = i;
+			sortblock[i].org_idx = -1;
+		}
 	}
-	
+/*	printf("%d verts: %d to be sorted, %d unchanged…\n", totvert, sorted, unchanged);*/
+	if (sorted == 0)
+		return;
+
 	ED_view3d_init_mats_rv3d(vc.obedit, vc.rv3d);
 	mesh_foreachScreenVert(&vc, xsortvert_flag__doSetX, sortblock, V3D_CLIP_TEST_OFF);
 
-	qsort(sortblock, amount, sizeof(xvertsort), vergxco);
-
-	/* make temporal listbase */
-	tbase.first = tbase.last = 0;
-	for (i = 0; i < amount; i++) {
-		eve = sortblock[i].v1;
+	qsort(sortblock, totvert, sizeof(xvertsort), vergxco);
 
-		if (eve) {
-			BLI_remlink(&vc.em->verts, eve);
-			BLI_addtail(&tbase, eve);
-		}
+	/* Convert sortblock into an array mapping old idx to new. */
+	vmap = unchangedblock;
+	unchangedblock = NULL;
+	if (unchanged) {
+		unchangedblock = MEM_mallocN(sizeof(int) * unchanged, "xsort unchanged");
+		memcpy(unchangedblock, vmap, unchanged * sizeof(int));
+	}
+	for (i = totvert; i--; ) {
+		if (i < unchanged)
+			vmap[unchangedblock[i]] = i;
+		else
+			vmap[sortblock[i].org_idx] = i;
 	}
-
-	BLI_movelisttolist(&vc.em->verts, &tbase);
 
 	MEM_freeN(sortblock);
-#endif
+	if (unchangedblock)
+		MEM_freeN(unchangedblock);
+
+	BM_mesh_remap(em->bm, vmap, NULL, NULL);
 
+	MEM_freeN(vmap);
 }
 
 static int edbm_vertices_sort_exec(bContext *C, wmOperator *UNUSED(op))
 {
-	xsortvert_flag(C, SELECT);
+	xsortvert_flag(C, BM_ELEM_SELECT);
 	return OPERATOR_FINISHED;
 }