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