From 5c82c9bae42c2fb3bf191e0100b88ec52930b1bd Mon Sep 17 00:00:00 2001 From: mano-wii Date: Mon, 27 Jan 2020 08:37:48 -0300 Subject: Edit Mesh: Auto Merge - Split Edges & Faces - Better logic for splitting faces Differential Revision: https://developer.blender.org/D6626 --- source/blender/bmesh/tools/bmesh_intersect_edges.c | 313 ++++++++++++++------- source/blender/bmesh/tools/bmesh_intersect_edges.h | 6 +- 2 files changed, 214 insertions(+), 105 deletions(-) (limited to 'source/blender/bmesh') diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c index c3687c5d477..b25dc82aac9 100644 --- a/source/blender/bmesh/tools/bmesh_intersect_edges.c +++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c @@ -57,7 +57,7 @@ struct EDBMSplitBestFaceData { * Track the range of vertices in edgenet along the faces normal, * find the lowest since it's most likely to be most co-planar with the face. */ - float best_face_range_on_normal_axis; + float best_edgenet_range_on_face_normal; BMFace *r_best_face; }; @@ -76,11 +76,14 @@ static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f, SWAP(float, min, max); } - BMVert *v_test = l_b->v; BMEdge **e_iter = &data->edgenet[0]; + BMEdge *e_next = data->edgenet[1]; + BMVert *v_test = ELEM((*e_iter)->v1, e_next->v1, e_next->v2) ? (*e_iter)->v2 : (*e_iter)->v1; + int verts_len = data->edgenet_len - 1; for (int i = verts_len; i--; e_iter++) { v_test = BM_edge_other_vert(*e_iter, v_test); + BLI_assert(v_test != NULL); if (!BM_face_point_inside_test(f, v_test->co)) { return false; } @@ -93,9 +96,9 @@ static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f, } } - const float test_face_range_on_normal_axis = max - min; - if (test_face_range_on_normal_axis < data->best_face_range_on_normal_axis) { - data->best_face_range_on_normal_axis = test_face_range_on_normal_axis; + const float test_edgenet_range_on_face_normal = max - min; + if (test_edgenet_range_on_face_normal < data->best_edgenet_range_on_face_normal) { + data->best_edgenet_range_on_face_normal = test_edgenet_range_on_face_normal; data->r_best_face = f; } @@ -111,114 +114,79 @@ static bool bm_vert_pair_share_splittable_face_cb(BMFace *UNUSED(f), float(*data)[3] = userdata; float *v_a_co = data[0]; float *v_a_b_dir = data[1]; - - float lambda; - if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_a->prev->v->co, l_a->next->v->co, &lambda)) { - if (IN_RANGE(lambda, 0.0f, 1.0f)) { + const float range_min = -FLT_EPSILON; + const float range_max = 1.0f + FLT_EPSILON; + + float co[3]; + float dir[3]; + float lambda_a; + float lambda_b; + + copy_v3_v3(co, l_a->prev->v->co); + sub_v3_v3v3(dir, l_a->next->v->co, co); + if (isect_ray_ray_v3(v_a_co, v_a_b_dir, co, dir, &lambda_a, &lambda_b)) { + if (IN_RANGE(lambda_a, range_min, range_max) && IN_RANGE(lambda_b, range_min, range_max)) { return true; } - else if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_b->prev->v->co, l_b->next->v->co, &lambda)) { - return IN_RANGE(lambda, 0.0f, 1.0f); + else { + copy_v3_v3(co, l_b->prev->v->co); + sub_v3_v3v3(dir, l_b->next->v->co, co); + if (isect_ray_ray_v3(v_a_co, v_a_b_dir, co, dir, &lambda_a, &lambda_b)) { + return IN_RANGE(lambda_a, range_min, range_max) && + IN_RANGE(lambda_b, range_min, range_max); + } } } return false; } -void BM_vert_weld_linked_wire_edges_into_linked_faces( - BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len) +static BMFace *bm_vert_pair_best_face_get( + BMVert *v_a, BMVert *v_b, BMEdge **edgenet, const int edgenet_len, const float epsilon) { - BMEdge **edgenet = *r_edgenet; - int edgenet_alloc_len = *r_edgenet_alloc_len; - - BMIter iter; - BMEdge *e; - BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { - int edgenet_len = 0; - BMVert *v_other = v; - while (BM_edge_is_wire(e)) { - if (edgenet_alloc_len == edgenet_len) { - edgenet_alloc_len = (edgenet_alloc_len + 1) * 2; - edgenet = MEM_reallocN(edgenet, (edgenet_alloc_len) * sizeof(*edgenet)); - } - edgenet[edgenet_len++] = e; - v_other = BM_edge_other_vert(e, v_other); - if (v_other == v) { - /* Endless loop. */ - break; - } - - BMEdge *e_next = BM_DISK_EDGE_NEXT(e, v_other); - if (e_next == e) { - /* Vert is wire_endpoint. */ - edgenet_len = 0; - break; - } - - BMEdge *e_test = e_next; - while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != e) { - if (e_test->l) { - /* Vert is linked to a face. */ - goto l_break; - } - } - - e = e_next; - } - - BMLoop *dummy; - BMFace *best_face; + BMFace *r_best_face = NULL; - l_break: - if (edgenet_len == 0) { - /* Nothing to do. */ - continue; - } - if (edgenet_len == 1) { - float data[2][3]; - copy_v3_v3(data[0], v_other->co); - sub_v3_v3v3(data[1], v->co, data[0]); - best_face = BM_vert_pair_shared_face_cb( - v_other, v, true, bm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy); - } - else { - struct EDBMSplitBestFaceData data = { - .edgenet = edgenet, - .edgenet_len = edgenet_len, - .best_face_range_on_normal_axis = FLT_MAX, - .r_best_face = NULL, - }; - BM_vert_pair_shared_face_cb( - v_other, v, true, bm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy); - - if (data.r_best_face) { - float no[3], min = FLT_MAX, max = -FLT_MAX; - copy_v3_v3(no, data.r_best_face->no); - BMVert *v_test; - BMIter f_iter; - BM_ITER_ELEM (v_test, &f_iter, data.r_best_face, BM_VERTS_OF_FACE) { - float dot = dot_v3v3(v_test->co, no); - if (dot < min) { - min = dot; - } - if (dot > max) { - max = dot; - } + BMLoop *dummy; + if (edgenet_len == 1) { + float data[2][3]; + copy_v3_v3(data[0], v_b->co); + sub_v3_v3v3(data[1], v_a->co, data[0]); + r_best_face = BM_vert_pair_shared_face_cb( + v_a, v_b, false, bm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy); + } + else { + struct EDBMSplitBestFaceData data = { + .edgenet = edgenet, + .edgenet_len = edgenet_len, + .best_edgenet_range_on_face_normal = FLT_MAX, + .r_best_face = NULL, + }; + BM_vert_pair_shared_face_cb( + v_a, v_b, true, bm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy); + + if (data.r_best_face) { + /* Check if the edgenet's range is smaller than the face's range. */ + float no[3], min = FLT_MAX, max = -FLT_MAX; + copy_v3_v3(no, data.r_best_face->no); + BMVert *v_test; + BMIter f_iter; + BM_ITER_ELEM (v_test, &f_iter, data.r_best_face, BM_VERTS_OF_FACE) { + float dot = dot_v3v3(v_test->co, no); + if (dot < min) { + min = dot; } - float range = max - min + 2 * epsilon; - if (range < data.best_face_range_on_normal_axis) { - data.r_best_face = NULL; + if (dot > max) { + max = dot; } } - best_face = data.r_best_face; - } - - if (best_face) { - BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, NULL, NULL); + float face_range_on_normal = max - min + 2 * epsilon; + if (face_range_on_normal < data.best_edgenet_range_on_face_normal) { + data.r_best_face = NULL; + } } + r_best_face = data.r_best_face; } - *r_edgenet = edgenet; - *r_edgenet_alloc_len = edgenet_alloc_len; + return r_best_face; } /** \} */ @@ -517,7 +485,8 @@ static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, voi #define INTERSECT_EDGES -bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap) +bool BM_mesh_intersect_edges( + BMesh *bm, const char hflag, const float dist, const bool split_faces, GHash *r_targetmap) { bool ok = false; @@ -560,6 +529,9 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas verts_remain_len++; } } + + /* The index will indicate which cut in pair_array this vertex belongs to. */ + BM_elem_index_set(v, -1); } bm->elem_index_dirty |= BM_VERT; @@ -621,6 +593,10 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas /* Don't test hidden edges or smaller than the minimum distance. * These have already been handled in the vertices overlap. */ BM_elem_index_set(e, 0); + if (split_faces) { + /* Tag to be ignored. */ + BM_elem_flag_enable(e, BM_ELEM_TAG); + } continue; } @@ -631,6 +607,10 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas else { BM_elem_index_set(e, EDGE_REMAIN_TO_TEST); edges_remain_len++; + if (split_faces) { + /* Tag to be ignored. */ + BM_elem_flag_enable(e, BM_ELEM_TAG); + } } } @@ -823,6 +803,11 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas lambda = (pair_elem->lambda - lambda_prev) / (1.0f - lambda_prev); lambda_prev = pair_elem->lambda; e = pair_elem->edge; + if (split_faces) { + /* Tagged edges are ignored when split faces. + /* Untag these. */ + BM_elem_flag_disable(e, BM_ELEM_TAG); + } BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda); pair_elem->vert = v_new; @@ -856,10 +841,136 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT); BLI_assert((*pair_iter)[1].elem->head.htype == BM_VERT); BLI_assert((*pair_iter)[0].elem != (*pair_iter)[1].elem); - - BLI_ghash_insert(r_targetmap, (*pair_iter)[0].vert, (*pair_iter)[1].vert); + BMVert *v_key, *v_val; + v_key = (*pair_iter)[0].vert; + v_val = (*pair_iter)[1].vert; + BLI_ghash_insert(r_targetmap, v_key, v_val); + if (split_faces) { + BM_elem_index_set(v_key, i * 2); + BM_elem_index_set(v_val, i * 2 + 1); + } } + if (split_faces) { + BMEdge **edgenet = NULL; + int edgenet_alloc_len = 0; + + struct EDBMSplitElem *pair_flat = (struct EDBMSplitElem *)&pair_array[0]; + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + continue; + } + BM_elem_flag_enable(e, BM_ELEM_TAG); + + BMVert *va, *vb, *va_dest = NULL; + va = e->v1; + vb = e->v2; + + int v_cut = BM_elem_index_get(va); + int v_cut_other = BM_elem_index_get(vb); + if (v_cut == -1 && v_cut_other == -1) { + continue; + } + + if (v_cut == -1) { + SWAP(BMVert *, va, vb); + v_cut = v_cut_other; + v_cut_other = -1; + } + + v_cut += v_cut % 2 ? -1 : 1; + va_dest = pair_flat[v_cut].vert; + + BMFace *best_face = NULL; + int edgenet_len = 0; + BMVert *v_other_dest, *v_other = vb; + BMEdge *e_net = e; + while (true) { + if (edgenet_alloc_len == edgenet_len) { + edgenet_alloc_len = (edgenet_alloc_len + 1) * 2; + edgenet = MEM_reallocN(edgenet, (edgenet_alloc_len) * sizeof(*edgenet)); + } + edgenet[edgenet_len++] = e_net; + + if (v_cut_other != -1) { + v_cut_other += v_cut_other % 2 ? -1 : 1; + v_other_dest = pair_flat[v_cut_other].vert; + } + else { + v_other_dest = v_other; + } + + best_face = bm_vert_pair_best_face_get( + va_dest, v_other_dest, edgenet, edgenet_len, dist); + + if (best_face) { + if (va_dest != va) { + e_net = edgenet[0]; + if (edgenet_len > 1) { + vb = BM_edge_other_vert(e_net, va); + } + else { + vb = v_other_dest; + } + edgenet[0] = BM_edge_create(bm, va_dest, vb, e_net, BM_CREATE_NOP); + } + if ((edgenet_len > 1) && (v_other_dest != v_other)) { + e_net = edgenet[edgenet_len - 1]; + edgenet[edgenet_len - 1] = BM_edge_create( + bm, v_other_dest, BM_edge_other_vert(e_net, v_other), e_net, BM_CREATE_NOP); + } + break; + } + + BMEdge *e_test = e_net, *e_next = NULL; + while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != (e_net)) { + if (!BM_edge_is_wire(e_test)) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + continue; + } + if (BM_elem_index_get(e_test->v1) == -1 && BM_elem_index_get(e_test->v2) == -1) { + continue; + } + } + else if (!BM_edge_is_wire(e_net)) { + continue; + } + e_next = e_test; + break; + } + + if (e_next == NULL) { + break; + } + + e_net = e_next; + v_other = BM_edge_other_vert(e_net, v_other); + if (v_other == va) { + /* Endless loop. */ + break; + } + v_cut_other = BM_elem_index_get(v_other); + } + + if (best_face) { + BMFace **face_arr = NULL; + int face_arr_len = 0; + BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, &face_arr, &face_arr_len); + if (face_arr) { + /* Update the new faces normal. + * Normal is necessary to obtain the best face for edgenet */ + while (face_arr_len--) { + BM_face_normal_update(face_arr[face_arr_len]); + } + MEM_freeN(face_arr); + } + } + } + + if (edgenet) { + MEM_freeN(edgenet); + } + } ok = true; } } diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.h b/source/blender/bmesh/tools/bmesh_intersect_edges.h index a22a1ca1e1d..7e2252250d6 100644 --- a/source/blender/bmesh/tools/bmesh_intersect_edges.h +++ b/source/blender/bmesh/tools/bmesh_intersect_edges.h @@ -21,9 +21,7 @@ #ifndef __BMESH_INTERSECT_EDGES_H__ #define __BMESH_INTERSECT_EDGES_H__ -void BM_vert_weld_linked_wire_edges_into_linked_faces( - BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len); - -bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap); +bool BM_mesh_intersect_edges( + BMesh *bm, const char hflag, const float dist, const bool split_faces, GHash *r_targetmap); #endif /* __BMESH_INTERSECT_EDGES_H__ */ -- cgit v1.2.3