3D triangular surface mesh generation using only the exact input points as vertices

Question

I have number of points from an exact numerical solution that constitute the surface of a smooth 3D body. These points already satisfy smoothness criteria and contain no noise (other than double-precision roundoff error). I now need to generate a triangular mesh from these points for physical simulation software.

Two aspects of this question different from the questions already asked on SO:

• The triangulation should use exactly the prescribed input points and only the prescribed points, without interpolation, without adding or omitting any points, "joggling", etc. It seems this type of question has been asked several times in the context of "point clouds", where the input points represent approximate locations on the surface, but my coordinates are exact.
• There are a number of mentions of Delaunay triangulation in 3d, but also mentions of caveats, and that Delaunay triangulation is not considered "optimal" for 3d.

Are there recommendations for open source libraries or algorithms that can generate some form of high-quality 3d triangulation (ultra-rigorous optimality guarantees not necessary, but some form of quality objective would be good) that retain only (and all) the vertices prescribed and don't treat this as a sampling and reconstruction problem?

Implementations in one (or more) of: C, OCaml, C++, or Python would be appreciated. I have found Qhull: http://www.qhull.org/ (also used in SciPy's scipy.spatial), but it looks like it does only Delaunay triangle generation and has a somewhat confusing bevy of options such that I'm not sure it can satisfy my first constraint.

Answer 1

What is the magnitude of the size of set of points? Are they in convex position, or mostly in convex position? What sort of surface do you want to reconstruct?

The 3D alpha shapes component of CGAL looks like a good tool to reconstruct a mesh from your points. It is licensed under GPLv3+. It does use 3D Delaunay triangulations, though. I wonder what caveat you are talking about. It depends on the type of point cloud you have.