diff options
-rw-r--r-- | source/blender/bmesh/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/bmesh/bmesh.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_duplicate.c | 139 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_duplicate.h | 33 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_query.c | 85 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_query.h | 7 | ||||
-rw-r--r-- | source/blender/editors/mesh/editmesh_tools.c | 198 |
7 files changed, 372 insertions, 93 deletions
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index 599871a505a..00954eb400c 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -99,6 +99,8 @@ set(SRC intern/bmesh_mesh.h intern/bmesh_mesh_conv.c intern/bmesh_mesh_conv.h + intern/bmesh_mesh_duplicate.c + intern/bmesh_mesh_duplicate.h intern/bmesh_mesh_validate.c intern/bmesh_mesh_validate.h intern/bmesh_mods.c diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h index b7356a89314..bdb719e0d7a 100644 --- a/source/blender/bmesh/bmesh.h +++ b/source/blender/bmesh/bmesh.h @@ -216,6 +216,7 @@ extern "C" { #include "intern/bmesh_marking.h" #include "intern/bmesh_mesh.h" #include "intern/bmesh_mesh_conv.h" +#include "intern/bmesh_mesh_duplicate.h" #include "intern/bmesh_mesh_validate.h" #include "intern/bmesh_mods.h" #include "intern/bmesh_operators.h" diff --git a/source/blender/bmesh/intern/bmesh_mesh_duplicate.c b/source/blender/bmesh/intern/bmesh_mesh_duplicate.c new file mode 100644 index 00000000000..51f9d2eab1d --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_duplicate.c @@ -0,0 +1,139 @@ +/* + * 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. + */ + +/** \file + * \ingroup bmesh + * + * Duplicate geometry from one mesh from another. + */ + +#include "DNA_object_types.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_alloca.h" +#include "BLI_math_vector.h" + +#include "bmesh.h" +#include "intern/bmesh_private.h" /* for element checking */ + +static BMVert *bm_vert_copy(BMesh *bm_src, BMesh *bm_dst, BMVert *v_src) +{ + BMVert *v_dst = BM_vert_create(bm_dst, v_src->co, NULL, BM_CREATE_SKIP_CD); + BM_elem_attrs_copy(bm_src, bm_dst, v_src, v_dst); + return v_dst; +} + +static BMEdge *bm_edge_copy_with_arrays(BMesh *bm_src, + BMesh *bm_dst, + BMEdge *e_src, + BMVert **verts_dst) +{ + BMVert *e_dst_v1 = verts_dst[BM_elem_index_get(e_src->v1)]; + BMVert *e_dst_v2 = verts_dst[BM_elem_index_get(e_src->v2)]; + BMEdge *e_dst = BM_edge_create(bm_dst, e_dst_v1, e_dst_v2, NULL, BM_CREATE_SKIP_CD); + BM_elem_attrs_copy(bm_src, bm_dst, e_src, e_dst); + return e_dst; +} + +static BMFace *bm_face_copy_with_arrays( + BMesh *bm_src, BMesh *bm_dst, BMFace *f_src, BMVert **verts_dst, BMEdge **edges_dst + +) +{ + BMFace *f_dst; + BMVert **vtar = BLI_array_alloca(vtar, f_src->len); + BMEdge **edar = BLI_array_alloca(edar, f_src->len); + BMLoop *l_iter_src, *l_iter_dst, *l_first_src; + int i; + + l_first_src = BM_FACE_FIRST_LOOP(f_src); + + /* Lookup verts & edges. */ + l_iter_src = l_first_src; + i = 0; + do { + vtar[i] = verts_dst[BM_elem_index_get(l_iter_src->v)]; + edar[i] = edges_dst[BM_elem_index_get(l_iter_src->e)]; + i++; + } while ((l_iter_src = l_iter_src->next) != l_first_src); + + /* Create new face. */ + f_dst = BM_face_create(bm_dst, vtar, edar, f_src->len, NULL, BM_CREATE_SKIP_CD); + + /* Copy attributes. */ + BM_elem_attrs_copy(bm_src, bm_dst, f_src, f_dst); + + /* Copy per-loop custom data. */ + l_iter_src = l_first_src; + l_iter_dst = BM_FACE_FIRST_LOOP(f_dst); + do { + BM_elem_attrs_copy(bm_src, bm_dst, l_iter_src, l_iter_dst); + } while ((void)(l_iter_dst = l_iter_dst->next), (l_iter_src = l_iter_src->next) != l_first_src); + + return f_dst; +} + +/** + * Geometry must be completely isolated. + */ +void BM_mesh_copy_arrays(BMesh *bm_src, + BMesh *bm_dst, + BMVert **verts_src, + uint verts_src_len, + BMEdge **edges_src, + uint edges_src_len, + BMFace **faces_src, + uint faces_src_len) +{ + /* Vertices. */ + BMVert **verts_dst = MEM_mallocN(sizeof(*verts_dst) * verts_src_len, __func__); + for (uint i = 0; i < verts_src_len; i++) { + BMVert *v_src = verts_src[i]; + BM_elem_index_set(v_src, i); /* set_dirty! */ + + BMVert *v_dst = bm_vert_copy(bm_src, bm_dst, v_src); + BM_elem_index_set(v_dst, i); /* set_ok */ + verts_dst[i] = v_dst; + } + bm_src->elem_index_dirty |= BM_VERT; + bm_dst->elem_index_dirty &= ~BM_VERT; + + /* Edges. */ + BMEdge **edges_dst = MEM_mallocN(sizeof(*edges_dst) * edges_src_len, __func__); + for (uint i = 0; i < edges_src_len; i++) { + BMEdge *e_src = edges_src[i]; + BM_elem_index_set(e_src, i); /* set_dirty! */ + + BMEdge *e_dst = bm_edge_copy_with_arrays(bm_src, bm_dst, e_src, verts_dst); + BM_elem_index_set(e_dst, i); + edges_dst[i] = e_dst; + } + bm_src->elem_index_dirty |= BM_EDGE; + bm_dst->elem_index_dirty &= ~BM_EDGE; + + /* Faces. */ + for (uint i = 0; i < faces_src_len; i++) { + BMFace *f_src = faces_src[i]; + BMFace *f_dst = bm_face_copy_with_arrays(bm_src, bm_dst, f_src, verts_dst, edges_dst); + BM_elem_index_set(f_dst, i); + } + bm_dst->elem_index_dirty &= ~BM_FACE; + + /* Cleanup. */ + MEM_freeN(verts_dst); + MEM_freeN(edges_dst); +} diff --git a/source/blender/bmesh/intern/bmesh_mesh_duplicate.h b/source/blender/bmesh/intern/bmesh_mesh_duplicate.h new file mode 100644 index 00000000000..17d4071b69f --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_duplicate.h @@ -0,0 +1,33 @@ +/* + * 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. + */ + +#ifndef __BMESH_MESH_DUPLICATE_H__ +#define __BMESH_MESH_DUPLICATE_H__ + +/** \file + * \ingroup bmesh + */ + +void BM_mesh_copy_arrays(BMesh *bm_src, + BMesh *bm_dst, + BMVert **verts_src, + uint verts_src_len, + BMEdge **edges_src, + uint edges_src_len, + BMFace **faces_src, + uint faces_src_len); + +#endif /* __BMESH_MESH_DUPLICATE_H__ */ diff --git a/source/blender/bmesh/intern/bmesh_query.c b/source/blender/bmesh/intern/bmesh_query.c index 219bec15e5b..cebfd4df75b 100644 --- a/source/blender/bmesh/intern/bmesh_query.c +++ b/source/blender/bmesh/intern/bmesh_query.c @@ -2808,6 +2808,91 @@ int BM_mesh_calc_edge_groups(BMesh *bm, return group_curr; } +int BM_mesh_calc_edge_groups_as_arrays( + BMesh *bm, BMVert **verts, BMEdge **edges, BMFace **faces, int (**r_groups)[3]) +{ + int(*groups)[3] = MEM_mallocN(sizeof(*groups) * bm->totvert, __func__); + STACK_DECLARE(groups); + STACK_INIT(groups, bm->totvert); + + /* Clear all selected vertices */ + BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false); + + BMVert **stack = MEM_mallocN(sizeof(*stack) * bm->totvert, __func__); + STACK_DECLARE(stack); + STACK_INIT(stack, bm->totvert); + + STACK_DECLARE(verts); + STACK_INIT(verts, bm->totvert); + + STACK_DECLARE(edges); + STACK_INIT(edges, bm->totedge); + + STACK_DECLARE(faces); + STACK_INIT(faces, bm->totface); + + BMIter iter; + BMVert *v_stack_init; + BM_ITER_MESH (v_stack_init, &iter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_flag_test(v_stack_init, BM_ELEM_TAG)) { + continue; + } + + const uint verts_init = STACK_SIZE(verts); + const uint edges_init = STACK_SIZE(edges); + const uint faces_init = STACK_SIZE(faces); + + /* Initialize stack. */ + BM_elem_flag_enable(v_stack_init, BM_ELEM_TAG); + STACK_PUSH(verts, v_stack_init); + + if (v_stack_init->e != NULL) { + BMVert *v_iter = v_stack_init; + do { + BMEdge *e_iter, *e_first; + e_iter = e_first = v_iter->e; + do { + if (!BM_elem_flag_test(e_iter, BM_ELEM_TAG)) { + BM_elem_flag_enable(e_iter, BM_ELEM_TAG); + STACK_PUSH(edges, e_iter); + + if (e_iter->l != NULL) { + BMLoop *l_iter, *l_first; + l_iter = l_first = e_iter->l; + do { + if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { + BM_elem_flag_enable(l_iter->f, BM_ELEM_TAG); + STACK_PUSH(faces, l_iter->f); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + + BMVert *v_other = BM_edge_other_vert(e_iter, v_iter); + if (!BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + BM_elem_flag_enable(v_other, BM_ELEM_TAG); + STACK_PUSH(verts, v_other); + + STACK_PUSH(stack, v_other); + } + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != e_first); + } while ((v_iter = STACK_POP(stack))); + } + + int *g = STACK_PUSH_RET(groups); + g[0] = STACK_SIZE(verts) - verts_init; + g[1] = STACK_SIZE(edges) - edges_init; + g[2] = STACK_SIZE(faces) - faces_init; + } + + MEM_freeN(stack); + + /* Reduce alloc to required size. */ + groups = MEM_reallocN(groups, sizeof(*groups) * STACK_SIZE(groups)); + *r_groups = groups; + return STACK_SIZE(groups); +} + float bmesh_subd_falloff_calc(const int falloff, float val) { switch (falloff) { diff --git a/source/blender/bmesh/intern/bmesh_query.h b/source/blender/bmesh/intern/bmesh_query.h index 3a864fbb5dd..134e0b99691 100644 --- a/source/blender/bmesh/intern/bmesh_query.h +++ b/source/blender/bmesh/intern/bmesh_query.h @@ -249,6 +249,13 @@ int BM_mesh_calc_edge_groups(BMesh *bm, void *user_data, const char hflag_test) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3); +int BM_mesh_calc_edge_groups_as_arrays(BMesh *bm, + BMVert **verts, + BMEdge **edges, + BMFace **faces, + int (**r_groups)[3]) ATTR_WARN_UNUSED_RESULT + ATTR_NONNULL(1, 2, 3, 4, 5); + /* not really any good place to put this */ float bmesh_subd_falloff_calc(const int falloff, float val) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c index cf3170b5446..83555e728d7 100644 --- a/source/blender/editors/mesh/editmesh_tools.c +++ b/source/blender/editors/mesh/editmesh_tools.c @@ -3946,6 +3946,61 @@ static Base *mesh_separate_tagged( return base_new; } +static Base *mesh_separate_arrays(Main *bmain, + Scene *scene, + ViewLayer *view_layer, + Base *base_old, + BMesh *bm_old, + BMVert **verts, + uint verts_len, + BMEdge **edges, + uint edges_len, + BMFace **faces, + uint faces_len) +{ + Base *base_new; + Object *obedit = base_old->object; + BMesh *bm_new; + + bm_new = BM_mesh_create(&bm_mesh_allocsize_default, + &((struct BMeshCreateParams){ + .use_toolflags = true, + })); + + CustomData_copy(&bm_old->vdata, &bm_new->vdata, CD_MASK_BMESH.vmask, CD_CALLOC, 0); + CustomData_copy(&bm_old->edata, &bm_new->edata, CD_MASK_BMESH.emask, CD_CALLOC, 0); + CustomData_copy(&bm_old->ldata, &bm_new->ldata, CD_MASK_BMESH.lmask, CD_CALLOC, 0); + CustomData_copy(&bm_old->pdata, &bm_new->pdata, CD_MASK_BMESH.pmask, CD_CALLOC, 0); + + CustomData_bmesh_init_pool(&bm_new->vdata, verts_len, BM_VERT); + CustomData_bmesh_init_pool(&bm_new->edata, edges_len, BM_EDGE); + CustomData_bmesh_init_pool(&bm_new->ldata, faces_len * 3, BM_LOOP); + CustomData_bmesh_init_pool(&bm_new->pdata, faces_len, BM_FACE); + + base_new = ED_object_add_duplicate(bmain, scene, view_layer, base_old, USER_DUP_MESH); + + /* normally would call directly after but in this case delay recalc */ + /* DAG_relations_tag_update(bmain); */ + + /* new in 2.5 */ + assign_matarar(bmain, base_new->object, give_matarar(obedit), *give_totcolp(obedit)); + + ED_object_base_select(base_new, BA_SELECT); + + BM_mesh_copy_arrays(bm_old, bm_new, verts, verts_len, edges, edges_len, faces, faces_len); + + for (uint i = 0; i < verts_len; i++) { + BM_vert_kill(bm_old, verts[i]); + } + + BM_mesh_bm_to_me(bmain, bm_new, base_new->object->data, (&(struct BMeshToMeshParams){0})); + + BM_mesh_free(bm_new); + ((Mesh *)base_new->object->data)->edit_mesh = NULL; + + return base_new; +} + static bool mesh_separate_selected( Main *bmain, Scene *scene, ViewLayer *view_layer, Base *base_old, BMesh *bm_old) { @@ -3959,41 +4014,6 @@ static bool mesh_separate_selected( return (mesh_separate_tagged(bmain, scene, view_layer, base_old, bm_old) != NULL); } -/* flush a hflag to from verts to edges/faces */ -static void bm_mesh_hflag_flush_vert(BMesh *bm, const char hflag) -{ - BMEdge *e; - BMLoop *l_iter; - BMLoop *l_first; - BMFace *f; - - BMIter eiter; - BMIter fiter; - - bool ok; - - BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e->v1, hflag) && BM_elem_flag_test(e->v2, hflag)) { - BM_elem_flag_enable(e, hflag); - } - else { - BM_elem_flag_disable(e, hflag); - } - } - BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { - ok = true; - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - if (!BM_elem_flag_test(l_iter->v, hflag)) { - ok = false; - break; - } - } while ((l_iter = l_iter->next) != l_first); - - BM_elem_flag_set(f, hflag, ok); - } -} - /** * Sets an object to a single material. from one of its slots. * @@ -4109,72 +4129,64 @@ static bool mesh_separate_material( static bool mesh_separate_loose( Main *bmain, Scene *scene, ViewLayer *view_layer, Base *base_old, BMesh *bm_old) { - int i; - BMEdge *e; - BMVert *v_seed; - BMWalker walker; - bool result = false; - int max_iter = bm_old->totvert; + /* Without this, we duplicate the object mode mesh for each loose part. + * This can get very slow especially for large meshes with many parts + * which would duplicate the mesh on entering edit-mode. */ + const bool clear_object_data = true; - /* Clear all selected vertices */ - BM_mesh_elem_hflag_disable_all(bm_old, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false); + bool result = false; - /* A "while (true)" loop should work here as each iteration should - * select and remove at least one vertex and when all vertices - * are selected the loop will break out. But guard against bad - * behavior by limiting iterations to the number of vertices in the - * original mesh.*/ - for (i = 0; i < max_iter; i++) { - int tot = 0; - /* Get a seed vertex to start the walk */ - v_seed = BM_iter_at_index(bm_old, BM_VERTS_OF_MESH, NULL, 0); + BMVert **vert_groups = MEM_mallocN(sizeof(*vert_groups) * bm_old->totvert, __func__); + BMEdge **edge_groups = MEM_mallocN(sizeof(*edge_groups) * bm_old->totedge, __func__); + BMFace **face_groups = MEM_mallocN(sizeof(*face_groups) * bm_old->totface, __func__); + + int(*groups)[3] = NULL; + int groups_len = BM_mesh_calc_edge_groups_as_arrays( + bm_old, vert_groups, edge_groups, face_groups, &groups); + if (groups_len <= 1) { + goto finally; + } + + if (clear_object_data) { + ED_mesh_geometry_clear(base_old->object->data); + } + + /* Separate out all groups except the first. */ + uint group_ofs[3] = {UNPACK3(groups[0])}; + for (int i = 1; i < groups_len; i++) { + Base *base_new = mesh_separate_arrays(bmain, + scene, + view_layer, + base_old, + bm_old, + vert_groups + group_ofs[0], + groups[i][0], + edge_groups + group_ofs[1], + groups[i][1], + face_groups + group_ofs[2], + groups[i][2]); + result |= (base_new != NULL); - /* No vertices available, can't do anything */ - if (v_seed == NULL) { - break; - } + group_ofs[0] += groups[i][0]; + group_ofs[1] += groups[i][1]; + group_ofs[2] += groups[i][2]; + } - /* Select the seed explicitly, in case it has no edges */ - if (!BM_elem_flag_test(v_seed, BM_ELEM_TAG)) { - BM_elem_flag_enable(v_seed, BM_ELEM_TAG); - tot++; - } + Mesh *me_old = base_old->object->data; + BMEditMesh *em_old = me_old->edit_mesh; - /* Walk from the single vertex, selecting everything connected - * to it */ - BMW_init(&walker, - bm_old, - BMW_VERT_SHELL, - BMW_MASK_NOP, - BMW_MASK_NOP, - BMW_MASK_NOP, - BMW_FLAG_NOP, - BMW_NIL_LAY); + BM_mesh_elem_hflag_disable_all(em_old->bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_SELECT, false); - for (e = BMW_begin(&walker, v_seed); e; e = BMW_step(&walker)) { - if (!BM_elem_flag_test(e->v1, BM_ELEM_TAG)) { - BM_elem_flag_enable(e->v1, BM_ELEM_TAG); - tot++; - } - if (!BM_elem_flag_test(e->v2, BM_ELEM_TAG)) { - BM_elem_flag_enable(e->v2, BM_ELEM_TAG); - tot++; - } - } - BMW_end(&walker); - - if (bm_old->totvert == tot) { - /* Every vertex selected, nothing to separate, work is done */ - break; - } + if (clear_object_data) { + BM_mesh_bm_to_me(NULL, em_old->bm, me_old, (&(struct BMeshToMeshParams){0})); + } - /* Flush the selection to get edge/face selections matching - * the vertex selection */ - bm_mesh_hflag_flush_vert(bm_old, BM_ELEM_TAG); +finally: + MEM_freeN(vert_groups); + MEM_freeN(edge_groups); + MEM_freeN(face_groups); - /* Move selection into a separate object */ - result |= (mesh_separate_tagged(bmain, scene, view_layer, base_old, bm_old) != NULL); - } + MEM_freeN(groups); return result; } |