This project is read-only.

Input vertex degeneracy

Oct 24, 2013 at 5:05 AM

I posted a few months back. I would like to generate a convex hull around a point cloud but I think I am getting degeneracy issues. It might be because some of the points are equidistant apart, I tried to add some noise to the input but I still receive the same problem. Do you have any thoughts on a potential solution?

Oct 24, 2013 at 5:58 PM
Hey, could you please also include the input data? (enough to provide new[] { new[] { X, Y, Z}, ... })
Oct 25, 2013 at 12:43 PM
Dave, Thanks for taking this on. I'm still a bit confused by the recycling of faces approach. My guess is that we may have a mistake in there. I noted as well that the resulting tessellated shape violates Euler's operator equation - the number of vertices should equal the number of faces divided by two plus two (V = F/2 + 2). Not sure this helps us find the bug though.
Oct 25, 2013 at 1:44 PM
Matt, the face recycling is just to save some work for the garbage collector.

I have played with the 3DConvexHullWPF example. Here are my observations:
  • Rnd Uniform: operator holds (convexHull.Points.Count() == convexHull.Faces.Count() / 2 + 2)
  • Rnd on Sphere: operator hold
  • Regular Grid: operator breaks
So I did more digging. If I use convexHull.Faces.SelectMany(f => f.Vertices).Distinct().Count() to count the hull vertices, the operator suddenly holds. Moreover, if I add even tiny amount of noise to the regular grid data (in the order of 1e-5 where the vertex indices are integers), the operator holds again.

After some digging I have found the bug that causes V != F/2 + 2. It is in the CommitCone() function. Due to the "degeneracy" (ie. too many points lying on the same plane) it might happen that the condition
if (newFace.VerticesBeyond.Count == 0)
does not hold for any new face, but the ConvexHull.Add(CurrentVertex); is still executed anyway. So the fix is to check if any new face was added to the hull in the CommitCone() function and only add the vertex to the hull if that is the case.

To know exactly what's going on with Damian's problem I would have to see the data. Tho I still think that properly adding the noise would solve his problem.
Oct 25, 2013 at 1:58 PM
I have played it with a bit more and the fix does not work exactly like I thought it would -- now it adds too few vertices instead of too many.

So perhaps a safer bet would be to use Vertices = Faces.SelectMany(f => f.Vertices).Distinct() before the hull is returned.

Moreover, I wonder if the information that if (newFace.VerticesBeyond.Count == 0) holds for no "new" faces could be somehow used to construct a better hull in the degenerate case.
Oct 28, 2013 at 11:51 PM
Well, I have solved some of the degeneracy issues in the latest push. However, I still don't know how to solve triangulation of points on a sphere (and perhaps some other cases I don't know about as well :)). Nevertheless, adding the noise seems to solve the problem for me.