[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [51372] trunk/blender: 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 .

Campbell Barton ideasman42 at gmail.com
Tue Oct 16 18:04:14 CEST 2012


Revision: 51372
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=51372
Author:   campbellbarton
Date:     2012-10-16 16:04:12 +0000 (Tue, 16 Oct 2012)
Log Message:
-----------
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

Modified Paths:
--------------
    trunk/blender/release/scripts/startup/bl_ui/space_view3d.py
    trunk/blender/source/blender/bmesh/CMakeLists.txt
    trunk/blender/source/blender/bmesh/intern/bmesh_core.c
    trunk/blender/source/blender/bmesh/intern/bmesh_iterators.h
    trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
    trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
    trunk/blender/source/blender/editors/mesh/editmesh_select.c
    trunk/blender/source/blender/editors/mesh/editmesh_tools.c
    trunk/blender/source/blender/editors/mesh/mesh_intern.h
    trunk/blender/source/blender/editors/mesh/mesh_ops.c

Added Paths:
-----------
    trunk/blender/source/blender/bmesh/operators/bmo_unsubdivide.c

Modified: trunk/blender/release/scripts/startup/bl_ui/space_view3d.py
===================================================================
--- trunk/blender/release/scripts/startup/bl_ui/space_view3d.py	2012-10-16 15:38:52 UTC (rev 51371)
+++ trunk/blender/release/scripts/startup/bl_ui/space_view3d.py	2012-10-16 16:04:12 UTC (rev 51372)
@@ -1821,6 +1821,7 @@
 
         layout.operator("mesh.edge_face_add")
         layout.operator("mesh.subdivide")
+        layout.operator("mesh.unsubdivide")
 
         layout.separator()
 

Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt	2012-10-16 15:38:52 UTC (rev 51371)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt	2012-10-16 16:04:12 UTC (rev 51372)
@@ -56,6 +56,7 @@
 	operators/bmo_subdivide.c
 	operators/bmo_subdivide.h
 	operators/bmo_triangulate.c
+	operators/bmo_unsubdivide.c
 	operators/bmo_utils.c
 	operators/bmo_wireframe.c
 

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_core.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_core.c	2012-10-16 15:38:52 UTC (rev 51371)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_core.c	2012-10-16 16:04:12 UTC (rev 51372)
@@ -1143,6 +1143,8 @@
 /**
  * \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.

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_iterators.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_iterators.h	2012-10-16 15:38:52 UTC (rev 51371)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_iterators.h	2012-10-16 16:04:12 UTC (rev 51372)
@@ -111,7 +111,7 @@
 		long        l;
 		float       f;
 	} filter;
-	int count;
+	int count;  /* note, only some iterators set this, don't rely on it */
 	char itype;
 } BMIter;
 

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c	2012-10-16 15:38:52 UTC (rev 51371)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c	2012-10-16 16:04:12 UTC (rev 51372)
@@ -698,6 +698,15 @@
 	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 @@
 	&bmo_translate_def,
 	&bmo_triangle_fill_def,
 	&bmo_triangulate_def,
+	&bmo_unsubdivide_def,
 	&bmo_weld_verts_def,
 	&bmo_wireframe_def,
 

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h	2012-10-16 15:38:52 UTC (rev 51371)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h	2012-10-16 16:04:12 UTC (rev 51372)
@@ -101,6 +101,7 @@
 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);
 

Added: trunk/blender/source/blender/bmesh/operators/bmo_unsubdivide.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_unsubdivide.c	                        (rev 0)
+++ trunk/blender/source/blender/bmesh/operators/bmo_unsubdivide.c	2012-10-16 16:04:12 UTC (rev 51372)
@@ -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) {

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list