Some lost cells of 3d Delaunay

[dnnkeeper]

I'm trying to make free Unity LightProbe placement extension and stuck with finding adjacent probes for a given one. Unity Light Probes uses Delaunay tetrahedralisation to find adjacent probes as I could understand (https://www.gdcvault.com/play/1015522/Light-Probe-Interpolation-Using-Tetrahedral) so I tried using your code to find matching probes from a list of all probes in a group. It worked almost like it should! But in some cases some cells gets lost for some reason.
I attached the script I used for testing and a GIF representing the issue. I'll appreciate if you could point out where to look for solution. Then I'll be able to release some free lightprobe placement tool :)

LightProbeGroupDelaunau.txt

[Scrawk]

I’m not sure. could be a bug. I don’t see anything wrong with your code. Try the original MIConvex hull project and see if it has the same issue.

[Scrawk]

Delaunay cell dont form around the edges sometimes as there might not be enough vertices close by.

You need to add a 8 more verts that make up the corners of a bounding box that encloses your current verts. Once you find the hull you can then ignore any simplex that has a vertex that belongs to the box.

[zmorris]

Unfortunately adding a bounding box of vertices still doesn't fix the problem with the most recent release. I've tried various sets of random vertices, and outsetting the bounding box, but no matter what I do, usually a handful are missing per every 10 or so, so the triangulation leaves gaps (even before ignoring any that touch the bounding vertices).

I thought it was maybe an issue with how I traversed the cells. I tried logging all Cell.Simplex and Cell.Simplex.Adjacen and some of the Id are not there. There are even some vertex ids missing from the resulting delaunay.Vertices even though it should match the original list that I passed to DelaunayTriangulation3.Generate() exactly. So it appears to be operating over the wrong vertex list from the start internally.

This could be a flaw in my approach, like perhaps I'm supposed to combine this somehow with a convex hull to derive all the cells? But since some of the interior vertices are missing, I don't think that is the case.

I feel like this could perhaps be a subtle difference between this project and MIConvexHull but I don't know what it would be. Maybe it's related to an issue like #2 ? Until this is fixed, I wouldn't recommend using Hull-Delaunay-Voronoi for 3D Delaunay triangulation since I lost a few days to this issue, unfortunately. Other than that, it seems really promising!

[zmorris]

Scrawk replied to my issue so I'll just paste the possible workaround here also:

---

Hey thanks for your quick response on this. Ya I've been looking through MIConvex Hull and might adapt it for my use case.

For anyone who finds this, I think the problem is maybe due to

Hull-Delaunay-Voronoi/Assets/HullDelaunayVoronoi/Scripts/Hull/ConvexHull.cs

Line 33 in 514465e

private const float PLANE_DISTANCE_TOLERANCE = 1e-7f;

For a test triangulating random vertices in a cube with bounds +/- 1, when I try values like 1e-1f through 1e-6f it seems to work. Although curiously a tolerance of 1 or larger seems to fail, as well as 1e-7f or smaller.

So a viable heuristic might be to set the tolerance to about 1/10,000th the largest vertex axis extent in the mesh around its center. It would also be nice if that constant was changed to an optional parameter.

Hope this helps someone.