9cf80c8f4cf7c84837c1232412cdf582cf867e6b
[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_key_types.h"
37
38 #include "BLI_math.h"
39 #include "BLI_alloca.h"
40 #include "BLI_buffer.h"
41 #include "BLI_kdtree.h"
42 #include "BLI_listbase.h"
43
44 #include "BKE_DerivedMesh.h"
45 #include "BKE_context.h"
46 #include "BKE_global.h"
47 #include "BKE_depsgraph.h"
48 #include "BKE_key.h"
49 #include "BKE_main.h"
50 #include "BKE_mesh.h"
51 #include "BKE_mesh_mapping.h"
52 #include "BKE_report.h"
53 #include "BKE_editmesh.h"
54 #include "BKE_editmesh_bvh.h"
55
56 #include "BKE_object.h"  /* XXX. only for EDBM_mesh_ensure_valid_dm_hack() which will be removed */
57
58 #include "WM_api.h"
59 #include "WM_types.h"
60
61 #include "ED_mesh.h"
62 #include "ED_screen.h"
63 #include "ED_util.h"
64 #include "ED_view3d.h"
65
66 #include "mesh_intern.h"  /* own include */
67
68 /* mesh backup implementation. This would greatly benefit from some sort of binary diffing
69  * just as the undo stack would. So leaving this as an interface for further work */
70
71 BMBackup EDBM_redo_state_store(BMEditMesh *em)
72 {
73         BMBackup backup;
74         backup.bmcopy = BM_mesh_copy(em->bm);
75         return backup;
76 }
77
78 void EDBM_redo_state_restore(BMBackup backup, BMEditMesh *em, int recalctess)
79 {
80         BMesh *tmpbm;
81         if (!em || !backup.bmcopy)
82                 return;
83
84         BM_mesh_data_free(em->bm);
85         tmpbm = BM_mesh_copy(backup.bmcopy);
86         *em->bm = *tmpbm;
87         MEM_freeN(tmpbm);
88         tmpbm = NULL;
89
90         if (recalctess)
91                 BKE_editmesh_tessface_calc(em);
92 }
93
94 void EDBM_redo_state_free(BMBackup *backup, BMEditMesh *em, int recalctess)
95 {
96         if (em && backup->bmcopy) {
97                 BM_mesh_data_free(em->bm);
98                 *em->bm = *backup->bmcopy;
99         }
100         else if (backup->bmcopy) {
101                 BM_mesh_data_free(backup->bmcopy);
102         }
103
104         if (backup->bmcopy)
105                 MEM_freeN(backup->bmcopy);
106         backup->bmcopy = NULL;
107
108         if (recalctess && em)
109                 BKE_editmesh_tessface_calc(em);
110 }
111
112 /* hack to workaround multiple operators being called within the same event loop without an update
113  * see: [#31811] */
114 void EDBM_mesh_ensure_valid_dm_hack(Scene *scene, BMEditMesh *em)
115 {
116         if ((((ID *)em->ob->data)->tag & LIB_TAG_ID_RECALC) ||
117             (em->ob->recalc & OB_RECALC_DATA))
118         {
119                 /* since we may not have done selection flushing */
120                 if ((em->ob->recalc & OB_RECALC_DATA) == 0) {
121                         DAG_id_tag_update(&em->ob->id, OB_RECALC_DATA);
122                 }
123                 BKE_object_handle_update(G.main->eval_ctx, scene, em->ob);
124         }
125 }
126
127 void EDBM_mesh_normals_update(BMEditMesh *em)
128 {
129         BM_mesh_normals_update(em->bm);
130 }
131
132 void EDBM_mesh_clear(BMEditMesh *em)
133 {
134         /* clear bmesh */
135         BM_mesh_clear(em->bm);
136         
137         /* free derived meshes */
138         BKE_editmesh_free_derivedmesh(em);
139         
140         /* free tessellation data */
141         em->tottri = 0;
142         if (em->looptris) {
143                 MEM_freeN(em->looptris);
144                 em->looptris = NULL;
145         }
146 }
147
148 void EDBM_stats_update(BMEditMesh *em)
149 {
150         const char iter_types[3] = {BM_VERTS_OF_MESH,
151                                     BM_EDGES_OF_MESH,
152                                     BM_FACES_OF_MESH};
153
154         BMIter iter;
155         BMElem *ele;
156         int *tots[3];
157         int i;
158
159         tots[0] = &em->bm->totvertsel;
160         tots[1] = &em->bm->totedgesel;
161         tots[2] = &em->bm->totfacesel;
162         
163         em->bm->totvertsel = em->bm->totedgesel = em->bm->totfacesel = 0;
164
165         for (i = 0; i < 3; i++) {
166                 ele = BM_iter_new(&iter, em->bm, iter_types[i], NULL);
167                 for ( ; ele; ele = BM_iter_step(&iter)) {
168                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
169                                 (*tots[i])++;
170                         }
171                 }
172         }
173 }
174
175 DerivedMesh *EDBM_mesh_deform_dm_get(BMEditMesh *em)
176 {
177         return ((em->derivedFinal != NULL) &&
178                 (em->derivedFinal->type == DM_TYPE_EDITBMESH) &&
179                 (em->derivedFinal->deformedOnly != false)) ? em->derivedFinal : NULL;
180 }
181
182 bool EDBM_op_init(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const char *fmt, ...)
183 {
184         BMesh *bm = em->bm;
185         va_list list;
186
187         va_start(list, fmt);
188
189         if (!BMO_op_vinitf(bm, bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
190                 BKE_reportf(op->reports, RPT_ERROR, "Parse error in %s", __func__);
191                 va_end(list);
192                 return false;
193         }
194         
195         if (!em->emcopy)
196                 em->emcopy = BKE_editmesh_copy(em);
197         em->emcopyusers++;
198
199         va_end(list);
200
201         return true;
202 }
203
204
205 /* returns 0 on error, 1 on success.  executes and finishes a bmesh operator */
206 bool EDBM_op_finish(BMEditMesh *em, BMOperator *bmop, wmOperator *op, const bool do_report)
207 {
208         const char *errmsg;
209         
210         BMO_op_finish(em->bm, bmop);
211
212         if (BMO_error_get(em->bm, &errmsg, NULL)) {
213                 BMEditMesh *emcopy = em->emcopy;
214
215                 if (do_report) {
216                         BKE_report(op->reports, RPT_ERROR, errmsg);
217                 }
218
219                 EDBM_mesh_free(em);
220                 *em = *emcopy;
221
222                 MEM_freeN(emcopy);
223                 em->emcopyusers = 0;
224                 em->emcopy = NULL;
225
226                 /* when copying, tessellation isn't to for faster copying,
227                  * but means we need to re-tessellate here */
228                 if (em->looptris == NULL) {
229                         BKE_editmesh_tessface_calc(em);
230                 }
231
232                 return false;
233         }
234         else {
235                 em->emcopyusers--;
236                 if (em->emcopyusers < 0) {
237                         printf("warning: em->emcopyusers was less than zero.\n");
238                 }
239
240                 if (em->emcopyusers <= 0) {
241                         BKE_editmesh_free(em->emcopy);
242                         MEM_freeN(em->emcopy);
243                         em->emcopy = NULL;
244                 }
245
246                 return true;
247         }
248 }
249
250 bool EDBM_op_callf(BMEditMesh *em, wmOperator *op, const char *fmt, ...)
251 {
252         BMesh *bm = em->bm;
253         BMOperator bmop;
254         va_list list;
255
256         va_start(list, fmt);
257
258         if (!BMO_op_vinitf(bm, &bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
259                 BKE_reportf(op->reports, RPT_ERROR, "Parse error in %s", __func__);
260                 va_end(list);
261                 return false;
262         }
263
264         if (!em->emcopy)
265                 em->emcopy = BKE_editmesh_copy(em);
266         em->emcopyusers++;
267
268         BMO_op_exec(bm, &bmop);
269
270         va_end(list);
271         return EDBM_op_finish(em, &bmop, op, true);
272 }
273
274 bool EDBM_op_call_and_selectf(BMEditMesh *em, wmOperator *op,
275                               const char *select_slot_out, const bool select_extend,
276                               const char *fmt, ...)
277 {
278         BMOpSlot *slot_select_out;
279         BMesh *bm = em->bm;
280         BMOperator bmop;
281         va_list list;
282         char hflag;
283
284         va_start(list, fmt);
285
286         if (!BMO_op_vinitf(bm, &bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
287                 BKE_reportf(op->reports, RPT_ERROR, "Parse error in %s", __func__);
288                 va_end(list);
289                 return false;
290         }
291
292         if (!em->emcopy)
293                 em->emcopy = BKE_editmesh_copy(em);
294         em->emcopyusers++;
295
296         BMO_op_exec(bm, &bmop);
297
298         slot_select_out = BMO_slot_get(bmop.slots_out, select_slot_out);
299         hflag = slot_select_out->slot_subtype.elem & BM_ALL_NOLOOP;
300         BLI_assert(hflag != 0);
301
302         if (select_extend == false) {
303                 BM_mesh_elem_hflag_disable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_SELECT, false);
304         }
305
306         BMO_slot_buffer_hflag_enable(em->bm, bmop.slots_out, select_slot_out, hflag, BM_ELEM_SELECT, true);
307
308         va_end(list);
309         return EDBM_op_finish(em, &bmop, op, true);
310 }
311
312 bool EDBM_op_call_silentf(BMEditMesh *em, const char *fmt, ...)
313 {
314         BMesh *bm = em->bm;
315         BMOperator bmop;
316         va_list list;
317
318         va_start(list, fmt);
319
320         if (!BMO_op_vinitf(bm, &bmop, BMO_FLAG_DEFAULTS, fmt, list)) {
321                 va_end(list);
322                 return false;
323         }
324
325         if (!em->emcopy)
326                 em->emcopy = BKE_editmesh_copy(em);
327         em->emcopyusers++;
328
329         BMO_op_exec(bm, &bmop);
330
331         va_end(list);
332         return EDBM_op_finish(em, &bmop, NULL, false);
333 }
334
335 void EDBM_selectmode_to_scene(bContext *C)
336 {
337         Scene *scene = CTX_data_scene(C);
338         Object *obedit = CTX_data_edit_object(C);
339         BMEditMesh *em = BKE_editmesh_from_object(obedit);
340
341         if (!em)
342                 return;
343
344         scene->toolsettings->selectmode = em->selectmode;
345
346         /* Request redraw of header buttons (to show new select mode) */
347         WM_event_add_notifier(C, NC_SCENE | ND_TOOLSETTINGS, scene);
348 }
349
350 void EDBM_mesh_make(ToolSettings *ts, Object *ob)
351 {
352         Mesh *me = ob->data;
353         BMesh *bm;
354
355         if (UNLIKELY(!me->mpoly && me->totface)) {
356                 BKE_mesh_convert_mfaces_to_mpolys(me);
357         }
358
359         bm = BKE_mesh_to_bmesh(me, ob);
360
361         if (me->edit_btmesh) {
362                 /* this happens when switching shape keys */
363                 EDBM_mesh_free(me->edit_btmesh);
364                 MEM_freeN(me->edit_btmesh);
365         }
366
367         /* currently executing operators re-tessellates, so we can avoid doing here
368          * but at some point it may need to be added back. */
369 #if 0
370         me->edit_btmesh = BKE_editmesh_create(bm, true);
371 #else
372         me->edit_btmesh = BKE_editmesh_create(bm, false);
373 #endif
374
375         me->edit_btmesh->selectmode = me->edit_btmesh->bm->selectmode = ts->selectmode;
376         me->edit_btmesh->mat_nr = (ob->actcol > 0) ? ob->actcol - 1 : 0;
377         me->edit_btmesh->ob = ob;
378
379         /* we need to flush selection because the mode may have changed from when last in editmode */
380         EDBM_selectmode_flush(me->edit_btmesh);
381 }
382
383 /**
384  * \warning This can invalidate the #DerivedMesh cache of other objects (for linked duplicates).
385  * Most callers should run #DAG_id_tag_update on \a ob->data, see: T46738, T46913
386  */
387 void EDBM_mesh_load(Object *ob)
388 {
389         Mesh *me = ob->data;
390         BMesh *bm = me->edit_btmesh->bm;
391
392         /* Workaround for T42360, 'ob->shapenr' should be 1 in this case.
393          * however this isn't synchronized between objects at the moment. */
394         if (UNLIKELY((ob->shapenr == 0) && (me->key && !BLI_listbase_is_empty(&me->key->block)))) {
395                 bm->shapenr = 1;
396         }
397
398         BM_mesh_bm_to_me(bm, me, false);
399
400 #ifdef USE_TESSFACE_DEFAULT
401         BKE_mesh_tessface_calc(me);
402 #endif
403
404         /* free derived mesh. usually this would happen through depsgraph but there
405          * are exceptions like file save that will not cause this, and we want to
406          * avoid ending up with an invalid derived mesh then */
407         BKE_object_free_derived_caches(ob);
408 }
409
410 /**
411  * Should only be called on the active editmesh, otherwise call #BKE_editmesh_free
412  */
413 void EDBM_mesh_free(BMEditMesh *em)
414 {
415         /* These tables aren't used yet, so it's not strictly necessary
416          * to 'end' them (with 'e' param) but if someone tries to start
417          * using them, having these in place will save a lot of pain */
418         ED_mesh_mirror_spatial_table(NULL, NULL, NULL, 'e');
419         ED_mesh_mirror_topo_table(NULL, 'e');
420
421         BKE_editmesh_free(em);
422 }
423
424 void EDBM_selectmode_flush_ex(BMEditMesh *em, const short selectmode)
425 {
426         BM_mesh_select_mode_flush_ex(em->bm, selectmode);
427 }
428
429 void EDBM_selectmode_flush(BMEditMesh *em)
430 {
431         EDBM_selectmode_flush_ex(em, em->selectmode);
432 }
433
434 void EDBM_deselect_flush(BMEditMesh *em)
435 {
436         /* function below doesnt use. just do this to keep the values in sync */
437         em->bm->selectmode = em->selectmode;
438         BM_mesh_deselect_flush(em->bm);
439 }
440
441
442 void EDBM_select_flush(BMEditMesh *em)
443 {
444         /* function below doesnt use. just do this to keep the values in sync */
445         em->bm->selectmode = em->selectmode;
446         BM_mesh_select_flush(em->bm);
447 }
448
449 void EDBM_select_more(BMEditMesh *em, const bool use_face_step)
450 {
451         BMOperator bmop;
452         const bool use_faces = (em->selectmode == SCE_SELECT_FACE);
453
454         BMO_op_initf(em->bm, &bmop, BMO_FLAG_DEFAULTS,
455                      "region_extend geom=%hvef use_contract=%b use_faces=%b use_face_step=%b",
456                      BM_ELEM_SELECT, false, use_faces, use_face_step);
457         BMO_op_exec(em->bm, &bmop);
458         /* don't flush selection in edge/vertex mode  */
459         BMO_slot_buffer_hflag_enable(em->bm, bmop.slots_out, "geom.out", BM_ALL_NOLOOP, BM_ELEM_SELECT, use_faces ? true : false);
460         BMO_op_finish(em->bm, &bmop);
461
462         EDBM_selectmode_flush(em);
463 }
464
465 void EDBM_select_less(BMEditMesh *em, const bool use_face_step)
466 {
467         BMOperator bmop;
468         const bool use_faces = (em->selectmode == SCE_SELECT_FACE);
469
470         BMO_op_initf(em->bm, &bmop, BMO_FLAG_DEFAULTS,
471                      "region_extend geom=%hvef use_contract=%b use_faces=%b use_face_step=%b",
472                      BM_ELEM_SELECT, true, use_faces, use_face_step);
473         BMO_op_exec(em->bm, &bmop);
474         /* don't flush selection in edge/vertex mode  */
475         BMO_slot_buffer_hflag_disable(em->bm, bmop.slots_out, "geom.out", BM_ALL_NOLOOP, BM_ELEM_SELECT, use_faces ? true : false);
476         BMO_op_finish(em->bm, &bmop);
477
478         EDBM_selectmode_flush(em);
479 }
480
481 void EDBM_flag_disable_all(BMEditMesh *em, const char hflag)
482 {
483         BM_mesh_elem_hflag_disable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, hflag, false);
484 }
485
486 void EDBM_flag_enable_all(BMEditMesh *em, const char hflag)
487 {
488         BM_mesh_elem_hflag_enable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, hflag, true);
489 }
490
491 /**************-------------- Undo ------------*****************/
492
493 /* for callbacks */
494
495 static void *getEditMesh(bContext *C)
496 {
497         Object *obedit = CTX_data_edit_object(C);
498         if (obedit && obedit->type == OB_MESH) {
499                 Mesh *me = obedit->data;
500                 return me->edit_btmesh;
501         }
502         return NULL;
503 }
504
505 typedef struct UndoMesh {
506         Mesh me;
507         int selectmode;
508
509         /** \note
510          * this isn't a prefect solution, if you edit keys and change shapes this works well (fixing [#32442]),
511          * but editing shape keys, going into object mode, removing or changing their order,
512          * then go back into editmode and undo will give issues - where the old index will be out of sync
513          * with the new object index.
514          *
515          * There are a few ways this could be made to work but for now its a known limitation with mixing
516          * object and editmode operations - Campbell */
517         int shapenr;
518 } UndoMesh;
519
520 /* undo simply makes copies of a bmesh */
521 static void *editbtMesh_to_undoMesh(void *emv, void *obdata)
522 {
523         BMEditMesh *em = emv;
524         Mesh *obme = obdata;
525         
526         UndoMesh *um = MEM_callocN(sizeof(UndoMesh), "undo Mesh");
527         
528         /* make sure shape keys work */
529         um->me.key = obme->key ? BKE_key_copy_nolib(obme->key) : NULL;
530
531         /* BM_mesh_validate(em->bm); */ /* for troubleshooting */
532
533         BM_mesh_bm_to_me(em->bm, &um->me, false);
534
535         um->selectmode = em->selectmode;
536         um->shapenr = em->bm->shapenr;
537
538         return um;
539 }
540
541 static void undoMesh_to_editbtMesh(void *umv, void *em_v, void *obdata)
542 {
543         BMEditMesh *em = em_v, *em_tmp;
544         Object *ob = em->ob;
545         UndoMesh *um = umv;
546         BMesh *bm;
547         Key *key = ((Mesh *) obdata)->key;
548
549         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(&um->me);
550
551         em->bm->shapenr = um->shapenr;
552
553         EDBM_mesh_free(em);
554
555         bm = BM_mesh_create(&allocsize);
556
557         BM_mesh_bm_from_me(bm, &um->me, true, false, um->shapenr);
558
559         em_tmp = BKE_editmesh_create(bm, true);
560         *em = *em_tmp;
561
562         em->selectmode = um->selectmode;
563         bm->selectmode = um->selectmode;
564         em->ob = ob;
565
566         /* T35170: Restore the active key on the RealMesh. Otherwise 'fake' offset propagation happens
567          *         if the active is a basis for any other. */
568         if (key && (key->type == KEY_RELATIVE)) {
569                 /* Since we can't add, remove or reorder keyblocks in editmode, it's safe to assume
570                  * shapenr from restored bmesh and keyblock indices are in sync. */
571                 const int kb_act_idx = ob->shapenr - 1;
572
573                 /* If it is, let's patch the current mesh key block to its restored value.
574                  * Else, the offsets won't be computed and it won't matter. */
575                 if (BKE_keyblock_is_basis(key, kb_act_idx)) {
576                         KeyBlock *kb_act = BLI_findlink(&key->block, kb_act_idx);
577
578                         if (kb_act->totelem != um->me.totvert) {
579                                 /* The current mesh has some extra/missing verts compared to the undo, adjust. */
580                                 MEM_SAFE_FREE(kb_act->data);
581                                 kb_act->data = MEM_mallocN((size_t)(key->elemsize * bm->totvert), __func__);
582                                 kb_act->totelem = um->me.totvert;
583                         }
584
585                         BKE_keyblock_update_from_mesh(&um->me, kb_act);
586                 }
587         }
588
589         ob->shapenr = um->shapenr;
590
591         MEM_freeN(em_tmp);
592 }
593
594 static void free_undo(void *me_v)
595 {
596         Mesh *me = me_v;
597         if (me->key) {
598                 BKE_key_free(me->key);
599                 MEM_freeN(me->key);
600         }
601
602         BKE_mesh_free(me, false);
603         MEM_freeN(me);
604 }
605
606 /* and this is all the undo system needs to know */
607 void undo_push_mesh(bContext *C, const char *name)
608 {
609         /* em->ob gets out of date and crashes on mesh undo,
610          * this is an easy way to ensure its OK
611          * though we could investigate the matter further. */
612         Object *obedit = CTX_data_edit_object(C);
613         BMEditMesh *em = BKE_editmesh_from_object(obedit);
614         em->ob = obedit;
615
616         undo_editmode_push(C, name, getEditMesh, free_undo, undoMesh_to_editbtMesh, editbtMesh_to_undoMesh, NULL);
617 }
618
619 /**
620  * Return a new UVVertMap from the editmesh
621  */
622 UvVertMap *BM_uv_vert_map_create(
623         BMesh *bm,
624         const float limit[2], const bool use_select, const bool use_winding)
625 {
626         BMVert *ev;
627         BMFace *efa;
628         BMLoop *l;
629         BMIter iter, liter;
630         /* vars from original func */
631         UvVertMap *vmap;
632         UvMapVert *buf;
633         /* MTexPoly *tf; */ /* UNUSED */
634         MLoopUV *luv;
635         unsigned int a;
636         int totverts, i, totuv, totfaces;
637         const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV);
638         bool *winding = NULL;
639         BLI_buffer_declare_static(vec2f, tf_uv_buf, BLI_BUFFER_NOP, BM_DEFAULT_NGON_STACK_SIZE);
640
641         BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE);
642         
643         totfaces = bm->totface;
644         totverts = bm->totvert;
645         totuv = 0;
646
647         /* generate UvMapVert array */
648         BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
649                 if ((use_select == false) || BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
650                         totuv += efa->len;
651                 }
652         }
653
654         if (totuv == 0) {
655                 return NULL;
656         }
657         vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
658         if (!vmap) {
659                 return NULL;
660         }
661
662         vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totverts, "UvMapVert_pt");
663         buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert");
664         if (use_winding) {
665                 winding = MEM_callocN(sizeof(*winding) * totfaces, "winding");
666         }
667
668         if (!vmap->vert || !vmap->buf) {
669                 BKE_mesh_uv_vert_map_free(vmap);
670                 return NULL;
671         }
672         
673         BM_ITER_MESH_INDEX (efa, &iter, bm, BM_FACES_OF_MESH, a) {
674                 if ((use_select == false) || BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
675                         float (*tf_uv)[2];
676
677                         if (use_winding) {
678                                 tf_uv = (float (*)[2])BLI_buffer_reinit_data(&tf_uv_buf, vec2f, efa->len);
679                         }
680
681                         BM_ITER_ELEM_INDEX(l, &liter, efa, BM_LOOPS_OF_FACE, i) {
682                                 buf->tfindex = i;
683                                 buf->f = a;
684                                 buf->separate = 0;
685                                 
686                                 buf->next = vmap->vert[BM_elem_index_get(l->v)];
687                                 vmap->vert[BM_elem_index_get(l->v)] = buf;
688                                 buf++;
689
690                                 if (use_winding) {
691                                         luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
692                                         copy_v2_v2(tf_uv[i], luv->uv);
693                                 }
694                         }
695
696                         if (use_winding) {
697                                 winding[a] = cross_poly_v2((const float (*)[2])tf_uv, efa->len) > 0;
698                         }
699                 }
700         }
701         
702         /* sort individual uvs for each vert */
703         BM_ITER_MESH_INDEX (ev, &iter, bm, BM_VERTS_OF_MESH, a) {
704                 UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
705                 UvMapVert *iterv, *v, *lastv, *next;
706                 float *uv, *uv2, uvdiff[2];
707
708                 while (vlist) {
709                         v = vlist;
710                         vlist = vlist->next;
711                         v->next = newvlist;
712                         newvlist = v;
713
714                         efa = BM_face_at_index(bm, v->f);
715                         /* tf = CustomData_bmesh_get(&bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
716                         
717                         l = BM_iter_at_index(bm, BM_LOOPS_OF_FACE, efa, v->tfindex);
718                         luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
719                         uv = luv->uv;
720                         
721                         lastv = NULL;
722                         iterv = vlist;
723
724                         while (iterv) {
725                                 next = iterv->next;
726                                 efa = BM_face_at_index(bm, iterv->f);
727                                 /* tf = CustomData_bmesh_get(&bm->pdata, efa->head.data, CD_MTEXPOLY); */ /* UNUSED */
728                                 
729                                 l = BM_iter_at_index(bm, BM_LOOPS_OF_FACE, efa, iterv->tfindex);
730                                 luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
731                                 uv2 = luv->uv;
732                                 
733                                 sub_v2_v2v2(uvdiff, uv2, uv);
734
735                                 if (fabsf(uvdiff[0]) < limit[0] && fabsf(uvdiff[1]) < limit[1] &&
736                                     (!use_winding || winding[iterv->f] == winding[v->f]))
737                                 {
738                                         if (lastv) lastv->next = next;
739                                         else vlist = next;
740                                         iterv->next = newvlist;
741                                         newvlist = iterv;
742                                 }
743                                 else {
744                                         lastv = iterv;
745                                 }
746
747                                 iterv = next;
748                         }
749
750                         newvlist->separate = 1;
751                 }
752
753                 vmap->vert[a] = newvlist;
754         }
755
756         if (use_winding) {
757                 MEM_freeN(winding);
758         }
759
760         BLI_buffer_free(&tf_uv_buf);
761
762         return vmap;
763 }
764
765
766 UvMapVert *BM_uv_vert_map_at_index(UvVertMap *vmap, unsigned int v)
767 {
768         return vmap->vert[v];
769 }
770
771
772 /* A specialized vert map used by stitch operator */
773 UvElementMap *BM_uv_element_map_create(
774         BMesh *bm,
775         const bool selected, const bool use_winding, const bool do_islands)
776 {
777         BMVert *ev;
778         BMFace *efa;
779         BMLoop *l;
780         BMIter iter, liter;
781         /* vars from original func */
782         UvElementMap *element_map;
783         UvElement *buf;
784         bool *winding;
785         BLI_buffer_declare_static(vec2f, tf_uv_buf, BLI_BUFFER_NOP, BM_DEFAULT_NGON_STACK_SIZE);
786
787         MLoopUV *luv;
788         int totverts, totfaces, i, totuv, j;
789
790         const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV);
791
792         BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE);
793
794         totfaces = bm->totface;
795         totverts = bm->totvert;
796         totuv = 0;
797
798         /* generate UvElement array */
799         BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
800                 if (!selected || BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
801                         totuv += efa->len;
802                 }
803         }
804
805         if (totuv == 0) {
806                 return NULL;
807         }
808
809         element_map = (UvElementMap *)MEM_callocN(sizeof(*element_map), "UvElementMap");
810         element_map->totalUVs = totuv;
811         element_map->vert = (UvElement **)MEM_callocN(sizeof(*element_map->vert) * totverts, "UvElementVerts");
812         buf = element_map->buf = (UvElement *)MEM_callocN(sizeof(*element_map->buf) * totuv, "UvElement");
813
814         if (use_winding) {
815                 winding = MEM_mallocN(sizeof(*winding) * totfaces, "winding");
816         }
817
818         BM_ITER_MESH_INDEX (efa, &iter, bm, BM_FACES_OF_MESH, j) {
819
820                 if (use_winding) {
821                         winding[j] = false;
822                 }
823
824                 if (!selected || BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
825                         float (*tf_uv)[2];
826
827                         if (use_winding) {
828                                 tf_uv = (float (*)[2])BLI_buffer_reinit_data(&tf_uv_buf, vec2f, efa->len);
829                         }
830
831                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, i) {
832                                 buf->l = l;
833                                 buf->separate = 0;
834                                 buf->island = INVALID_ISLAND;
835                                 buf->tfindex = i;
836
837                                 buf->next = element_map->vert[BM_elem_index_get(l->v)];
838                                 element_map->vert[BM_elem_index_get(l->v)] = buf;
839
840                                 if (use_winding) {
841                                         luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
842                                         copy_v2_v2(tf_uv[i], luv->uv);
843                                 }
844
845                                 buf++;
846                         }
847
848                         if (use_winding) {
849                                 winding[j] = cross_poly_v2((const float (*)[2])tf_uv, efa->len) > 0;
850                         }
851                 }
852         }
853
854         /* sort individual uvs for each vert */
855         BM_ITER_MESH_INDEX (ev, &iter, bm, BM_VERTS_OF_MESH, i) {
856                 UvElement *newvlist = NULL, *vlist = element_map->vert[i];
857                 UvElement *iterv, *v, *lastv, *next;
858                 float *uv, *uv2, uvdiff[2];
859
860                 while (vlist) {
861                         v = vlist;
862                         vlist = vlist->next;
863                         v->next = newvlist;
864                         newvlist = v;
865
866                         l = v->l;
867                         luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
868                         uv = luv->uv;
869
870                         lastv = NULL;
871                         iterv = vlist;
872
873                         while (iterv) {
874                                 next = iterv->next;
875
876                                 l = iterv->l;
877                                 luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
878                                 uv2 = luv->uv;
879
880                                 sub_v2_v2v2(uvdiff, uv2, uv);
881
882                                 if (fabsf(uvdiff[0]) < STD_UV_CONNECT_LIMIT && fabsf(uvdiff[1]) < STD_UV_CONNECT_LIMIT &&
883                                     (!use_winding || winding[BM_elem_index_get(iterv->l->f)] == winding[BM_elem_index_get(v->l->f)]))
884                                 {
885                                         if (lastv) lastv->next = next;
886                                         else vlist = next;
887                                         iterv->next = newvlist;
888                                         newvlist = iterv;
889                                 }
890                                 else {
891                                         lastv = iterv;
892                                 }
893
894                                 iterv = next;
895                         }
896
897                         newvlist->separate = 1;
898                 }
899
900                 element_map->vert[i] = newvlist;
901         }
902
903         if (use_winding) {
904                 MEM_freeN(winding);
905         }
906
907         if (do_islands) {
908                 unsigned int *map;
909                 BMFace **stack;
910                 int stacksize = 0;
911                 UvElement *islandbuf;
912                 /* island number for faces */
913                 int *island_number = NULL;
914
915                 int nislands = 0, islandbufsize = 0;
916
917                 /* map holds the map from current vmap->buf to the new, sorted map */
918                 map = MEM_mallocN(sizeof(*map) * totuv, "uvelement_remap");
919                 stack = MEM_mallocN(sizeof(*stack) * bm->totface, "uv_island_face_stack");
920                 islandbuf = MEM_callocN(sizeof(*islandbuf) * totuv, "uvelement_island_buffer");
921                 island_number = MEM_mallocN(sizeof(*island_number) * totfaces, "uv_island_number_face");
922                 copy_vn_i(island_number, totfaces, INVALID_ISLAND);
923
924                 /* at this point, every UvElement in vert points to a UvElement sharing the same vertex. Now we should sort uv's in islands. */
925                 for (i = 0; i < totuv; i++) {
926                         if (element_map->buf[i].island == INVALID_ISLAND) {
927                                 element_map->buf[i].island = nislands;
928                                 stack[0] = element_map->buf[i].l->f;
929                                 island_number[BM_elem_index_get(stack[0])] = nislands;
930                                 stacksize = 1;
931
932                                 while (stacksize > 0) {
933                                         efa = stack[--stacksize];
934
935                                         BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
936                                                 UvElement *element, *initelement = element_map->vert[BM_elem_index_get(l->v)];
937
938                                                 for (element = initelement; element; element = element->next) {
939                                                         if (element->separate)
940                                                                 initelement = element;
941
942                                                         if (element->l->f == efa) {
943                                                                 /* found the uv corresponding to our face and vertex. Now fill it to the buffer */
944                                                                 element->island = nislands;
945                                                                 map[element - element_map->buf] = islandbufsize;
946                                                                 islandbuf[islandbufsize].l = element->l;
947                                                                 islandbuf[islandbufsize].separate = element->separate;
948                                                                 islandbuf[islandbufsize].tfindex = element->tfindex;
949                                                                 islandbuf[islandbufsize].island =  nislands;
950                                                                 islandbufsize++;
951
952                                                                 for (element = initelement; element; element = element->next) {
953                                                                         if (element->separate && element != initelement)
954                                                                                 break;
955
956                                                                         if (island_number[BM_elem_index_get(element->l->f)] == INVALID_ISLAND) {
957                                                                                 stack[stacksize++] = element->l->f;
958                                                                                 island_number[BM_elem_index_get(element->l->f)] = nislands;
959                                                                         }
960                                                                 }
961                                                                 break;
962                                                         }
963                                                 }
964                                         }
965                                 }
966
967                                 nislands++;
968                         }
969                 }
970
971                 MEM_freeN(island_number);
972
973                 /* remap */
974                 for (i = 0; i < bm->totvert; i++) {
975                         /* important since we may do selection only. Some of these may be NULL */
976                         if (element_map->vert[i])
977                                 element_map->vert[i] = &islandbuf[map[element_map->vert[i] - element_map->buf]];
978                 }
979
980                 element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices) * nislands, "UvElementMap_island_indices");
981                 j = 0;
982                 for (i = 0; i < totuv; i++) {
983                         UvElement *element = element_map->buf[i].next;
984                         if (element == NULL)
985                                 islandbuf[map[i]].next = NULL;
986                         else
987                                 islandbuf[map[i]].next = &islandbuf[map[element - element_map->buf]];
988
989                         if (islandbuf[i].island != j) {
990                                 j++;
991                                 element_map->islandIndices[j] = i;
992                         }
993                 }
994
995                 MEM_freeN(element_map->buf);
996
997                 element_map->buf = islandbuf;
998                 element_map->totalIslands = nislands;
999                 MEM_freeN(stack);
1000                 MEM_freeN(map);
1001         }
1002
1003         BLI_buffer_free(&tf_uv_buf);
1004
1005         return element_map;
1006 }
1007
1008 void BM_uv_vert_map_free(UvVertMap *vmap)
1009 {
1010         if (vmap) {
1011                 if (vmap->vert) MEM_freeN(vmap->vert);
1012                 if (vmap->buf) MEM_freeN(vmap->buf);
1013                 MEM_freeN(vmap);
1014         }
1015 }
1016
1017 void BM_uv_element_map_free(UvElementMap *element_map)
1018 {
1019         if (element_map) {
1020                 if (element_map->vert) MEM_freeN(element_map->vert);
1021                 if (element_map->buf) MEM_freeN(element_map->buf);
1022                 if (element_map->islandIndices) MEM_freeN(element_map->islandIndices);
1023                 MEM_freeN(element_map);
1024         }
1025 }
1026
1027 UvElement *BM_uv_element_get(UvElementMap *map, BMFace *efa, BMLoop *l)
1028 {
1029         UvElement *element;
1030
1031         element = map->vert[BM_elem_index_get(l->v)];
1032
1033         for (; element; element = element->next)
1034                 if (element->l->f == efa)
1035                         return element;
1036
1037         return NULL;
1038 }
1039
1040 /* last_sel, use em->act_face otherwise get the last selected face in the editselections
1041  * at the moment, last_sel is mainly useful for making sure the space image dosnt flicker */
1042 MTexPoly *EDBM_mtexpoly_active_get(BMEditMesh *em, BMFace **r_act_efa, const bool sloppy, const bool selected)
1043 {
1044         BMFace *efa = NULL;
1045         
1046         if (!EDBM_mtexpoly_check(em))
1047                 return NULL;
1048         
1049         efa = BM_mesh_active_face_get(em->bm, sloppy, selected);
1050
1051         if (efa) {
1052                 if (r_act_efa) *r_act_efa = efa;
1053                 return CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY);
1054         }
1055
1056         if (r_act_efa) *r_act_efa = NULL;
1057         return NULL;
1058 }
1059
1060 /* can we edit UV's for this mesh?*/
1061 bool EDBM_mtexpoly_check(BMEditMesh *em)
1062 {
1063         /* some of these checks could be a touch overkill */
1064         return em && em->bm->totface && CustomData_has_layer(&em->bm->pdata, CD_MTEXPOLY) &&
1065                CustomData_has_layer(&em->bm->ldata, CD_MLOOPUV);
1066 }
1067
1068 bool EDBM_vert_color_check(BMEditMesh *em)
1069 {
1070         /* some of these checks could be a touch overkill */
1071         return em && em->bm->totface && CustomData_has_layer(&em->bm->ldata, CD_MLOOPCOL);
1072 }
1073
1074 static BMVert *cache_mirr_intptr_as_bmvert(intptr_t *index_lookup, int index)
1075 {
1076         intptr_t eve_i = index_lookup[index];
1077         return (eve_i == -1) ? NULL : (BMVert *)eve_i;
1078 }
1079
1080 /**
1081  * Mirror editing API, usage:
1082  *
1083  * \code{.c}
1084  * EDBM_verts_mirror_cache_begin(em, ...);
1085  *
1086  * BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
1087  *     v_mirror = EDBM_verts_mirror_get(em, v);
1088  *     e_mirror = EDBM_verts_mirror_get_edge(em, e);
1089  *     f_mirror = EDBM_verts_mirror_get_face(em, f);
1090  * }
1091  *
1092  * EDBM_verts_mirror_cache_end(em);
1093  * \endcode
1094  */
1095
1096 /* BM_SEARCH_MAXDIST is too big, copied from 2.6x MOC_THRESH, should become a
1097  * preference */
1098 #define BM_SEARCH_MAXDIST_MIRR 0.00002f
1099 #define BM_CD_LAYER_ID "__mirror_index"
1100 /**
1101  * \param em  Editmesh.
1102  * \param use_self  Allow a vertex to point to its self (middle verts).
1103  * \param use_select  Restrict to selected verts.
1104  * \param use_topology  Use topology mirror.
1105  * \param maxdist  Distance for close point test.
1106  * \param r_index  Optional array to write into, as an alternative to a customdata layer (length of total verts).
1107  */
1108 void EDBM_verts_mirror_cache_begin_ex(BMEditMesh *em, const int axis, const bool use_self, const bool use_select,
1109                                       /* extra args */
1110                                       const bool use_topology, float maxdist, int *r_index)
1111 {
1112         Mesh *me = (Mesh *)em->ob->data;
1113         BMesh *bm = em->bm;
1114         BMIter iter;
1115         BMVert *v;
1116         int cd_vmirr_offset;
1117         int i;
1118         const float maxdist_sq = SQUARE(maxdist);
1119
1120         /* one or the other is used depending if topo is enabled */
1121         KDTree *tree = NULL;
1122         MirrTopoStore_t mesh_topo_store = {NULL, -1, -1, -1};
1123
1124         BM_mesh_elem_table_ensure(bm, BM_VERT);
1125
1126         if (r_index == NULL) {
1127                 const char *layer_id = BM_CD_LAYER_ID;
1128                 em->mirror_cdlayer = CustomData_get_named_layer_index(&bm->vdata, CD_PROP_INT, layer_id);
1129                 if (em->mirror_cdlayer == -1) {
1130                         BM_data_layer_add_named(bm, &bm->vdata, CD_PROP_INT, layer_id);
1131                         em->mirror_cdlayer = CustomData_get_named_layer_index(&bm->vdata, CD_PROP_INT, layer_id);
1132                 }
1133
1134                 cd_vmirr_offset = CustomData_get_n_offset(&bm->vdata, CD_PROP_INT,
1135                                                           em->mirror_cdlayer - CustomData_get_layer_index(&bm->vdata, CD_PROP_INT));
1136
1137                 bm->vdata.layers[em->mirror_cdlayer].flag |= CD_FLAG_TEMPORARY;
1138         }
1139
1140         BM_mesh_elem_index_ensure(bm, BM_VERT);
1141
1142         if (use_topology) {
1143                 ED_mesh_mirrtopo_init(me, -1, &mesh_topo_store, true);
1144         }
1145         else {
1146                 tree = BLI_kdtree_new(bm->totvert);
1147                 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1148                         BLI_kdtree_insert(tree, i, v->co);
1149                 }
1150                 BLI_kdtree_balance(tree);
1151         }
1152
1153 #define VERT_INTPTR(_v, _i) r_index ? &r_index[_i] : BM_ELEM_CD_GET_VOID_P(_v, cd_vmirr_offset);
1154
1155         BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1156                 BLI_assert(BM_elem_index_get(v) == i);
1157
1158                 /* temporary for testing, check for selection */
1159                 if (use_select && !BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1160                         /* do nothing */
1161                 }
1162                 else {
1163                         BMVert *v_mirr;
1164                         int *idx = VERT_INTPTR(v, i);
1165
1166                         if (use_topology) {
1167                                 v_mirr = cache_mirr_intptr_as_bmvert(mesh_topo_store.index_lookup, i);
1168                         }
1169                         else {
1170                                 int i_mirr;
1171                                 float co[3];
1172                                 copy_v3_v3(co, v->co);
1173                                 co[axis] *= -1.0f;
1174
1175                                 v_mirr = NULL;
1176                                 i_mirr = BLI_kdtree_find_nearest(tree, co, NULL);
1177                                 if (i_mirr != -1) {
1178                                         BMVert *v_test = BM_vert_at_index(bm, i_mirr);
1179                                         if (len_squared_v3v3(co, v_test->co) < maxdist_sq) {
1180                                                 v_mirr = v_test;
1181                                         }
1182                                 }
1183                         }
1184
1185                         if (v_mirr && (use_self || (v_mirr != v))) {
1186                                 const int i_mirr = BM_elem_index_get(v_mirr);
1187                                 *idx = i_mirr;
1188                                 idx = VERT_INTPTR(v_mirr, i_mirr);
1189                                 *idx = i;
1190                         }
1191                         else {
1192                                 *idx = -1;
1193                         }
1194                 }
1195
1196         }
1197
1198 #undef VERT_INTPTR
1199
1200         if (use_topology) {
1201                 ED_mesh_mirrtopo_free(&mesh_topo_store);
1202         }
1203         else {
1204                 BLI_kdtree_free(tree);
1205         }
1206 }
1207
1208 void EDBM_verts_mirror_cache_begin(BMEditMesh *em, const int axis,
1209                                    const bool use_self, const bool use_select,
1210                                    const bool use_topology)
1211 {
1212         EDBM_verts_mirror_cache_begin_ex(em, axis,
1213                                          use_self, use_select,
1214                                          /* extra args */
1215                                          use_topology, BM_SEARCH_MAXDIST_MIRR, NULL);
1216 }
1217
1218 BMVert *EDBM_verts_mirror_get(BMEditMesh *em, BMVert *v)
1219 {
1220         const int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
1221
1222         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
1223
1224         if (mirr && *mirr >= 0 && *mirr < em->bm->totvert) {
1225                 if (!em->bm->vtable) {
1226                         printf("err: should only be called between "
1227                                "EDBM_verts_mirror_cache_begin and EDBM_verts_mirror_cache_end");
1228                         return NULL;
1229                 }
1230
1231                 return em->bm->vtable[*mirr];
1232         }
1233
1234         return NULL;
1235 }
1236
1237 BMEdge *EDBM_verts_mirror_get_edge(BMEditMesh *em, BMEdge *e)
1238 {
1239         BMVert *v1_mirr = EDBM_verts_mirror_get(em, e->v1);
1240         if (v1_mirr) {
1241                 BMVert *v2_mirr = EDBM_verts_mirror_get(em, e->v2);
1242                 if (v2_mirr) {
1243                         return BM_edge_exists(v1_mirr, v2_mirr);
1244                 }
1245         }
1246
1247         return NULL;
1248 }
1249
1250 BMFace *EDBM_verts_mirror_get_face(BMEditMesh *em, BMFace *f)
1251 {
1252         BMFace *f_mirr = NULL;
1253         BMVert **v_mirr_arr = BLI_array_alloca(v_mirr_arr, f->len);
1254
1255         BMLoop *l_iter, *l_first;
1256         unsigned int i = 0;
1257
1258         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1259         do {
1260                 if ((v_mirr_arr[i++] = EDBM_verts_mirror_get(em, l_iter->v)) == NULL) {
1261                         return NULL;
1262                 }
1263         } while ((l_iter = l_iter->next) != l_first);
1264
1265         BM_face_exists(v_mirr_arr, f->len, &f_mirr);
1266         return f_mirr;
1267 }
1268
1269 void EDBM_verts_mirror_cache_clear(BMEditMesh *em, BMVert *v)
1270 {
1271         int *mirr = CustomData_bmesh_get_layer_n(&em->bm->vdata, v->head.data, em->mirror_cdlayer);
1272
1273         BLI_assert(em->mirror_cdlayer != -1); /* invalid use */
1274
1275         if (mirr) {
1276                 *mirr = -1;
1277         }
1278 }
1279
1280 void EDBM_verts_mirror_cache_end(BMEditMesh *em)
1281 {
1282         em->mirror_cdlayer = -1;
1283 }
1284
1285 void EDBM_verts_mirror_apply(BMEditMesh *em, const int sel_from, const int sel_to)
1286 {
1287         BMIter iter;
1288         BMVert *v;
1289
1290         BLI_assert((em->bm->vtable != NULL) && ((em->bm->elem_table_dirty & BM_VERT) == 0));
1291
1292         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
1293                 if (BM_elem_flag_test(v, BM_ELEM_SELECT) == sel_from) {
1294                         BMVert *mirr = EDBM_verts_mirror_get(em, v);
1295                         if (mirr) {
1296                                 if (BM_elem_flag_test(mirr, BM_ELEM_SELECT) == sel_to) {
1297                                         copy_v3_v3(mirr->co, v->co);
1298                                         mirr->co[0] *= -1.0f;
1299                                 }
1300                         }
1301                 }
1302         }
1303 }
1304
1305
1306 /* swap is 0 or 1, if 1 it hides not selected */
1307 void EDBM_mesh_hide(BMEditMesh *em, bool swap)
1308 {
1309         BMIter iter;
1310         BMElem *ele;
1311         int itermode;
1312         char hflag_swap = swap ? BM_ELEM_SELECT : 0;
1313
1314         if (em == NULL) return;
1315
1316         if (em->selectmode & SCE_SELECT_VERTEX)
1317                 itermode = BM_VERTS_OF_MESH;
1318         else if (em->selectmode & SCE_SELECT_EDGE)
1319                 itermode = BM_EDGES_OF_MESH;
1320         else
1321                 itermode = BM_FACES_OF_MESH;
1322
1323         BM_ITER_MESH (ele, &iter, em->bm, itermode) {
1324                 if (BM_elem_flag_test(ele, BM_ELEM_SELECT) ^ hflag_swap)
1325                         BM_elem_hide_set(em->bm, ele, true);
1326         }
1327
1328         EDBM_selectmode_flush(em);
1329
1330         /* original hide flushing comment (OUTDATED):
1331          * hide happens on least dominant select mode, and flushes up, not down! (helps preventing errors in subsurf) */
1332         /* - vertex hidden, always means edge is hidden too
1333          * - edge hidden, always means face is hidden too
1334          * - face hidden, only set face hide
1335          * - then only flush back down what's absolute hidden
1336          */
1337 }
1338
1339
1340 void EDBM_mesh_reveal(BMEditMesh *em)
1341 {
1342         const char iter_types[3] = {BM_VERTS_OF_MESH,
1343                                     BM_EDGES_OF_MESH,
1344                                     BM_FACES_OF_MESH};
1345
1346         const bool sels[3] = {
1347             (em->selectmode & SCE_SELECT_VERTEX) != 0,
1348             (em->selectmode & SCE_SELECT_EDGE) != 0,
1349             (em->selectmode & SCE_SELECT_FACE) != 0,
1350         };
1351         int i;
1352
1353         /* Use tag flag to remember what was hidden before all is revealed.
1354          * BM_ELEM_HIDDEN --> BM_ELEM_TAG */
1355 #pragma omp parallel for schedule(static) if (em->bm->totvert + em->bm->totedge + em->bm->totface >= BM_OMP_LIMIT)
1356         for (i = 0; i < 3; i++) {
1357                 BMIter iter;
1358                 BMElem *ele;
1359
1360                 BM_ITER_MESH (ele, &iter, em->bm, iter_types[i]) {
1361                         BM_elem_flag_set(ele, BM_ELEM_TAG, BM_elem_flag_test(ele, BM_ELEM_HIDDEN));
1362                 }
1363         }
1364
1365         /* Reveal everything */
1366         EDBM_flag_disable_all(em, BM_ELEM_HIDDEN);
1367
1368         /* Select relevant just-revealed elements */
1369         for (i = 0; i < 3; i++) {
1370                 BMIter iter;
1371                 BMElem *ele;
1372
1373                 if (!sels[i]) {
1374                         continue;
1375                 }
1376
1377                 BM_ITER_MESH (ele, &iter, em->bm, iter_types[i]) {
1378                         if (BM_elem_flag_test(ele, BM_ELEM_TAG)) {
1379                                 BM_elem_select_set(em->bm, ele, true);
1380                         }
1381                 }
1382         }
1383
1384         EDBM_selectmode_flush(em);
1385
1386         /* hidden faces can have invalid normals */
1387         EDBM_mesh_normals_update(em);
1388 }
1389
1390 /* so many tools call these that we better make it a generic function.
1391  */
1392 void EDBM_update_generic(BMEditMesh *em, const bool do_tessface, const bool is_destructive)
1393 {
1394         Object *ob = em->ob;
1395         /* order of calling isn't important */
1396         DAG_id_tag_update(ob->data, OB_RECALC_DATA);
1397         WM_main_add_notifier(NC_GEOM | ND_DATA, ob->data);
1398
1399         if (do_tessface) {
1400                 BKE_editmesh_tessface_calc(em);
1401         }
1402
1403         if (is_destructive) {
1404                 /* TODO. we may be able to remove this now! - Campbell */
1405                 // BM_mesh_elem_table_free(em->bm, BM_ALL_NOLOOP);
1406         }
1407         else {
1408                 /* in debug mode double check we didn't need to recalculate */
1409                 BLI_assert(BM_mesh_elem_table_check(em->bm) == true);
1410         }
1411
1412         /* don't keep stale derivedMesh data around, see: [#38872] */
1413         BKE_editmesh_free_derivedmesh(em);
1414
1415 #ifdef DEBUG
1416         {
1417                 BMEditSelection *ese;
1418                 for (ese = em->bm->selected.first; ese; ese = ese->next) {
1419                         BLI_assert(BM_elem_flag_test(ese->ele, BM_ELEM_SELECT));
1420                 }
1421         }
1422 #endif
1423 }
1424
1425 /* poll call for mesh operators requiring a view3d context */
1426 int EDBM_view3d_poll(bContext *C)
1427 {
1428         if (ED_operator_editmesh(C) && ED_operator_view3d_active(C))
1429                 return 1;
1430
1431         return 0;
1432 }
1433
1434 BMElem *EDBM_elem_from_selectmode(BMEditMesh *em, BMVert *eve, BMEdge *eed, BMFace *efa)
1435 {
1436         BMElem *ele = NULL;
1437
1438         if ((em->selectmode & SCE_SELECT_VERTEX) && eve) {
1439                 ele = (BMElem *)eve;
1440         }
1441         else if ((em->selectmode & SCE_SELECT_EDGE) && eed) {
1442                 ele = (BMElem *)eed;
1443         }
1444         else if ((em->selectmode & SCE_SELECT_FACE) && efa) {
1445                 ele = (BMElem *)efa;
1446         }
1447
1448         return ele;
1449 }
1450
1451 /**
1452  * Used when we want to store a single index for any vert/edge/face.
1453  *
1454  * Intended for use with operators.
1455  */
1456 int EDBM_elem_to_index_any(BMEditMesh *em, BMElem *ele)
1457 {
1458         BMesh *bm = em->bm;
1459         int index = BM_elem_index_get(ele);
1460
1461         if (ele->head.htype == BM_VERT) {
1462                 BLI_assert(!(bm->elem_index_dirty & BM_VERT));
1463         }
1464         else if (ele->head.htype == BM_EDGE) {
1465                 BLI_assert(!(bm->elem_index_dirty & BM_EDGE));
1466                 index += bm->totvert;
1467         }
1468         else if (ele->head.htype == BM_FACE) {
1469                 BLI_assert(!(bm->elem_index_dirty & BM_FACE));
1470                 index += bm->totvert + bm->totedge;
1471         }
1472         else {
1473                 BLI_assert(0);
1474         }
1475
1476         return index;
1477 }
1478
1479 BMElem *EDBM_elem_from_index_any(BMEditMesh *em, int index)
1480 {
1481         BMesh *bm = em->bm;
1482
1483         if (index < bm->totvert) {
1484                 return (BMElem *)BM_vert_at_index_find_or_table(bm, index);
1485         }
1486         index -= bm->totvert;
1487         if (index < bm->totedge) {
1488                 return (BMElem *)BM_edge_at_index_find_or_table(bm, index);
1489         }
1490         index -= bm->totedge;
1491         if (index < bm->totface) {
1492                 return (BMElem *)BM_face_at_index_find_or_table(bm, index);
1493         }
1494
1495         return NULL;
1496 }
1497
1498 /* -------------------------------------------------------------------- */
1499 /* BMBVH functions */
1500 // XXX
1501 #if 0 //BMESH_TODO: not implemented yet
1502 int BMBVH_VertVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d)
1503 {
1504
1505 }
1506 #endif
1507
1508 static BMFace *edge_ray_cast(struct BMBVHTree *tree, const float co[3], const float dir[3], float *r_hitout, BMEdge *e)
1509 {
1510         BMFace *f = BKE_bmbvh_ray_cast(tree, co, dir, 0.0f, NULL, r_hitout, NULL);
1511
1512         if (f && BM_edge_in_face(e, f))
1513                 return NULL;
1514
1515         return f;
1516 }
1517
1518 static void scale_point(float c1[3], const float p[3], const float s)
1519 {
1520         sub_v3_v3(c1, p);
1521         mul_v3_fl(c1, s);
1522         add_v3_v3(c1, p);
1523 }
1524
1525 bool BMBVH_EdgeVisible(struct BMBVHTree *tree, BMEdge *e, ARegion *ar, View3D *v3d, Object *obedit)
1526 {
1527         BMFace *f;
1528         float co1[3], co2[3], co3[3], dir1[3], dir2[3], dir3[3];
1529         float origin[3], invmat[4][4];
1530         float epsilon = 0.01f;
1531         float end[3];
1532         const float mval_f[2] = {ar->winx / 2.0f,
1533                                  ar->winy / 2.0f};
1534
1535         ED_view3d_win_to_segment(ar, v3d, mval_f, origin, end, false);
1536
1537         invert_m4_m4(invmat, obedit->obmat);
1538         mul_m4_v3(invmat, origin);
1539
1540         copy_v3_v3(co1, e->v1->co);
1541         mid_v3_v3v3(co2, e->v1->co, e->v2->co);
1542         copy_v3_v3(co3, e->v2->co);
1543
1544         scale_point(co1, co2, 0.99);
1545         scale_point(co3, co2, 0.99);
1546
1547         /* ok, idea is to generate rays going from the camera origin to the
1548          * three points on the edge (v1, mid, v2)*/
1549         sub_v3_v3v3(dir1, origin, co1);
1550         sub_v3_v3v3(dir2, origin, co2);
1551         sub_v3_v3v3(dir3, origin, co3);
1552
1553         normalize_v3(dir1);
1554         normalize_v3(dir2);
1555         normalize_v3(dir3);
1556
1557         mul_v3_fl(dir1, epsilon);
1558         mul_v3_fl(dir2, epsilon);
1559         mul_v3_fl(dir3, epsilon);
1560
1561         /* offset coordinates slightly along view vectors, to avoid
1562          * hitting the faces that own the edge.*/
1563         add_v3_v3v3(co1, co1, dir1);
1564         add_v3_v3v3(co2, co2, dir2);
1565         add_v3_v3v3(co3, co3, dir3);
1566
1567         normalize_v3(dir1);
1568         normalize_v3(dir2);
1569         normalize_v3(dir3);
1570
1571         /* do three samplings: left, middle, right */
1572         f = edge_ray_cast(tree, co1, dir1, NULL, e);
1573         if (f && !edge_ray_cast(tree, co2, dir2, NULL, e))
1574                 return true;
1575         else if (f && !edge_ray_cast(tree, co3, dir3, NULL, e))
1576                 return true;
1577         else if (!f)
1578                 return true;
1579
1580         return false;
1581 }