diff options
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_intersect.c')
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect.c | 428 |
1 files changed, 402 insertions, 26 deletions
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index 19cf2d29aff..80b1780758d 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.c +++ b/source/blender/bmesh/tools/bmesh_intersect.c @@ -50,6 +50,7 @@ #endif #include "BLI_kdopbvh.h" +#include "BLI_buffer.h" #include "bmesh.h" #include "bmesh_intersect.h" /* own include */ @@ -70,12 +71,19 @@ #define USE_SEPARATE /* remove verts created by intersecting triangles */ #define USE_DISSOLVE +/* detect isolated holes and fill them */ +#define USE_NET_ISLAND_CONNECT /* strict asserts that may fail in practice (handy for debugging cases which should succeed) */ // #define USE_PARANOID /* use accelerated overlap check */ #define USE_BVH +// #define USE_BOOLEAN_RAYCAST_DRAW + +#ifdef USE_BOOLEAN_RAYCAST_DRAW +/* insert bl_debug_draw_quad_clear... here */ +#endif static void tri_v3_scale( float v1[3], float v2[3], float v3[3], @@ -147,21 +155,20 @@ 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; - ls_base = BLI_ghash_lookup(gh, key); - - if (ls_base) { - if (use_test && (BLI_linklist_index(ls_base->list, key) != -1)) { - return false; - } - } - else { - ls_base = BLI_memarena_alloc(mem_arena, sizeof(*ls_base)); + 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; - BLI_ghash_insert(gh, key, ls_base); + } + 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)); @@ -231,12 +238,13 @@ static void face_edges_add( #ifdef USE_NET static void face_edges_split( - BMesh *bm, - BMFace *f, - struct LinkBase *e_ls_base) + BMesh *bm, BMFace *f, struct LinkBase *e_ls_base, + bool use_island_connect, + MemArena *mem_arena_edgenet) { unsigned int i; - BMEdge **edge_arr = BLI_array_alloca(edge_arr, e_ls_base->list_len); + unsigned int 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); @@ -249,7 +257,30 @@ static void face_edges_split( printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len); #endif - BM_face_split_edgenet(bm, f, edge_arr, (int)e_ls_base->list_len, NULL, NULL); +#ifdef USE_NET_ISLAND_CONNECT + if (use_island_connect) { + unsigned int edge_arr_holes_len; + BMEdge **edge_arr_holes; + if (BM_face_split_edgenet_connect_islands( + bm, f, + edge_arr, edge_arr_len, + mem_arena_edgenet, + &edge_arr_holes, &edge_arr_holes_len)) + { + /* newly created wire edges need to be tagged */ + for (i = edge_arr_len; i < edge_arr_holes_len; i++) { + BM_elem_flag_enable(edge_arr_holes[i], BM_ELEM_TAG); + } + + 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 @@ -461,6 +492,35 @@ static BMVert *bm_isect_edge_tri( return NULL; } +struct LoopFilterWrap { + 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; +} + /** * Return true if we have any intersections. */ @@ -774,23 +834,146 @@ static void bm_isect_tri_tri( } } +#ifdef USE_BVH + +struct RaycastData { + const float **looptris; + BLI_Buffer *z_buffer; +}; + +#ifdef USE_KDOPBVH_WATERTIGHT +static const struct IsectRayPrecalc isect_precalc_x = {1, 2, 0, 0, 0, 1}; +#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__, depth); +#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]) +{ + 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 = FLT_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__, raycast_data.num_isect); +#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 (unsigned int 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 */ + /** * Intersect tessellated faces * leaving the resulting edges tagged. * * \param test_fn Return value: -1: skip, 0: tree_a, 1: tree_b (use_self == false) + * \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_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, + const int boolean_mode, const float eps) { struct ISectState s; bool has_isect; const int totface_orig = bm->totface; + /* 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; unsigned int tree_overlap_tot; @@ -799,6 +982,10 @@ bool BM_mesh_intersect( int i_a, i_b; #endif +#ifdef USE_BOOLEAN_RAYCAST_DRAW + bl_debug_draw_quad_clear(); +#endif + s.bm = bm; s.edgetri_cache = BLI_ghash_new(BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, __func__); @@ -840,13 +1027,31 @@ bool BM_mesh_intersect( 0); #ifdef 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); #endif #ifdef USE_DUMP printf("data = [\n"); #endif + 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; + } + #ifdef USE_BVH { int i; @@ -908,9 +1113,13 @@ bool BM_mesh_intersect( } MEM_freeN(overlap); } - BLI_bvhtree_free(tree_a); - if (tree_a != tree_b) { - BLI_bvhtree_free(tree_b); + + 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 @@ -979,7 +1188,7 @@ bool BM_mesh_intersect( } #ifdef USE_DUMP - printf("# SPLITTING EDGE: %d, %d\n", e_index, v_ls_base->list_len); + 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); @@ -999,7 +1208,8 @@ bool BM_mesh_intersect( const float fac = line_point_factor_v3(vi->co, e->v1->co, e->v2->co); if (BM_vert_in_edge(e, v_prev)) { - v_prev = BM_edge_split(bm, e, v_prev, NULL, CLAMPIS(fac, 0.0f, 1.0f)); + BMEdge *e_split; + v_prev = BM_edge_split(bm, e, v_prev, &e_split, CLAMPIS(fac, 0.0f, 1.0f)); BLI_assert(BM_vert_in_edge(e, v_end)); if (!BM_edge_exists(v_prev, vi) && @@ -1013,7 +1223,7 @@ bool BM_mesh_intersect( } v_prev = vi; if (is_wire) { - BLI_gset_insert(s.wire_edges, e); + BLI_gset_insert(s.wire_edges, e_split); } } } @@ -1025,7 +1235,7 @@ bool BM_mesh_intersect( /* 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); @@ -1249,6 +1459,8 @@ bool BM_mesh_intersect( GHashIterator gh_iter; BMFace **faces; + MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + faces = bm->ftable; GHASH_ITER (gh_iter, s.face_edges) { @@ -1265,9 +1477,15 @@ bool BM_mesh_intersect( BLI_assert(BM_elem_index_get(f) == f_index); - face_edges_split(bm, f, e_ls_base); + face_edges_split(bm, f, e_ls_base, use_island_connect, mem_arena_edgenet); + + BLI_memarena_clear(mem_arena_edgenet); } + + BLI_memarena_free(mem_arena_edgenet); } +#else + UNUSED_VARS(use_island_connect); #endif /* USE_NET */ (void)totface_orig; @@ -1284,10 +1502,168 @@ bool BM_mesh_intersect( BM_mesh_edgesplit(bm, false, true, false); } + else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) { + GSetIterator gs_iter; + + /* no need to clear for boolean */ + + 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); + +#ifdef USE_DUMP + 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_mean(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; + } + +#ifdef USE_BOOLEAN_RAYCAST_DRAW + { + unsigned int colors[4] = {0x00000000, 0xffffffff, 0xff000000, 0x0000ff}; + float co_other[3] = {UNPACK3(co)}; + co_other[0] += 1000.0f; + bl_debug_color_set(colors[(hits & 1) == 1]); + bl_debug_draw_edge_add(co, co_other); + } +#endif + + } + + 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]]); + } + } + } + + 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); + } + } + } + } +#endif + + { + 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); + + /* no booleans, just free immediate */ + BLI_bvhtree_free(tree_a); + if (tree_a != tree_b) { + BLI_bvhtree_free(tree_b); + } + } + has_isect = (BLI_ghash_size(s.face_edges) != 0); /* cleanup */ @@ -1299,5 +1675,5 @@ bool BM_mesh_intersect( BLI_memarena_free(s.mem_arena); - return has_isect; + return has_isect || (totface_orig != bm->totface); } |