From 6b189d2bcf3536231f7040926ed34fe01012f14e Mon Sep 17 00:00:00 2001 From: mano-wii Date: Mon, 26 Aug 2019 14:15:25 -0300 Subject: Edit Mesh: New option "Split Edges & Faces" to "AutoMerge" Ref T66423 Differential revision: https://developer.blender.org/D5562 --- source/blender/blenlib/BLI_kdopbvh.h | 6 + source/blender/blenlib/intern/BLI_kdopbvh.c | 89 ++++++ source/blender/bmesh/intern/bmesh_query.c | 28 ++ source/blender/bmesh/intern/bmesh_query.h | 7 + source/blender/editors/include/ED_mesh.h | 2 + source/blender/editors/mesh/editmesh_select.c | 310 +++++++++++++++++++++ .../editors/transform/transform_conversions.c | 9 +- source/blender/makesdna/DNA_scene_types.h | 6 + source/blender/makesrna/intern/rna_scene.c | 10 +- 9 files changed, 464 insertions(+), 3 deletions(-) (limited to 'source') diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index a348694c4da..abfd561200c 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -177,6 +177,12 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, BVHTree_NearestPointCallback callback, void *userdata); +int BLI_bvhtree_find_nearest_first(BVHTree *tree, + const float co[3], + const float dist_sq, + BVHTree_NearestPointCallback callback, + void *userdata); + int BLI_bvhtree_ray_cast_ex(BVHTree *tree, const float co[3], const float dir[3], diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 0e93fd8e13b..ed3c7096865 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -1466,6 +1466,95 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, /** \} */ +/* -------------------------------------------------------------------- */ +/** \name BLI_bvhtree_find_nearest_first + * \{ */ + +static bool isect_aabb_v3(BVHNode *node, const float co[3]) +{ + const BVHTreeAxisRange *bv = (const BVHTreeAxisRange *)node->bv; + + if (co[0] > bv[0].min && co[0] < bv[0].max && co[1] > bv[1].min && co[1] < bv[1].max && + co[2] > bv[2].min && co[2] < bv[2].max) { + return true; + } + + return false; +} + +static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node) +{ + if (node->totnode == 0) { + if (isect_aabb_v3(node, data->co)) { + if (data->callback) { + const float dist_sq = data->nearest.dist_sq; + data->callback(data->userdata, node->index, data->co, &data->nearest); + return (data->nearest.dist_sq < dist_sq); + } + else { + data->nearest.index = node->index; + return true; + } + } + } + else { + /* Better heuristic to pick the closest node to dive on */ + int i; + + if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) { + for (i = 0; i != node->totnode; i++) { + if (isect_aabb_v3(node->children[i], data->co)) { + if (dfs_find_duplicate_fast_dfs(data, node->children[i])) { + return true; + } + } + } + } + else { + for (i = node->totnode; i--;) { + if (isect_aabb_v3(node->children[i], data->co)) { + if (dfs_find_duplicate_fast_dfs(data, node->children[i])) { + return true; + } + } + } + } + } + return false; +} + +/** + * Find the first node nearby. + * Favors speed over quality since it doesn't find the best target node. + */ +int BLI_bvhtree_find_nearest_first(BVHTree *tree, + const float co[3], + const float dist_sq, + BVHTree_NearestPointCallback callback, + void *userdata) +{ + BVHNearestData data; + BVHNode *root = tree->nodes[tree->totleaf]; + + /* init data to search */ + data.tree = tree; + data.co = co; + + data.callback = callback; + data.userdata = userdata; + data.nearest.index = -1; + data.nearest.dist_sq = dist_sq; + + /* dfs search */ + if (root) { + dfs_find_duplicate_fast_dfs(&data, root); + } + + return data.nearest.index; +} + +/** \} */ + /* -------------------------------------------------------------------- */ /** \name BLI_bvhtree_ray_cast * diff --git a/source/blender/bmesh/intern/bmesh_query.c b/source/blender/bmesh/intern/bmesh_query.c index 51bc86e40eb..219bec15e5b 100644 --- a/source/blender/bmesh/intern/bmesh_query.c +++ b/source/blender/bmesh/intern/bmesh_query.c @@ -207,6 +207,34 @@ bool BM_vert_pair_share_face_check_cb(BMVert *v_a, return false; } +BMFace *BM_vert_pair_shared_face_cb(BMVert *v_a, + BMVert *v_b, + const bool allow_adjacent, + bool (*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata), + void *user_data, + BMLoop **r_l_a, + BMLoop **r_l_b) +{ + if (v_a->e && v_b->e) { + BMIter iter; + BMLoop *l_a, *l_b; + + BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) { + BMFace *f = l_a->f; + l_b = BM_face_vert_share_loop(f, v_b); + if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b)) && + callback(f, l_a, l_b, user_data)) { + *r_l_a = l_a; + *r_l_b = l_b; + + return f; + } + } + } + + return NULL; +} + /** * Given 2 verts, find the smallest face they share and give back both loops. */ diff --git a/source/blender/bmesh/intern/bmesh_query.h b/source/blender/bmesh/intern/bmesh_query.h index e96984490c0..3a864fbb5dd 100644 --- a/source/blender/bmesh/intern/bmesh_query.h +++ b/source/blender/bmesh/intern/bmesh_query.h @@ -62,6 +62,13 @@ bool BM_vert_pair_share_face_check_cb(BMVert *v_a, bool (*test_fn)(BMFace *f, void *user_data), void *user_data) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); +BMFace *BM_vert_pair_shared_face_cb(BMVert *v_a, + BMVert *v_b, + const bool allow_adjacent, + bool (*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata), + void *user_data, + BMLoop **r_l_a, + BMLoop **r_l_b) ATTR_NONNULL(1, 2, 4, 6, 7); BMFace *BM_vert_pair_share_face_by_len(BMVert *v_a, BMVert *v_b, BMLoop **r_l_a, diff --git a/source/blender/editors/include/ED_mesh.h b/source/blender/editors/include/ED_mesh.h index 0b2adfed531..30d4aa10c1b 100644 --- a/source/blender/editors/include/ED_mesh.h +++ b/source/blender/editors/include/ED_mesh.h @@ -145,6 +145,8 @@ void ED_mesh_undosys_type(struct UndoType *ut); void EDBM_select_mirrored( struct BMEditMesh *em, const int axis, const bool extend, int *r_totmirr, int *r_totfail); void EDBM_automerge(struct Scene *scene, struct Object *ob, bool update, const char hflag); +void EDBM_automerge_and_split( + struct Scene *scene, struct Object *ob, bool split_edges, bool update, const char hflag); struct BMVert *EDBM_vert_find_nearest_ex(struct ViewContext *vc, float *r_dist, diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c index 94ffd9a34d6..e60934734bc 100644 --- a/source/blender/editors/mesh/editmesh_select.c +++ b/source/blender/editors/mesh/editmesh_select.c @@ -31,8 +31,10 @@ #include "BLI_math.h" #include "BLI_math_bits.h" #include "BLI_rand.h" +#include "BLI_sort.h" #include "BLI_array.h" +#include "BKE_bvhutils.h" #include "BKE_context.h" #include "BKE_report.h" #include "BKE_paint.h" @@ -193,6 +195,314 @@ void EDBM_automerge(Scene *scene, Object *obedit, bool update, const char hflag) } } +struct EDBMSplitEdge { + BMVert *v; + BMEdge *e; + float lambda; +}; + +struct EDBMSplitEdgeData { + BMesh *bm; + + BMEdge *r_edge; + float r_lambda; +}; + +static bool edbm_automerge_and_split_check_best_face_cb(BMFace *UNUSED(f), + BMLoop *l_a, + BMLoop *l_b, + void *userdata) +{ + 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)) { + 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); + } + } + } + + return false; +} + +static bool edbm_automerge_check_and_split_faces(BMesh *bm, BMVert *v_src, BMVert *v_dst) +{ + BMIter iter; + BMEdge *e_iter; + BM_ITER_ELEM (e_iter, &iter, v_src, BM_EDGES_OF_VERT) { + BMVert *vert_other = BM_edge_other_vert(e_iter, v_src); + if (vert_other != v_dst) { + float data[2][3]; + copy_v3_v3(data[0], vert_other->co); + sub_v3_v3v3(data[1], v_dst->co, data[0]); + + BMLoop *l_a, *l_b; + BMFace *f = BM_vert_pair_shared_face_cb( + vert_other, v_dst, false, edbm_automerge_and_split_check_best_face_cb, data, &l_a, &l_b); + + if (f) { + BM_face_split(bm, f, l_a, l_b, NULL, NULL, true); + return true; + } + } + } + return false; +} + +static void ebbm_automerge_and_split_find_duplicate_cb(void *userdata, + int index, + const float co[3], + BVHTreeNearest *nearest) +{ + struct EDBMSplitEdgeData *data = userdata; + BMEdge *e = BM_edge_at_index(data->bm, index); + float lambda = line_point_factor_v3_ex(co, e->v1->co, e->v2->co, 0.0f, -1.0f); + if (IN_RANGE(lambda, 0.0f, 1.0f)) { + float near_co[3]; + interp_v3_v3v3(near_co, e->v1->co, e->v2->co, lambda); + float dist_sq = len_squared_v3v3(near_co, co); + if (dist_sq < nearest->dist_sq) { + nearest->dist_sq = dist_sq; + nearest->index = index; + + data->r_edge = e; + data->r_lambda = lambda; + } + } +} + +static int edbm_automerge_and_split_sort_cmp_by_keys_cb(const void *index1_v, + const void *index2_v, + void *keys_v) +{ + const struct EDBMSplitEdge *cuts = keys_v; + const int *index1 = (int *)index1_v; + const int *index2 = (int *)index2_v; + + if (cuts[*index1].lambda > cuts[*index2].lambda) { + return 1; + } + else { + return -1; + } +} + +void EDBM_automerge_and_split( + Scene *scene, Object *obedit, bool split_edges, bool update, const char hflag) +{ + bool ok = false; + + BMEditMesh *em = BKE_editmesh_from_object(obedit); + BMesh *bm = em->bm; + float dist = scene->toolsettings->doublimit; + BMOperator findop, weldop; + BMOpSlot *slot_targetmap; + BMIter iter; + BMVert *v; + + /* tag and count the verts to be tested. */ + BM_mesh_elem_toolflags_ensure(bm); + int verts_len = 0; + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_flag_test(v, hflag)) { + BM_elem_flag_enable(v, BM_ELEM_TAG); + BMO_vert_flag_enable(bm, v, BMO_ELE_TAG); + verts_len++; + } + else { + BM_elem_flag_disable(v, BM_ELEM_TAG); + } + } + + /* Search for doubles among all vertices, but only merge non-BMO_ELE_TAG + * vertices into BMO_ELE_TAG vertices. */ + BMO_op_initf(bm, &findop, 0, "find_doubles verts=%av keep_verts=%Fv dist=%f", BMO_ELE_TAG, dist); + BMO_op_exec(bm, &findop); + + /* Init weld_verts operator to later fill the targetmap. */ + BMO_op_init(bm, &weldop, 0, "weld_verts"); + BMO_slot_copy(&findop, slots_out, "targetmap.out", &weldop, slots_in, "targetmap"); + + slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap"); + + /* Remove duplicate vertices from the split edge test and check and split faces. */ + GHashIterator gh_iter; + GHash *ghash_targetmap = BMO_SLOT_AS_GHASH(slot_targetmap); + GHASH_ITER (gh_iter, ghash_targetmap) { + v = BLI_ghashIterator_getKey(&gh_iter); + BMVert *v_dst = BLI_ghashIterator_getValue(&gh_iter); + if (!BM_elem_flag_test(v, BM_ELEM_TAG)) { + /* Should this happen? */ + SWAP(BMVert *, v, v_dst); + } + BLI_assert(BM_elem_flag_test(v, BM_ELEM_TAG)); + BM_elem_flag_disable(v, BM_ELEM_TAG); + + edbm_automerge_check_and_split_faces(bm, v, v_dst); + + ok = true; + verts_len--; + } + + int totedge = bm->totedge; + if (totedge == 0 || verts_len == 0) { + split_edges = false; + } + + if (split_edges) { + /* Count and tag edges. */ + BMEdge *e; + int edges_len = 0; + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN) && !BM_elem_flag_test(e->v1, BM_ELEM_TAG) && + !BM_elem_flag_test(e->v2, BM_ELEM_TAG)) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + edges_len++; + } + else { + BM_elem_flag_disable(e, BM_ELEM_TAG); + } + } + + if (edges_len) { + /* Create a BVHTree of edges with `dist` as epsilon. */ + BVHTree *tree_edges = BLI_bvhtree_new(edges_len, dist, 2, 6); + int i; + BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + float co[2][3]; + copy_v3_v3(co[0], e->v1->co); + copy_v3_v3(co[1], e->v2->co); + + BLI_bvhtree_insert(tree_edges, i, co[0], 2); + + /* Use `e->head.index` to count intersections. */ + e->head.index = 0; + } + } + BLI_bvhtree_balance(tree_edges); + + struct EDBMSplitEdge *cuts_iter, *cuts; + + /* Store all intersections in this array. */ + cuts = MEM_mallocN(verts_len * sizeof(*cuts), __func__); + cuts_iter = &cuts[0]; + + int cuts_len = 0; + int cut_edges_len = 0; + float dist_sq = SQUARE(dist); + struct EDBMSplitEdgeData data = {bm}; + + /* Start the search for intersections. */ + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_flag_test(v, BM_ELEM_TAG)) { + float co[3]; + copy_v3_v3(co, v->co); + int e_index = BLI_bvhtree_find_nearest_first( + tree_edges, co, dist_sq, ebbm_automerge_and_split_find_duplicate_cb, &data); + + if (e_index != -1) { + e = data.r_edge; + e->head.index++; + + cuts_iter->v = v; + cuts_iter->e = e; + cuts_iter->lambda = data.r_lambda; + cuts_iter++; + cuts_len++; + + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BM_elem_flag_disable(e, BM_ELEM_TAG); + cut_edges_len++; + } + } + } + } + BLI_bvhtree_free(tree_edges); + + if (cuts_len) { + /* Map intersections per edge. */ + union { + struct { + int cuts_len; + int cuts_index[]; + }; + int as_int[0]; + } * e_map_iter, *e_map; + + e_map = MEM_mallocN((cut_edges_len * sizeof(*e_map)) + + (cuts_len * sizeof(*(e_map->cuts_index))), + __func__); + + int map_len = 0; + cuts_iter = &cuts[0]; + for (i = 0; i < cuts_len; i++, cuts_iter++) { + e = cuts_iter->e; + if (!BM_elem_flag_test(e, BM_ELEM_TAG)) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + int e_cuts_len = e->head.index; + + e_map_iter = (void *)&e_map->as_int[map_len]; + e_map_iter->cuts_len = e_cuts_len; + e_map_iter->cuts_index[0] = i; + + /* Use `e->head.index` to indicate which slot to fill with the `cuts` index. */ + e->head.index = map_len + 1; + map_len += 1 + e_cuts_len; + } + else { + e_map->as_int[++e->head.index] = i; + } + } + + /* Split Edges and Faces. */ + for (i = 0; i < map_len; + e_map_iter = (void *)&e_map->as_int[i], i += 1 + e_map_iter->cuts_len) { + + /* sort by lambda! */ + BLI_qsort_r(e_map_iter->cuts_index, + e_map_iter->cuts_len, + sizeof(*(e_map->cuts_index)), + edbm_automerge_and_split_sort_cmp_by_keys_cb, + cuts); + + float lambda, lambda_prev = 0.0f; + for (int j = 0; j < e_map_iter->cuts_len; j++) { + cuts_iter = &cuts[e_map_iter->cuts_index[j]]; + lambda = (cuts_iter->lambda - lambda_prev) / (1.0f - lambda_prev); + lambda_prev = cuts_iter->lambda; + v = cuts_iter->v; + e = cuts_iter->e; + + BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda); + + edbm_automerge_check_and_split_faces(bm, v, v_new); + BMO_slot_map_elem_insert(&weldop, slot_targetmap, v_new, v); + } + } + + ok = true; + MEM_freeN(e_map); + } + + MEM_freeN(cuts); + } + } + + BMO_op_exec(bm, &weldop); + + BMO_op_finish(bm, &findop); + BMO_op_finish(bm, &weldop); + + if (LIKELY(ok) && update) { + EDBM_update_generic(em, true, true); + } +} + /** \} */ /* -------------------------------------------------------------------- */ diff --git a/source/blender/editors/transform/transform_conversions.c b/source/blender/editors/transform/transform_conversions.c index a6514526166..94a19514a86 100644 --- a/source/blender/editors/transform/transform_conversions.c +++ b/source/blender/editors/transform/transform_conversions.c @@ -7126,7 +7126,14 @@ static void special_aftertrans_update__mesh(bContext *UNUSED(C), TransInfo *t) hflag = BM_ELEM_SELECT; } - EDBM_automerge(t->scene, tc->obedit, true, hflag); + if (t->scene->toolsettings->automerge & AUTO_MERGE) { + if (t->scene->toolsettings->automerge & AUTO_MERGE_AND_SPLIT) { + EDBM_automerge_and_split(t->scene, tc->obedit, true, true, hflag); + } + else { + EDBM_automerge(t->scene, tc->obedit, true, hflag); + } + } /* Special case, this is needed or faces won't re-select. * Flush selected edges to faces. */ diff --git a/source/blender/makesdna/DNA_scene_types.h b/source/blender/makesdna/DNA_scene_types.h index 412bf358a44..617656d1b2c 100644 --- a/source/blender/makesdna/DNA_scene_types.h +++ b/source/blender/makesdna/DNA_scene_types.h @@ -1366,6 +1366,12 @@ typedef struct MeshStatVis { /* *************************************************************** */ /* Tool Settings */ +/* CurvePaintSettings.surface_plane */ +enum { + AUTO_MERGE = 1 << 0, + AUTO_MERGE_AND_SPLIT = 1 << 1, +}; + typedef struct ToolSettings { /** Vertex paint. */ VPaint *vpaint; diff --git a/source/blender/makesrna/intern/rna_scene.c b/source/blender/makesrna/intern/rna_scene.c index 939572923ac..67c82484864 100644 --- a/source/blender/makesrna/intern/rna_scene.c +++ b/source/blender/makesrna/intern/rna_scene.c @@ -2944,9 +2944,15 @@ static void rna_def_tool_settings(BlenderRNA *brna) RNA_def_property_update(prop, NC_SPACE | ND_SPACE_VIEW3D, NULL); prop = RNA_def_property(srna, "use_mesh_automerge", PROP_BOOLEAN, PROP_NONE); - RNA_def_property_boolean_sdna(prop, NULL, "automerge", 0); + RNA_def_property_boolean_sdna(prop, NULL, "automerge", AUTO_MERGE); RNA_def_property_ui_text( - prop, "Auto Merge", "Automatically merge vertices moved to the same location"); + prop, "Auto Merge Vertices", "Automatically merge vertices moved to the same location"); + RNA_def_property_ui_icon(prop, ICON_AUTOMERGE_OFF, 1); + RNA_def_property_update(prop, NC_SCENE | ND_TOOLSETTINGS, NULL); /* header redraw */ + + prop = RNA_def_property(srna, "use_mesh_automerge_and_split", PROP_BOOLEAN, PROP_NONE); + RNA_def_property_boolean_sdna(prop, NULL, "automerge", AUTO_MERGE_AND_SPLIT); + RNA_def_property_ui_text(prop, "Split Edges & Faces", "Automatically split edges and faces"); RNA_def_property_ui_icon(prop, ICON_AUTOMERGE_OFF, 1); RNA_def_property_update(prop, NC_SCENE | ND_TOOLSETTINGS, NULL); /* header redraw */ -- cgit v1.2.3