diff options
author | Campbell Barton <ideasman42@gmail.com> | 2019-08-28 05:40:48 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2019-08-28 06:19:55 +0300 |
commit | f93b69c17a2e382a636f796ecf7256ba2e960138 (patch) | |
tree | c186566749fe2d9e7d8b1ae61be48bdc3e35a156 /source/blender/editors/mesh/editmesh_automerge.c | |
parent | 697fd86506fd0caaa41e2fbf0463b5229d09251e (diff) |
Cleanup: split automerge logic into own file
This isn't closely related to selection & this file was over 5k lines.
Diffstat (limited to 'source/blender/editors/mesh/editmesh_automerge.c')
-rw-r--r-- | source/blender/editors/mesh/editmesh_automerge.c | 496 |
1 files changed, 496 insertions, 0 deletions
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); + } +} + +/** \} */ |