Marching Cubes

• Categoria: Sensing › 3D maps & reconstruction
• Tags: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface

Um algoritmo que extrai uma malha de triângulos de uma superfície a partir de uma grade 3D de valores escalares, como um campo de distância com sinal, processando a grade um cubo de cada vez.

Definição

Marching cubes transforma um campo escalar volumétrico em uma malha poligonal de um de seus conjuntos de nível, chamado isossuperfície. William Lorensen e Harvey Cline o publicaram no SIGGRAPH em 1987 para construir superfícies a partir de exames médicos como tomografia computadorizada (CT) e ressonância magnética (MRI). Hoje é a forma padrão de obter uma malha de um mapa de campo de distância com sinal truncado (TSDF), de uma grade de ocupação ou de um campo neural.

O algoritmo percorre cada cubo formado por oito amostras vizinhas da grade. Cada canto é classificado como dentro ou fora comparando seu valor com o isonível, que é zero para um campo de distância com sinal. Oito cantos binários dão 256 configurações, que a simetria reduz a um pequeno conjunto de casos básicos (15 no artigo original); uma tabela de consulta indica então quais arestas do cubo a superfície cruza e como unir os cruzamentos em triângulos. A posição de cada vértice ao longo de uma aresta cruzada é encontrada por interpolação linear entre os valores dos dois cantos, de modo que os vértices são posicionados com mais precisão que o espaçamento da grade. As normais da superfície costumam ser tiradas do gradiente do campo.

O método tem limitações conhecidas. Algumas configurações de cantos são ambíguas, e a tabela de casos original pode deixar buracos entre cubos vizinhos; variantes posteriores como o asymptotic decider e o Marching Cubes 33, ou o método relacionado marching tetrahedra, resolvem isso. Arestas e cantos vivos são arredondados, e é por isso que o dual contouring e métodos semelhantes, que usam informação de gradiente, são preferidos quando detalhes afiados importam. O detalhe e o tamanho da malha acompanham a resolução da grade: para um campo neural, a rede precisa primeiro ser avaliada em uma grade densa, e a malha resultante não pode ter mais detalhe que essa grade.

Por que importa

Sistemas de mapeamento e modelos de cena aprendidos armazenam a geometria como campos, enquanto ferramentas de visualização, motores de física, verificadores de colisão e softwares CAD esperam malhas. O marching cubes é a ponte habitual entre os dois, então sua resolução e seus artefatos moldam diretamente as malhas com que os robôs planejam e simulam.

Principais aplicações

• Extração de malhas de mapas TSDF em mapeamento denso com RGB-D e lidar
• Conversão de campos neurais de distância com sinal ou de ocupação em malhas
• Construção de malhas de colisão para simulação a partir de escaneamentos 3D
• Avaliação da qualidade da reconstrução em relação a malhas de referência (ground truth)
• Reconstrução de superfícies a partir de exames volumétricos médicos e industriais

Na prática

Uma equipe que roda mapeamento denso em um robô móvel funde quadros de uma câmera de profundidade em uma TSDF com tamanho de voxel de alguns centímetros. Em vez de refazer a malha do mapa inteiro a cada quadro, eles rodam o marching cubes apenas nos blocos cujos valores mudaram e transmitem a malha resultante para uma ferramenta de visualização do operador. No fim de uma sessão a malha completa é extraída, simplificada com dizimação de malha e carregada em um simulador como malha de colisão estática. Buracos na malha geralmente indicam espaço não observado ou truncamento na TSDF, e não uma falha do próprio marching cubes.

Equívocos comuns

• O marching cubes reconstrói uma superfície diretamente a partir de pontos brutos — ele precisa de um campo escalar em uma grade; os pontos devem primeiro ser fundidos em uma TSDF, uma grade de ocupação ou uma função implícita
• A malha não pode ser mais precisa que o tamanho do voxel — os vértices são interpolados ao longo das arestas dos cubos, então o posicionamento é mais fino que a grade, embora detalhes menores que um voxel ainda se percam
• O marching cubes sempre produz malhas estanques — a tabela de casos original tem casos ambíguos que podem deixar buracos, e a superfície fica aberta onde quer que o campo esteja truncado ou não tenha sido observado
• Arestas vivas saem vivas — o método arredonda os cantos; dual contouring e métodos relacionados são usados quando detalhes afiados importam

Quem deve saber

• Engenheiros de percepção que constroem mapas 3D densos a partir de sensores de profundidade
• Engenheiros de simulação que criam malhas de colisão a partir de escaneamentos
• Pesquisadores que trabalham com representações implícitas neurais de geometria

Tecnologias relacionadas

• Campo de distância com sinal truncado (Truncated Signed Distance Field, TSDF)
• Dual Contouring
• Marching Tetrahedra
• KinectFusion
• Open3D
• scikit-image

Termos relacionados

• Signed Distance Field
• Neural Implicit Representation
• Point Cloud
• SLAM
• Octree
• Neural Radiance Field

Projetos 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

Wikipédia

• Marching cubes