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