From f57c1c8b34f01bc7f03ab039dcb4058c655611e2 Mon Sep 17 00:00:00 2001 From: Nicholas Bishop Date: Wed, 27 Jun 2012 18:39:17 +0000 Subject: 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 --- source/blender/bmesh/operators/bmo_hull.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'source/blender/bmesh') 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; } -- cgit v1.2.3