Geração de malha de pontos com coordenadas x, ye z

Problema: Geração de malha a partir de pontos 3D (com coordenadas x, yez).

insira a descrição da imagem aqui

insira a descrição da imagem aqui

O que eu tenho são pontos no espaço 3D (com coordenadas x, yez) você pode ver na imagem 1.
Qual seria a saída é a imagem 2 ou imagem 3 ou imagem 4. Em suma, seria malha. Material sobre ele pode ser fornecido se eu tiver malha.

Eu tenho visto muitas pessoas falarem sobre triangulações de Delaunay ou triangulações de Delaunay restritas irão me ajudar na geração de malha, mas o que eu mais encontrei é sua implementação em pontos 2D (com apenas coordenadas x e Y).

Mas meu problema é: eu tenho pontos em 3D como você pode ver na imagem 1.

As triangulações de Delaunay ou as triangulações de Delaunay limitadas funcionam bem com os pontos 3D? Se sim, então como? Ou eu tenho que encontrar outro algoritmo para gerar malha de pontos 3D?

Nota: Uma boa explicação sobre triangulações de Delaunay para pontos 2D pode ser encontrada aqui

Aqui estão alguns outros bons links para geração de malha e seu trabalho relacionado.

TetGen: Um Gerador de Malhas Tetraédrico de Qualidade http://wias-berlin.de/software/tetgen/

CGal – Biblioteca de Algoritmos de Geometria Computacional 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 .
Geração de malha de superfície 3D – http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Surface_mesher/Chapter_main.html

GTSLibrary – A Biblioteca de Superfícies Trianguladas GNU. http://gts.sourceforge.net/index.html

Jonathan Shewchukhttp://www.cs.berkeley.edu/~jrs/ http://www.cs.cmu.edu/~quake/robust.html

VTK: O Visualization Toolkit (VTK) é um sistema de software livre e de código aberto http://www.vtk.org/ .

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

Poly2Tri: Uma biblioteca de CDT de código aberto http://code.google.com/p/poly2tri/ .

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

Mosaico adaptativo – http://fluxionsdividebyzero.com/p1/math/geometry/g046.html#_3D

CUBIT – O kit de ferramentas de geometry e geração de malha CUBIT. http://cubit.sandia.gov/index.html

Geometria em Ação – http://www.ics.uci.edu/~eppstein/geom.html

SlimDX – SlimDX é uma estrutura livre de código aberto que permite aos desenvolvedores criar facilmente aplicativos DirectX usando tecnologias .NET como C #, VB http://slimdx.org/

A triangulação 3D Delauny resultará em uma malha de volume (3D). Suponho que o que você deseja é uma malha de superfície (2D) incorporada em 3D que se aproxime do conjunto de pontos fornecido.

Dependendo do tipo de dados (ruído pequeno ou grande, outliers, etc.), você pode adotar diferentes abordagens. Observe que você sempre pode pré-processar seus dados (por exemplo, para remover valores discrepantes, suavizar os dados ou estimar valores normais).

  • Para um conjunto de pontos orientados com pouco ruído e nenhum valor discrepante, você pode considerar a Reconstrução de Superfície de Poisson (por exemplo, em Michael Kazhdan, M. Bolitho e Hugues Hoppe. Reconstrução de Superfície de Poisson. Em Symp. Em Processamento de Geometria, páginas 61-70, 2005 ). .
    Observe que você pode pré-processar seus dados para preencher os requisitos, consulte, por exemplo, estimativa Normal . Aqui está uma biblioteca C ++ implementando a Reconstrução de Superfície de Poisson (com boas explicações): Reconstrução de Superfície CGAL de Conjuntos de Pontos

  • Para dados de pontos dispersos, ver por exemplo Ohtake, Y .; Belyaev, A. & Seidel, HP Uma abordagem multi-escala para a interpolação de dados 3D dispersos com funções de base compactamente suportadas Shape Modeling International, 2003, 2003, 153-161 . Ele usa uma abordagem hierárquica para criar vários níveis de interpolação.

  • Outra abordagem para dados dispersos altamente não uniformes ou ruidosos é Zhao, H.-K .; Osher, S. & Fedkiw, R. Reconstrução rápida da superfície usando o método de ajuste de níveis Variational and Level Set Methods em Computer Vision, 2001. Proceedings. Oficina IEEE em 2001, 194-201 . Ele usa methods variados e PDEs (particularmente methods de conjunto de níveis).

ENIGMA – Desenvolvido principalmente para resolver PDEs, também possui um gerador de malha de superfície e volume restrito. Ainda não tenho certeza se vai lançá-lo como código aberto no futuro.

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