Problem case

[bjnortier]

I have an example where the quickhull is not as expected (I'm not sure if I'm doing something wrong), and end up with holes and degenerate faces.

I created a fork of the gh-pages branch to illustrate the problem. The fork is here:
https://github.com/bjnortier/quickhull/tree/degenerate-hull

Here's the original:

And the hull:

[marklundin]

Ah yes. That's not right at all. Something very wrong going on there. I'll take a look to see what's happening. There doesn't seem to be anything strange in your geometry.

[kintel]

Another instance of this can be seen here, with the old three.js ConvexGeometry as reference:
http://codepen.io/kintel/pen/GpxOyE

[donmccurdy]

Not sure what geometry is involved in the first issue, but the problem @kintel points out is fixable. It's not exactly elegant:

var EPS = 1e-4;

// Perturb.
for (i = 0; i < geometry.vertices.length; i++) {
  geometry.vertices[i].x += (Math.random() - 0.5) * EPS;
  geometry.vertices[i].y += (Math.random() - 0.5) * EPS;
  geometry.vertices[i].z += (Math.random() - 0.5) * EPS;
}

// Compute the 3D convex hull.
hull = quickhull(geometry);

I can't quite remember why this works, but I think there's a plane-sweep along some axis (x, in this case?) and if several points have the same x coordinate there's a chance of non-deterministic results. Rare in "real-world" data, but pretty common in 3D models.