Mesh generation from points with x, y and z coordinates

algorithm geometry 3d delaunay
Pritesh picture Pritesh · Feb 3, 2011 · Viewed 43.1k times · Source

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

enter image description here

enter image description here

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

Answer

Pritesh picture Pritesh · Feb 4, 2011

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/

Related questions

Triangle Triangle Intersection in 3d-Space

I'm working with some 3d geometry. I need to find the intersection of triangle with another triangle. What algorithm could I use?

Read More
How to check if a point is inside an ellipsoid?

We have a point in three dimensional space and an ellipsoid centered at the point of origin. The ellipsoid is upstanding meaning there is no rotation applied. It has three different radii, or how you call it for an ellipsoid. …

Read More
Equation for testing if a point is inside a circle

If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?

Read More