add option so operators can be called with a flag, currently the only flag is to...
[blender.git] / source / blender / editors / mesh / editmesh_utils.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) 2004 by Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joseph Eagar
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/mesh/editmesh_utils.c
29  *  \ingroup edmesh
30  */
31
32 #include "MEM_guardedalloc.h"
33
34 #include "DNA_mesh_types.h"
35 #include "DNA_object_types.h"
36 #include "DNA_scene_types.h"
37
38 #include "BLI_blenlib.h"
39 #include "BLI_math.h"
40
41 #include "BKE_DerivedMesh.h"
42 #include "BKE_bmesh.h"
43 #include "BKE_context.h"
44 #include "BKE_depsgraph.h"
45 #include "BKE_key.h"
46 #include "BKE_library.h"
47 #include "BKE_mesh.h"
48 #include "BKE_report.h"
49 #include "BKE_tessmesh.h"
50
51 #include "WM_api.h"
52 #include "WM_types.h"
53
54 #include "ED_mesh.h"
55 #include "ED_util.h"
56
57 #include "bmesh.h"
58
59 #include "mesh_intern.h"
60
61 /* mesh backup implementation. This would greatly benefit from some sort of binary diffing
62  * just as the undo stack would. So leaving this as an interface for further work */
63
64 BMBackup EDBM_redo_state_store(BMEditMesh *em)
65 {
66         BMBackup backup;
67         backup.bmcopy = BM_mesh_copy(em->bm);
68         return backup;
69 }
70
71 void EDBM_redo_state_restore(BMBackup backup, BMEditMesh *em, int recalctess)
72 {
73         BMesh *tmpbm;
74         if (!em || !backup.bmcopy)
75                 return;
76
77         BM_mesh_data_free(em->bm);
78         tmpbm = BM_mesh_copy(backup.bmcopy);
79         *em->bm = *tmpbm;
80         MEM_freeN(tmpbm);
81         tmpbm = NULL;
82
83         if (recalctess)
84                 BMEdit_RecalcTessellation(em);
85 }
86
87 void EDBM_redo_state_free(BMBackup *backup, BMEditMesh *em, int recalctess)
88 {
89         if (em && backup->bmcopy) {
90                 BM_mesh_data_free(em->bm);
91                 *em->bm = *backup->bmcopy;
92         }
93         else if (backup->bmcopy) {
94                 BM_mesh_data_free(backup->bmcopy);
95         }
96
97         if (backup->bmcopy)
98                 MEM_freeN(backup->bmcopy);
99         backup->bmcopy = NULL;
100
101         if (recalctess && em)
102                 BMEdit_RecalcTessellation(em);
103 }
104
105
106
107 void EDBM_mesh_normals_update(BMEditMesh *em)
108 {
109         BM_mesh_normals_update(em->bm, TRUE);
110 }
111
112 void EDBM_mesh_clear(BMEditMesh *em)
113 {
114         /* clear bmesh */
115         BM_mesh_clear(em->bm);
116         
117         /* free derived meshes */
118         if (em->derivedCage) {
119                 em->derivedCage->needsFree = 1;
120                 em->derivedCage->release(em->derivedCage);
121         }
122         if (em->derivedFinal && em->derivedFinal != em->derivedCage) {
123                 em->derivedFinal->needsFree = 1;
124                 em->derivedFinal->release(em->derivedFinal);
125         }
126         
127         em->derivedCage = em->derivedFinal = NULL;
128         
129         /* free tessellation data */
130         em->tottri = 0;
131         if (em->looptris) 
132                 MEM_freeN(em->looptris);
133 }
134
135 void EDBM_stats_update(BMEditMesh *em)
136 {
137         const char iter_types[3] = {BM_VERTS_OF_MESH,
138                                     BM_EDGES_OF_MESH,
139                                     BM_FACES_OF_MESH};
140
141         BMIter iter;
142         BMElem *ele;
143         int *tots[3];
144         int i;
145
146         tots[0] = &em->bm->totvertsel;
147         tots[1] = &em->bm->totedgesel;
148         tots[2] = &em->bm->totfacesel;
149         
150         em->bm->totvertsel = em->bm->totedgesel = em->bm->totfacesel = 0;
151
152         for (i = 0; i < 3; i++) {
153                 ele = BM_iter_new(&iter, em->bm, iter_types[i], NULL);
154                 for ( ; ele; ele = BM_iter_step(&iter)) {
155                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
156                                 (*tots[i])++;
157                         }
158                 }
159         }
160 }
161
162 int EDBM_op_init(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const char *fmt, ...)
163 {
164         BMesh *bm = em->bm;
165         va_list list;
166
167         va_start(list, fmt);
168
169         if (!BMO_op_vinitf(bm, bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
170                 BKE_reportf(op->reports, RPT_ERROR, "Parse error in %s", __func__);
171                 va_end(list);
172                 return 0;
173         }
174         
175         if (!em->emcopy)
176                 em->emcopy = BMEdit_Copy(em);
177         em->emcopyusers++;
178
179         va_end(list);
180
181         return 1;
182 }
183
184
185 /* returns 0 on error, 1 on success.  executes and finishes a bmesh operator */
186 int EDBM_op_finish(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const int report)
187 {
188         const char *errmsg;
189         
190         BMO_op_finish(em->bm, bmop);
191
192         if (BMO_error_get(em->bm, &errmsg, NULL)) {
193                 BMEditMesh *emcopy = em->emcopy;
194
195                 if (report) {
196                         BKE_report(op->reports, RPT_ERROR, errmsg);
197                 }
198
199                 EDBM_mesh_free(em);
200                 *em = *emcopy;
201
202                 MEM_freeN(emcopy);
203                 em->emcopyusers = 0;
204                 em->emcopy = NULL;
205
206                 /* when copying, tessellation isn't to for faster copying,
207                  * but means we need to re-tessellate here */
208                 if (em->looptris == NULL) {
209                         BMEdit_RecalcTessellation(em);
210                 }
211
212                 return FALSE;
213         }
214         else {
215                 em->emcopyusers--;
216                 if (em->emcopyusers < 0) {
217                         printf("warning: em->emcopyusers was less then zero.\n");
218                 }
219
220                 if (em->emcopyusers <= 0) {
221                         BMEdit_Free(em->emcopy);
222                         MEM_freeN(em->emcopy);
223                         em->emcopy = NULL;
224                 }
225
226                 return TRUE;
227         }
228 }
229
230 int EDBM_op_callf(BMEditMesh *em, wmOperator *op, const char *fmt, ...)
231 {
232         BMesh *bm = em->bm;
233         BMOperator bmop;
234         va_list list;
235
236         va_start(list, fmt);
237
238         if (!BMO_op_vinitf(bm, &bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
239                 BKE_reportf(op->reports, RPT_ERROR, "Parse error in %s", __func__);
240                 va_end(list);
241                 return 0;
242         }
243
244         if (!em->emcopy)
245                 em->emcopy = BMEdit_Copy(em);
246         em->emcopyusers++;
247
248         BMO_op_exec(bm, &bmop);
249
250         va_end(list);
251         return EDBM_op_finish(em, &bmop, op, TRUE);
252 }
253
254 int EDBM_op_call_and_selectf(BMEditMesh *em, wmOperator *op, const char *selectslot, const char *fmt, ...)
255 {
256         BMesh *bm = em->bm;
257         BMOperator bmop;
258         va_list list;
259
260         va_start(list, fmt);
261
262         if (!BMO_op_vinitf(bm, &bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
263                 BKE_reportf(op->reports, RPT_ERROR, "Parse error in %s", __func__);
264                 va_end(list);
265                 return 0;
266         }
267
268         if (!em->emcopy)
269                 em->emcopy = BMEdit_Copy(em);
270         em->emcopyusers++;
271
272         BMO_op_exec(bm, &bmop);
273
274         BM_mesh_elem_hflag_disable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_SELECT, FALSE);
275
276         BMO_slot_buffer_hflag_enable(em->bm, &bmop, selectslot, BM_ALL, BM_ELEM_SELECT, TRUE);
277
278         va_end(list);
279         return EDBM_op_finish(em, &bmop, op, TRUE);
280 }
281
282 int EDBM_op_call_silentf(BMEditMesh *em, const char *fmt, ...)
283 {
284         BMesh *bm = em->bm;
285         BMOperator bmop;
286         va_list list;
287
288         va_start(list, fmt);
289
290         if (!BMO_op_vinitf(bm, &bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
291                 va_end(list);
292                 return 0;
293         }
294
295         if (!em->emcopy)
296                 em->emcopy = BMEdit_Copy(em);
297         em->emcopyusers++;
298
299         BMO_op_exec(bm, &bmop);
300
301         va_end(list);
302         return EDBM_op_finish(em, &bmop, NULL, FALSE);
303 }
304
305 void EDBM_selectmode_to_scene(bContext *C)
306 {
307         Scene *scene = CTX_data_scene(C);
308         Object *obedit = CTX_data_edit_object(C);
309         BMEditMesh *em = BMEdit_FromObject(obedit);
310
311         if (!em)
312                 return;
313
314         scene->toolsettings->selectmode = em->selectmode;
315
316         /* Request redraw of header buttons (to show new select mode) */
317         WM_event_add_notifier(C, NC_SCENE | ND_TOOLSETTINGS, scene);
318 }
319
320 void EDBM_mesh_make(ToolSettings *ts, Scene *UNUSED(scene), Object *ob)
321 {
322         Mesh *me = ob->data;
323         BMesh *bm;
324
325         if (UNLIKELY(!me->mpoly && me->totface)) {
326                 BKE_mesh_convert_mfaces_to_mpolys(me);
327         }
328
329         bm = BKE_mesh_to_bmesh(me, ob);
330
331         if (me->edit_btmesh) {
332                 /* this happens when switching shape keys */
333                 EDBM_mesh_free(me->edit_btmesh);
334                 MEM_freeN(me->edit_btmesh);
335         }
336
337         /* currently executing operators re-tessellates, so we can avoid doing here
338          * but at some point it may need to be added back. */
339 #if 0
340         me->edit_btmesh = BMEdit_Create(bm, TRUE);
341 #else
342         me->edit_btmesh = BMEdit_Create(bm, FALSE);
343 #endif
344
345         me->edit_btmesh->selectmode = me->edit_btmesh->bm->selectmode = ts->selectmode;
346         me->edit_btmesh->mat_nr = (ob->actcol > 0) ? ob->actcol - 1 : 0;
347
348         me->edit_btmesh->me = me;
349         me->edit_btmesh->ob = ob;
350 }
351
352 void EDBM_mesh_load(Object *ob)
353 {
354         Mesh *me = ob->data;
355         BMesh *bm = me->edit_btmesh->bm;
356
357         BM_mesh_bm_to_me(bm, me, FALSE);
358
359 #ifdef USE_TESSFACE_DEFAULT
360         BKE_mesh_tessface_calc(me);
361 #endif
362 }
363
364 /**
365  * Should only be called on the active editmesh, otherwise call #BMEdit_Free
366  */
367 void EDBM_mesh_free(BMEditMesh *em)
368 {
369         /* These tables aren't used yet, so it's not strictly necessary
370          * to 'end' them (with 'e' param) but if someone tries to start
371          * using them, having these in place will save a lot of pain */
372         mesh_octree_table(NULL, NULL, NULL, 'e');
373         mesh_mirrtopo_table(NULL, 'e');
374
375         BMEdit_Free(em);
376 }
377
378 void EDBM_index_arrays_init(BMEditMesh *tm, int forvert, int foredge, int forface)
379 {
380         EDBM_index_arrays_free(tm);
381
382         if (forvert) {
383                 BMIter iter;
384                 BMVert *ele;
385                 int i = 0;
386                 
387                 tm->vert_index = MEM_mallocN(sizeof(void **) * tm->bm->totvert, "tm->vert_index");
388
389                 ele = BM_iter_new(&iter, tm->bm, BM_VERTS_OF_MESH, NULL);
390                 for ( ; ele; ele = BM_iter_step(&iter)) {
391                         tm->vert_index[i++] = ele;
392                 }
393         }
394
395         if (foredge) {
396                 BMIter iter;
397                 BMEdge *ele;
398                 int i = 0;
399                 
400                 tm->edge_index = MEM_mallocN(sizeof(void **) * tm->bm->totedge, "tm->edge_index");
401
402                 ele = BM_iter_new(&iter, tm->bm, BM_EDGES_OF_MESH, NULL);
403                 for ( ; ele; ele = BM_iter_step(&iter)) {
404                         tm->edge_index[i++] = ele;
405                 }
406         }
407
408         if (forface) {
409                 BMIter iter;
410                 BMFace *ele;
411                 int i = 0;
412                 
413                 tm->face_index = MEM_mallocN(sizeof(void **) * tm->bm->totface, "tm->face_index");
414
415                 ele = BM_iter_new(&iter, tm->bm, BM_FACES_OF_MESH, NULL);
416                 for ( ; ele; ele = BM_iter_step(&iter)) {
417                         tm->face_index[i++] = ele;
418                 }
419         }
420 }
421
422 void EDBM_index_arrays_free(BMEditMesh *tm)
423 {
424         if (tm->vert_index) {
425                 MEM_freeN(tm->vert_index);
426                 tm->vert_index = NULL;
427         }
428
429         if (tm->edge_index) {
430                 MEM_freeN(tm->edge_index);
431                 tm->edge_index = NULL;
432         }
433
434         if (tm->face_index) {
435                 MEM_freeN(tm->face_index);
436                 tm->face_index = NULL;
437         }
438 }
439
440 BMVert *EDBM_vert_at_index(BMEditMesh *tm, int index)
441 {
442         return tm->vert_index && index < tm->bm->totvert ? tm->vert_index[index] : NULL;
443 }
444
445 BMEdge *EDBM_edge_at_index(BMEditMesh *tm, int index)
446 {
447         return tm->edge_index && index < tm->bm->totedge ? tm->edge_index[index] : NULL;
448 }
449
450 BMFace *EDBM_face_at_index(BMEditMesh *tm, int index)
451 {
452         return (tm->face_index && index < tm->bm->totface && index >= 0) ? tm->face_index[index] : NULL;
453 }
454
455 void EDBM_selectmode_flush_ex(BMEditMesh *em, const short selectmode)
456 {
457         BM_mesh_select_mode_flush_ex(em->bm, selectmode);
458 }
459
460 void EDBM_selectmode_flush(BMEditMesh *em)
461 {
462         EDBM_selectmode_flush_ex(em, em->selectmode);
463 }
464
465 void EDBM_deselect_flush(BMEditMesh *em)
466 {
467         /* function below doesnt use. just do this to keep the values in sync */
468         em->bm->selectmode = em->selectmode;
469         BM_mesh_deselect_flush(em->bm);
470 }
471
472
473 void EDBM_select_flush(BMEditMesh *em)
474 {
475         /* function below doesnt use. just do this to keep the values in sync */
476         em->bm->selectmode = em->selectmode;
477         BM_mesh_select_flush(em->bm);
478 }
479
480 void EDBM_select_more(BMEditMesh *em)
481 {
482         BMOperator bmop;
483         int use_faces = em->selectmode == SCE_SELECT_FACE;
484
485         BMO_op_initf(em->bm, &bmop, BMO_FLAG_DEFAULTS,
486                      "region_extend geom=%hvef constrict=%b use_faces=%b",
487                      BM_ELEM_SELECT, FALSE, use_faces);
488         BMO_op_exec(em->bm, &bmop);
489         /* don't flush selection in edge/vertex mode  */
490         BMO_slot_buffer_hflag_enable(em->bm, &bmop, "geomout", BM_ALL, BM_ELEM_SELECT, use_faces ? TRUE : FALSE);
491         BMO_op_finish(em->bm, &bmop);
492
493         EDBM_select_flush(em);
494 }
495
496 void EDBM_select_less(BMEditMesh *em)
497 {
498         BMOperator bmop;
499         int use_faces = em->selectmode == SCE_SELECT_FACE;
500
501         BMO_op_initf(em->bm, &bmop, BMO_FLAG_DEFAULTS,
502                      "region_extend geom=%hvef constrict=%b use_faces=%b",
503                      BM_ELEM_SELECT, TRUE, use_faces);
504         BMO_op_exec(em->bm, &bmop);
505         /* don't flush selection in edge/vertex mode  */
506         BMO_slot_buffer_hflag_disable(em->bm, &bmop, "geomout", BM_ALL, BM_ELEM_SELECT, use_faces ? TRUE : FALSE);
507         BMO_op_finish(em->bm, &bmop);
508
509         EDBM_selectmode_flush(em);
510 }
511
512 void EDBM_flag_disable_all(BMEditMesh *em, const char hflag)
513 {
514         BM_mesh_elem_hflag_disable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, hflag, FALSE);
515 }
516
517 void EDBM_flag_enable_all(BMEditMesh *em, const char hflag)
518 {
519         BM_mesh_elem_hflag_enable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, hflag, TRUE);
520 }
521
522 /**************-------------- Undo ------------*****************/
523
524 /* for callbacks */
525
526 static void *getEditMesh(bContext *C)
527 {
528         Object *obedit = CTX_data_edit_object(C);
529         if (obedit && obedit->type == OB_MESH) {
530                 Mesh *me = obedit->data;
531                 return me->edit_btmesh;
532         }
533         return NULL;
534 }
535
536 typedef struct UndoMesh {
537         Mesh me;
538         int selectmode;
539 } UndoMesh;
540
541 /* undo simply makes copies of a bmesh */
542 static void *editbtMesh_to_undoMesh(void *emv, void *obdata)
543 {
544         BMEditMesh *em = emv;
545         Mesh *obme = obdata;
546         
547         UndoMesh *um = MEM_callocN(sizeof(UndoMesh), "undo Mesh");
548         
549         /* make sure shape keys work */
550         um->me.key = obme->key ? copy_key_nolib(obme->key) : NULL;
551
552         /* BM_mesh_validate(em->bm); */ /* for troubleshooting */
553
554         BM_mesh_bm_to_me(em->bm, &um->me, FALSE);
555
556         um->selectmode = em->selectmode;
557
558         return um;
559 }
560
561 static void undoMesh_to_editbtMesh(void *umv, void *em_v, void *UNUSED(obdata))
562 {
563         BMEditMesh *em = em_v, *em_tmp;
564         Object *ob = em->ob;
565         UndoMesh *um = umv;
566         BMesh *bm;
567
568         ob->shapenr = em->bm->shapenr;
569
570         EDBM_mesh_free(em);
571
572         bm = BM_mesh_create(&bm_mesh_allocsize_default);
573
574         BM_mesh_bm_from_me(bm, &um->me, FALSE, ob->shapenr);
575
576         /* face normals need recalculation since we are not calling through an operator */
577         BM_mesh_normals_update(bm, TRUE);
578
579         em_tmp = BMEdit_Create(bm, TRUE);
580         *em = *em_tmp;
581         
582         em->selectmode = um->selectmode;
583         em->ob = ob;
584
585         MEM_freeN(em_tmp);
586 }
587
588 static void free_undo(void *me_v)
589 {
590         Mesh *me = me_v;
591         if (me->key) {
592                 BKE_key_free(me->key);
593                 MEM_freeN(me->key);
594         }
595
596         BKE_mesh_free(me, FALSE);
597         MEM_freeN(me);
598 }
599
600 /* and this is all the undo system needs to know */
601 void undo_push_mesh(bContext *C, const char *name)
602 {
603         /* em->ob gets out of date and crashes on mesh undo,
604          * this is an easy way to ensure its OK
605          * though we could investigate the matter further. */
606         Object *obedit = CTX_data_edit_object(C);
607         BMEditMesh *em = BMEdit_FromObject(obedit);
608         em->ob = obedit;
609
610         undo_editmode_push(C, name, getEditMesh, free_undo, undoMesh_to_editbtMesh, editbtMesh_to_undoMesh, NULL);
611 }
612
613 /* write comment here */
614 UvVertMap *EDBM_uv_vert_map_create(BMEditMesh *em, int selected, int do_face_idx_array, const float limit[2])
615 {
616         BMVert *ev;
617         BMFace *efa;
618         BMLoop *l;
619         BMIter iter, liter;
620         /* vars from original func */
621         UvVertMap *vmap;
622         UvMapVert *buf;
623         /* MTexPoly *tf; */ /* UNUSED */
624         MLoopUV *luv;
625         unsigned int a;
626         int totverts, i, totuv;
627         
628         if (do_face_idx_array)
629                 EDBM_index_arrays_init(em, 0, 0, 1);
630
631         BM_mesh_elem_index_ensure(em->bm, BM_VERT);
632         
633         totverts = em->bm->totvert;
634         totuv = 0;
635
636         /* generate UvMapVert array */
637         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
638                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT)))
639                         totuv += efa->len;
640         }
641
642         if (totuv == 0) {
643                 if (do_face_idx_array)
644                         EDBM_index_arrays_free(em);
645                 return NULL;
646         }
647         vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
648         if (!vmap) {
649                 if (do_face_idx_array)
650                         EDBM_index_arrays_free(em);
651                 return NULL;
652         }
653
654         vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totverts, "UvMapVert_pt");
655         buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert");
656
657         if (!vmap->vert || !vmap->buf) {
658                 BKE_mesh_uv_vert_map_free(vmap);
659                 if (do_face_idx_array)
660                         EDBM_index_arrays_free(em);
661                 return NULL;
662         }
663         
664         a = 0;
665         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
666                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT))) {
667                         i = 0;
668                         BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
669                                 buf->tfindex = i;
670                                 buf->f = a;
671                                 buf->separate = 0;
672                                 
673                                 buf->next = vmap->vert[BM_elem_index_get(l->v)];
674                                 vmap->vert[BM_elem_index_get(l->v)] = buf;
675                                 
676                                 buf++;
677                                 i++;
678                         }
679                 }
680
681                 a++;
682         }
683         
684         /* sort individual uvs for each vert */
685         a = 0;
686         BM_ITER_MESH (ev, &iter, em->bm, BM_VERTS_OF_MESH) {
687                 UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
688                 UvMapVert *iterv, *v, *lastv, *next;
689                 float *uv, *uv2, uvdiff[2];
690
691                 while (vlist) {
692                         v = vlist;
693                         vlist = vlist->next;
694                         v->next = newvlist;
695                         newvlist = v;
696
697                         efa = EDBM_face_at_index(em, v->f);
698                         /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
699                         
700                         l = BM_iter_at_index(em->bm, BM_LOOPS_OF_FACE, efa, v->tfindex);
701                         luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
702                         uv = luv->uv;
703                         
704                         lastv = NULL;
705                         iterv = vlist;
706
707                         while (iterv) {
708                                 next = iterv->next;
709                                 efa = EDBM_face_at_index(em, iterv->f);
710                                 /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
711                                 
712                                 l = BM_iter_at_index(em->bm, BM_LOOPS_OF_FACE, efa, iterv->tfindex);
713                                 luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
714                                 uv2 = luv->uv;
715                                 
716                                 sub_v2_v2v2(uvdiff, uv2, uv);
717
718                                 if (fabsf(uvdiff[0]) < limit[0] && fabsf(uvdiff[1]) < limit[1]) {
719                                         if (lastv) lastv->next = next;
720                                         else vlist = next;
721                                         iterv->next = newvlist;
722                                         newvlist = iterv;
723                                 }
724                                 else {
725                                         lastv = iterv;
726                                 }
727
728                                 iterv = next;
729                         }
730
731                         newvlist->separate = 1;
732                 }
733
734                 vmap->vert[a] = newvlist;
735                 a++;
736         }
737         
738         if (do_face_idx_array)
739                 EDBM_index_arrays_free(em);
740         
741         return vmap;
742 }
743
744
745 UvMapVert *EDBM_uv_vert_map_at_index(UvVertMap *vmap, unsigned int v)
746 {
747         return vmap->vert[v];
748 }
749
750 /* from editmesh_lib.c in trunk */
751
752
753 /* A specialized vert map used by stitch operator */
754 UvElementMap *EDBM_uv_element_map_create(BMEditMesh *em, int selected, int do_islands)
755 {
756         BMVert *ev;
757         BMFace *efa;
758         BMLoop *l;
759         BMIter iter, liter;
760         /* vars from original func */
761         UvElementMap *element_map;
762         UvElement *buf;
763         UvElement *islandbuf;
764         /* island number for faces */
765         int *island_number;
766
767         MLoopUV *luv;
768         int totverts, i, totuv, j, nislands = 0, islandbufsize = 0;
769
770         unsigned int *map;
771         BMFace **stack;
772         int stacksize = 0;
773
774         BM_mesh_elem_index_ensure(em->bm, BM_VERT | BM_FACE);
775
776         totverts = em->bm->totvert;
777         totuv = 0;
778
779         island_number = MEM_mallocN(sizeof(*stack) * em->bm->totface, "uv_island_number_face");
780         if (!island_number) {
781                 return NULL;
782         }
783
784         /* generate UvElement array */
785         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
786                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT)))
787                         totuv += efa->len;
788         }
789
790         if (totuv == 0) {
791                 MEM_freeN(island_number);
792                 return NULL;
793         }
794         element_map = (UvElementMap *)MEM_callocN(sizeof(*element_map), "UvElementMap");
795         if (!element_map) {
796                 MEM_freeN(island_number);
797                 return NULL;
798         }
799         element_map->totalUVs = totuv;
800         element_map->vert = (UvElement **)MEM_callocN(sizeof(*element_map->vert) * totverts, "UvElementVerts");
801         buf = element_map->buf = (UvElement *)MEM_callocN(sizeof(*element_map->buf) * totuv, "UvElement");
802
803         if (!element_map->vert || !element_map->buf) {
804                 EDBM_uv_element_map_free(element_map);
805                 MEM_freeN(island_number);
806                 return NULL;
807         }
808
809         j = 0;
810         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
811                 island_number[j++] = INVALID_ISLAND;
812                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT))) {
813                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, i) {
814                                 buf->l = l;
815                                 buf->face = efa;
816                                 buf->separate = 0;
817                                 buf->island = INVALID_ISLAND;
818                                 buf->tfindex = i;
819
820                                 buf->next = element_map->vert[BM_elem_index_get(l->v)];
821                                 element_map->vert[BM_elem_index_get(l->v)] = buf;
822
823                                 buf++;
824                         }
825                 }
826         }
827
828         /* sort individual uvs for each vert */
829         i = 0;
830         BM_ITER_MESH (ev, &iter, em->bm, BM_VERTS_OF_MESH) {
831                 UvElement *newvlist = NULL, *vlist = element_map->vert[i];
832                 UvElement *iterv, *v, *lastv, *next;
833                 float *uv, *uv2, uvdiff[2];
834
835                 while (vlist) {
836                         v = vlist;
837                         vlist = vlist->next;
838                         v->next = newvlist;
839                         newvlist = v;
840
841                         l = v->l;
842                         luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
843                         uv = luv->uv;
844
845                         lastv = NULL;
846                         iterv = vlist;
847
848                         while (iterv) {
849                                 next = iterv->next;
850
851                                 l = iterv->l;
852                                 luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
853                                 uv2 = luv->uv;
854
855                                 sub_v2_v2v2(uvdiff, uv2, uv);
856
857                                 if (fabsf(uvdiff[0]) < STD_UV_CONNECT_LIMIT && fabsf(uvdiff[1]) < STD_UV_CONNECT_LIMIT) {
858                                         if (lastv) lastv->next = next;
859                                         else vlist = next;
860                                         iterv->next = newvlist;
861                                         newvlist = iterv;
862                                 }
863                                 else {
864                                         lastv = iterv;
865                                 }
866
867                                 iterv = next;
868                         }
869
870                         newvlist->separate = 1;
871                 }
872
873                 element_map->vert[i] = newvlist;
874                 i++;
875         }
876
877         if (do_islands) {
878                 /* map holds the map from current vmap->buf to the new, sorted map */
879                 map = MEM_mallocN(sizeof(*map) * totuv, "uvelement_remap");
880                 stack = MEM_mallocN(sizeof(*stack) * em->bm->totface, "uv_island_face_stack");
881                 islandbuf = MEM_callocN(sizeof(*islandbuf) * totuv, "uvelement_island_buffer");
882
883                 /* at this point, every UvElement in vert points to a UvElement sharing the same vertex. Now we should sort uv's in islands. */
884                 for (i = 0; i < totuv; i++) {
885                         if (element_map->buf[i].island == INVALID_ISLAND) {
886                                 element_map->buf[i].island = nislands;
887                                 stack[0] = element_map->buf[i].face;
888                                 island_number[BM_elem_index_get(stack[0])] = nislands;
889                                 stacksize = 1;
890
891                                 while (stacksize > 0) {
892                                         efa = stack[--stacksize];
893
894                                         BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
895                                                 UvElement *element, *initelement = element_map->vert[BM_elem_index_get(l->v)];
896
897                                                 for (element = initelement; element; element = element->next) {
898                                                         if (element->separate)
899                                                                 initelement = element;
900
901                                                         if (element->face == efa) {
902                                                                 /* found the uv corresponding to our face and vertex. Now fill it to the buffer */
903                                                                 element->island = nislands;
904                                                                 map[element - element_map->buf] = islandbufsize;
905                                                                 islandbuf[islandbufsize].l = element->l;
906                                                                 islandbuf[islandbufsize].face = element->face;
907                                                                 islandbuf[islandbufsize].separate = element->separate;
908                                                                 islandbuf[islandbufsize].tfindex = element->tfindex;
909                                                                 islandbuf[islandbufsize].island =  nislands;
910                                                                 islandbufsize++;
911
912                                                                 for (element = initelement; element; element = element->next) {
913                                                                         if (element->separate && element != initelement)
914                                                                                 break;
915
916                                                                         if (island_number[BM_elem_index_get(element->face)] == INVALID_ISLAND) {
917                                                                                 stack[stacksize++] = element->face;
918                                                                                 island_number[BM_elem_index_get(element->face)] = nislands;
919                                                                         }
920                                                                 }
921                                                                 break;
922                                                         }
923                                                 }
924                                         }
925                                 }
926
927                                 nislands++;
928                         }
929                 }
930
931                 /* remap */
932                 for (i = 0; i < em->bm->totvert; i++) {
933                         /* important since we may do selection only. Some of these may be NULL */
934                         if (element_map->vert[i])
935                                 element_map->vert[i] = &islandbuf[map[element_map->vert[i] - element_map->buf]];
936                 }
937
938                 element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices) * nislands, "UvElementMap_island_indices");
939                 if (!element_map->islandIndices) {
940                         MEM_freeN(islandbuf);
941                         MEM_freeN(stack);
942                         MEM_freeN(map);
943                         EDBM_uv_element_map_free(element_map);
944                         MEM_freeN(island_number);
945                 }
946
947                 j = 0;
948                 for (i = 0; i < totuv; i++) {
949                         UvElement *element = element_map->buf[i].next;
950                         if (element == NULL)
951                                 islandbuf[map[i]].next = NULL;
952                         else
953                                 islandbuf[map[i]].next = &islandbuf[map[element - element_map->buf]];
954
955                         if (islandbuf[i].island != j) {
956                                 j++;
957                                 element_map->islandIndices[j] = i;
958                         }
959                 }
960
961                 MEM_freeN(element_map->buf);
962
963                 element_map->buf = islandbuf;
964                 element_map->totalIslands = nislands;
965                 MEM_freeN(stack);
966                 MEM_freeN(map);
967         }
968         MEM_freeN(island_number);
969
970         return element_map;
971 }
972
973 void EDBM_uv_vert_map_free(UvVertMap *vmap)
974 {
975         if (vmap) {
976                 if (vmap->vert) MEM_freeN(vmap->vert);
977                 if (vmap->buf) MEM_freeN(vmap->buf);
978                 MEM_freeN(vmap);
979         }
980 }
981
982 void EDBM_uv_element_map_free(UvElementMap *element_map)
983 {
984         if (element_map) {
985                 if (element_map->vert) MEM_freeN(element_map->vert);
986                 if (element_map->buf) MEM_freeN(element_map->buf);
987                 if (element_map->islandIndices) MEM_freeN(element_map->islandIndices);
988                 MEM_freeN(element_map);
989         }
990 }
991
992 /* last_sel, use em->act_face otherwise get the last selected face in the editselections
993  * at the moment, last_sel is mainly useful for making sure the space image dosnt flicker */
994 MTexPoly *EDBM_mtexpoly_active_get(BMEditMesh *em, BMFace **r_act_efa, int sloppy)
995 {
996         BMFace *efa = NULL;
997         
998         if (!EDBM_mtexpoly_check(em))
999                 return NULL;
1000         
1001         efa = BM_active_face_get(em->bm, sloppy);
1002         
1003         if (efa) {
1004                 if (r_act_efa) *r_act_efa = efa;
1005                 return CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY);
1006         }
1007
1008         if (r_act_efa) *r_act_efa = NULL;
1009         return NULL;
1010 }
1011
1012 /* can we edit UV's for this mesh?*/
1013 int EDBM_mtexpoly_check(BMEditMesh *em)
1014 {
1015         /* some of these checks could be a touch overkill */
1016         return em && em->bm->totface && CustomData_has_layer(&em->bm->pdata, CD_MTEXPOLY) &&
1017                CustomData_has_layer(&em->bm->ldata, CD_MLOOPUV);
1018 }
1019
1020 int EDBM_vert_color_check(BMEditMesh *em)
1021 {
1022         /* some of these checks could be a touch overkill */
1023         return em && em->bm->totface && CustomData_has_layer(&em->bm->ldata, CD_MLOOPCOL);
1024 }
1025
1026 static BMVert *cache_mirr_intptr_as_bmvert(intptr_t *index_lookup, int index)
1027 {
1028         intptr_t eve_i = index_lookup[index];
1029         return (eve_i == -1) ? NULL : (BMVert *)eve_i;
1030 }
1031
1032 /**
1033  * [note: I've decided to use ideasman's code for non-editmode stuff, but since
1034  *  it has a big "not for editmode!" disclaimer, I'm going to keep what I have here
1035  *  - joeedh]
1036  *
1037  * x-mirror editing api.  usage:
1038  *
1039  *  EDBM_verts_mirror_cache_begin(em);
1040  *  ...
1041  *  ...
1042  *  BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
1043  *     mirrorv = EDBM_verts_mirror_get(em, v);
1044  *  }
1045  *  ...
1046  *  ...
1047  *  EDBM_verts_mirror_cache_end(em);
1048  *
1049  * \note why do we only allow x axis mirror editing?
1050  */
1051
1052 /* BM_SEARCH_MAXDIST is too big, copied from 2.6x MOC_THRESH, should become a
1053  * preference */
1054 #define BM_SEARCH_MAXDIST_MIRR 0.00002f
1055 #define BM_CD_LAYER_ID "__mirror_index"
1056 void EDBM_verts_mirror_cache_begin(BMEditMesh *em, const short use_select)
1057 {
1058         Mesh *me = em->me;
1059         BMesh *bm = em->bm;
1060         BMIter iter;
1061         BMVert *v;
1062         int li, topo = 0;
1063
1064         /* one or the other is used depending if topo is enabled */
1065         BMBVHTree *tree = NULL;
1066         MirrTopoStore_t mesh_topo_store = {NULL, -1, -1, -1};
1067
1068         if (me && (me->editflag & ME_EDIT_MIRROR_TOPO)) {
1069                 topo = 1;
1070         }
1071
1072         if (!em->vert_index) {
1073                 EDBM_index_arrays_init(em, 1, 0, 0);
1074                 em->mirr_free_arrays = 1;
1075         }
1076
1077         if (!CustomData_get_layer_named(&bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID)) {
1078                 BM_data_layer_add_named(bm, &bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID);
1079         }
1080
1081         li = CustomData_get_named_layer_index(&bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID);
1082
1083         bm->vdata.layers[li].flag |= CD_FLAG_TEMPORARY;
1084
1085         BM_mesh_elem_index_ensure(bm, BM_VERT);
1086
1087         if (topo) {
1088                 ED_mesh_mirrtopo_init(me, -1, &mesh_topo_store, TRUE);
1089         }
1090         else {
1091                 tree = BMBVH_NewBVH(em, 0, NULL, NULL);
1092         }
1093
1094         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1095
1096                 /* temporary for testing, check for selection */
1097                 if (use_select && !BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1098                         /* do nothing */
1099                 }
1100                 else {
1101                         BMVert *mirr;
1102                         int *idx = CustomData_bmesh_get_layer_n(&bm->vdata, v->head.data, li);
1103
1104                         if (topo) {
1105                                 mirr = cache_mirr_intptr_as_bmvert(mesh_topo_store.index_lookup, BM_elem_index_get(v));
1106                         }
1107                         else {
1108                                 float co[3] = {-v->co[0], v->co[1], v->co[2]};
1109                                 mirr = BMBVH_FindClosestVert(tree, co, BM_SEARCH_MAXDIST_MIRR);
1110                         }
1111
1112                         if (mirr && mirr != v) {
1113                                 *idx = BM_elem_index_get(mirr);
1114                                 idx = CustomData_bmesh_get_layer_n(&bm->vdata, mirr->head.data, li);
1115                                 *idx = BM_elem_index_get(v);
1116                         }
1117                         else {
1118                                 *idx = -1;
1119                         }
1120                 }
1121
1122         }
1123
1124
1125         if (topo) {
1126                 ED_mesh_mirrtopo_free(&mesh_topo_store);
1127         }
1128         else {
1129                 BMBVH_FreeBVH(tree);
1130         }
1131
1132         em->mirror_cdlayer = li;
1133 }
1134
1135 BMVert *EDBM_verts_mirror_get(BMEditMesh *em, BMVert *v)
1136 {
1137         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
1138
1139         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
1140
1141         if (mirr && *mirr >= 0 && *mirr < em->bm->totvert) {
1142                 if (!em->vert_index) {
1143                         printf("err: should only be called between "
1144                                "EDBM_verts_mirror_cache_begin and EDBM_verts_mirror_cache_end");
1145                         return NULL;
1146                 }
1147
1148                 return em->vert_index[*mirr];
1149         }
1150
1151         return NULL;
1152 }
1153
1154 void EDBM_verts_mirror_cache_clear(BMEditMesh *em, BMVert *v)
1155 {
1156         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
1157
1158         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
1159
1160         if (mirr) {
1161                 *mirr = -1;
1162         }
1163 }
1164
1165 void EDBM_verts_mirror_cache_end(BMEditMesh *em)
1166 {
1167         if (em->mirr_free_arrays) {
1168                 MEM_freeN(em->vert_index);
1169                 em->vert_index = NULL;
1170         }
1171
1172         em->mirror_cdlayer = -1;
1173 }
1174
1175 void EDBM_verts_mirror_apply(BMEditMesh *em, const int sel_from, const int sel_to)
1176 {
1177         BMIter iter;
1178         BMVert *v;
1179
1180         BLI_assert(em->vert_index != NULL);
1181
1182         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
1183                 if (BM_elem_flag_test(v, BM_ELEM_SELECT) == sel_from) {
1184                         BMVert *mirr = EDBM_verts_mirror_get(em, v);
1185                         if (mirr) {
1186                                 if (BM_elem_flag_test(mirr, BM_ELEM_SELECT) == sel_to) {
1187                                         copy_v3_v3(mirr->co, v->co);
1188                                         mirr->co[0] *= -1.0f;
1189                                 }
1190                         }
1191                 }
1192         }
1193 }
1194
1195
1196 /* swap is 0 or 1, if 1 it hides not selected */
1197 void EDBM_mesh_hide(BMEditMesh *em, int swap)
1198 {
1199         BMIter iter;
1200         BMElem *ele;
1201         int itermode;
1202
1203         if (em == NULL) return;
1204
1205         if (em->selectmode & SCE_SELECT_VERTEX)
1206                 itermode = BM_VERTS_OF_MESH;
1207         else if (em->selectmode & SCE_SELECT_EDGE)
1208                 itermode = BM_EDGES_OF_MESH;
1209         else
1210                 itermode = BM_FACES_OF_MESH;
1211
1212         BM_ITER_MESH (ele, &iter, em->bm, itermode) {
1213                 if (BM_elem_flag_test(ele, BM_ELEM_SELECT) ^ swap)
1214                         BM_elem_hide_set(em->bm, ele, TRUE);
1215         }
1216
1217         EDBM_selectmode_flush(em);
1218
1219         /* original hide flushing comment (OUTDATED):
1220          * hide happens on least dominant select mode, and flushes up, not down! (helps preventing errors in subsurf) */
1221         /* - vertex hidden, always means edge is hidden too
1222          * - edge hidden, always means face is hidden too
1223          * - face hidden, only set face hide
1224          * - then only flush back down what's absolute hidden
1225          */
1226 }
1227
1228
1229 void EDBM_mesh_reveal(BMEditMesh *em)
1230 {
1231         const char iter_types[3] = {BM_VERTS_OF_MESH,
1232                                     BM_EDGES_OF_MESH,
1233                                     BM_FACES_OF_MESH};
1234
1235         int sels[3] = {(em->selectmode & SCE_SELECT_VERTEX),
1236                        (em->selectmode & SCE_SELECT_EDGE),
1237                        (em->selectmode & SCE_SELECT_FACE), };
1238
1239         BMIter iter;
1240         BMElem *ele;
1241         int i;
1242
1243         /* Use tag flag to remember what was hidden before all is revealed.
1244          * BM_ELEM_HIDDEN --> BM_ELEM_TAG */
1245         for (i = 0; i < 3; i++) {
1246                 BM_ITER_MESH (ele, &iter, em->bm, iter_types[i]) {
1247                         BM_elem_flag_set(ele, BM_ELEM_TAG, BM_elem_flag_test(ele, BM_ELEM_HIDDEN));
1248                 }
1249         }
1250
1251         /* Reveal everything */
1252         EDBM_flag_disable_all(em, BM_ELEM_HIDDEN);
1253
1254         /* Select relevant just-revealed elements */
1255         for (i = 0; i < 3; i++) {
1256                 if (!sels[i]) {
1257                         continue;
1258                 }
1259
1260                 BM_ITER_MESH (ele, &iter, em->bm, iter_types[i]) {
1261                         if (BM_elem_flag_test(ele, BM_ELEM_TAG)) {
1262                                 BM_elem_select_set(em->bm, ele, TRUE);
1263                         }
1264                 }
1265         }
1266
1267         EDBM_selectmode_flush(em);
1268
1269         /* hidden faces can have invalid normals */
1270         EDBM_mesh_normals_update(em);
1271 }
1272
1273 /* so many tools call these that we better make it a generic function.
1274  */
1275 void EDBM_update_generic(bContext *C, BMEditMesh *em, const short do_tessface)
1276 {
1277         Object *ob = em->ob;
1278         /* order of calling isn't important */
1279         DAG_id_tag_update(ob->data, OB_RECALC_DATA);
1280         WM_event_add_notifier(C, NC_GEOM | ND_DATA, ob->data);
1281
1282         if (do_tessface) {
1283                 BMEdit_RecalcTessellation(em);
1284         }
1285 }