[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [46081] trunk/blender/source/blender: Add convex hull operator (bmesh operator and wm operator.)

Nicholas Bishop nicholasbishop at gmail.com
Sun Apr 29 18:09:40 CEST 2012


Revision: 46081
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=46081
Author:   nicholasbishop
Date:     2012-04-29 16:09:40 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
Add convex hull operator (bmesh operator and wm operator.)

Image-heavy user documentation:
http://wiki.blender.org/index.php/User:Nicholasbishop/Convex_Hull

Thanks to Campbell for providing code review:
http://codereview.appspot.com/6114060

Modified Paths:
--------------
    trunk/blender/source/blender/bmesh/CMakeLists.txt
    trunk/blender/source/blender/bmesh/intern/bmesh_error.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_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_hull.c

Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt	2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt	2012-04-29 16:09:40 UTC (rev 46081)
@@ -41,6 +41,7 @@
 	operators/bmo_dupe.c
 	operators/bmo_edgesplit.c
 	operators/bmo_extrude.c
+	operators/bmo_hull.c
 	operators/bmo_inset.c
 	operators/bmo_join_triangles.c
 	operators/bmo_mesh_conv.c

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_error.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_error.h	2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_error.h	2012-04-29 16:09:40 UTC (rev 46081)
@@ -69,6 +69,7 @@
 #define BMERR_NONMANIFOLD				8
 #define BMERR_INVALID_SELECTION			9
 #define BMERR_MESH_ERROR				10
+#define BMERR_CONVEX_HULL_FAILED		11
 
 /* BMESH_ASSERT */
 #ifdef WITH_ASSERT_ABORT

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c	2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c	2012-04-29 16:09:40 UTC (rev 46081)
@@ -1144,7 +1144,36 @@
 	BMO_OP_FLAG_UNTAN_MULTIRES
 };
 
+/*
+ * Convex Hull
+ *
+ * Builds a convex hull from the vertices in 'input'.
+ *
+ * If 'use_existing_faces' is true, the hull will not output triangles
+ * that are covered by a pre-existing face.
+ *
+ * All hull vertices, faces, and edges are added to 'geomout'. Any
+ * input elements that end up inside the hull (i.e. are not used by an
+ * output face) are added to the 'interior_geom' slot. The
+ * 'unused_geom' slot will contain all interior geometry that is
+ * completely unused. Lastly, 'holes_geom' contains edges and faces
+ * that were in the input and are part of the hull.
+*/
+static BMOpDefine bmo_convex_hull_def = {
+	"convex_hull",
+	{{BMO_OP_SLOT_ELEMENT_BUF, "input"},
+	 {BMO_OP_SLOT_BOOL, "use_existing_faces"},
 
+	 /* Outputs */
+	 {BMO_OP_SLOT_ELEMENT_BUF, "geomout"},
+	 {BMO_OP_SLOT_ELEMENT_BUF, "interior_geom"},
+	 {BMO_OP_SLOT_ELEMENT_BUF, "unused_geom"},
+	 {BMO_OP_SLOT_ELEMENT_BUF, "holes_geom"},
+	 {0} /* null-terminating sentinel */},
+	bmo_convex_hull_exec,
+	0
+};
+
 BMOpDefine *opdefines[] = {
 	&bmo_split_def,
 	&bmo_spin_def,
@@ -1214,6 +1243,7 @@
 	&bmo_inset_def,
 	&bmo_wireframe_def,
 	&bmo_vertex_slide_def,
+	&bmo_convex_hull_def,
 };
 
 int bmesh_total_ops = (sizeof(opdefines) / sizeof(void *));

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h	2012-04-29 16:09:28 UTC (rev 46080)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h	2012-04-29 16:09:40 UTC (rev 46081)
@@ -101,5 +101,6 @@
 void bmo_solidify_face_region_exec(BMesh *bm, BMOperator *op);
 void bmo_inset_exec(BMesh *bm, BMOperator *op);
 void bmo_wireframe_exec(BMesh *bm, BMOperator *op);
+void bmo_convex_hull_exec(BMesh *bm, BMOperator *op);
 
 #endif /* __BMESH_OPERATORS_PRIVATE_H__ */

Added: trunk/blender/source/blender/bmesh/operators/bmo_hull.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_hull.c	                        (rev 0)
+++ trunk/blender/source/blender/bmesh/operators/bmo_hull.c	2012-04-29 16:09:40 UTC (rev 46081)
@@ -0,0 +1,742 @@
+/*
+ * ***** 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): Nicholas Bishop
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/operators/bmo_hull.c
+ *  \ingroup bmesh
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_ghash.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+
+/* XXX: using 128 for totelem and pchunk of mempool, no idea what good
+   values would be though */
+#include "BLI_mempool.h"
+
+#include "bmesh.h"
+
+/* Internal operator flags */
+typedef enum {
+	HULL_FLAG_INPUT =			(1 << 0),
+	HULL_FLAG_TETRA_VERT =		(1 << 1),
+	
+	HULL_FLAG_INTERIOR_ELE = 	(1 << 2),
+	HULL_FLAG_OUTPUT_GEOM =		(1 << 3),
+	
+	HULL_FLAG_DEL =				(1 << 4),
+	HULL_FLAG_HOLE =			(1 << 5)
+} HullFlags;
+
+/* Store hull triangles seperate from BMesh faces until the end; this
+   way we don't have to worry about cleaning up extraneous edges or
+   incorrectly deleting existing geometry. */
+typedef struct HullTriangle {
+	BMVert *v[3];
+	float no[3];
+	int skip;
+} HullTriangle;
+
+/* These edges define the hole created in the hull by deleting faces
+   that can "see" a new vertex (the boundary edges then form the edge
+   of a new triangle fan that has the new vertex as its center) */
+typedef struct HullBoundaryEdge {
+	struct HullBoundaryEdge *next, *prev;
+	BMVert *v[2];
+} HullBoundaryEdge;
+
+
+
+/*************************** Boundary Edges ***************************/
+
+static int edge_match(BMVert *e1_0, BMVert *e1_1, BMVert *e2[2])
+{
+	return (e1_0 == e2[0] && e1_1 == e2[1]) ||
+	       (e1_0 == e2[1] && e1_1 == e2[0]);
+}
+
+/* Returns true if the edge (e1, e2) is already in edges; that edge is
+   deleted here as well. if not found just returns 0 */
+static int check_for_dup(ListBase *edges, BLI_mempool *pool,
+						 BMVert *e1, BMVert *e2)
+{
+	HullBoundaryEdge *e, *next;
+
+	for (e = edges->first; e; e = next) {
+		next = e->next;
+
+		if (edge_match(e1, e2, e->v)) {
+			/* remove the interior edge */
+			BLI_remlink(edges, e);
+			BLI_mempool_free(pool, e);
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+static void expand_boundary_edges(ListBase *edges, BLI_mempool *edge_pool,
+								  const HullTriangle *t)
+{
+	HullBoundaryEdge *new;
+	int i;
+
+	/* Insert each triangle edge into the boundary list; if any of
+	   its edges are already in there, remove the edge entirely */
+	for (i = 0; i < 3; i++) {
+		if (!check_for_dup(edges, edge_pool, t->v[i], t->v[(i + 1) % 3])) {
+			new = BLI_mempool_calloc(edge_pool);
+			new->v[0] = t->v[i];
+			new->v[1] = t->v[(i + 1) % 3];
+			BLI_addtail(edges, new);
+		}
+	}
+}
+
+
+
+/*************************** Hull Triangles ***************************/
+
+static void hull_add_triangle(GHash *hull_triangles, BLI_mempool *pool,
+							  BMVert *v1, BMVert *v2, BMVert *v3)
+{
+	HullTriangle *t;
+
+	t = BLI_mempool_calloc(pool);
+	t->v[0] = v1;
+	t->v[1] = v2;
+	t->v[2] = v3;
+
+	BLI_ghash_insert(hull_triangles, t, NULL);
+	normal_tri_v3(t->no, v1->co, v2->co, v3->co);
+}
+
+static int hull_point_tri_side(const HullTriangle *t, const float co[3])
+{
+	float p[3], d;
+	sub_v3_v3v3(p, co, t->v[0]->co);
+	d = dot_v3v3(t->no, p);
+	if (d < 0) return -1;
+	else if (d > 0) return 1;
+	else return 0;
+}
+
+/* Get all hull triangles that vertex 'v' is outside of */
+static GHash *hull_triangles_v_outside(GHash *hull_triangles, const BMVert *v)
+{
+	GHash *outside;
+	GHashIterator iter;
+
+	outside = BLI_ghash_new(BLI_ghashutil_ptrhash,
+							BLI_ghashutil_ptrcmp,
+							"outside");
+
+	GHASH_ITER (iter, hull_triangles) {
+		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+		
+		if (hull_point_tri_side(t, v->co) >= 0)
+			BLI_ghash_insert(outside, t, NULL);
+	}
+
+	return outside;
+}
+
+/* Similar to above, but just get true/false rather than triangles */
+static int hull_test_v_outside(GHash *hull_triangles, const BMVert *v)
+{
+	GHashIterator iter;
+
+	GHASH_ITER (iter, hull_triangles) {
+		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+		
+		if (hull_point_tri_side(t, v->co) >= 0)
+			return TRUE;
+	}
+
+	return FALSE;
+}
+
+
+/* For vertex 'v', find which triangles must be deleted to extend the
+   hull; find the boundary edges of that hole so that it can be filled
+   with connections to the new vertex, and update the hull_triangles
+   to delete the marked triangles */
+static void add_point(GHash *hull_triangles, BLI_mempool *hull_pool,
+					  BLI_mempool *edge_pool, GHash *outside, BMVert *v)
+{
+	ListBase edges = {NULL, NULL};
+	HullBoundaryEdge *e, *next;
+	GHashIterator iter;
+
+	GHASH_ITER (iter, outside) {
+		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+		expand_boundary_edges(&edges, edge_pool, t);
+		
+		/* Delete the triangle */
+		BLI_ghash_remove(hull_triangles, t, NULL, NULL);
+		BLI_mempool_free(hull_pool, t);
+	}
+
+	/* Fill hole boundary with triangles to new point */
+	for (e = edges.first; e; e = next) {
+		next = e->next;
+		hull_add_triangle(hull_triangles, hull_pool, e->v[0], e->v[1], v);
+		BLI_mempool_free(edge_pool, e);
+	}
+}
+
+static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
+{
+	BMIter iter;
+	BMFace *f;
+
+	BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
+		if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
+			!BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
+			return f;
+	}
+
+	return NULL;
+}
+
+static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
+{
+	GHashIterator iter;
+	
+	GHASH_ITER (iter, hull_triangles) {
+		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+
+		if (!t->skip) {
+			BMEdge *edges[3] = {
+				BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
+				BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
+				BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
+			};
+			BMFace *f, *example = NULL;
+			int i;
+
+			/* Look for an adjacent face that existed before the hull */
+			for (i = 0; i < 3; i++) {
+				if (!example)
+					example = hull_find_example_face(bm, edges[i]);
+			}
+
+			f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
+			BM_face_copy_shared(bm, f);
+
+			/* Mark face/verts/edges for 'geomout' slot and select */

@@ Diff output truncated at 10240 characters. @@


More information about the Bf-blender-cvs mailing list