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