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