bmesh: fixed merge issues with navmesh (though I've not tested if it works yet).
[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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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 #include <stdlib.h>
28 #include <stdarg.h>
29 #include <string.h>
30 #include <math.h>
31 #include <float.h>
32
33 #include "MEM_guardedalloc.h"
34 #include "PIL_time.h"
35
36 #include "BLO_sys_types.h" // for intptr_t support
37
38 #include "DNA_mesh_types.h"
39 #include "DNA_material_types.h"
40 #include "DNA_meshdata_types.h"
41 #include "DNA_modifier_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_scene_types.h"
44 #include "DNA_screen_types.h"
45 #include "DNA_view3d_types.h"
46 #include "DNA_key_types.h"
47
48 #include "RNA_types.h"
49 #include "RNA_define.h"
50 #include "RNA_access.h"
51
52 #include "BLI_utildefines.h"
53 #include "BLI_blenlib.h"
54 #include "BLI_math.h"
55 #include "BLI_editVert.h"
56 #include "BLI_rand.h"
57 #include "BLI_ghash.h"
58 #include "BLI_linklist.h"
59 #include "BLI_heap.h"
60 #include "BLI_array.h"
61
62 #include "BKE_context.h"
63 #include "BKE_customdata.h"
64 #include "BKE_depsgraph.h"
65 #include "BKE_global.h"
66 #include "BKE_library.h"
67 #include "BKE_key.h"
68 #include "BKE_mesh.h"
69 #include "BKE_object.h"
70 #include "BKE_bmesh.h"
71 #include "BKE_report.h"
72 #include "BKE_tessmesh.h"
73
74 #include "bmesh.h"
75
76 #include "BIF_gl.h"
77 #include "BIF_glutil.h"
78
79 #include "WM_api.h"
80 #include "WM_types.h"
81
82 #include "ED_mesh.h"
83 #include "ED_view3d.h"
84 #include "ED_util.h"
85 #include "ED_screen.h"
86
87 #include "UI_interface.h"
88
89 #include "editbmesh_bvh.h"
90 #include "mesh_intern.h"
91
92 void EDBM_RecalcNormals(BMEditMesh *em)
93 {
94         BM_Compute_Normals(em->bm);
95 }
96
97 void EDBM_ClearMesh(BMEditMesh *em)
98 {
99         /*clear bmesh*/
100         BM_Clear_Mesh(em->bm);
101         
102         /*free derived meshes*/
103         if (em->derivedCage) {
104                 em->derivedCage->needsFree = 1;
105                 em->derivedCage->release(em->derivedCage);
106         }
107         if (em->derivedFinal && em->derivedFinal != em->derivedCage) {
108                 em->derivedFinal->needsFree = 1;
109                 em->derivedFinal->release(em->derivedFinal);
110         }
111         
112         em->derivedCage = em->derivedFinal = NULL;
113         
114         /*free tesselation data*/
115         em->tottri = 0;
116         if (em->looptris) 
117                 MEM_freeN(em->looptris);
118 }
119
120 void EDBM_stats_update(BMEditMesh *em)
121 {
122         BMIter iter;
123         BMHeader *ele;
124         int types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, BM_FACES_OF_MESH};
125         int *tots[3];
126         int i;
127
128         tots[0] = &em->bm->totvertsel;
129         tots[1] = &em->bm->totedgesel;
130         tots[2] = &em->bm->totfacesel;
131         
132         em->bm->totvertsel = em->bm->totedgesel = em->bm->totfacesel = 0;
133
134         for (i=0; i<3; i++) {
135                 ele = BMIter_New(&iter, em->bm, types[i], NULL);
136                 for ( ; ele; ele=BMIter_Step(&iter)) {
137                         if (BM_TestHFlag(ele, BM_SELECT)) {
138                                 *tots[i]++;
139                         }
140                 }
141         }
142 }
143
144 int EDBM_InitOpf(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const char *fmt, ...)
145 {
146         BMesh *bm = em->bm;
147         va_list list;
148
149         va_start(list, fmt);
150
151         if (!BMO_VInitOpf(bm, bmop, fmt, list)) {
152                 BKE_report(op->reports, RPT_ERROR,
153                            "Parse error in EDBM_CallOpf");
154                 va_end(list);
155                 return 0;
156         }
157         
158         if (!em->emcopy)
159                 em->emcopy = BMEdit_Copy(em);
160         em->emcopyusers++;
161
162         va_end(list);
163
164         return 1;
165 }
166
167
168 /*returns 0 on error, 1 on success.  executes and finishes a bmesh operator*/
169 int EDBM_FinishOp(BMEditMesh *em, BMOperator *bmop, wmOperator *op, int report)
170 {
171         const char *errmsg;
172         
173         BMO_Finish_Op(em->bm, bmop);
174
175         if (BMO_GetError(em->bm, &errmsg, NULL)) {
176                 BMEditMesh *emcopy = em->emcopy;
177
178                 if (report) BKE_report(op->reports, RPT_ERROR, errmsg);
179
180                 BMEdit_Free(em);
181                 *em = *emcopy;
182                 BMEdit_RecalcTesselation(em);
183
184                 MEM_freeN(emcopy);
185                 em->emcopyusers = 0;
186                 em->emcopy = NULL;
187                 return 0;
188         } else {
189                 em->emcopyusers--;
190                 if (em->emcopyusers < 0) {
191                         printf("warning: em->emcopyusers was less then zero.\n");
192                 }
193
194                 if (em->emcopyusers <= 0) {
195                         BMEdit_Free(em->emcopy);
196                         MEM_freeN(em->emcopy);
197                         em->emcopy = NULL;
198                 }
199         }
200
201         return 1;
202 }
203
204 int EDBM_CallOpf(BMEditMesh *em, wmOperator *op, const char *fmt, ...)
205 {
206         BMesh *bm = em->bm;
207         BMOperator bmop;
208         va_list list;
209
210         va_start(list, fmt);
211
212         if (!BMO_VInitOpf(bm, &bmop, fmt, list)) {
213                 BKE_report(op->reports, RPT_ERROR,
214                            "Parse error in EDBM_CallOpf");
215                 va_end(list);
216                 return 0;
217         }
218
219         if (!em->emcopy)
220                 em->emcopy = BMEdit_Copy(em);
221         em->emcopyusers++;
222
223         BMO_Exec_Op(bm, &bmop);
224
225         va_end(list);
226         return EDBM_FinishOp(em, &bmop, op, 1);
227 }
228
229 int EDBM_CallAndSelectOpf(BMEditMesh *em, wmOperator *op, const char *selectslot, const char *fmt, ...)
230 {
231         BMesh *bm = em->bm;
232         BMOperator bmop;
233         va_list list;
234
235         va_start(list, fmt);
236
237         if (!BMO_VInitOpf(bm, &bmop, fmt, list)) {
238                 BKE_report(op->reports, RPT_ERROR,
239                            "Parse error in EDBM_CallOpf");
240                 va_end(list);
241                 return 0;
242         }
243
244         if (!em->emcopy)
245                 em->emcopy = BMEdit_Copy(em);
246         em->emcopyusers++;
247
248         BMO_Exec_Op(bm, &bmop);
249         BMO_HeaderFlag_Buffer(em->bm, &bmop, selectslot, BM_SELECT, BM_ALL);
250
251         va_end(list);
252         return EDBM_FinishOp(em, &bmop, op, 1);
253 }
254
255 int EDBM_CallOpfSilent(BMEditMesh *em, const char *fmt, ...)
256 {
257         BMesh *bm = em->bm;
258         BMOperator bmop;
259         va_list list;
260
261         va_start(list, fmt);
262
263         if (!BMO_VInitOpf(bm, &bmop, fmt, list)) {
264                 va_end(list);
265                 return 0;
266         }
267
268         if (!em->emcopy)
269                 em->emcopy = BMEdit_Copy(em);
270         em->emcopyusers++;
271
272         BMO_Exec_Op(bm, &bmop);
273
274         va_end(list);
275         return EDBM_FinishOp(em, &bmop, NULL, 0);
276 }
277
278 void EDBM_selectmode_to_scene(bContext *C)
279 {
280         Scene *scene = CTX_data_scene(C);
281         Object *obedit = CTX_data_edit_object(C);
282         BMEditMesh *em = ((Mesh*)obedit->data)->edit_btmesh;
283
284         if (!em)
285                 return;
286
287         scene->toolsettings->selectmode = em->selectmode;
288
289         /* Request redraw of header buttons (to show new select mode) */
290         WM_event_add_notifier(C, NC_SCENE|ND_TOOLSETTINGS, scene);
291 }
292
293 void EDBM_MakeEditBMesh(ToolSettings *ts, Scene *UNUSED(scene), Object *ob)
294 {
295         Mesh *me = ob->data;
296         BMesh *bm;
297
298         if (!me->mpoly && me->totface) {
299                 fprintf(stderr, "%s: bmesh conversion issue! may lose lots of geometry! (bmesh internal error)\n", __func__);
300                 
301                 /*BMESH_TODO need to write smarter code here*/
302                 bm = BKE_mesh_to_bmesh(me, ob);
303         } else {
304                 bm = BKE_mesh_to_bmesh(me, ob);
305         }
306
307         if (me->edit_btmesh) {
308                 /* this happens when switching shape keys */
309                 BMEdit_Free(me->edit_btmesh);
310                 MEM_freeN(me->edit_btmesh);
311         }
312
313         me->edit_btmesh = BMEdit_Create(bm);
314         me->edit_btmesh->selectmode= me->edit_btmesh->bm->selectmode= ts->selectmode;
315         me->edit_btmesh->me = me;
316         me->edit_btmesh->ob = ob;
317 }
318
319 void EDBM_LoadEditBMesh(Scene *scene, Object *ob)
320 {
321         Mesh *me = ob->data;
322         BMesh *bm = me->edit_btmesh->bm;
323
324         BMO_CallOpf(bm, "object_load_bmesh scene=%p object=%p", scene, ob);
325 }
326
327 void EDBM_FreeEditBMesh(BMEditMesh *tm)
328 {
329         BMEdit_Free(tm);
330 }
331
332 void EDBM_init_index_arrays(BMEditMesh *tm, int forvert, int foredge, int forface)
333 {
334         EDBM_free_index_arrays(tm);
335
336         if (forvert) {
337                 BMIter iter;
338                 BMVert *ele;
339                 int i=0;
340                 
341                 tm->vert_index = MEM_mallocN(sizeof(void**)*tm->bm->totvert, "tm->vert_index");
342
343                 ele = BMIter_New(&iter, tm->bm, BM_VERTS_OF_MESH, NULL);
344                 for ( ; ele; ele=BMIter_Step(&iter)) {
345                         tm->vert_index[i++] = ele;
346                 }
347         }
348
349         if (foredge) {
350                 BMIter iter;
351                 BMEdge *ele;
352                 int i=0;
353                 
354                 tm->edge_index = MEM_mallocN(sizeof(void**)*tm->bm->totedge, "tm->edge_index");
355
356                 ele = BMIter_New(&iter, tm->bm, BM_EDGES_OF_MESH, NULL);
357                 for ( ; ele; ele=BMIter_Step(&iter)) {
358                         tm->edge_index[i++] = ele;
359                 }
360         }
361
362         if (forface) {
363                 BMIter iter;
364                 BMFace *ele;
365                 int i=0;
366                 
367                 tm->face_index = MEM_mallocN(sizeof(void**)*tm->bm->totface, "tm->face_index");
368
369                 ele = BMIter_New(&iter, tm->bm, BM_FACES_OF_MESH, NULL);
370                 for ( ; ele; ele=BMIter_Step(&iter)) {
371                         tm->face_index[i++] = ele;
372                 }
373         }
374 }
375
376 void EDBM_free_index_arrays(BMEditMesh *tm)
377 {
378         if (tm->vert_index) {
379                 MEM_freeN(tm->vert_index);
380                 tm->vert_index = NULL;
381         }
382
383         if (tm->edge_index) {
384                 MEM_freeN(tm->edge_index);
385                 tm->edge_index = NULL;
386         }
387
388         if (tm->face_index) {
389                 MEM_freeN(tm->face_index);
390                 tm->face_index = NULL;
391         }
392 }
393
394 BMVert *EDBM_get_vert_for_index(BMEditMesh *tm, int index)
395 {
396         return tm->vert_index && index < tm->bm->totvert ?tm->vert_index[index]:NULL;
397 }
398
399 BMEdge *EDBM_get_edge_for_index(BMEditMesh *tm, int index)
400 {
401         return tm->edge_index && index < tm->bm->totedge ?tm->edge_index[index]:NULL;
402 }
403
404 BMFace *EDBM_get_face_for_index(BMEditMesh *tm, int index)
405 {
406         return (tm->face_index && index<tm->bm->totface && index>=0) ? tm->face_index[index] : NULL;
407 }
408
409 void EDBM_select_flush(BMEditMesh *em, int selectmode)
410 {
411         em->bm->selectmode = selectmode;
412         BM_SelectMode_Flush(em->bm);
413         em->bm->selectmode = em->selectmode;
414 }
415
416 /*BMESH_TODO*/
417 void EDBM_deselect_flush(BMEditMesh *UNUSED(em))
418 {
419 }
420
421
422 void EDBM_selectmode_flush(BMEditMesh *em)
423 {
424         em->bm->selectmode = em->selectmode;
425         BM_SelectMode_Flush(em->bm);
426 }
427
428 /*EDBM_select_[more/less] are api functions, I think the uv editor
429   uses them? though the select more/less ops themselves do not.*/
430 static void EDBM_select_more(BMEditMesh *em)
431 {
432         BMOperator bmop;
433         int usefaces = em->selectmode > SCE_SELECT_EDGE;
434
435         BMO_InitOpf(em->bm, &bmop, 
436                     "regionextend geom=%hvef constrict=%d usefaces=%d",
437                     BM_SELECT, 0, usefaces);
438         BMO_Exec_Op(em->bm, &bmop);
439         BMO_HeaderFlag_Buffer(em->bm, &bmop, "geomout", BM_SELECT, BM_ALL);
440         BMO_Finish_Op(em->bm, &bmop);
441
442         EDBM_selectmode_flush(em);
443 }
444
445 static void EDBM_select_less(BMEditMesh *em)
446 {
447         BMOperator bmop;
448         int usefaces = em->selectmode > SCE_SELECT_EDGE;
449
450         BMO_InitOpf(em->bm, &bmop, 
451                     "regionextend geom=%hvef constrict=%d usefaces=%d",
452                     BM_SELECT, 0, usefaces);
453         BMO_Exec_Op(em->bm, &bmop);
454         BMO_HeaderFlag_Buffer(em->bm, &bmop, "geomout", BM_SELECT, BM_ALL);
455         BMO_Finish_Op(em->bm, &bmop);
456
457         EDBM_selectmode_flush(em);
458 }
459
460 int EDBM_get_actSelection(BMEditMesh *em, BMEditSelection *ese)
461 {
462         BMEditSelection *ese_last = em->bm->selected.last;
463         BMFace *efa = BM_get_actFace(em->bm, 0);
464
465         ese->next = ese->prev = NULL;
466         
467         if (ese_last) {
468                 if (ese_last->htype == BM_FACE) { /* if there is an active face, use it over the last selected face */
469                         if (efa) {
470                                 ese->data = (void *)efa;
471                         } else {
472                                 ese->data = ese_last->data;
473                         }
474                         ese->htype = BM_FACE;
475                 }
476                 else {
477                         ese->data = ese_last->data;
478                         ese->htype = ese_last->htype;
479                 }
480         }
481         else if (efa) { /* no */
482                 ese->data= (void *)efa;
483                 ese->htype= BM_FACE;
484         }
485         else {
486                 ese->data = NULL;
487                 return 0;
488         }
489         return 1;
490 }
491
492 void EDBM_clear_flag_all(BMEditMesh *em, const char hflag)
493 {
494         int types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, BM_FACES_OF_MESH};
495         BMIter iter;
496         BMHeader *ele;
497         int i;
498
499         if (hflag & BM_SELECT)
500                 BM_clear_selection_history(em->bm);
501
502         for (i=0; i<3; i++) {
503                 BM_ITER(ele, &iter, em->bm, types[i], NULL) {
504                         if (hflag & BM_SELECT) BM_Select(em->bm, ele, 0);
505                         BM_ClearHFlag(ele, hflag);
506                 }
507         }
508 }
509
510 void EDBM_set_flag_all(BMEditMesh *em, const char hflag)
511 {
512         int types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, BM_FACES_OF_MESH};
513         BMIter iter;
514         BMHeader *ele;
515         int i;
516
517         for (i=0; i<3; i++) {
518                 ele= BMIter_New(&iter, em->bm, types[i], NULL);
519                 for ( ; ele; ele=BMIter_Step(&iter)) {
520                         if (hflag & BM_SELECT) {
521                                 BM_Select(em->bm, ele, 1);
522                         }
523                         else {
524                                 BM_SetHFlag(ele, hflag);
525                         }
526                 }
527         }
528 }
529
530 /**************-------------- Undo ------------*****************/
531
532 /* for callbacks */
533
534 static void *getEditMesh(bContext *C)
535 {
536         Object *obedit= CTX_data_edit_object(C);
537         if(obedit && obedit->type==OB_MESH) {
538                 Mesh *me= obedit->data;
539                 return me->edit_btmesh;
540         }
541         return NULL;
542 }
543
544 typedef struct undomesh {
545         Mesh me;
546         int selectmode;
547         char obname[64];
548 } undomesh;
549
550 /*undo simply makes copies of a bmesh*/
551 static void *editbtMesh_to_undoMesh(void *emv, void *obdata)
552 {
553         BMEditMesh *em = emv;
554         Mesh *obme = obdata;
555         
556         undomesh *me = MEM_callocN(sizeof(undomesh), "undo Mesh");
557         strcpy(me->obname, em->bm->ob->id.name+2);
558         
559         /*make sure shape keys work*/
560         me->me.key = obme->key ? copy_key_nolib(obme->key) : NULL;
561
562         /*we recalc the tesselation here, to avoid seeding calls to
563           BMEdit_RecalcTesselation throughout the code.*/
564         BMEdit_RecalcTesselation(em);
565
566         BMO_CallOpf(em->bm, "bmesh_to_mesh mesh=%p notesselation=%i", me, 1);
567         me->selectmode = em->selectmode;
568
569         return me;
570 }
571
572 static void undoMesh_to_editbtMesh(void *umv, void *emv, void *UNUSED(obdata))
573 {
574         BMEditMesh *em = emv, *em2;
575         Object *ob;
576         undomesh *me = umv;
577         BMesh *bm;
578         int allocsize[4] = {512, 512, 2048, 512};
579         
580         ob = (Object*)find_id("OB", me->obname);
581         ob->shapenr = em->bm->shapenr;
582
583         BMEdit_Free(em);
584
585         bm = BM_Make_Mesh(ob, allocsize);
586         BMO_CallOpf(bm, "mesh_to_bmesh mesh=%p object=%p set_shapekey=%i", me, ob, 0);
587
588         em2 = BMEdit_Create(bm);
589         *em = *em2;
590         
591         em->selectmode = me->selectmode;
592
593         MEM_freeN(em2);
594 }
595
596
597 static void free_undo(void *umv)
598 {
599         if (((Mesh*)umv)->key)
600         {
601                 free_key(((Mesh*)umv)->key);
602                 MEM_freeN(((Mesh*)umv)->key);
603         }
604         
605         free_mesh(umv, 0);
606         MEM_freeN(umv);
607 }
608
609 /* and this is all the undo system needs to know */
610 void undo_push_mesh(bContext *C, const char *name)
611 {
612         undo_editmode_push(C, name, getEditMesh, free_undo, undoMesh_to_editbtMesh, editbtMesh_to_undoMesh, NULL);
613 }
614
615 /*write comment here*/
616 UvVertMap *EDBM_make_uv_vert_map(BMEditMesh *em, int selected, int do_face_idx_array, float *limit)
617 {
618         BMVert *ev;
619         BMFace *efa;
620         BMLoop *l;
621         BMIter iter, liter;
622         /* vars from original func */
623         UvVertMap *vmap;
624         UvMapVert *buf;
625         /* MTexPoly *tf; */ /* UNUSED */
626         MLoopUV *luv;
627         unsigned int a;
628         int totverts, i, totuv;
629         
630         if (do_face_idx_array)
631                 EDBM_init_index_arrays(em, 0, 0, 1);
632
633         /* BMESH_TODO this should be valid now, leaving here until we can ensure this - campbell */
634         /* we need the vert */
635         totverts=0;
636         BM_ITER(ev, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
637                 BM_SetIndex(ev, totverts);
638                 totverts++;
639         }
640         
641         totuv = 0;
642
643         /* generate UvMapVert array */
644         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
645                 if(!selected || ((!BM_TestHFlag(efa, BM_HIDDEN)) && BM_TestHFlag(efa, BM_SELECT)))
646                         totuv += efa->len;
647         }
648
649         if(totuv==0) {
650                 if (do_face_idx_array)
651                         EDBM_free_index_arrays(em);
652                 return NULL;
653         }
654         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
655         if (!vmap) {
656                 if (do_face_idx_array)
657                         EDBM_free_index_arrays(em);
658                 return NULL;
659         }
660
661         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totverts, "UvMapVert*");
662         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
663
664         if (!vmap->vert || !vmap->buf) {
665                 free_uv_vert_map(vmap);
666                 if (do_face_idx_array)
667                         EDBM_free_index_arrays(em);
668                 return NULL;
669         }
670         
671         a = 0;
672         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
673                 if(!selected || ((!BM_TestHFlag(efa, BM_HIDDEN)) && BM_TestHFlag(efa, BM_SELECT))) {
674                         i = 0;
675                         BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, efa) {
676                                 buf->tfindex= i;
677                                 buf->f= a;
678                                 buf->separate = 0;
679                                 
680                                 buf->next= vmap->vert[BM_GetIndex(l->v)];
681                                 vmap->vert[BM_GetIndex(l->v)]= buf;
682                                 
683                                 buf++;
684                                 i++;
685                         }
686                 }
687
688                 a++;
689         }
690         
691         /* sort individual uvs for each vert */
692         a = 0;
693         BM_ITER(ev, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
694                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
695                 UvMapVert *iterv, *v, *lastv, *next;
696                 float *uv, *uv2, uvdiff[2];
697
698                 while(vlist) {
699                         v= vlist;
700                         vlist= vlist->next;
701                         v->next= newvlist;
702                         newvlist= v;
703
704                         efa = EDBM_get_face_for_index(em, v->f);
705                         /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
706                         
707                         l = BMIter_AtIndex(em->bm, BM_LOOPS_OF_FACE, efa, v->tfindex);
708                         luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
709                         uv = luv->uv; 
710                         
711                         lastv= NULL;
712                         iterv= vlist;
713
714                         while(iterv) {
715                                 next= iterv->next;
716                                 efa = EDBM_get_face_for_index(em, iterv->f);
717                                 /* tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
718                                 
719                                 l = BMIter_AtIndex(em->bm, BM_LOOPS_OF_FACE, efa, iterv->tfindex);
720                                 luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
721                                 uv2 = luv->uv; 
722                                 
723                                 sub_v2_v2v2(uvdiff, uv2, uv);
724
725                                 if(fabs(uv[0]-uv2[0]) < limit[0] && fabs(uv[1]-uv2[1]) < limit[1]) {
726                                         if(lastv) lastv->next= next;
727                                         else vlist= next;
728                                         iterv->next= newvlist;
729                                         newvlist= iterv;
730                                 }
731                                 else
732                                         lastv=iterv;
733
734                                 iterv= next;
735                         }
736
737                         newvlist->separate = 1;
738                 }
739
740                 vmap->vert[a]= newvlist;
741                 a++;
742         }
743         
744         if (do_face_idx_array)
745                 EDBM_free_index_arrays(em);
746         
747         return vmap;
748 }
749
750
751 UvMapVert *EDBM_get_uv_map_vert(UvVertMap *vmap, unsigned int v)
752 {
753         return vmap->vert[v];
754 }
755
756 void EDBM_free_uv_vert_map(UvVertMap *vmap)
757 {
758         if (vmap) {
759                 if (vmap->vert) MEM_freeN(vmap->vert);
760                 if (vmap->buf) MEM_freeN(vmap->buf);
761                 MEM_freeN(vmap);
762         }
763 }
764
765
766 /* last_sel, use em->act_face otherwise get the last selected face in the editselections
767  * at the moment, last_sel is mainly useful for gaking sure the space image dosnt flicker */
768 MTexPoly *EDBM_get_active_mtexpoly(BMEditMesh *em, BMFace **act_efa, int sloppy)
769 {
770         BMFace *efa = NULL;
771         
772         if(!EDBM_texFaceCheck(em))
773                 return NULL;
774         
775         efa = BM_get_actFace(em->bm, sloppy);
776         
777         if (efa) {
778                 if (act_efa) *act_efa = efa; 
779                 return CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY);
780         }
781
782         if (act_efa) *act_efa= NULL;
783         return NULL;
784 }
785
786 /* can we edit UV's for this mesh?*/
787 int EDBM_texFaceCheck(BMEditMesh *em)
788 {
789         /* some of these checks could be a touch overkill */
790         return em && em->bm->totface && CustomData_has_layer(&em->bm->pdata, CD_MTEXPOLY) &&
791                    CustomData_has_layer(&em->bm->ldata, CD_MLOOPUV);
792 }
793
794 int EDBM_vertColorCheck(BMEditMesh *em)
795 {
796         /* some of these checks could be a touch overkill */
797         return em && em->bm->totface && CustomData_has_layer(&em->bm->ldata, CD_MLOOPCOL);
798 }
799
800 /* BM_SEARCH_MAXDIST is too big, copied from 2.6x MOC_THRESH, should become a
801  * preference */
802 #define BM_SEARCH_MAXDIST_MIRR 0.00002f
803 #define BM_CD_LAYER_ID "__mirror_index"
804 void EDBM_CacheMirrorVerts(BMEditMesh *em, const short use_select)
805 {
806         Mesh *me = em->me;
807         BMBVHTree *tree = BMBVH_NewBVH(em, 0, NULL, NULL);
808         BMIter iter;
809         BMVert *v;
810         float invmat[4][4];
811         int li, i, topo = 0;
812
813         if (me && (me->editflag & ME_EDIT_MIRROR_TOPO)) {
814                 topo = 1;
815         }
816
817         if (!em->vert_index) {
818                 EDBM_init_index_arrays(em, 1, 0, 0);
819                 em->mirr_free_arrays = 1;
820         }
821
822         if (!CustomData_get_layer_named(&em->bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID)) {
823                 BM_add_data_layer_named(em->bm, &em->bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID);
824         }
825
826         li= CustomData_get_named_layer_index(&em->bm->vdata, CD_PROP_INT, BM_CD_LAYER_ID);
827
828         em->bm->vdata.layers[li].flag |= CD_FLAG_TEMPORARY;
829
830         /* BMESH_TODO, we should STOP overwriting the vertex index data with bad
831          * indicies, once createTransEditVerts() stops doing this, this loop can be
832          * removed - campbell */
833         i= 0;
834         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
835                 BM_SetIndex(v, i++);
836         }
837         /* END BMESH_TODO */
838
839
840         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
841                 BMVert *mirr;
842                 int *idx = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, li);
843                 float co[3] = {-v->co[0], v->co[1], v->co[2]};
844
845                 //temporary for testing, check for selection
846                 if (use_select && !BM_TestHFlag(v, BM_SELECT))
847                         continue;
848                 
849                 mirr = topo ?
850                         BMBVH_FindClosestVertTopo(tree, co, BM_SEARCH_MAXDIST_MIRR, v) :
851                         BMBVH_FindClosestVert(tree, co, BM_SEARCH_MAXDIST_MIRR);
852
853                 if (mirr && mirr != v) {
854                         *idx = BM_GetIndex(mirr);
855                         idx = CustomData_bmesh_get_layer_n(&em->bm->vdata,mirr->head.data, li);
856                         *idx = BM_GetIndex(v);
857                 }
858                 else {
859                         *idx = -1;
860                 }
861         }
862
863         BMBVH_FreeBVH(tree);
864
865         em->mirror_cdlayer= li;
866 }
867
868 BMVert *EDBM_GetMirrorVert(BMEditMesh *em, BMVert *v)
869 {
870         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
871
872         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
873
874         if (mirr && *mirr >=0 && *mirr < em->bm->totvert) {
875                 if (!em->vert_index) {
876                         printf("err: should only be called between "
877                                 "EDBM_CacheMirrorVerts and EDBM_EndMirrorCache");
878                         return NULL;
879                 }
880
881                 return em->vert_index[*mirr];
882         }
883
884         return NULL;
885 }
886
887 void EDBM_ClearMirrorVert(BMEditMesh *em, BMVert *v)
888 {
889         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
890
891         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
892
893         if (mirr) {
894                 *mirr= -1;
895         }
896 }
897
898 void EDBM_EndMirrorCache(BMEditMesh *em)
899 {
900         if (em->mirr_free_arrays) {
901                 MEM_freeN(em->vert_index);
902                 em->vert_index = NULL;
903         }
904
905         em->mirror_cdlayer= -1;
906 }
907
908 void EDBM_ApplyMirrorCache(BMEditMesh *em, const int sel_from, const int sel_to)
909 {
910         BMIter iter;
911         BMVert *v;
912
913         BLI_assert(em->vert_index != NULL);
914
915         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
916                 if (BM_TestHFlag(v, BM_SELECT) == sel_from) {
917                         BMVert *mirr= EDBM_GetMirrorVert(em, v);
918                         if (mirr) {
919                                 if (BM_TestHFlag(mirr, BM_SELECT) == sel_to) {
920                                         copy_v3_v3(mirr->co, v->co);
921                                         mirr->co[0] *= -1.0f;
922                                 }
923                         }
924                 }
925         }
926 }