[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [48345] trunk/blender/source/blender/bmesh /operators/bmo_hull.c: Avoid adding overlapping triangles in convex hull

[Nicholas Bishop]

Revision: 48345
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=48345
Author:   nicholasbishop
Date:     2012-06-27 18:39:17 +0000 (Wed, 27 Jun 2012)
Log Message:
-----------
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

Modified Paths:
--------------
    trunk/blender/source/blender/bmesh/operators/bmo_hull.c

Modified: trunk/blender/source/blender/bmesh/operators/bmo_hull.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_hull.c	2012-06-27 18:29:47 UTC (rev 48344)
+++ trunk/blender/source/blender/bmesh/operators/bmo_hull.c	2012-06-27 18:39:17 UTC (rev 48345)
@@ -140,11 +140,14 @@
 
 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;
 }