un-subdivide bmesh operator, useful for making lower polygon versions of models,...
authorCampbell Barton <ideasman42@gmail.com>
Tue, 16 Oct 2012 16:04:12 +0000 (16:04 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 16 Oct 2012 16:04:12 +0000 (16:04 +0000)
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
source/blender/bmesh/CMakeLists.txt
source/blender/bmesh/intern/bmesh_core.c
source/blender/bmesh/intern/bmesh_iterators.h
source/blender/bmesh/intern/bmesh_opdefines.c
source/blender/bmesh/intern/bmesh_operators_private.h
source/blender/bmesh/operators/bmo_unsubdivide.c [new file with mode: 0644]
source/blender/editors/mesh/editmesh_select.c
source/blender/editors/mesh/editmesh_tools.c
source/blender/editors/mesh/mesh_intern.h
source/blender/editors/mesh/mesh_ops.c

index f787f18fad3b69666c7ce19bd346cbb1ae188e91..ee40bf96a70d7bbf6c14137e9b92036b9f9ae5e2 100644 (file)
@@ -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()
 
index c23eb60561470b294963941507b47b2402b58388..20387684b66b9da2b59f2ace884c3cbc4d7e483d 100644 (file)
@@ -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
 
index 16c7f6f153986fc14fc015577b06d5c17c51e2bd..413f480c60d2b6a429a6c4accb2ada60b68bbb55 100644 (file)
@@ -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.
index 8d0eeca31ed07e184fce56130e5a178975679ed5..27e01f4eaf5942fcd327813c383c47b71ae6f0a1 100644 (file)
@@ -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;
 
index f50de0d6ee4c9d2417962175ea2e30223af70218..407e7caae0f302e2fda037ad7ec6c8e195d5fe66 100644 (file)
@@ -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,
 
index fa239bb6ceb36ba9ad7c05d5099180364ca18453..d6135efe19ac7009dd670e6cf6611bbb9b70dd2c 100644 (file)
@@ -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 (file)
index 0000000..01a9b6f
--- /dev/null
@@ -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
+
+}
+
index fe3860de839ed63ce3858ca3b540a64f2c48c76a..40132c697e6b3c8c26c2fa64774dae15bb6c153e 100644 (file)
@@ -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);
index 1507597feebb0c2b87d50c0ccdb100fd67abe618..3255853442a85294cab2b4bf62348e09057829a0 100644 (file)
@@ -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;
index 5fcf4fe4377f93b690a2fba33018cb38aeaf6e35..5c782dc2266f86adabce675f7cb618130ba77b61 100644 (file)
@@ -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);
index 8a575e57a60e309d06a4917b22f0fb30da4381d1..c4e8fd709894cf9a2ec026dcb4922e090ca5bf14 100644 (file)
@@ -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);