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