49

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

1
  • 2
    3D delaunay (I assume you want tetrahedra, not that you're trying to fit a surface) is very very very very ill conditioned and almost impossible to get right robustly. Actually, the problem is less with the algorithm than with the typical data which is fed to it. Feb 4, 2011 at 14:20

3 Answers 3

32

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/

23

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).

4
  • Thank you so much for your replying, after seeing link you provide i had hope that i will found solution.
    – Pritesh
    Feb 3, 2011 at 7:23
  • 1
    please put here another good link if possible, because this question may become the best answer for many people.. Thanks...
    – Pritesh
    Feb 3, 2011 at 9:06
  • 2
    This method will work only if the points are oriented - i.e. they have a normal. OP doesn't specify whether this is the case or not. If the points are unoriented, the references in the cited paper might point to alternative methods.
    – brainjam
    Feb 3, 2011 at 23:15
  • 1
    True. However, you can pre-process your data and estimate the normals. I edited my answer to clarify this. Thanks.
    – Sascha
    Feb 3, 2011 at 23:55
1

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

1
  • I would suggest including more detail, if possible, and a project that uses this. Is there an open source fork available? Try posting that as well.
    – user3373470
    Aug 5, 2015 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.