Merge branch 'master' into blender2.8
[blender.git] / source / blender / bmesh / tools / bmesh_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/bmesh/tools/bmesh_intersect.c
22  *  \ingroup bmesh
23  *
24  * Cut meshes along intersections.
25  *
26  * Boolean-like modeling operation (without calculating inside/outside).
27  *
28  * Supported:
29  * - Concave faces.
30  * - Non-planar faces.
31  * - Custom-data (UV's etc).
32  *
33  * Unsupported:
34  * - Intersecting between different meshes.
35  * - No support for holes (cutting a hole into a single face).
36  */
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_math.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_memarena.h"
43 #include "BLI_alloca.h"
44 #include "BLI_sort_utils.h"
45
46 #include "BLI_linklist_stack.h"
47 #include "BLI_stackdefines.h"
48 #ifndef NDEBUG
49 #  include "BLI_array_utils.h"
50 #endif
51
52 #include "BLI_kdopbvh.h"
53 #include "BLI_buffer.h"
54
55 #include "bmesh.h"
56 #include "intern/bmesh_private.h"
57
58 #include "bmesh_intersect.h"  /* own include */
59
60 #include "tools/bmesh_edgesplit.h"
61
62 #include "BLI_strict_flags.h"
63
64 /*
65  * Some of these depend on each other:
66  */
67
68 /* splice verts into existing edges */
69 #define USE_SPLICE
70 /* split faces by intersecting edges */
71 #define USE_NET
72 /* split resulting edges */
73 #define USE_SEPARATE
74 /* remove verts created by intersecting triangles */
75 #define USE_DISSOLVE
76 /* detect isolated holes and fill them */
77 #define USE_NET_ISLAND_CONNECT
78
79 /* strict asserts that may fail in practice (handy for debugging cases which should succeed) */
80 // #define USE_PARANOID
81 /* use accelerated overlap check */
82 #define USE_BVH
83
84 // #define USE_DUMP
85
86 static void tri_v3_scale(
87         float v1[3], float v2[3], float v3[3],
88         const float t)
89 {
90         float p[3];
91
92         mid_v3_v3v3v3(p, v1, v2, v3);
93
94         interp_v3_v3v3(v1, p, v1, t);
95         interp_v3_v3v3(v2, p, v2, t);
96         interp_v3_v3v3(v3, p, v3, t);
97 }
98
99 #ifdef USE_DISSOLVE
100 /* other edge when a vert only has 2 edges */
101 static BMEdge *bm_vert_other_edge(BMVert *v, BMEdge *e)
102 {
103         BLI_assert(BM_vert_is_edge_pair(v));
104         BLI_assert(BM_vert_in_edge(e, v));
105
106         if (v->e != e) {
107                 return v->e;
108         }
109         else {
110                 return BM_DISK_EDGE_NEXT(v->e, v);
111         }
112 }
113 #endif
114
115 enum ISectType {
116         IX_NONE = -1,
117         IX_EDGE_TRI_EDGE0,
118         IX_EDGE_TRI_EDGE1,
119         IX_EDGE_TRI_EDGE2,
120         IX_EDGE_TRI,
121         IX_TOT,
122 };
123
124 struct ISectEpsilon {
125         float eps, eps_sq;
126         float eps2x, eps2x_sq;
127         float eps_margin, eps_margin_sq;
128 };
129
130 struct ISectState {
131         BMesh *bm;
132         GHash *edgetri_cache;  /* int[4]: BMVert */
133         GHash *edge_verts;  /* BMEdge: LinkList(of verts), new and original edges */
134         GHash *face_edges;  /* BMFace-index: LinkList(of edges), only original faces */
135         GSet  *wire_edges;  /* BMEdge  (could use tags instead) */
136         LinkNode *vert_dissolve;  /* BMVert's */
137
138         MemArena *mem_arena;
139
140         struct ISectEpsilon epsilon;
141 };
142
143 /**
144  * Store as value in GHash so we can get list-length without counting every time.
145  * Also means we don't need to update the GHash value each time.
146  */
147 struct LinkBase {
148         LinkNode    *list;
149         uint list_len;
150 };
151
152 static bool ghash_insert_link(
153         GHash *gh, void *key, void *val, bool use_test,
154         MemArena *mem_arena)
155 {
156         void           **ls_base_p;
157         struct LinkBase *ls_base;
158         LinkNode *ls;
159
160         if (!BLI_ghash_ensure_p(gh, key, &ls_base_p)) {
161                 ls_base = *ls_base_p = BLI_memarena_alloc(mem_arena, sizeof(*ls_base));
162                 ls_base->list     = NULL;
163                 ls_base->list_len = 0;
164         }
165         else {
166                 ls_base = *ls_base_p;
167                 if (use_test && (BLI_linklist_index(ls_base->list, val) != -1)) {
168                         return false;
169                 }
170         }
171
172         ls = BLI_memarena_alloc(mem_arena, sizeof(*ls));
173         ls->next = ls_base->list;
174         ls->link = val;
175         ls_base->list = ls;
176         ls_base->list_len += 1;
177
178         return true;
179 }
180
181 struct vert_sort_t {
182         float val;
183         BMVert *v;
184 };
185
186 #ifdef USE_SPLICE
187 static void edge_verts_sort(const float co[3], struct LinkBase *v_ls_base)
188 {
189         /* not optimal but list will be typically < 5 */
190         uint i;
191         struct vert_sort_t *vert_sort = BLI_array_alloca(vert_sort, v_ls_base->list_len);
192         LinkNode *node;
193
194         BLI_assert(v_ls_base->list_len > 1);
195
196         for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
197                 BMVert *v = node->link;
198                 BLI_assert(v->head.htype == BM_VERT);
199                 vert_sort[i].val = len_squared_v3v3(co, v->co);
200                 vert_sort[i].v   = v;
201         }
202
203         qsort(vert_sort, v_ls_base->list_len, sizeof(*vert_sort), BLI_sortutil_cmp_float);
204
205         for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
206                 node->link = vert_sort[i].v;
207         }
208 }
209 #endif
210
211 static void edge_verts_add(
212         struct ISectState *s,
213         BMEdge *e,
214         BMVert *v,
215         const bool use_test
216         )
217 {
218         BLI_assert(e->head.htype == BM_EDGE);
219         BLI_assert(v->head.htype == BM_VERT);
220         ghash_insert_link(s->edge_verts, (void *)e, v, use_test, s->mem_arena);
221 }
222
223 static void face_edges_add(
224         struct ISectState *s,
225         const int f_index,
226         BMEdge *e,
227         const bool use_test)
228 {
229         void *f_index_key = SET_INT_IN_POINTER(f_index);
230         BLI_assert(e->head.htype == BM_EDGE);
231         BLI_assert(BM_edge_in_face(e, s->bm->ftable[f_index]) == false);
232         BLI_assert(BM_elem_index_get(s->bm->ftable[f_index]) == f_index);
233
234         ghash_insert_link(s->face_edges, f_index_key, e, use_test, s->mem_arena);
235 }
236
237 #ifdef USE_NET
238 static void face_edges_split(
239         BMesh *bm, BMFace *f, struct LinkBase *e_ls_base,
240         bool use_island_connect,
241         MemArena *mem_arena_edgenet)
242 {
243         uint i;
244         uint edge_arr_len = e_ls_base->list_len;
245         BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len);
246         LinkNode *node;
247         BLI_assert(f->head.htype == BM_FACE);
248
249         for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) {
250                 edge_arr[i] = node->link;
251         }
252         BLI_assert(node == NULL);
253
254 #ifdef USE_DUMP
255         printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len);
256 #endif
257
258 #ifdef USE_NET_ISLAND_CONNECT
259         if (use_island_connect) {
260                 uint edge_arr_holes_len;
261                 BMEdge **edge_arr_holes;
262                 if (BM_face_split_edgenet_connect_islands(
263                         bm, f,
264                         edge_arr, edge_arr_len,
265                         false,
266                         mem_arena_edgenet,
267                         &edge_arr_holes, &edge_arr_holes_len))
268                 {
269                         edge_arr_len = edge_arr_holes_len;
270                         edge_arr = edge_arr_holes;  /* owned by the arena */
271                 }
272         }
273 #else
274         UNUSED_VARS(use_island_connect, mem_arena_edgenet);
275 #endif
276
277         BM_face_split_edgenet(bm, f, edge_arr, (int)edge_arr_len, NULL, NULL);
278 }
279 #endif
280
281 #ifdef USE_DISSOLVE
282 static void vert_dissolve_add(
283         struct ISectState *s,
284         BMVert *v)
285 {
286         BLI_assert(v->head.htype == BM_VERT);
287         BLI_assert(!BM_elem_flag_test(v, BM_ELEM_TAG));
288         BLI_assert(BLI_linklist_index(s->vert_dissolve, v) == -1);
289
290         BM_elem_flag_enable(v, BM_ELEM_TAG);
291         BLI_linklist_prepend_arena(&s->vert_dissolve, v, s->mem_arena);
292 }
293 #endif
294
295 static enum ISectType intersect_line_tri(
296         const float p0[3], const float p1[3],
297         const float *t_cos[3], const float t_nor[3],
298         float r_ix[3],
299         const struct ISectEpsilon *e)
300 {
301         float p_dir[3];
302         uint i_t0;
303         float fac;
304
305         sub_v3_v3v3(p_dir, p0, p1);
306         normalize_v3(p_dir);
307
308         for (i_t0 = 0; i_t0 < 3; i_t0++) {
309                 const uint i_t1 = (i_t0 + 1) % 3;
310                 float te_dir[3];
311
312                 sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]);
313                 normalize_v3(te_dir);
314                 if (fabsf(dot_v3v3(p_dir, te_dir)) >= 1.0f - e->eps) {
315                         /* co-linear */
316                 }
317                 else {
318                         float ix_pair[2][3];
319                         int ix_pair_type;
320
321                         ix_pair_type = isect_line_line_epsilon_v3(p0, p1, t_cos[i_t0], t_cos[i_t1], ix_pair[0], ix_pair[1], 0.0f);
322
323                         if (ix_pair_type != 0) {
324                                 if (ix_pair_type == 1) {
325                                         copy_v3_v3(ix_pair[1], ix_pair[0]);
326                                 }
327
328                                 if ((ix_pair_type == 1) ||
329                                     (len_squared_v3v3(ix_pair[0], ix_pair[1]) <= e->eps_margin_sq))
330                                 {
331                                         fac = line_point_factor_v3(ix_pair[1], t_cos[i_t0], t_cos[i_t1]);
332                                         if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
333                                                 fac = line_point_factor_v3(ix_pair[0], p0, p1);
334                                                 if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
335                                                         copy_v3_v3(r_ix, ix_pair[0]);
336                                                         return (IX_EDGE_TRI_EDGE0 + (enum ISectType)i_t0);
337                                                 }
338                                         }
339                                 }
340                         }
341                 }
342         }
343
344         /* check ray isn't planar with tri */
345         if (fabsf(dot_v3v3(p_dir, t_nor)) >= e->eps) {
346                 if (isect_line_segment_tri_epsilon_v3(p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac, NULL, 0.0f)) {
347                         if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
348                                 interp_v3_v3v3(r_ix, p0, p1, fac);
349                                 if (min_fff(len_squared_v3v3(t_cos[0], r_ix),
350                                             len_squared_v3v3(t_cos[1], r_ix),
351                                             len_squared_v3v3(t_cos[2], r_ix)) >= e->eps_margin_sq)
352                                 {
353                                         return IX_EDGE_TRI;
354                                 }
355                         }
356                 }
357         }
358
359         /* r_ix may be unset */
360         return IX_NONE;
361 }
362
363 static BMVert *bm_isect_edge_tri(
364         struct ISectState *s,
365         BMVert *e_v0, BMVert *e_v1,
366         BMVert *t[3], const int t_index,
367         const float *t_cos[3], const float t_nor[3],
368         enum ISectType *r_side)
369 {
370         BMesh *bm = s->bm;
371         int k_arr[IX_TOT][4];
372         uint i;
373         const int ti[3] = {UNPACK3_EX(BM_elem_index_get, t, )};
374         float ix[3];
375
376         if (BM_elem_index_get(e_v0) > BM_elem_index_get(e_v1)) {
377                 SWAP(BMVert *, e_v0, e_v1);
378         }
379
380 #ifdef USE_PARANOID
381         BLI_assert(len_squared_v3v3(e_v0->co, t[0]->co) >= s->epsilon.eps_sq);
382         BLI_assert(len_squared_v3v3(e_v0->co, t[1]->co) >= s->epsilon.eps_sq);
383         BLI_assert(len_squared_v3v3(e_v0->co, t[2]->co) >= s->epsilon.eps_sq);
384         BLI_assert(len_squared_v3v3(e_v1->co, t[0]->co) >= s->epsilon.eps_sq);
385         BLI_assert(len_squared_v3v3(e_v1->co, t[1]->co) >= s->epsilon.eps_sq);
386         BLI_assert(len_squared_v3v3(e_v1->co, t[2]->co) >= s->epsilon.eps_sq);
387 #endif
388
389 #define KEY_SET(k, i0, i1, i2, i3) { \
390         (k)[0] = i0; \
391         (k)[1] = i1; \
392         (k)[2] = i2; \
393         (k)[3] = i3; \
394 } (void)0
395
396         /* order tri, then order (1-2, 2-3)*/
397 #define KEY_EDGE_TRI_ORDER(k) { \
398         if (k[2] > k[3]) { \
399                 SWAP(int, k[2], k[3]); \
400         } \
401         if (k[0] > k[2]) { \
402                 SWAP(int, k[0], k[2]); \
403                 SWAP(int, k[1], k[3]); \
404         } \
405 } (void)0
406
407         KEY_SET(k_arr[IX_EDGE_TRI], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), t_index, -1);
408         /* need to order here */
409         KEY_SET(k_arr[IX_EDGE_TRI_EDGE0], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[0], ti[1]);
410         KEY_SET(k_arr[IX_EDGE_TRI_EDGE1], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[1], ti[2]);
411         KEY_SET(k_arr[IX_EDGE_TRI_EDGE2], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[2], ti[0]);
412
413         KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE0]);
414         KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE1]);
415         KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE2]);
416
417 #undef KEY_SET
418 #undef KEY_EDGE_TRI_ORDER
419
420
421
422         for (i = 0; i < ARRAY_SIZE(k_arr); i++) {
423                 BMVert *iv;
424
425                 iv = BLI_ghash_lookup(s->edgetri_cache, k_arr[i]);
426
427                 if (iv) {
428 #ifdef USE_DUMP
429                         printf("# cache hit (%d, %d, %d, %d)\n", UNPACK4(k_arr[i]));
430 #endif
431                         *r_side = (enum ISectType)i;
432                         return iv;
433                 }
434         }
435
436         *r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon);
437         if (*r_side != IX_NONE) {
438                 BMVert *iv;
439                 BMEdge *e;
440 #ifdef USE_DUMP
441                 printf("# new vertex (%.6f, %.6f, %.6f) %d\n", UNPACK3(ix), *r_side);
442 #endif
443
444 #ifdef USE_PARANOID
445                 BLI_assert(len_squared_v3v3(ix, e_v0->co) > s->epsilon.eps_sq);
446                 BLI_assert(len_squared_v3v3(ix, e_v1->co) > s->epsilon.eps_sq);
447                 BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq);
448                 BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq);
449                 BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq);
450 #endif
451                 iv = BM_vert_create(bm, ix, NULL, 0);
452
453                 e = BM_edge_exists(e_v0, e_v1);
454                 if (e) {
455 #ifdef USE_DUMP
456                         printf("# adding to edge %d\n", BM_elem_index_get(e));
457 #endif
458                         edge_verts_add(s, e, iv, false);
459                 }
460                 else {
461 #ifdef USE_DISSOLVE
462                         vert_dissolve_add(s, iv);
463 #endif
464                 }
465
466                 if ((*r_side >= IX_EDGE_TRI_EDGE0) && (*r_side <= IX_EDGE_TRI_EDGE2)) {
467                         i = (uint)(*r_side - IX_EDGE_TRI_EDGE0);
468                         e = BM_edge_exists(t[i], t[(i + 1) % 3]);
469                         if (e) {
470                                 edge_verts_add(s, e, iv, false);
471                         }
472                 }
473
474                 {
475                         int *k = BLI_memarena_alloc(s->mem_arena, sizeof(int[4]));
476                         memcpy(k, k_arr[*r_side], sizeof(int[4]));
477                         BLI_ghash_insert(s->edgetri_cache, k, iv);
478                 }
479
480                 return iv;
481
482         }
483
484         *r_side = IX_NONE;
485
486         return NULL;
487 }
488
489 struct LoopFilterWrap {
490         int (*test_fn)(BMFace *f, void *user_data);
491         void *user_data;
492 };
493
494 static bool bm_loop_filter_fn(const BMLoop *l, void *user_data)
495 {
496         if (BM_elem_flag_test(l->e, BM_ELEM_TAG)) {
497                 return false;
498         }
499
500         if (l->radial_next != l) {
501                 struct LoopFilterWrap *data = user_data;
502                 BMLoop *l_iter = l->radial_next;
503                 const int face_side = data->test_fn(l->f, data->user_data);
504                 do {
505                         const int face_side_other = data->test_fn(l_iter->f, data->user_data);
506                         if (UNLIKELY(face_side_other == -1)) {
507                                 /* pass */
508                         }
509                         else if (face_side_other != face_side) {
510                                 return false;
511                         }
512                 } while ((l_iter = l_iter->radial_next) != l);
513                 return true;
514         }
515         return false;
516 }
517
518 /**
519  * Return true if we have any intersections.
520  */
521 static void bm_isect_tri_tri(
522         struct ISectState *s,
523         int a_index, int b_index,
524         BMLoop **a, BMLoop **b)
525 {
526         BMFace *f_a = (*a)->f;
527         BMFace *f_b = (*b)->f;
528         BMVert *fv_a[3] = {UNPACK3_EX(, a, ->v)};
529         BMVert *fv_b[3] = {UNPACK3_EX(, b, ->v)};
530         const float *f_a_cos[3] = {UNPACK3_EX(, fv_a, ->co)};
531         const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)};
532         float f_a_nor[3];
533         float f_b_nor[3];
534         uint i;
535
536
537         /* should be enough but may need to bump */
538         BMVert *iv_ls_a[8];
539         BMVert *iv_ls_b[8];
540         STACK_DECLARE(iv_ls_a);
541         STACK_DECLARE(iv_ls_b);
542
543         if (UNLIKELY(ELEM(fv_a[0], UNPACK3(fv_b)) ||
544                      ELEM(fv_a[1], UNPACK3(fv_b)) ||
545                      ELEM(fv_a[2], UNPACK3(fv_b))))
546         {
547                 return;
548         }
549
550         STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a));
551         STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b));
552
553 #define VERT_VISIT_A _FLAG_WALK
554 #define VERT_VISIT_B _FLAG_WALK_ALT
555
556 #define STACK_PUSH_TEST_A(ele) \
557         if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \
558                 BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \
559                 STACK_PUSH(iv_ls_a, ele); \
560         } ((void)0)
561
562 #define STACK_PUSH_TEST_B(ele) \
563         if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \
564                 BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \
565                 STACK_PUSH(iv_ls_b, ele); \
566         } ((void)0)
567
568
569         /* vert-vert
570          * --------- */
571         {
572                 /* first check in any verts are touching
573                  * (any case where we wont create new verts)
574                  */
575                 uint i_a;
576                 for (i_a = 0; i_a < 3; i_a++) {
577                         uint i_b;
578                         for (i_b = 0; i_b < 3; i_b++) {
579                                 if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
580 #ifdef USE_DUMP
581                                         if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT) == 0) {
582                                                 printf("  ('VERT-VERT-A') %d, %d),\n",
583                                                        i_a, BM_elem_index_get(fv_a[i_a]));
584                                         }
585                                         if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT) == 0) {
586                                                 printf("  ('VERT-VERT-B') %d, %d),\n",
587                                                        i_b, BM_elem_index_get(fv_b[i_b]));
588                                         }
589 #endif
590                                         STACK_PUSH_TEST_A(fv_a[i_a]);
591                                         STACK_PUSH_TEST_B(fv_b[i_b]);
592                                 }
593                         }
594                 }
595         }
596
597         /* vert-edge
598          * --------- */
599         {
600                 uint i_a;
601                 for (i_a = 0; i_a < 3; i_a++) {
602                         if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {
603                                 uint i_b_e0;
604                                 for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
605                                         uint i_b_e1 = (i_b_e0 + 1) % 3;
606
607                                         if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
608                                             BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
609                                         {
610                                                 continue;
611                                         }
612
613                                         const float fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
614                                         if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
615                                                 float ix[3];
616                                                 interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);
617                                                 if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
618                                                         BMEdge *e;
619                                                         STACK_PUSH_TEST_B(fv_a[i_a]);
620                                                         // STACK_PUSH_TEST_A(fv_a[i_a]);
621                                                         e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
622 #ifdef USE_DUMP
623                                                         printf("  ('VERT-EDGE-A', %d, %d),\n",
624                                                                BM_elem_index_get(fv_b[i_b_e0]), BM_elem_index_get(fv_b[i_b_e1]));
625 #endif
626                                                         if (e) {
627 #ifdef USE_DUMP
628                                                                 printf("# adding to edge %d\n", BM_elem_index_get(e));
629 #endif
630                                                                 edge_verts_add(s, e, fv_a[i_a], true);
631                                                         }
632                                                         break;
633                                                 }
634                                         }
635                                 }
636                         }
637                 }
638         }
639
640         {
641                 uint i_b;
642                 for (i_b = 0; i_b < 3; i_b++) {
643                         if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {
644                                 uint i_a_e0;
645                                 for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
646                                         uint i_a_e1 = (i_a_e0 + 1) % 3;
647
648                                         if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
649                                             BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
650                                         {
651                                                 continue;
652                                         }
653
654                                         const float fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
655                                         if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
656                                                 float ix[3];
657                                                 interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);
658                                                 if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
659                                                         BMEdge *e;
660                                                         STACK_PUSH_TEST_A(fv_b[i_b]);
661                                                         // STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
662                                                         e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
663 #ifdef USE_DUMP
664                                                         printf("  ('VERT-EDGE-B', %d, %d),\n",
665                                                                BM_elem_index_get(fv_a[i_a_e0]), BM_elem_index_get(fv_a[i_a_e1]));
666 #endif
667                                                         if (e) {
668 #ifdef USE_DUMP
669                                                                 printf("# adding to edge %d\n", BM_elem_index_get(e));
670 #endif
671                                                                 edge_verts_add(s, e, fv_b[i_b], true);
672                                                         }
673                                                         break;
674                                                 }
675                                         }
676                                 }
677                         }
678                 }
679         }
680
681         /* vert-tri
682          * -------- */
683         {
684
685                 float t_scale[3][3];
686                 uint i_a;
687
688                 copy_v3_v3(t_scale[0], fv_b[0]->co);
689                 copy_v3_v3(t_scale[1], fv_b[1]->co);
690                 copy_v3_v3(t_scale[2], fv_b[2]->co);
691                 tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
692
693                 // second check for verts intersecting the triangle
694                 for (i_a = 0; i_a < 3; i_a++) {
695                         if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A)) {
696                                 continue;
697                         }
698
699                         float ix[3];
700                         if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {
701                                 if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
702                                         STACK_PUSH_TEST_A(fv_a[i_a]);
703                                         STACK_PUSH_TEST_B(fv_a[i_a]);
704 #ifdef USE_DUMP
705                                         printf("  'VERT TRI-A',\n");
706 #endif
707                                 }
708                         }
709                 }
710         }
711
712         {
713                 float t_scale[3][3];
714                 uint i_b;
715
716                 copy_v3_v3(t_scale[0], fv_a[0]->co);
717                 copy_v3_v3(t_scale[1], fv_a[1]->co);
718                 copy_v3_v3(t_scale[2], fv_a[2]->co);
719                 tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
720
721                 for (i_b = 0; i_b < 3; i_b++) {
722                         if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) {
723                                 continue;
724                         }
725
726                         float ix[3];
727                         if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {
728                                 if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
729                                         STACK_PUSH_TEST_A(fv_b[i_b]);
730                                         STACK_PUSH_TEST_B(fv_b[i_b]);
731 #ifdef USE_DUMP
732                                         printf("  'VERT TRI-B',\n");
733 #endif
734                                 }
735                         }
736                 }
737         }
738
739         if ((STACK_SIZE(iv_ls_a) >= 3) &&
740             (STACK_SIZE(iv_ls_b) >= 3))
741         {
742 #ifdef USE_DUMP
743                 printf("# OVERLAP\n");
744 #endif
745                 goto finally;
746         }
747
748         normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));
749         normal_tri_v3(f_b_nor, UNPACK3(f_b_cos));
750
751         /* edge-tri & edge-edge
752          * -------------------- */
753         {
754                 for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
755                         uint i_a_e1 = (i_a_e0 + 1) % 3;
756                         enum ISectType side;
757                         BMVert *iv;
758
759                         if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
760                             BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
761                         {
762                                 continue;
763                         }
764
765                         iv = bm_isect_edge_tri(s, fv_a[i_a_e0], fv_a[i_a_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
766                         if (iv) {
767                                 STACK_PUSH_TEST_A(iv);
768                                 STACK_PUSH_TEST_B(iv);
769 #ifdef USE_DUMP
770                                 printf("  ('EDGE-TRI-A', %d),\n", side);
771 #endif
772                         }
773                 }
774
775                 for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
776                         uint i_b_e1 = (i_b_e0 + 1) % 3;
777                         enum ISectType side;
778                         BMVert *iv;
779
780                         if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
781                             BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
782                         {
783                                 continue;
784                         }
785
786                         iv = bm_isect_edge_tri(s, fv_b[i_b_e0], fv_b[i_b_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
787                         if (iv) {
788                                 STACK_PUSH_TEST_A(iv);
789                                 STACK_PUSH_TEST_B(iv);
790 #ifdef USE_DUMP
791                                 printf("  ('EDGE-TRI-B', %d),\n", side);
792 #endif
793                         }
794                 }
795         }
796
797         {
798                 for (i = 0; i < 2; i++) {
799                         BMVert **ie_vs;
800                         BMFace *f;
801                         bool ie_exists;
802                         BMEdge *ie;
803
804                         if (i == 0) {
805                                 if (STACK_SIZE(iv_ls_a) != 2)
806                                         continue;
807                                 ie_vs = iv_ls_a;
808                                 f = f_a;
809                         }
810                         else {
811                                 if (STACK_SIZE(iv_ls_b) != 2)
812                                         continue;
813                                 ie_vs = iv_ls_b;
814                                 f = f_b;
815                         }
816
817                         /* possible but unlikely we get this - for edge-edge intersection */
818                         ie = BM_edge_exists(UNPACK2(ie_vs));
819                         if (ie == NULL) {
820                                 ie_exists = false;
821                                 /* one of the verts must be new if we are making an edge
822                                  * ...no, we need this in case 2x quads intersect at either ends.
823                                  * if not (ie_vs[0].index == -1 or ie_vs[1].index == -1):
824                                  *     continue */
825                                 ie = BM_edge_create(s->bm, UNPACK2(ie_vs), NULL, 0);
826                                 BLI_gset_insert(s->wire_edges, ie);
827                         }
828                         else {
829                                 ie_exists = true;
830                                 /* may already exist */
831                                 BLI_gset_add(s->wire_edges, ie);
832
833                                 if (BM_edge_in_face(ie, f)) {
834                                         continue;
835                                 }
836                         }
837
838                         face_edges_add(s, BM_elem_index_get(f), ie, ie_exists);
839                         // BLI_assert(len(ie_vs) <= 2)
840                 }
841         }
842
843 finally:
844         for (i = 0; i < STACK_SIZE(iv_ls_a); i++) {
845                 BM_ELEM_API_FLAG_DISABLE(iv_ls_a[i], VERT_VISIT_A); \
846         }
847         for (i = 0; i < STACK_SIZE(iv_ls_b); i++) {
848                 BM_ELEM_API_FLAG_DISABLE(iv_ls_b[i], VERT_VISIT_B); \
849         }
850
851 }
852
853 #ifdef USE_BVH
854
855 struct RaycastData {
856         const float **looptris;
857         BLI_Buffer *z_buffer;
858 };
859
860 #ifdef USE_KDOPBVH_WATERTIGHT
861 static const struct IsectRayPrecalc isect_precalc_x = {1, 2, 0, 0, 0, 1};
862 #endif
863
864 static void raycast_callback(void *userdata,
865                              int index,
866                              const BVHTreeRay *ray,
867                              BVHTreeRayHit *UNUSED(hit))
868 {
869         struct RaycastData *raycast_data = userdata;
870         const float **looptris = raycast_data->looptris;
871         const float *v0 = looptris[index * 3 + 0];
872         const float *v1 = looptris[index * 3 + 1];
873         const float *v2 = looptris[index * 3 + 2];
874         float dist;
875
876         if (
877 #ifdef USE_KDOPBVH_WATERTIGHT
878             isect_ray_tri_watertight_v3(ray->origin, &isect_precalc_x, v0, v1, v2, &dist, NULL)
879 #else
880             isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON)
881 #endif
882             )
883         {
884                 if (dist >= 0.0f) {
885 #ifdef USE_DUMP
886                         printf("%s:\n", __func__);
887                         print_v3("  origin", ray->origin);
888                         print_v3("  direction", ray->direction);
889                         printf("  dist %f\n", dist);
890                         print_v3("  v0", v0);
891                         print_v3("  v1", v1);
892                         print_v3("  v2", v2);
893 #endif
894
895 #ifdef USE_DUMP
896                         printf("%s: Adding depth %f\n", __func__, dist);
897 #endif
898                         BLI_buffer_append(raycast_data->z_buffer, float, dist);
899                 }
900         }
901 }
902
903 static int isect_bvhtree_point_v3(
904         BVHTree *tree,
905         const float **looptris,
906         const float co[3])
907 {
908         BLI_buffer_declare_static(float, z_buffer, BLI_BUFFER_NOP, 64);
909
910         struct RaycastData raycast_data = {
911                 looptris,
912                 &z_buffer,
913         };
914         BVHTreeRayHit hit = {0};
915         float dir[3] = {1.0f, 0.0f, 0.0f};
916
917         /* Need to initialize hit even tho it's not used.
918          * This is to make it so kdotree believes we didn't intersect anything and
919          * keeps calling the intersect callback.
920          */
921         hit.index = -1;
922         hit.dist = BVH_RAYCAST_DIST_MAX;
923
924         BLI_bvhtree_ray_cast(tree,
925                              co, dir,
926                              0.0f,
927                              &hit,
928                              raycast_callback,
929                              &raycast_data);
930
931 #ifdef USE_DUMP
932         printf("%s: Total intersections: %d\n", __func__, z_buffer.count);
933 #endif
934
935         int num_isect;
936
937         if (z_buffer.count == 0) {
938                 num_isect = 0;
939         }
940         else if (z_buffer.count == 1) {
941                 num_isect = 1;
942         }
943         else {
944                 /* 2 or more */
945                 const float eps = FLT_EPSILON * 10;
946                 num_isect = 1;  /* always count first */
947
948                 qsort(z_buffer.data, z_buffer.count, sizeof(float), BLI_sortutil_cmp_float);
949
950                 const float *depth_arr = z_buffer.data;
951                 float        depth_last = depth_arr[0];
952
953                 for (uint i = 1; i < z_buffer.count; i++) {
954                         if (depth_arr[i] - depth_last > eps) {
955                                 depth_last = depth_arr[i];
956                                 num_isect++;
957                         }
958                 }
959
960                 BLI_buffer_free(&z_buffer);
961         }
962
963
964         //      return (num_isect & 1) == 1;
965         return num_isect;
966 }
967
968 #endif  /* USE_BVH */
969
970 /**
971  * Intersect tessellated faces
972  * leaving the resulting edges tagged.
973  *
974  * \param test_fn Return value: -1: skip, 0: tree_a, 1: tree_b (use_self == false)
975  * \param boolean_mode -1: no-boolean, 0: intersection... see #BMESH_ISECT_BOOLEAN_ISECT.
976  * \return true if the mesh is changed (intersections cut or faces removed from boolean).
977  */
978 bool BM_mesh_intersect(
979         BMesh *bm,
980         struct BMLoop *(*looptris)[3], const int looptris_tot,
981         int (*test_fn)(BMFace *f, void *user_data), void *user_data,
982         const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect,
983         const bool use_edge_tag, const int boolean_mode,
984         const float eps)
985 {
986         struct ISectState s;
987         const int totface_orig = bm->totface;
988
989         /* use to check if we made any changes */
990         bool has_edit_isect = false, has_edit_boolean = false;
991
992         /* needed for boolean, since cutting up faces moves the loops within the face */
993         const float **looptri_coords = NULL;
994
995 #ifdef USE_BVH
996         BVHTree *tree_a, *tree_b;
997         uint tree_overlap_tot;
998         BVHTreeOverlap *overlap;
999 #else
1000         int i_a, i_b;
1001 #endif
1002
1003         s.bm = bm;
1004
1005         s.edgetri_cache = BLI_ghash_new(BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, __func__);
1006
1007         s.edge_verts = BLI_ghash_ptr_new(__func__);
1008         s.face_edges = BLI_ghash_int_new(__func__);
1009         s.wire_edges = BLI_gset_ptr_new(__func__);
1010         s.vert_dissolve = NULL;
1011
1012         s.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1013
1014         /* setup epsilon from base */
1015         s.epsilon.eps = eps;
1016         s.epsilon.eps2x = eps * 2.0f;
1017         s.epsilon.eps_margin = s.epsilon.eps2x * 10.0f;
1018
1019         s.epsilon.eps_sq = s.epsilon.eps * s.epsilon.eps;
1020         s.epsilon.eps2x_sq = s.epsilon.eps2x * s.epsilon.eps2x;
1021         s.epsilon.eps_margin_sq = s.epsilon.eps_margin * s.epsilon.eps_margin;
1022
1023         BM_mesh_elem_index_ensure(
1024                 bm,
1025                 BM_VERT |
1026                 BM_EDGE |
1027 #ifdef USE_NET
1028                 BM_FACE |
1029 #endif
1030                 0);
1031
1032
1033         BM_mesh_elem_table_ensure(
1034                 bm,
1035 #ifdef USE_SPLICE
1036                 BM_EDGE |
1037 #endif
1038 #ifdef USE_NET
1039                 BM_FACE |
1040 #endif
1041                 0);
1042
1043 #ifdef USE_DISSOLVE
1044         if (use_dissolve) {
1045                 BM_mesh_elem_hflag_disable_all(bm, BM_EDGE | BM_VERT, BM_ELEM_TAG, false);
1046         }
1047 #else
1048         UNUSED_VARS(use_dissolve);
1049 #endif
1050
1051 #ifdef USE_DUMP
1052         printf("data = [\n");
1053 #endif
1054
1055         if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {
1056                 /* keep original geometrty for raycast callbacks */
1057                 float **cos;
1058                 int i, j;
1059
1060                 cos = MEM_mallocN((size_t)looptris_tot * sizeof(*looptri_coords) * 3, __func__);
1061                 for (i = 0, j = 0; i < looptris_tot; i++) {
1062                         cos[j++] = looptris[i][0]->v->co;
1063                         cos[j++] = looptris[i][1]->v->co;
1064                         cos[j++] = looptris[i][2]->v->co;
1065                 }
1066                 looptri_coords = (const float **)cos;
1067         }
1068
1069 #ifdef USE_BVH
1070         {
1071                 int i;
1072                 tree_a = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8);
1073                 for (i = 0; i < looptris_tot; i++) {
1074                         if (test_fn(looptris[i][0]->f, user_data) == 0) {
1075                                 const float t_cos[3][3] = {
1076                                         {UNPACK3(looptris[i][0]->v->co)},
1077                                         {UNPACK3(looptris[i][1]->v->co)},
1078                                         {UNPACK3(looptris[i][2]->v->co)},
1079                                 };
1080
1081                                 BLI_bvhtree_insert(tree_a, i, (const float *)t_cos, 3);
1082                         }
1083                 }
1084                 BLI_bvhtree_balance(tree_a);
1085         }
1086
1087         if (use_self == false) {
1088                 int i;
1089                 tree_b = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8);
1090                 for (i = 0; i < looptris_tot; i++) {
1091                         if (test_fn(looptris[i][0]->f, user_data) == 1) {
1092                                 const float t_cos[3][3] = {
1093                                         {UNPACK3(looptris[i][0]->v->co)},
1094                                         {UNPACK3(looptris[i][1]->v->co)},
1095                                         {UNPACK3(looptris[i][2]->v->co)},
1096                                 };
1097
1098                                 BLI_bvhtree_insert(tree_b, i, (const float *)t_cos, 3);
1099                         }
1100                 }
1101                 BLI_bvhtree_balance(tree_b);
1102         }
1103         else {
1104                 tree_b = tree_a;
1105         }
1106
1107         overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot, NULL, NULL);
1108
1109         if (overlap) {
1110                 uint i;
1111
1112                 for (i = 0; i < tree_overlap_tot; i++) {
1113 #ifdef USE_DUMP
1114                         printf("  ((%d, %d), (\n",
1115                                overlap[i].indexA,
1116                                overlap[i].indexB);
1117 #endif
1118                         bm_isect_tri_tri(
1119                                 &s,
1120                                 overlap[i].indexA,
1121                                 overlap[i].indexB,
1122                                 looptris[overlap[i].indexA],
1123                                 looptris[overlap[i].indexB]);
1124 #ifdef USE_DUMP
1125                         printf(")),\n");
1126 #endif
1127                 }
1128                 MEM_freeN(overlap);
1129         }
1130
1131         if (boolean_mode == BMESH_ISECT_BOOLEAN_NONE) {
1132                 /* no booleans, just free immediate */
1133                 BLI_bvhtree_free(tree_a);
1134                 if (tree_a != tree_b) {
1135                         BLI_bvhtree_free(tree_b);
1136                 }
1137         }
1138
1139 #else
1140         {
1141                 for (i_a = 0; i_a < looptris_tot; i_a++) {
1142                         const int t_a = test_fn(looptris[i_a][0]->f, user_data);
1143                         for (i_b = i_a + 1; i_b < looptris_tot; i_b++) {
1144                                 const int t_b = test_fn(looptris[i_b][0]->f, user_data);
1145
1146                                 if (use_self) {
1147                                         if ((t_a != 0) || (t_b != 0)) {
1148                                                 continue;
1149                                         }
1150                                 }
1151                                 else {
1152                                         if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) {
1153                                                 continue;
1154                                         }
1155                                 }
1156
1157 #ifdef USE_DUMP
1158                                 printf("  ((%d, %d), (",
1159                                        i_a, i_b);
1160 #endif
1161                                 bm_isect_tri_tri(
1162                                         &s,
1163                                         i_a,
1164                                         i_b,
1165                                         looptris[i_a],
1166                                         looptris[i_b]);
1167 #ifdef USE_DUMP
1168                         printf(")),\n");
1169 #endif
1170                         }
1171                 }
1172         }
1173 #endif  /* USE_BVH */
1174
1175 #ifdef USE_DUMP
1176         printf("]\n");
1177 #endif
1178
1179         /* --------- */
1180
1181 #ifdef USE_SPLICE
1182         {
1183                 GHashIterator gh_iter;
1184
1185                 GHASH_ITER (gh_iter, s.edge_verts) {
1186                         BMEdge *e = BLI_ghashIterator_getKey(&gh_iter);
1187                         struct LinkBase *v_ls_base = BLI_ghashIterator_getValue(&gh_iter);
1188
1189                         BMVert *v_start;
1190                         BMVert *v_end;
1191                         BMVert *v_prev;
1192                         bool is_wire;
1193
1194                         LinkNode *node;
1195
1196                         /* direction is arbitrary, could be swapped */
1197                         v_start = e->v1;
1198                         v_end = e->v2;
1199
1200                         if (v_ls_base->list_len > 1) {
1201                                 edge_verts_sort(v_start->co, v_ls_base);
1202                         }
1203
1204 #ifdef USE_DUMP
1205                         printf("# SPLITTING EDGE: %d, %d\n", BM_elem_index_get(e), v_ls_base->list_len);
1206 #endif
1207                         /* intersect */
1208                         is_wire = BLI_gset_haskey(s.wire_edges,  e);
1209
1210 #ifdef USE_PARANOID
1211                         for (node = v_ls_base->list; node; node = node->next) {
1212                                 BMVert *_v = node->link;
1213                                 BLI_assert(len_squared_v3v3(_v->co, e->v1->co) > s.epsilon.eps_sq);
1214                                 BLI_assert(len_squared_v3v3(_v->co, e->v2->co) > s.epsilon.eps_sq);
1215                         }
1216 #endif
1217
1218                         v_prev = v_start;
1219
1220                         for (node = v_ls_base->list; node; node = node->next) {
1221                                 BMVert *vi = node->link;
1222                                 const float fac = line_point_factor_v3(vi->co, e->v1->co, e->v2->co);
1223
1224                                 if (BM_vert_in_edge(e, v_prev)) {
1225                                         BMEdge *e_split;
1226                                         v_prev = BM_edge_split(bm, e, v_prev, &e_split, CLAMPIS(fac, 0.0f, 1.0f));
1227                                         BLI_assert(BM_vert_in_edge(e, v_end));
1228
1229                                         if (!BM_edge_exists(v_prev, vi) &&
1230                                             !BM_vert_splice_check_double(v_prev, vi) &&
1231                                             !BM_vert_pair_share_face_check(v_prev, vi))
1232                                         {
1233                                                 BM_vert_splice(bm, vi, v_prev);
1234                                         }
1235                                         else {
1236                                                 copy_v3_v3(v_prev->co, vi->co);
1237                                         }
1238                                         v_prev = vi;
1239                                         if (is_wire) {
1240                                                 BLI_gset_insert(s.wire_edges, e_split);
1241                                         }
1242                                 }
1243                         }
1244                         UNUSED_VARS_NDEBUG(v_end);
1245                 }
1246         }
1247 #endif
1248
1249
1250         /* important to handle before edgenet */
1251 #ifdef USE_DISSOLVE
1252         if (use_dissolve && (boolean_mode == BMESH_ISECT_BOOLEAN_NONE)) {
1253                 /* first pass */
1254                 BMVert *(*splice_ls)[2];
1255                 STACK_DECLARE(splice_ls);
1256                 LinkNode *node;
1257
1258
1259                 for (node = s.vert_dissolve; node; node = node->next) {
1260                         BMVert *v = node->link;
1261                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1262                                 if (!BM_vert_is_edge_pair(v)) {
1263                                         BM_elem_flag_disable(v, BM_ELEM_TAG);
1264                                 }
1265                         }
1266                 }
1267
1268                 splice_ls = MEM_mallocN(BLI_gset_size(s.wire_edges) * sizeof(*splice_ls), __func__);
1269                 STACK_INIT(splice_ls, BLI_gset_size(s.wire_edges));
1270
1271                 for (node = s.vert_dissolve; node; node = node->next) {
1272                         BMEdge *e_pair[2];
1273                         BMVert *v = node->link;
1274                         BMVert *v_a, *v_b;
1275
1276                         if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
1277                                 continue;
1278                         }
1279
1280                         /* get chain */
1281                         e_pair[0] = v->e;
1282                         e_pair[1] = BM_DISK_EDGE_NEXT(v->e, v);
1283
1284                         if (BM_elem_flag_test(e_pair[0], BM_ELEM_TAG) ||
1285                             BM_elem_flag_test(e_pair[1], BM_ELEM_TAG))
1286                         {
1287                                 continue;
1288                         }
1289
1290                         v_a = BM_edge_other_vert(e_pair[0], v);
1291                         v_b = BM_edge_other_vert(e_pair[1], v);
1292
1293                         /* simple case */
1294                         if (BM_elem_flag_test(v_a, BM_ELEM_TAG) &&
1295                             BM_elem_flag_test(v_b, BM_ELEM_TAG))
1296                         {
1297                                 /* only start on an edge-case */
1298                                 /* pass */
1299                         }
1300                         else if ((!BM_elem_flag_test(v_a, BM_ELEM_TAG)) &&
1301                                  (!BM_elem_flag_test(v_b, BM_ELEM_TAG)))
1302                         {
1303                                 /* simple case, single edge spans face */
1304                                 BMVert **splice_pair;
1305                                 BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG);
1306                                 splice_pair = STACK_PUSH_RET(splice_ls);
1307                                 splice_pair[0] = v;
1308                                 splice_pair[1] = v_b;
1309 #ifdef USE_DUMP
1310                                 printf("# Simple Case!\n");
1311 #endif
1312                         }
1313                         else {
1314 #ifdef USE_PARANOID
1315                                 BMEdge *e_keep;
1316 #endif
1317                                 BMEdge *e;
1318                                 BMEdge *e_step;
1319                                 BMVert *v_step;
1320
1321                                 /* walk the chain! */
1322                                 if (BM_elem_flag_test(v_a, BM_ELEM_TAG)) {
1323                                         e = e_pair[0];
1324 #ifdef USE_PARANOID
1325                                         e_keep = e_pair[1];
1326 #endif
1327                                 }
1328                                 else {
1329                                         SWAP(BMVert *, v_a, v_b);
1330                                         e = e_pair[1];
1331 #ifdef USE_PARANOID
1332                                         e_keep = e_pair[0];
1333 #endif
1334                                 }
1335
1336                                 /* WALK */
1337                                 v_step = v;
1338                                 e_step = e;
1339
1340                                 while (true) {
1341                                         BMEdge *e_next;
1342                                         BMVert *v_next;
1343
1344                                         v_next = BM_edge_other_vert(e_step, v_step);
1345                                         BM_elem_flag_enable(e_step, BM_ELEM_TAG);
1346                                         if (!BM_elem_flag_test(v_next, BM_ELEM_TAG)) {
1347                                                 BMVert **splice_pair;
1348 #ifdef USE_PARANOID
1349                                                 BLI_assert(e_step != e_keep);
1350 #endif
1351                                                 splice_pair = STACK_PUSH_RET(splice_ls);
1352                                                 splice_pair[0] = v;
1353                                                 splice_pair[1] = v_next;
1354                                                 break;
1355                                         }
1356                                         else {
1357                                                 e_next = bm_vert_other_edge(v_next, e_step);
1358                                         }
1359
1360                                         e_step = e_next;
1361                                         v_step = v_next;
1362                                         BM_elem_flag_enable(e_step, BM_ELEM_TAG);
1363 #ifdef USE_PARANOID
1364                                         BLI_assert(e_step != e_keep);
1365 #endif
1366 #ifdef USE_DUMP
1367                                         printf("# walk step %p %p\n", e_next, v_next);
1368 #endif
1369                                 }
1370 #ifdef USE_PARANOID
1371                                 BLI_assert(BM_elem_flag_test(e_keep, BM_ELEM_TAG) == 0);
1372 #endif
1373                         }
1374                 }
1375
1376                 /* Remove edges! */
1377                 {
1378                         GHashIterator gh_iter;
1379
1380                         GHASH_ITER (gh_iter, s.face_edges) {
1381                                 struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter);
1382                                 LinkNode **node_prev_p;
1383                                 uint i;
1384
1385                                 node_prev_p = &e_ls_base->list;
1386                                 for (i = 0, node = e_ls_base->list; node; i++, node = node->next) {
1387                                         BMEdge *e = node->link;
1388                                         if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
1389                                                 /* allocated by arena, don't free */
1390                                                 *node_prev_p = node->next;
1391                                                 e_ls_base->list_len--;
1392                                         }
1393                                         else {
1394                                                 node_prev_p = &node->next;
1395                                         }
1396                                 }
1397                         }
1398                 }
1399
1400                 {
1401                         BMIter eiter;
1402                         BMEdge *e, *e_next;
1403
1404                         BM_ITER_MESH_MUTABLE (e, e_next, &eiter, bm, BM_EDGES_OF_MESH) {
1405                                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
1406
1407                                         /* in rare and annoying cases,
1408                                          * there can be faces from 's.face_edges' removed by the edges.
1409                                          * These are degenerate cases, so just make sure we don't reference the faces again. */
1410                                         if (e->l) {
1411                                                 BMLoop *l_iter = e->l;
1412                                                 BMFace **faces;
1413
1414                                                 faces = bm->ftable;
1415
1416                                                 do {
1417                                                         const int f_index = BM_elem_index_get(l_iter->f);
1418                                                         if (f_index >= 0) {
1419                                                                 BLI_assert(f_index < totface_orig);
1420                                                                 /* we could check if these are in: 's.face_edges', but easier just to remove */
1421                                                                 faces[f_index] = NULL;
1422                                                         }
1423                                                 } while ((l_iter = l_iter->radial_next) != e->l);
1424                                         }
1425
1426                                         BLI_gset_remove(s.wire_edges, e, NULL);
1427                                         BM_edge_kill(bm, e);
1428                                 }
1429                         }
1430                 }
1431
1432                 /* Remove verts! */
1433                 {
1434                         GSet *verts_invalid = BLI_gset_ptr_new(__func__);
1435
1436                         for (node = s.vert_dissolve; node; node = node->next) {
1437                                 /* arena allocated, don't free */
1438                                 BMVert *v = node->link;
1439                                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1440                                         if (!v->e) {
1441                                                 BLI_gset_add(verts_invalid, v);
1442                                                 BM_vert_kill(bm, v);
1443                                         }
1444                                 }
1445                         }
1446
1447                         {
1448                                 uint i;
1449                                 for (i = 0; i < STACK_SIZE(splice_ls); i++) {
1450                                         if (!BLI_gset_haskey(verts_invalid, splice_ls[i][0]) &&
1451                                             !BLI_gset_haskey(verts_invalid, splice_ls[i][1]))
1452                                         {
1453                                                 if (!BM_edge_exists(UNPACK2(splice_ls[i])) &&
1454                                                     !BM_vert_splice_check_double(UNPACK2(splice_ls[i])))
1455                                                 {
1456                                                         BM_vert_splice(bm, splice_ls[i][1], splice_ls[i][0]);
1457                                                 }
1458                                         }
1459                                 }
1460                         }
1461
1462                         BLI_gset_free(verts_invalid, NULL);
1463                 }
1464
1465                 MEM_freeN(splice_ls);
1466         }
1467 #endif  /* USE_DISSOLVE */
1468
1469
1470         /* now split faces */
1471 #ifdef USE_NET
1472         {
1473                 GHashIterator gh_iter;
1474                 BMFace **faces;
1475
1476                 MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1477
1478                 faces = bm->ftable;
1479
1480                 GHASH_ITER (gh_iter, s.face_edges) {
1481                         const int f_index = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter));
1482                         BMFace *f;
1483                         struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter);
1484
1485                         BLI_assert(f_index >= 0 && f_index < totface_orig);
1486
1487                         f = faces[f_index];
1488                         if (UNLIKELY(f == NULL)) {
1489                                 continue;
1490                         }
1491
1492                         BLI_assert(BM_elem_index_get(f) == f_index);
1493
1494                         face_edges_split(bm, f, e_ls_base, use_island_connect, mem_arena_edgenet);
1495
1496                         BLI_memarena_clear(mem_arena_edgenet);
1497                 }
1498
1499                 BLI_memarena_free(mem_arena_edgenet);
1500         }
1501 #else
1502         UNUSED_VARS(use_island_connect);
1503 #endif  /* USE_NET */
1504         (void)totface_orig;
1505
1506 #ifdef USE_SEPARATE
1507         if (use_separate) {
1508                 GSetIterator gs_iter;
1509
1510                 BM_mesh_elem_hflag_disable_all(bm, BM_EDGE, BM_ELEM_TAG, false);
1511
1512                 GSET_ITER (gs_iter, s.wire_edges) {
1513                         BMEdge *e = BLI_gsetIterator_getKey(&gs_iter);
1514                         BM_elem_flag_enable(e, BM_ELEM_TAG);
1515                 }
1516
1517                 BM_mesh_edgesplit(bm, false, true, false);
1518         }
1519         else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE || use_edge_tag) {
1520                 GSetIterator gs_iter;
1521
1522                 /* no need to clear for boolean */
1523
1524                 GSET_ITER (gs_iter, s.wire_edges) {
1525                         BMEdge *e = BLI_gsetIterator_getKey(&gs_iter);
1526                         BM_elem_flag_enable(e, BM_ELEM_TAG);
1527                 }
1528         }
1529 #else
1530         (void)use_separate;
1531 #endif  /* USE_SEPARATE */
1532
1533         if ((boolean_mode != BMESH_ISECT_BOOLEAN_NONE)) {
1534                 BVHTree *tree_pair[2] = {tree_a, tree_b};
1535
1536                 /* group vars */
1537                 int *groups_array;
1538                 int (*group_index)[2];
1539                 int group_tot;
1540                 int i;
1541                 BMFace **ftable;
1542
1543                 BM_mesh_elem_table_ensure(bm, BM_FACE);
1544                 ftable = bm->ftable;
1545
1546                 /* wrap the face-test callback to make it into an edge-loop delimiter */
1547                 struct LoopFilterWrap user_data_wrap = {
1548                         .test_fn = test_fn,
1549                         .user_data = user_data,
1550                 };
1551
1552                 groups_array = MEM_mallocN(sizeof(*groups_array) * (size_t)bm->totface, __func__);
1553                 group_tot = BM_mesh_calc_face_groups(
1554                         bm, groups_array, &group_index,
1555                         bm_loop_filter_fn, &user_data_wrap,
1556                         0, BM_EDGE);
1557
1558 #ifdef USE_DUMP
1559                 printf("%s: Total face-groups: %d\n", __func__, group_tot);
1560 #endif
1561
1562                 /* Check if island is inside/outside */
1563                 for (i = 0; i < group_tot; i++) {
1564                         int fg     = group_index[i][0];
1565                         int fg_end = group_index[i][1] + fg;
1566                         bool do_remove, do_flip;
1567
1568                         {
1569                                 /* for now assyme this is an OK face to test with (not degenerate!) */
1570                                 BMFace *f = ftable[groups_array[fg]];
1571                                 float co[3];
1572                                 int hits;
1573                                 int side = test_fn(f, user_data);
1574
1575                                 if (side == -1) {
1576                                         continue;
1577                                 }
1578                                 BLI_assert(ELEM(side, 0, 1));
1579                                 side = !side;
1580
1581                                 // BM_face_calc_center_mean(f, co);
1582                                 BM_face_calc_point_in_face(f, co);
1583
1584                                 hits = isect_bvhtree_point_v3(tree_pair[side], looptri_coords, co);
1585
1586                                 switch (boolean_mode) {
1587                                         case BMESH_ISECT_BOOLEAN_ISECT:
1588                                                 do_remove = ((hits & 1) != 1);
1589                                                 do_flip = false;
1590                                                 break;
1591                                         case BMESH_ISECT_BOOLEAN_UNION:
1592                                                 do_remove = ((hits & 1) == 1);
1593                                                 do_flip = false;
1594                                                 break;
1595                                         case BMESH_ISECT_BOOLEAN_DIFFERENCE:
1596                                                 do_remove = ((hits & 1) == 1) == side;
1597                                                 do_flip = (side == 0);
1598                                                 break;
1599                                 }
1600                         }
1601
1602                         if (do_remove) {
1603                                 for (; fg != fg_end; fg++) {
1604                                         /* postpone killing the face since we access below, mark instead */
1605                                         // BM_face_kill_loose(bm, ftable[groups_array[fg]]);
1606                                         ftable[groups_array[fg]]->mat_nr = -1;
1607                                 }
1608                         }
1609                         else if (do_flip) {
1610                                 for (; fg != fg_end; fg++) {
1611                                         BM_face_normal_flip(bm, ftable[groups_array[fg]]);
1612                                 }
1613                         }
1614
1615                         has_edit_boolean |= (do_flip || do_remove);
1616                 }
1617
1618                 MEM_freeN(groups_array);
1619                 MEM_freeN(group_index);
1620
1621 #ifdef USE_DISSOLVE
1622                 /* We have dissolve code above, this is alternative logic,
1623                  * we need to do it after the boolean is executed. */
1624                 if (use_dissolve) {
1625                         LinkNode *node;
1626                         for (node = s.vert_dissolve; node; node = node->next) {
1627                                 BMVert *v = node->link;
1628                                 if (BM_vert_is_edge_pair(v)) {
1629                                         /* we wont create degenerate faces from this */
1630                                         bool ok = true;
1631
1632                                         /* would we create a 2-sided-face?
1633                                          * if so, don't dissolve this since we may */
1634                                         if (v->e->l) {
1635                                                 BMLoop *l_iter = v->e->l;
1636                                                 do {
1637                                                         if (l_iter->f->len == 3) {
1638                                                                 ok = false;
1639                                                                 break;
1640                                                         }
1641                                                 } while ((l_iter = l_iter->radial_next) != v->e->l);
1642                                         }
1643
1644                                         if (ok) {
1645                                                 BM_vert_collapse_edge(bm, v->e, v, true, false);
1646                                         }
1647                                 }
1648                         }
1649                 }
1650 #endif
1651
1652                 {
1653                         int tot = bm->totface;
1654                         for (i = 0; i < tot; i++) {
1655                                 if (ftable[i]->mat_nr == -1) {
1656                                         BM_face_kill_loose(bm, ftable[i]);
1657                                 }
1658                         }
1659                 }
1660         }
1661
1662         if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {
1663                 MEM_freeN((void *)looptri_coords);
1664
1665                 /* no booleans, just free immediate */
1666                 BLI_bvhtree_free(tree_a);
1667                 if (tree_a != tree_b) {
1668                         BLI_bvhtree_free(tree_b);
1669                 }
1670         }
1671
1672         has_edit_isect = (BLI_ghash_size(s.face_edges) != 0);
1673
1674         /* cleanup */
1675         BLI_ghash_free(s.edgetri_cache, NULL, NULL);
1676
1677         BLI_ghash_free(s.edge_verts, NULL, NULL);
1678         BLI_ghash_free(s.face_edges, NULL, NULL);
1679         BLI_gset_free(s.wire_edges, NULL);
1680
1681         BLI_memarena_free(s.mem_arena);
1682
1683         return (has_edit_isect || has_edit_boolean);
1684 }