diff options
| -rw-r--r-- | source/blender/editors/include/ED_mesh.h | 14 | ||||
| -rw-r--r-- | source/blender/editors/mesh/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | source/blender/editors/mesh/editmesh_automerge.c | 496 | ||||
| -rw-r--r-- | source/blender/editors/mesh/editmesh_select.c | 447 |
4 files changed, 505 insertions, 453 deletions
diff --git a/source/blender/editors/include/ED_mesh.h b/source/blender/editors/include/ED_mesh.h index 194378d6bb6..f2ef3a60bc5 100644 --- a/source/blender/editors/include/ED_mesh.h +++ b/source/blender/editors/include/ED_mesh.h @@ -138,12 +138,7 @@ bool BMBVH_EdgeVisible(struct BMBVHTree *tree, struct View3D *v3d, struct Object *obedit); -/* editmesh_undo.c */ -void ED_mesh_undosys_type(struct UndoType *ut); - -/* editmesh_select.c */ -void EDBM_select_mirrored( - struct BMEditMesh *em, const int axis, const bool extend, int *r_totmirr, int *r_totfail); +/* editmesh_automerge.c */ 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, @@ -152,6 +147,13 @@ void EDBM_automerge_and_split(struct Scene *scene, bool update, const char hflag); +/* editmesh_undo.c */ +void ED_mesh_undosys_type(struct UndoType *ut); + +/* editmesh_select.c */ +void EDBM_select_mirrored( + struct BMEditMesh *em, const int axis, const bool extend, int *r_totmirr, int *r_totfail); + struct BMVert *EDBM_vert_find_nearest_ex(struct ViewContext *vc, float *r_dist, const bool use_select_bias, diff --git a/source/blender/editors/mesh/CMakeLists.txt b/source/blender/editors/mesh/CMakeLists.txt index 9a779db4812..d7d020ae19d 100644 --- a/source/blender/editors/mesh/CMakeLists.txt +++ b/source/blender/editors/mesh/CMakeLists.txt @@ -43,6 +43,7 @@ set(SRC editface.c editmesh_add.c editmesh_add_gizmo.c + editmesh_automerge.c editmesh_bevel.c editmesh_bisect.c editmesh_extrude.c diff --git a/source/blender/editors/mesh/editmesh_automerge.c b/source/blender/editors/mesh/editmesh_automerge.c new file mode 100644 index 00000000000..caf07051b00 --- /dev/null +++ b/source/blender/editors/mesh/editmesh_automerge.c @@ -0,0 +1,496 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2019 Blender Foundation. + * All rights reserved. + */ + +/** \file + * \ingroup edmesh + * + * Utility functions for merging geometry once transform has finished: + * + * - #EDBM_automerge + * - #EDBM_automerge_and_split + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_bitmap.h" +#include "BLI_math.h" +#include "BLI_sort.h" + +#include "BKE_bvhutils.h" +#include "BKE_editmesh.h" + +#include "WM_api.h" + +#include "ED_mesh.h" +#include "ED_screen.h" +#include "ED_transform.h" + +#include "DNA_object_types.h" + +#include "DEG_depsgraph.h" + +/* use bmesh operator flags for a few operators */ +#define BMO_ELE_TAG 1 + +/* -------------------------------------------------------------------- */ +/** \name Auto-Merge Selection + * + * Used after transform operations. + * \{ */ + +void EDBM_automerge(Scene *scene, Object *obedit, bool update, const char hflag) +{ + bool ok; + BMEditMesh *em = BKE_editmesh_from_object(obedit); + + ok = BMO_op_callf(em->bm, + BMO_FLAG_DEFAULTS, + "automerge verts=%hv dist=%f", + hflag, + scene->toolsettings->doublimit); + + if (LIKELY(ok) && update) { + EDBM_update_generic(em, true, true); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Auto-Merge & Split Selection + * + * Used after transform operations. + * \{ */ + +struct EDBMSplitEdge { + BMVert *v; + BMEdge *e; + float lambda; +}; + +struct EDBMSplitBestFaceData { + BMEdge **edgenet; + int edgenet_len; + + /** + * 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; + BMFace *r_best_face; +}; + +struct EDBMSplitEdgeData { + BMesh *bm; + + BMEdge *r_edge; + float r_lambda; +}; + +static bool edbm_vert_pair_share_best_splittable_face_cb(BMFace *f, + BMLoop *UNUSED(l_a), + BMLoop *UNUSED(l_b), + void *userdata) +{ + struct EDBMSplitBestFaceData *data = userdata; + float no[3], min = FLT_MAX, max = -FLT_MAX; + copy_v3_v3(no, f->no); + + BMVert *verts[2] = {NULL}; + BMEdge **e_iter = &data->edgenet[0]; + for (int i = data->edgenet_len; i--; e_iter++) { + BMIter iter; + BMVert *v; + BM_ITER_ELEM (v, &iter, *e_iter, BM_VERTS_OF_EDGE) { + if (!ELEM(v, verts[0], verts[1])) { + float dot = dot_v3v3(v->co, no); + if (dot < min) { + min = dot; + } + if (dot > max) { + max = dot; + } + } + } + verts[0] = (*e_iter)->v1; + verts[1] = (*e_iter)->v2; + } + + 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; + data->r_best_face = f; + } + + return false; +} + +/* find the best splittable face between the two vertices. */ +static bool edbm_vert_pair_share_splittable_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 void edbm_automerge_weld_linked_wire_edges_into_linked_faces(BMesh *bm, + BMVert *v, + BMEdge **r_edgenet[], + int *r_edgenet_alloc_len) +{ + 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); + BMEdge *e_next = BM_DISK_EDGE_NEXT(e, v_other); + if (e_next == e) { + /* Vert is wire_endpoint */ + edgenet_len = 0; + break; + } + e = e_next; + } + + BMLoop *dummy; + BMFace *best_face; + 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, edbm_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, edbm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy); + + best_face = data.r_best_face; + } + + if (best_face) { + BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, NULL, NULL); + } + } + + *r_edgenet = edgenet; + *r_edgenet_alloc_len = edgenet_alloc_len; +} + +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 split_faces, + 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); + + 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) { + /* Use `e->head.index` to count intersections. */ + bm->elem_index_dirty &= ~BM_EDGE; + + /* 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); + + 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); + + 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); + + BMEdge **edgenet = NULL; + int edgenet_alloc_len = 0; + if (split_faces) { + GHASH_ITER (gh_iter, ghash_targetmap) { + v = BLI_ghashIterator_getValue(&gh_iter); + BLI_assert(BM_elem_flag_test(v, hflag) || hflag == BM_ELEM_TAG); + edbm_automerge_weld_linked_wire_edges_into_linked_faces(bm, v, &edgenet, &edgenet_alloc_len); + } + } + + if (edgenet) { + MEM_freeN(edgenet); + } + + 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/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c index 4d511d45642..58ed4522399 100644 --- a/source/blender/editors/mesh/editmesh_select.c +++ b/source/blender/editors/mesh/editmesh_select.c @@ -24,26 +24,19 @@ #include "MEM_guardedalloc.h" #include "BLI_bitmap.h" -#include "BLI_bitmap_draw_2d.h" #include "BLI_listbase.h" #include "BLI_linklist.h" #include "BLI_linklist_stack.h" #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" #include "BKE_editmesh.h" #include "BKE_layer.h" -#include "IMB_imbuf_types.h" -#include "IMB_imbuf.h" - #include "WM_api.h" #include "WM_types.h" @@ -69,7 +62,6 @@ #include "DEG_depsgraph.h" #include "DEG_depsgraph_query.h" -#include "DRW_engine.h" #include "DRW_select_buffer.h" #include "mesh_intern.h" /* own include */ @@ -174,445 +166,6 @@ void EDBM_select_mirrored( /** \} */ /* -------------------------------------------------------------------- */ -/** \name Select Auto-Merge - * - * Used after transform operations. - * \{ */ - -void EDBM_automerge(Scene *scene, Object *obedit, bool update, const char hflag) -{ - bool ok; - BMEditMesh *em = BKE_editmesh_from_object(obedit); - - ok = BMO_op_callf(em->bm, - BMO_FLAG_DEFAULTS, - "automerge verts=%hv dist=%f", - hflag, - scene->toolsettings->doublimit); - - if (LIKELY(ok) && update) { - EDBM_update_generic(em, true, true); - } -} - -struct EDBMSplitEdge { - BMVert *v; - BMEdge *e; - float lambda; -}; - -struct EDBMSplitBestFaceData { - BMEdge **edgenet; - int edgenet_len; - - /** - * 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; - BMFace *r_best_face; -}; - -struct EDBMSplitEdgeData { - BMesh *bm; - - BMEdge *r_edge; - float r_lambda; -}; - -static bool edbm_vert_pair_share_best_splittable_face_cb(BMFace *f, - BMLoop *UNUSED(l_a), - BMLoop *UNUSED(l_b), - void *userdata) -{ - struct EDBMSplitBestFaceData *data = userdata; - float no[3], min = FLT_MAX, max = -FLT_MAX; - copy_v3_v3(no, f->no); - - BMVert *verts[2] = {NULL}; - BMEdge **e_iter = &data->edgenet[0]; - for (int i = data->edgenet_len; i--; e_iter++) { - BMIter iter; - BMVert *v; - BM_ITER_ELEM (v, &iter, *e_iter, BM_VERTS_OF_EDGE) { - if (!ELEM(v, verts[0], verts[1])) { - float dot = dot_v3v3(v->co, no); - if (dot < min) { - min = dot; - } - if (dot > max) { - max = dot; - } - } - } - verts[0] = (*e_iter)->v1; - verts[1] = (*e_iter)->v2; - } - - 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; - data->r_best_face = f; - } - - return false; -} - -/* find the best splittable face between the two vertices. */ -static bool edbm_vert_pair_share_splittable_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 void edbm_automerge_weld_linked_wire_edges_into_linked_faces(BMesh *bm, - BMVert *v, - BMEdge **r_edgenet[], - int *r_edgenet_alloc_len) -{ - 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); - BMEdge *e_next = BM_DISK_EDGE_NEXT(e, v_other); - if (e_next == e) { - /* Vert is wire_endpoint */ - edgenet_len = 0; - break; - } - e = e_next; - } - - BMLoop *dummy; - BMFace *best_face; - 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, edbm_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, edbm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy); - - best_face = data.r_best_face; - } - - if (best_face) { - BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, NULL, NULL); - } - } - - *r_edgenet = edgenet; - *r_edgenet_alloc_len = edgenet_alloc_len; -} - -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 split_faces, - 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); - - 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) { - /* Use `e->head.index` to count intersections. */ - bm->elem_index_dirty &= ~BM_EDGE; - - /* 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); - - 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); - - 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); - - BMEdge **edgenet = NULL; - int edgenet_alloc_len = 0; - if (split_faces) { - GHASH_ITER (gh_iter, ghash_targetmap) { - v = BLI_ghashIterator_getValue(&gh_iter); - BLI_assert(BM_elem_flag_test(v, hflag) || hflag == BM_ELEM_TAG); - edbm_automerge_weld_linked_wire_edges_into_linked_faces(bm, v, &edgenet, &edgenet_alloc_len); - } - } - - if (edgenet) { - MEM_freeN(edgenet); - } - - BMO_op_finish(bm, &findop); - BMO_op_finish(bm, &weldop); - - if (LIKELY(ok) && update) { - EDBM_update_generic(em, true, true); - } -} - -/** \} */ - -/* -------------------------------------------------------------------- */ /** \name Back-Buffer OpenGL Selection * \{ */ |