bmesh minor refactor
[blender.git] / source / blender / editors / mesh / bmeshutils.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 #include "MEM_guardedalloc.h"
29
30 #include "DNA_object_types.h"
31 #include "DNA_scene_types.h"
32
33 #include "BLI_blenlib.h"
34 #include "BLI_math.h"
35
36 #include "BKE_context.h"
37 #include "BKE_library.h"
38 #include "BKE_key.h"
39 #include "BKE_mesh.h"
40 #include "BKE_bmesh.h"
41 #include "BKE_report.h"
42 #include "BKE_tessmesh.h"
43
44 #include "WM_api.h"
45 #include "WM_types.h"
46
47 #include "ED_mesh.h"
48 #include "ED_util.h"
49
50 void EDBM_RecalcNormals(BMEditMesh *em)
51 {
52         BM_mesh_normals_update(em->bm);
53 }
54
55 void EDBM_ClearMesh(BMEditMesh *em)
56 {
57         /* clear bmesh */
58         BM_mesh_clear(em->bm);
59         
60         /* free derived meshes */
61         if (em->derivedCage) {
62                 em->derivedCage->needsFree = 1;
63                 em->derivedCage->release(em->derivedCage);
64         }
65         if (em->derivedFinal && em->derivedFinal != em->derivedCage) {
66                 em->derivedFinal->needsFree = 1;
67                 em->derivedFinal->release(em->derivedFinal);
68         }
69         
70         em->derivedCage = em->derivedFinal = NULL;
71         
72         /* free tesselation data */
73         em->tottri = 0;
74         if (em->looptris) 
75                 MEM_freeN(em->looptris);
76 }
77
78 void EDBM_stats_update(BMEditMesh *em)
79 {
80         const char iter_types[3] = {BM_VERTS_OF_MESH,
81                                     BM_EDGES_OF_MESH,
82                                     BM_FACES_OF_MESH};
83
84         BMIter iter;
85         BMHeader *ele;
86         int *tots[3];
87         int i;
88
89         tots[0] = &em->bm->totvertsel;
90         tots[1] = &em->bm->totedgesel;
91         tots[2] = &em->bm->totfacesel;
92         
93         em->bm->totvertsel = em->bm->totedgesel = em->bm->totfacesel = 0;
94
95         for (i = 0; i < 3; i++) {
96                 ele = BM_iter_new(&iter, em->bm, iter_types[i], NULL);
97                 for ( ; ele; ele = BM_iter_step(&iter)) {
98                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
99                                 (*tots[i])++;
100                         }
101                 }
102         }
103 }
104
105 int EDBM_InitOpf(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const char *fmt, ...)
106 {
107         BMesh *bm = em->bm;
108         va_list list;
109
110         va_start(list, fmt);
111
112         if (!BMO_op_vinitf(bm, bmop, fmt, list)) {
113                 BKE_report(op->reports, RPT_ERROR,
114                            "Parse error in EDBM_CallOpf");
115                 va_end(list);
116                 return 0;
117         }
118         
119         if (!em->emcopy)
120                 em->emcopy = BMEdit_Copy(em);
121         em->emcopyusers++;
122
123         va_end(list);
124
125         return 1;
126 }
127
128
129 /* returns 0 on error, 1 on success.  executes and finishes a bmesh operator */
130 int EDBM_FinishOp(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const int report)
131 {
132         const char *errmsg;
133         
134         BMO_op_finish(em->bm, bmop);
135
136         if (BMO_error_get(em->bm, &errmsg, NULL)) {
137                 BMEditMesh *emcopy = em->emcopy;
138
139                 if (report) BKE_report(op->reports, RPT_ERROR, errmsg);
140
141                 BMEdit_Free(em);
142                 *em = *emcopy;
143                 BMEdit_RecalcTesselation(em);
144
145                 MEM_freeN(emcopy);
146                 em->emcopyusers = 0;
147                 em->emcopy = NULL;
148                 return 0;
149         }
150         else {
151                 em->emcopyusers--;
152                 if (em->emcopyusers < 0) {
153                         printf("warning: em->emcopyusers was less then zero.\n");
154                 }
155
156                 if (em->emcopyusers <= 0) {
157                         BMEdit_Free(em->emcopy);
158                         MEM_freeN(em->emcopy);
159                         em->emcopy = NULL;
160                 }
161         }
162
163         return 1;
164 }
165
166 int EDBM_CallOpf(BMEditMesh *em, wmOperator *op, const char *fmt, ...)
167 {
168         BMesh *bm = em->bm;
169         BMOperator bmop;
170         va_list list;
171
172         va_start(list, fmt);
173
174         if (!BMO_op_vinitf(bm, &bmop, fmt, list)) {
175                 BKE_report(op->reports, RPT_ERROR,
176                            "Parse error in EDBM_CallOpf");
177                 va_end(list);
178                 return 0;
179         }
180
181         if (!em->emcopy)
182                 em->emcopy = BMEdit_Copy(em);
183         em->emcopyusers++;
184
185         BMO_op_exec(bm, &bmop);
186
187         va_end(list);
188         return EDBM_FinishOp(em, &bmop, op, TRUE);
189 }
190
191 int EDBM_CallAndSelectOpf(BMEditMesh *em, wmOperator *op, const char *selectslot, const char *fmt, ...)
192 {
193         BMesh *bm = em->bm;
194         BMOperator bmop;
195         va_list list;
196
197         va_start(list, fmt);
198
199         if (!BMO_op_vinitf(bm, &bmop, fmt, list)) {
200                 BKE_report(op->reports, RPT_ERROR,
201                            "Parse error in EDBM_CallOpf");
202                 va_end(list);
203                 return 0;
204         }
205
206         if (!em->emcopy)
207                 em->emcopy = BMEdit_Copy(em);
208         em->emcopyusers++;
209
210         BMO_op_exec(bm, &bmop);
211         BMO_slot_buffer_hflag(em->bm, &bmop, selectslot, BM_ELEM_SELECT, BM_ALL);
212
213         va_end(list);
214         return EDBM_FinishOp(em, &bmop, op, TRUE);
215 }
216
217 int EDBM_CallOpfSilent(BMEditMesh *em, const char *fmt, ...)
218 {
219         BMesh *bm = em->bm;
220         BMOperator bmop;
221         va_list list;
222
223         va_start(list, fmt);
224
225         if (!BMO_op_vinitf(bm, &bmop, fmt, list)) {
226                 va_end(list);
227                 return 0;
228         }
229
230         if (!em->emcopy)
231                 em->emcopy = BMEdit_Copy(em);
232         em->emcopyusers++;
233
234         BMO_op_exec(bm, &bmop);
235
236         va_end(list);
237         return EDBM_FinishOp(em, &bmop, NULL, FALSE);
238 }
239
240 void EDBM_selectmode_to_scene(bContext *C)
241 {
242         Scene *scene = CTX_data_scene(C);
243         Object *obedit = CTX_data_edit_object(C);
244         BMEditMesh *em = ((Mesh *)obedit->data)->edit_btmesh;
245
246         if (!em)
247                 return;
248
249         scene->toolsettings->selectmode = em->selectmode;
250
251         /* Request redraw of header buttons (to show new select mode) */
252         WM_event_add_notifier(C, NC_SCENE|ND_TOOLSETTINGS, scene);
253 }
254
255 void EDBM_MakeEditBMesh(ToolSettings *ts, Scene *UNUSED(scene), Object *ob)
256 {
257         Mesh *me = ob->data;
258         BMesh *bm;
259
260         if (!me->mpoly && me->totface) {
261                 fprintf(stderr, "%s: bmesh conversion issue! may lose lots of geometry! (bmesh internal error)\n", __func__);
262                 
263                 /* BMESH_TODO need to write smarter code here */
264                 bm = BKE_mesh_to_bmesh(me, ob);
265         }
266         else {
267                 bm = BKE_mesh_to_bmesh(me, ob);
268         }
269
270         if (me->edit_btmesh) {
271                 /* this happens when switching shape keys */
272                 BMEdit_Free(me->edit_btmesh);
273                 MEM_freeN(me->edit_btmesh);
274         }
275
276         /* currently executing operators re-tesselates, so we can avoid doing here
277          * but at some point it may need to be added back. */
278 #if 0
279         me->edit_btmesh = BMEdit_Create(bm, TRUE);
280 #else
281         me->edit_btmesh = BMEdit_Create(bm, FALSE);
282 #endif
283
284         me->edit_btmesh->selectmode = me->edit_btmesh->bm->selectmode = ts->selectmode;
285         me->edit_btmesh->me = me;
286         me->edit_btmesh->ob = ob;
287 }
288
289 void EDBM_LoadEditBMesh(Scene *scene, Object *ob)
290 {
291         Mesh *me = ob->data;
292         BMesh *bm = me->edit_btmesh->bm;
293
294         BMO_op_callf(bm, "object_load_bmesh scene=%p object=%p", scene, ob);
295 }
296
297 void EDBM_FreeEditBMesh(BMEditMesh *tm)
298 {
299         BMEdit_Free(tm);
300 }
301
302 void EDBM_init_index_arrays(BMEditMesh *tm, int forvert, int foredge, int forface)
303 {
304         EDBM_free_index_arrays(tm);
305
306         if (forvert) {
307                 BMIter iter;
308                 BMVert *ele;
309                 int i = 0;
310                 
311                 tm->vert_index = MEM_mallocN(sizeof(void **) * tm->bm->totvert, "tm->vert_index");
312
313                 ele = BM_iter_new(&iter, tm->bm, BM_VERTS_OF_MESH, NULL);
314                 for ( ; ele; ele = BM_iter_step(&iter)) {
315                         tm->vert_index[i++] = ele;
316                 }
317         }
318
319         if (foredge) {
320                 BMIter iter;
321                 BMEdge *ele;
322                 int i = 0;
323                 
324                 tm->edge_index = MEM_mallocN(sizeof(void **) * tm->bm->totedge, "tm->edge_index");
325
326                 ele = BM_iter_new(&iter, tm->bm, BM_EDGES_OF_MESH, NULL);
327                 for ( ; ele; ele = BM_iter_step(&iter)) {
328                         tm->edge_index[i++] = ele;
329                 }
330         }
331
332         if (forface) {
333                 BMIter iter;
334                 BMFace *ele;
335                 int i = 0;
336                 
337                 tm->face_index = MEM_mallocN(sizeof(void **) * tm->bm->totface, "tm->face_index");
338
339                 ele = BM_iter_new(&iter, tm->bm, BM_FACES_OF_MESH, NULL);
340                 for ( ; ele; ele = BM_iter_step(&iter)) {
341                         tm->face_index[i++] = ele;
342                 }
343         }
344 }
345
346 void EDBM_free_index_arrays(BMEditMesh *tm)
347 {
348         if (tm->vert_index) {
349                 MEM_freeN(tm->vert_index);
350                 tm->vert_index = NULL;
351         }
352
353         if (tm->edge_index) {
354                 MEM_freeN(tm->edge_index);
355                 tm->edge_index = NULL;
356         }
357
358         if (tm->face_index) {
359                 MEM_freeN(tm->face_index);
360                 tm->face_index = NULL;
361         }
362 }
363
364 BMVert *EDBM_get_vert_for_index(BMEditMesh *tm, int index)
365 {
366         return tm->vert_index && index < tm->bm->totvert ?tm->vert_index[index]:NULL;
367 }
368
369 BMEdge *EDBM_get_edge_for_index(BMEditMesh *tm, int index)
370 {
371         return tm->edge_index && index < tm->bm->totedge ?tm->edge_index[index]:NULL;
372 }
373
374 BMFace *EDBM_get_face_for_index(BMEditMesh *tm, int index)
375 {
376         return (tm->face_index && index < tm->bm->totface && index >= 0) ? tm->face_index[index] : NULL;
377 }
378
379 void EDBM_selectmode_flush_ex(BMEditMesh *em, int selectmode)
380 {
381         em->bm->selectmode = selectmode;
382         BM_mesh_select_mode_flush(em->bm);
383         em->bm->selectmode = em->selectmode;
384 }
385
386 void EDBM_selectmode_flush(BMEditMesh *em)
387 {
388         EDBM_selectmode_flush_ex(em, em->selectmode);
389 }
390
391 void EDBM_deselect_flush(BMEditMesh *em)
392 {
393         /* function below doesnt use. just do this to keep the values in sync */
394         em->bm->selectmode = em->selectmode;
395         BM_mesh_deselect_flush(em->bm);
396 }
397
398
399 void EDBM_select_flush(BMEditMesh *em)
400 {
401         /* function below doesnt use. just do this to keep the values in sync */
402         em->bm->selectmode = em->selectmode;
403         BM_mesh_select_flush(em->bm);
404 }
405
406 void EDBM_select_more(BMEditMesh *em)
407 {
408         BMOperator bmop;
409         int usefaces = em->selectmode > SCE_SELECT_EDGE;
410
411         BMO_op_initf(em->bm, &bmop, 
412                     "regionextend geom=%hvef constrict=%d usefaces=%d",
413                     BM_ELEM_SELECT, 0, usefaces);
414         BMO_op_exec(em->bm, &bmop);
415         BMO_slot_buffer_hflag(em->bm, &bmop, "geomout", BM_ELEM_SELECT, BM_ALL);
416         BMO_op_finish(em->bm, &bmop);
417
418         EDBM_selectmode_flush(em);
419 }
420
421 void EDBM_select_less(BMEditMesh *em)
422 {
423         BMOperator bmop;
424         int usefaces = em->selectmode > SCE_SELECT_EDGE;
425
426         BMO_op_initf(em->bm, &bmop, 
427                     "regionextend geom=%hvef constrict=%d usefaces=%d",
428                     BM_ELEM_SELECT, 0, usefaces);
429         BMO_op_exec(em->bm, &bmop);
430         BMO_slot_buffer_hflag(em->bm, &bmop, "geomout", BM_ELEM_SELECT, BM_ALL);
431         BMO_op_finish(em->bm, &bmop);
432
433         EDBM_selectmode_flush(em);
434 }
435
436 int EDBM_get_actSelection(BMEditMesh *em, BMEditSelection *ese)
437 {
438         BMEditSelection *ese_last = em->bm->selected.last;
439         BMFace *efa = BM_active_face_get(em->bm, FALSE);
440
441         ese->next = ese->prev = NULL;
442         
443         if (ese_last) {
444                 if (ese_last->htype == BM_FACE) { /* if there is an active face, use it over the last selected face */
445                         if (efa) {
446                                 ese->data = (void *)efa;
447                         }
448                         else {
449                                 ese->data = ese_last->data;
450                         }
451                         ese->htype = BM_FACE;
452                 }
453                 else {
454                         ese->data = ese_last->data;
455                         ese->htype = ese_last->htype;
456                 }
457         }
458         else if (efa) { /* no */
459                 ese->data = (void *)efa;
460                 ese->htype = BM_FACE;
461         }
462         else {
463                 ese->data = NULL;
464                 return 0;
465         }
466         return 1;
467 }
468
469 void EDBM_clear_flag_all(BMEditMesh *em, const char hflag)
470 {
471         const char iter_types[3] = {BM_VERTS_OF_MESH,
472                                     BM_EDGES_OF_MESH,
473                                     BM_FACES_OF_MESH};
474         BMIter iter;
475         BMHeader *ele;
476         int i;
477
478         if (hflag & BM_ELEM_SELECT)
479                 BM_select_history_clear(em->bm);
480
481         for (i = 0; i < 3; i++) {
482                 BM_ITER(ele, &iter, em->bm, iter_types[i], NULL) {
483                         if (hflag & BM_ELEM_SELECT) BM_elem_select_set(em->bm, ele, FALSE);
484                         BM_elem_flag_clear(ele, hflag);
485                 }
486         }
487 }
488
489 void EDBM_set_flag_all(BMEditMesh *em, const char hflag)
490 {
491         const char iter_types[3] = {BM_VERTS_OF_MESH,
492                                     BM_EDGES_OF_MESH,
493                                     BM_FACES_OF_MESH};
494         BMIter iter;
495         BMHeader *ele;
496         int i;
497
498         for (i = 0; i < 3; i++) {
499                 ele = BM_iter_new(&iter, em->bm, iter_types[i], NULL);
500                 for ( ; ele; ele = BM_iter_step(&iter)) {
501                         if (hflag & BM_ELEM_SELECT) {
502                                 BM_elem_select_set(em->bm, ele, TRUE);
503                         }
504                         else {
505                                 BM_elem_flag_set(ele, hflag);
506                         }
507                 }
508         }
509 }
510
511 /**************-------------- Undo ------------*****************/
512
513 /* for callbacks */
514
515 static void *getEditMesh(bContext *C)
516 {
517         Object *obedit = CTX_data_edit_object(C);
518         if (obedit && obedit->type == OB_MESH) {
519                 Mesh *me = obedit->data;
520                 return me->edit_btmesh;
521         }
522         return NULL;
523 }
524
525 typedef struct undomesh {
526         Mesh me;
527         int selectmode;
528         char obname[MAX_ID_NAME - 2];
529 } undomesh;
530
531 /* undo simply makes copies of a bmesh */
532 static void *editbtMesh_to_undoMesh(void *emv, void *obdata)
533 {
534         BMEditMesh *em = emv;
535         Mesh *obme = obdata;
536         
537         undomesh *um = MEM_callocN(sizeof(undomesh), "undo Mesh");
538         BLI_strncpy(um->obname, em->bm->ob->id.name + 2, sizeof(um->obname));
539         
540         /* make sure shape keys work */
541         um->me.key = obme->key ? copy_key_nolib(obme->key) : NULL;
542
543 #ifdef BMESH_EM_UNDO_RECALC_TESSFACE_WORKAROUND
544
545         /* we recalc the tesselation here, to avoid seeding calls to
546          * BMEdit_RecalcTesselation throughout the code. */
547         BMEdit_RecalcTesselation(em);
548
549 #endif
550
551         BMO_op_callf(em->bm, "bmesh_to_mesh mesh=%p notesselation=%i", &um->me, 1);
552         um->selectmode = em->selectmode;
553
554         return um;
555 }
556
557 static void undoMesh_to_editbtMesh(void *umv, void *emv, void *UNUSED(obdata))
558 {
559         BMEditMesh *em = emv, *em2;
560         Object *ob;
561         undomesh *um = umv;
562         BMesh *bm;
563         
564         ob = (Object *)find_id("OB", um->obname);
565         ob->shapenr = em->bm->shapenr;
566
567         BMEdit_Free(em);
568
569         bm = BM_mesh_create(ob, bm_mesh_allocsize_default);
570         BMO_op_callf(bm, "mesh_to_bmesh mesh=%p object=%p set_shapekey=%i", &um->me, ob, 0);
571
572         em2 = BMEdit_Create(bm, TRUE);
573         *em = *em2;
574         
575         em->selectmode = um->selectmode;
576
577         MEM_freeN(em2);
578 }
579
580
581 static void free_undo(void *umv)
582 {
583         if (((Mesh *)umv)->key) {
584                 free_key(((Mesh *)umv)->key);
585                 MEM_freeN(((Mesh *)umv)->key);
586         }
587         
588         free_mesh(umv, 0);
589         MEM_freeN(umv);
590 }
591
592 /* and this is all the undo system needs to know */
593 void undo_push_mesh(bContext *C, const char *name)
594 {
595         undo_editmode_push(C, name, getEditMesh, free_undo, undoMesh_to_editbtMesh, editbtMesh_to_undoMesh, NULL);
596 }
597
598 /* write comment here */
599 UvVertMap *EDBM_make_uv_vert_map(BMEditMesh *em, int selected, int do_face_idx_array, float *limit)
600 {
601         BMVert *ev;
602         BMFace *efa;
603         BMLoop *l;
604         BMIter iter, liter;
605         /* vars from original func */
606         UvVertMap *vmap;
607         UvMapVert *buf;
608         /* MTexPoly *tf; */ /* UNUSED */
609         MLoopUV *luv;
610         unsigned int a;
611         int totverts, i, totuv;
612         
613         if (do_face_idx_array)
614                 EDBM_init_index_arrays(em, 0, 0, 1);
615
616         BM_mesh_elem_index_ensure(em->bm, BM_VERT);
617         
618         totverts = em->bm->totvert;
619         totuv = 0;
620
621         /* generate UvMapVert array */
622         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
623                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT)))
624                         totuv += efa->len;
625         }
626
627         if (totuv == 0) {
628                 if (do_face_idx_array)
629                         EDBM_free_index_arrays(em);
630                 return NULL;
631         }
632         vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
633         if (!vmap) {
634                 if (do_face_idx_array)
635                         EDBM_free_index_arrays(em);
636                 return NULL;
637         }
638
639         vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert)*totverts, "UvMapVert_pt");
640         buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
641
642         if (!vmap->vert || !vmap->buf) {
643                 free_uv_vert_map(vmap);
644                 if (do_face_idx_array)
645                         EDBM_free_index_arrays(em);
646                 return NULL;
647         }
648         
649         a = 0;
650         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
651                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT))) {
652                         i = 0;
653                         BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, efa) {
654                                 buf->tfindex = i;
655                                 buf->f = a;
656                                 buf->separate = 0;
657                                 
658                                 buf->next = vmap->vert[BM_elem_index_get(l->v)];
659                                 vmap->vert[BM_elem_index_get(l->v)] = buf;
660                                 
661                                 buf++;
662                                 i++;
663                         }
664                 }
665
666                 a++;
667         }
668         
669         /* sort individual uvs for each vert */
670         a = 0;
671         BM_ITER(ev, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
672                 UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
673                 UvMapVert *iterv, *v, *lastv, *next;
674                 float *uv, *uv2, uvdiff[2];
675
676                 while (vlist) {
677                         v = vlist;
678                         vlist = vlist->next;
679                         v->next = newvlist;
680                         newvlist = v;
681
682                         efa = EDBM_get_face_for_index(em, v->f);
683                         /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
684                         
685                         l = BM_iter_at_index(em->bm, BM_LOOPS_OF_FACE, efa, v->tfindex);
686                         luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
687                         uv = luv->uv;
688                         
689                         lastv = NULL;
690                         iterv = vlist;
691
692                         while (iterv) {
693                                 next = iterv->next;
694                                 efa = EDBM_get_face_for_index(em, iterv->f);
695                                 /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
696                                 
697                                 l = BM_iter_at_index(em->bm, BM_LOOPS_OF_FACE, efa, iterv->tfindex);
698                                 luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
699                                 uv2 = luv->uv;
700                                 
701                                 sub_v2_v2v2(uvdiff, uv2, uv);
702
703                                 if (fabs(uvdiff[0]) < limit[0] && fabs(uvdiff[1]) < limit[1]) {
704                                         if (lastv) lastv->next = next;
705                                         else vlist = next;
706                                         iterv->next = newvlist;
707                                         newvlist = iterv;
708                                 }
709                                 else
710                                         lastv = iterv;
711
712                                 iterv = next;
713                         }
714
715                         newvlist->separate = 1;
716                 }
717
718                 vmap->vert[a] = newvlist;
719                 a++;
720         }
721         
722         if (do_face_idx_array)
723                 EDBM_free_index_arrays(em);
724         
725         return vmap;
726 }
727
728
729 UvMapVert *EDBM_get_uv_map_vert(UvVertMap *vmap, unsigned int v)
730 {
731         return vmap->vert[v];
732 }
733
734 /* from editmesh_lib.c in trunk */
735
736
737 /* A specialized vert map used by stitch operator */
738 UvElementMap *EDBM_make_uv_element_map(BMEditMesh *em, int selected, int do_islands)
739 {
740         BMVert *ev;
741         BMFace *efa;
742         BMLoop *l;
743         BMIter iter, liter;
744         /* vars from original func */
745         UvElementMap *element_map;
746         UvElement *buf;
747         UvElement *islandbuf;
748
749         MLoopUV *luv;
750         int totverts, i, totuv, j, nislands = 0, islandbufsize = 0;
751
752         unsigned int *map;
753         BMFace **stack;
754         int stacksize = 0;
755
756         BM_mesh_elem_index_ensure(em->bm, BM_VERT | BM_FACE);
757
758         totverts = em->bm->totvert;
759         totuv = 0;
760
761         /* generate UvElement array */
762         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
763                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT)))
764                         totuv += efa->len;
765         }
766
767         if (totuv == 0) {
768                 return NULL;
769         }
770         element_map = (UvElementMap *)MEM_callocN(sizeof(*element_map), "UvElementMap");
771         if (!element_map) {
772                 return NULL;
773         }
774         element_map->totalUVs = totuv;
775         element_map->vert = (UvElement **)MEM_callocN(sizeof(*element_map->vert) * totverts, "UvElementVerts");
776         buf = element_map->buf = (UvElement *)MEM_callocN(sizeof(*element_map->buf) * totuv, "UvElement");
777
778         if (!element_map->vert || !element_map->buf) {
779                 EDBM_free_uv_element_map(element_map);
780                 return NULL;
781         }
782
783         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
784                 if (!selected || ((!BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) && BM_elem_flag_test(efa, BM_ELEM_SELECT))) {
785                         i = 0;
786                         BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, efa) {
787                                 buf->tfindex = i;
788                                 buf->face = efa;
789                                 buf->separate = 0;
790                                 buf->island = INVALID_ISLAND;
791
792                                 buf->next = element_map->vert[BM_elem_index_get(l->v)];
793                                 element_map->vert[BM_elem_index_get(l->v)] = buf;
794
795                                 buf++;
796                                 i++;
797                         }
798                 }
799         }
800
801         /* sort individual uvs for each vert */
802         i = 0;
803         BM_ITER(ev, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
804                 UvElement *newvlist = NULL, *vlist = element_map->vert[i];
805                 UvElement *iterv, *v, *lastv, *next;
806                 float *uv, *uv2, uvdiff[2];
807
808                 while (vlist) {
809                         v = vlist;
810                         vlist = vlist->next;
811                         v->next = newvlist;
812                         newvlist = v;
813
814                         efa = v->face;
815                         /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
816
817                         l = BM_iter_at_index(em->bm, BM_LOOPS_OF_FACE, efa, v->tfindex);
818                         luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
819                         uv = luv->uv;
820
821                         lastv = NULL;
822                         iterv = vlist;
823
824                         while (iterv) {
825                                 next = iterv->next;
826                                 efa = iterv->face;
827                                 /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
828
829                                 l = BM_iter_at_index(em->bm, BM_LOOPS_OF_FACE, efa, iterv->tfindex);
830                                 luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
831                                 uv2 = luv->uv;
832
833                                 sub_v2_v2v2(uvdiff, uv2, uv);
834
835                                 if (fabsf(uvdiff[0]) < STD_UV_CONNECT_LIMIT && fabsf(uvdiff[1]) < STD_UV_CONNECT_LIMIT) {
836                                         if (lastv) lastv->next = next;
837                                         else vlist = next;
838                                         iterv->next = newvlist;
839                                         newvlist = iterv;
840                                 }
841                                 else {
842                                         lastv = iterv;
843                                 }
844
845                                 iterv = next;
846                         }
847
848                         newvlist->separate = 1;
849                 }
850
851                 element_map->vert[i] = newvlist;
852                 i++;
853         }
854
855         if (do_islands) {
856                 /* at this point, every UvElement in vert points to a UvElement sharing the same vertex. Now we should sort uv's in islands. */
857                 int *island_number;
858                 /* map holds the map from current vmap->buf to the new, sorted map */
859                 map = MEM_mallocN(sizeof(*map)*totuv, "uvelement_remap");
860                 stack = MEM_mallocN(sizeof(*stack)*em->bm->totface, "uv_island_face_stack");
861                 islandbuf = MEM_callocN(sizeof(*islandbuf)*totuv, "uvelement_island_buffer");
862                 island_number = MEM_mallocN(sizeof(*stack)*em->bm->totface, "uv_island_number_face");
863
864                 for (i = 0; i < totuv; i++) {
865                         if (element_map->buf[i].island == INVALID_ISLAND) {
866                                 element_map->buf[i].island = nislands;
867                                 stack[0] = element_map->buf[i].face;
868                                 island_number[BM_elem_index_get(stack[0])] = nislands;
869                                 stacksize = 1;
870
871                                 while (stacksize > 0) {
872                                         efa = stack[--stacksize];
873
874                                         BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, efa) {
875                                                 UvElement *element, *initelement = element_map->vert[BM_elem_index_get(l->v)];
876
877                                                 for (element = initelement; element; element = element->next) {
878                                                         if (element->separate)
879                                                                 initelement = element;
880
881                                                         if (element->face == efa) {
882                                                                 /* found the uv corresponding to our face and vertex. Now fill it to the buffer */
883                                                                 element->island = nislands;
884                                                                 map[element - element_map->buf] = islandbufsize;
885                                                                 islandbuf[islandbufsize].tfindex = element->tfindex;
886                                                                 islandbuf[islandbufsize].face = element->face;
887                                                                 islandbuf[islandbufsize].separate = element->separate;
888                                                                 islandbuf[islandbufsize].island =  nislands;
889                                                                 islandbufsize++;
890
891                                                                 for (element = initelement; element; element = element->next) {
892                                                                         if (element->separate && element != initelement)
893                                                                                 break;
894
895                                                                         if (island_number[BM_elem_index_get(element->face)] == INVALID_ISLAND) {
896                                                                                 stack[stacksize++] = element->face;
897                                                                                 island_number[BM_elem_index_get(element->face)] = nislands;
898                                                                         }
899                                                                 }
900                                                                 break;
901                                                         }
902                                                 }
903                                         }
904                                 }
905
906                                 nislands++;
907                         }
908                 }
909
910                 /* remap */
911                 for (i = 0; i < em->bm->totvert; i++) {
912                         /* important since we may do selection only. Some of these may be NULL */
913                         if (element_map->vert[i])
914                                 element_map->vert[i] = &islandbuf[map[element_map->vert[i] - element_map->buf]];
915                 }
916
917                 element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices)*nislands,"UvElementMap_island_indices");
918                 if (!element_map->islandIndices) {
919                         MEM_freeN(islandbuf);
920                         MEM_freeN(stack);
921                         MEM_freeN(map);
922                         EDBM_free_uv_element_map(element_map);
923                         MEM_freeN(island_number);
924                 }
925
926                 j = 0;
927                 for (i = 0; i < totuv; i++) {
928                         UvElement *element = element_map->buf[i].next;
929                         if (element == NULL)
930                                 islandbuf[map[i]].next = NULL;
931                         else
932                                 islandbuf[map[i]].next = &islandbuf[map[element - element_map->buf]];
933
934                         if (islandbuf[i].island != j) {
935                                 j++;
936                                 element_map->islandIndices[j] = i;
937                         }
938                 }
939
940                 MEM_freeN(element_map->buf);
941
942                 element_map->buf = islandbuf;
943                 element_map->totalIslands = nislands;
944                 MEM_freeN(stack);
945                 MEM_freeN(map);
946                 MEM_freeN(island_number);
947         }
948
949         return element_map;
950 }
951
952
953 UvMapVert *EM_get_uv_map_vert(UvVertMap *vmap, unsigned int v)
954 {
955         return vmap->vert[v];
956 }
957
958 void EDBM_free_uv_vert_map(UvVertMap *vmap)
959 {
960         if (vmap) {
961                 if (vmap->vert) MEM_freeN(vmap->vert);
962                 if (vmap->buf) MEM_freeN(vmap->buf);
963                 MEM_freeN(vmap);
964         }
965 }
966
967 void EDBM_free_uv_element_map(UvElementMap *element_map)
968 {
969         if (element_map) {
970                 if (element_map->vert) MEM_freeN(element_map->vert);
971                 if (element_map->buf) MEM_freeN(element_map->buf);
972                 if (element_map->islandIndices) MEM_freeN(element_map->islandIndices);
973                 MEM_freeN(element_map);
974         }
975 }
976
977 /* last_sel, use em->act_face otherwise get the last selected face in the editselections
978  * at the moment, last_sel is mainly useful for gaking sure the space image dosnt flicker */
979 MTexPoly *EDBM_get_active_mtexpoly(BMEditMesh *em, BMFace **act_efa, int sloppy)
980 {
981         BMFace *efa = NULL;
982         
983         if (!EDBM_texFaceCheck(em))
984                 return NULL;
985         
986         efa = BM_active_face_get(em->bm, sloppy);
987         
988         if (efa) {
989                 if (act_efa) *act_efa = efa;
990                 return CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY);
991         }
992
993         if (act_efa) *act_efa = NULL;
994         return NULL;
995 }
996
997 /* can we edit UV's for this mesh?*/
998 int EDBM_texFaceCheck(BMEditMesh *em)
999 {
1000         /* some of these checks could be a touch overkill */
1001         return em && em->bm->totface && CustomData_has_layer(&em->bm->pdata, CD_MTEXPOLY) &&
1002                    CustomData_has_layer(&em->bm->ldata, CD_MLOOPUV);
1003 }
1004
1005 int EDBM_vertColorCheck(BMEditMesh *em)
1006 {
1007         /* some of these checks could be a touch overkill */
1008         return em && em->bm->totface && CustomData_has_layer(&em->bm->ldata, CD_MLOOPCOL);
1009 }
1010
1011 static BMVert *cache_mirr_intptr_as_bmvert(intptr_t *index_lookup, int index)
1012 {
1013         intptr_t eve_i = index_lookup[index];
1014         return (eve_i == -1) ? NULL : (BMVert *)eve_i;
1015 }
1016
1017 /* BM_SEARCH_MAXDIST is too big, copied from 2.6x MOC_THRESH, should become a
1018  * preference */
1019 #define BM_SEARCH_MAXDIST_MIRR 0.00002f
1020 #define BM_CD_LAYER_ID "__mirror_index"
1021 void EDBM_CacheMirrorVerts(BMEditMesh *em, const short use_select)
1022 {
1023         Mesh *me = em->me;
1024         BMesh *bm = em->bm;
1025         BMIter iter;
1026         BMVert *v;
1027         int li, topo = 0;
1028
1029         /* one or the other is used depending if topo is enabled */
1030         BMBVHTree *tree = NULL;
1031         MirrTopoStore_t mesh_topo_store = {NULL, -1, -1, -1};
1032
1033         if (me && (me->editflag & ME_EDIT_MIRROR_TOPO)) {
1034                 topo = 1;
1035         }
1036
1037         if (!em->vert_index) {
1038                 EDBM_init_index_arrays(em, 1, 0, 0);
1039                 em->mirr_free_arrays = 1;
1040         }
1041
1042         if (!CustomData_get_layer_named(&bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID)) {
1043                 BM_data_layer_add_named(bm, &bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID);
1044         }
1045
1046         li = CustomData_get_named_layer_index(&bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID);
1047
1048         bm->vdata.layers[li].flag |= CD_FLAG_TEMPORARY;
1049
1050         BM_mesh_elem_index_ensure(bm, BM_VERT);
1051
1052         if (topo) {
1053                 ED_mesh_mirrtopo_init(me, -1, &mesh_topo_store, TRUE);
1054         }
1055         else {
1056                  tree = BMBVH_NewBVH(em, 0, NULL, NULL);
1057         }
1058
1059         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
1060
1061                 /* temporary for testing, check for selection */
1062                 if (use_select && !BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1063                         /* do nothing */
1064                 }
1065                 else {
1066                         BMVert *mirr;
1067                         int *idx = CustomData_bmesh_get_layer_n(&bm->vdata, v->head.data, li);
1068
1069                         if (topo) {
1070                                 mirr = cache_mirr_intptr_as_bmvert(mesh_topo_store.index_lookup, BM_elem_index_get(v));
1071                         }
1072                         else {
1073                                 float co[3] = {-v->co[0], v->co[1], v->co[2]};
1074                                 mirr = BMBVH_FindClosestVert(tree, co, BM_SEARCH_MAXDIST_MIRR);
1075                         }
1076
1077                         if (mirr && mirr != v) {
1078                                 *idx = BM_elem_index_get(mirr);
1079                                 idx = CustomData_bmesh_get_layer_n(&bm->vdata, mirr->head.data, li);
1080                                 *idx = BM_elem_index_get(v);
1081                         }
1082                         else {
1083                                 *idx = -1;
1084                         }
1085                 }
1086
1087         }
1088
1089
1090         if (topo) {
1091                 ED_mesh_mirrtopo_free(&mesh_topo_store);
1092         }
1093         else {
1094                 BMBVH_FreeBVH(tree);
1095         }
1096
1097         em->mirror_cdlayer = li;
1098 }
1099
1100 BMVert *EDBM_GetMirrorVert(BMEditMesh *em, BMVert *v)
1101 {
1102         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
1103
1104         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
1105
1106         if (mirr && *mirr >= 0 && *mirr < em->bm->totvert) {
1107                 if (!em->vert_index) {
1108                         printf("err: should only be called between "
1109                                "EDBM_CacheMirrorVerts and EDBM_EndMirrorCache");
1110                         return NULL;
1111                 }
1112
1113                 return em->vert_index[*mirr];
1114         }
1115
1116         return NULL;
1117 }
1118
1119 void EDBM_ClearMirrorVert(BMEditMesh *em, BMVert *v)
1120 {
1121         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
1122
1123         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
1124
1125         if (mirr) {
1126                 *mirr = -1;
1127         }
1128 }
1129
1130 void EDBM_EndMirrorCache(BMEditMesh *em)
1131 {
1132         if (em->mirr_free_arrays) {
1133                 MEM_freeN(em->vert_index);
1134                 em->vert_index = NULL;
1135         }
1136
1137         em->mirror_cdlayer = -1;
1138 }
1139
1140 void EDBM_ApplyMirrorCache(BMEditMesh *em, const int sel_from, const int sel_to)
1141 {
1142         BMIter iter;
1143         BMVert *v;
1144
1145         BLI_assert(em->vert_index != NULL);
1146
1147         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1148                 if (BM_elem_flag_test(v, BM_ELEM_SELECT) == sel_from) {
1149                         BMVert *mirr = EDBM_GetMirrorVert(em, v);
1150                         if (mirr) {
1151                                 if (BM_elem_flag_test(mirr, BM_ELEM_SELECT) == sel_to) {
1152                                         copy_v3_v3(mirr->co, v->co);
1153                                         mirr->co[0] *= -1.0f;
1154                                 }
1155                         }
1156                 }
1157         }
1158 }