diff options
author | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-06-27 22:39:17 +0400 |
---|---|---|
committer | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-06-27 22:39:17 +0400 |
commit | f57c1c8b34f01bc7f03ab039dcb4058c655611e2 (patch) | |
tree | 0c6c89d30655a6769b65d233856e9426e8f37e04 /source/blender | |
parent | 32478997ec1fac6b155ffc1442312c4c33fd53df (diff) |
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
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/bmesh/operators/bmo_hull.c | 9 |
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; } |