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

3 files changed, 32 insertions, 0 deletions

diff --git a/source/blender/bmesh/intern/bmesh_error.h b/source/blender/bmesh/intern/bmesh_error.h
index 84065fe88f6..606e9eeb23b 100644
--- a/source/blender/bmesh/intern/bmesh_error.h
+++ b/source/blender/bmesh/intern/bmesh_error.h
@@ -69,6 +69,7 @@ void BMO_error_clear(BMesh *bm);
 #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
diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index af083fc30a6..2ff28aee191 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -1144,6 +1144,35 @@ static BMOpDefine bmo_vertex_slide_def = {
 	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,
@@ -1214,6 +1243,7 @@ BMOpDefine *opdefines[] = {
 	&bmo_inset_def,
 	&bmo_wireframe_def,
 	&bmo_vertex_slide_def,
+	&bmo_convex_hull_def,
 };
 
 int bmesh_total_ops = (sizeof(opdefines) / sizeof(void *));
diff --git a/source/blender/bmesh/intern/bmesh_operators_private.h b/source/blender/bmesh/intern/bmesh_operators_private.h
index e222c3422c0..df48ec8468f 100644
--- a/source/blender/bmesh/intern/bmesh_operators_private.h
+++ b/source/blender/bmesh/intern/bmesh_operators_private.h
@@ -101,5 +101,6 @@ void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op);
 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__ */