algorithm - Algoritmo para generar una malla triangular a partir de una nube de puntos
geometry point (3)
En algún programa de simulación generamos superficies de objetos en términos de puntos, cada punto tiene coordenadas 3D y el vector que representa lo 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. Luego, 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.
Eche un vistazo al trabajo de Jonathan Shewchuk , especialmente en sus famosos documentos (junto con sus colegas) e implementaciones de:
También hay una implementación rápida de nubes de puntos sin clasificar implementadas en la biblioteca de nube de puntos (PCL). Compruebe su presentación en Triangulación rápida de nubes de puntos desordenadas .
Tenga en cuenta que las triangulaciones de Delaunay pueden no ser adecuadas para su aplicación, ya que las triangulaciones de Delaunay no son adecuadas para los verdaderos problemas 3D (es decir, donde los puntos están bien distribuidos en R3). Son más apropiados para múltiples problemas 2D (es decir, terreno, etc.).
Para generar superficies en R3, observe el trabajo de Hugues Hoppe y su trabajo de "reconstrucción de superficies".
La reconstrucción de la superficie se utiliza para encontrar una superficie mallada que se ajuste a la nube de puntos; sin embargo, este método produce altos conteos 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 mirar los métodos de reducción de OpenMesh.