Some lost cells of 3d Delaunay about hull-delaunay-voronoi HOT 4 CLOSED

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.

from hull-delaunay-voronoi.

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.

from hull-delaunay-voronoi.

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!

from hull-delaunay-voronoi.

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

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.

from hull-delaunay-voronoi.