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