Revert "Fix T67040: Undo crashes after renaming"
[blender.git] / source / blender / editors / mesh / editmesh_intersect.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
17 /** \file
18  * \ingroup edmesh
19  */
20
21 #include "MEM_guardedalloc.h"
22
23 #include "DNA_object_types.h"
24
25 #include "BLI_math.h"
26 #include "BLI_memarena.h"
27 #include "BLI_stack.h"
28 #include "BLI_buffer.h"
29 #include "BLI_linklist_stack.h"
30
31 #include "BKE_layer.h"
32 #include "BKE_editmesh_bvh.h"
33 #include "BKE_context.h"
34 #include "BKE_report.h"
35 #include "BKE_editmesh.h"
36
37 #include "RNA_access.h"
38 #include "RNA_define.h"
39
40 #include "WM_types.h"
41
42 #include "ED_mesh.h"
43 #include "ED_screen.h"
44
45 #include "intern/bmesh_private.h"
46
47 #include "mesh_intern.h" /* own include */
48
49 #include "tools/bmesh_intersect.h"
50 #include "tools/bmesh_separate.h"
51
52 /* detect isolated holes and fill them */
53 #define USE_NET_ISLAND_CONNECT
54
55 /**
56  * Compare selected with its self.
57  */
58 static int bm_face_isect_self(BMFace *f, void *UNUSED(user_data))
59 {
60   if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
61     return 0;
62   }
63   else {
64     return -1;
65   }
66 }
67
68 /**
69  * Compare selected/unselected.
70  */
71 static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data))
72 {
73   if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
74     return -1;
75   }
76   else if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
77     return 1;
78   }
79   else {
80     return 0;
81   }
82 }
83
84 /**
85  * A flipped version of #bm_face_isect_pair
86  * use for boolean 'difference', which depends on order.
87  */
88 static int bm_face_isect_pair_swap(BMFace *f, void *UNUSED(user_data))
89 {
90   if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
91     return -1;
92   }
93   else if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
94     return 0;
95   }
96   else {
97     return 1;
98   }
99 }
100
101 /**
102  * Use for intersect and boolean.
103  */
104 static void edbm_intersect_select(BMEditMesh *em)
105 {
106   BM_mesh_elem_hflag_disable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_SELECT, false);
107
108   if (em->bm->selectmode & (SCE_SELECT_VERTEX | SCE_SELECT_EDGE)) {
109     BMIter iter;
110     BMEdge *e;
111
112     BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
113       if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
114         BM_edge_select_set(em->bm, e, true);
115       }
116     }
117   }
118
119   EDBM_mesh_normals_update(em);
120   EDBM_update_generic(em, true, true);
121 }
122
123 /* -------------------------------------------------------------------- */
124 /* Cut intersections into geometry */
125
126 /** \name Simple Intersect (self-intersect)
127  * \{
128  */
129
130 enum {
131   ISECT_SEL = 0,
132   ISECT_SEL_UNSEL = 1,
133 };
134
135 enum {
136   ISECT_SEPARATE_ALL = 0,
137   ISECT_SEPARATE_CUT = 1,
138   ISECT_SEPARATE_NONE = 2,
139 };
140
141 static int edbm_intersect_exec(bContext *C, wmOperator *op)
142 {
143   const int mode = RNA_enum_get(op->ptr, "mode");
144   int (*test_fn)(BMFace *, void *);
145   bool use_separate_all = false;
146   bool use_separate_cut = false;
147   const int separate_mode = RNA_enum_get(op->ptr, "separate_mode");
148   const float eps = RNA_float_get(op->ptr, "threshold");
149   bool use_self;
150   bool has_isect;
151
152   switch (mode) {
153     case ISECT_SEL:
154       test_fn = bm_face_isect_self;
155       use_self = true;
156       break;
157     default: /* ISECT_SEL_UNSEL */
158       test_fn = bm_face_isect_pair;
159       use_self = false;
160       break;
161   }
162
163   switch (separate_mode) {
164     case ISECT_SEPARATE_ALL:
165       use_separate_all = true;
166       break;
167     case ISECT_SEPARATE_CUT:
168       if (use_self == false) {
169         use_separate_cut = true;
170       }
171       else {
172         /* we could support this but would require more advanced logic inside 'BM_mesh_intersect'
173          * for now just separate all */
174         use_separate_all = true;
175       }
176       break;
177     default: /* ISECT_SEPARATE_NONE */
178       break;
179   }
180   ViewLayer *view_layer = CTX_data_view_layer(C);
181   uint objects_len = 0;
182   uint isect_len = 0;
183   Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data(
184       view_layer, CTX_wm_view3d(C), &objects_len);
185   for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
186     Object *obedit = objects[ob_index];
187     BMEditMesh *em = BKE_editmesh_from_object(obedit);
188
189     if (em->bm->totfacesel == 0) {
190       continue;
191     }
192
193     has_isect = BM_mesh_intersect(em->bm,
194                                   em->looptris,
195                                   em->tottri,
196                                   test_fn,
197                                   NULL,
198                                   use_self,
199                                   use_separate_all,
200                                   true,
201                                   true,
202                                   true,
203                                   true,
204                                   -1,
205                                   eps);
206
207     if (use_separate_cut) {
208       /* detach selected/un-selected faces */
209       BM_mesh_separate_faces(
210           em->bm, BM_elem_cb_check_hflag_enabled_simple(const BMFace *, BM_ELEM_SELECT));
211     }
212
213     if (has_isect) {
214       edbm_intersect_select(em);
215     }
216     else {
217       isect_len++;
218     }
219   }
220   MEM_freeN(objects);
221
222   if (isect_len == objects_len) {
223     BKE_report(op->reports, RPT_WARNING, "No intersections found");
224   }
225   return OPERATOR_FINISHED;
226 }
227
228 void MESH_OT_intersect(struct wmOperatorType *ot)
229 {
230   static const EnumPropertyItem isect_mode_items[] = {
231       {ISECT_SEL, "SELECT", 0, "Self Intersect", "Self intersect selected faces"},
232       {ISECT_SEL_UNSEL,
233        "SELECT_UNSELECT",
234        0,
235        "Selected/Unselected",
236        "Intersect selected with unselected faces"},
237       {0, NULL, 0, NULL, NULL},
238   };
239
240   static const EnumPropertyItem isect_separate_items[] = {
241       {ISECT_SEPARATE_ALL, "ALL", 0, "All", "Separate all geometry from intersections"},
242       {ISECT_SEPARATE_CUT,
243        "CUT",
244        0,
245        "Cut",
246        "Cut into geometry keeping each side separate (Selected/Unselected only)"},
247       {ISECT_SEPARATE_NONE, "NONE", 0, "Merge", "Merge all geometry from the intersection"},
248       {0, NULL, 0, NULL, NULL},
249   };
250
251   /* identifiers */
252   ot->name = "Intersect (Knife)";
253   ot->description = "Cut an intersection into faces";
254   ot->idname = "MESH_OT_intersect";
255
256   /* api callbacks */
257   ot->exec = edbm_intersect_exec;
258   ot->poll = ED_operator_editmesh;
259
260   /* props */
261   RNA_def_enum(ot->srna, "mode", isect_mode_items, ISECT_SEL_UNSEL, "Source", "");
262   RNA_def_enum(
263       ot->srna, "separate_mode", isect_separate_items, ISECT_SEPARATE_CUT, "Separate Mode", "");
264   RNA_def_float_distance(
265       ot->srna, "threshold", 0.000001f, 0.0, 0.01, "Merge threshold", "", 0.0, 0.001);
266
267   /* flags */
268   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
269 }
270
271 /** \} */
272
273 /* -------------------------------------------------------------------- */
274 /* Boolean (a kind of intersect) */
275
276 /** \name Boolean Intersect
277  *
278  * \note internally this is nearly exactly the same as 'MESH_OT_intersect',
279  * however from a user perspective they are quite different, so expose as different tools.
280  *
281  * \{
282  */
283
284 static int edbm_intersect_boolean_exec(bContext *C, wmOperator *op)
285 {
286   const int boolean_operation = RNA_enum_get(op->ptr, "operation");
287   bool use_swap = RNA_boolean_get(op->ptr, "use_swap");
288   const float eps = RNA_float_get(op->ptr, "threshold");
289   int (*test_fn)(BMFace *, void *);
290   bool has_isect;
291
292   test_fn = use_swap ? bm_face_isect_pair_swap : bm_face_isect_pair;
293   ViewLayer *view_layer = CTX_data_view_layer(C);
294   uint objects_len = 0;
295   uint isect_len = 0;
296   Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data(
297       view_layer, CTX_wm_view3d(C), &objects_len);
298   for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
299     Object *obedit = objects[ob_index];
300     BMEditMesh *em = BKE_editmesh_from_object(obedit);
301
302     if (em->bm->totfacesel == 0) {
303       continue;
304     }
305
306     has_isect = BM_mesh_intersect(em->bm,
307                                   em->looptris,
308                                   em->tottri,
309                                   test_fn,
310                                   NULL,
311                                   false,
312                                   false,
313                                   true,
314                                   true,
315                                   false,
316                                   true,
317                                   boolean_operation,
318                                   eps);
319
320     if (has_isect) {
321       edbm_intersect_select(em);
322     }
323     else {
324       isect_len++;
325     }
326   }
327   MEM_freeN(objects);
328
329   if (isect_len == objects_len) {
330     BKE_report(op->reports, RPT_WARNING, "No intersections found");
331   }
332   return OPERATOR_FINISHED;
333 }
334
335 void MESH_OT_intersect_boolean(struct wmOperatorType *ot)
336 {
337   static const EnumPropertyItem isect_boolean_operation_items[] = {
338       {BMESH_ISECT_BOOLEAN_ISECT, "INTERSECT", 0, "Intersect", ""},
339       {BMESH_ISECT_BOOLEAN_UNION, "UNION", 0, "Union", ""},
340       {BMESH_ISECT_BOOLEAN_DIFFERENCE, "DIFFERENCE", 0, "Difference", ""},
341       {0, NULL, 0, NULL, NULL},
342   };
343
344   /* identifiers */
345   ot->name = "Intersect (Boolean)";
346   ot->description = "Cut solid geometry from selected to unselected";
347   ot->idname = "MESH_OT_intersect_boolean";
348
349   /* api callbacks */
350   ot->exec = edbm_intersect_boolean_exec;
351   ot->poll = ED_operator_editmesh;
352
353   /* props */
354   RNA_def_enum(ot->srna,
355                "operation",
356                isect_boolean_operation_items,
357                BMESH_ISECT_BOOLEAN_DIFFERENCE,
358                "Boolean",
359                "");
360   RNA_def_boolean(ot->srna,
361                   "use_swap",
362                   false,
363                   "Swap",
364                   "Use with difference intersection to swap which side is kept");
365   RNA_def_float_distance(
366       ot->srna, "threshold", 0.000001f, 0.0, 0.01, "Merge threshold", "", 0.0, 0.001);
367
368   /* flags */
369   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
370 }
371
372 /** \} */
373
374 /* -------------------------------------------------------------------- */
375 /* Face Split by Edges */
376
377 /** \name Face/Edge Split
378  * \{ */
379
380 static void bm_face_split_by_edges(BMesh *bm,
381                                    BMFace *f,
382                                    const char hflag,
383                                    /* reusable memory buffer */
384                                    BLI_Buffer *edge_net_temp_buf)
385 {
386   const int f_index = BM_elem_index_get(f);
387
388   BMLoop *l_iter;
389   BMLoop *l_first;
390   BMVert *v;
391
392   BMFace **face_arr;
393   int face_arr_len;
394
395   /* likely this will stay very small
396    * all verts pushed into this stack _must_ have their previous edges set! */
397   BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *);
398   BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *);
399
400   BLI_assert(edge_net_temp_buf->count == 0);
401
402   /* collect all edges */
403   l_iter = l_first = BM_FACE_FIRST_LOOP(f);
404   do {
405     BMIter iter;
406     BMEdge *e;
407
408     BM_ITER_ELEM (e, &iter, l_iter->v, BM_EDGES_OF_VERT) {
409       if (BM_elem_flag_test(e, hflag) && (BM_elem_index_get(e) == f_index)) {
410         v = BM_edge_other_vert(e, l_iter->v);
411         v->e = e;
412
413         BLI_SMALLSTACK_PUSH(vert_stack, v);
414         BLI_buffer_append(edge_net_temp_buf, BMEdge *, e);
415       }
416     }
417   } while ((l_iter = l_iter->next) != l_first);
418
419   /* now assign all */
420   /* pop free values into the next stack */
421   while ((v = BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next))) {
422     BMIter eiter;
423     BMEdge *e_next;
424
425     BM_ITER_ELEM (e_next, &eiter, v, BM_EDGES_OF_VERT) {
426       if (BM_elem_flag_test(e_next, hflag) && (BM_elem_index_get(e_next) == -1)) {
427         BMVert *v_next;
428         v_next = BM_edge_other_vert(e_next, v);
429         BM_elem_index_set(e_next, f_index);
430         BLI_SMALLSTACK_PUSH(vert_stack_next, v_next);
431         BLI_buffer_append(edge_net_temp_buf, BMEdge *, e_next);
432       }
433     }
434
435     if (BLI_SMALLSTACK_IS_EMPTY(vert_stack)) {
436       BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next);
437     }
438   }
439
440   BM_face_split_edgenet(
441       bm, f, edge_net_temp_buf->data, edge_net_temp_buf->count, &face_arr, &face_arr_len);
442
443   BLI_buffer_clear(edge_net_temp_buf);
444
445   if (face_arr_len) {
446     int i;
447     for (i = 0; i < face_arr_len; i++) {
448       BM_face_select_set(bm, face_arr[i], true);
449       BM_elem_flag_disable(face_arr[i], hflag);
450     }
451   }
452
453   if (face_arr) {
454     MEM_freeN(face_arr);
455   }
456 }
457
458 /**
459  * Check if a vert is in any of the faces connected to the edge,
460  * \a f_ignore is a face we happen to know isn't shared by the vertex.
461  */
462 static bool bm_vert_in_faces_radial(BMVert *v, BMEdge *e_radial, BMFace *f_ignore)
463 {
464   BLI_assert(BM_vert_in_face(v, f_ignore) == false);
465   if (e_radial->l) {
466     BMLoop *l_iter = e_radial->l;
467     do {
468       if (l_iter->f != f_ignore) {
469         if (BM_vert_in_face(v, l_iter->f)) {
470           return true;
471         }
472       }
473     } while ((l_iter = l_iter->radial_next) != e_radial->l);
474   }
475   return false;
476 }
477
478 #ifdef USE_NET_ISLAND_CONNECT
479
480 struct LinkBase {
481   LinkNode *list;
482   unsigned int list_len;
483 };
484
485 static void ghash_insert_face_edge_link(GHash *gh,
486                                         BMFace *f_key,
487                                         BMEdge *e_val,
488                                         MemArena *mem_arena)
489 {
490   void **ls_base_p;
491   struct LinkBase *ls_base;
492   LinkNode *ls;
493
494   if (!BLI_ghash_ensure_p(gh, f_key, &ls_base_p)) {
495     ls_base = *ls_base_p = BLI_memarena_alloc(mem_arena, sizeof(*ls_base));
496     ls_base->list = NULL;
497     ls_base->list_len = 0;
498   }
499   else {
500     ls_base = *ls_base_p;
501   }
502
503   ls = BLI_memarena_alloc(mem_arena, sizeof(*ls));
504   ls->next = ls_base->list;
505   ls->link = e_val;
506   ls_base->list = ls;
507   ls_base->list_len += 1;
508 }
509
510 static int bm_edge_sort_length_cb(const void *e_a_v, const void *e_b_v)
511 {
512   const float val_a = -BM_edge_calc_length_squared(*((BMEdge **)e_a_v));
513   const float val_b = -BM_edge_calc_length_squared(*((BMEdge **)e_b_v));
514
515   if (val_a > val_b) {
516     return 1;
517   }
518   else if (val_a < val_b) {
519     return -1;
520   }
521   else {
522     return 0;
523   }
524 }
525
526 static void bm_face_split_by_edges_island_connect(
527     BMesh *bm, BMFace *f, LinkNode *e_link, const int e_link_len, MemArena *mem_arena_edgenet)
528 {
529   BMEdge **edge_arr = BLI_memarena_alloc(mem_arena_edgenet, sizeof(*edge_arr) * e_link_len);
530   int edge_arr_len = 0;
531
532   while (e_link) {
533     edge_arr[edge_arr_len++] = e_link->link;
534     e_link = e_link->next;
535   }
536
537   {
538     unsigned int edge_arr_holes_len;
539     BMEdge **edge_arr_holes;
540     if (BM_face_split_edgenet_connect_islands(bm,
541                                               f,
542                                               edge_arr,
543                                               e_link_len,
544                                               true,
545                                               mem_arena_edgenet,
546                                               &edge_arr_holes,
547                                               &edge_arr_holes_len)) {
548       edge_arr_len = edge_arr_holes_len;
549       edge_arr = edge_arr_holes; /* owned by the arena */
550     }
551   }
552
553   BM_face_split_edgenet(bm, f, edge_arr, edge_arr_len, NULL, NULL);
554
555   for (int i = e_link_len; i < edge_arr_len; i++) {
556     BM_edge_select_set(bm, edge_arr[i], true);
557   }
558
559   if (e_link_len != edge_arr_len) {
560     /* connecting partial islands can add redundant edges
561      * sort before removal to give deterministic outcome */
562     qsort(edge_arr, edge_arr_len - e_link_len, sizeof(*edge_arr), bm_edge_sort_length_cb);
563     for (int i = e_link_len; i < edge_arr_len; i++) {
564       BMFace *f_pair[2];
565       if (BM_edge_face_pair(edge_arr[i], &f_pair[0], &f_pair[1])) {
566         if (BM_face_share_vert_count(f_pair[0], f_pair[1]) == 2) {
567           BMFace *f_new = BM_faces_join(bm, f_pair, 2, true);
568           if (f_new) {
569             BM_face_select_set(bm, f_new, true);
570           }
571         }
572       }
573     }
574   }
575 }
576
577 /**
578  * Check if \a v_pivot should be spliced into an existing edge.
579  *
580  * Detect one of 3 cases:
581  *
582  * - \a v_pivot is shared by 2+ edges from different faces.
583  *   in this case return the closest edge shared by all faces.
584  *
585  * - \a v_pivot is an end-point of an edge which has no other edges connected.
586  *   in this case return the closest edge in \a f_a to the \a v_pivot.
587  *
588  * - \a v_pivot has only edges from the same face connected,
589  *   in this case return NULL. This is the most common case - no action is needed.
590  *
591  * \return the edge to be split.
592  *
593  * \note Currently we don't snap to verts or split chains by verts on-edges.
594  */
595 static BMEdge *bm_face_split_edge_find(BMEdge *e_a,
596                                        BMFace *f_a,
597                                        BMVert *v_pivot,
598                                        BMFace **ftable,
599                                        const int ftable_len,
600                                        float r_v_pivot_co[3],
601                                        float *r_v_pivot_fac)
602 {
603   const int f_a_index = BM_elem_index_get(e_a);
604   bool found_other_self = false;
605   int found_other_face = 0;
606   BLI_SMALLSTACK_DECLARE(face_stack, BMFace *);
607
608   /* loop over surrounding edges to check if we're part of a chain or a delimiter vertex */
609   BMEdge *e_b = v_pivot->e;
610   do {
611     if (e_b != e_a) {
612       const int f_b_index = BM_elem_index_get(e_b);
613       if (f_b_index == f_a_index) {
614         /* not an endpoint */
615         found_other_self = true;
616       }
617       else if (f_b_index != -1) {
618         BLI_assert(f_b_index < ftable_len);
619         UNUSED_VARS_NDEBUG(ftable_len);
620
621         /* 'v_pivot' spans 2+ faces,
622          * tag to ensure we pick an edge that includes this face */
623         BMFace *f_b = ftable[f_b_index];
624         if (!BM_elem_flag_test(f_b, BM_ELEM_INTERNAL_TAG)) {
625           BM_elem_flag_enable(f_b, BM_ELEM_INTERNAL_TAG);
626           BLI_SMALLSTACK_PUSH(face_stack, f_b);
627           found_other_face++;
628         }
629       }
630     }
631   } while ((e_b = BM_DISK_EDGE_NEXT(e_b, v_pivot)) != v_pivot->e);
632
633   BMEdge *e_split = NULL;
634
635   /* if we have no others or the other edge is outside this face,
636    * we're an endpoint to connect to a boundary */
637   if ((found_other_self == false) || found_other_face) {
638
639     BMLoop *l_iter, *l_first;
640     l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
641     float dist_best_sq = FLT_MAX;
642
643     do {
644       float v_pivot_co_test[3];
645       float v_pivot_fac = line_point_factor_v3(v_pivot->co, l_iter->e->v1->co, l_iter->e->v2->co);
646       CLAMP(v_pivot_fac, 0.0f, 1.0f);
647       interp_v3_v3v3(v_pivot_co_test, l_iter->e->v1->co, l_iter->e->v2->co, v_pivot_fac);
648
649       float dist_test_sq = len_squared_v3v3(v_pivot_co_test, v_pivot->co);
650       if ((dist_test_sq < dist_best_sq) || (e_split == NULL)) {
651         bool ok = true;
652
653         if (UNLIKELY(BM_edge_exists(v_pivot, l_iter->e->v1) ||
654                      BM_edge_exists(v_pivot, l_iter->e->v2))) {
655           /* very unlikely but will cause complications splicing the verts together,
656            * so just skip this case */
657           ok = false;
658         }
659         else if (found_other_face) {
660           /* double check that _all_ the faces used by v_pivot's edges are attached
661            * to this edge otherwise don't attempt the split since it will give
662            * non-deterministic results */
663           BMLoop *l_radial_iter = l_iter->radial_next;
664           int other_face_shared = 0;
665           if (l_radial_iter != l_iter) {
666             do {
667               if (BM_elem_flag_test(l_radial_iter->f, BM_ELEM_INTERNAL_TAG)) {
668                 other_face_shared++;
669               }
670             } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
671           }
672           if (other_face_shared != found_other_face) {
673             ok = false;
674           }
675         }
676
677         if (ok) {
678           e_split = l_iter->e;
679           dist_best_sq = dist_test_sq;
680           copy_v3_v3(r_v_pivot_co, v_pivot_co_test);
681           *r_v_pivot_fac = v_pivot_fac;
682         }
683       }
684     } while ((l_iter = l_iter->next) != l_first);
685   }
686
687   {
688     /* reset the flag, for future use */
689     BMFace *f;
690     while ((f = BLI_SMALLSTACK_POP(face_stack))) {
691       BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
692     }
693   }
694
695   return e_split;
696 }
697
698 #endif /* USE_NET_ISLAND_CONNECT */
699
700 static int edbm_face_split_by_edges_exec(bContext *C, wmOperator *UNUSED(op))
701 {
702   const char hflag = BM_ELEM_TAG;
703
704   BMEdge *e;
705   BMIter iter;
706
707   ViewLayer *view_layer = CTX_data_view_layer(C);
708   uint objects_len = 0;
709   Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data(
710       view_layer, CTX_wm_view3d(C), &objects_len);
711   for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
712     Object *obedit = objects[ob_index];
713     BMEditMesh *em = BKE_editmesh_from_object(obedit);
714     BMesh *bm = em->bm;
715
716     if ((bm->totedgesel == 0) || (bm->totfacesel == 0)) {
717       continue;
718     }
719
720     BLI_SMALLSTACK_DECLARE(loop_stack, BMLoop *);
721
722     {
723       BMVert *v;
724       BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
725         BM_elem_flag_disable(v, hflag);
726       }
727     }
728
729     /* edge index is set to -1 then used to associate them with faces */
730     BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
731       if (BM_elem_flag_test(e, BM_ELEM_SELECT) && BM_edge_is_wire(e)) {
732         BM_elem_flag_enable(e, hflag);
733
734         BM_elem_flag_enable(e->v1, hflag);
735         BM_elem_flag_enable(e->v2, hflag);
736       }
737       else {
738         BM_elem_flag_disable(e, hflag);
739       }
740       BM_elem_index_set(e, -1); /* set_dirty */
741     }
742     bm->elem_index_dirty |= BM_EDGE;
743
744     {
745       BMFace *f;
746       int i;
747       BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
748         if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
749           BM_elem_flag_enable(f, hflag);
750         }
751         else {
752           BM_elem_flag_disable(f, hflag);
753         }
754         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
755         BM_elem_index_set(f, i); /* set_ok */
756       }
757     }
758     bm->elem_index_dirty &= ~BM_FACE;
759
760     BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
761       if (BM_elem_flag_test(e, hflag)) {
762         BMIter viter;
763         BMVert *v;
764         BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
765           BMIter liter;
766           BMLoop *l;
767
768           unsigned int loop_stack_len;
769           BMLoop *l_best = NULL;
770
771           BLI_assert(BLI_SMALLSTACK_IS_EMPTY(loop_stack));
772           loop_stack_len = 0;
773
774           BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
775             if (BM_elem_flag_test(l->f, hflag)) {
776               BLI_SMALLSTACK_PUSH(loop_stack, l);
777               loop_stack_len++;
778             }
779           }
780
781           if (loop_stack_len == 0) {
782             /* pass */
783           }
784           else if (loop_stack_len == 1) {
785             l_best = BLI_SMALLSTACK_POP(loop_stack);
786           }
787           else {
788             /* complicated case, match the edge with a face-loop */
789
790             BMVert *v_other = BM_edge_other_vert(e, v);
791             float e_dir[3];
792
793             /* we want closest to zero */
794             float dot_best = FLT_MAX;
795
796             sub_v3_v3v3(e_dir, v_other->co, v->co);
797             normalize_v3(e_dir);
798
799             while ((l = BLI_SMALLSTACK_POP(loop_stack))) {
800               float dot_test;
801
802               /* Check dot first to save on expensive angle-comparison.
803                * ideal case is 90d difference == 0.0 dot */
804               dot_test = fabsf(dot_v3v3(e_dir, l->f->no));
805               if (dot_test < dot_best) {
806
807                 /* check we're in the correct corner
808                  * (works with convex loops too) */
809                 if (angle_signed_on_axis_v3v3v3_v3(
810                         l->prev->v->co, l->v->co, v_other->co, l->f->no) <
811                     angle_signed_on_axis_v3v3v3_v3(
812                         l->prev->v->co, l->v->co, l->next->v->co, l->f->no)) {
813                   dot_best = dot_test;
814                   l_best = l;
815                 }
816               }
817             }
818           }
819
820           if (l_best) {
821             BM_elem_index_set(e, BM_elem_index_get(l_best->f)); /* set_dirty */
822           }
823         }
824       }
825     }
826
827     {
828       BMFace *f;
829       BLI_buffer_declare_static(BMEdge **, edge_net_temp_buf, 0, 128);
830
831       BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
832         if (BM_elem_flag_test(f, hflag)) {
833           bm_face_split_by_edges(bm, f, hflag, &edge_net_temp_buf);
834         }
835       }
836       BLI_buffer_free(&edge_net_temp_buf);
837     }
838
839 #ifdef USE_NET_ISLAND_CONNECT
840     /* before overwriting edge index values, collect edges left untouched */
841     BLI_Stack *edges_loose = BLI_stack_new(sizeof(BMEdge *), __func__);
842     BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
843       if (BM_elem_flag_test(e, BM_ELEM_SELECT) && BM_edge_is_wire(e)) {
844         BLI_stack_push(edges_loose, &e);
845       }
846     }
847 #endif
848
849     EDBM_mesh_normals_update(em);
850     EDBM_update_generic(em, true, true);
851
852 #ifdef USE_NET_ISLAND_CONNECT
853     /* we may have remaining isolated regions remaining,
854      * these will need to have connecting edges created */
855     if (!BLI_stack_is_empty(edges_loose)) {
856       GHash *face_edge_map = BLI_ghash_ptr_new(__func__);
857
858       MemArena *mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
859
860       BM_mesh_elem_index_ensure(bm, BM_FACE);
861
862       {
863         BMBVHTree *bmbvh = BKE_bmbvh_new(
864             bm, em->looptris, em->tottri, BMBVH_RESPECT_SELECT, NULL, false);
865
866         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
867           BM_elem_index_set(e, -1); /* set_dirty */
868         }
869
870         while (!BLI_stack_is_empty(edges_loose)) {
871           BLI_stack_pop(edges_loose, &e);
872           float e_center[3];
873           mid_v3_v3v3(e_center, e->v1->co, e->v2->co);
874
875           BMFace *f = BKE_bmbvh_find_face_closest(bmbvh, e_center, FLT_MAX);
876           if (f) {
877             ghash_insert_face_edge_link(face_edge_map, f, e, mem_arena);
878             BM_elem_index_set(e, BM_elem_index_get(f)); /* set_dirty */
879           }
880         }
881
882         BKE_bmbvh_free(bmbvh);
883       }
884
885       bm->elem_index_dirty |= BM_EDGE;
886
887       BM_mesh_elem_table_ensure(bm, BM_FACE);
888
889       /* detect edges chains that span faces
890        * and splice vertices into the closest edges */
891       {
892         GHashIterator gh_iter;
893
894         GHASH_ITER (gh_iter, face_edge_map) {
895           BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
896           struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter);
897           LinkNode *e_link = e_ls_base->list;
898
899           do {
900             e = e_link->link;
901
902             for (int j = 0; j < 2; j++) {
903               BMVert *v_pivot = (&e->v1)[j];
904               /* checking that \a v_pivot isn't in the face prevents attempting
905                * to splice the same vertex into an edge from multiple faces */
906               if (!BM_vert_in_face(v_pivot, f)) {
907                 float v_pivot_co[3];
908                 float v_pivot_fac;
909                 BMEdge *e_split = bm_face_split_edge_find(
910                     e, f, v_pivot, bm->ftable, bm->totface, v_pivot_co, &v_pivot_fac);
911
912                 if (e_split) {
913                   /* for degenerate cases this vertex may be in one
914                    * of this edges radial faces */
915                   if (!bm_vert_in_faces_radial(v_pivot, e_split, f)) {
916                     BMEdge *e_new;
917                     BMVert *v_new = BM_edge_split(bm, e_split, e_split->v1, &e_new, v_pivot_fac);
918                     if (v_new) {
919                       /* we _know_ these don't share an edge */
920                       BM_vert_splice(bm, v_pivot, v_new);
921                       BM_elem_index_set(e_new, BM_elem_index_get(e_split));
922                     }
923                   }
924                 }
925               }
926             }
927
928           } while ((e_link = e_link->next));
929         }
930       }
931
932       {
933         MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
934
935         GHashIterator gh_iter;
936
937         GHASH_ITER (gh_iter, face_edge_map) {
938           BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
939           struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter);
940
941           bm_face_split_by_edges_island_connect(
942               bm, f, e_ls_base->list, e_ls_base->list_len, mem_arena_edgenet);
943
944           BLI_memarena_clear(mem_arena_edgenet);
945         }
946
947         BLI_memarena_free(mem_arena_edgenet);
948       }
949
950       BLI_memarena_free(mem_arena);
951
952       BLI_ghash_free(face_edge_map, NULL, NULL);
953
954       EDBM_mesh_normals_update(em);
955       EDBM_update_generic(em, true, true);
956     }
957
958     BLI_stack_free(edges_loose);
959 #endif /* USE_NET_ISLAND_CONNECT */
960   }
961   MEM_freeN(objects);
962   return OPERATOR_FINISHED;
963 }
964
965 void MESH_OT_face_split_by_edges(struct wmOperatorType *ot)
966 {
967   /* identifiers */
968   ot->name = "Weld Edges into Faces";
969   ot->description = "Weld loose edges into faces (splitting them into new faces)";
970   ot->idname = "MESH_OT_face_split_by_edges";
971
972   /* api callbacks */
973   ot->exec = edbm_face_split_by_edges_exec;
974   ot->poll = ED_operator_editmesh;
975
976   /* flags */
977   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
978 }
979
980 /** \} */