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