# Surface mesh from labeled 3D points

I'm trying to figure out how to create a surface mesh from a set of labeled 3D points. The 3D object could be something like part of a cave system or asteroid where there would be parts of the surface not visible from looking on the outside. Each point has a radius and not all points are on the surface. The output should be a Nx3 matrix (coordinate matrix) and another matrix to represent the triangles of the mesh (as in the Libigl tutorial https://libigl.github.io/tutorial/). What algorithms are there to find the points on the surface and what algorithms can create meshes from 3D points with complicated pockets? A example 2D slice is below.

• Is it both the outer surface of a body and also surfaces of internal cavities in it? – Maxim Umansky Jul 8 '20 at 2:56
• I've updated the question to show a 2D slice example. It's just the outer surface with no internal cavities. – tapemagnet Jul 8 '20 at 14:13
• I would look into Delaunay triangulation for this, en.wikipedia.org/wiki/Delaunay_triangulation – Maxim Umansky Jul 8 '20 at 16:08
• I am copying these from wikipedia article "Surface Triangulation", so I am not going to put it as an answer. It looks like marching method is a good simple option and "E. Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN, p. 81", "E. Hartmann: A marching method for the triangulation of surfaces, The Visual Computer (1998), 14, pp. 95–108", "S. Akkouche & E Galin: Adaptive Implicit Surface Polygonization Using Marching Triangles, COMPUTER GRAPHICS forum (2001), Vol. 20, pp. 67–80" are some papers describe the method. – Abdullah Ali Sivas Jul 8 '20 at 16:19
• Also I found the following research report: cs.jhu.edu/~misha/Fall13b/Papers/Cazals06.pdf "Delaunay Triangulation Based Surface Reconstruction: Ideas and Algorithms" by Frederic Cazals and Joachim Giesen – Abdullah Ali Sivas Jul 8 '20 at 16:21