diff options
author | Campbell Barton <ideasman42@gmail.com> | 2019-04-17 07:17:24 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2019-04-17 07:21:24 +0300 |
commit | e12c08e8d170b7ca40f204a5b0423c23a9fbc2c1 (patch) | |
tree | 8cf3453d12edb177a218ef8009357518ec6cab6a /source/blender/bmesh/tools/bmesh_intersect.c | |
parent | b3dabc200a4b0399ec6b81f2ff2730d07b44fcaa (diff) |
ClangFormat: apply to source, most of intern
Apply clang format as proposed in T53211.
For details on usage and instructions for migrating branches
without conflicts, see:
https://wiki.blender.org/wiki/Tools/ClangFormat
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_intersect.c')
-rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect.c | 2670 |
1 files changed, 1314 insertions, 1356 deletions
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index 2445978e294..66845b6f33c 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.c +++ b/source/blender/bmesh/tools/bmesh_intersect.c @@ -50,7 +50,7 @@ #include "bmesh.h" #include "intern/bmesh_private.h" -#include "bmesh_intersect.h" /* own include */ +#include "bmesh_intersect.h" /* own include */ #include "tools/bmesh_edgesplit.h" @@ -78,61 +78,59 @@ // #define USE_DUMP -static void tri_v3_scale( - float v1[3], float v2[3], float v3[3], - const float t) +static void tri_v3_scale(float v1[3], float v2[3], float v3[3], const float t) { - float p[3]; + float p[3]; - mid_v3_v3v3v3(p, v1, v2, v3); + mid_v3_v3v3v3(p, v1, v2, v3); - interp_v3_v3v3(v1, p, v1, t); - interp_v3_v3v3(v2, p, v2, t); - interp_v3_v3v3(v3, p, v3, t); + interp_v3_v3v3(v1, p, v1, t); + interp_v3_v3v3(v2, p, v2, t); + interp_v3_v3v3(v3, p, v3, t); } #ifdef USE_DISSOLVE /* other edge when a vert only has 2 edges */ static BMEdge *bm_vert_other_edge(BMVert *v, BMEdge *e) { - BLI_assert(BM_vert_is_edge_pair(v)); - BLI_assert(BM_vert_in_edge(e, v)); - - if (v->e != e) { - return v->e; - } - else { - return BM_DISK_EDGE_NEXT(v->e, v); - } + BLI_assert(BM_vert_is_edge_pair(v)); + BLI_assert(BM_vert_in_edge(e, v)); + + if (v->e != e) { + return v->e; + } + else { + return BM_DISK_EDGE_NEXT(v->e, v); + } } #endif enum ISectType { - IX_NONE = -1, - IX_EDGE_TRI_EDGE0, - IX_EDGE_TRI_EDGE1, - IX_EDGE_TRI_EDGE2, - IX_EDGE_TRI, - IX_TOT, + IX_NONE = -1, + IX_EDGE_TRI_EDGE0, + IX_EDGE_TRI_EDGE1, + IX_EDGE_TRI_EDGE2, + IX_EDGE_TRI, + IX_TOT, }; struct ISectEpsilon { - float eps, eps_sq; - float eps2x, eps2x_sq; - float eps_margin, eps_margin_sq; + float eps, eps_sq; + float eps2x, eps2x_sq; + float eps_margin, eps_margin_sq; }; struct ISectState { - BMesh *bm; - GHash *edgetri_cache; /* int[4]: BMVert */ - GHash *edge_verts; /* BMEdge: LinkList(of verts), new and original edges */ - GHash *face_edges; /* BMFace-index: LinkList(of edges), only original faces */ - GSet *wire_edges; /* BMEdge (could use tags instead) */ - LinkNode *vert_dissolve; /* BMVert's */ + BMesh *bm; + GHash *edgetri_cache; /* int[4]: BMVert */ + GHash *edge_verts; /* BMEdge: LinkList(of verts), new and original edges */ + GHash *face_edges; /* BMFace-index: LinkList(of edges), only original faces */ + GSet *wire_edges; /* BMEdge (could use tags instead) */ + LinkNode *vert_dissolve; /* BMVert's */ - MemArena *mem_arena; + MemArena *mem_arena; - struct ISectEpsilon epsilon; + struct ISectEpsilon epsilon; }; /** @@ -140,829 +138,809 @@ struct ISectState { * Also means we don't need to update the GHash value each time. */ struct LinkBase { - LinkNode *list; - uint list_len; + LinkNode *list; + uint list_len; }; -static bool ghash_insert_link( - GHash *gh, void *key, void *val, bool use_test, - MemArena *mem_arena) +static bool ghash_insert_link(GHash *gh, void *key, void *val, bool use_test, MemArena *mem_arena) { - void **ls_base_p; - struct LinkBase *ls_base; - LinkNode *ls; - - if (!BLI_ghash_ensure_p(gh, key, &ls_base_p)) { - ls_base = *ls_base_p = BLI_memarena_alloc(mem_arena, sizeof(*ls_base)); - ls_base->list = NULL; - ls_base->list_len = 0; - } - else { - ls_base = *ls_base_p; - if (use_test && (BLI_linklist_index(ls_base->list, val) != -1)) { - return false; - } - } - - ls = BLI_memarena_alloc(mem_arena, sizeof(*ls)); - ls->next = ls_base->list; - ls->link = val; - ls_base->list = ls; - ls_base->list_len += 1; - - return true; + void **ls_base_p; + struct LinkBase *ls_base; + LinkNode *ls; + + if (!BLI_ghash_ensure_p(gh, key, &ls_base_p)) { + ls_base = *ls_base_p = BLI_memarena_alloc(mem_arena, sizeof(*ls_base)); + ls_base->list = NULL; + ls_base->list_len = 0; + } + else { + ls_base = *ls_base_p; + if (use_test && (BLI_linklist_index(ls_base->list, val) != -1)) { + return false; + } + } + + ls = BLI_memarena_alloc(mem_arena, sizeof(*ls)); + ls->next = ls_base->list; + ls->link = val; + ls_base->list = ls; + ls_base->list_len += 1; + + return true; } struct vert_sort_t { - float val; - BMVert *v; + float val; + BMVert *v; }; #ifdef USE_SPLICE static void edge_verts_sort(const float co[3], struct LinkBase *v_ls_base) { - /* not optimal but list will be typically < 5 */ - uint i; - struct vert_sort_t *vert_sort = BLI_array_alloca(vert_sort, v_ls_base->list_len); - LinkNode *node; + /* not optimal but list will be typically < 5 */ + uint i; + struct vert_sort_t *vert_sort = BLI_array_alloca(vert_sort, v_ls_base->list_len); + LinkNode *node; - BLI_assert(v_ls_base->list_len > 1); + BLI_assert(v_ls_base->list_len > 1); - for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) { - BMVert *v = node->link; - BLI_assert(v->head.htype == BM_VERT); - vert_sort[i].val = len_squared_v3v3(co, v->co); - vert_sort[i].v = v; - } + for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) { + BMVert *v = node->link; + BLI_assert(v->head.htype == BM_VERT); + vert_sort[i].val = len_squared_v3v3(co, v->co); + vert_sort[i].v = v; + } - qsort(vert_sort, v_ls_base->list_len, sizeof(*vert_sort), BLI_sortutil_cmp_float); + qsort(vert_sort, v_ls_base->list_len, sizeof(*vert_sort), BLI_sortutil_cmp_float); - for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) { - node->link = vert_sort[i].v; - } + for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) { + node->link = vert_sort[i].v; + } } #endif -static void edge_verts_add( - struct ISectState *s, - BMEdge *e, - BMVert *v, - const bool use_test - ) +static void edge_verts_add(struct ISectState *s, BMEdge *e, BMVert *v, const bool use_test) { - BLI_assert(e->head.htype == BM_EDGE); - BLI_assert(v->head.htype == BM_VERT); - ghash_insert_link(s->edge_verts, (void *)e, v, use_test, s->mem_arena); + BLI_assert(e->head.htype == BM_EDGE); + BLI_assert(v->head.htype == BM_VERT); + ghash_insert_link(s->edge_verts, (void *)e, v, use_test, s->mem_arena); } -static void face_edges_add( - struct ISectState *s, - const int f_index, - BMEdge *e, - const bool use_test) +static void face_edges_add(struct ISectState *s, const int f_index, BMEdge *e, const bool use_test) { - void *f_index_key = POINTER_FROM_INT(f_index); - BLI_assert(e->head.htype == BM_EDGE); - BLI_assert(BM_edge_in_face(e, s->bm->ftable[f_index]) == false); - BLI_assert(BM_elem_index_get(s->bm->ftable[f_index]) == f_index); + void *f_index_key = POINTER_FROM_INT(f_index); + BLI_assert(e->head.htype == BM_EDGE); + BLI_assert(BM_edge_in_face(e, s->bm->ftable[f_index]) == false); + BLI_assert(BM_elem_index_get(s->bm->ftable[f_index]) == f_index); - ghash_insert_link(s->face_edges, f_index_key, e, use_test, s->mem_arena); + ghash_insert_link(s->face_edges, f_index_key, e, use_test, s->mem_arena); } #ifdef USE_NET -static void face_edges_split( - BMesh *bm, BMFace *f, struct LinkBase *e_ls_base, - bool use_island_connect, bool use_partial_connect, - MemArena *mem_arena_edgenet) +static void face_edges_split(BMesh *bm, + BMFace *f, + struct LinkBase *e_ls_base, + bool use_island_connect, + bool use_partial_connect, + MemArena *mem_arena_edgenet) { - uint i; - uint edge_arr_len = e_ls_base->list_len; - BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len); - LinkNode *node; - BLI_assert(f->head.htype == BM_FACE); - - for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) { - edge_arr[i] = node->link; - } - BLI_assert(node == NULL); - -#ifdef USE_DUMP - printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len); -#endif - -#ifdef USE_NET_ISLAND_CONNECT - if (use_island_connect) { - uint edge_arr_holes_len; - BMEdge **edge_arr_holes; - if (BM_face_split_edgenet_connect_islands( - bm, f, - edge_arr, edge_arr_len, - use_partial_connect, - mem_arena_edgenet, - &edge_arr_holes, &edge_arr_holes_len)) - { - edge_arr_len = edge_arr_holes_len; - edge_arr = edge_arr_holes; /* owned by the arena */ - } - } -#else - UNUSED_VARS(use_island_connect, mem_arena_edgenet); -#endif - - BM_face_split_edgenet(bm, f, edge_arr, (int)edge_arr_len, NULL, NULL); + uint i; + uint edge_arr_len = e_ls_base->list_len; + BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len); + LinkNode *node; + BLI_assert(f->head.htype == BM_FACE); + + for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) { + edge_arr[i] = node->link; + } + BLI_assert(node == NULL); + +# ifdef USE_DUMP + printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len); +# endif + +# ifdef USE_NET_ISLAND_CONNECT + if (use_island_connect) { + uint edge_arr_holes_len; + BMEdge **edge_arr_holes; + if (BM_face_split_edgenet_connect_islands(bm, + f, + edge_arr, + edge_arr_len, + use_partial_connect, + mem_arena_edgenet, + &edge_arr_holes, + &edge_arr_holes_len)) { + edge_arr_len = edge_arr_holes_len; + edge_arr = edge_arr_holes; /* owned by the arena */ + } + } +# else + UNUSED_VARS(use_island_connect, mem_arena_edgenet); +# endif + + BM_face_split_edgenet(bm, f, edge_arr, (int)edge_arr_len, NULL, NULL); } #endif #ifdef USE_DISSOLVE -static void vert_dissolve_add( - struct ISectState *s, - BMVert *v) +static void vert_dissolve_add(struct ISectState *s, BMVert *v) { - BLI_assert(v->head.htype == BM_VERT); - BLI_assert(!BM_elem_flag_test(v, BM_ELEM_TAG)); - BLI_assert(BLI_linklist_index(s->vert_dissolve, v) == -1); + BLI_assert(v->head.htype == BM_VERT); + BLI_assert(!BM_elem_flag_test(v, BM_ELEM_TAG)); + BLI_assert(BLI_linklist_index(s->vert_dissolve, v) == -1); - BM_elem_flag_enable(v, BM_ELEM_TAG); - BLI_linklist_prepend_arena(&s->vert_dissolve, v, s->mem_arena); + BM_elem_flag_enable(v, BM_ELEM_TAG); + BLI_linklist_prepend_arena(&s->vert_dissolve, v, s->mem_arena); } #endif -static enum ISectType intersect_line_tri( - const float p0[3], const float p1[3], - const float *t_cos[3], const float t_nor[3], - float r_ix[3], - const struct ISectEpsilon *e) +static enum ISectType intersect_line_tri(const float p0[3], + const float p1[3], + const float *t_cos[3], + const float t_nor[3], + float r_ix[3], + const struct ISectEpsilon *e) { - float p_dir[3]; - uint i_t0; - float fac; - - sub_v3_v3v3(p_dir, p0, p1); - normalize_v3(p_dir); - - for (i_t0 = 0; i_t0 < 3; i_t0++) { - const uint i_t1 = (i_t0 + 1) % 3; - float te_dir[3]; - - sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]); - normalize_v3(te_dir); - if (fabsf(dot_v3v3(p_dir, te_dir)) >= 1.0f - e->eps) { - /* co-linear */ - } - else { - float ix_pair[2][3]; - int ix_pair_type; - - 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); - - if (ix_pair_type != 0) { - if (ix_pair_type == 1) { - copy_v3_v3(ix_pair[1], ix_pair[0]); - } - - if ((ix_pair_type == 1) || - (len_squared_v3v3(ix_pair[0], ix_pair[1]) <= e->eps_margin_sq)) - { - fac = line_point_factor_v3(ix_pair[1], t_cos[i_t0], t_cos[i_t1]); - if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) { - fac = line_point_factor_v3(ix_pair[0], p0, p1); - if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) { - copy_v3_v3(r_ix, ix_pair[0]); - return (IX_EDGE_TRI_EDGE0 + (enum ISectType)i_t0); - } - } - } - } - } - } - - /* check ray isn't planar with tri */ - if (fabsf(dot_v3v3(p_dir, t_nor)) >= e->eps) { - if (isect_line_segment_tri_epsilon_v3(p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac, NULL, 0.0f)) { - if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) { - interp_v3_v3v3(r_ix, p0, p1, fac); - if (min_fff(len_squared_v3v3(t_cos[0], r_ix), - len_squared_v3v3(t_cos[1], r_ix), - len_squared_v3v3(t_cos[2], r_ix)) >= e->eps_margin_sq) - { - return IX_EDGE_TRI; - } - } - } - } - - /* r_ix may be unset */ - return IX_NONE; + float p_dir[3]; + uint i_t0; + float fac; + + sub_v3_v3v3(p_dir, p0, p1); + normalize_v3(p_dir); + + for (i_t0 = 0; i_t0 < 3; i_t0++) { + const uint i_t1 = (i_t0 + 1) % 3; + float te_dir[3]; + + sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]); + normalize_v3(te_dir); + if (fabsf(dot_v3v3(p_dir, te_dir)) >= 1.0f - e->eps) { + /* co-linear */ + } + else { + float ix_pair[2][3]; + int ix_pair_type; + + 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); + + if (ix_pair_type != 0) { + if (ix_pair_type == 1) { + copy_v3_v3(ix_pair[1], ix_pair[0]); + } + + if ((ix_pair_type == 1) || + (len_squared_v3v3(ix_pair[0], ix_pair[1]) <= e->eps_margin_sq)) { + fac = line_point_factor_v3(ix_pair[1], t_cos[i_t0], t_cos[i_t1]); + if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) { + fac = line_point_factor_v3(ix_pair[0], p0, p1); + if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) { + copy_v3_v3(r_ix, ix_pair[0]); + return (IX_EDGE_TRI_EDGE0 + (enum ISectType)i_t0); + } + } + } + } + } + } + + /* check ray isn't planar with tri */ + if (fabsf(dot_v3v3(p_dir, t_nor)) >= e->eps) { + if (isect_line_segment_tri_epsilon_v3( + p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac, NULL, 0.0f)) { + if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) { + interp_v3_v3v3(r_ix, p0, p1, fac); + if (min_fff(len_squared_v3v3(t_cos[0], r_ix), + len_squared_v3v3(t_cos[1], r_ix), + len_squared_v3v3(t_cos[2], r_ix)) >= e->eps_margin_sq) { + return IX_EDGE_TRI; + } + } + } + } + + /* r_ix may be unset */ + return IX_NONE; } -static BMVert *bm_isect_edge_tri( - struct ISectState *s, - BMVert *e_v0, BMVert *e_v1, - BMVert *t[3], const int t_index, - const float *t_cos[3], const float t_nor[3], - enum ISectType *r_side) +static BMVert *bm_isect_edge_tri(struct ISectState *s, + BMVert *e_v0, + BMVert *e_v1, + BMVert *t[3], + const int t_index, + const float *t_cos[3], + const float t_nor[3], + enum ISectType *r_side) { - BMesh *bm = s->bm; - int k_arr[IX_TOT][4]; - uint i; - const int ti[3] = {UNPACK3_EX(BM_elem_index_get, t, )}; - float ix[3]; + BMesh *bm = s->bm; + int k_arr[IX_TOT][4]; + uint i; + const int ti[3] = {UNPACK3_EX(BM_elem_index_get, t, )}; + float ix[3]; - if (BM_elem_index_get(e_v0) > BM_elem_index_get(e_v1)) { - SWAP(BMVert *, e_v0, e_v1); - } + if (BM_elem_index_get(e_v0) > BM_elem_index_get(e_v1)) { + SWAP(BMVert *, e_v0, e_v1); + } #ifdef USE_PARANOID - BLI_assert(len_squared_v3v3(e_v0->co, t[0]->co) >= s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(e_v0->co, t[1]->co) >= s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(e_v0->co, t[2]->co) >= s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(e_v1->co, t[0]->co) >= s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(e_v1->co, t[1]->co) >= s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(e_v1->co, t[2]->co) >= s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(e_v0->co, t[0]->co) >= s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(e_v0->co, t[1]->co) >= s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(e_v0->co, t[2]->co) >= s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(e_v1->co, t[0]->co) >= s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(e_v1->co, t[1]->co) >= s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(e_v1->co, t[2]->co) >= s->epsilon.eps_sq); #endif -#define KEY_SET(k, i0, i1, i2, i3) { \ - (k)[0] = i0; \ - (k)[1] = i1; \ - (k)[2] = i2; \ - (k)[3] = i3; \ -} (void)0 - - /* order tri, then order (1-2, 2-3)*/ -#define KEY_EDGE_TRI_ORDER(k) { \ - if (k[2] > k[3]) { \ - SWAP(int, k[2], k[3]); \ - } \ - if (k[0] > k[2]) { \ - SWAP(int, k[0], k[2]); \ - SWAP(int, k[1], k[3]); \ - } \ -} (void)0 - - KEY_SET(k_arr[IX_EDGE_TRI], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), t_index, -1); - /* need to order here */ - KEY_SET(k_arr[IX_EDGE_TRI_EDGE0], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[0], ti[1]); - KEY_SET(k_arr[IX_EDGE_TRI_EDGE1], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[1], ti[2]); - KEY_SET(k_arr[IX_EDGE_TRI_EDGE2], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[2], ti[0]); - - KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE0]); - KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE1]); - KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE2]); +#define KEY_SET(k, i0, i1, i2, i3) \ + { \ + (k)[0] = i0; \ + (k)[1] = i1; \ + (k)[2] = i2; \ + (k)[3] = i3; \ + } \ + (void)0 + + /* order tri, then order (1-2, 2-3)*/ +#define KEY_EDGE_TRI_ORDER(k) \ + { \ + if (k[2] > k[3]) { \ + SWAP(int, k[2], k[3]); \ + } \ + if (k[0] > k[2]) { \ + SWAP(int, k[0], k[2]); \ + SWAP(int, k[1], k[3]); \ + } \ + } \ + (void)0 + + KEY_SET(k_arr[IX_EDGE_TRI], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), t_index, -1); + /* need to order here */ + KEY_SET( + k_arr[IX_EDGE_TRI_EDGE0], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[0], ti[1]); + KEY_SET( + k_arr[IX_EDGE_TRI_EDGE1], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[1], ti[2]); + KEY_SET( + k_arr[IX_EDGE_TRI_EDGE2], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[2], ti[0]); + + KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE0]); + KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE1]); + KEY_EDGE_TRI_ORDER(k_arr[IX_EDGE_TRI_EDGE2]); #undef KEY_SET #undef KEY_EDGE_TRI_ORDER + for (i = 0; i < ARRAY_SIZE(k_arr); i++) { + BMVert *iv; + iv = BLI_ghash_lookup(s->edgetri_cache, k_arr[i]); - for (i = 0; i < ARRAY_SIZE(k_arr); i++) { - BMVert *iv; - - iv = BLI_ghash_lookup(s->edgetri_cache, k_arr[i]); - - if (iv) { + if (iv) { #ifdef USE_DUMP - printf("# cache hit (%d, %d, %d, %d)\n", UNPACK4(k_arr[i])); + printf("# cache hit (%d, %d, %d, %d)\n", UNPACK4(k_arr[i])); #endif - *r_side = (enum ISectType)i; - return iv; - } - } - - *r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon); - if (*r_side != IX_NONE) { - BMVert *iv; - BMEdge *e; + *r_side = (enum ISectType)i; + return iv; + } + } + + *r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon); + if (*r_side != IX_NONE) { + BMVert *iv; + BMEdge *e; #ifdef USE_DUMP - printf("# new vertex (%.6f, %.6f, %.6f) %d\n", UNPACK3(ix), *r_side); + printf("# new vertex (%.6f, %.6f, %.6f) %d\n", UNPACK3(ix), *r_side); #endif #ifdef USE_PARANOID - BLI_assert(len_squared_v3v3(ix, e_v0->co) > s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(ix, e_v1->co) > s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq); - BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(ix, e_v0->co) > s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(ix, e_v1->co) > s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq); + BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq); #endif - iv = BM_vert_create(bm, ix, NULL, 0); + iv = BM_vert_create(bm, ix, NULL, 0); - e = BM_edge_exists(e_v0, e_v1); - if (e) { + e = BM_edge_exists(e_v0, e_v1); + if (e) { #ifdef USE_DUMP - printf("# adding to edge %d\n", BM_elem_index_get(e)); + printf("# adding to edge %d\n", BM_elem_index_get(e)); #endif - edge_verts_add(s, e, iv, false); - } - else { + edge_verts_add(s, e, iv, false); + } + else { #ifdef USE_DISSOLVE - vert_dissolve_add(s, iv); + vert_dissolve_add(s, iv); #endif - } + } - if ((*r_side >= IX_EDGE_TRI_EDGE0) && (*r_side <= IX_EDGE_TRI_EDGE2)) { - i = (uint)(*r_side - IX_EDGE_TRI_EDGE0); - e = BM_edge_exists(t[i], t[(i + 1) % 3]); - if (e) { - edge_verts_add(s, e, iv, false); - } - } + if ((*r_side >= IX_EDGE_TRI_EDGE0) && (*r_side <= IX_EDGE_TRI_EDGE2)) { + i = (uint)(*r_side - IX_EDGE_TRI_EDGE0); + e = BM_edge_exists(t[i], t[(i + 1) % 3]); + if (e) { + edge_verts_add(s, e, iv, false); + } + } - { - int *k = BLI_memarena_alloc(s->mem_arena, sizeof(int[4])); - memcpy(k, k_arr[*r_side], sizeof(int[4])); - BLI_ghash_insert(s->edgetri_cache, k, iv); - } + { + int *k = BLI_memarena_alloc(s->mem_arena, sizeof(int[4])); + memcpy(k, k_arr[*r_side], sizeof(int[4])); + BLI_ghash_insert(s->edgetri_cache, k, iv); + } - return iv; + return iv; + } - } + *r_side = IX_NONE; - *r_side = IX_NONE; - - return NULL; + return NULL; } struct LoopFilterWrap { - int (*test_fn)(BMFace *f, void *user_data); - void *user_data; + int (*test_fn)(BMFace *f, void *user_data); + void *user_data; }; static bool bm_loop_filter_fn(const BMLoop *l, void *user_data) { - if (BM_elem_flag_test(l->e, BM_ELEM_TAG)) { - return false; - } - - if (l->radial_next != l) { - struct LoopFilterWrap *data = user_data; - BMLoop *l_iter = l->radial_next; - const int face_side = data->test_fn(l->f, data->user_data); - do { - const int face_side_other = data->test_fn(l_iter->f, data->user_data); - if (UNLIKELY(face_side_other == -1)) { - /* pass */ - } - else if (face_side_other != face_side) { - return false; - } - } while ((l_iter = l_iter->radial_next) != l); - return true; - } - return false; + if (BM_elem_flag_test(l->e, BM_ELEM_TAG)) { + return false; + } + + if (l->radial_next != l) { + struct LoopFilterWrap *data = user_data; + BMLoop *l_iter = l->radial_next; + const int face_side = data->test_fn(l->f, data->user_data); + do { + const int face_side_other = data->test_fn(l_iter->f, data->user_data); + if (UNLIKELY(face_side_other == -1)) { + /* pass */ + } + else if (face_side_other != face_side) { + return false; + } + } while ((l_iter = l_iter->radial_next) != l); + return true; + } + return false; } /** * Return true if we have any intersections. */ static void bm_isect_tri_tri( - struct ISectState *s, - int a_index, int b_index, - BMLoop **a, BMLoop **b) + struct ISectState *s, int a_index, int b_index, BMLoop **a, BMLoop **b) { - BMFace *f_a = (*a)->f; - BMFace *f_b = (*b)->f; - BMVert *fv_a[3] = {UNPACK3_EX(, a, ->v)}; - BMVert *fv_b[3] = {UNPACK3_EX(, b, ->v)}; - const float *f_a_cos[3] = {UNPACK3_EX(, fv_a, ->co)}; - const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)}; - float f_a_nor[3]; - float f_b_nor[3]; - uint i; - - - /* should be enough but may need to bump */ - BMVert *iv_ls_a[8]; - BMVert *iv_ls_b[8]; - STACK_DECLARE(iv_ls_a); - STACK_DECLARE(iv_ls_b); - - if (UNLIKELY(ELEM(fv_a[0], UNPACK3(fv_b)) || - ELEM(fv_a[1], UNPACK3(fv_b)) || - ELEM(fv_a[2], UNPACK3(fv_b)))) - { - return; - } - - STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a)); - STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b)); + BMFace *f_a = (*a)->f; + BMFace *f_b = (*b)->f; + BMVert *fv_a[3] = {UNPACK3_EX(, a, ->v)}; + BMVert *fv_b[3] = {UNPACK3_EX(, b, ->v)}; + const float *f_a_cos[3] = {UNPACK3_EX(, fv_a, ->co)}; + const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)}; + float f_a_nor[3]; + float f_b_nor[3]; + uint i; + + /* should be enough but may need to bump */ + BMVert *iv_ls_a[8]; + BMVert *iv_ls_b[8]; + STACK_DECLARE(iv_ls_a); + STACK_DECLARE(iv_ls_b); + + if (UNLIKELY(ELEM(fv_a[0], UNPACK3(fv_b)) || ELEM(fv_a[1], UNPACK3(fv_b)) || + ELEM(fv_a[2], UNPACK3(fv_b)))) { + return; + } + + STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a)); + STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b)); #define VERT_VISIT_A _FLAG_WALK #define VERT_VISIT_B _FLAG_WALK_ALT #define STACK_PUSH_TEST_A(ele) \ - if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \ - BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \ - STACK_PUSH(iv_ls_a, ele); \ - } ((void)0) + if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \ + BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \ + STACK_PUSH(iv_ls_a, ele); \ + } \ + ((void)0) #define STACK_PUSH_TEST_B(ele) \ - if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \ - BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \ - STACK_PUSH(iv_ls_b, ele); \ - } ((void)0) - - - /* vert-vert - * --------- */ - { - /* first check in any verts are touching - * (any case where we wont create new verts) - */ - uint i_a; - for (i_a = 0; i_a < 3; i_a++) { - uint i_b; - for (i_b = 0; i_b < 3; i_b++) { - if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { + if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \ + BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \ + STACK_PUSH(iv_ls_b, ele); \ + } \ + ((void)0) + + /* vert-vert + * --------- */ + { + /* first check in any verts are touching + * (any case where we wont create new verts) + */ + uint i_a; + for (i_a = 0; i_a < 3; i_a++) { + uint i_b; + for (i_b = 0; i_b < 3; i_b++) { + if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { #ifdef USE_DUMP - if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT) == 0) { - printf(" ('VERT-VERT-A') %d, %d),\n", - i_a, BM_elem_index_get(fv_a[i_a])); - } - if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT) == 0) { - printf(" ('VERT-VERT-B') %d, %d),\n", - i_b, BM_elem_index_get(fv_b[i_b])); - } + if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT) == 0) { + printf(" ('VERT-VERT-A') %d, %d),\n", i_a, BM_elem_index_get(fv_a[i_a])); + } + if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT) == 0) { + printf(" ('VERT-VERT-B') %d, %d),\n", i_b, BM_elem_index_get(fv_b[i_b])); + } #endif - STACK_PUSH_TEST_A(fv_a[i_a]); - STACK_PUSH_TEST_B(fv_b[i_b]); - } - } - } - } - - /* vert-edge - * --------- */ - { - uint i_a; - for (i_a = 0; i_a < 3; i_a++) { - if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) { - uint i_b_e0; - for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { - uint i_b_e1 = (i_b_e0 + 1) % 3; - - if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) || - BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B)) - { - continue; - } - - const float fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co); - if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) { - float ix[3]; - interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac); - if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) { - BMEdge *e; - STACK_PUSH_TEST_B(fv_a[i_a]); - // STACK_PUSH_TEST_A(fv_a[i_a]); - e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]); + STACK_PUSH_TEST_A(fv_a[i_a]); + STACK_PUSH_TEST_B(fv_b[i_b]); + } + } + } + } + + /* vert-edge + * --------- */ + { + uint i_a; + for (i_a = 0; i_a < 3; i_a++) { + if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) { + uint i_b_e0; + for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { + uint i_b_e1 = (i_b_e0 + 1) % 3; + + if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) || + BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B)) { + continue; + } + + const float fac = line_point_factor_v3( + fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co); + if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) { + float ix[3]; + interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac); + if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) { + BMEdge *e; + STACK_PUSH_TEST_B(fv_a[i_a]); + // STACK_PUSH_TEST_A(fv_a[i_a]); + e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]); #ifdef USE_DUMP - printf(" ('VERT-EDGE-A', %d, %d),\n", - BM_elem_index_get(fv_b[i_b_e0]), BM_elem_index_get(fv_b[i_b_e1])); + printf(" ('VERT-EDGE-A', %d, %d),\n", + BM_elem_index_get(fv_b[i_b_e0]), + BM_elem_index_get(fv_b[i_b_e1])); #endif - if (e) { + if (e) { #ifdef USE_DUMP - printf("# adding to edge %d\n", BM_elem_index_get(e)); + printf("# adding to edge %d\n", BM_elem_index_get(e)); #endif - edge_verts_add(s, e, fv_a[i_a], true); - } - break; - } - } - } - } - } - } - - { - uint i_b; - for (i_b = 0; i_b < 3; i_b++) { - if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) { - uint i_a_e0; - for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { - uint i_a_e1 = (i_a_e0 + 1) % 3; - - if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) || - BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A)) - { - continue; - } - - const float fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co); - if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) { - float ix[3]; - interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac); - if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { - BMEdge *e; - STACK_PUSH_TEST_A(fv_b[i_b]); - // STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]); - e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]); + edge_verts_add(s, e, fv_a[i_a], true); + } + break; + } + } + } + } + } + } + + { + uint i_b; + for (i_b = 0; i_b < 3; i_b++) { + if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) { + uint i_a_e0; + for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { + uint i_a_e1 = (i_a_e0 + 1) % 3; + + if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) || + BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A)) { + continue; + } + + const float fac = line_point_factor_v3( + fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co); + if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) { + float ix[3]; + interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac); + if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { + BMEdge *e; + STACK_PUSH_TEST_A(fv_b[i_b]); + // STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]); + e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]); #ifdef USE_DUMP - printf(" ('VERT-EDGE-B', %d, %d),\n", - BM_elem_index_get(fv_a[i_a_e0]), BM_elem_index_get(fv_a[i_a_e1])); + printf(" ('VERT-EDGE-B', %d, %d),\n", + BM_elem_index_get(fv_a[i_a_e0]), + BM_elem_index_get(fv_a[i_a_e1])); #endif - if (e) { + if (e) { #ifdef USE_DUMP - printf("# adding to edge %d\n", BM_elem_index_get(e)); + printf("# adding to edge %d\n", BM_elem_index_get(e)); #endif - edge_verts_add(s, e, fv_b[i_b], true); - } - break; - } - } - } - } - } - } - - /* vert-tri - * -------- */ - { - - float t_scale[3][3]; - uint i_a; - - copy_v3_v3(t_scale[0], fv_b[0]->co); - copy_v3_v3(t_scale[1], fv_b[1]->co); - copy_v3_v3(t_scale[2], fv_b[2]->co); - tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x); - - // second check for verts intersecting the triangle - for (i_a = 0; i_a < 3; i_a++) { - if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A)) { - continue; - } - - float ix[3]; - if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) { - if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) { - STACK_PUSH_TEST_A(fv_a[i_a]); - STACK_PUSH_TEST_B(fv_a[i_a]); + edge_verts_add(s, e, fv_b[i_b], true); + } + break; + } + } + } + } + } + } + + /* vert-tri + * -------- */ + { + + float t_scale[3][3]; + uint i_a; + + copy_v3_v3(t_scale[0], fv_b[0]->co); + copy_v3_v3(t_scale[1], fv_b[1]->co); + copy_v3_v3(t_scale[2], fv_b[2]->co); + tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x); + + // second check for verts intersecting the triangle + for (i_a = 0; i_a < 3; i_a++) { + if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A)) { + continue; + } + + float ix[3]; + if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) { + if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) { + STACK_PUSH_TEST_A(fv_a[i_a]); + STACK_PUSH_TEST_B(fv_a[i_a]); #ifdef USE_DUMP - printf(" 'VERT TRI-A',\n"); + printf(" 'VERT TRI-A',\n"); #endif - } - } - } - } - - { - float t_scale[3][3]; - uint i_b; - - copy_v3_v3(t_scale[0], fv_a[0]->co); - copy_v3_v3(t_scale[1], fv_a[1]->co); - copy_v3_v3(t_scale[2], fv_a[2]->co); - tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x); - - for (i_b = 0; i_b < 3; i_b++) { - if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) { - continue; - } - - float ix[3]; - if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) { - if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { - STACK_PUSH_TEST_A(fv_b[i_b]); - STACK_PUSH_TEST_B(fv_b[i_b]); + } + } + } + } + + { + float t_scale[3][3]; + uint i_b; + + copy_v3_v3(t_scale[0], fv_a[0]->co); + copy_v3_v3(t_scale[1], fv_a[1]->co); + copy_v3_v3(t_scale[2], fv_a[2]->co); + tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x); + + for (i_b = 0; i_b < 3; i_b++) { + if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) { + continue; + } + + float ix[3]; + if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) { + if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) { + STACK_PUSH_TEST_A(fv_b[i_b]); + STACK_PUSH_TEST_B(fv_b[i_b]); #ifdef USE_DUMP - printf(" 'VERT TRI-B',\n"); + printf(" 'VERT TRI-B',\n"); #endif - } - } - } - } - - if ((STACK_SIZE(iv_ls_a) >= 3) && - (STACK_SIZE(iv_ls_b) >= 3)) - { + } + } + } + } + + if ((STACK_SIZE(iv_ls_a) >= 3) && (STACK_SIZE(iv_ls_b) >= 3)) { #ifdef USE_DUMP - printf("# OVERLAP\n"); + printf("# OVERLAP\n"); #endif - goto finally; - } - - normal_tri_v3(f_a_nor, UNPACK3(f_a_cos)); - normal_tri_v3(f_b_nor, UNPACK3(f_b_cos)); - - /* edge-tri & edge-edge - * -------------------- */ - { - for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { - uint i_a_e1 = (i_a_e0 + 1) % 3; - enum ISectType side; - BMVert *iv; - - if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) || - BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A)) - { - continue; - } - - 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); - if (iv) { - STACK_PUSH_TEST_A(iv); - STACK_PUSH_TEST_B(iv); + goto finally; + } + + normal_tri_v3(f_a_nor, UNPACK3(f_a_cos)); + normal_tri_v3(f_b_nor, UNPACK3(f_b_cos)); + + /* edge-tri & edge-edge + * -------------------- */ + { + for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) { + uint i_a_e1 = (i_a_e0 + 1) % 3; + enum ISectType side; + BMVert *iv; + + if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) || + BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A)) { + continue; + } + + 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); + if (iv) { + STACK_PUSH_TEST_A(iv); + STACK_PUSH_TEST_B(iv); #ifdef USE_DUMP - printf(" ('EDGE-TRI-A', %d),\n", side); + printf(" ('EDGE-TRI-A', %d),\n", side); #endif - } - } - - for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { - uint i_b_e1 = (i_b_e0 + 1) % 3; - enum ISectType side; - BMVert *iv; - - if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) || - BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B)) - { - continue; - } - - 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); - if (iv) { - STACK_PUSH_TEST_A(iv); - STACK_PUSH_TEST_B(iv); + } + } + + for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) { + uint i_b_e1 = (i_b_e0 + 1) % 3; + enum ISectType side; + BMVert *iv; + + if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) || + BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B)) { + continue; + } + + 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); + if (iv) { + STACK_PUSH_TEST_A(iv); + STACK_PUSH_TEST_B(iv); #ifdef USE_DUMP - printf(" ('EDGE-TRI-B', %d),\n", side); + printf(" ('EDGE-TRI-B', %d),\n", side); #endif - } - } - } - - { - for (i = 0; i < 2; i++) { - BMVert **ie_vs; - BMFace *f; - bool ie_exists; - BMEdge *ie; - - if (i == 0) { - if (STACK_SIZE(iv_ls_a) != 2) { - continue; - } - ie_vs = iv_ls_a; - f = f_a; - } - else { - if (STACK_SIZE(iv_ls_b) != 2) { - continue; - } - ie_vs = iv_ls_b; - f = f_b; - } - - /* possible but unlikely we get this - for edge-edge intersection */ - ie = BM_edge_exists(UNPACK2(ie_vs)); - if (ie == NULL) { - ie_exists = false; - /* one of the verts must be new if we are making an edge - * ...no, we need this in case 2x quads intersect at either ends. - * if not (ie_vs[0].index == -1 or ie_vs[1].index == -1): - * continue */ - ie = BM_edge_create(s->bm, UNPACK2(ie_vs), NULL, 0); - BLI_gset_insert(s->wire_edges, ie); - } - else { - ie_exists = true; - /* may already exist */ - BLI_gset_add(s->wire_edges, ie); - - if (BM_edge_in_face(ie, f)) { - continue; - } - } - - face_edges_add(s, BM_elem_index_get(f), ie, ie_exists); - // BLI_assert(len(ie_vs) <= 2) - } - } + } + } + } + + { + for (i = 0; i < 2; i++) { + BMVert **ie_vs; + BMFace *f; + bool ie_exists; + BMEdge *ie; + + if (i == 0) { + if (STACK_SIZE(iv_ls_a) != 2) { + continue; + } + ie_vs = iv_ls_a; + f = f_a; + } + else { + if (STACK_SIZE(iv_ls_b) != 2) { + continue; + } + ie_vs = iv_ls_b; + f = f_b; + } + + /* possible but unlikely we get this - for edge-edge intersection */ + ie = BM_edge_exists(UNPACK2(ie_vs)); + if (ie == NULL) { + ie_exists = false; + /* one of the verts must be new if we are making an edge + * ...no, we need this in case 2x quads intersect at either ends. + * if not (ie_vs[0].index == -1 or ie_vs[1].index == -1): + * continue */ + ie = BM_edge_create(s->bm, UNPACK2(ie_vs), NULL, 0); + BLI_gset_insert(s->wire_edges, ie); + } + else { + ie_exists = true; + /* may already exist */ + BLI_gset_add(s->wire_edges, ie); + + if (BM_edge_in_face(ie, f)) { + continue; + } + } + + face_edges_add(s, BM_elem_index_get(f), ie, ie_exists); + // BLI_assert(len(ie_vs) <= 2) + } + } finally: - for (i = 0; i < STACK_SIZE(iv_ls_a); i++) { - BM_ELEM_API_FLAG_DISABLE(iv_ls_a[i], VERT_VISIT_A); \ - } - for (i = 0; i < STACK_SIZE(iv_ls_b); i++) { - BM_ELEM_API_FLAG_DISABLE(iv_ls_b[i], VERT_VISIT_B); \ - } - + for (i = 0; i < STACK_SIZE(iv_ls_a); i++) { + BM_ELEM_API_FLAG_DISABLE(iv_ls_a[i], VERT_VISIT_A); + } + for (i = 0; i < STACK_SIZE(iv_ls_b); i++) { + BM_ELEM_API_FLAG_DISABLE(iv_ls_b[i], VERT_VISIT_B); + } } #ifdef USE_BVH struct RaycastData { - const float **looptris; - BLI_Buffer *z_buffer; + const float **looptris; + BLI_Buffer *z_buffer; }; -#ifdef USE_KDOPBVH_WATERTIGHT +# ifdef USE_KDOPBVH_WATERTIGHT static const struct IsectRayPrecalc isect_precalc_x = {1, 2, 0, 0, 0, 1}; -#endif +# endif static void raycast_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *UNUSED(hit)) { - struct RaycastData *raycast_data = userdata; - const float **looptris = raycast_data->looptris; - const float *v0 = looptris[index * 3 + 0]; - const float *v1 = looptris[index * 3 + 1]; - const float *v2 = looptris[index * 3 + 2]; - float dist; - - if ( -#ifdef USE_KDOPBVH_WATERTIGHT - isect_ray_tri_watertight_v3(ray->origin, &isect_precalc_x, v0, v1, v2, &dist, NULL) -#else - isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON) -#endif - ) - { - if (dist >= 0.0f) { -#ifdef USE_DUMP - printf("%s:\n", __func__); - print_v3(" origin", ray->origin); - print_v3(" direction", ray->direction); - printf(" dist %f\n", dist); - print_v3(" v0", v0); - print_v3(" v1", v1); - print_v3(" v2", v2); -#endif - -#ifdef USE_DUMP - printf("%s: Adding depth %f\n", __func__, dist); -#endif - BLI_buffer_append(raycast_data->z_buffer, float, dist); - } - } + struct RaycastData *raycast_data = userdata; + const float **looptris = raycast_data->looptris; + const float *v0 = looptris[index * 3 + 0]; + const float *v1 = looptris[index * 3 + 1]; + const float *v2 = looptris[index * 3 + 2]; + float dist; + + if ( +# ifdef USE_KDOPBVH_WATERTIGHT + isect_ray_tri_watertight_v3(ray->origin, &isect_precalc_x, v0, v1, v2, &dist, NULL) +# else + isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON) +# endif + ) { + if (dist >= 0.0f) { +# ifdef USE_DUMP + printf("%s:\n", __func__); + print_v3(" origin", ray->origin); + print_v3(" direction", ray->direction); + printf(" dist %f\n", dist); + print_v3(" v0", v0); + print_v3(" v1", v1); + print_v3(" v2", v2); +# endif + +# ifdef USE_DUMP + printf("%s: Adding depth %f\n", __func__, dist); +# endif + BLI_buffer_append(raycast_data->z_buffer, float, dist); + } + } } -static int isect_bvhtree_point_v3( - BVHTree *tree, - const float **looptris, - const float co[3]) +static int isect_bvhtree_point_v3(BVHTree *tree, const float **looptris, const float co[3]) { - BLI_buffer_declare_static(float, z_buffer, BLI_BUFFER_NOP, 64); - - struct RaycastData raycast_data = { - looptris, - &z_buffer, - }; - BVHTreeRayHit hit = {0}; - float dir[3] = {1.0f, 0.0f, 0.0f}; - - /* Need to initialize hit even tho it's not used. - * This is to make it so kdotree believes we didn't intersect anything and - * keeps calling the intersect callback. - */ - hit.index = -1; - hit.dist = BVH_RAYCAST_DIST_MAX; - - BLI_bvhtree_ray_cast(tree, - co, dir, - 0.0f, - &hit, - raycast_callback, - &raycast_data); - -#ifdef USE_DUMP - printf("%s: Total intersections: %d\n", __func__, z_buffer.count); -#endif - - int num_isect; - - if (z_buffer.count == 0) { - num_isect = 0; - } - else if (z_buffer.count == 1) { - num_isect = 1; - } - else { - /* 2 or more */ - const float eps = FLT_EPSILON * 10; - num_isect = 1; /* always count first */ - - qsort(z_buffer.data, z_buffer.count, sizeof(float), BLI_sortutil_cmp_float); - - const float *depth_arr = z_buffer.data; - float depth_last = depth_arr[0]; - - for (uint i = 1; i < z_buffer.count; i++) { - if (depth_arr[i] - depth_last > eps) { - depth_last = depth_arr[i]; - num_isect++; - } - } - - BLI_buffer_free(&z_buffer); - } - - - // return (num_isect & 1) == 1; - return num_isect; + BLI_buffer_declare_static(float, z_buffer, BLI_BUFFER_NOP, 64); + + struct RaycastData raycast_data = { + looptris, + &z_buffer, + }; + BVHTreeRayHit hit = {0}; + float dir[3] = {1.0f, 0.0f, 0.0f}; + + /* Need to initialize hit even tho it's not used. + * This is to make it so kdotree believes we didn't intersect anything and + * keeps calling the intersect callback. + */ + hit.index = -1; + hit.dist = BVH_RAYCAST_DIST_MAX; + + BLI_bvhtree_ray_cast(tree, co, dir, 0.0f, &hit, raycast_callback, &raycast_data); + +# ifdef USE_DUMP + printf("%s: Total intersections: %d\n", __func__, z_buffer.count); +# endif + + int num_isect; + + if (z_buffer.count == 0) { + num_isect = 0; + } + else if (z_buffer.count == 1) { + num_isect = 1; + } + else { + /* 2 or more */ + const float eps = FLT_EPSILON * 10; + num_isect = 1; /* always count first */ + + qsort(z_buffer.data, z_buffer.count, sizeof(float), BLI_sortutil_cmp_float); + + const float *depth_arr = z_buffer.data; + float depth_last = depth_arr[0]; + + for (uint i = 1; i < z_buffer.count; i++) { + if (depth_arr[i] - depth_last > eps) { + depth_last = depth_arr[i]; + num_isect++; + } + } + + BLI_buffer_free(&z_buffer); + } + + // return (num_isect & 1) == 1; + return num_isect; } -#endif /* USE_BVH */ +#endif /* USE_BVH */ /** * Intersect tessellated faces @@ -972,710 +950,690 @@ static int isect_bvhtree_point_v3( * \param boolean_mode: -1: no-boolean, 0: intersection... see #BMESH_ISECT_BOOLEAN_ISECT. * \return true if the mesh is changed (intersections cut or faces removed from boolean). */ -bool BM_mesh_intersect( - BMesh *bm, - struct BMLoop *(*looptris)[3], const int looptris_tot, - int (*test_fn)(BMFace *f, void *user_data), void *user_data, - const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, - const bool use_partial_connect, const bool use_edge_tag, const int boolean_mode, - const float eps) +bool BM_mesh_intersect(BMesh *bm, + struct BMLoop *(*looptris)[3], + const int looptris_tot, + int (*test_fn)(BMFace *f, void *user_data), + void *user_data, + const bool use_self, + const bool use_separate, + const bool use_dissolve, + const bool use_island_connect, + const bool use_partial_connect, + const bool use_edge_tag, + const int boolean_mode, + const float eps) { - struct ISectState s; - const int totface_orig = bm->totface; + struct ISectState s; + const int totface_orig = bm->totface; - /* use to check if we made any changes */ - bool has_edit_isect = false, has_edit_boolean = false; + /* use to check if we made any changes */ + bool has_edit_isect = false, has_edit_boolean = false; - /* needed for boolean, since cutting up faces moves the loops within the face */ - const float **looptri_coords = NULL; + /* needed for boolean, since cutting up faces moves the loops within the face */ + const float **looptri_coords = NULL; #ifdef USE_BVH - BVHTree *tree_a, *tree_b; - uint tree_overlap_tot; - BVHTreeOverlap *overlap; + BVHTree *tree_a, *tree_b; + uint tree_overlap_tot; + BVHTreeOverlap *overlap; #else - int i_a, i_b; + int i_a, i_b; #endif - s.bm = bm; + s.bm = bm; - s.edgetri_cache = BLI_ghash_new(BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, __func__); + s.edgetri_cache = BLI_ghash_new( + BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, __func__); - s.edge_verts = BLI_ghash_ptr_new(__func__); - s.face_edges = BLI_ghash_int_new(__func__); - s.wire_edges = BLI_gset_ptr_new(__func__); - s.vert_dissolve = NULL; + s.edge_verts = BLI_ghash_ptr_new(__func__); + s.face_edges = BLI_ghash_int_new(__func__); + s.wire_edges = BLI_gset_ptr_new(__func__); + s.vert_dissolve = NULL; - s.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + s.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); - /* setup epsilon from base */ - s.epsilon.eps = eps; - s.epsilon.eps2x = eps * 2.0f; - s.epsilon.eps_margin = s.epsilon.eps2x * 10.0f; + /* setup epsilon from base */ + s.epsilon.eps = eps; + s.epsilon.eps2x = eps * 2.0f; + s.epsilon.eps_margin = s.epsilon.eps2x * 10.0f; - s.epsilon.eps_sq = s.epsilon.eps * s.epsilon.eps; - s.epsilon.eps2x_sq = s.epsilon.eps2x * s.epsilon.eps2x; - s.epsilon.eps_margin_sq = s.epsilon.eps_margin * s.epsilon.eps_margin; + s.epsilon.eps_sq = s.epsilon.eps * s.epsilon.eps; + s.epsilon.eps2x_sq = s.epsilon.eps2x * s.epsilon.eps2x; + s.epsilon.eps_margin_sq = s.epsilon.eps_margin * s.epsilon.eps_margin; - BM_mesh_elem_index_ensure( - bm, - BM_VERT | - BM_EDGE | + BM_mesh_elem_index_ensure(bm, + BM_VERT | BM_EDGE | #ifdef USE_NET - BM_FACE | + BM_FACE | #endif - 0); - + 0); - BM_mesh_elem_table_ensure( - bm, + BM_mesh_elem_table_ensure(bm, #ifdef USE_SPLICE - BM_EDGE | + BM_EDGE | #endif #ifdef USE_NET - BM_FACE | + BM_FACE | #endif - 0); + 0); #ifdef USE_DISSOLVE - if (use_dissolve) { - BM_mesh_elem_hflag_disable_all(bm, BM_EDGE | BM_VERT, BM_ELEM_TAG, false); - } + if (use_dissolve) { + BM_mesh_elem_hflag_disable_all(bm, BM_EDGE | BM_VERT, BM_ELEM_TAG, false); + } #else - UNUSED_VARS(use_dissolve); + UNUSED_VARS(use_dissolve); #endif #ifdef USE_DUMP - printf("data = [\n"); + printf("data = [\n"); #endif - if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) { - /* keep original geometrty for raycast callbacks */ - float **cos; - int i, j; + if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) { + /* keep original geometrty for raycast callbacks */ + float **cos; + int i, j; - cos = MEM_mallocN((size_t)looptris_tot * sizeof(*looptri_coords) * 3, __func__); - for (i = 0, j = 0; i < looptris_tot; i++) { - cos[j++] = looptris[i][0]->v->co; - cos[j++] = looptris[i][1]->v->co; - cos[j++] = looptris[i][2]->v->co; - } - looptri_coords = (const float **)cos; - } + cos = MEM_mallocN((size_t)looptris_tot * sizeof(*looptri_coords) * 3, __func__); + for (i = 0, j = 0; i < looptris_tot; i++) { + cos[j++] = looptris[i][0]->v->co; + cos[j++] = looptris[i][1]->v->co; + cos[j++] = looptris[i][2]->v->co; + } + looptri_coords = (const float **)cos; + } #ifdef USE_BVH - { - int i; - tree_a = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8); - for (i = 0; i < looptris_tot; i++) { - if (test_fn(looptris[i][0]->f, user_data) == 0) { - const float t_cos[3][3] = { - {UNPACK3(looptris[i][0]->v->co)}, - {UNPACK3(looptris[i][1]->v->co)}, - {UNPACK3(looptris[i][2]->v->co)}, - }; - - BLI_bvhtree_insert(tree_a, i, (const float *)t_cos, 3); - } - } - BLI_bvhtree_balance(tree_a); - } - - if (use_self == false) { - int i; - tree_b = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8); - for (i = 0; i < looptris_tot; i++) { - if (test_fn(looptris[i][0]->f, user_data) == 1) { - const float t_cos[3][3] = { - {UNPACK3(looptris[i][0]->v->co)}, - {UNPACK3(looptris[i][1]->v->co)}, - {UNPACK3(looptris[i][2]->v->co)}, - }; - - BLI_bvhtree_insert(tree_b, i, (const float *)t_cos, 3); - } - } - BLI_bvhtree_balance(tree_b); - } - else { - tree_b = tree_a; - } - - overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot, NULL, NULL); - - if (overlap) { - uint i; - - for (i = 0; i < tree_overlap_tot; i++) { -#ifdef USE_DUMP - printf(" ((%d, %d), (\n", - overlap[i].indexA, - overlap[i].indexB); -#endif - bm_isect_tri_tri( - &s, - overlap[i].indexA, - overlap[i].indexB, - looptris[overlap[i].indexA], - looptris[overlap[i].indexB]); -#ifdef USE_DUMP - printf(")),\n"); -#endif - } - MEM_freeN(overlap); - } - - if (boolean_mode == BMESH_ISECT_BOOLEAN_NONE) { - /* no booleans, just free immediate */ - BLI_bvhtree_free(tree_a); - if (tree_a != tree_b) { - BLI_bvhtree_free(tree_b); - } - } + { + int i; + tree_a = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8); + for (i = 0; i < looptris_tot; i++) { + if (test_fn(looptris[i][0]->f, user_data) == 0) { + const float t_cos[3][3] = { + {UNPACK3(looptris[i][0]->v->co)}, + {UNPACK3(looptris[i][1]->v->co)}, + {UNPACK3(looptris[i][2]->v->co)}, + }; + + BLI_bvhtree_insert(tree_a, i, (const float *)t_cos, 3); + } + } + BLI_bvhtree_balance(tree_a); + } + + if (use_self == false) { + int i; + tree_b = BLI_bvhtree_new(looptris_tot, s.epsilon.eps_margin, 8, 8); + for (i = 0; i < looptris_tot; i++) { + if (test_fn(looptris[i][0]->f, user_data) == 1) { + const float t_cos[3][3] = { + {UNPACK3(looptris[i][0]->v->co)}, + {UNPACK3(looptris[i][1]->v->co)}, + {UNPACK3(looptris[i][2]->v->co)}, + }; + + BLI_bvhtree_insert(tree_b, i, (const float *)t_cos, 3); + } + } + BLI_bvhtree_balance(tree_b); + } + else { + tree_b = tree_a; + } + + overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot, NULL, NULL); + + if (overlap) { + uint i; + + for (i = 0; i < tree_overlap_tot; i++) { +# ifdef USE_DUMP + printf(" ((%d, %d), (\n", overlap[i].indexA, overlap[i].indexB); +# endif + bm_isect_tri_tri(&s, + overlap[i].indexA, + overlap[i].indexB, + looptris[overlap[i].indexA], + looptris[overlap[i].indexB]); +# ifdef USE_DUMP + printf(")),\n"); +# endif + } + MEM_freeN(overlap); + } + + if (boolean_mode == BMESH_ISECT_BOOLEAN_NONE) { + /* no booleans, just free immediate */ + BLI_bvhtree_free(tree_a); + if (tree_a != tree_b) { + BLI_bvhtree_free(tree_b); + } + } #else - { - for (i_a = 0; i_a < looptris_tot; i_a++) { - const int t_a = test_fn(looptris[i_a][0]->f, user_data); - for (i_b = i_a + 1; i_b < looptris_tot; i_b++) { - const int t_b = test_fn(looptris[i_b][0]->f, user_data); - - if (use_self) { - if ((t_a != 0) || (t_b != 0)) { - continue; - } - } - else { - if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) { - continue; - } - } - -#ifdef USE_DUMP - printf(" ((%d, %d), (", - i_a, i_b); -#endif - bm_isect_tri_tri( - &s, - i_a, - i_b, - looptris[i_a], - looptris[i_b]); -#ifdef USE_DUMP - printf(")),\n"); -#endif - } - } - } -#endif /* USE_BVH */ + { + for (i_a = 0; i_a < looptris_tot; i_a++) { + const int t_a = test_fn(looptris[i_a][0]->f, user_data); + for (i_b = i_a + 1; i_b < looptris_tot; i_b++) { + const int t_b = test_fn(looptris[i_b][0]->f, user_data); + + if (use_self) { + if ((t_a != 0) || (t_b != 0)) { + continue; + } + } + else { + if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) { + continue; + } + } + +# ifdef USE_DUMP + printf(" ((%d, %d), (", i_a, i_b); +# endif + bm_isect_tri_tri(&s, i_a, i_b, looptris[i_a], looptris[i_b]); +# ifdef USE_DUMP + printf(")),\n"); +# endif + } + } + } +#endif /* USE_BVH */ #ifdef USE_DUMP - printf("]\n"); + printf("]\n"); #endif - /* --------- */ + /* --------- */ #ifdef USE_SPLICE - { - GHashIterator gh_iter; - - GHASH_ITER (gh_iter, s.edge_verts) { - BMEdge *e = BLI_ghashIterator_getKey(&gh_iter); - struct LinkBase *v_ls_base = BLI_ghashIterator_getValue(&gh_iter); - - BMVert *v_start; - BMVert *v_end; - BMVert *v_prev; - bool is_wire; - - LinkNode *node; - - /* direction is arbitrary, could be swapped */ - v_start = e->v1; - v_end = e->v2; - - if (v_ls_base->list_len > 1) { - edge_verts_sort(v_start->co, v_ls_base); - } - -#ifdef USE_DUMP - printf("# SPLITTING EDGE: %d, %d\n", BM_elem_index_get(e), v_ls_base->list_len); + { + GHashIterator gh_iter; + + GHASH_ITER (gh_iter, s.edge_verts) { + BMEdge *e = BLI_ghashIterator_getKey(&gh_iter); + struct LinkBase *v_ls_base = BLI_ghashIterator_getValue(&gh_iter); + + BMVert *v_start; + BMVert *v_end; + BMVert *v_prev; + bool is_wire; + + LinkNode *node; + + /* direction is arbitrary, could be swapped */ + v_start = e->v1; + v_end = e->v2; + + if (v_ls_base->list_len > 1) { + edge_verts_sort(v_start->co, v_ls_base); + } + +# ifdef USE_DUMP + printf("# SPLITTING EDGE: %d, %d\n", BM_elem_index_get(e), v_ls_base->list_len); +# endif + /* intersect */ + is_wire = BLI_gset_haskey(s.wire_edges, e); + +# ifdef USE_PARANOID + for (node = v_ls_base->list; node; node = node->next) { + BMVert *_v = node->link; + BLI_assert(len_squared_v3v3(_v->co, e->v1->co) > s.epsilon.eps_sq); + BLI_assert(len_squared_v3v3(_v->co, e->v2->co) > s.epsilon.eps_sq); + } +# endif + + v_prev = v_start; + + for (node = v_ls_base->list; node; node = node->next) { + BMVert *vi = node->link; + const float fac = line_point_factor_v3(vi->co, e->v1->co, e->v2->co); + + if (BM_vert_in_edge(e, v_prev)) { + BMEdge *e_split; + v_prev = BM_edge_split(bm, e, v_prev, &e_split, clamp_f(fac, 0.0f, 1.0f)); + BLI_assert(BM_vert_in_edge(e, v_end)); + + if (!BM_edge_exists(v_prev, vi) && !BM_vert_splice_check_double(v_prev, vi) && + !BM_vert_pair_share_face_check(v_prev, vi)) { + BM_vert_splice(bm, vi, v_prev); + } + else { + copy_v3_v3(v_prev->co, vi->co); + } + v_prev = vi; + if (is_wire) { + BLI_gset_insert(s.wire_edges, e_split); + } + } + } + UNUSED_VARS_NDEBUG(v_end); + } + } #endif - /* intersect */ - is_wire = BLI_gset_haskey(s.wire_edges, e); -#ifdef USE_PARANOID - for (node = v_ls_base->list; node; node = node->next) { - BMVert *_v = node->link; - BLI_assert(len_squared_v3v3(_v->co, e->v1->co) > s.epsilon.eps_sq); - BLI_assert(len_squared_v3v3(_v->co, e->v2->co) > s.epsilon.eps_sq); - } -#endif + /* important to handle before edgenet */ +#ifdef USE_DISSOLVE + if (use_dissolve && (boolean_mode == BMESH_ISECT_BOOLEAN_NONE)) { + /* first pass */ + BMVert *(*splice_ls)[2]; + STACK_DECLARE(splice_ls); + LinkNode *node; + + for (node = s.vert_dissolve; node; node = node->next) { + BMVert *v = node->link; + if (BM_elem_flag_test(v, BM_ELEM_TAG)) { + if (!BM_vert_is_edge_pair(v)) { + BM_elem_flag_disable(v, BM_ELEM_TAG); + } + } + } + + splice_ls = MEM_mallocN(BLI_gset_len(s.wire_edges) * sizeof(*splice_ls), __func__); + STACK_INIT(splice_ls, BLI_gset_len(s.wire_edges)); + + for (node = s.vert_dissolve; node; node = node->next) { + BMEdge *e_pair[2]; + BMVert *v = node->link; + BMVert *v_a, *v_b; + + if (!BM_elem_flag_test(v, BM_ELEM_TAG)) { + continue; + } + + /* get chain */ + e_pair[0] = v->e; + e_pair[1] = BM_DISK_EDGE_NEXT(v->e, v); + + if (BM_elem_flag_test(e_pair[0], BM_ELEM_TAG) || BM_elem_flag_test(e_pair[1], BM_ELEM_TAG)) { + continue; + } + + v_a = BM_edge_other_vert(e_pair[0], v); + v_b = BM_edge_other_vert(e_pair[1], v); + + /* simple case */ + if (BM_elem_flag_test(v_a, BM_ELEM_TAG) && BM_elem_flag_test(v_b, BM_ELEM_TAG)) { + /* only start on an edge-case */ + /* pass */ + } + else if ((!BM_elem_flag_test(v_a, BM_ELEM_TAG)) && (!BM_elem_flag_test(v_b, BM_ELEM_TAG))) { + /* simple case, single edge spans face */ + BMVert **splice_pair; + BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG); + splice_pair = STACK_PUSH_RET(splice_ls); + splice_pair[0] = v; + splice_pair[1] = v_b; +# ifdef USE_DUMP + printf("# Simple Case!\n"); +# endif + } + else { +# ifdef USE_PARANOID + BMEdge *e_keep; +# endif + BMEdge *e; + BMEdge *e_step; + BMVert *v_step; + + /* walk the chain! */ + if (BM_elem_flag_test(v_a, BM_ELEM_TAG)) { + e = e_pair[0]; +# ifdef USE_PARANOID + e_keep = e_pair[1]; +# endif + } + else { + SWAP(BMVert *, v_a, v_b); + e = e_pair[1]; +# ifdef USE_PARANOID + e_keep = e_pair[0]; +# endif + } + + /* WALK */ + v_step = v; + e_step = e; + + while (true) { + BMEdge *e_next; + BMVert *v_next; + + v_next = BM_edge_other_vert(e_step, v_step); + BM_elem_flag_enable(e_step, BM_ELEM_TAG); + if (!BM_elem_flag_test(v_next, BM_ELEM_TAG)) { + BMVert **splice_pair; +# ifdef USE_PARANOID + BLI_assert(e_step != e_keep); +# endif + splice_pair = STACK_PUSH_RET(splice_ls); + splice_pair[0] = v; + splice_pair[1] = v_next; + break; + } + else { + e_next = bm_vert_other_edge(v_next, e_step); + } + + e_step = e_next; + v_step = v_next; + BM_elem_flag_enable(e_step, BM_ELEM_TAG); +# ifdef USE_PARANOID + BLI_assert(e_step != e_keep); +# endif +# ifdef USE_DUMP + printf("# walk step %p %p\n", e_next, v_next); +# endif + } +# ifdef USE_PARANOID + BLI_assert(BM_elem_flag_test(e_keep, BM_ELEM_TAG) == 0); +# endif + } + } + + /* Remove edges! */ + { + GHashIterator gh_iter; + + GHASH_ITER (gh_iter, s.face_edges) { + struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter); + LinkNode **node_prev_p; + uint i; + + node_prev_p = &e_ls_base->list; + for (i = 0, node = e_ls_base->list; node; i++, node = node->next) { + BMEdge *e = node->link; + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + /* allocated by arena, don't free */ + *node_prev_p = node->next; + e_ls_base->list_len--; + } + else { + node_prev_p = &node->next; + } + } + } + } + + { + BMIter eiter; + BMEdge *e, *e_next; + + BM_ITER_MESH_MUTABLE (e, e_next, &eiter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + + /* in rare and annoying cases, + * there can be faces from 's.face_edges' removed by the edges. + * These are degenerate cases, so just make sure we don't reference the faces again. */ + if (e->l) { + BMLoop *l_iter = e->l; + BMFace **faces; + + faces = bm->ftable; + + do { + const int f_index = BM_elem_index_get(l_iter->f); + if (f_index >= 0) { + BLI_assert(f_index < totface_orig); + /* we could check if these are in: 's.face_edges', but easier just to remove */ + faces[f_index] = NULL; + } + } while ((l_iter = l_iter->radial_next) != e->l); + } + + BLI_gset_remove(s.wire_edges, e, NULL); + BM_edge_kill(bm, e); + } + } + } + + /* Remove verts! */ + { + GSet *verts_invalid = BLI_gset_ptr_new(__func__); + + for (node = s.vert_dissolve; node; node = node->next) { + /* arena allocated, don't free */ + BMVert *v = node->link; + if (BM_elem_flag_test(v, BM_ELEM_TAG)) { + if (!v->e) { + BLI_gset_add(verts_invalid, v); + BM_vert_kill(bm, v); + } + } + } + + { + uint i; + for (i = 0; i < STACK_SIZE(splice_ls); i++) { + if (!BLI_gset_haskey(verts_invalid, splice_ls[i][0]) && + !BLI_gset_haskey(verts_invalid, splice_ls[i][1])) { + if (!BM_edge_exists(UNPACK2(splice_ls[i])) && + !BM_vert_splice_check_double(UNPACK2(splice_ls[i]))) { + BM_vert_splice(bm, splice_ls[i][1], splice_ls[i][0]); + } + } + } + } + + BLI_gset_free(verts_invalid, NULL); + } + + MEM_freeN(splice_ls); + } +#endif /* USE_DISSOLVE */ + + /* now split faces */ +#ifdef USE_NET + { + GHashIterator gh_iter; + BMFace **faces; - v_prev = v_start; - - for (node = v_ls_base->list; node; node = node->next) { - BMVert *vi = node->link; - const float fac = line_point_factor_v3(vi->co, e->v1->co, e->v2->co); - - if (BM_vert_in_edge(e, v_prev)) { - BMEdge *e_split; - v_prev = BM_edge_split(bm, e, v_prev, &e_split, clamp_f(fac, 0.0f, 1.0f)); - BLI_assert(BM_vert_in_edge(e, v_end)); - - if (!BM_edge_exists(v_prev, vi) && - !BM_vert_splice_check_double(v_prev, vi) && - !BM_vert_pair_share_face_check(v_prev, vi)) - { - BM_vert_splice(bm, vi, v_prev); - } - else { - copy_v3_v3(v_prev->co, vi->co); - } - v_prev = vi; - if (is_wire) { - BLI_gset_insert(s.wire_edges, e_split); - } - } - } - UNUSED_VARS_NDEBUG(v_end); - } - } -#endif + MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + faces = bm->ftable; - /* important to handle before edgenet */ -#ifdef USE_DISSOLVE - if (use_dissolve && (boolean_mode == BMESH_ISECT_BOOLEAN_NONE)) { - /* first pass */ - BMVert *(*splice_ls)[2]; - STACK_DECLARE(splice_ls); - LinkNode *node; - - - for (node = s.vert_dissolve; node; node = node->next) { - BMVert *v = node->link; - if (BM_elem_flag_test(v, BM_ELEM_TAG)) { - if (!BM_vert_is_edge_pair(v)) { - BM_elem_flag_disable(v, BM_ELEM_TAG); - } - } - } - - splice_ls = MEM_mallocN(BLI_gset_len(s.wire_edges) * sizeof(*splice_ls), __func__); - STACK_INIT(splice_ls, BLI_gset_len(s.wire_edges)); - - for (node = s.vert_dissolve; node; node = node->next) { - BMEdge *e_pair[2]; - BMVert *v = node->link; - BMVert *v_a, *v_b; - - if (!BM_elem_flag_test(v, BM_ELEM_TAG)) { - continue; - } - - /* get chain */ - e_pair[0] = v->e; - e_pair[1] = BM_DISK_EDGE_NEXT(v->e, v); - - if (BM_elem_flag_test(e_pair[0], BM_ELEM_TAG) || - BM_elem_flag_test(e_pair[1], BM_ELEM_TAG)) - { - continue; - } - - v_a = BM_edge_other_vert(e_pair[0], v); - v_b = BM_edge_other_vert(e_pair[1], v); - - /* simple case */ - if (BM_elem_flag_test(v_a, BM_ELEM_TAG) && - BM_elem_flag_test(v_b, BM_ELEM_TAG)) - { - /* only start on an edge-case */ - /* pass */ - } - else if ((!BM_elem_flag_test(v_a, BM_ELEM_TAG)) && - (!BM_elem_flag_test(v_b, BM_ELEM_TAG))) - { - /* simple case, single edge spans face */ - BMVert **splice_pair; - BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG); - splice_pair = STACK_PUSH_RET(splice_ls); - splice_pair[0] = v; - splice_pair[1] = v_b; -#ifdef USE_DUMP - printf("# Simple Case!\n"); -#endif - } - else { -#ifdef USE_PARANOID - BMEdge *e_keep; -#endif - BMEdge *e; - BMEdge *e_step; - BMVert *v_step; + GHASH_ITER (gh_iter, s.face_edges) { + const int f_index = POINTER_AS_INT(BLI_ghashIterator_getKey(&gh_iter)); + BMFace *f; + struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter); - /* walk the chain! */ - if (BM_elem_flag_test(v_a, BM_ELEM_TAG)) { - e = e_pair[0]; -#ifdef USE_PARANOID - e_keep = e_pair[1]; -#endif - } - else { - SWAP(BMVert *, v_a, v_b); - e = e_pair[1]; -#ifdef USE_PARANOID - e_keep = e_pair[0]; -#endif - } + BLI_assert(f_index >= 0 && f_index < totface_orig); - /* WALK */ - v_step = v; - e_step = e; + f = faces[f_index]; + if (UNLIKELY(f == NULL)) { + continue; + } - while (true) { - BMEdge *e_next; - BMVert *v_next; + BLI_assert(BM_elem_index_get(f) == f_index); - v_next = BM_edge_other_vert(e_step, v_step); - BM_elem_flag_enable(e_step, BM_ELEM_TAG); - if (!BM_elem_flag_test(v_next, BM_ELEM_TAG)) { - BMVert **splice_pair; -#ifdef USE_PARANOID - BLI_assert(e_step != e_keep); -#endif - splice_pair = STACK_PUSH_RET(splice_ls); - splice_pair[0] = v; - splice_pair[1] = v_next; - break; - } - else { - e_next = bm_vert_other_edge(v_next, e_step); - } - - e_step = e_next; - v_step = v_next; - BM_elem_flag_enable(e_step, BM_ELEM_TAG); -#ifdef USE_PARANOID - BLI_assert(e_step != e_keep); -#endif -#ifdef USE_DUMP - printf("# walk step %p %p\n", e_next, v_next); -#endif - } -#ifdef USE_PARANOID - BLI_assert(BM_elem_flag_test(e_keep, BM_ELEM_TAG) == 0); -#endif - } - } - - /* Remove edges! */ - { - GHashIterator gh_iter; - - GHASH_ITER (gh_iter, s.face_edges) { - struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter); - LinkNode **node_prev_p; - uint i; - - node_prev_p = &e_ls_base->list; - for (i = 0, node = e_ls_base->list; node; i++, node = node->next) { - BMEdge *e = node->link; - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - /* allocated by arena, don't free */ - *node_prev_p = node->next; - e_ls_base->list_len--; - } - else { - node_prev_p = &node->next; - } - } - } - } - - { - BMIter eiter; - BMEdge *e, *e_next; - - BM_ITER_MESH_MUTABLE (e, e_next, &eiter, bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - - /* in rare and annoying cases, - * there can be faces from 's.face_edges' removed by the edges. - * These are degenerate cases, so just make sure we don't reference the faces again. */ - if (e->l) { - BMLoop *l_iter = e->l; - BMFace **faces; - - faces = bm->ftable; - - do { - const int f_index = BM_elem_index_get(l_iter->f); - if (f_index >= 0) { - BLI_assert(f_index < totface_orig); - /* we could check if these are in: 's.face_edges', but easier just to remove */ - faces[f_index] = NULL; - } - } while ((l_iter = l_iter->radial_next) != e->l); - } - - BLI_gset_remove(s.wire_edges, e, NULL); - BM_edge_kill(bm, e); - } - } - } - - /* Remove verts! */ - { - GSet *verts_invalid = BLI_gset_ptr_new(__func__); - - for (node = s.vert_dissolve; node; node = node->next) { - /* arena allocated, don't free */ - BMVert *v = node->link; - if (BM_elem_flag_test(v, BM_ELEM_TAG)) { - if (!v->e) { - BLI_gset_add(verts_invalid, v); - BM_vert_kill(bm, v); - } - } - } - - { - uint i; - for (i = 0; i < STACK_SIZE(splice_ls); i++) { - if (!BLI_gset_haskey(verts_invalid, splice_ls[i][0]) && - !BLI_gset_haskey(verts_invalid, splice_ls[i][1])) - { - if (!BM_edge_exists(UNPACK2(splice_ls[i])) && - !BM_vert_splice_check_double(UNPACK2(splice_ls[i]))) - { - BM_vert_splice(bm, splice_ls[i][1], splice_ls[i][0]); - } - } - } - } - - BLI_gset_free(verts_invalid, NULL); - } - - MEM_freeN(splice_ls); - } -#endif /* USE_DISSOLVE */ - - - /* now split faces */ -#ifdef USE_NET - { - GHashIterator gh_iter; - BMFace **faces; + face_edges_split( + bm, f, e_ls_base, use_island_connect, use_partial_connect, mem_arena_edgenet); - MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + BLI_memarena_clear(mem_arena_edgenet); + } - faces = bm->ftable; - - GHASH_ITER (gh_iter, s.face_edges) { - const int f_index = POINTER_AS_INT(BLI_ghashIterator_getKey(&gh_iter)); - BMFace *f; - struct LinkBase *e_ls_base = BLI_ghashIterator_getValue(&gh_iter); + BLI_memarena_free(mem_arena_edgenet); + } +#else + UNUSED_VARS(use_island_connect); +#endif /* USE_NET */ + (void)totface_orig; - BLI_assert(f_index >= 0 && f_index < totface_orig); +#ifdef USE_SEPARATE + if (use_separate) { + GSetIterator gs_iter; - f = faces[f_index]; - if (UNLIKELY(f == NULL)) { - continue; - } + BM_mesh_elem_hflag_disable_all(bm, BM_EDGE, BM_ELEM_TAG, false); - BLI_assert(BM_elem_index_get(f) == f_index); + GSET_ITER (gs_iter, s.wire_edges) { + BMEdge *e = BLI_gsetIterator_getKey(&gs_iter); + BM_elem_flag_enable(e, BM_ELEM_TAG); + } - face_edges_split(bm, f, e_ls_base, use_island_connect, use_partial_connect, mem_arena_edgenet); + BM_mesh_edgesplit(bm, false, true, false); + } + else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE || use_edge_tag) { + GSetIterator gs_iter; - BLI_memarena_clear(mem_arena_edgenet); - } + /* no need to clear for boolean */ - BLI_memarena_free(mem_arena_edgenet); - } + GSET_ITER (gs_iter, s.wire_edges) { + BMEdge *e = BLI_gsetIterator_getKey(&gs_iter); + BM_elem_flag_enable(e, BM_ELEM_TAG); + } + } #else - UNUSED_VARS(use_island_connect); -#endif /* USE_NET */ - (void)totface_orig; - -#ifdef USE_SEPARATE - if (use_separate) { - GSetIterator gs_iter; + (void)use_separate; +#endif /* USE_SEPARATE */ - BM_mesh_elem_hflag_disable_all(bm, BM_EDGE, BM_ELEM_TAG, false); + if ((boolean_mode != BMESH_ISECT_BOOLEAN_NONE)) { + BVHTree *tree_pair[2] = {tree_a, tree_b}; - GSET_ITER (gs_iter, s.wire_edges) { - BMEdge *e = BLI_gsetIterator_getKey(&gs_iter); - BM_elem_flag_enable(e, BM_ELEM_TAG); - } + /* group vars */ + int *groups_array; + int(*group_index)[2]; + int group_tot; + int i; + BMFace **ftable; - BM_mesh_edgesplit(bm, false, true, false); - } - else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE || use_edge_tag) { - GSetIterator gs_iter; + BM_mesh_elem_table_ensure(bm, BM_FACE); + ftable = bm->ftable; - /* no need to clear for boolean */ + /* wrap the face-test callback to make it into an edge-loop delimiter */ + struct LoopFilterWrap user_data_wrap = { + .test_fn = test_fn, + .user_data = user_data, + }; - GSET_ITER (gs_iter, s.wire_edges) { - BMEdge *e = BLI_gsetIterator_getKey(&gs_iter); - BM_elem_flag_enable(e, BM_ELEM_TAG); - } - } -#else - (void)use_separate; -#endif /* USE_SEPARATE */ - - if ((boolean_mode != BMESH_ISECT_BOOLEAN_NONE)) { - BVHTree *tree_pair[2] = {tree_a, tree_b}; - - /* group vars */ - int *groups_array; - int (*group_index)[2]; - int group_tot; - int i; - BMFace **ftable; - - BM_mesh_elem_table_ensure(bm, BM_FACE); - ftable = bm->ftable; - - /* wrap the face-test callback to make it into an edge-loop delimiter */ - struct LoopFilterWrap user_data_wrap = { - .test_fn = test_fn, - .user_data = user_data, - }; - - groups_array = MEM_mallocN(sizeof(*groups_array) * (size_t)bm->totface, __func__); - group_tot = BM_mesh_calc_face_groups( - bm, groups_array, &group_index, - bm_loop_filter_fn, &user_data_wrap, - 0, BM_EDGE); + groups_array = MEM_mallocN(sizeof(*groups_array) * (size_t)bm->totface, __func__); + group_tot = BM_mesh_calc_face_groups( + bm, groups_array, &group_index, bm_loop_filter_fn, &user_data_wrap, 0, BM_EDGE); #ifdef USE_DUMP - printf("%s: Total face-groups: %d\n", __func__, group_tot); + printf("%s: Total face-groups: %d\n", __func__, group_tot); #endif - /* Check if island is inside/outside */ - for (i = 0; i < group_tot; i++) { - int fg = group_index[i][0]; - int fg_end = group_index[i][1] + fg; - bool do_remove, do_flip; - - { - /* for now assyme this is an OK face to test with (not degenerate!) */ - BMFace *f = ftable[groups_array[fg]]; - float co[3]; - int hits; - int side = test_fn(f, user_data); - - if (side == -1) { - continue; - } - BLI_assert(ELEM(side, 0, 1)); - side = !side; - - // BM_face_calc_center_median(f, co); - BM_face_calc_point_in_face(f, co); - - hits = isect_bvhtree_point_v3(tree_pair[side], looptri_coords, co); - - switch (boolean_mode) { - case BMESH_ISECT_BOOLEAN_ISECT: - do_remove = ((hits & 1) != 1); - do_flip = false; - break; - case BMESH_ISECT_BOOLEAN_UNION: - do_remove = ((hits & 1) == 1); - do_flip = false; - break; - case BMESH_ISECT_BOOLEAN_DIFFERENCE: - do_remove = ((hits & 1) == 1) == side; - do_flip = (side == 0); - break; - } - } - - if (do_remove) { - for (; fg != fg_end; fg++) { - /* postpone killing the face since we access below, mark instead */ - // BM_face_kill_loose(bm, ftable[groups_array[fg]]); - ftable[groups_array[fg]]->mat_nr = -1; - } - } - else if (do_flip) { - for (; fg != fg_end; fg++) { - BM_face_normal_flip(bm, ftable[groups_array[fg]]); - } - } - - has_edit_boolean |= (do_flip || do_remove); - } - - MEM_freeN(groups_array); - MEM_freeN(group_index); + /* Check if island is inside/outside */ + for (i = 0; i < group_tot; i++) { + int fg = group_index[i][0]; + int fg_end = group_index[i][1] + fg; + bool do_remove, do_flip; + + { + /* for now assyme this is an OK face to test with (not degenerate!) */ + BMFace *f = ftable[groups_array[fg]]; + float co[3]; + int hits; + int side = test_fn(f, user_data); + + if (side == -1) { + continue; + } + BLI_assert(ELEM(side, 0, 1)); + side = !side; + + // BM_face_calc_center_median(f, co); + BM_face_calc_point_in_face(f, co); + + hits = isect_bvhtree_point_v3(tree_pair[side], looptri_coords, co); + + switch (boolean_mode) { + case BMESH_ISECT_BOOLEAN_ISECT: + do_remove = ((hits & 1) != 1); + do_flip = false; + break; + case BMESH_ISECT_BOOLEAN_UNION: + do_remove = ((hits & 1) == 1); + do_flip = false; + break; + case BMESH_ISECT_BOOLEAN_DIFFERENCE: + do_remove = ((hits & 1) == 1) == side; + do_flip = (side == 0); + break; + } + } + + if (do_remove) { + for (; fg != fg_end; fg++) { + /* postpone killing the face since we access below, mark instead */ + // BM_face_kill_loose(bm, ftable[groups_array[fg]]); + ftable[groups_array[fg]]->mat_nr = -1; + } + } + else if (do_flip) { + for (; fg != fg_end; fg++) { + BM_face_normal_flip(bm, ftable[groups_array[fg]]); + } + } + + has_edit_boolean |= (do_flip || do_remove); + } + + MEM_freeN(groups_array); + MEM_freeN(group_index); #ifdef USE_DISSOLVE - /* We have dissolve code above, this is alternative logic, - * we need to do it after the boolean is executed. */ - if (use_dissolve) { - LinkNode *node; - for (node = s.vert_dissolve; node; node = node->next) { - BMVert *v = node->link; - if (BM_vert_is_edge_pair(v)) { - /* we wont create degenerate faces from this */ - bool ok = true; - - /* would we create a 2-sided-face? - * if so, don't dissolve this since we may */ - if (v->e->l) { - BMLoop *l_iter = v->e->l; - do { - if (l_iter->f->len == 3) { - ok = false; - break; - } - } while ((l_iter = l_iter->radial_next) != v->e->l); - } - - if (ok) { - BM_vert_collapse_edge(bm, v->e, v, true, false); - } - } - } - } + /* We have dissolve code above, this is alternative logic, + * we need to do it after the boolean is executed. */ + if (use_dissolve) { + LinkNode *node; + for (node = s.vert_dissolve; node; node = node->next) { + BMVert *v = node->link; + if (BM_vert_is_edge_pair(v)) { + /* we wont create degenerate faces from this */ + bool ok = true; + + /* would we create a 2-sided-face? + * if so, don't dissolve this since we may */ + if (v->e->l) { + BMLoop *l_iter = v->e->l; + do { + if (l_iter->f->len == 3) { + ok = false; + break; + } + } while ((l_iter = l_iter->radial_next) != v->e->l); + } + + if (ok) { + BM_vert_collapse_edge(bm, v->e, v, true, false); + } + } + } + } #endif - { - int tot = bm->totface; - for (i = 0; i < tot; i++) { - if (ftable[i]->mat_nr == -1) { - BM_face_kill_loose(bm, ftable[i]); - } - } - } - } + { + int tot = bm->totface; + for (i = 0; i < tot; i++) { + if (ftable[i]->mat_nr == -1) { + BM_face_kill_loose(bm, ftable[i]); + } + } + } + } - if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) { - MEM_freeN((void *)looptri_coords); + if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) { + MEM_freeN((void *)looptri_coords); - /* no booleans, just free immediate */ - BLI_bvhtree_free(tree_a); - if (tree_a != tree_b) { - BLI_bvhtree_free(tree_b); - } - } + /* no booleans, just free immediate */ + BLI_bvhtree_free(tree_a); + if (tree_a != tree_b) { + BLI_bvhtree_free(tree_b); + } + } - has_edit_isect = (BLI_ghash_len(s.face_edges) != 0); + has_edit_isect = (BLI_ghash_len(s.face_edges) != 0); - /* cleanup */ - BLI_ghash_free(s.edgetri_cache, NULL, NULL); + /* cleanup */ + BLI_ghash_free(s.edgetri_cache, NULL, NULL); - BLI_ghash_free(s.edge_verts, NULL, NULL); - BLI_ghash_free(s.face_edges, NULL, NULL); - BLI_gset_free(s.wire_edges, NULL); + BLI_ghash_free(s.edge_verts, NULL, NULL); + BLI_ghash_free(s.face_edges, NULL, NULL); + BLI_gset_free(s.wire_edges, NULL); - BLI_memarena_free(s.mem_arena); + BLI_memarena_free(s.mem_arena); - return (has_edit_isect || has_edit_boolean); + return (has_edit_isect || has_edit_boolean); } |