From 12a8c19956815cda832c87761923f573a4d6b8d3 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 16 Oct 2012 16:04:12 +0000 Subject: un-subdivide bmesh operator, useful for making lower polygon versions of models, can give nicer results then edge collapsing which tends to give a lot of sharp triangles. works on edges and faces, has iteration option to further reduce the poly count. access from the edge menu, under subdivide. example: http://www.graphicall.org/ftp/ideasman42/bmesh_unsubdivide.png --- release/scripts/startup/bl_ui/space_view3d.py | 1 + source/blender/bmesh/CMakeLists.txt | 1 + source/blender/bmesh/intern/bmesh_core.c | 2 + source/blender/bmesh/intern/bmesh_iterators.h | 2 +- source/blender/bmesh/intern/bmesh_opdefines.c | 10 + .../blender/bmesh/intern/bmesh_operators_private.h | 1 + source/blender/bmesh/operators/bmo_unsubdivide.c | 348 +++++++++++++++++++++ source/blender/editors/mesh/editmesh_select.c | 14 +- source/blender/editors/mesh/editmesh_tools.c | 45 +++ source/blender/editors/mesh/mesh_intern.h | 1 + source/blender/editors/mesh/mesh_ops.c | 1 + 11 files changed, 422 insertions(+), 4 deletions(-) create mode 100644 source/blender/bmesh/operators/bmo_unsubdivide.c diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py index f787f18fad3..ee40bf96a70 100644 --- a/release/scripts/startup/bl_ui/space_view3d.py +++ b/release/scripts/startup/bl_ui/space_view3d.py @@ -1821,6 +1821,7 @@ class VIEW3D_MT_edit_mesh_edges(Menu): layout.operator("mesh.edge_face_add") layout.operator("mesh.subdivide") + layout.operator("mesh.unsubdivide") layout.separator() diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index c23eb605614..20387684b66 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -56,6 +56,7 @@ set(SRC operators/bmo_subdivide.c operators/bmo_subdivide.h operators/bmo_triangulate.c + operators/bmo_unsubdivide.c operators/bmo_utils.c operators/bmo_wireframe.c diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index 16c7f6f1539..413f480c60d 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -1143,6 +1143,8 @@ static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *UNUSED(example)) /** * \brief Split Face Make Edge (SFME) * + * \warning this is a low level function, most likely you want to use #BM_face_split() + * * Takes as input two vertices in a single face. An edge is created which divides the original face * into two distinct regions. One of the regions is assigned to the original face and it is closed off. * The second region has a new face assigned to it. diff --git a/source/blender/bmesh/intern/bmesh_iterators.h b/source/blender/bmesh/intern/bmesh_iterators.h index 8d0eeca31ed..27e01f4eaf5 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.h +++ b/source/blender/bmesh/intern/bmesh_iterators.h @@ -111,7 +111,7 @@ typedef struct BMIter { long l; float f; } filter; - int count; + int count; /* note, only some iterators set this, don't rely on it */ char itype; } BMIter; diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index f50de0d6ee4..407e7caae0f 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -698,6 +698,15 @@ static BMOpDefine bmo_triangulate_def = { BMO_OP_FLAG_UNTAN_MULTIRES }; +static BMOpDefine bmo_unsubdivide_def = { + "unsubdivide", + {{BMO_OP_SLOT_ELEMENT_BUF, "verts"}, /* input vertices */ + {BMO_OP_SLOT_INT, "iterations"}, + {0} /* null-terminating sentinel */}, + bmo_unsubdivide_exec, + BMO_OP_FLAG_UNTAN_MULTIRES +}; + static BMOpDefine bmo_subdivide_edges_def = { "subdivide_edges", {{BMO_OP_SLOT_ELEMENT_BUF, "edges"}, @@ -1274,6 +1283,7 @@ BMOpDefine *opdefines[] = { &bmo_translate_def, &bmo_triangle_fill_def, &bmo_triangulate_def, + &bmo_unsubdivide_def, &bmo_weld_verts_def, &bmo_wireframe_def, diff --git a/source/blender/bmesh/intern/bmesh_operators_private.h b/source/blender/bmesh/intern/bmesh_operators_private.h index fa239bb6ceb..d6135efe19a 100644 --- a/source/blender/bmesh/intern/bmesh_operators_private.h +++ b/source/blender/bmesh/intern/bmesh_operators_private.h @@ -101,6 +101,7 @@ void bmo_transform_exec(BMesh *bm, BMOperator *op); void bmo_translate_exec(BMesh *bm, BMOperator *op); void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op); void bmo_triangulate_exec(BMesh *bm, BMOperator *op); +void bmo_unsubdivide_exec(BMesh *bm, BMOperator *op); void bmo_weld_verts_exec(BMesh *bm, BMOperator *op); void bmo_wireframe_exec(BMesh *bm, BMOperator *op); diff --git a/source/blender/bmesh/operators/bmo_unsubdivide.c b/source/blender/bmesh/operators/bmo_unsubdivide.c new file mode 100644 index 00000000000..01a9b6f8416 --- /dev/null +++ b/source/blender/bmesh/operators/bmo_unsubdivide.c @@ -0,0 +1,348 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * 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. + * + * Contributor(s): Campbell Barton + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/operators/bmo_unsubdivide.c + * \ingroup bmesh + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_math.h" + +#include "bmesh.h" + +#include "intern/bmesh_operators_private.h" /* own include */ + + +static int bm_vert_dissolve_fan_test(BMVert *v) +{ + /* check if we should walk over these verts */ + BMIter iter; + BMEdge *e; + + unsigned int tot_edge = 0; + unsigned int tot_edge_boundary = 0; + unsigned int tot_edge_manifold = 0; + unsigned int tot_edge_wire = 0; + + BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { + if (BM_edge_is_boundary(e)) { + tot_edge_boundary++; + } + else if (BM_edge_is_manifold(e)) { + tot_edge_manifold++; + } + else if (BM_edge_is_wire(e)) { + tot_edge_wire++; + } + tot_edge++; + } + + if ((tot_edge == 4) && (tot_edge_boundary == 0) && (tot_edge_manifold == 4)) { + return TRUE; + } + else if ((tot_edge == 3) && (tot_edge_boundary == 0) && (tot_edge_manifold == 3)) { + return TRUE; + } + else if ((tot_edge == 3) && (tot_edge_boundary == 2) && (tot_edge_manifold == 1)) { + return TRUE; + } + else if ((tot_edge == 2) && (tot_edge_wire == 2)) { + return TRUE; + } + return FALSE; +} + +static int bm_vert_dissolve_fan(BMesh *bm, BMVert *v) +{ + /* collapse under 2 conditions. + * - vert connects to 4 manifold edges (and 4 faces). + * - vert connecrs to 1 manifold edge, 2 boundary edges (and 2 faces). + * + * This covers boundary verts of a quad grid and center verts. + * note that surrounding faces dont have to be quads. + */ + + BMIter iter; + BMEdge *e; + + unsigned int tot_loop = 0; + unsigned int tot_edge = 0; + unsigned int tot_edge_boundary = 0; + unsigned int tot_edge_manifold = 0; + unsigned int tot_edge_wire = 0; + + BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { + if (BM_edge_is_boundary(e)) { + tot_edge_boundary++; + } + else if (BM_edge_is_manifold(e)) { + tot_edge_manifold++; + } + else if (BM_edge_is_wire(e)) { + tot_edge_wire++; + } + tot_edge++; + } + + if (tot_edge == 2) { + /* check for 2 wire verts only */ + if (tot_edge_wire == 2) { + return (BM_vert_collapse_edge(bm, v->e, v, TRUE) != NULL); + } + } + else if (tot_edge == 4) { + /* check for 4 faces surrounding */ + if (tot_edge_boundary == 0 && tot_edge_manifold == 4) { + /* good to go! */ + tot_loop = 4; + } + } + else if (tot_edge == 3) { + /* check for 2 faces surrounding at a boundary */ + if (tot_edge_boundary == 2 && tot_edge_manifold == 1) { + /* good to go! */ + tot_loop = 2; + } + else if (tot_edge_boundary == 0 && tot_edge_manifold == 3) { + /* good to go! */ + tot_loop = 3; + } + } + + if (tot_loop) { + BMLoop *f_loop[4]; + unsigned int i; + + /* ensure there are exactly tot_loop loops */ + BLI_assert(BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v, tot_loop) == NULL); + BM_iter_as_array(bm, BM_LOOPS_OF_VERT, v, (void **)f_loop, tot_loop); + + for (i = 0; i < tot_loop; i++) { + BMLoop *l = f_loop[i]; + if (l->f->len > 3) { + BLI_assert(l->prev->v != l->next->v); + BM_face_split(bm, l->f, l->prev->v, l->next->v, NULL, NULL, TRUE); + } + } + + return BM_vert_dissolve(bm, v); + } + + return FALSE; +} + +enum { + VERT_INDEX_DO_COLLAPSE = -1, + VERT_INDEX_INIT = 0, + VERT_INDEX_IGNORE = 1 +}; + +// #define USE_WALKER /* gives uneven results, disable for now */ +// #define USE_ALL_VERTS + +/* - BMVert.flag & BM_ELEM_TAG: shows we touched this vert + * - BMVert.index == -1: shows we will remove this vert + */ +void bmo_unsubdivide_exec(BMesh *bm, BMOperator *op) +{ +#ifdef USE_WALKER +# define ELE_VERT_TAG 1 +#else + BMVert **vert_seek_a = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__); + BMVert **vert_seek_b = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__); + unsigned vert_seek_a_tot = 0; + unsigned vert_seek_b_tot = 0; +#endif + + BMVert *v; + BMIter iter; + + const unsigned int offset = 0; + const unsigned int nth = 2; + + const int iterations = maxi(1, BMO_slot_int_get(op, "iterations")); + int iter_step; + +#ifdef USE_ALL_VERTS + (void)op; + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + BM_elem_flag_enable(v, BM_ELEM_TAG); + } +#else /* USE_ALL_VERTS */ + BMOpSlot *vinput = BMO_slot_get(op, "verts"); + BMVert **vinput_arr = (BMVert **)vinput->data.p; + int v_index; + + /* tag verts */ + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + BM_elem_flag_disable(v, BM_ELEM_TAG); + } + for (v_index = 0; v_index < vinput->len; v_index++) { + v = vinput_arr[v_index]; + BM_elem_flag_enable(v, BM_ELEM_TAG); + } +#endif /* USE_ALL_VERTS */ + + + for (iter_step = 0; iter_step < iterations; iter_step++) { + int iter_done; + + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_flag_test(v, BM_ELEM_TAG) && bm_vert_dissolve_fan_test(v)) { +#ifdef USE_WALKER + BMO_elem_flag_enable(bm, v, ELE_VERT_TAG); +#endif + BM_elem_index_set(v, VERT_INDEX_INIT); /* set_dirty! */ + } + else { + BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */ + } + } + /* dont with selecting tagged verts */ + + + /* main loop, keep tagging until we can't tag any more islands */ + while (TRUE) { +#ifdef USE_WALKER + BMWalker walker; +#else + unsigned int depth = 1; + unsigned int i; +#endif + BMVert *v_first = NULL; + BMVert *v; + + /* we could avoid iterating from the start each time */ + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + if (v->e && (BM_elem_index_get(v) == VERT_INDEX_INIT)) { +#ifdef USE_WALKER + if (BMO_elem_flag_test(bm, v, ELE_VERT_TAG)) +#endif + { + /* check again incase the topology changed */ + if (bm_vert_dissolve_fan_test(v)) { + v_first = v; + } + break; + } + } + } + if (v_first == NULL) { + break; + } + +#ifdef USE_WALKER + /* Walk over selected elements starting at active */ + BMW_init(&walker, bm, BMW_CONNECTED_VERTEX, + ELE_VERT_TAG, BMW_MASK_NOP, BMW_MASK_NOP, + BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */ + BMW_NIL_LAY); + + BLI_assert(walker.order == BMW_BREADTH_FIRST); + for (v = BMW_begin(&walker, v_first); v != NULL; v = BMW_step(&walker)) { + /* Deselect elements that aren't at "nth" depth from active */ + if (BM_elem_index_get(v) == VERT_INDEX_INIT) { + if ((offset + BMW_current_depth(&walker)) % nth) { + /* tag for removal */ + BM_elem_index_set(v, VERT_INDEX_DO_COLLAPSE); /* set_dirty! */ + } + else { + /* works better to allow these verts to be checked again */ + //BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */ + } + } + } + BMW_end(&walker); +#else + + BM_elem_index_set(v_first, (offset + depth) % nth ? VERT_INDEX_IGNORE : VERT_INDEX_DO_COLLAPSE); /* set_dirty! */ + + vert_seek_b_tot = 0; + vert_seek_b[vert_seek_b_tot++] = v_first; + + while (TRUE) { + BMEdge *e; + + if ((offset + depth) % nth) { + vert_seek_a_tot = 0; + for (i = 0; i < vert_seek_b_tot; i++) { + v = vert_seek_b[i]; + BLI_assert(BM_elem_index_get(v) == VERT_INDEX_IGNORE); + BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) { + BM_elem_index_set(v_other, VERT_INDEX_DO_COLLAPSE); /* set_dirty! */ + vert_seek_a[vert_seek_a_tot++] = v_other; + } + } + } + if (vert_seek_a_tot == 0) { + break; + } + } + else { + vert_seek_b_tot = 0; + for (i = 0; i < vert_seek_a_tot; i++) { + v = vert_seek_a[i]; + BLI_assert(BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE); + BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) { + BM_elem_index_set(v_other, VERT_INDEX_IGNORE); /* set_dirty! */ + vert_seek_b[vert_seek_b_tot++] = v_other; + } + } + } + if (vert_seek_b_tot == 0) { + break; + } + } + + depth++; + } +#endif /* USE_WALKER */ + + } + + /* now we tagged all verts -1 for removal, lets loop over and rebuild faces */ + iter_done = FALSE; + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE) { + iter_done |= bm_vert_dissolve_fan(bm, v); + } + } + + if (iter_done == FALSE) { + break; + } + } + + bm->elem_index_dirty |= BM_VERT; + +#ifndef USE_WALKER + MEM_freeN(vert_seek_a); + MEM_freeN(vert_seek_b); +#endif + +} + diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c index fe3860de839..40132c697e6 100644 --- a/source/blender/editors/mesh/editmesh_select.c +++ b/source/blender/editors/mesh/editmesh_select.c @@ -2165,11 +2165,19 @@ static void walker_deselect_nth(BMEditMesh *em, int nth, int offset, BMHeader *h BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */ BMW_NIL_LAY); + /* use tag to avoid touching the same verts twice */ + BM_ITER_MESH (ele, &iter, bm, itertype) { + BM_elem_flag_disable(ele, BM_ELEM_TAG); + } + BLI_assert(walker.order == BMW_BREADTH_FIRST); for (ele = BMW_begin(&walker, h_act); ele != NULL; ele = BMW_step(&walker)) { - /* Deselect elements that aren't at "nth" depth from active */ - if ((offset + BMW_current_depth(&walker)) % nth) { - BM_elem_select_set(bm, ele, FALSE); + if (!BM_elem_flag_test(ele, BM_ELEM_TAG)) { + /* Deselect elements that aren't at "nth" depth from active */ + if ((offset + BMW_current_depth(&walker)) % nth) { + BM_elem_select_set(bm, ele, FALSE); + } + BM_elem_flag_enable(ele, BM_ELEM_TAG); } } BMW_end(&walker); diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c index 1507597feeb..3255853442a 100644 --- a/source/blender/editors/mesh/editmesh_tools.c +++ b/source/blender/editors/mesh/editmesh_tools.c @@ -156,6 +156,51 @@ void MESH_OT_subdivide(wmOperatorType *ot) } +static int edbm_unsubdivide_exec(bContext *C, wmOperator *op) +{ + Object *obedit = CTX_data_edit_object(C); + BMEditMesh *em = BMEdit_FromObject(obedit); + BMOperator bmop; + + int iterations = RNA_int_get(op->ptr, "iterations"); + + EDBM_op_init(em, &bmop, op, + "unsubdivide verts=%hv iterations=%i", BM_ELEM_SELECT, iterations); + + BMO_op_exec(em->bm, &bmop); + + if (!EDBM_op_finish(em, &bmop, op, TRUE)) { + return 0; + } + + if ((em->selectmode & SCE_SELECT_VERTEX) == 0) { + EDBM_selectmode_flush_ex(em, SCE_SELECT_VERTEX); /* need to flush vert->face first */ + } + EDBM_selectmode_flush(em); + + EDBM_update_generic(C, em, TRUE); + + return OPERATOR_FINISHED; +} + +void MESH_OT_unsubdivide(wmOperatorType *ot) +{ + /* identifiers */ + ot->name = "Un-Subdivide"; + ot->description = "UnSubdivide selected edges & faces"; + ot->idname = "MESH_OT_unsubdivide"; + + /* api callbacks */ + ot->exec = edbm_unsubdivide_exec; + ot->poll = ED_operator_editmesh; + + /* flags */ + ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; + + /* props */ + RNA_def_int(ot->srna, "iterations", 2, 1, INT_MAX, "Iterations", "Number of times to unsubdivide", 1, 100); +} + void EMBM_project_snap_verts(bContext *C, ARegion *ar, BMEditMesh *em) { Object *obedit = em->ob; diff --git a/source/blender/editors/mesh/mesh_intern.h b/source/blender/editors/mesh/mesh_intern.h index 5fcf4fe4377..5c782dc2266 100644 --- a/source/blender/editors/mesh/mesh_intern.h +++ b/source/blender/editors/mesh/mesh_intern.h @@ -144,6 +144,7 @@ extern struct EnumPropertyItem *corner_type_items; void MESH_OT_merge(struct wmOperatorType *ot); void MESH_OT_subdivide(struct wmOperatorType *ot); +void MESH_OT_unsubdivide(struct wmOperatorType *ot); void MESH_OT_remove_doubles(struct wmOperatorType *ot); void MESH_OT_spin(struct wmOperatorType *ot); void MESH_OT_screw(struct wmOperatorType *ot); diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c index 8a575e57a60..c4e8fd70989 100644 --- a/source/blender/editors/mesh/mesh_ops.c +++ b/source/blender/editors/mesh/mesh_ops.c @@ -74,6 +74,7 @@ void ED_operatortypes_mesh(void) WM_operatortype_append(MESH_OT_normals_make_consistent); WM_operatortype_append(MESH_OT_merge); WM_operatortype_append(MESH_OT_subdivide); + WM_operatortype_append(MESH_OT_unsubdivide); WM_operatortype_append(MESH_OT_faces_select_linked_flat); WM_operatortype_append(MESH_OT_edges_select_sharp); WM_operatortype_append(MESH_OT_primitive_plane_add); -- cgit v1.2.3