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