UV: implement copy and paste for uv

Implement a new topology-based copy and paste solution for UVs.

Usage notes:

* Open the UV Editor

* Use the selection tools to select a Quad joined to a Triangle joined to another Quad.
* From the menu, choose UV > UV Copy
 * The UV co-ordinates for your quad<=>tri<=>quad are now stored internally

* Use the selection tools to select a different Quad joined to a Triangle joined to a Quad.
* (Optional) From the menu, choose UV > Split > Selection

* From the menu, choose UV > UV Paste
 * The UV co-ordinates for the new selection will be moved to match the stored UVs.

Repeat selection / UV Paste steps as many times as desired.
For performance considerations, see https://en.wikipedia.org/wiki/Graph_isomorphism_problem

In theory, UV Copy and Paste should work with all UV selection modes.
Please report any problems.

A copy has been made of the Graph Isomorphism code from https://github.com/stefanoquer/graphISO
Copyright (c) 2019 Stefano Quer stefano.quer@polito.it GPL v3 or later.

Additional integration code Copyright (c) 2022 by Blender Foundation, GPL v2 or later.

Maniphest Tasks: T77911
Differential Revision: https://developer.blender.org/D16278

release/scripts/startup/bl_ui/space_image.py

@@ -440,6 +440,11 @@ class IMAGE_MT_uvs(Menu):
 
         layout.separator()
 
+        layout.operator("uv.copy")
+        layout.operator("uv.paste")
+
+        layout.separator()
+
         layout.menu("IMAGE_MT_uvs_showhide")
 
         layout.separator()

source/blender/blenkernel/BKE_mesh_mapping.h

@@ -343,6 +343,9 @@ int *BKE_mesh_calc_smoothgroups(const struct MEdge *medge,
 #endif
 
 #ifdef __cplusplus
+
+#  include "DNA_meshdata_types.h" /* MPoly */
+
 namespace blender::bke::mesh_topology {
 
 Array<int> build_loop_to_poly_map(Span<MPoly> polys, int loops_num);

source/blender/editors/uvedit/CMakeLists.txt

@@ -21,6 +21,8 @@ set(INC
 
 set(SRC
   uvedit_buttons.c
+  uvedit_clipboard.cc
+  uvedit_clipboard_graph_iso.cc
   uvedit_draw.c
   uvedit_islands.cc
   uvedit_ops.c
@@ -30,6 +32,7 @@ set(SRC
   uvedit_smart_stitch.c
   uvedit_unwrap_ops.c
 
+  uvedit_clipboard_graph_iso.hh
   uvedit_intern.h
 )
 

source/blender/editors/uvedit/uvedit_clipboard.cc

@@ -0,0 +1,369 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later
+ * Copyright 2022 Blender Foundation. All rights reserved. */
+
+/** \file
+ * \ingroup eduv
+ *
+ * Attempt to find a graph isomorphism between the topology of two different UV islands.
+ *
+ * \note On terminology, for the purposes of this file:
+ * * An iso_graph is a "Graph" in Graph Theory.
+ *  * An iso_graph has an unordered set of iso_verts.
+ *  * An iso_graph has an unordered set of iso_edges.
+ * * An iso_vert is a "Vertex" in Graph Theory
+ *   * Each iso_vert has a label.
+ * * An iso_edge is an "Edge" in Graph Theory
+ *   * Each iso_edge connects two iso_verts.
+ *   * An iso_edge is undirected.
+ */
+
+#include "BLI_math.h"
+
+#include "BKE_context.h"
+#include "BKE_customdata.h"
+#include "BKE_editmesh.h"
+#include "BKE_layer.h"
+#include "BKE_mesh_mapping.h" /* UvElementMap */
+
+#include "DEG_depsgraph.h"
+
+#include "ED_mesh.h"
+#include "ED_screen.h"
+#include "ED_uvedit.h" /* Own include. */
+
+#include "WM_api.h"
+
+#include "uvedit_clipboard_graph_iso.hh"
+#include "uvedit_intern.h" /* linker, extern "C" */
+
+extern "C" {
+void UV_clipboard_free(void);
+}
+
+class UV_ClipboardBuffer {
+ public:
+  ~UV_ClipboardBuffer();
+
+  void append(UvElementMap *element_map, const int cd_loop_uv_offset);
+  bool find_isomorphism(UvElementMap *dest_element_map,
+                        int island_index,
+                        blender::Vector<int> &r_label,
+                        int cd_loop_uv_offset);
+
+  void write_uvs(UvElementMap *element_map,
+                 int island_index,
+                 const int cd_loop_uv_offset,
+                 const blender::Vector<int> &label);
+
+ private:
+  blender::Vector<GraphISO *> graph;
+  blender::Vector<int> offset;
+  blender::Vector<std::pair<float, float>> uv;
+};
+
+static UV_ClipboardBuffer *uv_clipboard = nullptr;
+
+UV_ClipboardBuffer::~UV_ClipboardBuffer()
+{
+  for (const int index : graph.index_range()) {
+    delete graph[index];
+  }
+  graph.clear();
+  offset.clear();
+  uv.clear();
+}
+
+/* Given a `BMLoop`, possibly belonging to an island in a `UvElementMap`,
+ * return the `iso_index` corresponding to it's representation
+ * in the `iso_graph`.
+ *
+ * If the `BMLoop` is not part of the `iso_graph`, return -1.
+ */
+static int iso_index_for_loop(const BMLoop *loop,
+                              UvElementMap *element_map,
+                              const int island_index)
+{
+  UvElement *element = BM_uv_element_get(element_map, loop->f, loop);
+  if (!element) {
+    return -1; /* Either unselected, or a different island. */
+  }
+  const int index = BM_uv_element_get_unique_index(element_map, element);
+  const int base_index = BM_uv_element_get_unique_index(
+      element_map, element_map->storage + element_map->island_indices[island_index]);
+  return index - base_index;
+}
+
+/* Add an `iso_edge` to an `iso_graph` between two BMLoops.
+ */
+static void add_iso_edge(
+    GraphISO *graph, BMLoop *loop_v, BMLoop *loop_w, UvElementMap *element_map, int island_index)
+{
+  BLI_assert(loop_v->f == loop_w->f); /* Ensure on the same face. */
+  const int index_v = iso_index_for_loop(loop_v, element_map, island_index);
+  const int index_w = iso_index_for_loop(loop_w, element_map, island_index);
+  BLI_assert(index_v != index_w);
+  if (index_v == -1 || index_w == -1) {
+    return; /* Unselected. */
+  }
+
+  BLI_assert(0 <= index_v && index_v < graph->n);
+  BLI_assert(0 <= index_w && index_w < graph->n);
+
+  graph->add_edge(index_v, index_w);
+}
+
+/* Build an `iso_graph` representation of an island of a `UvElementMap`.
+ */
+GraphISO *build_iso_graph(UvElementMap *element_map, const int island_index, int cd_loop_uv_offset)
+{
+  GraphISO *g = new GraphISO(element_map->island_total_unique_uvs[island_index]);
+  for (int i = 0; i < g->n; i++) {
+    g->label[i] = i;
+  }
+
+  const int i0 = element_map->island_indices[island_index];
+  const int i1 = i0 + element_map->island_total_uvs[island_index];
+
+  /* Add iso_edges. */
+  for (int i = i0; i < i1; i++) {
+    const UvElement *element = element_map->storage + i;
+    /* Look forward around the current face. */
+    add_iso_edge(g, element->l, element->l->next, element_map, island_index);
+
+    /* Look backward around the current face.
+     * (Required for certain vertex selection cases.)
+     */
+    add_iso_edge(g, element->l->prev, element->l, element_map, island_index);
+  }
+
+  /* TODO: call g->sort_vertices_by_degree() */
+
+  return g;
+}
+
+/* Convert each island inside an `element_map` into an `iso_graph`, and append them to the
+ * clipboard buffer. */
+void UV_ClipboardBuffer::append(UvElementMap *element_map, const int cd_loop_uv_offset)
+{
+  for (int island_index = 0; island_index < element_map->total_islands; island_index++) {
+    offset.append(uv.size());
+    graph.append(build_iso_graph(element_map, island_index, cd_loop_uv_offset));
+
+    /* TODO: Consider iterating over `BM_uv_element_map_ensure_unique_index` instead. */
+    for (int j = 0; j < element_map->island_total_uvs[island_index]; j++) {
+      UvElement *element = element_map->storage + element_map->island_indices[island_index] + j;
+      if (!element->separate) {
+        continue;
+      }
+      MLoopUV *luv = static_cast<MLoopUV *>(BM_ELEM_CD_GET_VOID_P(element->l, cd_loop_uv_offset));
+      uv.append(std::make_pair(luv->uv[0], luv->uv[1]));
+    }
+  }
+}
+
+/* Write UVs back to an island. */
+void UV_ClipboardBuffer::write_uvs(UvElementMap *element_map,
+                                   int island_index,
+                                   const int cd_loop_uv_offset,
+                                   const blender::Vector<int> &label)
+{
+  BLI_assert(label.size() == element_map->island_total_unique_uvs[island_index]);
+
+  /* TODO: Consider iterating over `BM_uv_element_map_ensure_unique_index` instead. */
+  int unique_uv = 0;
+  for (int j = 0; j < element_map->island_total_uvs[island_index]; j++) {
+    int k = element_map->island_indices[island_index] + j;
+    UvElement *element = element_map->storage + k;
+    if (!element->separate) {
+      continue;
+    }
+    BLI_assert(0 <= unique_uv);
+    BLI_assert(unique_uv < label.size());
+    const std::pair<float, float> &source_uv = uv_clipboard->uv[label[unique_uv]];
+    while (element) {
+      MLoopUV *luv = static_cast<MLoopUV *>(BM_ELEM_CD_GET_VOID_P(element->l, cd_loop_uv_offset));
+      luv->uv[0] = source_uv.first;
+      luv->uv[1] = source_uv.second;
+      element = element->next;
+      if (!element || element->separate) {
+        break;
+      }
+    }
+    unique_uv++;
+  }
+  BLI_assert(unique_uv == label.size());
+}
+
+/* Call the external isomorphism solver. */
+static bool find_isomorphism(UvElementMap *dest,
+                             const int dest_island_index,
+                             GraphISO *graph_source,
+                             blender::Vector<int> &r_label,
+                             int cd_loop_uv_offset)
+{
+
+  const int island_total_unique_uvs = dest->island_total_unique_uvs[dest_island_index];
+  if (island_total_unique_uvs != graph_source->n) {
+    return false; /* Isomorphisms can't differ in |iso_vert|. */
+  }
+  r_label.resize(island_total_unique_uvs);
+
+  GraphISO *graph_dest = build_iso_graph(dest, dest_island_index, cd_loop_uv_offset);
+
+  int(*solution)[2] = (int(*)[2])MEM_mallocN(graph_source->n * sizeof(*solution), __func__);
+  int solution_length = 0;
+  const bool result = ED_uvedit_clipboard_maximum_common_subgraph(
+      graph_source, graph_dest, solution, &solution_length);
+
+  /* Todo: Implement "Best Effort" / "Nearest Match" paste functionality here. */
+
+  if (result) {
+    BLI_assert(solution_length == dest->island_total_unique_uvs[dest_island_index]);
+    for (int i = 0; i < solution_length; i++) {
+      int index_s = solution[i][0];
+      int index_t = solution[i][1];
+      BLI_assert(0 <= index_s && index_s < solution_length);
+      BLI_assert(0 <= index_t && index_t < solution_length);
+      r_label[index_t] = index_s;
+    }
+  }
+
+  MEM_SAFE_FREE(solution);
+  delete graph_dest;
+  return result;
+}
+
+bool UV_ClipboardBuffer::find_isomorphism(UvElementMap *dest_element_map,
+                                          int dest_island_index,
+                                          blender::Vector<int> &r_label,
+                                          int cd_loop_uv_offset)
+{
+  for (int source_island_index : graph.index_range()) {
+    if (::find_isomorphism(dest_element_map,
+                           dest_island_index,
+                           graph[source_island_index],
+                           r_label,
+                           cd_loop_uv_offset)) {
+      const int island_total_unique_uvs =
+          dest_element_map->island_total_unique_uvs[dest_island_index];
+      const int island_offset = offset[source_island_index];
+      BLI_assert(island_total_unique_uvs == r_label.size());
+      for (int i = 0; i < island_total_unique_uvs; i++) {
+        r_label[i] += island_offset; /* TODO: (minor optimization) Defer offset. */
+      }
+
+      /* TODO: There may be more than one match. How to choose between them? */
+      return true;
+    }
+  }
+
+  return false;
+}
+
+static int uv_copy_exec(bContext *C, wmOperator *op)
+{
+  UV_clipboard_free();
+  uv_clipboard = new UV_ClipboardBuffer();
+
+  ViewLayer *view_layer = CTX_data_view_layer(C);
+  Scene *scene = CTX_data_scene(C);
+
+  uint objects_len = 0;
+  Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(
+      scene, view_layer, ((View3D *)NULL), &objects_len);
+
+  for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+    Object *ob = objects[ob_index];
+    BMEditMesh *em = BKE_editmesh_from_object(ob);
+
+    const bool use_seams = false;
+    UvElementMap *element_map = BM_uv_element_map_create(
+        em->bm, scene, true, false, use_seams, true);
+
+    const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+    uv_clipboard->append(element_map, cd_loop_uv_offset);
+    BM_uv_element_map_free(element_map);
+  }
+
+  MEM_freeN(objects);
+
+  /* TODO: Serialize `UvClipboard` to system clipboard. */
+
+  return OPERATOR_FINISHED;
+}
+
+static int uv_paste_exec(bContext *C, wmOperator *op)
+{
+  /* TODO: Restore `UvClipboard` from system clipboard. */
+  if (!uv_clipboard) {
+    return OPERATOR_FINISHED; /* Nothing to do. */
+  }
+  ViewLayer *view_layer = CTX_data_view_layer(C);
+  Scene *scene = CTX_data_scene(C);
+
+  uint objects_len = 0;
+  Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(
+      scene, view_layer, ((View3D *)NULL), &objects_len);
+
+  for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+    Object *ob = objects[ob_index];
+    BMEditMesh *em = BKE_editmesh_from_object(ob);
+
+    const bool use_seams = false;
+    const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+
+    UvElementMap *dest_element_map = BM_uv_element_map_create(
+        em->bm, scene, true, false, use_seams, true);
+
+    for (int i = 0; i < dest_element_map->total_islands; i++) {
+      blender::Vector<int> label;
+      const bool found = uv_clipboard->find_isomorphism(
+          dest_element_map, i, label, cd_loop_uv_offset);
+      if (!found) {
+        continue; /* No source UVs can be found that is isomorphic to this island. */
+      }
+
+      uv_clipboard->write_uvs(dest_element_map, i, cd_loop_uv_offset, label);
+    }
+
+    BM_uv_element_map_free(dest_element_map);
+    DEG_id_tag_update(static_cast<ID *>(ob->data), 0);
+    WM_event_add_notifier(C, NC_GEOM | ND_DATA, ob->data);
+  }
+
+  MEM_freeN(objects);
+
+  return OPERATOR_FINISHED;
+}
+
+void UV_OT_copy(wmOperatorType *ot)
+{
+  /* identifiers */
+  ot->name = "Copy UVs";
+  ot->description = "Copy selected UV vertices";
+  ot->idname = "UV_OT_copy";
+  ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+  /* api callbacks */
+  ot->exec = uv_copy_exec;
+  ot->poll = ED_operator_uvedit;
+}
+
+void UV_OT_paste(wmOperatorType *ot)
+{
+  /* identifiers */
+  ot->name = "Paste UVs";
+  ot->description = "Paste selected UV vertices";
+  ot->idname = "UV_OT_paste";
+  ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+  /* api callbacks */
+  ot->exec = uv_paste_exec;
+  ot->poll = ED_operator_uvedit;
+}
+
+void UV_clipboard_free()
+{
+  delete uv_clipboard;
+  uv_clipboard = nullptr;
+}

source/blender/editors/uvedit/uvedit_clipboard_graph_iso.cc

@@ -0,0 +1,419 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later
+ * Copyright (c) 2019 Stefano Quer.
+ * Additional code, copyright 2022 Blender Foundation. All rights reserved.
+ *
+ * Originally 6846114 from https://github.com/stefanoquer/graphISO/blob/master/v3
+ * graphISO: Tools to compute the Maximum Common Subgraph between two graphs.
+ */
+
+#include "uvedit_clipboard_graph_iso.hh"
+
+#include "BLI_assert.h"
+
+#include "MEM_guardedalloc.h"
+
+#include <algorithm>
+#include <limits.h>
+
+#define L 0
+#define R 1
+#define LL 2
+#define RL 3
+#define ADJ 4
+#define P 5
+#define W 6
+#define IRL 7
+
+#define BDS 8
+
+GraphISO::GraphISO(int n)
+{
+  this->n = n;
+  label = static_cast<uint *>(MEM_mallocN(n * sizeof *label, __func__));
+  adjmat = static_cast<uint8_t **>(MEM_mallocN(n * sizeof *adjmat, __func__));
+
+  /* \note Allocation of `n * n` bytes total! */
+
+  for (int i = 0; i < n; i++) {
+    /* Caution, are you trying to change the representation of adjmat?
+     * Consider `blender::Vector<std::pair<int, int>> adjmat;` instead.
+     * Better still is to use a different algorithm. See for example:
+     * https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/beatcs09.pdf
+     */
+    adjmat[i] = static_cast<unsigned char *>(MEM_callocN(n * sizeof *adjmat[i], __func__));
+  }
+  degree = nullptr;
+}
+
+GraphISO::~GraphISO()
+{
+  for (int i = 0; i < n; i++) {
+    MEM_freeN(adjmat[i]);
+  }
+  MEM_freeN(adjmat);
+  MEM_freeN(label);
+  if (degree) {
+    MEM_freeN(degree);
+  }
+}
+
+void GraphISO::add_edge(int v, int w)
+{
+  BLI_assert(v != w);
+  adjmat[v][w] = 1;
+  adjmat[w][v] = 1;
+}
+
+void GraphISO::calculate_degrees() const
+{
+  if (degree) {
+    return;
+  }
+  degree = static_cast<unsigned int *>(MEM_mallocN(n * sizeof *degree, __func__));
+  for (int v = 0; v < n; v++) {
+    int row_count = 0;
+    for (int w = 0; w < n; w++) {
+      if (adjmat[v][w]) {
+        row_count++;
+      }
+    }
+    degree[v] = row_count;
+  }
+}
+
+class GraphISO_DegreeCompare {
+ public:
+  GraphISO_DegreeCompare(const GraphISO *g)
+  {
+    this->g = g;
+  }
+  const GraphISO *g;
+
+  bool operator()(int i, int j) const
+  {
+    return g->degree[i] < g->degree[j];
+  }
+};
+
+GraphISO *GraphISO::sort_vertices_by_degree() const
+{
+  calculate_degrees();
+
+  int *vv = static_cast<int *>(MEM_mallocN(n * sizeof *vv, __func__));
+  for (int i = 0; i < n; i++) {
+    vv[i] = i;
+  }
+  /* Currently ordering iso_verts by degree.
+   * Instead should order iso_verts by frequency of degree. */
+  GraphISO_DegreeCompare compare_obj(this);
+  std::sort(vv, vv + n, compare_obj);
+
+  GraphISO *subg = new GraphISO(n);
+  for (int i = 0; i < n; i++) {
+    for (int j = 0; j < n; j++) {
+      subg->adjmat[i][j] = adjmat[vv[i]][vv[j]];
+    }
+  }
+  for (int i = 0; i < n; i++) {
+    subg->label[i] = label[vv[i]];
+  }
+  subg->calculate_degrees();
+
+  MEM_freeN(vv);
+  return subg;
+}
+
+static void update_incumbent(uint8_t cur[][2], int inc[][2], int cur_pos, int *inc_pos)
+{
+  if (cur_pos > *inc_pos) {
+    *inc_pos = cur_pos;
+    for (int i = 0; i < cur_pos; i++) {
+      inc[i][L] = cur[i][L];
+      inc[i][R] = cur[i][R];
+    }
+  }
+}
+
+static void add_bidomain(uint8_t domains[][BDS],
+                         int *bd_pos,
+                         uint8_t left_i,
+                         uint8_t right_i,
+                         uint8_t left_len,
+                         uint8_t right_len,
+                         uint8_t is_adjacent,
+                         uint8_t cur_pos)
+{
+  domains[*bd_pos][L] = left_i;
+  domains[*bd_pos][R] = right_i;
+  domains[*bd_pos][LL] = left_len;
+  domains[*bd_pos][RL] = right_len;
+  domains[*bd_pos][ADJ] = is_adjacent;
+  domains[*bd_pos][P] = cur_pos;
+  domains[*bd_pos][W] = UINT8_MAX;
+  domains[*bd_pos][IRL] = right_len;
+  (*bd_pos)++;
+}
+
+static int calc_bound(uint8_t domains[][BDS], int bd_pos, int cur_pos)
+{
+  int bound = 0;
+  for (int i = bd_pos - 1; i >= 0 && domains[i][P] == cur_pos; i--) {
+    bound += std::min(domains[i][LL], domains[i][IRL]);
+  }
+  return bound;
+}
+
+static int partition(uint8_t *arr, int start, int len, const uint8_t *adjrow)
+{
+  int i = 0;
+  for (int j = 0; j < len; j++) {
+    if (adjrow[arr[start + j]]) {
+      std::swap(arr[start + i], arr[start + j]);
+      i++;
+    }
+  }
+  return i;
+}
+
+static void generate_next_domains(uint8_t domains[][BDS],
+                                  int *bd_pos,
+                                  int cur_pos,
+                                  uint8_t *left,
+                                  uint8_t *right,
+                                  uint8_t v,
+                                  uint8_t w,
+                                  int inc_pos,
+                                  uint8_t **adjmat0,
+                                  uint8_t **adjmat1)
+{
+  int i;
+  int bd_backup = *bd_pos;
+  int bound = 0;
+  uint8_t *bd;
+  for (i = *bd_pos - 1, bd = &domains[i][L]; i >= 0 && bd[P] == cur_pos - 1;
+       i--, bd = &domains[i][L]) {
+
+    uint8_t l_len = partition(left, bd[L], bd[LL], adjmat0[v]);
+    uint8_t r_len = partition(right, bd[R], bd[RL], adjmat1[w]);
+
+    if (bd[LL] - l_len && bd[RL] - r_len) {
+      add_bidomain(domains,
+                   bd_pos,
+                   bd[L] + l_len,
+                   bd[R] + r_len,
+                   bd[LL] - l_len,
+                   bd[RL] - r_len,
+                   bd[ADJ],
+                   (uint8_t)(cur_pos));
+      bound += std::min(bd[LL] - l_len, bd[RL] - r_len);
+    }
+    if (l_len && r_len) {
+      add_bidomain(domains, bd_pos, bd[L], bd[R], l_len, r_len, true, (uint8_t)(cur_pos));
+      bound += std::min(l_len, r_len);
+    }
+  }
+  if (cur_pos + bound <= inc_pos) {
+    *bd_pos = bd_backup;
+  }
+}
+
+static uint8_t select_next_v(uint8_t *left, uint8_t *bd)
+{
+  uint8_t min = UINT8_MAX;
+  uint8_t idx = UINT8_MAX;
+  if (bd[RL] != bd[IRL]) {
+    return left[bd[L] + bd[LL]];
+  }
+  for (uint8_t i = 0; i < bd[LL]; i++) {
+    if (left[bd[L] + i] < min) {
+      min = left[bd[L] + i];
+      idx = i;
+    }
+  }
+  std::swap(left[bd[L] + idx], left[bd[L] + bd[LL] - 1]);
+  bd[LL]--;
+  bd[RL]--;
+  return min;
+}
+
+static uint8_t find_min_value(uint8_t *arr, uint8_t start_idx, uint8_t len)
+{
+  uint8_t min_v = UINT8_MAX;
+  for (int i = 0; i < len; i++) {
+    if (arr[start_idx + i] < min_v) {
+      min_v = arr[start_idx + i];
+    }
+  }
+  return min_v;
+}
+
+static void select_bidomain(
+    uint8_t domains[][BDS], int bd_pos, uint8_t *left, int current_matching_size, bool connected)
+{
+  int i;
+  int min_size = INT_MAX;
+  int min_tie_breaker = INT_MAX;
+  int best = INT_MAX;
+  uint8_t *bd;
+  for (i = bd_pos - 1, bd = &domains[i][L]; i >= 0 && bd[P] == current_matching_size;
+       i--, bd = &domains[i][L]) {
+    if (connected && current_matching_size > 0 && !bd[ADJ]) {
+      continue;
+    }
+    int len = bd[LL] > bd[RL] ? bd[LL] : bd[RL];
+    if (len < min_size) {
+      min_size = len;
+      min_tie_breaker = find_min_value(left, bd[L], bd[LL]);
+      best = i;
+    }
+    else if (len == min_size) {
+      int tie_breaker = find_min_value(left, bd[L], bd[LL]);
+      if (tie_breaker < min_tie_breaker) {
+        min_tie_breaker = tie_breaker;
+        best = i;
+      }
+    }
+  }
+  if (best != INT_MAX && best != bd_pos - 1) {
+    uint8_t tmp[BDS];
+    for (i = 0; i < BDS; i++) {
+      tmp[i] = domains[best][i];
+    }
+    for (i = 0; i < BDS; i++) {
+      domains[best][i] = domains[bd_pos - 1][i];
+    }
+    for (i = 0; i < BDS; i++) {
+      domains[bd_pos - 1][i] = tmp[i];
+    }
+  }
+}
+
+static uint8_t select_next_w(uint8_t *right, uint8_t *bd)
+{
+  uint8_t min = UINT8_MAX;
+  uint8_t idx = UINT8_MAX;
+  for (uint8_t i = 0; i < bd[RL] + 1; i++) {
+    if ((right[bd[R] + i] > bd[W] || bd[W] == UINT8_MAX) && right[bd[R] + i] < min) {
+      min = right[bd[R] + i];
+      idx = i;
+    }
+  }
+  if (idx == UINT8_MAX) {
+    bd[RL]++;
+  }
+  return idx;
+}
+
+static void maximum_common_subgraph_internal(
+    int incumbent[][2], int *inc_pos, uint8_t **adjmat0, int n0, uint8_t **adjmat1, int n1)
+{
+  int min = std::min(n0, n1);
+
+  uint8_t cur[min][2];
+  uint8_t domains[min * min][BDS];
+  uint8_t left[n0], right[n1];
+  uint8_t v, w, *bd;
+  int bd_pos = 0;
+  for (int i = 0; i < n0; i++) {
+    left[i] = i;
+  }
+  for (int i = 0; i < n1; i++) {
+    right[i] = i;
+  }
+  add_bidomain(domains, &bd_pos, 0, 0, n0, n1, 0, 0);
+
+  int iteration_count = 0;
+
+  while (bd_pos > 0) {
+    if (iteration_count++ > 10000000) {
+      /* Unlikely to find a solution, may as well give up.
+       * Can occur with moderate sized inputs where the graph has lots of symmetry, e.g. a cube
+       * subdivided 3x times.
+       */
+      return;
+    }
+    bd = &domains[bd_pos - 1][L];
+    if (calc_bound(domains, bd_pos, bd[P]) + bd[P] <= *inc_pos ||
+        (bd[LL] == 0 && bd[RL] == bd[IRL])) {
+      bd_pos--;
+    }
+    else {
+      const bool connected = false;
+      select_bidomain(domains, bd_pos, left, domains[bd_pos - 1][P], connected);
+      v = select_next_v(left, bd);
+      if ((bd[W] = select_next_w(right, bd)) != UINT8_MAX) {
+        w = right[bd[R] + bd[W]]; /* Swap the W after the bottom of the current right domain. */
+        right[bd[R] + bd[W]] = right[bd[R] + bd[RL]];
+        right[bd[R] + bd[RL]] = w;
+        bd[W] = w; /* Store the W used for this iteration. */
+        cur[bd[P]][L] = v;
+        cur[bd[P]][R] = w;
+        update_incumbent(cur, incumbent, bd[P] + (uint8_t)1, inc_pos);
+        generate_next_domains(
+            domains, &bd_pos, bd[P] + 1, left, right, v, w, *inc_pos, adjmat0, adjmat1);
+      }
+    }
+  }
+}
+
+static bool check_automorphism(const GraphISO *g0,
+                               const GraphISO *g1,
+                               int solution[][2],
+                               int *solution_length)
+{
+  if (g0->n != g1->n) {
+    return false;
+  }
+  for (int i = 0; i < g0->n; i++) {
+    if (g0->label[i] != g1->label[i]) {
+      return false;
+    }
+    for (int j = 0; j < g0->n; j++) {
+      if (g0->adjmat[i][j] != g1->adjmat[i][j]) {
+        return false;
+      }
+    }
+    solution[i][0] = i;
+    solution[i][1] = i;
+  }
+  *solution_length = g0->n;
+  return true;
+}
+
+bool ED_uvedit_clipboard_maximum_common_subgraph(GraphISO *g0_input,
+                                                 GraphISO *g1_input,
+                                                 int solution[][2],
+                                                 int *solution_length)
+{
+  if (check_automorphism(g0_input, g1_input, solution, solution_length)) {
+    return true;
+  }
+
+  int n0 = g0_input->n;
+  int n1 = g1_input->n;
+
+  int min_size = std::min(n0, n1);
+  if (min_size >= UINT8_MAX - 2) {
+    return false;
+  }
+
+  GraphISO *g0 = g0_input->sort_vertices_by_degree();
+  GraphISO *g1 = g1_input->sort_vertices_by_degree();
+
+  int sol_len = 0;
+  maximum_common_subgraph_internal(solution, &sol_len, g0->adjmat, n0, g1->adjmat, n1);
+  *solution_length = sol_len;
+
+  bool result = (sol_len == n0);
+  if (result) {
+    for (int i = 0; i < sol_len; i++) {
+      solution[i][0] = g0->label[solution[i][0]]; /* Index from input. */
+      solution[i][1] = g1->label[solution[i][1]];
+    }
+  }
+
+  delete g1;
+  delete g0;
+
+  return result;
+}

source/blender/editors/uvedit/uvedit_clipboard_graph_iso.hh

@@ -0,0 +1,40 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later
+ * Copyright (c) 2019 Stefano Quer.
+ * Additional code, copyright 2022 Blender Foundation. All rights reserved.
+ *
+ * Originally 6846114 from https://github.com/stefanoquer/graphISO/blob/master/v3
+ * graphISO: Tools to compute the Maximum Common Subgraph between two graphs.
+ */
+
+/** \file
+ * \ingroup eduv
+ */
+
+#pragma once
+
+#include <sys/types.h>
+
+/* A thin representation of a "Graph" in graph theory. */
+class GraphISO {
+ public:
+  GraphISO(int n);
+  ~GraphISO();
+  int n;
+  uint8_t **adjmat;
+  uint *label;
+  mutable uint *degree;
+
+  void add_edge(int v, int w);
+  GraphISO *sort_vertices_by_degree() const;
+
+ private:
+  void calculate_degrees() const;
+};
+
+/* Find the maximum common subgraph between two graphs.
+ * (Can be used to find graph ismorphism.)
+ */
+bool ED_uvedit_clipboard_maximum_common_subgraph(GraphISO *,
+                                                 GraphISO *,
+                                                 int solution[][2],
+                                                 int *solution_length);

source/blender/editors/uvedit/uvedit_intern.h

@@ -7,6 +7,10 @@
 
 #pragma once
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 struct BMFace;
 struct BMLoop;
 struct Object;
@@ -146,6 +150,10 @@ void UV_OT_rip(struct wmOperatorType *ot);
 void UV_OT_stitch(struct wmOperatorType *ot);
 void UV_OT_smart_project(struct wmOperatorType *ot);
 
+/* uvedit_copy_paste.cc */
+void UV_OT_copy(wmOperatorType *ot);
+void UV_OT_paste(wmOperatorType *ot);
+
 /* uvedit_path.c */
 
 void UV_OT_shortest_path_pick(struct wmOperatorType *ot);
@@ -182,3 +190,7 @@ void UV_OT_select_overlap(struct wmOperatorType *ot);
 void UV_OT_select_similar(struct wmOperatorType *ot);
 /* Used only when UV sync select is disabled. */
 void UV_OT_select_mode(struct wmOperatorType *ot);
+
+#ifdef __cplusplus
+}
+#endif

source/blender/editors/uvedit/uvedit_ops.c

@@ -2091,6 +2091,8 @@ void ED_operatortypes_uvedit(void)
 
   WM_operatortype_append(UV_OT_reveal);
   WM_operatortype_append(UV_OT_hide);
+  WM_operatortype_append(UV_OT_copy);
+  WM_operatortype_append(UV_OT_paste);
 
   WM_operatortype_append(UV_OT_cursor_set);
 }

source/blender/windowmanager/intern/wm_init_exit.c

@@ -428,6 +428,8 @@ void wm_exit_schedule_delayed(const bContext *C)
   WM_event_add_mousemove(win); /* ensure handler actually gets called */
 }
 
+void UV_clipboard_free(void);
+
 void WM_exit_ex(bContext *C, const bool do_python)
 {
   wmWindowManager *wm = C ? CTX_wm_manager(C) : NULL;
@@ -536,6 +538,7 @@ void WM_exit_ex(bContext *C, const bool do_python)
   BKE_mask_clipboard_free();
   BKE_vfont_clipboard_free();
   BKE_node_clipboard_free();
+  UV_clipboard_free();
 
 #ifdef WITH_COMPOSITOR_CPU
   COM_deinitialize();