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

1 files changed, 40 insertions, 0 deletions

diff --git a/source/blender/editors/uvedit/uvedit_clipboard_graph_iso.hh b/source/blender/editors/uvedit/uvedit_clipboard_graph_iso.hh
new file mode 100644
index 00000000000..adfe4de2367
--- /dev/null
+++ b/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);