algoritmo robusto para la reconstrucción de la superficie a partir de nubes de puntos 3D?

StackOverflow https://stackoverflow.com/questions/838761

Pregunta

Estoy tratando de averiguar lo que los algoritmos no son para hacer la reconstrucción de la superficie de 3D rango de datos.A primera vista, parece que el Bola giratoria algoritmo (BPA) y Poisson reconstrucción de la superficie son las más métodos establecidos?

  • ¿Cuáles son los establecidos, más robusto algoritmo en el campo distinto de BPA y de Poisson de la superficie algoritmo de reconstrucción?
  • Se recomienda publicaciones de investigación?
  • Hay disponible el código fuente?
¿Fue útil?

Solución

He enfrentado este dilema durante algunos meses y he realizado 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 es powercrust , porque está teóricamente bien establecido: garantiza una malla estanca.

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

Funciones implícitas

Uno ajusta las funciones implícitas en la nube de puntos, luego usa un algoritmo similar a un cubo de marcha 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 de esta categoría. Si eres nuevo en el tema, te recomiendo leer la tesis de Hoppe, es muy explicativo.

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

Implementaciones

Encontrará un pequeño número de implementaciones gratuitas. Sin embargo, depende de si lo va a integrar en software libre (en este caso, la licencia GPL es aceptable para usted) o en un software comercial (en este caso necesita una licencia más liberal). Esto ú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.

Echa un vistazo a esta implementación de Poisson, y luego comparte tu experiencia al respecto conmigo, por favor.

También: aquí 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 módulo dedicado a la reconstrucción de superficies y está en desarrollo activo (y forma 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 su datos de puntos, esta funcionalidad se puede encontrar en las funciones módulo . 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.

Otros consejos

Si desea hacer algunos experimentos directos con varios algoritmos de reconstrucción de la superficie que usted debe tratar de MeshLab, la malla del sistema de procesamiento, es de código abierto y contiene implementaciones de muchos de los anteriormente citados de la superficie de algoritmos de reconstrucción, como:

  • Poisson Superficie Recon
  • un par de MLS enfoque basado en los
  • una bola giratoria de implementación
  • una variante de la Curless volumen enfoque basado en
  • Delaunay técnicas basadas en (Alfa y formas de Voronoi de filtrado)
  • herramientas para calcular las normales de la dispersión de punto conjuntos
  • y muchas otras herramientas para comparar/medición/limpieza/simplificación de las mallas resultantes.

Las fuentes están protegidos por la licencia GPL, por lo que no podían hacer uso de ellos en un comercial de código cerrado el proyecto, pero es muy importante para conseguir la sensación de derecho sobre las propiedades de los distintos algoritmos de reconstrucción de la superficie (cómo de sensible al ruido que son, la velocidad, la resistencia a los valores atípicos, cómo se conservan los detalles más finos, etc, etc) antes de empezar a implementar uno de ellos.

Puede comenzar a mirar algunos trabajos recientes en el campo, actualmente algo así como Reconstrucción rápida MLS con poca memoria en streaming de superficies muestreadas por puntos por Gianmauro Cuccuru, Enrico Gobbetti, Fabio Marton, Renato Pajarola y Ruggero Pintus. Sus citas pueden ayudarlo a revisar la literatura rápidamente.

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:

Enlace

¿Alguien lo intentó?

No estoy seguro de si es exactamente el adecuado para su caso, ya que parece extraño que lo haya omitido, pero marchando cubos se menciona comúnmente en casos como estos.

Aquí en GitHub, es un código abierto Biblioteca de procesamiento de mallas en C ++ por Dr. Hugues Hoppe , en el que el programa de reconstrucción de superficie Recon es una buena opción para su problema ...

Hay herramienta 3D Delaunay de Geometric Tools . Esta herramienta se usa DirecX y OpenGL. Desafortunadamente, es posible que necesite comprar un libro para ver el código de ejemplo real de la biblioteca. Todavía lees el código y te das cuenta.

Matlab también introdujo una herramienta de reconstrucción de superficie usando Delaunay, delaunayTriangulation class .

Como también tuve este problema, desarrollé e implementé mi propio algoritmo de 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 puede ayudarte. También puede encontrar un breve script de Python en la página que ilustra cómo usar la biblioteca. ¡Diviértete!

Quizás le interese Alpha Shapes .

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top