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