BKE: Add 'mesh remap' code.

This is the (big!) core of mesh transfer data, it defines a set of structures
to represent a mapping of mesh elements (verts, edges, polys of loops) between
two arbitrary meshes, and code to compute such mappings.

No similarity is required between source and destination meshes (though results
when using complete different meshes are rather unlikely to be useful!).

This code is not bound to data transfer, it is defined to be as generic as possible,
and easy to reuse or extend as needs arise.

Several methods of mapping generation are defined for each element type,
we probably will have to adjust that in future (remove useless ones, add
new ones...).

For loops, you can also define islands (for UVs e.g.) so that loops of a same
destination polygon do not 'spread' across several source islands.

Heavily reviewed and enhanced by Campbell, thanks a lot!

1 files changed, 334 insertions, 43 deletions

diff --git a/source/blender/blenkernel/intern/mesh_mapping.c b/source/blender/blenkernel/intern/mesh_mapping.c
index 53d1aae104c..9e490ae6766 100644
--- a/source/blender/blenkernel/intern/mesh_mapping.c
+++ b/source/blender/blenkernel/intern/mesh_mapping.c
@@ -32,10 +32,12 @@
 #include "DNA_meshdata_types.h"
 
 #include "BLI_utildefines.h"
+#include "BLI_bitmap.h"
 #include "BLI_math.h"
 
 #include "BKE_mesh_mapping.h"
 #include "BKE_customdata.h"
+#include "BLI_memarena.h"
 
 #include "BLI_strict_flags.h"
 
@@ -156,18 +158,25 @@ void BKE_mesh_uv_vert_map_free(UvVertMap *vmap)
 	}
 }
 
-/* Generates a map where the key is the vertex and the value is a list
- * of polys that use that vertex as a corner. The lists are allocated
- * from one memory pool. */
-void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const MPoly *mpoly, const MLoop *mloop,
-                                   int totvert, int totpoly, int totloop)
+/**
+
+
+ * Generates a map where the key is the vertex and the value is a list
+ * of polys or loops that use that vertex as a corner. The lists are allocated
+ * from one memory pool.
+ *
+ * Wrapped by #BKE_mesh_vert_poly_map_create & BKE_mesh_vert_loop_map_create
+ */
+static void mesh_vert_poly_or_loop_map_create(
+        MeshElemMap **r_map, int **r_mem,
+        const MPoly *mpoly, const MLoop *mloop,
+        int totvert, int totpoly, int totloop, const bool do_loops)
 {
-	MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, "vert poly map");
+	MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, __func__);
 	int *indices, *index_iter;
 	int i, j;
 
-	indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)totloop, "vert poly map mem");
+	indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)totloop, __func__);
 
 	/* Count number of polys for each vertex */
 	for (i = 0; i < totpoly; i++) {
@@ -193,7 +202,7 @@ void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
 		for (j = 0; j < p->totloop; j++) {
 			unsigned int v = mloop[p->loopstart + j].v;
 
-			map[v].indices[map[v].count] = i;
+			map[v].indices[map[v].count] = do_loops ? p->loopstart + j : i;
 			map[v].count++;
 		}
 	}
@@ -202,6 +211,28 @@ void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
 	*r_mem = indices;
 }
 
+/**
+ * Generates a map where the key is the vertex and the value is a list of polys that use that vertex as a corner.
+ * The lists are allocated from one memory pool.
+ */
+void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
+                                   const MPoly *mpoly, const MLoop *mloop,
+                                   int totvert, int totpoly, int totloop)
+{
+	mesh_vert_poly_or_loop_map_create(r_map, r_mem, mpoly, mloop, totvert, totpoly, totloop, false);
+}
+
+/**
+ * Generates a map where the key is the vertex and the value is a list of loops that use that vertex as a corner.
+ * The lists are allocated from one memory pool.
+ */
+void BKE_mesh_vert_loop_map_create(MeshElemMap **r_map, int **r_mem,
+                                   const MPoly *mpoly, const MLoop *mloop,
+                                   int totvert, int totpoly, int totloop)
+{
+	mesh_vert_poly_or_loop_map_create(r_map, r_mem, mpoly, mloop, totvert, totpoly, totloop, true);
+}
+
 /* Generates a map where the key is the vertex and the value is a list
  * of edges that use that vertex as an endpoint. The lists are allocated
  * from one memory pool. */
@@ -345,26 +376,30 @@ void BKE_mesh_origindex_map_create(MeshElemMap **r_map, int **r_mem,
 /** \} */
 
 
-
 /* -------------------------------------------------------------------- */
 
-/** \name Mesh Smooth Groups
+/** \name Mesh loops/poly islands.
+ * Used currently for UVs and 'smooth groups'.
  * \{ */
 
-/**
- * Calculate smooth groups from sharp edges.
- *
- * \param r_totgroup The total number of groups, 1 or more.
- * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1.
+/** Callback deciding whether the given poly/loop/edge define an island boundary or not.
  */
-int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
-                                const MPoly *mpoly, const int totpoly,
-                                const MLoop *mloop, const int totloop,
-                                int *r_totgroup, const bool use_bitflags)
+typedef bool (*MeshRemap_CheckIslandBoundary)(
+        const struct MPoly *mpoly, const struct MLoop *mloop, const struct MEdge *medge,
+        const int nbr_egde_users);
+
+static void poly_edge_loop_islands_calc(
+        const MEdge *medge, const int totedge, const MPoly *mpoly, const int totpoly,
+        const MLoop *mloop, const int totloop, MeshElemMap *edge_poly_map,
+        const bool use_bitflags, MeshRemap_CheckIslandBoundary edge_boundary_check,
+        int **r_poly_groups, int *r_totgroup, BLI_bitmap **r_edge_borders, int *r_totedgeborder)
 {
 	int *poly_groups;
 	int *poly_stack;
 
+	BLI_bitmap *edge_borders = NULL;
+	int num_edgeborders = 0;
+
 	int poly_prev = 0;
 	const int temp_poly_group_id = 3;  /* Placeholder value. */
 	const int poly_group_id_overflowed = 5;  /* Group we could not find any available bit, will be reset to 0 at end */
@@ -372,18 +407,27 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
 	bool group_id_overflow = false;
 
 	/* map vars */
-	MeshElemMap *edge_poly_map;
-	int *edge_poly_mem;
+	int *edge_poly_mem = NULL;
 
 	if (totpoly == 0) {
 		*r_totgroup = 0;
-		return NULL;
+		*r_poly_groups = NULL;
+		if (r_edge_borders) {
+			*r_edge_borders = NULL;
+			*r_totedgeborder = 0;
+		}
+		return;
 	}
 
-	BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem,
-	                              medge, totedge,
-	                              mpoly, totpoly,
-	                              mloop, totloop);
+	if (r_edge_borders) {
+		edge_borders = BLI_BITMAP_NEW(totedge, __func__);
+		*r_totedgeborder = 0;
+	}
+
+	if (!edge_poly_map) {
+		BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem,
+		                              medge, totedge, mpoly, totpoly, mloop, totloop);
+	}
 
 	poly_groups = MEM_callocN(sizeof(int) * (size_t)totpoly, __func__);
 	poly_stack  = MEM_mallocN(sizeof(int) * (size_t)totpoly, __func__);
@@ -416,22 +460,20 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
 		while (ps_curr_idx != ps_end_idx) {
 			const MPoly *mp;
 			const MLoop *ml;
-			bool sharp_poly;
 			int j;
 
 			poly = poly_stack[ps_curr_idx++];
 			BLI_assert(poly_groups[poly] == poly_group_id);
 
 			mp = &mpoly[poly];
-			sharp_poly = !(mp->flag & ME_SMOOTH);
 			for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) {
 				/* loop over poly users */
-				const MeshElemMap *map_ele = &edge_poly_map[ml->e];
+				const int me_idx = (int)ml->e;
+				const MEdge *me = &medge[me_idx];
+				const MeshElemMap *map_ele = &edge_poly_map[me_idx];
 				const int *p = map_ele->indices;
 				int i = map_ele->count;
-				/* Edge is smooth only if its poly is not sharp, edge is not sharp,
-				 * and edge is used by exactly two polygons. */
-				if (!sharp_poly && !(medge[ml->e].flag & ME_SHARP) && i == 2) {
+				if (!edge_boundary_check(mp, ml, me, i)) {
 					for (; i--; p++) {
 						/* if we meet other non initialized its a bug */
 						BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id));
@@ -442,14 +484,20 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
 						}
 					}
 				}
-				else if (use_bitflags) {
-					/* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
-					for (; i--; p++) {
-						int bit = poly_groups[*p];
-						if (!ELEM(bit, 0, poly_group_id, poly_group_id_overflowed) &&
-						    !(bit_poly_group_mask & bit))
-						{
-							bit_poly_group_mask |= bit;
+				else {
+					if (edge_borders && !BLI_BITMAP_TEST(edge_borders, me_idx)) {
+						BLI_BITMAP_ENABLE(edge_borders, me_idx);
+						num_edgeborders++;
+					}
+					if (use_bitflags) {
+						/* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
+						for (; i--; p++) {
+							int bit = poly_groups[*p];
+							if (!ELEM(bit, 0, poly_group_id, poly_group_id_overflowed) &&
+							    !(bit_poly_group_mask & bit))
+							{
+								bit_poly_group_mask |= bit;
+							}
 						}
 					}
 				}
@@ -502,12 +550,255 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
 		tot_group++;
 	}
 
-	MEM_freeN(edge_poly_map);
-	MEM_freeN(edge_poly_mem);
+	if (edge_poly_mem) {
+		MEM_freeN(edge_poly_map);
+		MEM_freeN(edge_poly_mem);
+	}
 	MEM_freeN(poly_stack);
 
 	*r_totgroup = tot_group;
+	*r_poly_groups = poly_groups;
+	if (r_edge_borders) {
+		*r_edge_borders = edge_borders;
+		*r_totedgeborder = num_edgeborders;
+	}
+}
+
+static bool poly_is_island_boundary_smooth_cb(
+        const MPoly *mp, const MLoop *UNUSED(ml), const MEdge *me,
+        const int nbr_egde_users)
+{
+	/* Edge is sharp if its poly is sharp, or edge itself is sharp, or edge is not used by exactly two polygons. */
+	return (!(mp->flag & ME_SMOOTH) || (me->flag & ME_SHARP) || (nbr_egde_users != 2));
+}
+
+/**
+ * Calculate smooth groups from sharp edges.
+ *
+ * \param r_totgroup The total number of groups, 1 or more.
+ * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1
+ *         (0 being used as 'invalid' flag).
+ *         Note it's callers's responsibility to MEM_freeN returned array.
+ */
+int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
+                                const MPoly *mpoly, const int totpoly,
+                                const MLoop *mloop, const int totloop,
+                                int *r_totgroup, const bool use_bitflags)
+{
+	int *poly_groups = NULL;
+
+	poly_edge_loop_islands_calc(
+	        medge, totedge, mpoly, totpoly, mloop, totloop, NULL, use_bitflags,
+	        poly_is_island_boundary_smooth_cb, &poly_groups, r_totgroup, NULL, NULL);
 
 	return poly_groups;
 }
+
+#define MISLAND_DEFAULT_BUFSIZE 64
+
+void BKE_mesh_loop_islands_init(
+        MeshIslandStore *island_store,
+        const short item_type, const int items_num, const short island_type, const short innercut_type)
+{
+	MemArena *mem = island_store->mem;
+
+	if (mem == NULL) {
+		mem = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
+		island_store->mem = mem;
+	}
+	/* else memarena should be cleared */
+
+	BLI_assert(ELEM(item_type, MISLAND_TYPE_VERT, MISLAND_TYPE_EDGE, MISLAND_TYPE_POLY, MISLAND_TYPE_LOOP));
+	BLI_assert(ELEM(island_type, MISLAND_TYPE_VERT, MISLAND_TYPE_EDGE, MISLAND_TYPE_POLY, MISLAND_TYPE_LOOP));
+
+	island_store->item_type = item_type;
+	island_store->items_to_islands_num = items_num;
+	island_store->items_to_islands = BLI_memarena_alloc(mem, sizeof(*island_store->items_to_islands) * (size_t)items_num);
+
+	island_store->island_type = island_type;
+	island_store->islands_num_alloc = MISLAND_DEFAULT_BUFSIZE;
+	island_store->islands = BLI_memarena_alloc(mem, sizeof(*island_store->islands) * island_store->islands_num_alloc);
+
+	island_store->innercut_type = innercut_type;
+	island_store->innercuts = BLI_memarena_alloc(mem, sizeof(*island_store->innercuts) * island_store->islands_num_alloc);
+}
+
+void BKE_mesh_loop_islands_clear(MeshIslandStore *island_store)
+{
+	island_store->item_type = MISLAND_TYPE_NONE;
+	island_store->items_to_islands_num = 0;
+	island_store->items_to_islands = NULL;
+
+	island_store->island_type = MISLAND_TYPE_NONE;
+	island_store->islands_num = 0;
+	island_store->islands = NULL;
+
+	island_store->innercut_type = MISLAND_TYPE_NONE;
+	island_store->innercuts = NULL;
+
+	if (island_store->mem) {
+		BLI_memarena_clear(island_store->mem);
+	}
+
+	island_store->islands_num_alloc = 0;
+}
+
+void BKE_mesh_loop_islands_free(MeshIslandStore *island_store)
+{
+	if (island_store->mem) {
+		BLI_memarena_free(island_store->mem);
+		island_store->mem = NULL;
+	}
+}
+
+void BKE_mesh_loop_islands_add(
+        MeshIslandStore *island_store, const int item_num, int *items_indices,
+        const int num_island_items, int *island_item_indices,
+        const int num_innercut_items, int *innercut_item_indices)
+{
+	MemArena *mem = island_store->mem;
+
+	MeshElemMap *isld, *innrcut;
+	const int curr_island_idx = island_store->islands_num++;
+	const size_t curr_num_islands = (size_t)island_store->islands_num;
+	int i = item_num;
+
+	island_store->items_to_islands_num = item_num;
+	while (i--) {
+		island_store->items_to_islands[items_indices[i]] = curr_island_idx;
+	}
+
+	if (UNLIKELY(curr_num_islands > island_store->islands_num_alloc)) {
+		MeshElemMap **islds, **innrcuts;
+
+		island_store->islands_num_alloc *= 2;
+		islds = BLI_memarena_alloc(mem, sizeof(*islds) * island_store->islands_num_alloc);
+		memcpy(islds, island_store->islands, sizeof(*islds) * (curr_num_islands - 1));
+		island_store->islands = islds;
+
+		innrcuts = BLI_memarena_alloc(mem, sizeof(*innrcuts) * island_store->islands_num_alloc);
+		memcpy(innrcuts, island_store->innercuts, sizeof(*innrcuts) * (curr_num_islands - 1));
+		island_store->innercuts = innrcuts;
+	}
+
+	island_store->islands[curr_island_idx] = isld = BLI_memarena_alloc(mem, sizeof(*isld));
+	isld->count = num_island_items;
+	isld->indices = BLI_memarena_alloc(mem, sizeof(*isld->indices) * (size_t)num_island_items);
+	memcpy(isld->indices, island_item_indices, sizeof(*isld->indices) * (size_t)num_island_items);
+
+	island_store->innercuts[curr_island_idx] = innrcut = BLI_memarena_alloc(mem, sizeof(*innrcut));
+	innrcut->count = num_innercut_items;
+	innrcut->indices = BLI_memarena_alloc(mem, sizeof(*innrcut->indices) * (size_t)num_innercut_items);
+	memcpy(innrcut->indices, innercut_item_indices, sizeof(*innrcut->indices) * (size_t)num_innercut_items);
+}
+
+/* TODO: I'm not sure edge seam flag is enough to define UV islands? Maybe we should also consider UVmaps values
+ *       themselves (i.e. different UV-edges for a same mesh-edge => boundary edge too?).
+ *       Would make things much more complex though, and each UVMap would then need its own mesh mapping,
+ *       not sure we want that at all!
+ */
+static bool mesh_check_island_boundary_uv(
+        const MPoly *UNUSED(mp), const MLoop *UNUSED(ml), const MEdge *me,
+        const int UNUSED(nbr_egde_users))
+{
+	/* Edge is UV boundary if tagged as seam. */
+	return (me->flag & ME_SEAM) != 0;
+}
+
+/**
+ * \note all this could be optimized...
+ * Not sure it would be worth the more complex code, though, those loops
+ * are supposed to be really quick to do...
+ */
+bool BKE_mesh_calc_islands_loop_poly_uv(
+        MVert *UNUSED(verts), const int UNUSED(totvert),
+        MEdge *edges, const int totedge,
+        MPoly *polys, const int totpoly,
+        MLoop *loops, const int totloop,
+        MeshIslandStore *r_island_store)
+{
+	int *poly_groups = NULL;
+	int num_poly_groups;
+
+	/* map vars */
+	MeshElemMap *edge_poly_map;
+	int *edge_poly_mem;
+
+	int *poly_indices = MEM_mallocN(sizeof(*poly_indices) * (size_t)totpoly, __func__);
+	int *loop_indices = MEM_mallocN(sizeof(*loop_indices) * (size_t)totloop, __func__);
+	int num_pidx, num_lidx;
+
+	/* Those are used to detect 'inner cuts', i.e. edges that are borders, and yet have two or more polys of
+	 * a same group using them (typical case: seam used to unwrap properly a cylinder). */
+	BLI_bitmap *edge_borders;
+	int num_edge_borders;
+	char *edge_border_count = NULL;
+	int *edge_innercut_indices = NULL;
+	int num_einnercuts = 0;
+
+	int grp_idx, p_idx, pl_idx, l_idx;
+
+	BKE_mesh_loop_islands_clear(r_island_store);
+	BKE_mesh_loop_islands_init(r_island_store, MISLAND_TYPE_LOOP, totloop, MISLAND_TYPE_POLY, MISLAND_TYPE_EDGE);
+
+	BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem,
+	                              edges, totedge, polys, totpoly, loops, totloop);
+
+	poly_edge_loop_islands_calc(
+	        edges, totedge, polys, totpoly, loops, totloop, edge_poly_map, false,
+	        mesh_check_island_boundary_uv, &poly_groups, &num_poly_groups, &edge_borders, &num_edge_borders);
+
+	if (!num_poly_groups) {
+		/* Should never happen... */
+		return false;
+	}
+
+	if (num_edge_borders) {
+		edge_border_count = MEM_mallocN(sizeof(*edge_border_count) * (size_t)totedge, __func__);
+		edge_innercut_indices = MEM_mallocN(sizeof(*edge_innercut_indices) * (size_t)num_edge_borders, __func__);
+	}
+
+	/* Note: here we ignore '0' invalid group - this should *never* happen in this case anyway? */
+	for (grp_idx = 1; grp_idx <= num_poly_groups; grp_idx++) {
+		num_pidx = num_lidx = 0;
+		if (num_edge_borders) {
+			num_einnercuts = 0;
+			memset(edge_border_count, 0, sizeof(*edge_border_count) * (size_t)totedge);
+		}
+
+		for (p_idx = 0; p_idx < totpoly; p_idx++) {
+			MPoly *mp;
+
+			if (poly_groups[p_idx] != grp_idx) {
+				continue;
+			}
+
+			mp = &polys[p_idx];
+			poly_indices[num_pidx++] = p_idx;
+			for (l_idx = mp->loopstart, pl_idx = 0; pl_idx < mp->totloop; l_idx++, pl_idx++) {
+				MLoop *ml = &loops[l_idx];
+				loop_indices[num_lidx++] = l_idx;
+				if (num_edge_borders && BLI_BITMAP_TEST(edge_borders, ml->e) && (edge_border_count[ml->e] < 2)) {
+					edge_border_count[ml->e]++;
+					if (edge_border_count[ml->e] == 2) {
+						edge_innercut_indices[num_einnercuts++] = (int)ml->e;
+					}
+				}
+			}
+		}
+
+		BKE_mesh_loop_islands_add(r_island_store, num_lidx, loop_indices, num_pidx, poly_indices,
+		                          num_einnercuts, edge_innercut_indices);
+	}
+
+	MEM_freeN(poly_indices);
+	MEM_freeN(loop_indices);
+	MEM_freeN(poly_groups);
+	if (num_edge_borders) {
+		MEM_freeN(edge_border_count);
+		MEM_freeN(edge_innercut_indices);
+	}
+	return true;
+}
+
 /** \} */