Marching Cubes
- Categoría: Sensing › 3D maps & reconstruction
- Etiquetas: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface
Un algoritmo que extrae una malla de triángulos de una superficie a partir de una rejilla 3D de valores escalares, como un campo de distancia con signo, procesando la rejilla cubo a cubo.
Definición
Marching cubes convierte un campo escalar volumétrico en una malla poligonal de uno de sus conjuntos de nivel, llamado isosuperficie. William Lorensen y Harvey Cline lo publicaron en SIGGRAPH en 1987 para construir superficies a partir de exploraciones médicas como la tomografía computarizada (CT) y la resonancia magnética (MRI). Hoy es la forma estándar de obtener una malla de un mapa de campo de distancia con signo truncado (TSDF), una rejilla de ocupación o un campo neuronal.
El algoritmo recorre cada cubo formado por ocho muestras vecinas de la rejilla. Cada vértice del cubo se clasifica como dentro o fuera comparando su valor con el isonivel, que es cero para un campo de distancia con signo. Ocho esquinas binarias dan 256 configuraciones, que la simetría reduce a un pequeño conjunto de casos base (15 en el artículo original); una tabla de consulta indica entonces qué aristas del cubo cruza la superficie y cómo unir los cruces en triángulos. La posición de cada vértice a lo largo de una arista cruzada se obtiene por interpolación lineal entre los valores de las dos esquinas, de modo que los vértices se sitúan con más finura que el espaciado de la rejilla. Las normales de la superficie suelen tomarse del gradiente del campo.
El método tiene limitaciones conocidas. Algunas configuraciones de esquinas son ambiguas, y la tabla de casos original puede dejar agujeros entre cubos vecinos; variantes posteriores como el asymptotic decider y Marching Cubes 33, o el método relacionado marching tetrahedra, lo resuelven. Las aristas y esquinas vivas se redondean, y por eso se prefieren dual contouring y métodos similares, que usan información del gradiente, cuando importan los rasgos afilados. El detalle y el tamaño de la malla siguen la resolución de la rejilla: para un campo neuronal, primero hay que evaluar la red en una rejilla densa, y la malla resultante no puede tener más detalle que esa rejilla.
Por qué importa
Los sistemas de mapeo y los modelos de escena aprendidos almacenan la geometría como campos, mientras que las herramientas de visualización, los motores de física, los comprobadores de colisiones y el software CAD esperan mallas. Marching cubes es el puente habitual entre ambos, así que su resolución y sus artefactos determinan directamente las mallas con las que los robots planifican y simulan.
Aplicaciones clave
- Extracción de mallas de mapas TSDF en el mapeo denso con RGB-D y lidar
- Conversión de campos neuronales de distancia con signo o de ocupación en mallas
- Construcción de mallas de colisión para simulación a partir de escaneos 3D
- Evaluación de la calidad de la reconstrucción frente a mallas de referencia (ground truth)
- Reconstrucción de superficies a partir de exploraciones volumétricas médicas e industriales
En la práctica
Un equipo que ejecuta mapeo denso en un robot móvil fusiona los fotogramas de una cámara de profundidad en una TSDF con un tamaño de vóxel de unos pocos centímetros. En lugar de volver a generar la malla de todo el mapa tras cada fotograma, ejecutan marching cubes solo en los bloques cuyos valores han cambiado y envían en streaming la malla resultante a una herramienta de visualización para el operador. Al final de una sesión se extrae la malla completa, se simplifica con diezmado de malla y se carga en un simulador como malla de colisión estática. Los agujeros en la malla suelen indicar espacio no observado o truncamiento en la TSDF, más que un fallo del propio marching cubes.
Ideas erróneas comunes
- Marching cubes reconstruye una superficie directamente a partir de puntos en bruto — necesita un campo escalar en una rejilla; los puntos deben fusionarse antes en una TSDF, una rejilla de ocupación o una función implícita
- La malla no puede ser más precisa que el tamaño del vóxel — los vértices se interpolan a lo largo de las aristas de los cubos, así que su colocación es más fina que la rejilla, aunque los rasgos más pequeños que un vóxel siguen perdiéndose
- Marching cubes siempre produce mallas estancas — la tabla de casos original tiene casos ambiguos que pueden dejar agujeros, y la superficie queda abierta allí donde el campo está truncado o no se ha observado
- Las aristas vivas salen vivas — el método redondea las esquinas; dual contouring y métodos relacionados se usan cuando importan los rasgos afilados
Quién debería saberlo
- Ingenieros de percepción que construyen mapas 3D densos a partir de sensores de profundidad
- Ingenieros de simulación que crean mallas de colisión a partir de escaneos
- Investigadores que trabajan con representaciones implícitas neuronales de la geometría
Tecnologías relacionadas
- Campo de distancia con signo truncado (Truncated Signed Distance Field, TSDF)
- Dual Contouring
- Marching Tetrahedra
- KinectFusion
- Open3D
- scikit-image
Términos relacionados
Proyectos relacionados
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
Vídeos
- Coding Adventure: Marching Cubes: Sebastian Lague
- Mesh from Math - The basics of Marching Cubes: Deadlock