Cleanup: add unique_index_table to UvElementMap

In anticipation of UV Copy+Paste, we need fast access to indices
of unique UvElements. Can also be used to improve performance and
simplify code for UV Sculpt tools and UV Stitch.

No user visible changes expected.

Maniphest Tasks: T77911

See also: D16278

3 files changed, 51 insertions, 2 deletions

diff --git a/source/blender/blenkernel/BKE_mesh_mapping.h b/source/blender/blenkernel/BKE_mesh_mapping.h
index 9d9c2f57f89..d0813ebb168 100644
--- a/source/blender/blenkernel/BKE_mesh_mapping.h
+++ b/source/blender/blenkernel/BKE_mesh_mapping.h
@@ -63,6 +63,10 @@ typedef struct UvElement {
  * If islands are calculated, it also stores UvElements
  * belonging to the same uv island in sequence and
  * the number of uvs per island.
+ *
+ * \note in C++, #head_table and #unique_index_table would
+ * be `mutable`, as they are created on demand, and never
+ * changed after creation.
  */
 typedef struct UvElementMap {
   /** UvElement Storage. */
@@ -78,6 +82,9 @@ typedef struct UvElementMap {
   /** If Non-NULL, pointer to local head of each unique UV. */
   struct UvElement **head_table;
 
+  /** If Non-NULL, pointer to index of each unique UV. */
+  int **unique_index_table;
+
   /** Number of islands, or zero if not calculated. */
   int total_islands;
   /** Array of starting index in #storage where each island begins. */
diff --git a/source/blender/editors/include/ED_mesh.h b/source/blender/editors/include/ED_mesh.h
index c100bf9b60b..7dfebf58bef 100644
--- a/source/blender/editors/include/ED_mesh.h
+++ b/source/blender/editors/include/ED_mesh.h
@@ -142,12 +142,15 @@ struct UvElementMap *BM_uv_element_map_create(struct BMesh *bm,
                                               bool use_seams,
                                               bool do_islands);
 void BM_uv_element_map_free(struct UvElementMap *element_map);
-struct UvElement *BM_uv_element_get(const struct UvElementMap *map,
+struct UvElement *BM_uv_element_get(const struct UvElementMap *element_map,
                                     const struct BMFace *efa,
                                     const struct BMLoop *l);
-struct UvElement *BM_uv_element_get_head(struct UvElementMap *map, struct UvElement *child);
+struct UvElement *BM_uv_element_get_head(struct UvElementMap *element_map,
+                                         struct UvElement *child);
+int BM_uv_element_get_unique_index(struct UvElementMap *element_map, struct UvElement *child);
 
 struct UvElement **BM_uv_element_map_ensure_head_table(struct UvElementMap *element_map);
+int **BM_uv_element_map_ensure_unique_index(struct UvElementMap *element_map);
 
 /**
  * Can we edit UV's for this mesh?
diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c
index f6ffbec094e..33162cd2256 100644
--- a/source/blender/editors/mesh/editmesh_utils.c
+++ b/source/blender/editors/mesh/editmesh_utils.c
@@ -619,6 +619,44 @@ struct UvElement **BM_uv_element_map_ensure_head_table(struct UvElementMap *elem
   return element_map->head_table;
 }
 
+int **BM_uv_element_map_ensure_unique_index(struct UvElementMap *element_map)
+{
+  if (!element_map->unique_index_table) {
+    element_map->unique_index_table = MEM_callocN(
+        element_map->total_uvs * sizeof(*element_map->unique_index_table), __func__);
+
+    int j = 0;
+    for (int i = 0; i < element_map->total_uvs; i++) {
+      UvElement *element = element_map->storage + i;
+      if (!element->separate) {
+        continue;
+      }
+      BLI_assert(0 <= j);
+      BLI_assert(j < element_map->total_unique_uvs);
+      while (element) {
+        element_map->unique_index_table[element - element_map->storage] = j;
+        element = element->next;
+        if (!element || element->separate) {
+          break;
+        }
+      }
+      j++;
+    }
+    BLI_assert(j == element_map->total_unique_uvs);
+  }
+
+  return element_map->unique_index_table;
+}
+
+int BM_uv_element_get_unique_index(struct UvElementMap *element_map, struct UvElement *child)
+{
+  int **unique_index = BM_uv_element_map_ensure_unique_index(element_map);
+  int index = child - element_map->storage;
+  BLI_assert(0 <= index);
+  BLI_assert(index < element_map->total_uvs);
+  return unique_index[index];
+}
+
 #define INVALID_ISLAND ((uint)-1)
 
 static void bm_uv_assign_island(UvElementMap *element_map,
@@ -1163,6 +1201,7 @@ void BM_uv_element_map_free(UvElementMap *element_map)
     MEM_SAFE_FREE(element_map->storage);
     MEM_SAFE_FREE(element_map->vertex);
     MEM_SAFE_FREE(element_map->head_table);
+    MEM_SAFE_FREE(element_map->unique_index_table);
     MEM_SAFE_FREE(element_map->island_indices);
     MEM_SAFE_FREE(element_map->island_total_uvs);
     MEM_SAFE_FREE(element_map->island_total_unique_uvs);