Partially replace convex hull implementation with Bullet implementation

* Bullet's convex hull implementation is significantly more robust
  than the one I implemented, as well as being faster.

* This fixes bug [#32864] "Convex Hull fails in some cases."
  projects.blender.org/tracker/?func=detail&aid=32864&group_id=9&atid=498

  That bug, and others like it, relate to the poor handling of
  co-planar surfaces in the input. Pretty much any model that is
  simple-subdivided a few times gave very bad results before, Bullet's
  implementation handles this much better.

* In order to ensure a smooth transition, the Bullet output is
  translated into the existing HullTriangle hash structure. This makes
  it easy to ensure that the existing slot output stays the same; the
  interactions between the slots are somewhat complicated, detangling
  is a TODO.

* Reviewed by Brecht:
  https://codereview.appspot.com/6741063

8 files changed, 159 insertions, 321 deletions

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 3c329b1dce4..1e39e7f77d3 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -29,6 +29,7 @@ set(INC
 	../blenlib
 	../makesdna
 	../../../intern/guardedalloc
+	../../../extern/bullet2/src
 )
 
 set(INC_SYS
@@ -113,4 +114,8 @@ if(MSVC)
 	set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} /WX")
 endif()
 
+if(WITH_BULLET)
+  add_definitions(-DWITH_BULLET)
+endif()
+
 blender_add_lib(bf_bmesh "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/bmesh/SConscript b/source/blender/bmesh/SConscript
index fb00aef4d78..be6332be478 100644
--- a/source/blender/bmesh/SConscript
+++ b/source/blender/bmesh/SConscript
@@ -13,7 +13,12 @@ incs = [
 	'../makesdna',
 	'../blenkernel',
 	'#/intern/guardedalloc',
+        '#/extern/bullet2/src'
 	]
 
 defs = []
+
+if env['WITH_BF_BULLET']:
+    defs.append('WITH_BULLET')
+
 env.BlenderLib ( libname = 'bf_bmesh', sources = sources, includes = Split(incs), libtype = ['core','player'], defines=defs, priority=[100, 100], compileflags=cflags )
diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index 9f47892c15b..b527cffbfdc 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -1162,6 +1162,7 @@ static BMOpDefine bmo_slide_vert_def = {
 	BMO_OP_FLAG_UNTAN_MULTIRES
 };
 
+#ifdef WITH_BULLET
 /*
  * Convex Hull
  *
@@ -1191,6 +1192,7 @@ static BMOpDefine bmo_convex_hull_def = {
 	bmo_convex_hull_exec,
 	0
 };
+#endif
 
 /*
  * Symmetrize
@@ -1227,7 +1229,9 @@ BMOpDefine *opdefines[] = {
 	&bmo_collapse_uvs_def,
 	&bmo_connect_verts_def,
 	&bmo_contextual_create_def,
+#ifdef WITH_BULLET
 	&bmo_convex_hull_def,
+#endif
 	&bmo_create_circle_def,
 	&bmo_create_cone_def,
 	&bmo_create_cube_def,
diff --git a/source/blender/bmesh/operators/bmo_hull.c b/source/blender/bmesh/operators/bmo_hull.c
index d97d901777c..0d8c06817c8 100644
--- a/source/blender/bmesh/operators/bmo_hull.c
+++ b/source/blender/bmesh/operators/bmo_hull.c
@@ -24,19 +24,17 @@
  *  \ingroup bmesh
  */
 
+#ifdef WITH_BULLET
+
 #include "MEM_guardedalloc.h"
 
+#include "BLI_array.h"
 #include "BLI_ghash.h"
 #include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 
-/*XXX: This operator doesn't work well (at all?) for flat surfaces with
- * >3 sides - creating overlapping faces at times.
- * An easy workaround is to add in some noise but this is
- * weak and unreliable, ideally this would detect flat surfaces
- * (possibly making them into ngons) - see
- */
+#include "Bullet-C-Api.h"
 
 /* XXX: using 128 for totelem and pchunk of mempool, no idea what good
  * values would be though */
@@ -46,21 +44,15 @@
 
 #include "intern/bmesh_operators_private.h"  /* own include */
 
-#define HULL_EPSILON_FLT 0.0001f
-/* values above 0.0001 cause errors, see below for details, don't increase
- * without checking against bug [#32027] */
-#define HULL_EPSILON_DOT_FLT 0.00000001f
-
 /* 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_INTERIOR_ELE =    (1 << 1),
+	HULL_FLAG_OUTPUT_GEOM =     (1 << 2),
 	
-	HULL_FLAG_DEL =             (1 << 4),
-	HULL_FLAG_HOLE =            (1 << 5)
+	HULL_FLAG_DEL =             (1 << 3),
+	HULL_FLAG_HOLE =            (1 << 4)
 } HullFlags;
 
 /* Store hull triangles separate from BMesh faces until the end; this
@@ -72,63 +64,6 @@ typedef struct HullTriangle {
 	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_v1, BMVert *e1_v2, BMVert *e2[2])
-{
-	return (e1_v1 == e2[0] && e1_v2 == e2[1]) ||
-	       (e1_v1 == e2[1] && e1_v2 == 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 *v1, BMVert *v2)
-{
-	HullBoundaryEdge *e, *e_next;
-
-	for (e = edges->first; e; e = e_next) {
-		e_next = e->next;
-
-		if (edge_match(v1, v2, 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 *e_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])) {
-			e_new = BLI_mempool_calloc(edge_pool);
-			e_new->v[0] = t->v[i];
-			e_new->v[1] = t->v[(i + 1) % 3];
-			BLI_addtail(edges, e_new);
-		}
-	}
-}
-
 
 
 /*************************** Hull Triangles ***************************/
@@ -152,75 +87,6 @@ static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *poo
 	normal_tri_v3(t->no, v1->co, v2->co, v3->co);
 }
 
-static int hull_point_tri_side(const HullTriangle *t, const float co[3])
-{
-	/* Added epsilon to fix bug [#31941], improves output when some
-	 * vertices are nearly coplanar. Might need further tweaking for
-	 * other cases though.
-	 * ...
-	 * Update: epsilon of 0.0001 causes [#32027], use HULL_EPSILON_DOT_FLT
-	 * and give it a much smaller value
-	 * */
-	float p[3], d;
-	sub_v3_v3v3(p, co, t->v[0]->co);
-	d = dot_v3v3(t->no, p);
-	if      (d < -HULL_EPSILON_DOT_FLT) return -1;
-	else if (d >  HULL_EPSILON_DOT_FLT) 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_ptr_new("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;
-}
-
-/* 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(BMesh *bm, GHash *hull_triangles, BLI_mempool *hull_pool,
-                      BLI_mempool *edge_pool, GHash *outside, BMVert *v)
-{
-	ListBase edges = {NULL, NULL};
-	HullBoundaryEdge *e, *e_next;
-	GHashIterator iter;
-
-	GHASH_ITER (iter, outside) {
-		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
-		int i;
-		
-		expand_boundary_edges(&edges, edge_pool, t);
-
-		/* Mark triangle's vertices as interior */
-		for (i = 0; i < 3; i++)
-			BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
-		
-		/* 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 = e_next) {
-		e_next = e->next;
-		hull_add_triangle(bm, 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;
@@ -362,158 +228,6 @@ static void hull_final_edges_free(HullFinalEdges *final_edges)
 
 
 
-/************************* Initial Tetrahedron ************************/
-
-static void hull_add_tetrahedron(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
-                                 BMVert *tetra[4])
-{
-	float center[3];
-	int i, indices[4][3] = {
-		{0, 1, 2},
-		{0, 2, 3},
-		{1, 0, 3},
-		{2, 1, 3}
-	};
-
-	/* Calculate center */
-	zero_v3(center);
-	for (i = 0; i < 4; i++)
-		add_v3_v3(center, tetra[i]->co);
-	mul_v3_fl(center, 0.25f);
-
-	for (i = 0; i < 4; i++) {
-		BMVert *v1 = tetra[indices[i][0]];
-		BMVert *v2 = tetra[indices[i][1]];
-		BMVert *v3 = tetra[indices[i][2]];
-		float no[3], d[3];
-
-		normal_tri_v3(no, v1->co, v2->co, v3->co);
-		sub_v3_v3v3(d, center, v1->co);
-		if (dot_v3v3(no, d) > 0)
-			SWAP(BMVert *, v1, v3);
-
-		hull_add_triangle(bm, hull_triangles, pool, v1, v2, v3);
-	}
-}
-
-/* For each axis, get the minimum and maximum input vertices */
-static void hull_get_min_max(BMesh *bm, BMOperator *op,
-                             BMVert *min[3], BMVert *max[3])
-{
-	BMOIter oiter;
-	BMVert *v;
-
-	min[0] = min[1] = min[2] = NULL;
-	max[0] = max[1] = max[2] = NULL;
-
-	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
-		int i;
-		
-		for (i = 0; i < 3; i++) {
-			if (!min[i] || v->co[i] < min[i]->co[i])
-				min[i] = v;
-			if (!max[i] || v->co[i] > max[i]->co[i])
-				max[i] = v;
-		}
-	}
-}
-
-/* Returns true if input is coplanar */
-static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
-                                       BMVert *tetra[4])
-{
-	BMVert *min[3], *max[3], *v;
-	BMOIter oiter;
-	float widest_axis_len, largest_dist, plane_normal[3];
-	int i, j, widest_axis;
-	
-	tetra[0] = tetra[1] = tetra[2] = tetra[3] = NULL;
-	hull_get_min_max(bm, op, min, max);
-
-	/* Check for flat axis */
-	for (i = 0; i < 3; i++) {
-		if (min[i] == max[i]) {
-			return TRUE;
-		}
-	}
-
-	/* Find widest axis */
-	widest_axis_len = 0.0f;
-	widest_axis = 0; /* set here in the unlikey case this isn't set below */
-	for (i = 0; i < 3; i++) {
-		float len = (max[i]->co[i] - min[i]->co[i]);
-		if (len >= widest_axis_len) {
-			widest_axis_len = len;
-			widest_axis = i;
-		}
-	}
-
-	/* Use widest axis for first two points */
-	tetra[0] = min[widest_axis];
-	tetra[1] = max[widest_axis];
-	BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
-	BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
-
-	/* Choose third vertex farthest from existing line segment */
-	largest_dist = 0;
-	for (i = 0; i < 3; i++) {
-		BMVert *v;
-		float dist;
-
-		if (i == widest_axis)
-			continue;
-
-		v = min[i];
-		for (j = 0; j < 2; j++) {
-			dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
-			if (dist > largest_dist) {
-				largest_dist = dist;
-				tetra[2] = v;
-			}
-
-			v = max[i];
-		}
-	}
-
-	if (tetra[2]) {
-		BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
-	}
-	else {
-		return TRUE;
-	}
-
-	/* Check for colinear vertices */
-	if (largest_dist < HULL_EPSILON_FLT)
-		return TRUE;
-
-	/* Choose fourth point farthest from existing plane */
-	largest_dist = 0;
-	normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
-	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
-		if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
-			float dist = fabsf(dist_to_plane_v3(v->co, tetra[0]->co, plane_normal));
-			if (dist > largest_dist) {
-				largest_dist = dist;
-				tetra[3] = v;
-			}
-		}
-	}
-
-	if (tetra[3]) {
-		BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
-	}
-	else {
-		return TRUE;
-	}
-
-	if (largest_dist < HULL_EPSILON_FLT)
-		return TRUE;
-
-	return FALSE;
-}
-
-
-
 /**************************** Final Output ****************************/
 
 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
@@ -666,11 +380,132 @@ static void hull_tag_holes(BMesh *bm, BMOperator *op)
 	}
 }
 
+static int hull_input_vert_count(BMesh *bm, BMOperator *op)
+{
+	BMOIter oiter;
+	BMVert *v;
+	int count = 0;
+
+	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
+		count++;
+	}
+
+	return count;
+}
+
+static BMVert **hull_input_verts_copy(BMesh *bm, BMOperator *op,
+									  const int num_input_verts)
+{
+	BMOIter oiter;
+	BMVert *v;
+	BMVert **input_verts = MEM_callocN(sizeof(*input_verts) *
+									   num_input_verts, AT);
+	int i = 0;
+
+	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
+		input_verts[i++] = v;
+	}
+
+	return input_verts;
+}
+
+static float (*hull_verts_for_bullet(BMVert **input_verts,
+									 const int num_input_verts))[3]
+{
+	float (*coords)[3] = MEM_callocN(sizeof(*coords) * num_input_verts, AT);
+	int i;
+
+	for (i = 0; i < num_input_verts; i++) {
+		copy_v3_v3(coords[i], input_verts[i]->co);
+	}
+
+	return coords;
+}
+
+static BMVert **hull_verts_from_bullet(plConvexHull hull,
+									   BMVert **input_verts,
+									   const int num_input_verts)
+{
+	const int num_verts = plConvexHullNumVertices(hull);
+	BMVert **hull_verts = MEM_mallocN(sizeof(*hull_verts) *
+									  num_verts, AT);
+	int i;
+
+	for (i = 0; i < num_verts; i++) {
+		float co[3];
+		int original_index;
+		plConvexHullGetVertex(hull, i, co, &original_index);
+
+		if (original_index >= 0 && original_index < num_input_verts) {
+			hull_verts[i] = input_verts[original_index];
+		}
+		else
+			BLI_assert(!"Unexpected new vertex in hull output");
+	}
+
+	return hull_verts;
+}
+
+static void hull_from_bullet(BMesh *bm, BMOperator *op,
+							 GHash *hull_triangles,
+							 BLI_mempool *pool)
+{
+	int *fvi = NULL;
+	BLI_array_declare(fvi);
+
+	BMVert **input_verts;
+	float (*coords)[3];
+	BMVert **hull_verts;
+
+	plConvexHull hull;
+	int i, count = 0;
+
+	const int num_input_verts = hull_input_vert_count(bm, op);
+
+	input_verts = hull_input_verts_copy(bm, op, num_input_verts);
+	coords = hull_verts_for_bullet(input_verts, num_input_verts);
+
+	hull = plConvexHullCompute(coords, num_input_verts);
+	hull_verts = hull_verts_from_bullet(hull, input_verts, num_input_verts);
+	
+	count = plConvexHullNumFaces(hull);
+	for (i = 0; i < count; i++) {
+		const int len = plConvexHullGetFaceSize(hull, i);
+
+		if (len > 2) {
+			BMVert *fv[3];
+			int j;
+
+			/* Get face vertex indices */
+			BLI_array_empty(fvi);
+			BLI_array_grow_items(fvi, len);
+			plConvexHullGetFaceVertices(hull, i, fvi);
+
+			/* Note: here we throw away any NGons from Bullet and turn
+			 * them into triangle fans. Would be nice to use these
+			 * directly, but will have to wait until HullTriangle goes
+			 * away (TODO) */
+			fv[0] = hull_verts[fvi[0]];
+			for (j = 2; j < len; j++) {
+				fv[1] = hull_verts[fvi[j - 1]];
+				fv[2] = hull_verts[fvi[j]];
+
+				hull_add_triangle(bm, hull_triangles, pool,
+								  fv[0], fv[1], fv[2]);
+			}
+		}
+	}
+
+	BLI_array_free(fvi);
+	MEM_freeN(hull_verts);
+	MEM_freeN(coords);
+	MEM_freeN(input_verts);
+}
+
 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 {
 	HullFinalEdges *final_edges;
-	BLI_mempool *hull_pool, *edge_pool;
-	BMVert *v, *tetra[4];
+	BLI_mempool *hull_pool;
 	BMElemF *ele;
 	BMOIter oiter;
 	GHash *hull_triangles;
@@ -682,15 +517,6 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 		return;
 	}
 
-	/* Initialize the convex hull by building a tetrahedron. A
-	 * degenerate tetrahedron can cause problems, so report error and
-	 * fail if the result is coplanar */
-	if (hull_find_large_tetrahedron(bm, op, tetra)) {
-		BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
-		                "Input vertices are coplanar");
-		return;
-	}
-
 	/* Tag input elements */
 	BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL) {
 		BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
@@ -700,26 +526,11 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 			BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
 	}
 
-	edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
 	hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
 	hull_triangles = BLI_ghash_ptr_new("hull_triangles");
 
-	/* Add tetrahedron triangles */
-	hull_add_tetrahedron(bm, hull_triangles, hull_pool, tetra);
+	hull_from_bullet(bm, op, hull_triangles, hull_pool);
 
-	/* Expand hull to cover new vertices outside the existing hull */
-	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
-		if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
-			GHash *outside = hull_triangles_v_outside(hull_triangles, v);
-			if (BLI_ghash_size(outside)) {
-				/* Expand hull and delete interior triangles */
-				add_point(bm, hull_triangles, hull_pool, edge_pool, outside, v);
-			}
-			BLI_ghash_free(outside, NULL, NULL);
-		}
-	}
-
-	BLI_mempool_destroy(edge_pool);
 	final_edges = hull_final_edges(hull_triangles);
 	
 	hull_mark_interior_elements(bm, op, final_edges);
@@ -762,3 +573,5 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 	BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
 	                                  HULL_FLAG_OUTPUT_GEOM);
 }
+
+#endif  /* WITH_BULLET */
diff --git a/source/blender/editors/mesh/CMakeLists.txt b/source/blender/editors/mesh/CMakeLists.txt
index 9aa3f3633f3..417cf92c29f 100644
--- a/source/blender/editors/mesh/CMakeLists.txt
+++ b/source/blender/editors/mesh/CMakeLists.txt
@@ -73,4 +73,8 @@ if(WITH_INTERNATIONAL)
 	add_definitions(-DWITH_INTERNATIONAL)
 endif()
 
+if(WITH_BULLET)
+    add_definitions(-DWITH_BULLET)
+endif()
+
 blender_add_lib(bf_editor_mesh "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/editors/mesh/SConscript b/source/blender/editors/mesh/SConscript
index 923bb3f9057..91ffdc91685 100644
--- a/source/blender/editors/mesh/SConscript
+++ b/source/blender/editors/mesh/SConscript
@@ -27,4 +27,7 @@ else:
 if env['WITH_BF_INTERNATIONAL']:
     defs.append('WITH_INTERNATIONAL')
 
+if env['WITH_BF_BULLET']:
+    defs.append('WITH_BULLET')
+
 env.BlenderLib ( 'bf_editors_mesh', sources, Split(incs), defs, libtype=['core'], priority=[45] )
diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c
index 90a7e2fe0ea..44933f6a1c0 100644
--- a/source/blender/editors/mesh/editmesh_tools.c
+++ b/source/blender/editors/mesh/editmesh_tools.c
@@ -5389,6 +5389,7 @@ void MESH_OT_wireframe(wmOperatorType *ot)
 	RNA_def_boolean(ot->srna, "use_replace",         TRUE, "Replace", "Remove original faces");
 }
 
+#ifdef WITH_BULLET
 static int edbm_convex_hull_exec(bContext *C, wmOperator *op)
 {
 	Object *obedit = CTX_data_edit_object(C);
@@ -5482,6 +5483,7 @@ void MESH_OT_convex_hull(wmOperatorType *ot)
 
 	join_triangle_props(ot);
 }
+#endif
 
 static int mesh_symmetrize_exec(bContext *C, wmOperator *op)
 {
diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c
index c4e8fd70989..864db7f096d 100644
--- a/source/blender/editors/mesh/mesh_ops.c
+++ b/source/blender/editors/mesh/mesh_ops.c
@@ -165,7 +165,9 @@ void ED_operatortypes_mesh(void)
 	WM_operatortype_append(MESH_OT_wireframe);
 	WM_operatortype_append(MESH_OT_edge_split);
 
+#ifdef WITH_BULLET
 	WM_operatortype_append(MESH_OT_convex_hull);
+#endif
 
 	WM_operatortype_append(MESH_OT_symmetrize);