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, 61 insertions, 2 deletions

diff --git a/source/blender/blenkernel/BKE_mesh_mapping.h b/source/blender/blenkernel/BKE_mesh_mapping.h
index ed7e506941c..da44c989146 100644
--- a/source/blender/blenkernel/BKE_mesh_mapping.h
+++ b/source/blender/blenkernel/BKE_mesh_mapping.h
@@ -31,8 +31,9 @@
  *  \ingroup bke
  */
 
-struct MPoly;
+struct MVert;
 struct MEdge;
+struct MPoly;
 struct MLoop;
 struct MLoopUV;
 
@@ -109,6 +110,10 @@ void BKE_mesh_vert_poly_map_create(
         MeshElemMap **r_map, int **r_mem,
         const struct MPoly *mface, const struct MLoop *mloop,
         int totvert, int totface, int totloop);
+void BKE_mesh_vert_loop_map_create(
+        MeshElemMap **r_map, int **r_mem,
+        const struct MPoly *mface, const struct MLoop *mloop,
+        int totvert, int totface, int totloop);
 void BKE_mesh_vert_edge_map_create(
         MeshElemMap **r_map, int **r_mem,
         const struct MEdge *medge, int totvert, int totedge);
@@ -122,7 +127,61 @@ void BKE_mesh_origindex_map_create(
         const int totorig,
         const int *final_origindex, const int totfinal);
 
-/* smoothgroups */
+
+/* islands */
+
+/* Loop islands data helpers. */
+enum {
+	MISLAND_TYPE_NONE = 0,
+	MISLAND_TYPE_VERT = 1,
+	MISLAND_TYPE_EDGE = 2,
+	MISLAND_TYPE_POLY = 3,
+	MISLAND_TYPE_LOOP = 4,
+};
+
+typedef struct MeshIslandStore {
+	short item_type;      /* MISLAND_TYPE_... */
+	short island_type;    /* MISLAND_TYPE_... */
+	short innercut_type;  /* MISLAND_TYPE_... */
+
+	int  items_to_islands_num;
+	int *items_to_islands;  /* map the item to the island index */
+
+	int                  islands_num;
+	size_t               islands_num_alloc;
+	struct MeshElemMap **islands;    /* Array of pointers, one item per island. */
+	struct MeshElemMap **innercuts;  /* Array of pointers, one item per island. */
+
+	struct MemArena *mem;  /* Memory arena, internal use only. */
+} MeshIslandStore;
+
+void BKE_mesh_loop_islands_init(
+        MeshIslandStore *island_store,
+        const short item_type, const int item_num, const short island_type, const short innercut_type);
+void BKE_mesh_loop_islands_clear(MeshIslandStore *island_store);
+void BKE_mesh_loop_islands_free(MeshIslandStore *island_store);
+void BKE_mesh_loop_islands_add(
+        MeshIslandStore *islands, const int item_num, int *item_indices,
+        const int num_island_items, int *island_item_indices,
+        const int num_innercut_items, int *innercut_item_indices);
+
+typedef bool (*MeshRemapIslandsCalc)(
+        struct MVert *verts, const int totvert,
+        struct MEdge *edges, const int totedge,
+        struct MPoly *polys, const int totpoly,
+        struct MLoop *loops, const int totloop,
+        struct MeshIslandStore *r_island_store);
+
+/* Above vert/UV mapping stuff does not do what we need here, but does things we do not need here.
+ * So better keep them separated for now, I think.
+ */
+bool BKE_mesh_calc_islands_loop_poly_uv(
+        struct MVert *verts, const int totvert,
+        struct MEdge *edges, const int totedge,
+        struct MPoly *polys, const int totpoly,
+        struct MLoop *loops, const int totloop,
+        MeshIslandStore *r_island_store);
+
 int *BKE_mesh_calc_smoothgroups(
         const struct MEdge *medge, const int totedge,
         const struct MPoly *mpoly, const int totpoly,