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