网格生成从点与x, y和z坐标。

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

问题:网格生成从三维点(x, y和z坐标)。

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 provide if I have mesh.

我所拥有的是三维空间中的点(x, y, z坐标)，你可以在图1中看到。输出是图像2或图像3或图像4。简而言之，它就是网格。如果我有网格，可以提供材料。

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

我见过很多人说Delaunay triangulations或约束Delaunay triangulations会在网格生成中帮助我，但我主要发现的是它在2D点上的实现(只有x和Y坐标)。

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

但我的问题是:我有3D的点，你可以从图1中看到。

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

Delaunay triangulations或受限的Delaunay triangulations可以在三维点上正常工作吗?如果是的,那么如何?或者我是否需要找到另一种算法来从3D点生成网格?

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

注:在这里可以找到对Delaunay三角测量的一个很好的解释。

3 个解决方案

#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/

一种高质量的四面体网格发生器，http://wiasberlin.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

•cgal -计算几何算法图书馆http://www.cgal.org/。http://www.cgal.org/Manual/latest/doc_html/cgal_manual/packages.html包裹: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表面网格生成- 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

•GTSLibrary - GNU三角表面图书馆。http://gts.sourceforge.net/index.html

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

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

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

可视化工具包(VTK)是一个开源的、免费的软件系统http://www.vtk.org/。

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

•体积和表面啮合- http://www.cse.ohiostate.edu/~ tamaldey/mesh.htm。

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

•Poly2Tri:一个开源的CDT库http://code.google.com/p/poly2tri/。

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

•CM2Mesh工具- http://www.computing-objects.com/index.php。

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

•自适应的棋盘格- http://fluxionsdividebyzero.com/p1/math/geometry/g046.html#_3D。

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

•CUBIT - CUBIT几何体和网格生成工具箱。http://cubit.sandia.gov/index.html

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

•行动的几何学- http://www.ics.uci.edu/~eppstein/地。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/

slidx - SlimDX是一个免费的开源框架，开发者可以使用。net技术(如c#， VB http://slimdx.org/)轻松构建DirectX应用程序。

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

3D Delauny三角测量将产生一个(3D)体积网格。我猜你想要的是一个嵌入3D的(2D)曲面网格，它近似于给定的点集。

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

  对于没有噪声且没有异常值的定向点集，可以考虑泊松表面重构(例如:Michael Kazhdan, M. Bolitho，和Hugues Hoppe)。泊松表面重建。在计算机协会。关于几何处理，第61-70页，2005年。注意，您可以预先处理您的数据以满足需求，如正常估计。这是一个c++库实现泊松曲面重构(有很好的解释):从点集的CGAL表面重建。

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

  对于散乱点的数据，请参见。多尺度的三维散射数据插值方法，基于紧凑支持的基函数形状建模国际，2003,2003,153-161。它使用分层的方法来创建多个插值级别。

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

  另一种高度不均匀或噪声分散的方法是赵，h - k。利用计算机视觉中的水平集方法变分和水平集方法进行快速曲面重构。程序。IEEE研讨会，2001,194-201。它使用变量方法和PDEs(特别是水平集方法)。

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

ENigMA主要是用来解决PDEs的，它也有一个受约束的表面和体积网格发生器。仍然不确定是否会在将来发布它作为开源。

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

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