Algoritmo para generar una malla triangular a partir de una nube de puntos

Question

En algún programa de simulación generamos superficies de objeto en términos de puntos, cada punto tiene coordenadas 3D y el vector que representa la normal a la superficie en ese punto. Para fines de visualización, nos gustaría generar una malla compuesta de triángulos; cada tres puntos cercanos forman un triángulo con su normal. A continuación, podemos enviar esta información a algunos programas de visualización estándar que representan la superficie como VMD (Visual Molecular Dynamics).

Nos preguntamos cuál es el algoritmo más rápido/disponible para hacer esto.

Answer 1

Tome un vistazo a Jonathan Shewchuk 's de trabajo, sobre todo en sus (junto con sus colegas) famosos papeles e implementaciones de:

• Streaming Computation of Delaunay Triangulations

• A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator

Hay también es una implementación rápida de nubes de puntos sin clasificar implementadas en Point Cloud Library (PCL). Verifique su presentación en Fast triangulation of unordered point clouds.

Answer 2

El algoritmo poisson de Misha Kazhdan podría funcionar bien en sus datos. Su página de software es here. Tenga en cuenta que también existe una versión CGAL. Manual es here y demo de Windows lista para usar here (siempre que haya instalado estos dlls).

Answer 3

Tenga en cuenta que las triangulaciones de Delaunay pueden no adaptarse a su aplicación, ya que las triangulaciones de Delaunay no son adecuadas para problemas reales en 3D (es decir, donde los puntos están bien distribuidos en R3). Son más apropiados para problemas de múltiples en 2D (es decir, terreno, etc.).

Para generar superficies en R3, observe el trabajo de Hugues Hoppe y su trabajo de "reconstrucción de superficie".

La reconstrucción de superficie se utiliza para encontrar una superficie mallada que se ajuste a la nube de puntos; sin embargo, este método produce recuentos altos de triángulos. Si esto es un problema, puede aplicar una técnica de reducción de malla para reducir el recuento de polígonos de forma que se minimice el error. Como ejemplo, puedes ver los métodos de aniquilación de OpenMesh.

Hugues Hoppe

OpenMesh