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