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