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