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