1

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.

Nick Rivers
  • 11
  • 2
  • possible duplicate of [Triangulate a surface with vtk from points AND normals](http://stackoverflow.com/questions/14062401/triangulate-a-surface-with-vtk-from-points-and-normals) – finnw Jan 28 '13 at 20:08
  • 1
    I think this is a similar question, but I'm not limited to vtk. It does seem @Alejandro had a similar objective to me. However, I'm being strict with the notion that a "reconstruction" approach (treating the points as approximate) is not what I'm after, and Alejandro was willing to consider something like Point Cloud Library whereas I'm not. – Nick Rivers Jan 28 '13 at 20:49
  • 1
    Is your 3D body convex? The convex hull of your set of points will be a polyhedron, and each face of that polyhedron could be triangulated using a Delaunay triangulation. But if your body is not convex, there would be some interior points which would not be used at all. If you have such interior points, then this solution will not work, and in general the body will not be unambiguously described by the points. Perhaps http://stackoverflow.com/q/8023301/1468366 might provide some useful pointers for that case. – MvG Jan 28 '13 at 22:02
  • I highly recommend you figure out Qhull because it is a nightmare to write your own triangulation. Also Qhull has a C++ interface and is extremely fast, it was built by a group of computational scientists and has gone through several years of optimization. This is one wheel you do not need to re-invent! And yes you can set Qhull to only use the input points without adding or omitting points, in fact that's the default on the version I'm using. – Adam Cadien Jan 29 '13 at 04:41
  • @MvG: The 3D body is always at least star-convex. For practical purposes, let's say the body is essentially a kind of tube; each cross-section of the tube is guaranteed to be a simple polygon, star-convex. The "axis" of the tube (the line made by connecting the centroids of each cross-section) forms a very gently-curved line that never knots, curves steeply or back on itself, etc. – Nick Rivers Jan 29 '13 at 16:25
  • @AdamCadien I agree completely; I really don't want to write my own code to generate the mesh. I presently do generate my own mesh, but I now need to add some features, and my existing code is complex and brittle. My area of expertise is not computational geometry, and I'm sure my methods are excessively ad-hoc, so I'd rather start to rely on the expertise of others in the field. In my response to Irineau below, there are some links to SO posts where caveats to Delaunay in 3D are mentioned. – Nick Rivers Jan 29 '13 at 16:49

1 Answers1

0

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.

lrineau
  • 6,036
  • 3
  • 34
  • 47
  • The magnitude is between 15000 - 25000 points. I hope I've clarified the issue of convexity in my comment to MvG above. I think the surface construction from the points should be unambiguous. Some comments I saw regarding Delaunay in 3D were in SO posts such as: http://stackoverflow.com/questions/7879160/algorithm-for-generating-a-triangular-mesh-from-a-cloud-of-points and http://stackoverflow.com/questions/7879160/algorithm-for-generating-a-triangular-mesh-from-a-cloud-of-points . Thanks for the mention of the 3D alpha shapes, I hadn't heard of that before. – Nick Rivers Jan 29 '13 at 16:33
  • Well, I disagree with the comment on that other thread. In my company GeometryFactory we solve a lot of 3D problems with tools that use 3D Delaunay triangulations. – lrineau Feb 06 '13 at 09:29