Issue with many points on one plane

[BitingBum]

trafficstars

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/b5d28ba5c30bc0a76b98427871fd10d17b8d9602/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!

Edit: Updated the link to unit tests to point to specific commit as the files changed afterwards.

[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.

[GNSS-Stylist]

Found a lot simpler problematic shape while randomly rotating rectangular cuboids: Red cuboid is the problematic one, green is the same shape in a different angle (mesh for it is also generated with 3d-quickhull).

Points generating the broken mesh (can be copy-pasted to the main.cpp found in my previous message):

qh_vertex_t vertices[] =
{
    {   -3.0012702992169213,    4.43013053449861,       -0.8459784447958123 },
    {   -3.8907708074140266,    14.250979827381919,     11.38491831100901	},
    {   8.430575024286357,      2.1030941122589777,     1.8539140394637963  },
    {   7.541074516089251,      11.923943405142285,     14.084810795268618	},
    {   -4.27546998821548,      1.133826236523765,      1.7081357045333831  },
    {   -5.164970496412586,     10.954675529407073,     13.939032460338204  },
    {   7.156375335287798,      -1.1932101857158681,    4.408028188792992   },
    {   6.266874827090692,      8.62763910716744,       16.638924944597814  },
};

Tried with and without the fix mentioned above, both versions generated identical meshes.

Tested also by changing all floats to doubles in quickhull.h and both meshes (this and the sphere above) were fixed.