algorithm - topografia - nubes de tetrahedrons




algoritmo robusto para la reconstrucción de la superficie de la nube de puntos 3D? (6)

Estoy tratando de averiguar qué algoritmos hay para hacer la reconstrucción de la superficie a partir de datos de rango 3D. A primera vista, parece que el algoritmo de pivote Ball ( BPA ) y la reconstrucción de la superficie de Poisson son los métodos más establecidos?

  • ¿Cuáles son los algoritmos más robustos y establecidos en el campo que no sean el algoritmo de reconstrucción de superficie BPA y Poisson?
  • ¿Publicaciones de investigación recomendadas?
  • ¿Hay código fuente disponible?

Aunque no es una representación de malla, un ex colega me recomendó este enlace al código fuente para un método Thin Plate Spline:

Link

¿Alguien lo intentó?


Como también tuve este problema, desarrollé e implementé mi propio algoritmo de la corteza de nube de puntos. Las fuentes y la documentación se pueden encontrar en github.com: https://github.com/ricebean-net/PointCloudCrust . El algoritmo se implementa en Java.

Tal vez esto pueda ayudarle. También puede encontrar un breve script de python en la página que ilustra cómo usar la biblioteca. ¡Que te diviertas!


He estado enfrentando este dilema durante algunos meses y realicé una investigación exhaustiva.

Algoritmos

Principalmente hay 2 categorías de algoritmos: geometría de cálculo y superficies implícitas.

Geometría de Computación

Se ajustan a la malla en los puntos existentes.

Probablemente el algoritmo más famoso de este grupo sea el powercrust , porque está teóricamente bien establecido: garantiza una malla hermética.

Ball Pivoting está patentado por IBM. Además, no es adecuado para nubes puntuales con densidad de puntos variable.

Funciones implícitas

Uno se ajusta a las funciones implícitas en la nube de puntos, luego utiliza un algoritmo de estilo de cubo de marchas para extraer el conjunto cero de la función en una malla.

Los métodos en esta categoría difieren principalmente por las diferentes funciones implícitas utilizadas.

Poisson , Hoppe's y MPU son los algoritmos más famosos en esta categoría. Si eres nuevo en el tema, recomiendo leer la tesis de Hoppe, es muy explicativo.

Los algoritmos de esta categoría generalmente se pueden implementar para que puedan procesar enormes entradas de manera muy eficiente, y se puede escalar su relación de calidad <-> velocidad. No les molesta el ruido, la densidad de punto variable, los agujeros. Una desventaja de ellos es que requieren superficies normales orientadas consistentemente en los puntos de entrada.

Implementaciones

Encontrará una pequeña cantidad de implementaciones gratuitas. Sin embargo, depende de si vas a integrarlo en el software libre (en este caso, la licencia GPL es aceptable para ti) o en un software comercial (en este caso, necesitas una licencia más liberal). Este último es muy raro.

Uno está en VTK . Sospecho que es difícil de integrar (no hay documentación disponible de forma gratuita), tiene una arquitectura extraña y demasiado complicada, y no está diseñada para aplicaciones de alto rendimiento. También tiene algunas limitaciones para los puntos de entrada permitidos.

Eche un vistazo a this implementación de Poisson, y luego comparta su experiencia al respecto conmigo por favor.

Además: here hay algunos algoritmos de alto rendimiento, con reconstrucción de superficie entre ellos.

CGAL es una famosa biblioteca en 3D, pero es gratuita solo para proyectos gratuitos. Meshlab es una aplicación famosa con GPL.

También (Agregado en agosto de 2013): La biblioteca PCL tiene un module dedicado a la reconstrucción de superficies y está en desarrollo activo (y es parte del Summer of Code de Google). El módulo de superficie contiene varios algoritmos diferentes para la reconstrucción. PCL también tiene la capacidad de estimar las normales de superficie, en caso de que no las tenga provistas con sus datos de punto, esta funcionalidad se puede encontrar en el module características. PCL se publica bajo los términos de la licencia BSD y es un software de código abierto, es gratuito para uso comercial y de investigación.


No estoy seguro de si es exactamente lo correcto para su caso, ya que parece extraño que lo haya omitido, pero los cubos de marcha se mencionan comúnmente en casos como estos.


Si desea realizar algunos experimentos directos con varios algoritmos de reconstrucción de superficie, debe probar Meshlab , el sistema de procesamiento de malla, es de código abierto y contiene implementaciones de muchos de los algoritmos de reconstrucción de superficie citados anteriormente, como:

  • Poisson Surface Recon
  • un par de enfoques basados ​​en MLS,
  • una implementación de pivote de bola
  • una variante del enfoque basado en el volumen de Curless
  • Técnicas basadas en Delaunay (formas Alpha y filtrado Voronoi)
  • herramientas para calcular normales a partir de conjuntos de puntos dispersos
  • y muchas otras herramientas para comparar / medir / limpiar / simplificar las mallas resultantes.

Las fuentes están protegidas por GPL, por lo que no podrías usarlas en un proyecto de fuente cerrada comercial, pero es muy importante tener la sensación correcta sobre las propiedades de los diversos algoritmos de reconstrucción de superficie (qué tan sensibles son al ruido, la velocidad, la robustez a valores atípicos, cómo conservan detalles finos, etc.) antes de comenzar a implementar uno de ellos.






computational-geometry