Issue with many points on one plane

[BitingBum]

I was testing your algorithm on cube and 3d octagon and it found intersecting coplanar triangles in cube and invalid face in octagon
I changed one line in qh__face_can_see_vertex_epsilon
if (dot <= epsilon && dot >= 0)
to
if (dot <= epsilon && dot > 0)
and algorithm start working correctly

cube (with some points inside face)
0, 50, 0
100, 100, 0
0, 100, 0
-100, 100, 0
-100, 0, 0
100, -100, 0
0, -50, 0
50, -50, 0
-100, -100, 0
0, -100, 0
100, 0, 0
100, 100, 200
-100, 100, 200
100, -100, 200
-100, -100, 200

3d octagon (invalid face with points 8,7,14)
40, 100, 0
100, 40, 0
100, -40, 0
40, -100, 0
-40, -100, 0
-100, -40, 0
-100, 40, 0
-40, 100, 0
40, 100, 100
100, 40, 100
100, -40, 100
40, -100, 100
-40, -100, 100
-100, -40, 100
-100, 40, 100
-40, 100, 100

[GNSS-Stylist]

I also stumbled onto this issue while creating convex hulls of spheres (whose "point clouds" in addition to the surface also have a lot of randomized points inside for testing) having regular n-gons (n being 16-32) on their poles. Examples:


The other side of the previous one looks even worse around the other pole (where there's no n-gon as it has one (randomized) point inside):

Project (made with Qt, issue found by unit tests) where this happened can be currently found here: https://github.com/GNSS-Stylist/GNSS-Stylus/blob/develop/UnitTests/tst_convexhull.cpp , function TestConvexHull::randomSpheres(). Sources there have a workaround for this issue (single point on the pole / center of the n-gon), but it's commented if someone wants to recreate it.

The fix mentioned above also fixes my issue so thanks!

[GNSS-Stylist]

Looks like the fix mentioned above doesn't fix all cases. While randomizing points I still stumbled into one case where the generated hull is broken:

Source (including the points) generating the hull above and obj- and xyz point cloud-files:
3d-quickhull_bug.zip

3d-quickhull sources included in the zip already has the aforementioned fix applied.

This type of breakage seems to be very rare. In my case I generated 100 spheres and this was the only one that broke when the pseudorandom generator's initial state changed. And generating one random number before the test fixed it again.

I have no idea what's causing this type of breakage. Just for a test I tried to filter the points to be at least 0.001 units apart (in this case they are limited to around -20...20 units area, so precision of floats should be good enough), but this didn't change anything.

[karimnaaji]

@GNSS-Stylist thanks for the details on this one, I had a setup to iteratively visualize the hull generation process which can help narrow down exactly what step leads to degeneration. I will try to get that running again and investigate your degenerate case.

In the meantime we can already integrate your commit that fixes issues for points on the same plane.