Cleanup: fixes for building with recent clang
[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 #include "BLI_array.h"
49
50 #include "BLI_kdopbvh.h"
51
52 #include "bmesh.h"
53 #include "bmesh_intersect.h"  /* own include */
54
55 #include "tools/bmesh_edgesplit.h"
56
57 #include "BLI_strict_flags.h"
58
59 /*
60  * Some of these depend on each other:
61  */
62
63 /* splice verts into existing edges */
64 #define USE_SPLICE
65 /* split faces by intersecting edges */
66 #define USE_NET
67 /* split resulting edges */
68 #define USE_SEPARATE
69 /* remove verts created by intersecting triangles */
70 #define USE_DISSOLVE
71
72 /* strict asserts that may fail in practice (handy for debugging cases which should succeed) */
73 // #define USE_PARANOID
74 /* use accelerated overlap check */
75 #define USE_BVH
76
77
78 static void tri_v3_scale(
79         float v1[3], float v2[3], float v3[3],
80         const float t)
81 {
82         float p[3];
83
84         mid_v3_v3v3v3(p, v1, v2, v3);
85
86         interp_v3_v3v3(v1, p, v1, t);
87         interp_v3_v3v3(v2, p, v2, t);
88         interp_v3_v3v3(v3, p, v3, t);
89 }
90
91 #ifdef USE_DISSOLVE
92 /* other edge when a vert only has 2 edges */
93 static BMEdge *bm_vert_other_edge(BMVert *v, BMEdge *e)
94 {
95         BLI_assert(BM_vert_is_edge_pair(v));
96         BLI_assert(BM_vert_in_edge(e, v));
97
98         if (v->e != e) {
99                 return v->e;
100         }
101         else {
102                 return BM_DISK_EDGE_NEXT(v->e, v);
103         }
104 }
105 #endif
106
107 enum ISectType {
108         IX_NONE = -1,
109         IX_EDGE_TRI_EDGE0,
110         IX_EDGE_TRI_EDGE1,
111         IX_EDGE_TRI_EDGE2,
112         IX_EDGE_TRI,
113         IX_TOT,
114 };
115
116 struct ISectEpsilon {
117         float eps, eps_sq;
118         float eps2x, eps2x_sq;
119         float eps_margin, eps_margin_sq;
120 };
121
122 struct ISectState {
123         BMesh *bm;
124         GHash *edgetri_cache;  /* int[4]: BMVert */
125         GHash *edge_verts;  /* BMEdge: LinkList(of verts), new and original edges */
126         GHash *face_edges;  /* BMFace-index: LinkList(of edges), only original faces */
127         GSet  *wire_edges;  /* BMEdge  (could use tags instead) */
128         LinkNode *vert_dissolve;  /* BMVert's */
129
130         MemArena *mem_arena;
131
132         struct ISectEpsilon epsilon;
133 };
134
135 /**
136  * Store as value in GHash so we can get list-length without counting every time.
137  * Also means we don't need to update the GHash value each time.
138  */
139 struct LinkBase {
140         LinkNode    *list;
141         unsigned int list_len;
142 };
143
144 static bool ghash_insert_link(
145         GHash *gh, void *key, void *val, bool use_test,
146         MemArena *mem_arena)
147 {
148         struct LinkBase *ls_base;
149         LinkNode *ls;
150
151         ls_base = BLI_ghash_lookup(gh, key);
152
153         if (ls_base) {
154                 if (use_test && (BLI_linklist_index(ls_base->list, key) != -1)) {
155                         return false;
156                 }
157         }
158         else {
159                 ls_base = BLI_memarena_alloc(mem_arena, sizeof(*ls_base));
160                 ls_base->list     = NULL;
161                 ls_base->list_len = 0;
162                 BLI_ghash_insert(gh, key, ls_base);
163         }
164
165         ls = BLI_memarena_alloc(mem_arena, sizeof(*ls));
166         ls->next = ls_base->list;
167         ls->link = val;
168         ls_base->list = ls;
169         ls_base->list_len += 1;
170
171         return true;
172 }
173
174 struct vert_sort_t {
175         float val;
176         BMVert *v;
177 };
178
179 #ifdef USE_SPLICE
180 static void edge_verts_sort(const float co[3], struct LinkBase *v_ls_base)
181 {
182         /* not optimal but list will be typically < 5 */
183         unsigned int i;
184         struct vert_sort_t *vert_sort = BLI_array_alloca(vert_sort, v_ls_base->list_len);
185         LinkNode *node;
186
187         BLI_assert(v_ls_base->list_len > 1);
188
189         for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
190                 BMVert *v = node->link;
191                 BLI_assert(v->head.htype == BM_VERT);
192                 vert_sort[i].val = len_squared_v3v3(co, v->co);
193                 vert_sort[i].v   = v;
194         }
195
196         qsort(vert_sort, v_ls_base->list_len, sizeof(*vert_sort), BLI_sortutil_cmp_float);
197
198         for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
199                 node->link = vert_sort[i].v;
200         }
201 }
202 #endif
203
204 static void edge_verts_add(
205         struct ISectState *s,
206         BMEdge *e,
207         BMVert *v,
208         const bool use_test
209         )
210 {
211         BLI_assert(e->head.htype == BM_EDGE);
212         BLI_assert(v->head.htype == BM_VERT);
213         ghash_insert_link(s->edge_verts, (void *)e, v, use_test, s->mem_arena);
214 }
215
216 static void face_edges_add(
217         struct ISectState *s,
218         const int f_index,
219         BMEdge *e,
220         const bool use_test)
221 {
222         void *f_index_key = SET_INT_IN_POINTER(f_index);
223         BLI_assert(e->head.htype == BM_EDGE);
224         BLI_assert(BM_edge_in_face(e, s->bm->ftable[f_index]) == false);
225         BLI_assert(BM_elem_index_get(s->bm->ftable[f_index]) == f_index);
226
227         ghash_insert_link(s->face_edges, f_index_key, e, use_test, s->mem_arena);
228 }
229
230 #ifdef USE_NET
231 static void face_edges_split(
232         BMesh *bm,
233         BMFace *f,
234         struct LinkBase *e_ls_base)
235 {
236         unsigned int i;
237         BMEdge **edge_arr = BLI_array_alloca(edge_arr, e_ls_base->list_len);
238         LinkNode *node;
239         BLI_assert(f->head.htype == BM_FACE);
240
241         for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) {
242                 edge_arr[i] = node->link;
243         }
244         BLI_assert(node == NULL);
245
246 #ifdef USE_DUMP
247         printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len);
248 #endif
249
250         BM_face_split_edgenet(bm, f, edge_arr, (int)e_ls_base->list_len, NULL, NULL);
251 }
252 #endif
253
254 #ifdef USE_DISSOLVE
255 static void vert_dissolve_add(
256         struct ISectState *s,
257         BMVert *v)
258 {
259         BLI_assert(v->head.htype == BM_VERT);
260         BLI_assert(!BM_elem_flag_test(v, BM_ELEM_TAG));
261         BLI_assert(BLI_linklist_index(s->vert_dissolve, v) == -1);
262
263         BM_elem_flag_enable(v, BM_ELEM_TAG);
264         BLI_linklist_prepend_arena(&s->vert_dissolve, v, s->mem_arena);
265 }
266 #endif
267
268 static enum ISectType intersect_line_tri(
269         const float p0[3], const float p1[3],
270         const float *t_cos[3], const float t_nor[3],
271         float r_ix[3],
272         const struct ISectEpsilon *e)
273 {
274         float p_dir[3];
275         unsigned int i_t0;
276         float fac;
277
278         sub_v3_v3v3(p_dir, p0, p1);
279         normalize_v3(p_dir);
280
281         for (i_t0 = 0; i_t0 < 3; i_t0++) {
282                 const unsigned int i_t1 = (i_t0 + 1) % 3;
283                 float te_dir[3];
284
285                 sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]);
286                 normalize_v3(te_dir);
287                 if (fabsf(dot_v3v3(p_dir, te_dir)) >= 1.0f - e->eps) {
288                         /* co-linear */
289                 }
290                 else {
291                         float ix_pair[2][3];
292                         int ix_pair_type;
293
294                         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);
295
296                         if (ix_pair_type != 0) {
297                                 if (ix_pair_type == 1) {
298                                         copy_v3_v3(ix_pair[1], ix_pair[0]);
299                                 }
300
301                                 if ((ix_pair_type == 1) ||
302                                     (len_squared_v3v3(ix_pair[0], ix_pair[1]) <= e->eps_margin_sq))
303                                 {
304                                         fac = line_point_factor_v3(ix_pair[1], t_cos[i_t0], t_cos[i_t1]);
305                                         if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
306                                                 fac = line_point_factor_v3(ix_pair[0], p0, p1);
307                                                 if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
308                                                         copy_v3_v3(r_ix, ix_pair[0]);
309                                                         return (IX_EDGE_TRI_EDGE0 + (enum ISectType)i_t0);
310                                                 }
311                                         }
312                                 }
313                         }
314                 }
315         }
316
317         /* check ray isn't planar with tri */
318         if (fabsf(dot_v3v3(p_dir, t_nor)) >= e->eps) {
319                 if (isect_line_tri_epsilon_v3(p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac, NULL, 0.0f)) {
320                         if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
321                                 interp_v3_v3v3(r_ix, p0, p1, fac);
322                                 if (min_fff(len_squared_v3v3(t_cos[0], r_ix),
323                                             len_squared_v3v3(t_cos[1], r_ix),
324                                             len_squared_v3v3(t_cos[2], r_ix)) >= e->eps_margin_sq)
325                                 {
326                                         return IX_EDGE_TRI;
327                                 }
328                         }
329                 }
330         }
331
332         /* r_ix may be unset */
333         return IX_NONE;
334 }
335
336 static BMVert *bm_isect_edge_tri(
337         struct ISectState *s,
338         BMVert *e_v0, BMVert *e_v1,
339         BMVert *t[3], const int t_index,
340         const float *t_cos[3], const float t_nor[3],
341         enum ISectType *r_side)
342 {
343         BMesh *bm = s->bm;
344         int k_arr[IX_TOT][4];
345         unsigned int i;
346         const int ti[3] = {UNPACK3_EX(BM_elem_index_get, t, )};
347         float ix[3];
348
349         if (BM_elem_index_get(e_v0) > BM_elem_index_get(e_v1)) {
350                 SWAP(BMVert *, e_v0, e_v1);
351         }
352
353 #ifdef USE_PARANOID
354         BLI_assert(len_squared_v3v3(e_v0->co, t[0]->co) >= s->epsilon.eps_sq);
355         BLI_assert(len_squared_v3v3(e_v0->co, t[1]->co) >= s->epsilon.eps_sq);
356         BLI_assert(len_squared_v3v3(e_v0->co, t[2]->co) >= s->epsilon.eps_sq);
357         BLI_assert(len_squared_v3v3(e_v1->co, t[0]->co) >= s->epsilon.eps_sq);
358         BLI_assert(len_squared_v3v3(e_v1->co, t[1]->co) >= s->epsilon.eps_sq);
359         BLI_assert(len_squared_v3v3(e_v1->co, t[2]->co) >= s->epsilon.eps_sq);
360 #endif
361
362 #define KEY_SET(k, i0, i1, i2, i3) { \
363         (k)[0] = i0; \
364         (k)[1] = i1; \
365         (k)[2] = i2; \
366         (k)[3] = i3; \
367 } (void)0
368
369         /* order tri, then order (1-2, 2-3)*/
370 #define KEY_EDGE_TRI_ORDER(k) { \
371         if (k[2] > k[3]) { \
372                 SWAP(int, k[2], k[3]); \
373         } \
374         if (k[0] > k[2]) { \
375                 SWAP(int, k[0], k[2]); \
376                 SWAP(int, k[1], k[3]); \
377         } \
378 } (void)0
379
380         KEY_SET(k_arr[IX_EDGE_TRI], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), t_index, -1);
381         /* need to order here */
382         KEY_SET(k_arr[IX_EDGE_TRI_EDGE0], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[0], ti[1]);
383         KEY_SET(k_arr[IX_EDGE_TRI_EDGE1], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[1], ti[2]);
384         KEY_SET(k_arr[IX_EDGE_TRI_EDGE2], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[2], ti[0]);
385
386         KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE0]);
387         KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE1]);
388         KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE2]);
389
390 #undef KEY_SET
391 #undef KEY_EDGE_TRI_ORDER
392
393
394
395         for (i = 0; i < ARRAY_SIZE(k_arr); i++) {
396                 BMVert *iv;
397
398                 iv = BLI_ghash_lookup(s->edgetri_cache, k_arr[i]);
399
400                 if (iv) {
401 #ifdef USE_DUMP
402                         printf("# cache hit (%d, %d, %d, %d)\n", UNPACK4(k_arr[i]));
403 #endif
404                         *r_side = (enum ISectType)i;
405                         return iv;
406                 }
407         }
408
409         *r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon);
410         if (*r_side != IX_NONE) {
411                 BMVert *iv;
412                 BMEdge *e;
413 #ifdef USE_DUMP
414                 printf("# new vertex (%.6f, %.6f, %.6f) %d\n", UNPACK3(ix), *r_side);
415 #endif
416
417 #ifdef USE_PARANOID
418                 BLI_assert(len_squared_v3v3(ix, e_v0->co) > s->epsilon.eps_sq);
419                 BLI_assert(len_squared_v3v3(ix, e_v1->co) > s->epsilon.eps_sq);
420                 BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq);
421                 BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq);
422                 BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq);
423 #endif
424                 iv = BM_vert_create(bm, ix, NULL, 0);
425
426                 e = BM_edge_exists(e_v0, e_v1);
427                 if (e) {
428 #ifdef USE_DUMP
429                         printf("# adding to edge %d\n", BM_elem_index_get(e));
430 #endif
431                         edge_verts_add(s, e, iv, false);
432                 }
433                 else {
434 #ifdef USE_DISSOLVE
435                         vert_dissolve_add(s, iv);
436 #endif
437                 }
438
439                 if ((*r_side >= IX_EDGE_TRI_EDGE0) && (*r_side <= IX_EDGE_TRI_EDGE2)) {
440                         i = (unsigned int)(*r_side - IX_EDGE_TRI_EDGE0);
441                         e = BM_edge_exists(t[i], t[(i + 1) % 3]);
442                         if (e) {
443                                 edge_verts_add(s, e, iv, false);
444                         }
445                 }
446
447                 {
448                         int *k = BLI_memarena_alloc(s->mem_arena, sizeof(int[4]));
449                         memcpy(k, k_arr[*r_side], sizeof(int[4]));
450                         BLI_ghash_insert(s->edgetri_cache, k, iv);
451                 }
452
453                 return iv;
454
455         }
456
457         *r_side = IX_NONE;
458
459         return NULL;
460 }
461
462 /**
463  * Return true if we have any intersections.
464  */
465 static void bm_isect_tri_tri(
466         struct ISectState *s,
467         int a_index, int b_index,
468         BMLoop **a, BMLoop **b)
469 {
470         BMFace *f_a = (*a)->f;
471         BMFace *f_b = (*b)->f;
472         BMVert *fv_a[3] = {UNPACK3_EX(, a, ->v)};
473         BMVert *fv_b[3] = {UNPACK3_EX(, b, ->v)};
474         const float *f_a_cos[3] = {UNPACK3_EX(, fv_a, ->co)};
475         const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)};
476         float f_a_nor[3];
477         float f_b_nor[3];
478         int a_mask = 0;
479         int b_mask = 0;
480         unsigned int i;
481
482
483         /* should be enough but may need to bump */
484         BMVert *iv_ls_a[8];
485         BMVert *iv_ls_b[8];
486         STACK_DECLARE(iv_ls_a);
487         STACK_DECLARE(iv_ls_b);
488
489         if (UNLIKELY(ELEM(fv_a[0], UNPACK3(fv_b)) ||
490                      ELEM(fv_a[1], UNPACK3(fv_b)) ||
491                      ELEM(fv_a[2], UNPACK3(fv_b))))
492         {
493                 return;
494         }
495
496         STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a));
497         STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b));
498
499         /* vert-vert
500          * --------- */
501         {
502                 /* first check in any verts are touching
503                  * (any case where we wont create new verts)
504                  */
505                 unsigned int i_a;
506                 for (i_a = 0; i_a < 3; i_a++) {
507                         unsigned int i_b;
508                         for (i_b = 0; i_b < 3; i_b++) {
509                                 if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
510                                         if (!((1 << i_a) & a_mask)) {
511                                                 STACK_PUSH(iv_ls_a, fv_a[i_a]);
512                                                 a_mask |= (1 << i_a);
513 #ifdef USE_DUMP
514                                                 printf("  ('VERT-VERT-A') %d, %d),\n",
515                                                        i_a, BM_elem_index_get(fv_a[i_a]));
516 #endif
517                                         }
518                                         if (!((1 << i_b) & b_mask)) {
519                                                 STACK_PUSH(iv_ls_b, fv_b[i_b]);
520                                                 b_mask |= (1 << i_b);
521 #ifdef USE_DUMP
522                                                 printf("  ('VERT-VERT-B') %d, %d),\n",
523                                                        i_b, BM_elem_index_get(fv_b[i_b]));
524 #endif
525                                         }
526                                 }
527                         }
528                 }
529         }
530
531         /* vert-edge
532          * --------- */
533         {
534                 unsigned int i_a;
535                 for (i_a = 0; i_a < 3; i_a++) {
536                         if (!((1 << i_a) & a_mask)) {
537                                 unsigned int i_b_e0;
538                                 for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
539                                         unsigned int i_b_e1 = (i_b_e0 + 1) % 3;
540                                         float fac;
541                                         if (((1 << i_b_e0) | (1 << i_b_e1)) & b_mask)
542                                                 continue;
543                                         fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
544                                         if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0 + s->epsilon.eps)) {
545                                                 float ix[3];
546                                                 interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);
547                                                 if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
548                                                         BMEdge *e;
549                                                         STACK_PUSH(iv_ls_b, fv_a[i_a]);
550                                                         // STACK_PUSH(iv_ls_a, fv_a[i_a]);
551                                                         a_mask |= (1 << i_a);
552                                                         e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
553 #ifdef USE_DUMP
554                                                         printf("  ('VERT-EDGE-A', %d, %d),\n",
555                                                                BM_elem_index_get(fv_b[i_b_e0]), BM_elem_index_get(fv_b[i_b_e1]));
556 #endif
557                                                         if (e) {
558 #ifdef USE_DUMP
559                                                                 printf("# adding to edge %d\n", BM_elem_index_get(e));
560 #endif
561                                                                 edge_verts_add(s, e, fv_a[i_a], true);
562                                                         }
563                                                         break;
564                                                 }
565                                         }
566                                 }
567                         }
568                 }
569         }
570
571         {
572                 unsigned int i_b;
573                 for (i_b = 0; i_b < 3; i_b++) {
574                         if (!((1 << i_b) & b_mask)) {
575                                 unsigned int i_a_e0;
576                                 for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
577                                         unsigned int i_a_e1 = (i_a_e0 + 1) % 3;
578                                         float fac;
579                                         if (((1 << i_a_e0) | (1 << i_a_e1)) & a_mask)
580                                                 continue;
581                                         fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
582                                         if ((fac > 0.0 - s->epsilon.eps) && (fac < 1.0 + s->epsilon.eps)) {
583                                                 float ix[3];
584                                                 interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);
585                                                 if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
586                                                         BMEdge *e;
587                                                         STACK_PUSH(iv_ls_a, fv_b[i_b]);
588                                                         // STACK_PUSH(iv_ls_b, fv_b[i_b]);
589                                                         b_mask |= (1 << i_b);
590                                                         e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
591 #ifdef USE_DUMP
592                                                         printf("  ('VERT-EDGE-B', %d, %d),\n",
593                                                                BM_elem_index_get(fv_a[i_a_e0]), BM_elem_index_get(fv_a[i_a_e1]));
594 #endif
595                                                         if (e) {
596 #ifdef USE_DUMP
597                                                                 printf("  adding to edge %d\n", BM_elem_index_get(e));
598 #endif
599                                                                 edge_verts_add(s, e, fv_b[i_b], true);
600                                                         }
601                                                         break;
602                                                 }
603                                         }
604                                 }
605                         }
606                 }
607         }
608
609         /* vert-tri
610          * -------- */
611         {
612
613                 float t_scale[3][3];
614                 unsigned int i_a;
615
616                 copy_v3_v3(t_scale[0], fv_b[0]->co);
617                 copy_v3_v3(t_scale[1], fv_b[1]->co);
618                 copy_v3_v3(t_scale[2], fv_b[2]->co);
619                 tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
620
621                 // second check for verts intersecting the triangle
622                 for (i_a = 0; i_a < 3; i_a++) {
623                         float ix[3];
624                         if ((1 << i_a) & a_mask)
625                                 continue;
626                         if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {
627                                 if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
628                                         BLI_assert(BLI_array_findindex(iv_ls_a, STACK_SIZE(iv_ls_a), fv_a[i_a]) == -1);
629                                         BLI_assert(BLI_array_findindex(iv_ls_b, STACK_SIZE(iv_ls_b), fv_a[i_a]) == -1);
630
631                                         STACK_PUSH(iv_ls_a, fv_a[i_a]);
632                                         STACK_PUSH(iv_ls_b, fv_a[i_a]);
633                                         a_mask |= (1 << i_a);
634 #ifdef USE_DUMP
635                                         printf("  'VERT TRI-A',\n");
636 #endif
637                                 }
638                         }
639                 }
640         }
641
642         {
643                 float t_scale[3][3];
644                 unsigned int i_b;
645
646                 copy_v3_v3(t_scale[0], fv_a[0]->co);
647                 copy_v3_v3(t_scale[1], fv_a[1]->co);
648                 copy_v3_v3(t_scale[2], fv_a[2]->co);
649                 tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
650
651                 for (i_b = 0; i_b < 3; i_b++) {
652                         float ix[3];
653                         if ((1 << i_b) & b_mask)
654                                 continue;
655
656                         if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {
657                                 if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
658                                         BLI_assert(BLI_array_findindex((void **)iv_ls_a, STACK_SIZE(iv_ls_a), fv_b[i_b]) == -1);
659                                         BLI_assert(BLI_array_findindex((void **)iv_ls_b, STACK_SIZE(iv_ls_b), fv_b[i_b]) == -1);
660
661                                         STACK_PUSH(iv_ls_a, fv_b[i_b]);
662                                         STACK_PUSH(iv_ls_b, fv_b[i_b]);
663                                         b_mask |= (1 << i_b);
664 #ifdef USE_DUMP
665                                         printf("  'VERT TRI-B',\n");
666 #endif
667                                 }
668                         }
669                 }
670         }
671
672         if ((STACK_SIZE(iv_ls_a) >= 3) &&
673             (STACK_SIZE(iv_ls_b) >= 3))
674         {
675 #ifdef USE_DUMP
676                 printf("# OVERLAP\n");
677 #endif
678                 return;
679         }
680
681         normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));
682         normal_tri_v3(f_b_nor, UNPACK3(f_b_cos));
683
684         /* edge-tri & edge-edge
685          * -------------------- */
686         {
687                 unsigned int i_e0;
688                 for (i_e0 = 0; i_e0 < 3; i_e0++) {
689                         unsigned int i_e1 = (i_e0 + 1) % 3;
690                         enum ISectType side;
691                         BMVert *iv;
692                         if (((1 << i_e0) | (1 << i_e1)) & a_mask)
693                                 continue;
694                         iv = bm_isect_edge_tri(s, fv_a[i_e0], fv_a[i_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
695                         if (iv) {
696                                 BLI_assert(BLI_array_findindex((void **)iv_ls_a, STACK_SIZE(iv_ls_a), iv) == -1);
697                                 BLI_assert(BLI_array_findindex((void **)iv_ls_b, STACK_SIZE(iv_ls_b), iv) == -1);
698                                 STACK_PUSH(iv_ls_a, iv);
699                                 STACK_PUSH(iv_ls_b, iv);
700 #ifdef USE_DUMP
701                                 printf("  ('EDGE-TRI-A', %d),\n", side);
702 #endif
703                         }
704                 }
705
706                 for (i_e0 = 0; i_e0 < 3; i_e0++) {
707                         unsigned int i_e1 = (i_e0 + 1) % 3;
708                         enum ISectType side;
709                         BMVert *iv;
710                         if (((1 << i_e0) | (1 << i_e1)) & b_mask)
711                                 continue;
712                         iv = bm_isect_edge_tri(s, fv_b[i_e0], fv_b[i_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
713                         if (iv) {
714                                 /* check this wasn't handled above */
715                                 if (!(side >= IX_EDGE_TRI_EDGE0 && side <= IX_EDGE_TRI_EDGE2)) {
716                                         BLI_assert(BLI_array_findindex((void **)iv_ls_a, STACK_SIZE(iv_ls_a), iv) == -1);
717                                         BLI_assert(BLI_array_findindex((void **)iv_ls_b, STACK_SIZE(iv_ls_b), iv) == -1);
718                                         STACK_PUSH(iv_ls_a, iv);
719                                         STACK_PUSH(iv_ls_b, iv);
720 #ifdef USE_DUMP
721                                         printf("  ('EDGE-RAY-B', %d),\n", side);
722 #endif
723                                 }
724                         }
725                 }
726         }
727
728         {
729                 for (i = 0; i < 2; i++) {
730                         BMVert **ie_vs;
731                         BMFace *f;
732                         bool ie_exists;
733                         BMEdge *ie;
734
735                         if (i == 0) {
736                                 if (STACK_SIZE(iv_ls_a) != 2)
737                                         continue;
738                                 ie_vs = iv_ls_a;
739                                 f = f_a;
740                         }
741                         else {
742                                 if (STACK_SIZE(iv_ls_b) != 2)
743                                         continue;
744                                 ie_vs = iv_ls_b;
745                                 f = f_b;
746                         }
747
748                         /* possible but unlikely we get this - for edge-edge intersection */
749                         ie = BM_edge_exists(UNPACK2(ie_vs));
750                         if (ie == NULL) {
751                                 ie_exists = false;
752                                 /* one of the verts must be new if we are making an edge
753                                  * ...no, we need this in case 2x quads intersect at either ends.
754                                  * if not (ie_vs[0].index == -1 or ie_vs[1].index == -1):
755                                  *     continue */
756                                 ie = BM_edge_create(s->bm, UNPACK2(ie_vs), NULL, 0);
757                                 BLI_gset_insert(s->wire_edges, ie);
758                         }
759                         else {
760                                 ie_exists = true;
761                                 /* may already exist */
762                                 BLI_gset_add(s->wire_edges, ie);
763
764                                 if (BM_edge_in_face(ie, f)) {
765                                         continue;
766                                 }
767                         }
768
769                         face_edges_add(s, BM_elem_index_get(f), ie, ie_exists);
770                         // BLI_assert(len(ie_vs) <= 2)
771                 }
772         }
773 }
774
775 /**
776  * Intersect tessellated faces
777  * leaving the resulting edges tagged.
778  *
779  * \param test_fn Return value: -1: skip, 0: tree_a, 1: tree_b (use_self == false)
780  */
781 bool BM_mesh_intersect(
782         BMesh *bm,
783         struct BMLoop *(*looptris)[3], const int looptris_tot,
784         int (*test_fn)(BMFace *f, void *user_data), void *user_data,
785         const bool use_self, const bool use_separate,
786         const float eps)
787 {
788         struct ISectState s;
789         bool has_isect;
790         const int totface_orig = bm->totface;
791
792 #ifdef USE_BVH
793         BVHTree *tree_a, *tree_b;
794         unsigned int tree_overlap_tot;
795         BVHTreeOverlap *overlap;
796 #else
797         int i_a, i_b;
798 #endif
799
800         s.bm = bm;
801
802         s.edgetri_cache = BLI_ghash_new(BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, __func__);
803
804         s.edge_verts = BLI_ghash_ptr_new(__func__);
805         s.face_edges = BLI_ghash_ptr_new(__func__);
806         s.wire_edges = BLI_gset_ptr_new(__func__);
807         s.vert_dissolve = NULL;
808
809         s.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
810
811         /* setup epsilon from base */
812         s.epsilon.eps = eps;
813         s.epsilon.eps2x = eps * 2.0f;
814         s.epsilon.eps_margin = s.epsilon.eps2x * 10.0f;
815
816         s.epsilon.eps_sq = s.epsilon.eps * s.epsilon.eps;
817         s.epsilon.eps2x_sq = s.epsilon.eps2x * s.epsilon.eps2x;
818         s.epsilon.eps_margin_sq = s.epsilon.eps_margin * s.epsilon.eps_margin;
819
820         BM_mesh_elem_index_ensure(
821                 bm,
822                 BM_VERT |
823                 BM_EDGE |
824 #ifdef USE_NET
825                 BM_FACE |
826 #endif
827                 0);
828
829
830         BM_mesh_elem_table_ensure(
831                 bm,
832 #ifdef USE_SPLICE
833                 BM_EDGE |
834 #endif
835 #ifdef USE_NET
836                 BM_FACE |
837 #endif
838                 0);
839
840 #ifdef USE_DISSOLVE
841         BM_mesh_elem_hflag_disable_all(bm, BM_EDGE | BM_VERT, BM_ELEM_TAG, false);
842 #endif
843
844 #ifdef USE_DUMP
845         printf("data = [\n");
846 #endif
847
848 #ifdef USE_BVH
849         {
850                 int i;
851                 tree_a = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8);
852                 for (i = 0; i < looptris_tot; i++) {
853                         if (test_fn(looptris[i][0]->f, user_data) == 0) {
854                                 const float t_cos[3][3] = {
855                                         {UNPACK3(looptris[i][0]->v->co)},
856                                         {UNPACK3(looptris[i][1]->v->co)},
857                                         {UNPACK3(looptris[i][2]->v->co)},
858                                 };
859
860                                 BLI_bvhtree_insert(tree_a, i, (const float *)t_cos, 3);
861                         }
862                 }
863                 BLI_bvhtree_balance(tree_a);
864         }
865
866         if (use_self == false) {
867                 int i;
868                 tree_b = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8);
869                 for (i = 0; i < looptris_tot; i++) {
870                         if (test_fn(looptris[i][0]->f, user_data) == 1) {
871                                 const float t_cos[3][3] = {
872                                         {UNPACK3(looptris[i][0]->v->co)},
873                                         {UNPACK3(looptris[i][1]->v->co)},
874                                         {UNPACK3(looptris[i][2]->v->co)},
875                                 };
876
877                                 BLI_bvhtree_insert(tree_b, i, (const float *)t_cos, 3);
878                         }
879                 }
880                 BLI_bvhtree_balance(tree_b);
881         }
882         else {
883                 tree_b = tree_a;
884         }
885
886         overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot);
887
888         if (overlap) {
889                 unsigned int i;
890
891                 for (i = 0; i < tree_overlap_tot; i++) {
892 #ifdef USE_DUMP
893                         printf("  ((%d, %d), (\n",
894                                overlap[i].indexA,
895                                overlap[i].indexB);
896 #endif
897                         bm_isect_tri_tri(
898                                 &s,
899                                 overlap[i].indexA,
900                                 overlap[i].indexB,
901                                 looptris[overlap[i].indexA],
902                                 looptris[overlap[i].indexB]);
903 #ifdef USE_DUMP
904                         printf(")),\n");
905 #endif
906                 }
907                 MEM_freeN(overlap);
908         }
909         BLI_bvhtree_free(tree_a);
910         if (tree_a != tree_b) {
911                 BLI_bvhtree_free(tree_b);
912         }
913
914 #else
915         {
916                 for (i_a = 0; i_a < looptris_tot; i_a++) {
917                         const int t_a = test_fn(looptris[i_a][0]->f, user_data);
918                         for (i_b = i_a + 1; i_b < looptris_tot; i_b++) {
919                                 const int t_b = test_fn(looptris[i_b][0]->f, user_data);
920
921                                 if (use_self) {
922                                         if ((t_a != 0) || (t_b != 0)) {
923                                                 continue;
924                                         }
925                                 }
926                                 else {
927                                         if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) {
928                                                 continue;
929                                         }
930                                 }
931
932 #ifdef USE_DUMP
933                                 printf("  ((%d, %d), (",
934                                        i_a, i_b);
935 #endif
936                                 bm_isect_tri_tri(
937                                         &s,
938                                         i_a,
939                                         i_b,
940                                         looptris[i_a],
941                                         looptris[i_b]);
942 #ifdef USE_DUMP
943                         printf(")),\n");
944 #endif
945                         }
946                 }
947         }
948 #endif  /* USE_BVH */
949
950 #ifdef USE_DUMP
951         printf("]\n");
952 #endif
953
954         /* --------- */
955
956 #ifdef USE_SPLICE
957         {
958                 GHashIterator gh_iter;
959
960                 GHASH_ITER (gh_iter, s.edge_verts) {
961                         BMEdge *e = BLI_ghashIterator_getKey(&gh_iter);
962                         struct LinkBase *v_ls_base = BLI_ghashIterator_getValue(&gh_iter);
963
964                         BMVert *v_start;
965                         BMVert *v_end;
966                         BMVert *v_prev;
967                         bool is_wire;
968
969                         LinkNode *node;
970
971                         /* direction is arbitrary, could be swapped */
972                         v_start = e->v1;
973                         v_end = e->v2;
974
975                         if (v_ls_base->list_len > 1) {
976                                 edge_verts_sort(v_start->co, v_ls_base);
977                         }
978
979 #ifdef USE_DUMP
980                         printf("# SPLITTING EDGE: %d, %d\n", e_index, v_ls_base->list_len);
981 #endif
982                         /* intersect */
983                         is_wire = BLI_gset_haskey(s.wire_edges,  e);
984
985 #ifdef USE_PARANOID
986                         for (node = v_ls_base->list; node; node = node->next) {
987                                 BMVert *_v = node->link;
988                                 BLI_assert(len_squared_v3v3(_v->co, e->v1->co) > s.epsilon.eps_sq);
989                                 BLI_assert(len_squared_v3v3(_v->co, e->v2->co) > s.epsilon.eps_sq);
990                         }
991 #endif
992
993                         v_prev = v_start;
994
995                         for (node = v_ls_base->list; node; node = node->next) {
996                                 BMVert *vi = node->link;
997                                 const float fac = line_point_factor_v3(vi->co, e->v1->co, e->v2->co);
998
999                                 if (BM_vert_in_edge(e, v_prev)) {
1000                                         v_prev = BM_edge_split(bm, e, v_prev, NULL, CLAMPIS(fac, 0.0f, 1.0f));
1001                                         BLI_assert( BM_vert_in_edge(e, v_end));
1002
1003                                         if (!BM_edge_exists(v_prev, vi) &&
1004                                             !BM_vert_splice_check_double(v_prev, vi) &&
1005                                             !BM_vert_pair_share_face_check(v_prev, vi))
1006                                         {
1007                                                 BM_vert_splice(bm, v_prev, vi);
1008                                         }
1009                                         else {
1010                                                 copy_v3_v3(v_prev->co, vi->co);
1011                                         }
1012                                         v_prev = vi;
1013                                         if (is_wire) {
1014                                                 BLI_gset_insert(s.wire_edges, e);
1015                                         }
1016                                 }
1017                         }
1018                 }
1019         }
1020 #endif
1021
1022
1023         /* important to handle before edgenet */
1024 #ifdef USE_DISSOLVE
1025         {
1026                 /* first pass */
1027                 BMVert *(*splice_ls)[2];
1028                 STACK_DECLARE(splice_ls);
1029                 LinkNode *node;
1030
1031
1032                 for (node = s.vert_dissolve; node; node = node->next) {
1033                         BMVert *v = node->link;
1034                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1035                                 if (!BM_vert_is_edge_pair(v)) {
1036                                         BM_elem_flag_disable(v, BM_ELEM_TAG);
1037                                 }
1038                         }
1039                 }
1040
1041                 splice_ls = MEM_mallocN((unsigned int)BLI_gset_size(s.wire_edges) * sizeof(*splice_ls), __func__);
1042                 STACK_INIT(splice_ls, (unsigned int)BLI_gset_size(s.wire_edges));
1043
1044                 for (node = s.vert_dissolve; node; node = node->next) {
1045                         BMEdge *e_pair[2];
1046                         BMVert *v = node->link;
1047                         BMVert *v_a, *v_b;
1048
1049                         if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
1050                                 continue;
1051                         }
1052
1053                         /* get chain */
1054                         e_pair[0] = v->e;
1055                         e_pair[1] = BM_DISK_EDGE_NEXT(v->e, v);
1056
1057                         if (BM_elem_flag_test(e_pair[0], BM_ELEM_TAG) ||
1058                             BM_elem_flag_test(e_pair[1], BM_ELEM_TAG))
1059                         {
1060                                 continue;
1061                         }
1062
1063                         v_a = BM_edge_other_vert(e_pair[0], v);
1064                         v_b = BM_edge_other_vert(e_pair[1], v);
1065
1066                         /* simple case */
1067                         if (BM_elem_flag_test(v_a, BM_ELEM_TAG) &&
1068                             BM_elem_flag_test(v_b, BM_ELEM_TAG))
1069                         {
1070                                 /* only start on an edge-case */
1071                                 /* pass */
1072                         }
1073                         else if ((!BM_elem_flag_test(v_a, BM_ELEM_TAG)) &&
1074                                  (!BM_elem_flag_test(v_b, BM_ELEM_TAG)))
1075                         {
1076                                 /* simple case, single edge spans face */
1077                                 BMVert **splice_pair;
1078                                 BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG);
1079                                 splice_pair = STACK_PUSH_RET(splice_ls);
1080                                 splice_pair[0] = v;
1081                                 splice_pair[1] = v_b;
1082 #ifdef USE_DUMP
1083                                 printf("# Simple Case!\n");
1084 #endif
1085                         }
1086                         else {
1087 #ifdef USE_PARANOID
1088                                 BMEdge *e_keep;
1089 #endif
1090                                 BMEdge *e;
1091                                 BMEdge *e_step;
1092                                 BMVert *v_step;
1093
1094                                 /* walk the chain! */
1095                                 if (BM_elem_flag_test(v_a, BM_ELEM_TAG)) {
1096                                         e = e_pair[0];
1097 #ifdef USE_PARANOID
1098                                         e_keep = e_pair[1];
1099 #endif
1100                                 }
1101                                 else {
1102                                         SWAP(BMVert *, v_a, v_b);
1103                                         e = e_pair[1];
1104 #ifdef USE_PARANOID
1105                                         e_keep = e_pair[0];
1106 #endif
1107                                 }
1108
1109                                 /* WALK */
1110                                 v_step = v;
1111                                 e_step = e;
1112
1113                                 while (true) {
1114                                         BMEdge *e_next;
1115                                         BMVert *v_next;
1116
1117                                         v_next = BM_edge_other_vert(e_step, v_step);
1118                                         BM_elem_flag_enable(e_step, BM_ELEM_TAG);
1119                                         if (!BM_elem_flag_test(v_next, BM_ELEM_TAG)) {
1120                                                 BMVert **splice_pair;
1121 #ifdef USE_PARANOID
1122                                                 BLI_assert(e_step != e_keep);
1123 #endif
1124                                                 splice_pair = STACK_PUSH_RET(splice_ls);
1125                                                 splice_pair[0] = v;
1126                                                 splice_pair[1] = v_next;
1127                                                 break;
1128                                         }
1129                                         else {
1130                                                 e_next = bm_vert_other_edge(v_next, e_step);
1131                                         }
1132
1133                                         e_step = e_next;
1134                                         v_step = v_next;
1135                                         BM_elem_flag_enable(e_step, BM_ELEM_TAG);
1136 #ifdef USE_PARANOID
1137                                         BLI_assert(e_step != e_keep);
1138 #endif
1139 #ifdef USE_DUMP
1140                                         printf("# walk step %p %p\n", e_next, v_next);
1141 #endif
1142                                 }
1143 #ifdef USE_PARANOID
1144                                 BLI_assert(BM_elem_flag_test(e_keep, BM_ELEM_TAG) == 0);
1145 #endif
1146                         }
1147                 }
1148
1149                 /* Remove edges! */
1150                 {
1151                         GHashIterator gh_iter;
1152
1153                         GHASH_ITER (gh_iter, s.face_edges) {
1154                                 struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter);
1155                                 LinkNode **node_prev_p;
1156                                 unsigned int i;
1157
1158                                 node_prev_p = &e_ls_base->list;
1159                                 for (i = 0, node = e_ls_base->list; node; i++, node = node->next) {
1160                                         BMEdge *e = node->link;
1161                                         if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
1162                                                 /* allocated by arena, don't free */
1163                                                 *node_prev_p = node->next;
1164                                                 e_ls_base->list_len--;
1165                                         }
1166                                         else {
1167                                                 node_prev_p = &node->next;
1168                                         }
1169                                 }
1170                         }
1171                 }
1172
1173                 {
1174                         BMIter eiter;
1175                         BMEdge *e, *e_next;
1176
1177                         BM_ITER_MESH_MUTABLE (e, e_next, &eiter, bm, BM_EDGES_OF_MESH) {
1178                                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
1179
1180                                         /* in rare and annoying cases,
1181                                          * there can be faces from 's.face_edges' removed by the edges.
1182                                          * These are degenerate cases, so just make sure we don't reference the faces again. */
1183                                         if (e->l) {
1184                                                 BMLoop *l_iter = e->l;
1185                                                 BMFace **faces;
1186
1187                                                 faces = bm->ftable;
1188
1189                                                 do {
1190                                                         const int f_index = BM_elem_index_get(l_iter->f);
1191                                                         if (f_index >= 0) {
1192                                                                 BLI_assert(f_index < totface_orig);
1193                                                                 /* we could check if these are in: 's.face_edges', but easier just to remove */
1194                                                                 faces[f_index] = NULL;
1195                                                         }
1196                                                 } while ((l_iter = l_iter->radial_next) != e->l);
1197                                         }
1198
1199                                         BLI_gset_remove(s.wire_edges, e, NULL);
1200                                         BM_edge_kill(bm, e);
1201                                 }
1202                         }
1203                 }
1204
1205                 /* Remove verts! */
1206                 {
1207                         GSet *verts_invalid = BLI_gset_ptr_new(__func__);
1208
1209                         for (node = s.vert_dissolve; node; node = node->next) {
1210                                 /* arena allocated, don't free */
1211                                 BMVert *v = node->link;
1212                                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1213                                         if (!v->e) {
1214                                                 BLI_gset_add(verts_invalid, v);
1215                                                 BM_vert_kill(bm, v);
1216                                         }
1217                                 }
1218                         }
1219
1220                         {
1221                                 unsigned int i;
1222                                 for (i = 0; i < STACK_SIZE(splice_ls); i++) {
1223                                         if (!BLI_gset_haskey(verts_invalid, splice_ls[i][0]) &&
1224                                             !BLI_gset_haskey(verts_invalid, splice_ls[i][1]))
1225                                         {
1226                                                 if (!BM_edge_exists(UNPACK2(splice_ls[i])) &&
1227                                                     !BM_vert_splice_check_double(UNPACK2(splice_ls[i])))
1228                                                 {
1229                                                         BM_vert_splice(bm, UNPACK2(splice_ls[i]));
1230                                                 }
1231                                         }
1232                                 }
1233                         }
1234
1235                         BLI_gset_free(verts_invalid, NULL);
1236                 }
1237
1238                 MEM_freeN(splice_ls);
1239         }
1240 #endif  /* USE_DISSOLVE */
1241
1242
1243         /* now split faces */
1244 #ifdef USE_NET
1245         {
1246                 GHashIterator gh_iter;
1247                 BMFace **faces;
1248
1249                 faces = bm->ftable;
1250
1251                 GHASH_ITER (gh_iter, s.face_edges) {
1252                         const int f_index = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter));
1253                         BMFace *f;
1254                         struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter);
1255
1256                         BLI_assert(f_index >= 0 && f_index < totface_orig);
1257
1258                         f = faces[f_index];
1259                         if (UNLIKELY(f == NULL)) {
1260                                 continue;
1261                         }
1262
1263                         BLI_assert(BM_elem_index_get(f) == f_index);
1264
1265                         face_edges_split(bm, f, e_ls_base);
1266                 }
1267         }
1268 #else
1269         (void)totface_orig;
1270 #endif  /* USE_NET */
1271
1272
1273 #ifdef USE_SEPARATE
1274         if (use_separate) {
1275                 GSetIterator gs_iter;
1276
1277                 BM_mesh_elem_hflag_disable_all(bm, BM_EDGE, BM_ELEM_TAG, false);
1278
1279                 GSET_ITER (gs_iter, s.wire_edges) {
1280                         BMEdge *e = BLI_gsetIterator_getKey(&gs_iter);
1281                         BM_elem_flag_enable(e, BM_ELEM_TAG);
1282                 }
1283
1284                 BM_mesh_edgesplit(bm, false, true, false);
1285         }
1286 #else
1287         (void)use_separate;
1288 #endif  /* USE_SEPARATE */
1289
1290         has_isect = (BLI_ghash_size(s.face_edges) != 0);
1291
1292         /* cleanup */
1293         BLI_ghash_free(s.edgetri_cache, NULL, NULL);
1294
1295         BLI_ghash_free(s.edge_verts, NULL, NULL);
1296         BLI_ghash_free(s.face_edges, NULL, NULL);
1297         BLI_gset_free(s.wire_edges, NULL);
1298
1299         BLI_memarena_free(s.mem_arena);
1300
1301         return has_isect;
1302 }