diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-12-16 21:02:39 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-12-16 21:13:57 +0300 |
commit | 88191f7fa32530db8eeb78d131cb5d91dea8d435 (patch) | |
tree | 6e903cc1d267162126cf4f841410e7b245b2c86d /source/blender/bmesh/intern | |
parent | 8b1b320c9fa6e27fd33746ada6da183ad2b88c9d (diff) |
BMesh: support connecting single-edge island links
Handle these cases by temporarily disconnecting the single links to ensure isolated islands,
then link back up after.
Diffstat (limited to 'source/blender/bmesh/intern')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon_edgenet.c | 296 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon_edgenet.h | 3 |
2 files changed, 285 insertions, 14 deletions
diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c index 420fb26ca08..85efffb82d3 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c @@ -606,6 +606,10 @@ bool BM_face_split_edgenet( * * \{ */ + +#define USE_PARTIAL_CONNECT + + #define VERT_IS_VALID BM_ELEM_INTERNAL_TAG /* can be X or Y */ @@ -685,8 +689,10 @@ static void bvhtree_test_edges_isect_2d_vert_cb( if (edge_isect_verts_point_2d(e, data->v_origin, data->v_other, co_isect)) { const float t = line_point_factor_v2(co_isect, data->v_origin->co, data->v_other->co); const float dist_new = data->dist_orig * t; - /* avoid float precision issues, possible this is greater */ - if (LIKELY(dist_new < hit->dist)) { + /* avoid float precision issues, possible this is greater, + * check anove zero to allow some overlap + * (and needed for partial-connect which will overlap vertices) */ + if (LIKELY((dist_new < hit->dist) && (dist_new > 0.0f))) { /* v1/v2 will both be in the same group */ if (v1_index < (int)data->vert_range[0] || v1_index >= (int)data->vert_range[1]) @@ -707,8 +713,10 @@ static void bvhtree_test_edges_isect_2d_ray_cb( /* direction is normalized, so this will be the distance */ float dist_new; if (isect_ray_seg_v2(data->v_origin->co, ray->direction, e->v1->co, e->v2->co, &dist_new, NULL)) { - /* avoid float precision issues, possible this is greater */ - if (LIKELY(dist_new < hit->dist)) { + /* avoid float precision issues, possible this is greater, + * check anove zero to allow some overlap + * (and needed for partial-connect which will overlap vertices) */ + if (LIKELY(dist_new < hit->dist && (dist_new > 0.0f))) { if (e->v1 != data->v_origin && e->v2 != data->v_origin) { const int v1_index = BM_elem_index_get(e->v1); /* v1/v2 will both be in the same group */ @@ -909,15 +917,188 @@ static int bm_face_split_edgenet_find_connection( return v_other ? BM_elem_index_get(v_other) : -1; } + +/** + * Support for connecting islands that have single-edge connections. + * This options is not very optimal (however its not needed for booleans either). + */ +#ifdef USE_PARTIAL_CONNECT + +/** + * Split vertices which are part of a partial connection + * (only a single vertex connecting an island). + * + * \note All edges and vertices must have their #BM_ELEM_INTERNAL_TAG flag enabled. + * This function leaves all the flags set as well. + * + */ +static BMVert *bm_face_split_edgenet_partial_connect(BMesh *bm, BMVert *v_delimit) +{ + /* -------------------------------------------------------------------- */ + /* Initial check that we may be a delimiting vert (keep this fast) */ + + /* initial check - see if we have 3+ flagged edges attached to 'v_delimit' + * if not, we can early exit */ + LinkNode *e_delimit_list = NULL; + unsigned int e_delimit_list_len = 0; + +#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG +#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG + +#define FOREACH_VERT_EDGE(v_, e_, body_) { \ + BMEdge *e_ = v_->e; \ + do { body_ } while ((e_ = BM_DISK_EDGE_NEXT(e_, v_)) != v_->e); \ +} ((void)0) + + /* start with face edges, since we need to split away wire-only edges */ + BMEdge *e_face_init = NULL; + + FOREACH_VERT_EDGE(v_delimit, e_iter, { + if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) { + BLI_assert(BM_elem_flag_test(BM_edge_other_vert(e_iter, v_delimit), VERT_NOT_IN_STACK)); + BLI_linklist_prepend_alloca(&e_delimit_list, e_iter); + e_delimit_list_len++; + if (e_iter->l != NULL) { + e_face_init = e_iter; + } + } + }); + + /* skip typical edge-chain verts */ + if (LIKELY(e_delimit_list_len <= 2)) { + return NULL; + } + + + /* -------------------------------------------------------------------- */ + /* Complicated stuff starts now! */ + + + /* Store connected vertices for restoring the flag */ + LinkNode *vert_stack = NULL; + BLI_linklist_prepend_alloca(&vert_stack, v_delimit); + BM_elem_flag_disable(v_delimit, VERT_NOT_IN_STACK); + + /* Walk the net... */ + { + BLI_SMALLSTACK_DECLARE(search, BMVert *); + BMVert *v_other = BM_edge_other_vert(e_face_init ? e_face_init : v_delimit->e, v_delimit); + + BLI_SMALLSTACK_PUSH(search, v_other); + BM_elem_flag_disable(v_other, VERT_NOT_IN_STACK); + + while ((v_other = BLI_SMALLSTACK_POP(search))) { + BLI_assert(BM_elem_flag_test(v_other, VERT_NOT_IN_STACK) == false); + BLI_linklist_prepend_alloca(&vert_stack, v_other); + BMEdge *e_iter = v_other->e; + do { + BMVert *v_step = BM_edge_other_vert(e_iter, v_other); + if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) { + if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK)) { + BM_elem_flag_disable(v_step, VERT_NOT_IN_STACK); + BLI_SMALLSTACK_PUSH(search, v_step); + } + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_other)) != v_other->e); + } + } + + /* Detect if this is a delimiter by checking if we didn't walk any of edges connected to 'v_delimit' */ + bool is_delimit = false; + FOREACH_VERT_EDGE(v_delimit, e_iter, { + BMVert *v_step = BM_edge_other_vert(e_iter, v_delimit); + if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK)) { + is_delimit = true; /* if one vertex is valid - we have a mix */ + } + else { + /* match the vertex flag (only for edges around 'v_delimit') */ + BM_elem_flag_disable(e_iter, EDGE_NOT_IN_STACK); + } + }); + +#undef FOREACH_VERT_EDGE + + /* Execute the split */ + BMVert *v_split = NULL; + if (is_delimit) { + v_split = BM_vert_create(bm, v_delimit->co, NULL, 0); + BM_vert_separate_wire_hflag(bm, v_split, v_delimit, EDGE_NOT_IN_STACK); + BM_elem_flag_enable(v_split, VERT_NOT_IN_STACK); + + BLI_assert(v_delimit->e != NULL); + BLI_assert(v_split->e != NULL); + } + + /* Restore flags */ + do { + BM_elem_flag_enable((BMVert *)vert_stack->link, VERT_NOT_IN_STACK); + } while ((vert_stack = vert_stack->next)); + + do { + BM_elem_flag_enable((BMEdge *)e_delimit_list->link, EDGE_NOT_IN_STACK); + } while ((e_delimit_list = e_delimit_list->next)); + +#undef EDGE_NOT_IN_STACK +#undef VERT_NOT_IN_STACK + + return v_split; +} + + +/** + * Check if creating a connection between 2 edges will later overlap when splicing vertices back together. + */ +static bool bm_vert_partial_connect_check_overlap( + BMVert **vert_arr, const int *remap, + const int v_a_index, const int v_b_index) +{ + int v_a_remap = remap[v_a_index]; + int v_b_remap = remap[v_b_index]; + + if (v_a_remap == -1 && v_b_remap == -1) { + return false; + } + else if (UNLIKELY((v_a_remap == v_b_index) || (v_b_remap == v_a_index))) { + /* connected to eachother */ + return true; + } + else { + /* check that creating an edge here will overlap an existing edge + * once adjacent vertices are spliced together. */ + const int v_pair[2] = {v_a_index, v_b_index}; + for (int i = 0; i < 2; i++) { + BMVert *v = vert_arr[v_pair[i]]; + BMEdge *e_iter = v->e; + do { + BMVert *v_step = BM_edge_other_vert(e_iter, v); + const int v_step_index = BM_elem_index_get(v_step); + if (remap[v_step_index] == v_pair[!i]) { + return true; + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != v->e); + } + } + + return false; +} + + +#endif /* USE_PARTIAL_CONNECT */ + + + /** * For when the edge-net has holes in it-this connects them. * + * \param use_partial_connect: Support for handling islands connected by only a single edge, + * \note that this is quite slow so avoid using where possible. * \param mem_arena: Avoids many small allocs & should be cleared after each use. * take care since \a r_edge_net_new is stored in \a r_edge_net_new. */ bool BM_face_split_edgenet_connect_islands( BMesh *bm, BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len, + bool use_partial_connect, MemArena *mem_arena, BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len) { @@ -959,6 +1140,48 @@ bool BM_face_split_edgenet_connect_islands( BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_STACK); } + + +#ifdef USE_PARTIAL_CONNECT + /* Split-out delimiting vertices */ + struct TempVertPair { + struct TempVertPair *next; + BMVert *v_temp; + BMVert *v_orig; + }; + + struct { + struct TempVertPair *list; + unsigned int len; + int *remap; /* temp -> orig mapping */ + } temp_vert_pairs = {NULL}; + + if (use_partial_connect) { + for (unsigned int i = 0; i < edge_net_init_len; i++) { + for (unsigned j = 0; j < 2; j++) { + BMVert *v_delimit = (&edge_arr[i]->v1)[j]; + BMVert *v_other; + + /* note, remapping will _never_ map a vertex to an already mapped vertex */ + while (UNLIKELY((v_other = bm_face_split_edgenet_partial_connect(bm, v_delimit)))) { + struct TempVertPair *tvp = BLI_memarena_alloc(mem_arena, sizeof(*tvp)); + tvp->next = temp_vert_pairs.list; + tvp->v_orig = v_delimit; + tvp->v_temp = v_other; + temp_vert_pairs.list = tvp; + temp_vert_pairs.len++; + } + } + } + + if (temp_vert_pairs.len == 0) { + use_partial_connect = false; + } + } +#endif /* USE_PARTIAL_CONNECT */ + + + unsigned int group_arr_len = 0; LinkNode *group_head = NULL; { @@ -1150,6 +1373,23 @@ bool BM_face_split_edgenet_connect_islands( } BLI_bvhtree_balance(bvhtree); + + +#ifdef USE_PARTIAL_CONNECT + if (use_partial_connect) { + /* needs to be done once the vertex indices have been written into */ + temp_vert_pairs.remap = BLI_memarena_alloc(mem_arena, sizeof(*temp_vert_pairs.remap) * vert_arr_len); + copy_vn_i(temp_vert_pairs.remap, vert_arr_len, -1); + + struct TempVertPair *tvp = temp_vert_pairs.list; + do { + temp_vert_pairs.remap[BM_elem_index_get(tvp->v_temp)] = BM_elem_index_get(tvp->v_orig); + } while ((tvp = tvp->next)); + } +#endif /* USE_PARTIAL_CONNECT */ + + + /* Create connections between groups */ /* may be an over-alloc, but not by much */ @@ -1195,11 +1435,19 @@ bool BM_face_split_edgenet_connect_islands( /* only for degenerate geometry */ if (index_other != -1) { - BMVert *v_end = vert_arr[index_other]; +#ifdef USE_PARTIAL_CONNECT + if ((use_partial_connect == false) || + (bm_vert_partial_connect_check_overlap( + vert_arr, temp_vert_pairs.remap, + BM_elem_index_get(v_origin), index_other) == false)) +#endif + { + BMVert *v_end = vert_arr[index_other]; - edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0); - edge_net_new_index++; - args.edge_arr_new_len++; + edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0); + edge_net_new_index++; + args.edge_arr_new_len++; + } } } @@ -1211,11 +1459,18 @@ bool BM_face_split_edgenet_connect_islands( /* only for degenerate geometry */ if (index_other != -1) { - BMVert *v_end = vert_arr[index_other]; - - edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0); - edge_net_new_index++; - args.edge_arr_new_len++; +#ifdef USE_PARTIAL_CONNECT + if ((use_partial_connect == false) || + (bm_vert_partial_connect_check_overlap( + vert_arr, temp_vert_pairs.remap, + BM_elem_index_get(v_origin), index_other) == false)) +#endif + { + BMVert *v_end = vert_arr[index_other]; + edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0); + edge_net_new_index++; + args.edge_arr_new_len++; + } /* tell the 'next' group it doesn't need to create its own back-link */ unsigned int g_index_other = verts_group_table[index_other]; @@ -1239,6 +1494,21 @@ bool BM_face_split_edgenet_connect_islands( } finally: + +#ifdef USE_PARTIAL_CONNECT + /* don't free 'vert_temp_pair_list', its part of the arena */ + if (use_partial_connect) { + struct TempVertPair *tvp = temp_vert_pairs.list; + do { + /* we must _never_ create connections here + * (inface the islands can't have a connection at all) */ + BLI_assert(BM_edge_exists(tvp->v_orig, tvp->v_temp) == NULL); + BM_vert_splice(bm, tvp->v_orig, tvp->v_temp); + } while ((tvp = tvp->next)); + } +#endif + + for (unsigned int i = 0; i < edge_arr_len; i++) { BM_elem_flag_disable(edge_arr[i], EDGE_NOT_IN_STACK); BM_elem_flag_disable(edge_arr[i]->v1, VERT_NOT_IN_STACK); diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.h b/source/blender/bmesh/intern/bmesh_polygon_edgenet.h index b6642319fe6..72ae7695f0f 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.h +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.h @@ -33,8 +33,9 @@ bool BM_face_split_edgenet( bool BM_face_split_edgenet_connect_islands( BMesh *bm, BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len, + bool use_partial_connect, struct MemArena *arena, BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len) -ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5, 6, 7); +ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 6, 7, 8); #endif /* __BMESH_POLYGON_EDGENET_H__ */ |