Mesh generation from points with x, y and z coordinates

Problem: Mesh generation from 3D points (with x, y and z coordinates).

What I have is points in 3D space (with x, y and z coordinates) you can see it in image 1.
What would be the output is image 2 or image 3, or image 4. In short it would be mesh. Material on it can be provided if I have the mesh.

I have seen many people say about Delaunay triangulations or constrained Delaunay triangulations will help me in mesh generation, but what I mostly found is its implementation in 2D points (with only x and Y coordinates).

But my problem is: I have points in 3D as you can see from image 1.

Will Delaunay triangulations or constrained Delaunay triangulations work fine with 3D Points? If yes, then how? Or do I have to find another algorithm for generating mesh from 3D points?

Note: One good explanation of Delaunay triangulations for 2D points can be found here

Solution 1:

here are some other good links for mesh generation and its related work.

• TetGen : A Quality Tetrahedral Mesh Generator http://wias-berlin.de/software/tetgen/

• CGal-Computational Geometry Algorithms Library http://www.cgal.org/. http://www.cgal.org/Manual/latest/doc_html/cgal_manual/packages.html#Pkg:Triangulation3. http://www.cgal.org/Manual/latest/doc_html/cgal_manual/contents.html#part_VI.
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Surface_reconstruction_points_3/Chapter_main.html.
3D Surface Mesh Generation - http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Surface_mesher/Chapter_main.html

• GTSLibrary – The GNU Triangulated Surface Library. http://gts.sourceforge.net/index.html

• Jonathan Shewchuk - http://www.cs.berkeley.edu/~jrs/ http://www.cs.cmu.edu/~quake/robust.html

• VTK: The Visualization Toolkit (VTK) is an open-source, freely available software system http://www.vtk.org/.

• Volume and Surface Meshing – http://www.cse.ohio-state.edu/~tamaldey/mesh.htm.

• Poly2Tri: An open source CDT library http://code.google.com/p/poly2tri/.

• CM2Mesh Tools – http://www.computing-objects.com/index.php.

• Adaptive tessellation – http://fluxionsdividebyzero.com/p1/math/geometry/g046.html#_3D

• CUBIT – The CUBIT Geometry and Mesh Generation Toolkit. http://cubit.sandia.gov/index.html

• Geometry in Action - http://www.ics.uci.edu/~eppstein/geom.html

• SlimDX - SlimDX is a free open source framework that enables developers to easily build DirectX applications using .NET technologies such as C#, VB http://slimdx.org/

Solution 2:

3D Delauny triangulation will result in a (3D) volume mesh. I suppose what you want is a (2D) surface mesh embedded in 3D which approximates the given point set.

Depending on the type of data (little or big noise, outliers, etc.) you can take different approaches. Note that you can always pre-process your data (e.g. to remove outliers, smooth the data, or estimate normals).

• For oriented point set with little noise and no outliers, you can consider Poisson Surface Reconstruction (e.g. in Michael Kazhdan, M. Bolitho, and Hugues Hoppe. Poisson Surface Reconstruction. In Symp. on Geometry Processing, pages 61-70, 2005.).
  Note that you can pre-process your data to fullfill the requirements, see for example Normal estimation. Here is a C++ library implementing Poisson Surface Reconstruction (with nice explanations): CGAL Surface Reconstruction from Point Sets

• For scattered point data see for example Ohtake, Y.; Belyaev, A. & Seidel, H. P. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions Shape Modeling International, 2003, 2003, 153-161. It uses a hierarchical approach to create multiple interpolation levels.

• Another approach for highly non-uniform or noisy scattered data is Zhao, H.-K.; Osher, S. & Fedkiw, R. Fast surface reconstruction using the level set method Variational and Level Set Methods in Computer Vision, 2001. Proceedings. IEEE Workshop on, 2001, 194-201. It uses variatonal methods and PDEs (particularly level set methods).

Solution 3:

ENigMA - Developed mostly to solve PDEs it also has a constrained surface and volume mesh generator. Still not sure if going to release it as open source in the future.

https://www.sites.google.com/site/billyaraujo/enigma/volume-mesh-generation