Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / bmesh / intern / bmesh_polygon_edgenet.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 \ingroup bmesh
18  *
19  * This file contains functions for splitting faces into isolated regions,
20  * defined by connected edges.
21  */
22 // #define DEBUG_PRINT
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_math.h"
27 #include "BLI_memarena.h"
28 #include "BLI_array.h"
29 #include "BLI_alloca.h"
30 #include "BLI_utildefines_stack.h"
31 #include "BLI_linklist_stack.h"
32 #include "BLI_sort_utils.h"
33 #include "BLI_kdopbvh.h"
34
35 #include "BKE_customdata.h"
36
37 #include "bmesh.h"
38 #include "intern/bmesh_private.h"
39
40 /* -------------------------------------------------------------------- */
41 /* Face Split Edge-Net */
42
43 /** \name BM_face_split_edgenet and helper functions.
44  *
45  * \note Don't use #BM_edge_is_wire or #BM_edge_is_boundary
46  * since we need to take flagged faces into account.
47  * Also take care accessing e->l directly.
48  *
49  * \{ */
50
51 /* Note: All these flags _must_ be cleared on exit */
52
53 /* face is apart of the edge-net (including the original face we're splitting) */
54 #define FACE_NET  _FLAG_WALK
55 /* edge is apart of the edge-net we're filling */
56 #define EDGE_NET   _FLAG_WALK
57 /* tag verts we've visit */
58 #define VERT_VISIT _FLAG_WALK
59 #define VERT_IN_QUEUE _FLAG_WALK_ALT
60
61 struct VertOrder {
62         float   angle;
63         BMVert *v;
64 };
65
66 static uint bm_edge_flagged_radial_count(BMEdge *e)
67 {
68         uint count = 0;
69         BMLoop *l;
70
71         if ((l = e->l)) {
72                 do {
73                         if (BM_ELEM_API_FLAG_TEST(l->f, FACE_NET)) {
74                                 count++;
75                         }
76                 } while ((l = l->radial_next) != e->l);
77         }
78         return count;
79 }
80
81 static BMLoop *bm_edge_flagged_radial_first(BMEdge *e)
82 {
83         BMLoop *l;
84
85         if ((l = e->l)) {
86                 do {
87                         if (BM_ELEM_API_FLAG_TEST(l->f, FACE_NET)) {
88                                 return l;
89                         }
90                 } while ((l = l->radial_next) != e->l);
91         }
92         return NULL;
93 }
94
95 static void normalize_v2_m3_v3v3(float out[2], float axis_mat[3][3], const float v1[3], const float v2[3])
96 {
97         float dir[3];
98         sub_v3_v3v3(dir, v1, v2);
99         mul_v2_m3v3(out, axis_mat, dir);
100         normalize_v2(out);
101 }
102
103
104 /**
105  * \note Be sure to update #bm_face_split_edgenet_find_loop_pair_exists
106  * when making changed to edge picking logic.
107  */
108 static bool bm_face_split_edgenet_find_loop_pair(
109         BMVert *v_init,
110         const float face_normal[3], float face_normal_matrix[3][3],
111         BMEdge *e_pair[2])
112 {
113         /* Always find one boundary edge (to determine winding)
114          * and one wire (if available), otherwise another boundary.
115          */
116
117         /* detect winding */
118         BMLoop *l_walk;
119         bool swap;
120
121         BLI_SMALLSTACK_DECLARE(edges_boundary, BMEdge *);
122         BLI_SMALLSTACK_DECLARE(edges_wire,     BMEdge *);
123         int edges_boundary_len = 0;
124         int edges_wire_len = 0;
125
126         {
127                 BMEdge *e, *e_first;
128                 e = e_first = v_init->e;
129                 do {
130                         if (BM_ELEM_API_FLAG_TEST(e, EDGE_NET)) {
131                                 const uint count = bm_edge_flagged_radial_count(e);
132                                 if (count == 1) {
133                                         BLI_SMALLSTACK_PUSH(edges_boundary, e);
134                                         edges_boundary_len++;
135                                 }
136                                 else if (count == 0) {
137                                         BLI_SMALLSTACK_PUSH(edges_wire, e);
138                                         edges_wire_len++;
139                                 }
140                         }
141                 } while ((e = BM_DISK_EDGE_NEXT(e, v_init)) != e_first);
142         }
143
144         /* first edge should always be boundary */
145         if (edges_boundary_len == 0) {
146                 return false;
147         }
148         e_pair[0] = BLI_SMALLSTACK_POP(edges_boundary);
149
150         /* use to hold boundary OR wire edges */
151         BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
152
153         /* attempt one boundary and one wire, or 2 boundary */
154         if (edges_wire_len == 0) {
155                 if (edges_boundary_len > 1) {
156                         e_pair[1] = BLI_SMALLSTACK_POP(edges_boundary);
157
158                         if (edges_boundary_len > 2) {
159                                 BLI_SMALLSTACK_SWAP(edges_search, edges_boundary);
160                         }
161                 }
162                 else {
163                         /* one boundary and no wire */
164                         return false;
165                 }
166         }
167         else {
168                 e_pair[1] = BLI_SMALLSTACK_POP(edges_wire);
169                 if (edges_wire_len > 1) {
170                         BLI_SMALLSTACK_SWAP(edges_search, edges_wire);
171                 }
172         }
173
174         /* if we swapped above, search this list for the best edge */
175         if (!BLI_SMALLSTACK_IS_EMPTY(edges_search)) {
176                 /* find the best edge in 'edge_list' to use for 'e_pair[1]' */
177                 const BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
178                 const BMVert *v_next = BM_edge_other_vert(e_pair[1], v_init);
179
180                 float dir_prev[2], dir_next[2];
181
182                 normalize_v2_m3_v3v3(dir_prev, face_normal_matrix, v_prev->co, v_init->co);
183                 normalize_v2_m3_v3v3(dir_next, face_normal_matrix, v_next->co, v_init->co);
184                 float angle_best_cos = dot_v2v2(dir_next, dir_prev);
185
186                 BMEdge *e;
187                 while ((e = BLI_SMALLSTACK_POP(edges_search))) {
188                         v_next = BM_edge_other_vert(e, v_init);
189                         float dir_test[2];
190
191                         normalize_v2_m3_v3v3(dir_test, face_normal_matrix, v_next->co, v_init->co);
192                         const float angle_test_cos = dot_v2v2(dir_prev, dir_test);
193
194                         if (angle_test_cos > angle_best_cos) {
195                                 angle_best_cos = angle_test_cos;
196                                 e_pair[1] = e;
197                         }
198                 }
199         }
200
201         /* flip based on winding */
202         l_walk = bm_edge_flagged_radial_first(e_pair[0]);
203         swap = false;
204         if (face_normal == l_walk->f->no) {
205                 swap = !swap;
206         }
207         if (l_walk->v != v_init) {
208                 swap = !swap;
209         }
210         if (swap) {
211                 SWAP(BMEdge *, e_pair[0], e_pair[1]);
212         }
213
214         return true;
215 }
216
217 /**
218  * A reduced version of #bm_face_split_edgenet_find_loop_pair
219  * that only checks if it would return true.
220  *
221  * \note There is no use in caching resulting edges here,
222  * since between this check and running #bm_face_split_edgenet_find_loop,
223  * the selected edges may have had faces attached.
224  */
225 static bool bm_face_split_edgenet_find_loop_pair_exists(
226         BMVert *v_init)
227 {
228         int edges_boundary_len = 0;
229         int edges_wire_len = 0;
230
231         {
232                 BMEdge *e, *e_first;
233                 e = e_first = v_init->e;
234                 do {
235                         if (BM_ELEM_API_FLAG_TEST(e, EDGE_NET)) {
236                                 const uint count = bm_edge_flagged_radial_count(e);
237                                 if (count == 1) {
238                                         edges_boundary_len++;
239                                 }
240                                 else if (count == 0) {
241                                         edges_wire_len++;
242                                 }
243                         }
244                 } while ((e = BM_DISK_EDGE_NEXT(e, v_init)) != e_first);
245         }
246
247         /* first edge should always be boundary */
248         if (edges_boundary_len == 0) {
249                 return false;
250         }
251
252         /* attempt one boundary and one wire, or 2 boundary */
253         if (edges_wire_len == 0) {
254                 if (edges_boundary_len >= 2) {
255                         /* pass */
256                 }
257                 else {
258                         /* one boundary and no wire */
259                         return false;
260                 }
261         }
262         else {
263                 /* pass */
264         }
265
266         return true;
267 }
268
269 static bool bm_face_split_edgenet_find_loop_walk(
270         BMVert *v_init, const float face_normal[3],
271         /* cache to avoid realloc every time */
272         struct VertOrder *edge_order, const uint edge_order_len,
273         BMEdge *e_pair[2])
274 {
275         /* fast-path for the common case (avoid push-pop).
276          * Also avoids tagging as visited since we know we
277          * can't reach these verts some other way */
278 #define USE_FASTPATH_NOFORK
279
280         BMVert *v;
281         BMVert *v_dst;
282         bool found = false;
283
284         struct VertOrder *eo;
285         STACK_DECLARE(edge_order);
286
287         /* store visited verts so we can clear the visit flag after execution */
288         BLI_SMALLSTACK_DECLARE(vert_visit, BMVert *);
289
290         /* likely this will stay very small
291          * all verts pushed into this stack _must_ have their previous edges set! */
292         BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *);
293         BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *);
294
295         STACK_INIT(edge_order, edge_order_len);
296
297         /* start stepping */
298         v = BM_edge_other_vert(e_pair[0], v_init);
299         v->e = e_pair[0];
300         BLI_SMALLSTACK_PUSH(vert_stack, v);
301
302         v_dst = BM_edge_other_vert(e_pair[1], v_init);
303
304 #ifdef DEBUG_PRINT
305         printf("%s: vert (search) %d\n", __func__, BM_elem_index_get(v_init));
306 #endif
307
308         /* This loop will keep stepping over the best possible edge,
309          * in most cases it finds the direct route to close the face.
310          *
311          * In cases where paths can't be closed,
312          * alternatives are stored in the 'vert_stack'.
313          */
314         while ((v = BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next))) {
315 #ifdef USE_FASTPATH_NOFORK
316 walk_nofork:
317 #else
318                 BLI_SMALLSTACK_PUSH(vert_visit, v);
319                 BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
320 #endif
321
322                 BLI_assert(STACK_SIZE(edge_order) == 0);
323
324                 /* check if we're done! */
325                 if (v == v_dst) {
326                         found = true;
327                         goto finally;
328                 }
329
330                 BMEdge *e_next, *e_first;
331                 e_first = v->e;
332                 e_next = BM_DISK_EDGE_NEXT(e_first, v);  /* always skip this verts edge */
333
334                 /* in rare cases there may be edges with a single connecting vertex */
335                 if (e_next != e_first) {
336                         do {
337                                 if ((BM_ELEM_API_FLAG_TEST(e_next, EDGE_NET)) &&
338                                     (bm_edge_flagged_radial_count(e_next) < 2))
339                                 {
340                                         BMVert *v_next;
341
342                                         v_next = BM_edge_other_vert(e_next, v);
343                                         BLI_assert(v->e != e_next);
344
345 #ifdef DEBUG_PRINT
346                                         /* indent and print */
347                                         {
348                                                 BMVert *_v = v;
349                                                 do {
350                                                         printf("  ");
351                                                 } while ((_v = BM_edge_other_vert(_v->e, _v)) != v_init);
352                                                 printf("vert %d -> %d (add=%d)\n",
353                                                        BM_elem_index_get(v), BM_elem_index_get(v_next),
354                                                        BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT) == 0);
355                                         }
356 #endif
357
358                                         if (!BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT)) {
359                                                 eo = STACK_PUSH_RET_PTR(edge_order);
360                                                 eo->v = v_next;
361
362                                                 v_next->e = e_next;
363                                         }
364                                 }
365                         } while ((e_next = BM_DISK_EDGE_NEXT(e_next, v)) != e_first);
366                 }
367
368 #ifdef USE_FASTPATH_NOFORK
369                 if (STACK_SIZE(edge_order) == 1) {
370                         eo = STACK_POP_PTR(edge_order);
371                         v = eo->v;
372
373                         goto walk_nofork;
374                 }
375 #endif
376
377                 /* sort by angle if needed */
378                 if (STACK_SIZE(edge_order) > 1) {
379                         uint j;
380                         BMVert *v_prev = BM_edge_other_vert(v->e, v);
381
382                         for (j = 0; j < STACK_SIZE(edge_order); j++) {
383                                 edge_order[j].angle = angle_signed_on_axis_v3v3v3_v3(v_prev->co, v->co, edge_order[j].v->co, face_normal);
384                         }
385                         qsort(edge_order, STACK_SIZE(edge_order), sizeof(struct VertOrder), BLI_sortutil_cmp_float_reverse);
386
387 #ifdef USE_FASTPATH_NOFORK
388                         /* only tag forks */
389                         BLI_SMALLSTACK_PUSH(vert_visit, v);
390                         BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
391 #endif
392                 }
393
394                 while ((eo = STACK_POP_PTR(edge_order))) {
395                         BLI_SMALLSTACK_PUSH(vert_stack_next, eo->v);
396                 }
397
398                 if (!BLI_SMALLSTACK_IS_EMPTY(vert_stack_next)) {
399                         BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next);
400                 }
401         }
402
403
404 finally:
405         /* clear flag for next execution */
406         while ((v = BLI_SMALLSTACK_POP(vert_visit))) {
407                 BM_ELEM_API_FLAG_DISABLE(v, VERT_VISIT);
408         }
409
410         return found;
411
412 #undef USE_FASTPATH_NOFORK
413 }
414
415 static bool bm_face_split_edgenet_find_loop(
416         BMVert *v_init, const float face_normal[3], float face_normal_matrix[3][3],
417         /* cache to avoid realloc every time */
418         struct VertOrder *edge_order, const uint edge_order_len,
419         BMVert **r_face_verts, int *r_face_verts_len)
420 {
421         BMEdge *e_pair[2];
422         BMVert *v;
423
424         if (!bm_face_split_edgenet_find_loop_pair(v_init, face_normal, face_normal_matrix, e_pair)) {
425                 return false;
426         }
427
428         BLI_assert((bm_edge_flagged_radial_count(e_pair[0]) == 1) ||
429                    (bm_edge_flagged_radial_count(e_pair[1]) == 1));
430
431         if (bm_face_split_edgenet_find_loop_walk(v_init, face_normal, edge_order, edge_order_len, e_pair)) {
432                 uint i = 0;
433
434                 r_face_verts[i++] = v_init;
435                 v = BM_edge_other_vert(e_pair[1], v_init);
436                 do {
437                         r_face_verts[i++] = v;
438                 } while ((v = BM_edge_other_vert(v->e, v)) != v_init);
439                 *r_face_verts_len = i;
440                 return (i > 2) ? true : false;
441         }
442         else {
443                 return false;
444         }
445 }
446
447 /**
448  * Splits a face into many smaller faces defined by an edge-net.
449  * handle customdata and degenerate cases.
450  *
451  * - isolated holes or unsupported face configurations, will be ignored.
452  * - customdata calculations aren't efficient
453  *   (need to calculate weights for each vert).
454  */
455 bool BM_face_split_edgenet(
456         BMesh *bm,
457         BMFace *f, BMEdge **edge_net, const int edge_net_len,
458         BMFace ***r_face_arr, int *r_face_arr_len)
459 {
460         /* re-use for new face verts */
461         BMVert **face_verts;
462         int      face_verts_len;
463
464         BMFace **face_arr = NULL;
465         BLI_array_declare(face_arr);
466
467         BMVert **vert_queue;
468         STACK_DECLARE(vert_queue);
469         int i;
470
471         struct VertOrder *edge_order;
472         const uint edge_order_len = edge_net_len + 2;
473
474         BMVert *v;
475
476         BMLoop *l_iter, *l_first;
477
478
479         if (!edge_net_len) {
480                 if (r_face_arr) {
481                         *r_face_arr = NULL;
482                         *r_face_arr_len = 0;
483                 }
484                 return false;
485         }
486
487         /* over-alloc (probably 2-4 is only used in most cases), for the biggest-fan */
488         edge_order = BLI_array_alloca(edge_order, edge_order_len);
489
490         /* use later */
491         face_verts = BLI_array_alloca(face_verts, edge_net_len + f->len);
492
493         vert_queue = BLI_array_alloca(vert_queue, edge_net_len + f->len);
494         STACK_INIT(vert_queue, f->len + edge_net_len);
495
496         BLI_assert(BM_ELEM_API_FLAG_TEST(f, FACE_NET) == 0);
497         BM_ELEM_API_FLAG_ENABLE(f, FACE_NET);
498
499 #ifdef DEBUG
500         for (i = 0; i < edge_net_len; i++) {
501                 BLI_assert(BM_ELEM_API_FLAG_TEST(edge_net[i], EDGE_NET) == 0);
502                 BLI_assert(BM_edge_in_face(edge_net[i], f) == false);
503         }
504         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
505         do {
506                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_iter->e, EDGE_NET) == 0);
507         } while ((l_iter = l_iter->next) != l_first);
508 #endif
509
510         /* Note: 'VERT_IN_QUEUE' is often not needed at all,
511          * however in rare cases verts are added multiple times to the queue,
512          * that on it's own is harmless but in _very_ rare cases,
513          * the queue will overflow its maximum size,
514          * so we better be strict about this! see: T51539 */
515
516         for (i = 0; i < edge_net_len; i++) {
517                 BM_ELEM_API_FLAG_ENABLE(edge_net[i], EDGE_NET);
518                 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v1, VERT_IN_QUEUE);
519                 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v2, VERT_IN_QUEUE);
520         }
521         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
522         do {
523                 BM_ELEM_API_FLAG_ENABLE(l_iter->e, EDGE_NET);
524                 BM_ELEM_API_FLAG_DISABLE(l_iter->v, VERT_IN_QUEUE);
525         } while ((l_iter = l_iter->next) != l_first);
526
527         float face_normal_matrix[3][3];
528         axis_dominant_v3_to_m3(face_normal_matrix, f->no);
529
530
531         /* any vert can be used to begin with */
532         STACK_PUSH(vert_queue, l_first->v);
533         BM_ELEM_API_FLAG_ENABLE(l_first->v, VERT_IN_QUEUE);
534
535         while ((v = STACK_POP(vert_queue))) {
536                 BM_ELEM_API_FLAG_DISABLE(v, VERT_IN_QUEUE);
537                 if (bm_face_split_edgenet_find_loop(
538                         v, f->no, face_normal_matrix,
539                         edge_order, edge_order_len, face_verts, &face_verts_len))
540                 {
541                         BMFace *f_new;
542
543                         f_new = BM_face_create_verts(bm, face_verts, face_verts_len, f, BM_CREATE_NOP, false);
544
545                         for (i = 0; i < edge_net_len; i++) {
546                                 BLI_assert(BM_ELEM_API_FLAG_TEST(edge_net[i], EDGE_NET));
547                         }
548
549                         if (f_new) {
550                                 BLI_array_append(face_arr, f_new);
551                                 copy_v3_v3(f_new->no, f->no);
552
553                                 /* warning, normally don't do this,
554                                  * its needed for mesh intersection - which tracks face-sides based on selection */
555                                 f_new->head.hflag = f->head.hflag;
556                                 if (f->head.hflag & BM_ELEM_SELECT) {
557                                         bm->totfacesel++;
558                                 }
559
560                                 BM_ELEM_API_FLAG_ENABLE(f_new, FACE_NET);
561
562                                 /* add new verts to keep finding loops for
563                                  * (verts between boundary and manifold edges) */
564                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
565                                 do {
566                                         /* Avoid adding to queue multiple times (not common but happens). */
567                                         if (!BM_ELEM_API_FLAG_TEST(l_iter->v, VERT_IN_QUEUE) &&
568                                             bm_face_split_edgenet_find_loop_pair_exists(l_iter->v))
569                                         {
570                                                 STACK_PUSH(vert_queue, l_iter->v);
571                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->v, VERT_IN_QUEUE);
572                                         }
573                                 } while ((l_iter = l_iter->next) != l_first);
574                         }
575                 }
576         }
577
578
579         if (CustomData_has_math(&bm->ldata)) {
580                 /* reuse VERT_VISIT here to tag vert's already interpolated */
581                 BMIter iter;
582                 BMLoop *l_other;
583
584                 /* see: #BM_loop_interp_from_face for similar logic  */
585                 void **blocks   = BLI_array_alloca(blocks, f->len);
586                 float (*cos_2d)[2] = BLI_array_alloca(cos_2d, f->len);
587                 float *w        = BLI_array_alloca(w, f->len);
588                 float axis_mat[3][3];
589                 float co[2];
590
591                 /* interior loops */
592                 axis_dominant_v3_to_m3(axis_mat, f->no);
593
594
595                 /* first simply copy from existing face */
596                 i = 0;
597                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
598                 do {
599                         BM_ITER_ELEM (l_other, &iter, l_iter->v, BM_LOOPS_OF_VERT) {
600                                 if ((l_other->f != f) && BM_ELEM_API_FLAG_TEST(l_other->f, FACE_NET)) {
601                                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata,
602                                                                    l_iter->head.data, &l_other->head.data);
603                                 }
604                         }
605                         /* tag not to interpolate */
606                         BM_ELEM_API_FLAG_ENABLE(l_iter->v, VERT_VISIT);
607
608
609                         mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
610                         blocks[i] = l_iter->head.data;
611
612                 } while ((void)i++, (l_iter = l_iter->next) != l_first);
613
614
615                 for (i = 0; i < edge_net_len; i++) {
616                         BM_ITER_ELEM (v, &iter, edge_net[i], BM_VERTS_OF_EDGE) {
617                                 if (!BM_ELEM_API_FLAG_TEST(v, VERT_VISIT)) {
618                                         BMIter liter;
619
620                                         BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
621
622                                         /* interpolate this loop, then copy to the rest */
623                                         l_first = NULL;
624
625                                         BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
626                                                 if (BM_ELEM_API_FLAG_TEST(l_iter->f, FACE_NET)) {
627                                                         if (l_first == NULL) {
628                                                                 mul_v2_m3v3(co, axis_mat, v->co);
629                                                                 interp_weights_poly_v2(w, cos_2d, f->len, co);
630                                                                 CustomData_bmesh_interp(
631                                                                         &bm->ldata, (const void **)blocks,
632                                                                         w, NULL, f->len, l_iter->head.data);
633                                                                 l_first = l_iter;
634                                                         }
635                                                         else {
636                                                                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata,
637                                                                                            l_first->head.data, &l_iter->head.data);
638                                                         }
639                                                 }
640                                         }
641                                 }
642                         }
643                 }
644         }
645
646
647
648         /* cleanup */
649         for (i = 0; i < edge_net_len; i++) {
650                 BM_ELEM_API_FLAG_DISABLE(edge_net[i], EDGE_NET);
651                 /* from interp only */
652                 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v1, VERT_VISIT);
653                 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v2, VERT_VISIT);
654         }
655         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
656         do {
657                 BM_ELEM_API_FLAG_DISABLE(l_iter->e, EDGE_NET);
658                 /* from interp only */
659                 BM_ELEM_API_FLAG_DISABLE(l_iter->v, VERT_VISIT);
660         } while ((l_iter = l_iter->next) != l_first);
661
662         if (BLI_array_len(face_arr)) {
663                 bmesh_face_swap_data(f, face_arr[0]);
664                 BM_face_kill(bm, face_arr[0]);
665                 face_arr[0] = f;
666         }
667         else {
668                 BM_ELEM_API_FLAG_DISABLE(f, FACE_NET);
669         }
670
671         for (i = 0; i < BLI_array_len(face_arr); i++) {
672                 BM_ELEM_API_FLAG_DISABLE(face_arr[i], FACE_NET);
673         }
674
675         if (r_face_arr) {
676                 *r_face_arr = face_arr;
677                 *r_face_arr_len = BLI_array_len(face_arr);
678         }
679         else {
680                 if (face_arr) {
681                         MEM_freeN(face_arr);
682                 }
683         }
684
685         return true;
686 }
687
688 #undef FACE_NET
689 #undef VERT_VISIT
690 #undef EDGE_NET
691
692 /** \} */
693
694
695 /* -------------------------------------------------------------------- */
696 /* Face Split Edge-Net Connect Islands */
697
698 /** \name BM_face_split_edgenet_connect_islands and helper functions.
699  *
700  * Connect isolated mesh 'islands' so they form legal regions from which we can create faces.
701  *
702  * Intended to be used as a pre-processing step for #BM_face_split_edgenet.
703  *
704  * \warning Currently this risks running out of stack memory (#alloca),
705  * likely we'll pass in a memory arena (cleared each use) eventually.
706  *
707  * \{ */
708
709
710 #define USE_PARTIAL_CONNECT
711
712
713 #define VERT_IS_VALID BM_ELEM_INTERNAL_TAG
714
715 /* can be X or Y */
716 #define SORT_AXIS 0
717
718 BLI_INLINE bool edge_isect_verts_point_2d(
719         const BMEdge *e, const BMVert *v_a, const BMVert *v_b,
720         float r_isect[2])
721 {
722         /* This bias seems like it could be too large,
723          * mostly its not needed, see T52329 for example where it is. */
724         const float endpoint_bias = 1e-4f;
725         return ((isect_seg_seg_v2_point_ex(v_a->co, v_b->co, e->v1->co, e->v2->co, endpoint_bias, r_isect) == 1) &&
726                 ((e->v1 != v_a) && (e->v2 != v_a) && (e->v1 != v_b)  && (e->v2 != v_b)));
727 }
728
729 BLI_INLINE int axis_pt_cmp(const float pt_a[2], const float pt_b[2])
730 {
731         if (pt_a[0] < pt_b[0]) {
732                 return -1;
733         }
734         if (pt_a[0] > pt_b[0]) {
735                 return 1;
736         }
737         if (pt_a[1] < pt_b[1]) {
738                 return -1;
739         }
740         if (pt_a[1] > pt_b[1]) {
741                 return 1;
742         }
743         return 0;
744 }
745
746 /**
747  * Represents isolated edge-links,
748  * each island owns contiguous slices of the vert array.
749  * (edges remain in `edge_links`).
750  */
751 struct EdgeGroupIsland {
752         LinkNode edge_links;  /* keep first */
753         uint vert_len, edge_len;
754
755         /* Set the following vars once we have >1 groups */
756
757         /* when when an edge in a previous group connects to this one,
758          * so theres no need to create one pointing back. */
759         uint has_prev_edge : 1;
760
761         /* verts in the group which has the lowest & highest values,
762          * the lower vertex is connected to the first edge */
763         struct {
764                 BMVert *min, *max;
765                 /* used for sorting only */
766                 float min_axis[2];
767                 float max_axis[2];
768         } vert_span;
769 };
770
771 static int group_min_cmp_fn(const void *p1, const void *p2)
772 {
773         const struct EdgeGroupIsland *g1 = *(struct EdgeGroupIsland **)p1;
774         const struct EdgeGroupIsland *g2 = *(struct EdgeGroupIsland **)p2;
775         /* min->co[SORT_AXIS] hasn't been applied yet */
776         int test = axis_pt_cmp(g1->vert_span.min_axis, g2->vert_span.min_axis);
777         if (UNLIKELY(test == 0)) {
778                 test = axis_pt_cmp(g1->vert_span.max_axis, g2->vert_span.max_axis);
779         }
780         return test;
781 }
782
783 struct Edges_VertVert_BVHTreeTest {
784         float dist_orig;
785         BMEdge **edge_arr;
786
787         BMVert *v_origin;
788         BMVert *v_other;
789
790         const uint *vert_range;
791 };
792
793 struct Edges_VertRay_BVHTreeTest {
794         BMEdge **edge_arr;
795
796         BMVert *v_origin;
797
798         const uint *vert_range;
799 };
800
801 static void bvhtree_test_edges_isect_2d_vert_cb(
802         void *user_data, int index, const BVHTreeRay *UNUSED(ray), BVHTreeRayHit *hit)
803 {
804         struct Edges_VertVert_BVHTreeTest *data = user_data;
805         const BMEdge *e = data->edge_arr[index];
806         const int v1_index = BM_elem_index_get(e->v1);
807         float co_isect[2];
808
809         if (edge_isect_verts_point_2d(e, data->v_origin, data->v_other, co_isect)) {
810                 const float t = line_point_factor_v2(co_isect, data->v_origin->co, data->v_other->co);
811                 const float dist_new = data->dist_orig * t;
812                 /* avoid float precision issues, possible this is greater,
813                  * check above zero to allow some overlap
814                  * (and needed for partial-connect which will overlap vertices) */
815                 if (LIKELY((dist_new < hit->dist) && (dist_new > 0.0f))) {
816                         /* v1/v2 will both be in the same group */
817                         if (v1_index <  (int)data->vert_range[0] ||
818                             v1_index >= (int)data->vert_range[1])
819                         {
820                                 hit->dist = dist_new;
821                                 hit->index = index;
822                         }
823                 }
824         }
825 }
826
827 static void bvhtree_test_edges_isect_2d_ray_cb(
828         void *user_data, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
829 {
830         struct Edges_VertRay_BVHTreeTest *data = user_data;
831         const BMEdge *e = data->edge_arr[index];
832
833         /* direction is normalized, so this will be the distance */
834         float dist_new;
835         if (isect_ray_seg_v2(data->v_origin->co, ray->direction, e->v1->co, e->v2->co, &dist_new, NULL)) {
836                 /* avoid float precision issues, possible this is greater,
837                  * check above zero to allow some overlap
838                  * (and needed for partial-connect which will overlap vertices) */
839                 if (LIKELY(dist_new < hit->dist && (dist_new > 0.0f))) {
840                         if (e->v1 != data->v_origin && e->v2 != data->v_origin) {
841                                 const int v1_index = BM_elem_index_get(e->v1);
842                                 /* v1/v2 will both be in the same group */
843                                 if (v1_index <  (int)data->vert_range[0] ||
844                                     v1_index >= (int)data->vert_range[1])
845                                 {
846                                         hit->dist = dist_new;
847                                         hit->index = index;
848                                 }
849                         }
850                 }
851         }
852 }
853
854 /**
855  * Store values for:
856  * - #bm_face_split_edgenet_find_connection
857  * - #test_edges_isect_2d_vert
858  * ... which don't change each call.
859  */
860 struct EdgeGroup_FindConnection_Args {
861         BVHTree *bvhtree;
862         BMEdge **edge_arr;
863         uint edge_arr_len;
864
865         BMEdge **edge_arr_new;
866         uint edge_arr_new_len;
867
868         const uint *vert_range;
869 };
870
871 static BMEdge *test_edges_isect_2d_vert(
872         const struct EdgeGroup_FindConnection_Args *args,
873         BMVert *v_origin, BMVert *v_other)
874 {
875         int index;
876
877         BVHTreeRayHit hit = {0};
878         float dir[3];
879
880         sub_v2_v2v2(dir, v_other->co, v_origin->co);
881         dir[2] = 0.0f;
882         hit.index = -1;
883         hit.dist = normalize_v2(dir);
884
885         struct Edges_VertVert_BVHTreeTest user_data = {0};
886         user_data.dist_orig = hit.dist;
887         user_data.edge_arr = args->edge_arr;
888         user_data.v_origin = v_origin;
889         user_data.v_other = v_other;
890         user_data.vert_range = args->vert_range;
891
892         index = BLI_bvhtree_ray_cast_ex(
893                 args->bvhtree, v_origin->co, dir, 0.0f, &hit,
894                 bvhtree_test_edges_isect_2d_vert_cb, &user_data, 0);
895
896         BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : NULL;
897
898         /* check existing connections (no spatial optimization here since we're continually adding). */
899         if (LIKELY(index == -1)) {
900                 float t_best = 1.0f;
901                 for (uint i = 0; i < args->edge_arr_new_len; i++) {
902                         float co_isect[2];
903                         if (UNLIKELY(edge_isect_verts_point_2d(args->edge_arr_new[i], v_origin, v_other, co_isect))) {
904                                 const float t_test = line_point_factor_v2(co_isect, v_origin->co, v_other->co);
905                                 if (t_test < t_best) {
906                                         t_best = t_test;
907
908                                         e_hit = args->edge_arr_new[i];
909                                 }
910                         }
911                 }
912         }
913
914         return e_hit;
915 }
916
917 /**
918  * Similar to #test_edges_isect_2d_vert but we're casting into a direction,
919  * (not to a vertex)
920  */
921 static BMEdge *test_edges_isect_2d_ray(
922         const struct EdgeGroup_FindConnection_Args *args,
923         BMVert *v_origin, const float dir[3])
924 {
925         int index;
926         BVHTreeRayHit hit = {0};
927
928         BLI_ASSERT_UNIT_V2(dir);
929
930         hit.index = -1;
931         hit.dist = BVH_RAYCAST_DIST_MAX;
932
933         struct Edges_VertRay_BVHTreeTest user_data = {0};
934         user_data.edge_arr = args->edge_arr;
935         user_data.v_origin = v_origin;
936         user_data.vert_range = args->vert_range;
937
938         index = BLI_bvhtree_ray_cast_ex(
939                 args->bvhtree, v_origin->co, dir, 0.0f, &hit,
940                 bvhtree_test_edges_isect_2d_ray_cb, &user_data, 0);
941
942         BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : NULL;
943
944         /* check existing connections (no spatial optimization here since we're continually adding). */
945         if (LIKELY(index != -1)) {
946                 for (uint i = 0; i < args->edge_arr_new_len; i++) {
947                         BMEdge *e = args->edge_arr_new[i];
948                         float dist_new;
949                         if (isect_ray_seg_v2(v_origin->co, dir, e->v1->co, e->v2->co, &dist_new, NULL)) {
950                                 if (e->v1 != v_origin && e->v2 != v_origin) {
951                                         /* avoid float precision issues, possible this is greater */
952                                         if (LIKELY(dist_new < hit.dist)) {
953                                                 hit.dist = dist_new;
954
955                                                 e_hit = args->edge_arr_new[i];
956                                         }
957                                 }
958                         }
959                 }
960         }
961
962         return e_hit;
963 }
964
965 static int bm_face_split_edgenet_find_connection(
966         const struct EdgeGroup_FindConnection_Args *args,
967         BMVert *v_origin,
968         /* false = negative, true = positive */
969         bool direction_sign)
970 {
971         /**
972          * Method for finding connection is as follows:
973          *
974          * - Cast a ray along either the positive or negative directions.
975          * - Take the hit-edge, and cast rays to their vertices checking those rays don't intersect a closer edge.
976          * - Keep taking the hit-edge and testing its verts until a vertex is found which isn't blocked by an edge.
977          *
978          * \note It's possible none of the verts can be accessed (with self-intersecting lines).
979          * In that case theres no right answer (without subdividing edges),
980          * so return a fall-back vertex in that case.
981          */
982
983         const float dir[3] = {[SORT_AXIS] = direction_sign ? 1.0f : -1.0f};
984         BMEdge *e_hit = test_edges_isect_2d_ray(args, v_origin, dir);
985         BMVert *v_other = NULL;
986
987         if (e_hit) {
988                 BMVert *v_other_fallback = NULL;
989
990                 BLI_SMALLSTACK_DECLARE(vert_search, BMVert *);
991
992                 /* ensure we never add verts multiple times (not all that likely - but possible) */
993                 BLI_SMALLSTACK_DECLARE(vert_blacklist, BMVert *);
994
995                 do {
996                         BMVert *v_pair[2];
997                         /* ensure the closest vertex is popped back off the stack first */
998                         if (len_squared_v2v2(v_origin->co, e_hit->v1->co) >
999                             len_squared_v2v2(v_origin->co, e_hit->v2->co))
1000                         {
1001                                 ARRAY_SET_ITEMS(v_pair, e_hit->v1, e_hit->v2);
1002                         }
1003                         else {
1004                                 ARRAY_SET_ITEMS(v_pair, e_hit->v2, e_hit->v1);
1005                         }
1006
1007                         for (int j = 0; j < 2; j++) {
1008                                 BMVert *v_iter = v_pair[j];
1009                                 if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) {
1010                                         if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) :
1011                                                              (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS]))
1012                                         {
1013                                                 BLI_SMALLSTACK_PUSH(vert_search, v_iter);
1014                                                 BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter);
1015                                                 BM_elem_flag_disable(v_iter, VERT_IS_VALID);
1016                                         }
1017                                 }
1018                         }
1019                         v_other_fallback = v_other;
1020
1021                 } while ((v_other = BLI_SMALLSTACK_POP(vert_search)) &&
1022                          (e_hit   = test_edges_isect_2d_vert(args, v_origin, v_other)));
1023
1024                 if (v_other == NULL) {
1025                         printf("Using fallback\n");
1026                         v_other = v_other_fallback;
1027                 }
1028
1029                 /* reset the blacklist flag, for future use */
1030                 BMVert *v;
1031                 while ((v = BLI_SMALLSTACK_POP(vert_blacklist))) {
1032                         BM_elem_flag_enable(v, VERT_IS_VALID);
1033                 }
1034         }
1035
1036         /* if we reach this line, v_other is either the best vertex or its NULL */
1037         return v_other ? BM_elem_index_get(v_other) : -1;
1038 }
1039
1040
1041 /**
1042  * Support for connecting islands that have single-edge connections.
1043  * This options is not very optimal (however its not needed for booleans either).
1044  */
1045 #ifdef USE_PARTIAL_CONNECT
1046
1047 /**
1048  * Used to identify edges that  get split off when making island from partial connection.
1049  * fptr should be a BMFace*, but is a void* for general interface to BM_vert_separate_tested_edges
1050  */
1051 static bool test_tagged_and_notface(BMEdge *e, void *fptr)
1052 {
1053         BMFace *f = (BMFace *)fptr;
1054         return BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) && !BM_edge_in_face(e, f);
1055 }
1056
1057 /**
1058  * Split vertices which are part of a partial connection
1059  * (only a single vertex connecting an island).
1060  *
1061  * \note All edges and vertices must have their #BM_ELEM_INTERNAL_TAG flag enabled.
1062  * This function leaves all the flags set as well.
1063  */
1064 static BMVert *bm_face_split_edgenet_partial_connect(BMesh *bm, BMVert *v_delimit, BMFace *f)
1065 {
1066         /* -------------------------------------------------------------------- */
1067         /* Initial check that we may be a delimiting vert (keep this fast) */
1068
1069         /* initial check - see if we have 3+ flagged edges attached to 'v_delimit'
1070          * if not, we can early exit */
1071         LinkNode *e_delimit_list = NULL;
1072         uint e_delimit_list_len = 0;
1073
1074 #define EDGE_NOT_IN_STACK  BM_ELEM_INTERNAL_TAG
1075 #define VERT_NOT_IN_STACK  BM_ELEM_INTERNAL_TAG
1076
1077 #define FOREACH_VERT_EDGE(v_, e_, body_) { \
1078         BMEdge *e_ = v_->e; \
1079         do { body_ } while ((e_ = BM_DISK_EDGE_NEXT(e_, v_)) != v_->e); \
1080 } ((void)0)
1081
1082         /* start with face edges, since we need to split away wire-only edges */
1083         BMEdge *e_face_init = NULL;
1084
1085         FOREACH_VERT_EDGE(v_delimit, e_iter, {
1086                 if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
1087                         BLI_assert(BM_elem_flag_test(BM_edge_other_vert(e_iter, v_delimit), VERT_NOT_IN_STACK));
1088                         BLI_linklist_prepend_alloca(&e_delimit_list, e_iter);
1089                         e_delimit_list_len++;
1090                         if (e_iter->l != NULL && BM_edge_in_face(e_iter, f)) {
1091                                 e_face_init = e_iter;
1092                         }
1093                 }
1094         });
1095
1096         /* skip typical edge-chain verts */
1097         if (LIKELY(e_delimit_list_len <= 2)) {
1098                 return NULL;
1099         }
1100
1101
1102         /* -------------------------------------------------------------------- */
1103         /* Complicated stuff starts now! */
1104
1105
1106         /* Store connected vertices for restoring the flag */
1107         LinkNode *vert_stack = NULL;
1108         BLI_linklist_prepend_alloca(&vert_stack, v_delimit);
1109         BM_elem_flag_disable(v_delimit, VERT_NOT_IN_STACK);
1110
1111         /* Walk the net... */
1112         {
1113                 BLI_SMALLSTACK_DECLARE(search, BMVert *);
1114                 BMVert *v_other = BM_edge_other_vert(e_face_init ? e_face_init : v_delimit->e, v_delimit);
1115
1116                 BLI_SMALLSTACK_PUSH(search, v_other);
1117                 BM_elem_flag_disable(v_other, VERT_NOT_IN_STACK);
1118
1119                 while ((v_other = BLI_SMALLSTACK_POP(search))) {
1120                         BLI_assert(BM_elem_flag_test(v_other, VERT_NOT_IN_STACK) == false);
1121                         BLI_linklist_prepend_alloca(&vert_stack, v_other);
1122                         BMEdge *e_iter = v_other->e;
1123                         do {
1124                                 BMVert *v_step = BM_edge_other_vert(e_iter, v_other);
1125                                 if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
1126                                         if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK)) {
1127                                                 BM_elem_flag_disable(v_step, VERT_NOT_IN_STACK);
1128                                                 BLI_SMALLSTACK_PUSH(search, v_step);
1129                                         }
1130                                 }
1131                         } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_other)) != v_other->e);
1132                 }
1133         }
1134
1135         /* Detect if this is a delimiter by checking if we didn't walk any of edges connected to 'v_delimit' */
1136         bool is_delimit = false;
1137         FOREACH_VERT_EDGE(v_delimit, e_iter, {
1138                 BMVert *v_step = BM_edge_other_vert(e_iter, v_delimit);
1139                 if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK) && !BM_edge_in_face(e_iter, f)) {
1140                         is_delimit = true;  /* if one vertex is valid - we have a mix */
1141                 }
1142                 else {
1143                         /* match the vertex flag (only for edges around 'v_delimit') */
1144                         BM_elem_flag_disable(e_iter, EDGE_NOT_IN_STACK);
1145                 }
1146         });
1147
1148 #undef FOREACH_VERT_EDGE
1149
1150         /* Execute the split */
1151         BMVert *v_split = NULL;
1152         if (is_delimit) {
1153                 v_split = BM_vert_create(bm, v_delimit->co, NULL, 0);
1154                 BM_vert_separate_tested_edges(bm, v_split, v_delimit, test_tagged_and_notface, f);
1155                 BM_elem_flag_enable(v_split, VERT_NOT_IN_STACK);
1156
1157                 BLI_assert(v_delimit->e != NULL);
1158
1159                 /* Degenerate, avoid eternal loop, see: T59074. */
1160 #if 0
1161                 BLI_assert(v_split->e != NULL);
1162 #else
1163                 if (UNLIKELY(v_split->e == NULL)) {
1164                         BM_vert_kill(bm, v_split);
1165                         v_split = NULL;
1166                 }
1167 #endif
1168         }
1169
1170         /* Restore flags */
1171         do {
1172                 BM_elem_flag_enable((BMVert *)vert_stack->link, VERT_NOT_IN_STACK);
1173         } while ((vert_stack = vert_stack->next));
1174
1175         do {
1176                 BM_elem_flag_enable((BMEdge *)e_delimit_list->link, EDGE_NOT_IN_STACK);
1177         } while ((e_delimit_list = e_delimit_list->next));
1178
1179 #undef EDGE_NOT_IN_STACK
1180 #undef VERT_NOT_IN_STACK
1181
1182         return v_split;
1183 }
1184
1185
1186 /**
1187  * Check if connecting vertices would cause an edge with duplicate verts.
1188  */
1189 static bool bm_vert_partial_connect_check_overlap(
1190         const int *remap,
1191         const int v_a_index, const int v_b_index)
1192 {
1193         /* connected to eachother */
1194         if (UNLIKELY((remap[v_a_index] == v_b_index) ||
1195                      (remap[v_b_index] == v_a_index)))
1196         {
1197                 return true;
1198         }
1199         else {
1200                 return false;
1201         }
1202 }
1203
1204
1205 #endif  /* USE_PARTIAL_CONNECT */
1206
1207
1208
1209 /**
1210  * For when the edge-net has holes in it-this connects them.
1211  *
1212  * \param use_partial_connect: Support for handling islands connected by only a single edge,
1213  * \note that this is quite slow so avoid using where possible.
1214  * \param mem_arena: Avoids many small allocs & should be cleared after each use.
1215  * take care since \a r_edge_net_new is stored in \a r_edge_net_new.
1216  */
1217 bool BM_face_split_edgenet_connect_islands(
1218         BMesh *bm,
1219         BMFace *f, BMEdge **edge_net_init, const uint edge_net_init_len,
1220         bool use_partial_connect,
1221         MemArena *mem_arena,
1222         BMEdge ***r_edge_net_new, uint *r_edge_net_new_len)
1223 {
1224         /* -------------------------------------------------------------------- */
1225         /* This function has 2 main parts.
1226          *
1227          * - Check if there are any holes.
1228          * - Connect the holes with edges (if any are found).
1229          *
1230          * Keep the first part fast since it will run very often for edge-nets that have no holes.
1231          *
1232          * \note Don't use the mem_arena unless he have holes to fill.
1233          * (avoid thrashing the area when the initial check isn't so intensive on the stack).
1234          */
1235
1236         const uint edge_arr_len = (uint)edge_net_init_len + (uint)f->len;
1237         BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len);
1238         bool ok = false;
1239         uint edge_net_new_len = (uint)edge_net_init_len;
1240
1241         memcpy(edge_arr, edge_net_init, sizeof(*edge_arr) * (size_t)edge_net_init_len);
1242
1243         /* _must_ clear on exit */
1244 #define EDGE_NOT_IN_STACK  BM_ELEM_INTERNAL_TAG
1245 #define VERT_NOT_IN_STACK  BM_ELEM_INTERNAL_TAG
1246
1247         {
1248                 uint i = edge_net_init_len;
1249                 BMLoop *l_iter, *l_first;
1250                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1251                 do {
1252                         BLI_assert(!BM_elem_flag_test(l_iter->v, VERT_NOT_IN_STACK));
1253                         BLI_assert(!BM_elem_flag_test(l_iter->e, EDGE_NOT_IN_STACK));
1254                         edge_arr[i++] = l_iter->e;
1255                 } while ((l_iter = l_iter->next) != l_first);
1256                 BLI_assert(i == edge_arr_len);
1257         }
1258
1259         for (uint i = 0; i < edge_arr_len; i++) {
1260                 BM_elem_flag_enable(edge_arr[i], EDGE_NOT_IN_STACK);
1261                 BM_elem_flag_enable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
1262                 BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_STACK);
1263         }
1264
1265
1266
1267 #ifdef USE_PARTIAL_CONNECT
1268         /* Split-out delimiting vertices */
1269         struct TempVertPair {
1270                 struct TempVertPair *next;
1271                 BMVert *v_temp;
1272                 BMVert *v_orig;
1273         };
1274
1275         struct {
1276                 struct TempVertPair *list;
1277                 uint len;
1278                 int *remap;  /* temp -> orig mapping */
1279         } temp_vert_pairs = {NULL};
1280
1281         if (use_partial_connect) {
1282                 for (uint i = 0; i < edge_net_init_len; i++) {
1283                         for (unsigned j = 0; j < 2; j++) {
1284                                 BMVert *v_delimit = (&edge_arr[i]->v1)[j];
1285                                 BMVert *v_other;
1286
1287                                 /* note, remapping will _never_ map a vertex to an already mapped vertex */
1288                                 while (UNLIKELY((v_other = bm_face_split_edgenet_partial_connect(bm, v_delimit, f)))) {
1289                                         struct TempVertPair *tvp = BLI_memarena_alloc(mem_arena, sizeof(*tvp));
1290                                         tvp->next = temp_vert_pairs.list;
1291                                         tvp->v_orig = v_delimit;
1292                                         tvp->v_temp = v_other;
1293                                         temp_vert_pairs.list = tvp;
1294                                         temp_vert_pairs.len++;
1295                                 }
1296                         }
1297                 }
1298
1299                 if (temp_vert_pairs.len == 0) {
1300                         use_partial_connect = false;
1301                 }
1302         }
1303 #endif  /* USE_PARTIAL_CONNECT */
1304
1305
1306
1307         uint group_arr_len = 0;
1308         LinkNode *group_head = NULL;
1309         {
1310                 /* scan 'edge_arr' backwards so the outer face boundary is handled first
1311                  * (since its likely to be the largest) */
1312                 uint edge_index = (edge_arr_len - 1);
1313                 uint edge_in_group_tot = 0;
1314
1315                 BLI_SMALLSTACK_DECLARE(vstack, BMVert *);
1316
1317                 while (true) {
1318                         LinkNode *edge_links = NULL;
1319                         uint unique_verts_in_group = 0, unique_edges_in_group = 0;
1320
1321                         /* list of groups */
1322                         BLI_assert(BM_elem_flag_test(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK));
1323                         BLI_SMALLSTACK_PUSH(vstack, edge_arr[edge_index]->v1);
1324                         BM_elem_flag_disable(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK);
1325
1326                         BMVert *v_iter;
1327                         while ((v_iter = BLI_SMALLSTACK_POP(vstack))) {
1328                                 unique_verts_in_group++;
1329
1330                                 BMEdge *e_iter = v_iter->e;
1331                                 do {
1332                                         if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
1333                                                 BM_elem_flag_disable(e_iter, EDGE_NOT_IN_STACK);
1334                                                 unique_edges_in_group++;
1335
1336                                                 BLI_linklist_prepend_alloca(&edge_links, e_iter);
1337
1338                                                 BMVert *v_other = BM_edge_other_vert(e_iter, v_iter);
1339                                                 if (BM_elem_flag_test(v_other, VERT_NOT_IN_STACK)) {
1340                                                         BLI_SMALLSTACK_PUSH(vstack, v_other);
1341                                                         BM_elem_flag_disable(v_other, VERT_NOT_IN_STACK);
1342                                                 }
1343                                         }
1344                                 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != v_iter->e);
1345                         }
1346
1347                         struct EdgeGroupIsland *g = alloca(sizeof(*g));
1348                         g->vert_len = unique_verts_in_group;
1349                         g->edge_len = unique_edges_in_group;
1350                         edge_in_group_tot += unique_edges_in_group;
1351
1352                         BLI_linklist_prepend_nlink(&group_head, edge_links, (LinkNode *)g);
1353
1354                         group_arr_len++;
1355
1356                         if (edge_in_group_tot == edge_arr_len) {
1357                                 break;
1358                         }
1359
1360                         /* skip edges in the stack */
1361                         while (BM_elem_flag_test(edge_arr[edge_index], EDGE_NOT_IN_STACK) == false) {
1362                                 BLI_assert(edge_index != 0);
1363                                 edge_index--;
1364                         }
1365                 }
1366         }
1367
1368         /* single group - no holes */
1369         if (group_arr_len == 1) {
1370                 goto finally;
1371         }
1372
1373
1374         /* -------------------------------------------------------------------- */
1375         /* Previous checks need to be kept fast, since they will run very often,
1376          * now we know there are holes, so calculate a spatial lookup info and
1377          * other per-group data.
1378          */
1379
1380         float axis_mat[3][3];
1381         axis_dominant_v3_to_m3(axis_mat, f->no);
1382
1383 #define VERT_IN_ARRAY BM_ELEM_INTERNAL_TAG
1384
1385         struct EdgeGroupIsland **group_arr = BLI_memarena_alloc(mem_arena, sizeof(*group_arr) * group_arr_len);
1386         uint vert_arr_len = 0;
1387         /* sort groups by lowest value vertex */
1388         {
1389                 /* fill 'groups_arr' in reverse order so the boundary face is first */
1390                 struct EdgeGroupIsland **group_arr_p = &group_arr[group_arr_len];
1391
1392                 for (struct EdgeGroupIsland *g = (void *)group_head; g; g = (struct EdgeGroupIsland *)g->edge_links.next) {
1393                         LinkNode *edge_links = g->edge_links.link;
1394
1395                         /* init with *any* different verts */
1396                         g->vert_span.min = ((BMEdge *)edge_links->link)->v1;
1397                         g->vert_span.max = ((BMEdge *)edge_links->link)->v2;
1398                         float min_axis[2] =  {FLT_MAX, FLT_MAX};
1399                         float max_axis[2] = {-FLT_MAX, -FLT_MAX};
1400
1401                         do {
1402                                 BMEdge *e = edge_links->link;
1403                                 BLI_assert(e->head.htype == BM_EDGE);
1404
1405                                 for (int j = 0; j < 2; j++) {
1406                                         BMVert *v_iter = (&e->v1)[j];
1407                                         BLI_assert(v_iter->head.htype == BM_VERT);
1408                                         /* ideally we could use 'v_iter->co[SORT_AXIS]' here,
1409                                          * but we need to sort the groups before setting the vertex array order */
1410                                         const float axis_value[2] = {
1411 #if SORT_AXIS == 0
1412                                             dot_m3_v3_row_x(axis_mat, v_iter->co),
1413                                             dot_m3_v3_row_y(axis_mat, v_iter->co),
1414 #else
1415                                             dot_m3_v3_row_y(axis_mat, v_iter->co),
1416                                             dot_m3_v3_row_x(axis_mat, v_iter->co),
1417 #endif
1418                                         };
1419
1420                                         if (axis_pt_cmp(axis_value, min_axis) == -1) {
1421                                                 g->vert_span.min = v_iter;
1422                                                 copy_v2_v2(min_axis, axis_value);
1423                                         }
1424                                         if (axis_pt_cmp(axis_value, max_axis) == 1) {
1425                                                 g->vert_span.max = v_iter;
1426                                                 copy_v2_v2(max_axis, axis_value);
1427                                         }
1428                                 }
1429                         } while ((edge_links = edge_links->next));
1430
1431                         copy_v2_v2(g->vert_span.min_axis, min_axis);
1432                         copy_v2_v2(g->vert_span.max_axis, max_axis);
1433
1434                         g->has_prev_edge = false;
1435
1436                         vert_arr_len += g->vert_len;
1437
1438                         *(--group_arr_p) = g;
1439                 }
1440         }
1441
1442         qsort(group_arr, group_arr_len, sizeof(*group_arr), group_min_cmp_fn);
1443
1444         /* we don't know how many unique verts there are connecting the edges, so over-alloc */
1445         BMVert **vert_arr = BLI_memarena_alloc(mem_arena, sizeof(*vert_arr) * vert_arr_len);
1446         /* map vertex -> group index */
1447         uint *verts_group_table = BLI_memarena_alloc(mem_arena, sizeof(*verts_group_table) * vert_arr_len);
1448
1449         float (*vert_coords_backup)[3] = BLI_memarena_alloc(mem_arena, sizeof(*vert_coords_backup) * vert_arr_len);
1450
1451         {
1452                 /* relative location, for higher precision calculations */
1453                 const float f_co_ref[3] = {UNPACK3(BM_FACE_FIRST_LOOP(f)->v->co)};
1454
1455                 int v_index = 0;  /* global vert index */
1456                 for (uint g_index = 0; g_index < group_arr_len; g_index++) {
1457                         LinkNode *edge_links = group_arr[g_index]->edge_links.link;
1458                         do {
1459                                 BMEdge *e = edge_links->link;
1460                                 for (int j = 0; j < 2; j++) {
1461                                         BMVert *v_iter = (&e->v1)[j];
1462                                         if (!BM_elem_flag_test(v_iter, VERT_IN_ARRAY)) {
1463                                                 BM_elem_flag_enable(v_iter, VERT_IN_ARRAY);
1464
1465                                                 /* not nice, but alternatives arent much better :S */
1466                                                 {
1467                                                         copy_v3_v3(vert_coords_backup[v_index], v_iter->co);
1468
1469                                                         /* for higher precision */
1470                                                         sub_v3_v3(v_iter->co, f_co_ref);
1471
1472                                                         float co_2d[2];
1473                                                         mul_v2_m3v3(co_2d, axis_mat, v_iter->co);
1474                                                         v_iter->co[0] = co_2d[0];
1475                                                         v_iter->co[1] = co_2d[1];
1476                                                         v_iter->co[2] = 0.0f;
1477                                                 }
1478
1479                                                 BM_elem_index_set(v_iter, v_index);  /* set_dirty */
1480
1481                                                 vert_arr[v_index] = v_iter;
1482                                                 verts_group_table[v_index] = g_index;
1483                                                 v_index++;
1484                                         }
1485                                 }
1486                         } while ((edge_links = edge_links->next));
1487                 }
1488         }
1489
1490         bm->elem_index_dirty |= BM_VERT;
1491
1492         /* Now create bvh tree
1493          *
1494          * Note that a large epsilon is used because meshes with dimensions of around 100+ need it. see T52329. */
1495         BVHTree *bvhtree = BLI_bvhtree_new(edge_arr_len, 1e-4f, 8, 8);
1496         for (uint i = 0; i < edge_arr_len; i++) {
1497                 const float e_cos[2][3] = {
1498                     {UNPACK2(edge_arr[i]->v1->co), 0.0f},
1499                     {UNPACK2(edge_arr[i]->v2->co), 0.0f},
1500                 };
1501                 BLI_bvhtree_insert(bvhtree, i, (const float *)e_cos, 2);
1502         }
1503         BLI_bvhtree_balance(bvhtree);
1504
1505
1506
1507 #ifdef USE_PARTIAL_CONNECT
1508         if (use_partial_connect) {
1509                 /* needs to be done once the vertex indices have been written into */
1510                 temp_vert_pairs.remap = BLI_memarena_alloc(mem_arena, sizeof(*temp_vert_pairs.remap) * vert_arr_len);
1511                 copy_vn_i(temp_vert_pairs.remap, vert_arr_len, -1);
1512
1513                 struct TempVertPair *tvp = temp_vert_pairs.list;
1514                 do {
1515                         temp_vert_pairs.remap[BM_elem_index_get(tvp->v_temp)] = BM_elem_index_get(tvp->v_orig);
1516                 } while ((tvp = tvp->next));
1517         }
1518 #endif  /* USE_PARTIAL_CONNECT */
1519
1520
1521
1522         /* Create connections between groups */
1523
1524         /* may be an over-alloc, but not by much */
1525         edge_net_new_len = (uint)edge_net_init_len + ((group_arr_len - 1) * 2);
1526         BMEdge **edge_net_new = BLI_memarena_alloc(mem_arena, sizeof(*edge_net_new) * edge_net_new_len);
1527         memcpy(edge_net_new, edge_net_init, sizeof(*edge_net_new) * (size_t)edge_net_init_len);
1528
1529         {
1530                 uint edge_net_new_index = edge_net_init_len;
1531                 /* start-end of the verts in the current group */
1532
1533                 uint vert_range[2];
1534
1535                 vert_range[0] = 0;
1536                 vert_range[1] = group_arr[0]->vert_len;
1537
1538                 struct EdgeGroup_FindConnection_Args args = {
1539                         .bvhtree = bvhtree,
1540
1541                         /* use the new edge array so we can scan edges which have been added */
1542                         .edge_arr = edge_arr,
1543                         .edge_arr_len = edge_arr_len,
1544
1545                         /* we only want to check newly created edges */
1546                         .edge_arr_new = edge_net_new + edge_net_init_len,
1547                         .edge_arr_new_len = 0,
1548
1549                         .vert_range = vert_range,
1550                 };
1551
1552                 for (uint g_index = 1; g_index < group_arr_len; g_index++) {
1553                         struct EdgeGroupIsland *g = group_arr[g_index];
1554
1555                         /* the range of verts this group uses in 'verts_arr' (not uncluding the last index) */
1556                         vert_range[0]  = vert_range[1];
1557                         vert_range[1] += g->vert_len;
1558
1559                         if (g->has_prev_edge == false) {
1560                                 BMVert *v_origin = g->vert_span.min;
1561
1562                                 const int index_other = bm_face_split_edgenet_find_connection(&args, v_origin, false);
1563                                 // BLI_assert(index_other >= 0 && index_other < (int)vert_arr_len);
1564
1565                                 /* only for degenerate geometry */
1566                                 if (index_other != -1) {
1567 #ifdef USE_PARTIAL_CONNECT
1568                                         if ((use_partial_connect == false) ||
1569                                             (bm_vert_partial_connect_check_overlap(
1570                                                  temp_vert_pairs.remap,
1571                                                  BM_elem_index_get(v_origin), index_other) == false))
1572 #endif
1573                                         {
1574                                                 BMVert *v_end = vert_arr[index_other];
1575
1576                                                 edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0);
1577 #ifdef USE_PARTIAL_CONNECT
1578                                                 BM_elem_index_set(edge_net_new[edge_net_new_index], edge_net_new_index);
1579 #endif
1580                                                 edge_net_new_index++;
1581                                                 args.edge_arr_new_len++;
1582                                         }
1583                                 }
1584                         }
1585
1586                         {
1587                                 BMVert *v_origin = g->vert_span.max;
1588
1589                                 const int index_other = bm_face_split_edgenet_find_connection(&args, v_origin, true);
1590                                 // BLI_assert(index_other >= 0 && index_other < (int)vert_arr_len);
1591
1592                                 /* only for degenerate geometry */
1593                                 if (index_other != -1) {
1594 #ifdef USE_PARTIAL_CONNECT
1595                                         if ((use_partial_connect == false) ||
1596                                             (bm_vert_partial_connect_check_overlap(
1597                                                  temp_vert_pairs.remap,
1598                                                  BM_elem_index_get(v_origin), index_other) == false))
1599 #endif
1600                                         {
1601                                                 BMVert *v_end = vert_arr[index_other];
1602                                                 edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0);
1603 #ifdef USE_PARTIAL_CONNECT
1604                                                 BM_elem_index_set(edge_net_new[edge_net_new_index], edge_net_new_index);
1605 #endif
1606                                                 edge_net_new_index++;
1607                                                 args.edge_arr_new_len++;
1608                                         }
1609
1610                                         /* tell the 'next' group it doesn't need to create its own back-link */
1611                                         uint g_index_other = verts_group_table[index_other];
1612                                         group_arr[g_index_other]->has_prev_edge = true;
1613                                 }
1614                         }
1615
1616                 }
1617                 BLI_assert(edge_net_new_len >= edge_net_new_index);
1618                 edge_net_new_len = edge_net_new_index;
1619         }
1620
1621         BLI_bvhtree_free(bvhtree);
1622
1623         *r_edge_net_new = edge_net_new;
1624         *r_edge_net_new_len = edge_net_new_len;
1625         ok = true;
1626
1627         for (uint i = 0; i < vert_arr_len; i++) {
1628                 copy_v3_v3(vert_arr[i]->co, vert_coords_backup[i]);
1629         }
1630
1631 finally:
1632
1633 #ifdef USE_PARTIAL_CONNECT
1634         /* don't free 'vert_temp_pair_list', its part of the arena */
1635         if (use_partial_connect) {
1636
1637                 /* Sanity check: ensure we don't have connecting edges before splicing begins. */
1638 #ifdef DEBUG
1639                 {
1640                         struct TempVertPair *tvp = temp_vert_pairs.list;
1641                         do {
1642                                 /* we must _never_ create connections here
1643                                  * (inface the islands can't have a connection at all) */
1644                                 BLI_assert(BM_edge_exists(tvp->v_orig, tvp->v_temp) == NULL);
1645                         } while ((tvp = tvp->next));
1646                 }
1647 #endif
1648
1649                 struct TempVertPair *tvp = temp_vert_pairs.list;
1650                 do {
1651                         /* its _very_ unlikely the edge exists,
1652                          * however splicing may case this. see: T48012 */
1653                         if (!BM_edge_exists(tvp->v_orig, tvp->v_temp)) {
1654                                 BM_vert_splice(bm, tvp->v_orig, tvp->v_temp);
1655                         }
1656                 } while ((tvp = tvp->next));
1657
1658                 /* Remove edges which have become doubles since splicing vertices together,
1659                  * its less trouble then detecting future-doubles on edge-creation. */
1660                 for (uint i = edge_net_init_len; i < edge_net_new_len; i++) {
1661                         while (BM_edge_find_double(edge_net_new[i])) {
1662                                 BM_edge_kill(bm, edge_net_new[i]);
1663                                 edge_net_new_len--;
1664                                 if (i == edge_net_new_len) {
1665                                         break;
1666                                 }
1667                                 edge_net_new[i] = edge_net_new[edge_net_new_len];
1668                         }
1669                 }
1670
1671                 *r_edge_net_new_len = edge_net_new_len;
1672         }
1673 #endif
1674
1675
1676         for (uint i = 0; i < edge_arr_len; i++) {
1677                 BM_elem_flag_disable(edge_arr[i], EDGE_NOT_IN_STACK);
1678                 BM_elem_flag_disable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
1679                 BM_elem_flag_disable(edge_arr[i]->v2, VERT_NOT_IN_STACK);
1680         }
1681
1682 #undef VERT_IN_ARRAY
1683 #undef VERT_NOT_IN_STACK
1684 #undef EDGE_NOT_IN_STACK
1685
1686         return ok;
1687 }
1688
1689 #undef SORT_AXIS
1690
1691 /** \} */