source/blender/editors/uvedit/uvedit_smart_stitch.c

   1 /*
   2  * ***** BEGIN GPL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  19  * All rights reserved.
  20  *
  21  * The Original Code is: all of this file.
  22  *
  23  * Contributor(s): Antony Riakiotakis.
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 /** \file blender/editors/uvedit/uvedit_smart_stitch.c
  29  *  \ingroup eduv
  30  */
  31
  32
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <math.h>
  36
  37 #include "MEM_guardedalloc.h"
  38
  39 #include "DNA_object_types.h"
  40 #include "DNA_meshdata_types.h"
  41 #include "DNA_scene_types.h"
  42
  43 #include "BLI_utildefines.h"
  44 #include "BLI_ghash.h"
  45 #include "BLI_math.h"
  46 #include "BLI_math_vector.h"
  47 #include "BLI_string.h"
  48
  49 #include "BLT_translation.h"
  50
  51 #include "BIF_gl.h"
  52
  53 #include "BKE_context.h"
  54 #include "BKE_customdata.h"
  55 #include "BKE_depsgraph.h"
  56 #include "BKE_mesh_mapping.h"
  57 #include "BKE_editmesh.h"
  58
  59 #include "UI_interface.h"
  60
  61 #include "ED_mesh.h"
  62 #include "ED_uvedit.h"
  63 #include "ED_screen.h"
  64 #include "ED_space_api.h"
  65
  66 #include "RNA_access.h"
  67 #include "RNA_define.h"
  68
  69 #include "WM_api.h"
  70 #include "WM_types.h"
  71
  72 #include "UI_view2d.h"
  73 #include "UI_resources.h"
  74
  75 #include "uvedit_intern.h"
  76
  77 /* ********************** smart stitch operator *********************** */
  78
  79 /* object that stores display data for previewing before confirming stitching */
  80 typedef struct StitchPreviewer {
  81         /* here we'll store the preview triangle indices of the mesh */
  82         float *preview_polys;
  83         /* uvs per polygon. */
  84         unsigned int *uvs_per_polygon;
  85         /*number of preview polygons */
  86         unsigned int num_polys;
  87         /* preview data. These will be either the previewed vertices or edges depending on stitch mode settings */
  88         float *preview_stitchable;
  89         float *preview_unstitchable;
  90         /* here we'll store the number of elements to be drawn */
  91         unsigned int num_stitchable;
  92         unsigned int num_unstitchable;
  93         unsigned int preview_uvs;
  94         /* ...and here we'll store the static island triangles */
  95         float *static_tris;
  96         unsigned int num_static_tris;
  97 } StitchPreviewer;
  98
  99
 100 struct IslandStitchData;
 101
 102 /**
 103  * This is a straightforward implementation, count the UVs in the island
 104  * that will move and take the mean displacement/rotation and apply it to all
 105  * elements of the island except from the stitchable.
 106  */
 107 typedef struct IslandStitchData {
 108         /* rotation can be used only for edges, for vertices there is no such notion */
 109         float rotation;
 110         float rotation_neg;
 111         float translation[2];
 112         /* Used for rotation, the island will rotate around this point */
 113         float medianPoint[2];
 114         int numOfElements;
 115         int num_rot_elements;
 116         int num_rot_elements_neg;
 117         /* flag to remember if island has been added for preview */
 118         char addedForPreview;
 119         /* flag an island to be considered for determining static island */
 120         char stitchableCandidate;
 121         /* if edge rotation is used, flag so that vertex rotation is not used */
 122         bool use_edge_rotation;
 123 } IslandStitchData;
 124
 125 /* just for averaging UVs */
 126 typedef struct UVVertAverage {
 127         float uv[2];
 128         unsigned short count;
 129 } UVVertAverage;
 130
 131 typedef struct UvEdge {
 132         /* index to uv buffer */
 133         unsigned int uv1;
 134         unsigned int uv2;
 135         /* general use flag (Used to check if edge is boundary here, and propagates to adjacency elements) */
 136         unsigned char flag;
 137         /* element that guarantees element->face has the edge on element->tfindex and element->tfindex+1 is the second uv */
 138         UvElement *element;
 139         /* next uv edge with the same exact vertices as this one.. Calculated at startup to save time */
 140         struct UvEdge *next;
 141         /* point to first of common edges. Needed for iteration */
 142         struct UvEdge *first;
 143 } UvEdge;
 144
 145
 146 /* stitch state object */
 147 typedef struct StitchState {
 148         float aspect;
 149         /* use limit flag */
 150         bool use_limit;
 151         /* limit to operator, same as original operator */
 152         float limit_dist;
 153         /* snap uv islands together during stitching */
 154         bool snap_islands;
 155         /* stitch at midpoints or at islands */
 156         bool midpoints;
 157         /* editmesh, cached for use in modal handler */
 158         BMEditMesh *em;
 159         /* clear seams of stitched edges after stitch */
 160         bool clear_seams;
 161         /* element map for getting info about uv connectivity */
 162         UvElementMap *element_map;
 163         /* edge container */
 164         UvEdge *uvedges;
 165         /* container of first of a group of coincident uvs, these will be operated upon */
 166         UvElement **uvs;
 167         /* maps uvelements to their first coincident uv */
 168         int *map;
 169         /* 2D normals per uv to calculate rotation for snapping */
 170         float *normals;
 171         /* edge storage */
 172         UvEdge *edges;
 173         /* hash for quick lookup of edges */
 174         GHash *edge_hash;
 175
 176         /* count of separate uvs and edges */
 177         int total_separate_edges;
 178         int total_separate_uvs;
 179         /* hold selection related information */
 180         void **selection_stack;
 181         int selection_size;
 182         /* island that stays in place */
 183         int static_island;
 184         /* store number of primitives per face so that we can allocate the active island buffer later */
 185         unsigned int *tris_per_island;
 186
 187         /* vert or edge mode used for stitching */
 188         char mode;
 189         /* handle for drawing */
 190         void *draw_handle;
 191         /* preview data */
 192         StitchPreviewer *stitch_preview;
 193 } StitchState;
 194
 195 typedef struct PreviewPosition {
 196         int data_position;
 197         int polycount_position;
 198 } PreviewPosition;
 199 /*
 200  * defines for UvElement/UcEdge flags
 201  */
 202 #define STITCH_SELECTED 1
 203 #define STITCH_STITCHABLE 2
 204 #define STITCH_PROCESSED 4
 205 #define STITCH_BOUNDARY 8
 206 #define STITCH_STITCHABLE_CANDIDATE 16
 207
 208 #define STITCH_NO_PREVIEW -1
 209
 210 enum StitchModes {
 211         STITCH_VERT,
 212         STITCH_EDGE
 213 };
 214
 215 /* constructor */
 216 static StitchPreviewer *stitch_preview_init(void)
 217 {
 218         StitchPreviewer *stitch_preview;
 219
 220         stitch_preview = MEM_mallocN(sizeof(StitchPreviewer), "stitch_previewer");
 221         stitch_preview->preview_polys = NULL;
 222         stitch_preview->preview_stitchable = NULL;
 223         stitch_preview->preview_unstitchable = NULL;
 224         stitch_preview->uvs_per_polygon = NULL;
 225
 226         stitch_preview->preview_uvs = 0;
 227         stitch_preview->num_polys = 0;
 228         stitch_preview->num_stitchable = 0;
 229         stitch_preview->num_unstitchable = 0;
 230
 231         stitch_preview->static_tris = NULL;
 232
 233         stitch_preview->num_static_tris = 0;
 234
 235         return stitch_preview;
 236 }
 237
 238 /* destructor...yeah this should be C++ :) */
 239 static void stitch_preview_delete(StitchPreviewer *stitch_preview)
 240 {
 241         if (stitch_preview) {
 242                 if (stitch_preview->preview_polys) {
 243                         MEM_freeN(stitch_preview->preview_polys);
 244                         stitch_preview->preview_polys = NULL;
 245                 }
 246                 if (stitch_preview->uvs_per_polygon) {
 247                         MEM_freeN(stitch_preview->uvs_per_polygon);
 248                         stitch_preview->uvs_per_polygon = NULL;
 249                 }
 250                 if (stitch_preview->preview_stitchable) {
 251                         MEM_freeN(stitch_preview->preview_stitchable);
 252                         stitch_preview->preview_stitchable = NULL;
 253                 }
 254                 if (stitch_preview->preview_unstitchable) {
 255                         MEM_freeN(stitch_preview->preview_unstitchable);
 256                         stitch_preview->preview_unstitchable = NULL;
 257                 }
 258                 if (stitch_preview->static_tris) {
 259                         MEM_freeN(stitch_preview->static_tris);
 260                         stitch_preview->static_tris = NULL;
 261                 }
 262                 MEM_freeN(stitch_preview);
 263         }
 264 }
 265
 266 /* This function updates the header of the UV editor when the stitch tool updates its settings */
 267 static void stitch_update_header(StitchState *state, bContext *C)
 268 {
 269         const char *str = IFACE_(
 270             "Mode(TAB) %s, "
 271             "(S)nap %s, "
 272             "(M)idpoints %s, "
 273             "(L)imit %.2f (Alt Wheel adjust) %s, "
 274             "Switch (I)sland, "
 275             "shift select vertices"
 276         );
 277
 278         char msg[UI_MAX_DRAW_STR];
 279         ScrArea *sa = CTX_wm_area(C);
 280
 281         if (sa) {
 282                 BLI_snprintf(msg, sizeof(msg), str,
 283                              state->mode == STITCH_VERT ? IFACE_("Vertex") : IFACE_("Edge"),
 284                              WM_bool_as_string(state->snap_islands),
 285                              WM_bool_as_string(state->midpoints),
 286                              state->limit_dist,
 287                              WM_bool_as_string(state->use_limit));
 288
 289                 ED_area_headerprint(sa, msg);
 290         }
 291 }
 292
 293 static int getNumOfIslandUvs(UvElementMap *elementMap, int island)
 294 {
 295         if (island == elementMap->totalIslands - 1) {
 296                 return elementMap->totalUVs - elementMap->islandIndices[island];
 297         }
 298         else {
 299                 return elementMap->islandIndices[island + 1] - elementMap->islandIndices[island];
 300         }
 301 }
 302
 303 static void stitch_uv_rotate(float mat[2][2], float medianPoint[2], float uv[2], float aspect)
 304 {
 305         float uv_rotation_result[2];
 306
 307         uv[1] /= aspect;
 308
 309         sub_v2_v2(uv, medianPoint);
 310         mul_v2_m2v2(uv_rotation_result, mat, uv);
 311         add_v2_v2v2(uv, uv_rotation_result, medianPoint);
 312
 313         uv[1] *= aspect;
 314 }
 315
 316 /* check if two uvelements are stitchable. This should only operate on -different- separate UvElements */
 317 static bool stitch_check_uvs_stitchable(UvElement *element, UvElement *element_iter, StitchState *state)
 318 {
 319         BMesh *bm = state->em->bm;
 320         float limit;
 321
 322         if (element_iter == element) {
 323                 return 0;
 324         }
 325
 326         limit = state->limit_dist;
 327
 328         if (state->use_limit) {
 329                 MLoopUV *luv, *luv_iter;
 330                 BMLoop *l;
 331
 332
 333                 l = element->l;
 334                 luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 335                 l = element_iter->l;
 336                 luv_iter = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 337
 338                 if (fabsf(luv->uv[0] - luv_iter->uv[0]) < limit &&
 339                     fabsf(luv->uv[1] - luv_iter->uv[1]) < limit)
 340                 {
 341                         return 1;
 342                 }
 343                 else {
 344                         return 0;
 345                 }
 346         }
 347         else {
 348                 return 1;
 349         }
 350 }
 351
 352 static bool stitch_check_edges_stitchable(UvEdge *edge, UvEdge *edge_iter, StitchState *state)
 353 {
 354         BMesh *bm = state->em->bm;
 355         float limit;
 356
 357         if (edge_iter == edge) {
 358                 return 0;
 359         }
 360
 361         limit = state->limit_dist;
 362
 363         if (state->use_limit) {
 364                 BMLoop *l;
 365                 MLoopUV *luv_orig1, *luv_iter1;
 366                 MLoopUV *luv_orig2, *luv_iter2;
 367
 368                 l = state->uvs[edge->uv1]->l;
 369                 luv_orig1 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 370                 l = state->uvs[edge_iter->uv1]->l;
 371                 luv_iter1 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 372
 373                 l = state->uvs[edge->uv2]->l;
 374                 luv_orig2 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 375                 l = state->uvs[edge_iter->uv2]->l;
 376                 luv_iter2 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 377
 378                 if (fabsf(luv_orig1->uv[0] - luv_iter1->uv[0]) < limit &&
 379                     fabsf(luv_orig1->uv[1] - luv_iter1->uv[1]) < limit &&
 380                     fabsf(luv_orig2->uv[0] - luv_iter2->uv[0]) < limit &&
 381                     fabsf(luv_orig2->uv[1] - luv_iter2->uv[1]) < limit)
 382                 {
 383                         return 1;
 384                 }
 385                 else {
 386                         return 0;
 387                 }
 388         }
 389         else {
 390                 return 1;
 391         }
 392 }
 393
 394 static bool stitch_check_uvs_state_stitchable(UvElement *element, UvElement *element_iter, StitchState *state)
 395 {
 396         if ((state->snap_islands && element->island == element_iter->island) ||
 397             (!state->midpoints && element->island == element_iter->island))
 398         {
 399                 return 0;
 400         }
 401
 402         return stitch_check_uvs_stitchable(element, element_iter, state);
 403 }
 404
 405
 406 static bool stitch_check_edges_state_stitchable(UvEdge *edge, UvEdge *edge_iter, StitchState *state)
 407 {
 408         if ((state->snap_islands && edge->element->island == edge_iter->element->island) ||
 409             (!state->midpoints && edge->element->island == edge_iter->element->island))
 410         {
 411                 return 0;
 412         }
 413
 414         return stitch_check_edges_stitchable(edge, edge_iter, state);
 415 }
 416
 417 /* calculate snapping for islands */
 418 static void stitch_calculate_island_snapping(
 419         StitchState *state, PreviewPosition *preview_position, StitchPreviewer *preview,
 420         IslandStitchData *island_stitch_data, int final)
 421 {
 422         BMesh *bm = state->em->bm;
 423         int i;
 424         UvElement *element;
 425
 426         for (i = 0; i < state->element_map->totalIslands; i++) {
 427                 if (island_stitch_data[i].addedForPreview) {
 428                         int numOfIslandUVs = 0, j;
 429                         int totelem = island_stitch_data[i].num_rot_elements_neg + island_stitch_data[i].num_rot_elements;
 430                         float rotation;
 431                         float rotation_mat[2][2];
 432
 433                         /* check to avoid divide by 0 */
 434                         if (island_stitch_data[i].num_rot_elements > 1)
 435                                 island_stitch_data[i].rotation /= island_stitch_data[i].num_rot_elements;
 436
 437                         if (island_stitch_data[i].num_rot_elements_neg > 1)
 438                                 island_stitch_data[i].rotation_neg /= island_stitch_data[i].num_rot_elements_neg;
 439
 440                         if (island_stitch_data[i].numOfElements > 1) {
 441                                 island_stitch_data[i].medianPoint[0] /= island_stitch_data[i].numOfElements;
 442                                 island_stitch_data[i].medianPoint[1] /= island_stitch_data[i].numOfElements;
 443
 444                                 island_stitch_data[i].translation[0] /= island_stitch_data[i].numOfElements;
 445                                 island_stitch_data[i].translation[1] /= island_stitch_data[i].numOfElements;
 446                         }
 447
 448                         island_stitch_data[i].medianPoint[1] /= state->aspect;
 449                         if ((island_stitch_data[i].rotation + island_stitch_data[i].rotation_neg < (float)M_PI_2) ||
 450                             island_stitch_data[i].num_rot_elements == 0 || island_stitch_data[i].num_rot_elements_neg == 0)
 451                         {
 452                                 rotation = (island_stitch_data[i].rotation * island_stitch_data[i].num_rot_elements -
 453                                             island_stitch_data[i].rotation_neg *
 454                                             island_stitch_data[i].num_rot_elements_neg) / totelem;
 455                         }
 456                         else {
 457                                 rotation = (island_stitch_data[i].rotation * island_stitch_data[i].num_rot_elements +
 458                                             (2.0f * (float)M_PI - island_stitch_data[i].rotation_neg) *
 459                                             island_stitch_data[i].num_rot_elements_neg) / totelem;
 460                         }
 461
 462                         angle_to_mat2(rotation_mat, rotation);
 463                         numOfIslandUVs = getNumOfIslandUvs(state->element_map, i);
 464                         element = &state->element_map->buf[state->element_map->islandIndices[i]];
 465                         for (j = 0; j < numOfIslandUVs; j++, element++) {
 466                                 /* stitchable uvs have already been processed, don't process */
 467                                 if (!(element->flag & STITCH_PROCESSED)) {
 468                                         MLoopUV *luv;
 469                                         BMLoop *l;
 470
 471                                         l = element->l;
 472                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 473
 474                                         if (final) {
 475
 476                                                 stitch_uv_rotate(rotation_mat, island_stitch_data[i].medianPoint, luv->uv, state->aspect);
 477
 478                                                 add_v2_v2(luv->uv, island_stitch_data[i].translation);
 479                                         }
 480
 481                                         else {
 482
 483                                                 int face_preview_pos = preview_position[BM_elem_index_get(element->l->f)].data_position;
 484
 485                                                 stitch_uv_rotate(rotation_mat, island_stitch_data[i].medianPoint,
 486                                                                  preview->preview_polys + face_preview_pos + 2 * element->tfindex, state->aspect);
 487
 488                                                 add_v2_v2(preview->preview_polys + face_preview_pos + 2 * element->tfindex,
 489                                                           island_stitch_data[i].translation);
 490                                         }
 491                                 }
 492                                 /* cleanup */
 493                                 element->flag &= STITCH_SELECTED;
 494                         }
 495                 }
 496         }
 497 }
 498
 499
 500
 501 static void stitch_island_calculate_edge_rotation(
 502         UvEdge *edge, StitchState *state, UVVertAverage *uv_average, unsigned int *uvfinal_map,
 503         IslandStitchData *island_stitch_data)
 504 {
 505         BMesh *bm = state->em->bm;
 506         UvElement *element1, *element2;
 507         float uv1[2], uv2[2];
 508         float edgecos, edgesin;
 509         int index1, index2;
 510         float rotation;
 511         MLoopUV *luv1, *luv2;
 512
 513         element1 = state->uvs[edge->uv1];
 514         element2 = state->uvs[edge->uv2];
 515
 516         luv1 = CustomData_bmesh_get(&bm->ldata, element1->l->head.data, CD_MLOOPUV);
 517         luv2 = CustomData_bmesh_get(&bm->ldata, element2->l->head.data, CD_MLOOPUV);
 518
 519         if (state->mode == STITCH_VERT) {
 520                 index1 = uvfinal_map[element1 - state->element_map->buf];
 521                 index2 = uvfinal_map[element2 - state->element_map->buf];
 522         }
 523         else {
 524                 index1 = edge->uv1;
 525                 index2 = edge->uv2;
 526         }
 527         /* the idea here is to take the directions of the edges and find the rotation between final and initial
 528          * direction. This, using inner and outer vector products, gives the angle. Directions are differences so... */
 529         uv1[0] = luv2->uv[0] - luv1->uv[0];
 530         uv1[1] = luv2->uv[1] - luv1->uv[1];
 531
 532         uv1[1] /= state->aspect;
 533
 534         uv2[0] = uv_average[index2].uv[0] - uv_average[index1].uv[0];
 535         uv2[1] = uv_average[index2].uv[1] - uv_average[index1].uv[1];
 536
 537         uv2[1] /= state->aspect;
 538
 539         normalize_v2(uv1);
 540         normalize_v2(uv2);
 541
 542         edgecos = dot_v2v2(uv1, uv2);
 543         edgesin = cross_v2v2(uv1, uv2);
 544         rotation = acosf(max_ff(-1.0f, min_ff(1.0f, edgecos)));
 545
 546         if (edgesin > 0.0f) {
 547                 island_stitch_data[element1->island].num_rot_elements++;
 548                 island_stitch_data[element1->island].rotation += rotation;
 549         }
 550         else {
 551                 island_stitch_data[element1->island].num_rot_elements_neg++;
 552                 island_stitch_data[element1->island].rotation_neg += rotation;
 553         }
 554 }
 555
 556
 557 static void stitch_island_calculate_vert_rotation(
 558         UvElement *element, StitchState *state,
 559         IslandStitchData *island_stitch_data)
 560 {
 561         float edgecos = 1.0f, edgesin = 0.0f;
 562         int index;
 563         UvElement *element_iter;
 564         float rotation = 0, rotation_neg = 0;
 565         int rot_elem = 0, rot_elem_neg = 0;
 566         BMLoop *l;
 567
 568         if (element->island == state->static_island && !state->midpoints)
 569                 return;
 570
 571         l = element->l;
 572
 573         index = BM_elem_index_get(l->v);
 574
 575         element_iter = state->element_map->vert[index];
 576
 577         for (; element_iter; element_iter = element_iter->next) {
 578                 if (element_iter->separate && stitch_check_uvs_state_stitchable(element, element_iter, state)) {
 579                         int index_tmp1, index_tmp2;
 580                         float normal[2];
 581
 582                         /* only calculate rotation against static island uv verts */
 583                         if (!state->midpoints && element_iter->island != state->static_island)
 584                                 continue;
 585
 586                         index_tmp1 = element_iter - state->element_map->buf;
 587                         index_tmp1 = state->map[index_tmp1];
 588                         index_tmp2 = element - state->element_map->buf;
 589                         index_tmp2 = state->map[index_tmp2];
 590
 591                         negate_v2_v2(normal, state->normals + index_tmp2 * 2);
 592                         edgecos = dot_v2v2(normal, state->normals + index_tmp1 * 2);
 593                         edgesin = cross_v2v2(normal, state->normals + index_tmp1 * 2);
 594                         if (edgesin > 0.0f) {
 595                                 rotation += acosf(max_ff(-1.0f, min_ff(1.0f, edgecos)));
 596                                 rot_elem++;
 597                         }
 598                         else {
 599                                 rotation_neg += acosf(max_ff(-1.0f, min_ff(1.0f, edgecos)));
 600                                 rot_elem_neg++;
 601                         }
 602                 }
 603         }
 604
 605         if (state->midpoints) {
 606                 rotation /= 2.0f;
 607                 rotation_neg /= 2.0f;
 608         }
 609         island_stitch_data[element->island].num_rot_elements += rot_elem;
 610         island_stitch_data[element->island].rotation += rotation;
 611         island_stitch_data[element->island].num_rot_elements_neg += rot_elem_neg;
 612         island_stitch_data[element->island].rotation_neg += rotation_neg;
 613 }
 614
 615
 616 static void state_delete(StitchState *state)
 617 {
 618         if (state) {
 619                 if (state->element_map) {
 620                         BM_uv_element_map_free(state->element_map);
 621                 }
 622                 if (state->uvs) {
 623                         MEM_freeN(state->uvs);
 624                 }
 625                 if (state->selection_stack) {
 626                         MEM_freeN(state->selection_stack);
 627                 }
 628                 if (state->tris_per_island) {
 629                         MEM_freeN(state->tris_per_island);
 630                 }
 631                 if (state->map) {
 632                         MEM_freeN(state->map);
 633                 }
 634                 if (state->normals) {
 635                         MEM_freeN(state->normals);
 636                 }
 637                 if (state->edges) {
 638                         MEM_freeN(state->edges);
 639                 }
 640                 if (state->stitch_preview) {
 641                         stitch_preview_delete(state->stitch_preview);
 642                 }
 643                 if (state->edge_hash) {
 644                         BLI_ghash_free(state->edge_hash, NULL, NULL);
 645                 }
 646                 MEM_freeN(state);
 647         }
 648 }
 649
 650 static void stitch_uv_edge_generate_linked_edges(GHash *edge_hash, StitchState *state)
 651 {
 652         UvEdge *edges = state->edges;
 653         const int *map = state->map;
 654         UvElementMap *element_map = state->element_map;
 655         UvElement *first_element = element_map->buf;
 656         int i;
 657
 658         for (i = 0; i < state->total_separate_edges; i++) {
 659                 UvEdge *edge = edges + i;
 660
 661                 if (edge->first)
 662                         continue;
 663
 664                 /* only boundary edges can be stitched. Yes. Sorry about that :p */
 665                 if (edge->flag & STITCH_BOUNDARY) {
 666                         UvElement *element1 = state->uvs[edge->uv1];
 667                         UvElement *element2 = state->uvs[edge->uv2];
 668
 669                         /* Now iterate through all faces and try to find edges sharing the same vertices */
 670                         UvElement *iter1 = element_map->vert[BM_elem_index_get(element1->l->v)];
 671                         UvEdge *last_set = edge;
 672                         int elemindex2 = BM_elem_index_get(element2->l->v);
 673
 674                         edge->first = edge;
 675
 676                         for (; iter1; iter1 = iter1->next) {
 677                                 UvElement *iter2 = NULL;
 678
 679                                 /* check to see if other vertex of edge belongs to same vertex as */
 680                                 if (BM_elem_index_get(iter1->l->next->v) == elemindex2)
 681                                         iter2 = BM_uv_element_get(element_map, iter1->l->f, iter1->l->next);
 682                                 else if (BM_elem_index_get(iter1->l->prev->v) == elemindex2)
 683                                         iter2 = BM_uv_element_get(element_map, iter1->l->f, iter1->l->prev);
 684
 685                                 if (iter2) {
 686                                         int index1 = map[iter1 - first_element];
 687                                         int index2 = map[iter2 - first_element];
 688                                         UvEdge edgetmp;
 689                                         UvEdge *edge2, *eiter;
 690                                         bool valid = true;
 691
 692                                         /* make sure the indices are well behaved */
 693                                         if (index1 > index2) {
 694                                                 SWAP(int, index1, index2);
 695                                         }
 696
 697                                         edgetmp.uv1 = index1;
 698                                         edgetmp.uv2 = index2;
 699
 700                                         /* get the edge from the hash */
 701                                         edge2 = BLI_ghash_lookup(edge_hash, &edgetmp);
 702
 703                                         /* more iteration to make sure non-manifold case is handled nicely */
 704                                         for (eiter = edge; eiter; eiter = eiter->next) {
 705                                                 if (edge2 == eiter) {
 706                                                         valid = false;
 707                                                         break;
 708                                                 }
 709                                         }
 710
 711                                         if (valid) {
 712                                                 /* here I am taking care of non manifold case, assuming more than two matching edges.
 713                                                  * I am not too sure we want this though */
 714                                                 last_set->next = edge2;
 715                                                 last_set = edge2;
 716                                                 /* set first, similarly to uv elements. Now we can iterate among common edges easily */
 717                                                 edge2->first = edge;
 718                                         }
 719                                 }
 720                         }
 721                 }
 722                 else {
 723                         /* so stitchability code works */
 724                         edge->first = edge;
 725                 }
 726         }
 727 }
 728
 729
 730 /* checks for remote uvs that may be stitched with a certain uv, flags them if stitchable. */
 731 static void determine_uv_stitchability(
 732         UvElement *element, StitchState *state,
 733         IslandStitchData *island_stitch_data)
 734 {
 735         int vert_index;
 736         UvElement *element_iter;
 737         BMLoop *l;
 738
 739         l = element->l;
 740
 741         vert_index = BM_elem_index_get(l->v);
 742         element_iter = state->element_map->vert[vert_index];
 743
 744         for (; element_iter; element_iter = element_iter->next) {
 745                 if (element_iter->separate) {
 746                         if (stitch_check_uvs_stitchable(element, element_iter, state)) {
 747                                 island_stitch_data[element_iter->island].stitchableCandidate = 1;
 748                                 island_stitch_data[element->island].stitchableCandidate = 1;
 749                                 element->flag |= STITCH_STITCHABLE_CANDIDATE;
 750                         }
 751                 }
 752         }
 753 }
 754
 755 static void determine_uv_edge_stitchability(
 756         UvEdge *edge, StitchState *state,
 757         IslandStitchData *island_stitch_data)
 758 {
 759         UvEdge *edge_iter = edge->first;
 760
 761         for (; edge_iter; edge_iter = edge_iter->next) {
 762                 if (stitch_check_edges_stitchable(edge, edge_iter, state)) {
 763                         island_stitch_data[edge_iter->element->island].stitchableCandidate = 1;
 764                         island_stitch_data[edge->element->island].stitchableCandidate = 1;
 765                         edge->flag |= STITCH_STITCHABLE_CANDIDATE;
 766                 }
 767         }
 768 }
 769
 770
 771 /* set preview buffer position of UV face in editface->tmp.l */
 772 static void stitch_set_face_preview_buffer_position(
 773         BMFace *efa, StitchPreviewer *preview, PreviewPosition *preview_position)
 774 {
 775         int index = BM_elem_index_get(efa);
 776
 777         if (preview_position[index].data_position == STITCH_NO_PREVIEW) {
 778                 preview_position[index].data_position = preview->preview_uvs * 2;
 779                 preview_position[index].polycount_position = preview->num_polys++;
 780                 preview->preview_uvs += efa->len;
 781         }
 782 }
 783
 784
 785 /* setup face preview for all coincident uvs and their faces */
 786 static void stitch_setup_face_preview_for_uv_group(
 787         UvElement *element, StitchState *state, IslandStitchData *island_stitch_data,
 788         PreviewPosition *preview_position)
 789 {
 790         StitchPreviewer *preview = state->stitch_preview;
 791
 792         /* static island does not change so returning immediately */
 793         if (state->snap_islands && !state->midpoints && state->static_island == element->island)
 794                 return;
 795
 796         if (state->snap_islands) {
 797                 island_stitch_data[element->island].addedForPreview = 1;
 798         }
 799
 800         do {
 801                 stitch_set_face_preview_buffer_position(element->l->f, preview, preview_position);
 802                 element = element->next;
 803         } while (element && !element->separate);
 804 }
 805
 806
 807 /* checks if uvs are indeed stitchable and registers so that they can be shown in preview */
 808 static void stitch_validate_uv_stitchability(
 809         UvElement *element, StitchState *state, IslandStitchData *island_stitch_data,
 810         PreviewPosition *preview_position)
 811 {
 812         UvElement *element_iter;
 813         StitchPreviewer *preview = state->stitch_preview;
 814         int vert_index;
 815         BMLoop *l;
 816
 817         l = element->l;
 818
 819         vert_index = BM_elem_index_get(l->v);
 820
 821         element_iter = state->element_map->vert[vert_index];
 822
 823         for (; element_iter; element_iter = element_iter->next) {
 824                 if (element_iter->separate) {
 825                         if (element_iter == element)
 826                                 continue;
 827                         if (stitch_check_uvs_state_stitchable(element, element_iter, state)) {
 828                                 if ((element_iter->island == state->static_island) || (element->island == state->static_island)) {
 829                                         element->flag |= STITCH_STITCHABLE;
 830                                         preview->num_stitchable++;
 831                                         stitch_setup_face_preview_for_uv_group(element, state, island_stitch_data, preview_position);
 832                                         return;
 833                                 }
 834                         }
 835                 }
 836         }
 837
 838         /* this can happen if the uvs to be stitched are not on a stitchable island */
 839         if (!(element->flag & STITCH_STITCHABLE)) {
 840                 preview->num_unstitchable++;
 841         }
 842 }
 843
 844
 845 static void stitch_validate_edge_stitchability(
 846         UvEdge *edge, StitchState *state, IslandStitchData *island_stitch_data,
 847         PreviewPosition *preview_position)
 848 {
 849         UvEdge *edge_iter = edge->first;
 850         StitchPreviewer *preview = state->stitch_preview;
 851
 852         for (; edge_iter; edge_iter = edge_iter->next) {
 853                 if (edge_iter == edge)
 854                         continue;
 855                 if (stitch_check_edges_state_stitchable(edge, edge_iter, state)) {
 856                         if ((edge_iter->element->island == state->static_island) || (edge->element->island == state->static_island)) {
 857                                 edge->flag |= STITCH_STITCHABLE;
 858                                 preview->num_stitchable++;
 859                                 stitch_setup_face_preview_for_uv_group(state->uvs[edge->uv1], state, island_stitch_data, preview_position);
 860                                 stitch_setup_face_preview_for_uv_group(state->uvs[edge->uv2], state, island_stitch_data, preview_position);
 861                                 return;
 862                         }
 863                 }
 864         }
 865
 866         /* this can happen if the uvs to be stitched are not on a stitchable island */
 867         if (!(edge->flag & STITCH_STITCHABLE)) {
 868                 preview->num_unstitchable++;
 869         }
 870 }
 871
 872
 873 static void stitch_propagate_uv_final_position(
 874         Scene *scene,
 875         UvElement *element, int index, PreviewPosition *preview_position,
 876         UVVertAverage *final_position, StitchState *state,
 877         const bool final)
 878 {
 879         BMesh *bm = state->em->bm;
 880         StitchPreviewer *preview = state->stitch_preview;
 881
 882         const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV);
 883
 884         if (element->flag & STITCH_STITCHABLE) {
 885                 UvElement *element_iter = element;
 886                 /* propagate to coincident uvs */
 887                 do {
 888                         BMLoop *l;
 889                         MLoopUV *luv;
 890
 891                         l = element_iter->l;
 892                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
 893
 894                         element_iter->flag |= STITCH_PROCESSED;
 895                         /* either flush to preview or to the MTFace, if final */
 896                         if (final) {
 897                                 copy_v2_v2(luv->uv, final_position[index].uv);
 898
 899                                 uvedit_uv_select_enable(state->em, scene, l, false, cd_loop_uv_offset);
 900                         }
 901                         else {
 902                                 int face_preview_pos = preview_position[BM_elem_index_get(element_iter->l->f)].data_position;
 903                                 if (face_preview_pos != STITCH_NO_PREVIEW) {
 904                                         copy_v2_v2(preview->preview_polys + face_preview_pos + 2 * element_iter->tfindex,
 905                                                    final_position[index].uv);
 906                                 }
 907                         }
 908
 909                         /* end of calculations, keep only the selection flag */
 910                         if ((!state->snap_islands) || ((!state->midpoints) && (element_iter->island == state->static_island))) {
 911                                 element_iter->flag &= STITCH_SELECTED;
 912                         }
 913
 914                         element_iter = element_iter->next;
 915                 } while (element_iter && !element_iter->separate);
 916         }
 917 }
 918
 919 /* main processing function. It calculates preview and final positions. */
 920 static int stitch_process_data(StitchState *state, Scene *scene, int final)
 921 {
 922         int i;
 923         StitchPreviewer *preview;
 924         IslandStitchData *island_stitch_data = NULL;
 925         int previous_island = state->static_island;
 926         BMesh *bm = state->em->bm;
 927         BMFace *efa;
 928         BMIter iter;
 929         UVVertAverage *final_position = NULL;
 930
 931         char stitch_midpoints = state->midpoints;
 932         /* used to map uv indices to uvaverage indices for selection */
 933         unsigned int *uvfinal_map = NULL;
 934         /* per face preview position in preview buffer */
 935         PreviewPosition *preview_position = NULL;
 936
 937         /* cleanup previous preview */
 938         stitch_preview_delete(state->stitch_preview);
 939         preview = state->stitch_preview = stitch_preview_init();
 940         if (preview == NULL)
 941                 return 0;
 942
 943         preview_position = MEM_mallocN(bm->totface * sizeof(*preview_position), "stitch_face_preview_position");
 944         /* each face holds its position in the preview buffer in tmp. -1 is uninitialized */
 945         for (i = 0; i < bm->totface; i++) {
 946                 preview_position[i].data_position = STITCH_NO_PREVIEW;
 947         }
 948
 949         island_stitch_data = MEM_callocN(sizeof(*island_stitch_data) * state->element_map->totalIslands, "stitch_island_data");
 950         if (!island_stitch_data) {
 951                 return 0;
 952         }
 953
 954         /* store indices to editVerts and Faces. May be unneeded but ensuring anyway */
 955         BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE);
 956
 957         /*****************************************
 958          *  First determine stitchability of uvs *
 959          *****************************************/
 960
 961         for (i = 0; i < state->selection_size; i++) {
 962                 if (state->mode == STITCH_VERT) {
 963                         UvElement *element = (UvElement *)state->selection_stack[i];
 964                         determine_uv_stitchability(element, state, island_stitch_data);
 965                 }
 966                 else {
 967                         UvEdge *edge = (UvEdge *)state->selection_stack[i];
 968                         determine_uv_edge_stitchability(edge, state, island_stitch_data);
 969                 }
 970         }
 971
 972         /* set static island to one that is added for preview */
 973         state->static_island %= state->element_map->totalIslands;
 974         while (!(island_stitch_data[state->static_island].stitchableCandidate)) {
 975                 state->static_island++;
 976                 state->static_island %= state->element_map->totalIslands;
 977                 /* this is entirely possible if for example limit stitching with no stitchable verts or no selection */
 978                 if (state->static_island == previous_island)
 979                         break;
 980         }
 981
 982         for (i = 0; i < state->selection_size; i++) {
 983                 if (state->mode == STITCH_VERT) {
 984                         UvElement *element = (UvElement *)state->selection_stack[i];
 985                         if (element->flag & STITCH_STITCHABLE_CANDIDATE) {
 986                                 element->flag &= ~STITCH_STITCHABLE_CANDIDATE;
 987                                 stitch_validate_uv_stitchability(element, state, island_stitch_data, preview_position);
 988                         }
 989                         else {
 990                                 /* add to preview for unstitchable */
 991                                 preview->num_unstitchable++;
 992                         }
 993                 }
 994                 else {
 995                         UvEdge *edge = (UvEdge *)state->selection_stack[i];
 996                         if (edge->flag & STITCH_STITCHABLE_CANDIDATE) {
 997                                 edge->flag &= ~STITCH_STITCHABLE_CANDIDATE;
 998                                 stitch_validate_edge_stitchability(edge, state, island_stitch_data, preview_position);
 999                         }
1000                         else {
1001                                 preview->num_unstitchable++;
1002                         }
1003                 }
1004         }
1005
1006         /*****************************************
1007          *  Setup preview for stitchable islands *
1008          *****************************************/
1009         if (state->snap_islands) {
1010                 for (i = 0; i < state->element_map->totalIslands; i++) {
1011                         if (island_stitch_data[i].addedForPreview) {
1012                                 int numOfIslandUVs = 0, j;
1013                                 UvElement *element;
1014                                 numOfIslandUVs = getNumOfIslandUvs(state->element_map, i);
1015                                 element = &state->element_map->buf[state->element_map->islandIndices[i]];
1016                                 for (j = 0; j < numOfIslandUVs; j++, element++) {
1017                                         stitch_set_face_preview_buffer_position(element->l->f, preview, preview_position);
1018                                 }
1019                         }
1020                 }
1021         }
1022
1023         /*********************************************************************
1024          * Setup the preview buffers and fill them with the appropriate data *
1025          *********************************************************************/
1026         if (!final) {
1027                 BMIter liter;
1028                 BMLoop *l;
1029                 MLoopUV *luv;
1030                 unsigned int buffer_index = 0;
1031                 int stitchBufferIndex = 0, unstitchBufferIndex = 0;
1032                 int preview_size = (state->mode == STITCH_VERT) ? 2 : 4;
1033                 /* initialize the preview buffers */
1034                 preview->preview_polys = (float *)MEM_mallocN(preview->preview_uvs * sizeof(float) * 2, "tri_uv_stitch_prev");
1035                 preview->uvs_per_polygon = MEM_mallocN(preview->num_polys * sizeof(*preview->uvs_per_polygon), "tri_uv_stitch_prev");
1036                 preview->preview_stitchable = (float *)MEM_mallocN(preview->num_stitchable * sizeof(float) * preview_size, "stitch_preview_stitchable_data");
1037                 preview->preview_unstitchable = (float *)MEM_mallocN(preview->num_unstitchable * sizeof(float) * preview_size, "stitch_preview_unstitchable_data");
1038
1039                 preview->static_tris = (float *)MEM_mallocN(state->tris_per_island[state->static_island] * sizeof(float) * 6, "static_island_preview_tris");
1040
1041                 preview->num_static_tris = state->tris_per_island[state->static_island];
1042                 /* will cause cancel and freeing of all data structures so OK */
1043                 if (!preview->preview_polys || !preview->preview_stitchable || !preview->preview_unstitchable) {
1044                         return 0;
1045                 }
1046
1047                 /* copy data from MLoopUVs to the preview display buffers */
1048                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
1049                         /* just to test if face was added for processing. uvs of unselected vertices will return NULL */
1050                         UvElement *element = BM_uv_element_get(state->element_map, efa, BM_FACE_FIRST_LOOP(efa));
1051
1052                         if (element) {
1053                                 int numoftris = efa->len - 2;
1054                                 int index = BM_elem_index_get(efa);
1055                                 int face_preview_pos = preview_position[index].data_position;
1056                                 if (face_preview_pos != STITCH_NO_PREVIEW) {
1057                                         preview->uvs_per_polygon[preview_position[index].polycount_position] = efa->len;
1058                                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, i) {
1059                                                 luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1060                                                 copy_v2_v2(preview->preview_polys + face_preview_pos + i * 2, luv->uv);
1061                                         }
1062                                 }
1063
1064                                 if (element->island == state->static_island) {
1065                                         BMLoop *fl = BM_FACE_FIRST_LOOP(efa);
1066                                         MLoopUV *fuv = CustomData_bmesh_get(&bm->ldata, fl->head.data, CD_MLOOPUV);
1067
1068                                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, i) {
1069                                                 if (i < numoftris) {
1070                                                         /* using next since the first uv is already accounted for */
1071                                                         BMLoop *lnext = l->next;
1072                                                         MLoopUV *luvnext = CustomData_bmesh_get(&bm->ldata, lnext->next->head.data, CD_MLOOPUV);
1073                                                         luv = CustomData_bmesh_get(&bm->ldata, lnext->head.data, CD_MLOOPUV);
1074
1075                                                         memcpy(preview->static_tris + buffer_index, fuv->uv, 2 * sizeof(float));
1076                                                         memcpy(preview->static_tris + buffer_index + 2, luv->uv, 2 * sizeof(float));
1077                                                         memcpy(preview->static_tris + buffer_index + 4, luvnext->uv, 2 * sizeof(float));
1078                                                         buffer_index += 6;
1079                                                 }
1080                                                 else {
1081                                                         break;
1082                                                 }
1083                                         }
1084                                 }
1085                         }
1086                 }
1087
1088                 /* fill the appropriate preview buffers */
1089                 if (state->mode == STITCH_VERT) {
1090                         for (i = 0; i < state->total_separate_uvs; i++) {
1091                                 UvElement *element = (UvElement *)state->uvs[i];
1092                                 if (element->flag & STITCH_STITCHABLE) {
1093                                         l = element->l;
1094                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1095
1096                                         copy_v2_v2(&preview->preview_stitchable[stitchBufferIndex * 2], luv->uv);
1097
1098                                         stitchBufferIndex++;
1099                                 }
1100                                 else if (element->flag & STITCH_SELECTED) {
1101                                         l = element->l;
1102                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1103
1104                                         copy_v2_v2(&preview->preview_unstitchable[unstitchBufferIndex * 2], luv->uv);
1105                                         unstitchBufferIndex++;
1106                                 }
1107                         }
1108                 }
1109                 else {
1110                         for (i = 0; i < state->total_separate_edges; i++) {
1111                                 UvEdge *edge = state->edges + i;
1112                                 UvElement *element1 = state->uvs[edge->uv1];
1113                                 UvElement *element2 = state->uvs[edge->uv2];
1114
1115                                 if (edge->flag & STITCH_STITCHABLE) {
1116                                         l = element1->l;
1117                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1118                                         copy_v2_v2(&preview->preview_stitchable[stitchBufferIndex * 4], luv->uv);
1119
1120                                         l = element2->l;
1121                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1122                                         copy_v2_v2(&preview->preview_stitchable[stitchBufferIndex * 4 + 2], luv->uv);
1123
1124                                         stitchBufferIndex++;
1125                                         BLI_assert(stitchBufferIndex <= preview->num_stitchable);
1126                                 }
1127                                 else if (edge->flag & STITCH_SELECTED) {
1128                                         l = element1->l;
1129                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1130                                         copy_v2_v2(&preview->preview_unstitchable[unstitchBufferIndex * 4], luv->uv);
1131
1132                                         l = element2->l;
1133                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1134                                         copy_v2_v2(&preview->preview_unstitchable[unstitchBufferIndex * 4 + 2], luv->uv);
1135
1136                                         unstitchBufferIndex++;
1137                                         BLI_assert(unstitchBufferIndex <= preview->num_unstitchable);
1138                                 }
1139                         }
1140                 }
1141         }
1142
1143         /******************************************************
1144          * Here we calculate the final coordinates of the uvs *
1145          ******************************************************/
1146
1147         if (state->mode == STITCH_VERT) {
1148                 final_position = MEM_callocN(state->selection_size * sizeof(*final_position), "stitch_uv_average");
1149                 uvfinal_map = MEM_mallocN(state->element_map->totalUVs * sizeof(*uvfinal_map), "stitch_uv_final_map");
1150         }
1151         else {
1152                 final_position = MEM_callocN(state->total_separate_uvs * sizeof(*final_position), "stitch_uv_average");
1153         }
1154
1155         /* first pass, calculate final position for stitchable uvs of the static island */
1156         for (i = 0; i < state->selection_size; i++) {
1157                 if (state->mode == STITCH_VERT) {
1158                         UvElement *element = state->selection_stack[i];
1159
1160                         if (element->flag & STITCH_STITCHABLE) {
1161                                 BMLoop *l;
1162                                 MLoopUV *luv;
1163                                 UvElement *element_iter;
1164
1165                                 l = element->l;
1166                                 luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1167
1168                                 uvfinal_map[element - state->element_map->buf] = i;
1169
1170                                 copy_v2_v2(final_position[i].uv, luv->uv);
1171                                 final_position[i].count = 1;
1172
1173                                 if (state->snap_islands && element->island == state->static_island && !stitch_midpoints)
1174                                         continue;
1175
1176                                 element_iter = state->element_map->vert[BM_elem_index_get(l->v)];
1177
1178                                 for ( ; element_iter; element_iter = element_iter->next) {
1179                                         if (element_iter->separate) {
1180                                                 if (stitch_check_uvs_state_stitchable(element, element_iter, state)) {
1181                                                         l = element_iter->l;
1182                                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1183                                                         if (stitch_midpoints) {
1184                                                                 add_v2_v2(final_position[i].uv, luv->uv);
1185                                                                 final_position[i].count++;
1186                                                         }
1187                                                         else if (element_iter->island == state->static_island) {
1188                                                                 /* if multiple uvs on the static island exist,
1189                                                                  * last checked remains. to disambiguate we need to limit or use
1190                                                                  * edge stitch */
1191                                                                 copy_v2_v2(final_position[i].uv, luv->uv);
1192                                                         }
1193                                                 }
1194                                         }
1195                                 }
1196                         }
1197                         if (stitch_midpoints) {
1198                                 final_position[i].uv[0] /= final_position[i].count;
1199                                 final_position[i].uv[1] /= final_position[i].count;
1200                         }
1201                 }
1202                 else {
1203                         UvEdge *edge = state->selection_stack[i];
1204
1205                         if (edge->flag & STITCH_STITCHABLE) {
1206                                 MLoopUV *luv2, *luv1;
1207                                 BMLoop *l;
1208                                 UvEdge *edge_iter;
1209
1210                                 l = state->uvs[edge->uv1]->l;
1211                                 luv1 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1212                                 l = state->uvs[edge->uv2]->l;
1213                                 luv2 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1214
1215                                 copy_v2_v2(final_position[edge->uv1].uv, luv1->uv);
1216                                 copy_v2_v2(final_position[edge->uv2].uv, luv2->uv);
1217                                 final_position[edge->uv1].count = 1;
1218                                 final_position[edge->uv2].count = 1;
1219
1220                                 state->uvs[edge->uv1]->flag |= STITCH_STITCHABLE;
1221                                 state->uvs[edge->uv2]->flag |= STITCH_STITCHABLE;
1222
1223                                 if (state->snap_islands && edge->element->island == state->static_island && !stitch_midpoints)
1224                                         continue;
1225
1226                                 for (edge_iter = edge->first; edge_iter; edge_iter = edge_iter->next) {
1227                                         if (stitch_check_edges_state_stitchable (edge, edge_iter, state)) {
1228                                                 l = state->uvs[edge_iter->uv1]->l;
1229                                                 luv1 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1230                                                 l = state->uvs[edge_iter->uv2]->l;
1231                                                 luv2 = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1232
1233                                                 if (stitch_midpoints) {
1234                                                         add_v2_v2(final_position[edge->uv1].uv, luv1->uv);
1235                                                         final_position[edge->uv1].count++;
1236                                                         add_v2_v2(final_position[edge->uv2].uv, luv2->uv);
1237                                                         final_position[edge->uv2].count++;
1238                                                 }
1239                                                 else if (edge_iter->element->island == state->static_island) {
1240                                                         copy_v2_v2(final_position[edge->uv1].uv, luv1->uv);
1241                                                         copy_v2_v2(final_position[edge->uv2].uv, luv2->uv);
1242                                                 }
1243                                         }
1244                                 }
1245                         }
1246                 }
1247         }
1248
1249         /* take mean position here. For edge case, this can't be done inside the loop for shared uvverts */
1250         if (state->mode == STITCH_EDGE && stitch_midpoints) {
1251                 for (i = 0; i < state->total_separate_uvs; i++) {
1252                         final_position[i].uv[0] /= final_position[i].count;
1253                         final_position[i].uv[1] /= final_position[i].count;
1254                 }
1255         }
1256
1257         /* second pass, calculate island rotation and translation before modifying any uvs */
1258         if (state->snap_islands) {
1259                 if (state->mode == STITCH_VERT) {
1260                         for (i = 0; i < state->selection_size; i++) {
1261                                 UvElement *element = state->selection_stack[i];
1262
1263                                 if (element->flag & STITCH_STITCHABLE) {
1264                                         BMLoop *l;
1265                                         MLoopUV *luv;
1266
1267                                         l = element->l;
1268                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1269
1270                                         /* accumulate each islands' translation from stitchable elements. it is important to do here
1271                                          * because in final pass MTFaces get modified and result is zero. */
1272                                         island_stitch_data[element->island].translation[0] += final_position[i].uv[0] - luv->uv[0];
1273                                         island_stitch_data[element->island].translation[1] += final_position[i].uv[1] - luv->uv[1];
1274                                         island_stitch_data[element->island].medianPoint[0] += luv->uv[0];
1275                                         island_stitch_data[element->island].medianPoint[1] += luv->uv[1];
1276                                         island_stitch_data[element->island].numOfElements++;
1277                                 }
1278                         }
1279
1280                         /* only calculate rotation when an edge has been fully selected */
1281                         for (i = 0; i < state->total_separate_edges; i++) {
1282                                 UvEdge *edge = state->edges + i;
1283                                 if ((edge->flag & STITCH_BOUNDARY) &&
1284                                     (state->uvs[edge->uv1]->flag & STITCH_STITCHABLE) &&
1285                                     (state->uvs[edge->uv2]->flag & STITCH_STITCHABLE))
1286                                 {
1287                                         stitch_island_calculate_edge_rotation(edge, state, final_position, uvfinal_map, island_stitch_data);
1288                                         island_stitch_data[state->uvs[edge->uv1]->island].use_edge_rotation = true;
1289                                 }
1290                         }
1291
1292                         /* clear seams of stitched edges */
1293                         if (final && state->clear_seams) {
1294                                 for (i = 0; i < state->total_separate_edges; i++) {
1295                                         UvEdge *edge = state->edges + i;
1296                                         if ((state->uvs[edge->uv1]->flag & STITCH_STITCHABLE) &&
1297                                             (state->uvs[edge->uv2]->flag & STITCH_STITCHABLE))
1298                                         {
1299                                                 BM_elem_flag_disable(edge->element->l->e, BM_ELEM_SEAM);
1300                                         }
1301                                 }
1302                         }
1303
1304                         for (i = 0; i < state->selection_size; i++) {
1305                                 UvElement *element = state->selection_stack[i];
1306                                 if (!island_stitch_data[element->island].use_edge_rotation) {
1307                                         if (element->flag & STITCH_STITCHABLE) {
1308                                                 stitch_island_calculate_vert_rotation(element, state, island_stitch_data);
1309                                         }
1310                                 }
1311                         }
1312                 }
1313                 else {
1314                         for (i = 0; i < state->total_separate_uvs; i++) {
1315                                 UvElement *element = state->uvs[i];
1316
1317                                 if (element->flag & STITCH_STITCHABLE) {
1318                                         BMLoop *l;
1319                                         MLoopUV *luv;
1320
1321                                         l = element->l;
1322                                         luv = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MLOOPUV);
1323
1324                                         /* accumulate each islands' translation from stitchable elements. it is important to do here
1325                                          * because in final pass MTFaces get modified and result is zero. */
1326                                         island_stitch_data[element->island].translation[0] += final_position[i].uv[0] - luv->uv[0];
1327                                         island_stitch_data[element->island].translation[1] += final_position[i].uv[1] - luv->uv[1];
1328                                         island_stitch_data[element->island].medianPoint[0] += luv->uv[0];
1329                                         island_stitch_data[element->island].medianPoint[1] += luv->uv[1];
1330                                         island_stitch_data[element->island].numOfElements++;
1331                                 }
1332                         }
1333
1334                         for (i = 0; i < state->selection_size; i++) {
1335                                 UvEdge *edge = state->selection_stack[i];
1336
1337                                 if (edge->flag & STITCH_STITCHABLE) {
1338                                         stitch_island_calculate_edge_rotation(edge, state, final_position, NULL, island_stitch_data);
1339                                         island_stitch_data[state->uvs[edge->uv1]->island].use_edge_rotation = true;
1340                                 }
1341                         }
1342
1343                         /* clear seams of stitched edges */
1344                         if (final && state->clear_seams) {
1345                                 for (i = 0; i < state->selection_size; i++) {
1346                                         UvEdge *edge = state->selection_stack[i];
1347                                         if (edge->flag & STITCH_STITCHABLE) {
1348                                                 BM_elem_flag_disable(edge->element->l->e, BM_ELEM_SEAM);
1349                                         }
1350                                 }
1351                         }
1352                 }
1353         }
1354
1355         /* third pass, propagate changes to coincident uvs */
1356         for (i = 0; i < state->selection_size; i++) {
1357                 if (state->mode == STITCH_VERT) {
1358                         UvElement *element = state->selection_stack[i];
1359
1360                         stitch_propagate_uv_final_position(scene, element, i, preview_position, final_position, state, final);
1361                 }
1362                 else {
1363                         UvEdge *edge = state->selection_stack[i];
1364
1365                         stitch_propagate_uv_final_position(
1366                                 scene, state->uvs[edge->uv1], edge->uv1, preview_position, final_position, state, final);
1367                         stitch_propagate_uv_final_position(
1368                                 scene, state->uvs[edge->uv2], edge->uv2, preview_position, final_position, state, final);
1369
1370                         edge->flag &= (STITCH_SELECTED | STITCH_BOUNDARY);
1371                 }
1372         }
1373
1374         /* final pass, calculate Island translation/rotation if needed */
1375         if (state->snap_islands) {
1376                 stitch_calculate_island_snapping(state, preview_position, preview, island_stitch_data, final);
1377         }
1378
1379         MEM_freeN(final_position);
1380         if (state->mode == STITCH_VERT) {
1381                 MEM_freeN(uvfinal_map);
1382         }
1383         MEM_freeN(island_stitch_data);
1384         MEM_freeN(preview_position);
1385
1386         return 1;
1387 }
1388
1389 /* Stitch hash initialization functions */
1390 static unsigned int uv_edge_hash(const void *key)
1391 {
1392         const UvEdge *edge = key;
1393         return (BLI_ghashutil_uinthash(edge->uv2) +
1394                 BLI_ghashutil_uinthash(edge->uv1));
1395 }
1396
1397 static bool uv_edge_compare(const void *a, const void *b)
1398 {
1399         const UvEdge *edge1 = a;
1400         const UvEdge *edge2 = b;
1401
1402         if ((edge1->uv1 == edge2->uv1) && (edge1->uv2 == edge2->uv2)) {
1403                 return 0;
1404         }
1405         return 1;
1406 }
1407
1408 /* select all common edges */
1409 static void stitch_select_edge(UvEdge *edge, StitchState *state, int always_select)
1410 {
1411         UvEdge *eiter;
1412         UvEdge **selection_stack = (UvEdge **)state->selection_stack;
1413
1414         for (eiter = edge->first; eiter; eiter = eiter->next) {
1415                 if (eiter->flag & STITCH_SELECTED) {
1416                         int i;
1417                         if (always_select)
1418                                 continue;
1419
1420                         eiter->flag &= ~STITCH_SELECTED;
1421                         for (i = 0; i < state->selection_size; i++) {
1422                                 if (selection_stack[i] == eiter) {
1423                                         (state->selection_size)--;
1424                                         selection_stack[i] = selection_stack[state->selection_size];
1425                                         break;
1426                                 }
1427                         }
1428                 }
1429                 else {
1430                         eiter->flag |= STITCH_SELECTED;
1431                         selection_stack[state->selection_size++] = eiter;
1432                 }
1433         }
1434 }
1435
1436
1437 /* Select all common uvs */
1438 static void stitch_select_uv(UvElement *element, StitchState *state, int always_select)
1439 {
1440         BMLoop *l;
1441         UvElement *element_iter;
1442         UvElement **selection_stack = (UvElement **)state->selection_stack;
1443
1444         l = element->l;
1445
1446         element_iter = state->element_map->vert[BM_elem_index_get(l->v)];
1447         /* first deselect all common uvs */
1448         for (; element_iter; element_iter = element_iter->next) {
1449                 if (element_iter->separate) {
1450                         /* only separators go to selection */
1451                         if (element_iter->flag & STITCH_SELECTED) {
1452                                 int i;
1453                                 if (always_select)
1454                                         continue;
1455
1456                                 element_iter->flag &= ~STITCH_SELECTED;
1457                                 for (i = 0; i < state->selection_size; i++) {
1458                                         if (selection_stack[i] == element_iter) {
1459                                                 (state->selection_size)--;
1460                                                 selection_stack[i] = selection_stack[state->selection_size];
1461                                                 break;
1462                                         }
1463                                 }
1464                         }
1465                         else {
1466                                 element_iter->flag |= STITCH_SELECTED;
1467                                 selection_stack[state->selection_size++] = element_iter;
1468                         }
1469                 }
1470         }
1471 }
1472
1473 static void stitch_switch_selection_mode(StitchState *state)
1474 {
1475         void **old_selection_stack = state->selection_stack;
1476         int old_selection_size = state->selection_size;
1477         state->selection_size = 0;
1478
1479         if (state->mode == STITCH_VERT) {
1480                 int i;
1481                 state->selection_stack = MEM_mallocN(state->total_separate_edges * sizeof(*state->selection_stack),
1482                                                      "stitch_new_edge_selection_stack");
1483
1484                 /* check if both elements of an edge are selected */
1485                 for (i = 0; i < state->total_separate_edges; i++) {
1486                         UvEdge *edge = state->edges + i;
1487                         UvElement *element1 = state->uvs[edge->uv1];
1488                         UvElement *element2 = state->uvs[edge->uv2];
1489
1490                         if ((element1->flag & STITCH_SELECTED) && (element2->flag & STITCH_SELECTED))
1491                                 stitch_select_edge(edge, state, true);
1492                 }
1493
1494                 /* unselect selected uvelements */
1495                 for (i = 0; i < old_selection_size; i++) {
1496                         UvElement *element = old_selection_stack[i];
1497
1498                         element->flag &= ~STITCH_SELECTED;
1499                 }
1500                 state->mode = STITCH_EDGE;
1501         }
1502         else {
1503                 int i;
1504                 state->selection_stack = MEM_mallocN(state->total_separate_uvs * sizeof(*state->selection_stack),
1505                                                      "stitch_new_vert_selection_stack");
1506
1507                 for (i = 0; i < old_selection_size; i++) {
1508                         UvEdge *edge = old_selection_stack[i];
1509                         UvElement *element1 = state->uvs[edge->uv1];
1510                         UvElement *element2 = state->uvs[edge->uv2];
1511
1512                         stitch_select_uv(element1, state, true);
1513                         stitch_select_uv(element2, state, true);
1514
1515                         edge->flag &= ~STITCH_SELECTED;
1516                 }
1517                 state->mode = STITCH_VERT;
1518         }
1519         MEM_freeN(old_selection_stack);
1520 }
1521
1522 static void stitch_calculate_edge_normal(BMEditMesh *em, UvEdge *edge, float *normal, float aspect)
1523 {
1524         BMLoop *l1 = edge->element->l;
1525         MLoopUV *luv1, *luv2;
1526         float tangent[2];
1527
1528         luv1 = CustomData_bmesh_get(&em->bm->ldata, l1->head.data, CD_MLOOPUV);
1529         luv2 = CustomData_bmesh_get(&em->bm->ldata, l1->next->head.data, CD_MLOOPUV);
1530
1531         sub_v2_v2v2(tangent, luv2->uv,  luv1->uv);
1532
1533         tangent[1] /= aspect;
1534
1535         normal[0] = tangent[1];
1536         normal[1] = -tangent[0];
1537
1538         normalize_v2(normal);
1539 }
1540
1541 static void stitch_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void *arg)
1542 {
1543         int i, index = 0;
1544         StitchState *state = (StitchState *)arg;
1545         StitchPreviewer *stitch_preview = state->stitch_preview;
1546
1547         glPushClientAttrib(GL_CLIENT_VERTEX_ARRAY_BIT);
1548         glEnableClientState(GL_VERTEX_ARRAY);
1549
1550         glEnable(GL_BLEND);
1551
1552         UI_ThemeColor4(TH_STITCH_PREVIEW_ACTIVE);
1553         glVertexPointer(2, GL_FLOAT, 0, stitch_preview->static_tris);
1554         glDrawArrays(GL_TRIANGLES, 0, stitch_preview->num_static_tris * 3);
1555
1556         glVertexPointer(2, GL_FLOAT, 0, stitch_preview->preview_polys);
1557         for (i = 0; i < stitch_preview->num_polys; i++) {
1558                 glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
1559                 UI_ThemeColor4(TH_STITCH_PREVIEW_FACE);
1560                 glDrawArrays(GL_POLYGON, index, stitch_preview->uvs_per_polygon[i]);
1561                 glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
1562                 UI_ThemeColor4(TH_STITCH_PREVIEW_EDGE);
1563                 glDrawArrays(GL_POLYGON, index, stitch_preview->uvs_per_polygon[i]);
1564 #if 0
1565                 glPolygonMode(GL_FRONT_AND_BACK, GL_POINT);
1566                 UI_ThemeColor4(TH_STITCH_PREVIEW_VERT);
1567                 glDrawArrays(GL_POLYGON, index, stitch_preview->uvs_per_polygon[i]);
1568 #endif
1569
1570                 index += stitch_preview->uvs_per_polygon[i];
1571         }
1572         glDisable(GL_BLEND);
1573
1574         /* draw vert preview */
1575         if (state->mode == STITCH_VERT) {
1576                 glPointSize(UI_GetThemeValuef(TH_VERTEX_SIZE) * 2.0f);
1577
1578                 UI_ThemeColor4(TH_STITCH_PREVIEW_STITCHABLE);
1579                 glVertexPointer(2, GL_FLOAT, 0, stitch_preview->preview_stitchable);
1580                 glDrawArrays(GL_POINTS, 0, stitch_preview->num_stitchable);
1581
1582                 UI_ThemeColor4(TH_STITCH_PREVIEW_UNSTITCHABLE);
1583                 glVertexPointer(2, GL_FLOAT, 0, stitch_preview->preview_unstitchable);
1584                 glDrawArrays(GL_POINTS, 0, stitch_preview->num_unstitchable);
1585         }
1586         else {
1587                 UI_ThemeColor4(TH_STITCH_PREVIEW_STITCHABLE);
1588                 glVertexPointer(2, GL_FLOAT, 0, stitch_preview->preview_stitchable);
1589                 glDrawArrays(GL_LINES, 0, 2 * stitch_preview->num_stitchable);
1590
1591                 UI_ThemeColor4(TH_STITCH_PREVIEW_UNSTITCHABLE);
1592                 glVertexPointer(2, GL_FLOAT, 0, stitch_preview->preview_unstitchable);
1593                 glDrawArrays(GL_LINES, 0, 2 * stitch_preview->num_unstitchable);
1594         }
1595
1596         glPopClientAttrib();
1597         glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
1598 }
1599
1600 static UvEdge *uv_edge_get(BMLoop *l, StitchState *state)
1601 {
1602         UvEdge tmp_edge;
1603
1604         UvElement *element1 = BM_uv_element_get(state->element_map, l->f, l);
1605         UvElement *element2 = BM_uv_element_get(state->element_map, l->f, l->next);
1606
1607         int uv1 = state->map[element1 - state->element_map->buf];
1608         int uv2 = state->map[element2 - state->element_map->buf];
1609
1610         if (uv1 < uv2) {
1611                 tmp_edge.uv1 = uv1;
1612                 tmp_edge.uv2 = uv2;
1613         }
1614         else {
1615                 tmp_edge.uv1 = uv2;
1616                 tmp_edge.uv2 = uv1;
1617         }
1618
1619         return BLI_ghash_lookup(state->edge_hash, &tmp_edge);
1620 }
1621
1622 static int stitch_init(bContext *C, wmOperator *op)
1623 {
1624         /* for fast edge lookup... */
1625         GHash *edge_hash;
1626         /* ...and actual edge storage */
1627         UvEdge *edges;
1628         int total_edges;
1629         /* maps uvelements to their first coincident uv */
1630         int *map;
1631         int counter = 0, i;
1632         BMFace *efa;
1633         BMLoop *l;
1634         BMIter iter, liter;
1635         GHashIterator gh_iter;
1636         UvEdge *all_edges;
1637         StitchState *state;
1638         Scene *scene = CTX_data_scene(C);
1639         ToolSettings *ts = scene->toolsettings;
1640         ARegion *ar = CTX_wm_region(C);
1641         float aspx, aspy;
1642         Object *obedit = CTX_data_edit_object(C);
1643         BMEditMesh *em = BKE_editmesh_from_object(obedit);
1644         const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
1645
1646         if (!ar)
1647                 return 0;
1648
1649         state = MEM_callocN(sizeof(StitchState), "stitch state");
1650
1651         op->customdata = state;
1652
1653         /* initialize state */
1654         state->use_limit = RNA_boolean_get(op->ptr, "use_limit");
1655         state->limit_dist = RNA_float_get(op->ptr, "limit");
1656         state->em = em;
1657         state->snap_islands = RNA_boolean_get(op->ptr, "snap_islands");
1658         state->static_island = RNA_int_get(op->ptr, "static_island");
1659         state->midpoints = RNA_boolean_get(op->ptr, "midpoint_snap");
1660         state->clear_seams = RNA_boolean_get(op->ptr, "clear_seams");
1661         if (RNA_struct_property_is_set(op->ptr, "mode")) {
1662                 state->mode = RNA_enum_get(op->ptr, "mode");
1663         }
1664         else {
1665                 if (ts->uv_flag & UV_SYNC_SELECTION) {
1666                         if (ts->selectmode & SCE_SELECT_VERTEX)
1667                                 state->mode = STITCH_VERT;
1668                         else
1669                                 state->mode = STITCH_EDGE;
1670                 }
1671                 else {
1672                         if (ts->uv_selectmode & UV_SELECT_VERTEX) {
1673                                 state->mode = STITCH_VERT;
1674                         }
1675                         else {
1676                                 state->mode = STITCH_EDGE;
1677                         }
1678                 }
1679         }
1680
1681         /* in uv synch selection, all uv's are visible */
1682         if (ts->uv_flag & UV_SYNC_SELECTION) {
1683                 state->element_map = BM_uv_element_map_create(state->em->bm, false, true, true);
1684         }
1685         else {
1686                 state->element_map = BM_uv_element_map_create(state->em->bm, true, true, true);
1687         }
1688         if (!state->element_map) {
1689                 state_delete(state);
1690                 return 0;
1691         }
1692
1693         ED_uvedit_get_aspect(scene, obedit, em->bm, &aspx, &aspy);
1694         state->aspect = aspx / aspy;
1695
1696         /* Entirely possible if redoing last operator that static island is bigger than total number of islands.
1697          * This ensures we get no hang in the island checking code in stitch_stitch_process_data. */
1698         state->static_island %= state->element_map->totalIslands;
1699
1700         /* Count 'unique' uvs */
1701         for (i = 0; i < state->element_map->totalUVs; i++) {
1702                 if (state->element_map->buf[i].separate) {
1703                         counter++;
1704                 }
1705         }
1706
1707         /* explicitly set preview to NULL, to avoid deleting an invalid pointer on stitch_process_data */
1708         state->stitch_preview = NULL;
1709         /* Allocate the unique uv buffers */
1710         state->uvs = MEM_mallocN(sizeof(*state->uvs) * counter, "uv_stitch_unique_uvs");
1711         /* internal uvs need no normals but it is hard and slow to keep a map of
1712          * normals only for boundary uvs, so allocating for all uvs */
1713         state->normals = MEM_callocN(sizeof(*state->normals) * counter * 2, "uv_stitch_normals");
1714         state->total_separate_uvs = counter;
1715         state->map = map = MEM_mallocN(sizeof(*map) * state->element_map->totalUVs, "uv_stitch_unique_map");
1716         /* Allocate the edge stack */
1717         edge_hash = BLI_ghash_new(uv_edge_hash, uv_edge_compare, "stitch_edge_hash");
1718         all_edges = MEM_mallocN(sizeof(*all_edges) * state->element_map->totalUVs, "stitch_all_edges");
1719
1720         if (!state->uvs || !map || !edge_hash || !all_edges) {
1721                 state_delete(state);
1722                 return 0;
1723         }
1724
1725         /* So that we can use this as index for the UvElements */
1726         counter = -1;
1727         /* initialize the unique UVs and map */
1728         for (i = 0; i < em->bm->totvert; i++) {
1729                 UvElement *element = state->element_map->vert[i];
1730                 for (; element; element = element->next) {
1731                         if (element->separate) {
1732                                 counter++;
1733                                 state->uvs[counter] = element;
1734                         }
1735                         /* pointer arithmetic to the rescue, as always :)*/
1736                         map[element - state->element_map->buf] = counter;
1737                 }
1738         }
1739
1740         counter = 0;
1741         /* Now, on to generate our uv connectivity data */
1742         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1743                 if (!(ts->uv_flag & UV_SYNC_SELECTION) &&
1744                     ((BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) || !BM_elem_flag_test(efa, BM_ELEM_SELECT)))
1745                 {
1746                         continue;
1747                 }
1748
1749                 BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
1750                         UvElement *element = BM_uv_element_get(state->element_map, efa, l);
1751                         int offset1, itmp1 = element - state->element_map->buf;
1752                         int offset2, itmp2 = BM_uv_element_get(state->element_map, efa, l->next) - state->element_map->buf;
1753                         UvEdge *edge;
1754
1755                         offset1 = map[itmp1];
1756                         offset2 = map[itmp2];
1757
1758                         all_edges[counter].next = NULL;
1759                         all_edges[counter].first = NULL;
1760                         all_edges[counter].flag = 0;
1761                         all_edges[counter].element = element;
1762                         /* using an order policy, sort uvs according to address space. This avoids
1763                          * Having two different UvEdges with the same uvs on different positions  */
1764                         if (offset1 < offset2) {
1765                                 all_edges[counter].uv1 = offset1;
1766                                 all_edges[counter].uv2 = offset2;
1767                         }
1768                         else {
1769                                 all_edges[counter].uv1 = offset2;
1770                                 all_edges[counter].uv2 = offset1;
1771                         }
1772
1773                         edge = BLI_ghash_lookup(edge_hash, &all_edges[counter]);
1774                         if (edge) {
1775                                 edge->flag = 0;
1776                         }
1777                         else {
1778                                 BLI_ghash_insert(edge_hash, &all_edges[counter], &all_edges[counter]);
1779                                 all_edges[counter].flag = STITCH_BOUNDARY;
1780                         }
1781                         counter++;
1782                 }
1783         }
1784
1785         total_edges = BLI_ghash_len(edge_hash);
1786         state->edges = edges = MEM_mallocN(sizeof(*edges) * total_edges, "stitch_edges");
1787
1788         /* I assume any system will be able to at least allocate an iterator :p */
1789         if (!edges) {
1790                 state_delete(state);
1791                 return 0;
1792         }
1793
1794         state->total_separate_edges = total_edges;
1795
1796         /* fill the edges with data */
1797         i = 0;
1798         GHASH_ITER (gh_iter, edge_hash) {
1799                 edges[i++] = *((UvEdge *)BLI_ghashIterator_getKey(&gh_iter));
1800         }
1801
1802         /* cleanup temporary stuff */
1803         MEM_freeN(all_edges);
1804
1805         BLI_ghash_free(edge_hash, NULL, NULL);
1806
1807         /* refill an edge hash to create edge connnectivity data */
1808         state->edge_hash = edge_hash = BLI_ghash_new(uv_edge_hash, uv_edge_compare, "stitch_edge_hash");
1809         for (i = 0; i < total_edges; i++) {
1810                 BLI_ghash_insert(edge_hash, edges + i, edges + i);
1811         }
1812         stitch_uv_edge_generate_linked_edges(edge_hash, state);
1813
1814         /***** calculate 2D normals for boundary uvs *****/
1815
1816         /* we use boundary edges to calculate 2D normals.
1817          * to disambiguate the direction of the normal, we also need
1818          * a point "inside" the island, that can be provided by
1819          * the winding of the polygon (assuming counter-clockwise flow). */
1820
1821         for (i = 0; i < total_edges; i++) {
1822                 UvEdge *edge = edges + i;
1823                 float normal[2];
1824                 if (edge->flag & STITCH_BOUNDARY) {
1825                         stitch_calculate_edge_normal(em, edge, normal, state->aspect);
1826
1827                         add_v2_v2(state->normals + edge->uv1 * 2, normal);
1828                         add_v2_v2(state->normals + edge->uv2 * 2, normal);
1829
1830                         normalize_v2(state->normals + edge->uv1 * 2);
1831                         normalize_v2(state->normals + edge->uv2 * 2);
1832                 }
1833         }
1834
1835
1836         /***** fill selection stack *******/
1837
1838         state->selection_size = 0;
1839
1840         /* Load old selection if redoing operator with different settings */
1841         if (RNA_struct_property_is_set(op->ptr, "selection")) {
1842                 int faceIndex, elementIndex;
1843                 UvElement *element;
1844                 enum StitchModes stored_mode = RNA_enum_get(op->ptr, "stored_mode");
1845
1846                 BM_mesh_elem_table_ensure(em->bm, BM_FACE);
1847
1848                 if (stored_mode == STITCH_VERT) {
1849                         state->selection_stack = MEM_mallocN(sizeof(*state->selection_stack) * state->total_separate_uvs, "uv_stitch_selection_stack");
1850
1851                         RNA_BEGIN (op->ptr, itemptr, "selection")
1852                         {
1853                                 faceIndex = RNA_int_get(&itemptr, "face_index");
1854                                 elementIndex = RNA_int_get(&itemptr, "element_index");
1855                                 efa = BM_face_at_index(em->bm, faceIndex);
1856                                 element = BM_uv_element_get(state->element_map, efa, BM_iter_at_index(NULL, BM_LOOPS_OF_FACE, efa, elementIndex));
1857                                 stitch_select_uv(element, state, 1);
1858                         }
1859                         RNA_END;
1860                 }
1861                 else {
1862                         state->selection_stack = MEM_mallocN(sizeof(*state->selection_stack) * state->total_separate_edges, "uv_stitch_selection_stack");
1863
1864                         RNA_BEGIN (op->ptr, itemptr, "selection")
1865                         {
1866                                 UvEdge tmp_edge, *edge;
1867                                 int uv1, uv2;
1868                                 faceIndex = RNA_int_get(&itemptr, "face_index");
1869                                 elementIndex = RNA_int_get(&itemptr, "element_index");
1870                                 efa = BM_face_at_index(em->bm, faceIndex);
1871                                 element = BM_uv_element_get(state->element_map, efa, BM_iter_at_index(NULL, BM_LOOPS_OF_FACE, efa, elementIndex));
1872                                 uv1 = map[element - state->element_map->buf];
1873
1874                                 element = BM_uv_element_get(state->element_map, efa, BM_iter_at_index(NULL, BM_LOOPS_OF_FACE, efa, (elementIndex + 1) % efa->len));
1875                                 uv2 = map[element - state->element_map->buf];
1876
1877                                 if (uv1 < uv2) {
1878                                         tmp_edge.uv1 = uv1;
1879                                         tmp_edge.uv2 = uv2;
1880                                 }
1881                                 else {
1882                                         tmp_edge.uv1 = uv2;
1883                                         tmp_edge.uv2 = uv1;
1884                                 }
1885
1886                                 edge = BLI_ghash_lookup(edge_hash, &tmp_edge);
1887
1888                                 stitch_select_edge(edge, state, true);
1889                         }
1890                         RNA_END;
1891                 }
1892                 /* if user has switched the operator mode after operation, we need to convert
1893                  * the stored format */
1894                 if (state->mode != stored_mode) {
1895                         state->mode = stored_mode;
1896                         stitch_switch_selection_mode(state);
1897                 }
1898                 /* Clear the selection */
1899                 RNA_collection_clear(op->ptr, "selection");
1900
1901         }
1902         else {
1903                 if (state->mode == STITCH_VERT) {
1904                         state->selection_stack = MEM_mallocN(sizeof(*state->selection_stack) * state->total_separate_uvs, "uv_stitch_selection_stack");
1905
1906                         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1907                                 BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, i) {
1908                                         if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
1909                                                 UvElement *element = BM_uv_element_get(state->element_map, efa, l);
1910                                                 if (element) {
1911                                                         stitch_select_uv(element, state, 1);
1912                                                 }
1913                                         }
1914                                 }
1915                         }
1916                 }
1917                 else {
1918                         state->selection_stack = MEM_mallocN(sizeof(*state->selection_stack) * state->total_separate_edges, "uv_stitch_selection_stack");
1919
1920                         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1921                                 if (!(ts->uv_flag & UV_SYNC_SELECTION) &&
1922                                     ((BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) || !BM_elem_flag_test(efa, BM_ELEM_SELECT)))
1923                                 {
1924                                         continue;
1925                                 }
1926
1927                                 BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
1928                                         if (uvedit_edge_select_test(scene, l, cd_loop_uv_offset)) {
1929                                                 UvEdge *edge = uv_edge_get(l, state);
1930                                                 if (edge) {
1931                                                         stitch_select_edge(edge, state, true);
1932                                                 }
1933                                         }
1934                                 }
1935                         }
1936                 }
1937         }
1938
1939         /***** initialize static island preview data *****/
1940
1941         state->tris_per_island = MEM_mallocN(sizeof(*state->tris_per_island) * state->element_map->totalIslands,
1942                                              "stitch island tris");
1943         for (i = 0; i < state->element_map->totalIslands; i++) {
1944                 state->tris_per_island[i] = 0;
1945         }
1946
1947         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1948                 UvElement *element = BM_uv_element_get(state->element_map, efa, BM_FACE_FIRST_LOOP(efa));
1949
1950                 if (element) {
1951                         state->tris_per_island[element->island] += (efa->len > 2) ? efa->len - 2 : 0;
1952                 }
1953         }
1954
1955         if (!stitch_process_data(state, scene, false)) {
1956
1957                 state_delete(state);
1958                 return 0;
1959         }
1960
1961         state->draw_handle = ED_region_draw_cb_activate(ar->type, stitch_draw, state, REGION_DRAW_POST_VIEW);
1962
1963         stitch_update_header(state, C);
1964         return 1;
1965 }
1966
1967 static int stitch_invoke(bContext *C, wmOperator *op, const wmEvent *UNUSED(event))
1968 {
1969         Object *obedit = CTX_data_edit_object(C);
1970         if (!stitch_init(C, op))
1971                 return OPERATOR_CANCELLED;
1972
1973         WM_event_add_modal_handler(C, op);
1974         WM_event_add_notifier(C, NC_GEOM | ND_DATA, obedit->data);
1975         return OPERATOR_RUNNING_MODAL;
1976 }
1977
1978 static void stitch_exit(bContext *C, wmOperator *op, int finished)
1979 {
1980         StitchState *state;
1981         Scene *scene;
1982         SpaceImage *sima;
1983         ScrArea *sa = CTX_wm_area(C);
1984         Object *obedit;
1985
1986         scene = CTX_data_scene(C);
1987         obedit = CTX_data_edit_object(C);
1988         sima = CTX_wm_space_image(C);
1989
1990         state = (StitchState *)op->customdata;
1991
1992         if (finished) {
1993                 int i;
1994
1995                 RNA_float_set(op->ptr, "limit", state->limit_dist);
1996                 RNA_boolean_set(op->ptr, "use_limit", state->use_limit);
1997                 RNA_boolean_set(op->ptr, "snap_islands", state->snap_islands);
1998                 RNA_int_set(op->ptr, "static_island", state->static_island);
1999                 RNA_boolean_set(op->ptr, "midpoint_snap", state->midpoints);
2000                 RNA_enum_set(op->ptr, "mode", state->mode);
2001                 RNA_enum_set(op->ptr, "stored_mode", state->mode);
2002
2003                 /* Store selection for re-execution of stitch */
2004                 for (i = 0; i < state->selection_size; i++) {
2005                         UvElement *element;
2006                         PointerRNA itemptr;
2007                         if (state->mode == STITCH_VERT) {
2008                                 element = state->selection_stack[i];
2009                         }
2010                         else {
2011                                 element = ((UvEdge *)state->selection_stack[i])->element;
2012                         }
2013                         RNA_collection_add(op->ptr, "selection", &itemptr);
2014
2015                         RNA_int_set(&itemptr, "face_index", BM_elem_index_get(element->l->f));
2016                         RNA_int_set(&itemptr, "element_index", element->tfindex);
2017                 }
2018
2019                 uvedit_live_unwrap_update(sima, scene, obedit);
2020         }
2021
2022         if (sa)
2023                 ED_area_headerprint(sa, NULL);
2024
2025         ED_region_draw_cb_exit(CTX_wm_region(C)->type, state->draw_handle);
2026
2027         DAG_id_tag_update(obedit->data, 0);
2028         WM_event_add_notifier(C, NC_GEOM | ND_DATA, obedit->data);
2029
2030         state_delete(state);
2031         op->customdata = NULL;
2032 }
2033
2034
2035 static void stitch_cancel(bContext *C, wmOperator *op)
2036 {
2037         stitch_exit(C, op, 0);
2038 }
2039
2040
2041 static int stitch_exec(bContext *C, wmOperator *op)
2042 {
2043         Scene *scene = CTX_data_scene(C);
2044
2045         if (!stitch_init(C, op))
2046                 return OPERATOR_CANCELLED;
2047         if (stitch_process_data((StitchState *)op->customdata, scene, 1)) {
2048                 stitch_exit(C, op, 1);
2049                 return OPERATOR_FINISHED;
2050         }
2051         else {
2052                 stitch_cancel(C, op);
2053                 return OPERATOR_CANCELLED;
2054         }
2055 }
2056
2057 static void stitch_select(bContext *C, Scene *scene, const wmEvent *event, StitchState *state)
2058 {
2059         /* add uv under mouse to processed uv's */
2060         float co[2];
2061         NearestHit hit;
2062         ARegion *ar = CTX_wm_region(C);
2063         Image *ima = CTX_data_edit_image(C);
2064
2065         UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1], &co[0], &co[1]);
2066
2067         if (state->mode == STITCH_VERT) {
2068                 uv_find_nearest_vert(scene, ima, state->em, co, NULL, &hit);
2069
2070                 if (hit.efa) {
2071                         /* Add vertex to selection, deselect all common uv's of vert other
2072                          * than selected and update the preview. This behavior was decided so that
2073                          * you can do stuff like deselect the opposite stitchable vertex and the initial still gets deselected */
2074
2075                         /* This works due to setting of tmp in find nearest uv vert */
2076                         UvElement *element = BM_uv_element_get(state->element_map, hit.efa, hit.l);
2077                         stitch_select_uv(element, state, false);
2078
2079                 }
2080         }
2081         else {
2082                 uv_find_nearest_edge(scene, ima, state->em, co, &hit);
2083
2084                 if (hit.efa) {
2085                         UvEdge *edge = uv_edge_get(hit.l, state);
2086                         stitch_select_edge(edge, state, false);
2087                 }
2088         }
2089 }
2090
2091 static int stitch_modal(bContext *C, wmOperator *op, const wmEvent *event)
2092 {
2093         StitchState *state;
2094         Scene *scene = CTX_data_scene(C);
2095
2096         state = (StitchState *)op->customdata;
2097
2098         switch (event->type) {
2099                 case MIDDLEMOUSE:
2100                         return OPERATOR_PASS_THROUGH;
2101
2102                         /* Cancel */
2103                 case ESCKEY:
2104                         stitch_cancel(C, op);
2105                         return OPERATOR_CANCELLED;
2106
2107                 case LEFTMOUSE:
2108                         if (event->shift && (U.flag & USER_LMOUSESELECT)) {
2109                                 if (event->val == KM_PRESS) {
2110                                         stitch_select(C, scene, event, state);
2111
2112                                         if (!stitch_process_data(state, scene, false)) {
2113                                                 stitch_cancel(C, op);
2114                                                 return OPERATOR_CANCELLED;
2115                                         }
2116                                 }
2117                                 break;
2118                         }
2119                         ATTR_FALLTHROUGH;
2120                 case PADENTER:
2121                 case RETKEY:
2122                         if (event->val == KM_PRESS) {
2123                                 if (stitch_process_data(state, scene, true)) {
2124                                         stitch_exit(C, op, 1);
2125                                         return OPERATOR_FINISHED;
2126                                 }
2127                                 else {
2128                                         stitch_cancel(C, op);
2129                                         return OPERATOR_CANCELLED;
2130                                 }
2131                         }
2132                         else {
2133                                 return OPERATOR_PASS_THROUGH;
2134                         }
2135                         /* Increase limit */
2136                 case PADPLUSKEY:
2137                 case WHEELUPMOUSE:
2138                         if (event->val == KM_PRESS && event->alt) {
2139                                 state->limit_dist += 0.01f;
2140                                 if (!stitch_process_data(state, scene, false)) {
2141                                         stitch_cancel(C, op);
2142                                         return OPERATOR_CANCELLED;
2143                                 }
2144                                 break;
2145                         }
2146                         else {
2147                                 return OPERATOR_PASS_THROUGH;
2148                         }
2149                         /* Decrease limit */
2150                 case PADMINUS:
2151                 case WHEELDOWNMOUSE:
2152                         if (event->val == KM_PRESS && event->alt) {
2153                                 state->limit_dist -= 0.01f;
2154                                 state->limit_dist = MAX2(0.01f, state->limit_dist);
2155                                 if (!stitch_process_data(state, scene, false)) {
2156                                         stitch_cancel(C, op);
2157                                         return OPERATOR_CANCELLED;
2158                                 }
2159                                 break;
2160                         }
2161                         else {
2162                                 return OPERATOR_PASS_THROUGH;
2163                         }
2164
2165                         /* Use Limit (Default off) */
2166                 case LKEY:
2167                         if (event->val == KM_PRESS) {
2168                                 state->use_limit = !state->use_limit;
2169                                 if (!stitch_process_data(state, scene, false)) {
2170                                         stitch_cancel(C, op);
2171                                         return OPERATOR_CANCELLED;
2172                                 }
2173                                 break;
2174                         }
2175                         return OPERATOR_RUNNING_MODAL;
2176
2177                 case IKEY:
2178                         if (event->val == KM_PRESS) {
2179                                 state->static_island++;
2180                                 state->static_island %= state->element_map->totalIslands;
2181
2182                                 if (!stitch_process_data(state, scene, false)) {
2183                                         stitch_cancel(C, op);
2184                                         return OPERATOR_CANCELLED;
2185                                 }
2186                                 break;
2187                         }
2188                         return OPERATOR_RUNNING_MODAL;
2189
2190                 case MKEY:
2191                         if (event->val == KM_PRESS) {
2192                                 state->midpoints = !state->midpoints;
2193                                 if (!stitch_process_data(state, scene, false)) {
2194                                         stitch_cancel(C, op);
2195                                         return OPERATOR_CANCELLED;
2196                                 }
2197                         }
2198                         break;
2199
2200                         /* Select geometry */
2201                 case RIGHTMOUSE:
2202                         if (!event->shift) {
2203                                 stitch_cancel(C, op);
2204                                 return OPERATOR_CANCELLED;
2205                         }
2206                         if (event->val == KM_PRESS && !(U.flag & USER_LMOUSESELECT)) {
2207                                 stitch_select(C, scene, event, state);
2208
2209                                 if (!stitch_process_data(state, scene, false)) {
2210                                         stitch_cancel(C, op);
2211                                         return OPERATOR_CANCELLED;
2212                                 }
2213                                 break;
2214                         }
2215                         return OPERATOR_RUNNING_MODAL;
2216
2217                         /* snap islands on/off */
2218                 case SKEY:
2219                         if (event->val == KM_PRESS) {
2220                                 state->snap_islands = !state->snap_islands;
2221                                 if (!stitch_process_data(state, scene, false)) {
2222                                         stitch_cancel(C, op);
2223                                         return OPERATOR_CANCELLED;
2224                                 }
2225                                 break;
2226                         }
2227                         else {
2228                                 return OPERATOR_RUNNING_MODAL;
2229                         }
2230
2231                         /* switch between edge/vertex mode */
2232                 case TABKEY:
2233                         if (event->val == KM_PRESS) {
2234                                 stitch_switch_selection_mode(state);
2235
2236                                 if (!stitch_process_data(state, scene, false)) {
2237                                         stitch_cancel(C, op);
2238                                         return OPERATOR_CANCELLED;
2239                                 }
2240                         }
2241                         break;
2242
2243                 default:
2244                         return OPERATOR_RUNNING_MODAL;
2245         }
2246
2247         /* if updated settings, renew feedback message */
2248         stitch_update_header(state, C);
2249         ED_region_tag_redraw(CTX_wm_region(C));
2250         return OPERATOR_RUNNING_MODAL;
2251 }
2252
2253 void UV_OT_stitch(wmOperatorType *ot)
2254 {
2255         PropertyRNA *prop;
2256
2257         static const EnumPropertyItem stitch_modes[] = {
2258             {STITCH_VERT, "VERTEX", 0, "Vertex", ""},
2259             {STITCH_EDGE, "EDGE", 0, "Edge", ""},
2260             {0, NULL, 0, NULL, NULL}
2261         };
2262
2263         /* identifiers */
2264         ot->name = "Stitch";
2265         ot->description = "Stitch selected UV vertices by proximity";
2266         ot->idname = "UV_OT_stitch";
2267         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2268
2269         /* api callbacks */
2270         ot->invoke = stitch_invoke;
2271         ot->modal = stitch_modal;
2272         ot->exec = stitch_exec;
2273         ot->cancel = stitch_cancel;
2274         ot->poll = ED_operator_uvedit;
2275
2276         /* properties */
2277         RNA_def_boolean(ot->srna, "use_limit", 0, "Use Limit", "Stitch UVs within a specified limit distance");
2278         RNA_def_boolean(ot->srna, "snap_islands", 1, "Snap Islands",
2279                         "Snap islands together (on edge stitch mode, rotates the islands too)");
2280
2281         RNA_def_float(ot->srna, "limit", 0.01f, 0.0f, FLT_MAX, "Limit",
2282                       "Limit distance in normalized coordinates", 0.0, FLT_MAX);
2283         RNA_def_int(ot->srna, "static_island", 0, 0, INT_MAX, "Static Island",
2284                     "Island that stays in place when stitching islands", 0, INT_MAX);
2285         RNA_def_boolean(ot->srna, "midpoint_snap", 0, "Snap At Midpoint",
2286                         "UVs are stitched at midpoint instead of at static island");
2287         RNA_def_boolean(ot->srna, "clear_seams", 1, "Clear Seams",
2288                         "Clear seams of stitched edges");
2289         RNA_def_enum(ot->srna, "mode", stitch_modes, STITCH_VERT, "Operation Mode",
2290                      "Use vertex or edge stitching");
2291         prop =  RNA_def_enum(ot->srna, "stored_mode", stitch_modes, STITCH_VERT, "Stored Operation Mode",
2292                              "Use vertex or edge stitching");
2293         RNA_def_property_flag(prop, PROP_HIDDEN);
2294         prop = RNA_def_collection_runtime(ot->srna, "selection", &RNA_SelectedUvElement, "Selection", "");
2295         /* Selection should not be editable or viewed in toolbar */
2296         RNA_def_property_flag(prop, PROP_HIDDEN);
2297 }