Avoid adding overlapping triangles in convex hull

Add an epsilon value to the point-outside-hull test, helps when some
of the input vertices are nearly coplanar.

Fixes bug [#31941] convex hull fails (and depends on vertex order when it shouldn't)
http://projects.blender.org/tracker/index.php?func=detail&aid=31941&group_id=9&atid=498

1 files changed, 6 insertions, 3 deletions

diff --git a/source/blender/bmesh/operators/bmo_hull.c b/source/blender/bmesh/operators/bmo_hull.c
index 160db7cba75..cfff3d63ca1 100644
--- a/source/blender/bmesh/operators/bmo_hull.c
+++ b/source/blender/bmesh/operators/bmo_hull.c
@@ -140,11 +140,14 @@ static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *poo
 
 static int hull_point_tri_side(const HullTriangle *t, const float co[3])
 {
-	float p[3], d;
+	/* Added epsilon to fix bug [#31941], improves output when some
+	   vertices are nearly coplanar. Might need further tweaking for
+	   other cases though. */
+	float p[3], d, epsilon = 0.0001;
 	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;
+	if (d < -epsilon) return -1;
+	else if (d > epsilon) return 1;
 	else return 0;
 }