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
This commit is contained in:
parent
533c396898
commit
721fc9c1c9
Notes:
blender-bot
2023-02-14 08:08:54 +01:00
Referenced by commit909f47e0e1
, UV: fix crash with uv copy on empty selection Referenced by commitfba7461e1a
, UV: fix compile on windows Referenced by issue #102480, UV: Copy empty selection uv cused crash Referenced by issue #77911, UV Island Copy/Paste
|
@ -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()
|
||||
|
|
|
@ -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);
|
||||
|
|
|
@ -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
|
||||
)
|
||||
|
||||
|
|
|
@ -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;
|
||||
}
|
|
@ -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;
|
||||
}
|
|
@ -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);
|
|
@ -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
|
||||
|
|
|
@ -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);
|
||||
}
|
||||
|
|
|
@ -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();
|
||||
|
|
Loading…
Reference in New Issue