From 721fc9c1c95017d55785ea42e7ba473a0285b9ad Mon Sep 17 00:00:00 2001 From: Chris Blackbourn Date: Sun, 13 Nov 2022 12:27:28 +1300 Subject: 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 | 5 + source/blender/blenkernel/BKE_mesh_mapping.h | 3 + source/blender/editors/uvedit/CMakeLists.txt | 3 + source/blender/editors/uvedit/uvedit_clipboard.cc | 369 ++++++++++++++++++ .../editors/uvedit/uvedit_clipboard_graph_iso.cc | 419 +++++++++++++++++++++ .../editors/uvedit/uvedit_clipboard_graph_iso.hh | 40 ++ source/blender/editors/uvedit/uvedit_intern.h | 12 + source/blender/editors/uvedit/uvedit_ops.c | 2 + source/blender/windowmanager/intern/wm_init_exit.c | 3 + 9 files changed, 856 insertions(+) create mode 100644 source/blender/editors/uvedit/uvedit_clipboard.cc create mode 100644 source/blender/editors/uvedit/uvedit_clipboard_graph_iso.cc create mode 100644 source/blender/editors/uvedit/uvedit_clipboard_graph_iso.hh diff --git a/release/scripts/startup/bl_ui/space_image.py b/release/scripts/startup/bl_ui/space_image.py index fcbd7bb423d..f4c64831b3e 100644 --- a/release/scripts/startup/bl_ui/space_image.py +++ b/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() diff --git a/source/blender/blenkernel/BKE_mesh_mapping.h b/source/blender/blenkernel/BKE_mesh_mapping.h index 705158bec0b..c5c81b31b79 100644 --- a/source/blender/blenkernel/BKE_mesh_mapping.h +++ b/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 build_loop_to_poly_map(Span polys, int loops_num); diff --git a/source/blender/editors/uvedit/CMakeLists.txt b/source/blender/editors/uvedit/CMakeLists.txt index 4574c745d93..9a9f79b7972 100644 --- a/source/blender/editors/uvedit/CMakeLists.txt +++ b/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 ) diff --git a/source/blender/editors/uvedit/uvedit_clipboard.cc b/source/blender/editors/uvedit/uvedit_clipboard.cc new file mode 100644 index 00000000000..7e6d6a2e0d0 --- /dev/null +++ b/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 &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 &label); + + private: + blender::Vector graph; + blender::Vector offset; + blender::Vector> 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(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 &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 &source_uv = uv_clipboard->uv[label[unique_uv]]; + while (element) { + MLoopUV *luv = static_cast(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 &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 &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 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(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; +} diff --git a/source/blender/editors/uvedit/uvedit_clipboard_graph_iso.cc b/source/blender/editors/uvedit/uvedit_clipboard_graph_iso.cc new file mode 100644 index 00000000000..43975d0d382 --- /dev/null +++ b/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 +#include + +#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(MEM_mallocN(n * sizeof *label, __func__)); + adjmat = static_cast(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> 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(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(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(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; +} 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 + +/* 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); diff --git a/source/blender/editors/uvedit/uvedit_intern.h b/source/blender/editors/uvedit/uvedit_intern.h index 434bfbc64f9..098c6ad8655 100644 --- a/source/blender/editors/uvedit/uvedit_intern.h +++ b/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 diff --git a/source/blender/editors/uvedit/uvedit_ops.c b/source/blender/editors/uvedit/uvedit_ops.c index 0e77a8ba4ad..dbbba2656fd 100644 --- a/source/blender/editors/uvedit/uvedit_ops.c +++ b/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); } diff --git a/source/blender/windowmanager/intern/wm_init_exit.c b/source/blender/windowmanager/intern/wm_init_exit.c index c5d7152246c..f7b24c998e6 100644 --- a/source/blender/windowmanager/intern/wm_init_exit.c +++ b/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(); -- cgit v1.2.3