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