Commit: 5c82c9bae42c2fb3bf191e0100b88ec52930b1bd Author: mano-wii Date: Mon Jan 27 08:37:48 2020 -0300 Branches: master https://developer.blender.org/rB5c82c9bae42c2fb3bf191e0100b88ec52930b1bd
Edit Mesh: Auto Merge - Split Edges & Faces - Better logic for splitting faces Differential Revision: https://developer.blender.org/D6626 =================================================================== M source/blender/bmesh/tools/bmesh_intersect_edges.c M source/blender/bmesh/tools/bmesh_intersect_edges.h M source/blender/editors/mesh/editmesh_automerge.c =================================================================== 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) @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org https://lists.blender.org/mailman/listinfo/bf-blender-cvs